1 /* 2 * Copyright (C) 2014 The Android Open Source Project 3 * 4 * Licensed under the Apache License, Version 2.0 (the "License"); 5 * you may not use this file except in compliance with the License. 6 * You may obtain a copy of the License at 7 * 8 * http://www.apache.org/licenses/LICENSE-2.0 9 * 10 * Unless required by applicable law or agreed to in writing, software 11 * distributed under the License is distributed on an "AS IS" BASIS, 12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13 * See the License for the specific language governing permissions and 14 * limitations under the License. 15 */ 16 17 #ifndef ART_COMPILER_OPTIMIZING_SSA_BUILDER_H_ 18 #define ART_COMPILER_OPTIMIZING_SSA_BUILDER_H_ 19 20 #include "nodes.h" 21 #include "optimization.h" 22 23 namespace art { 24 25 static constexpr int kDefaultNumberOfLoops = 2; 26 27 /** 28 * Transforms a graph into SSA form. The liveness guarantees of 29 * this transformation are listed below. A DEX register 30 * being killed means its value at a given position in the code 31 * will not be available to its environment uses. A merge in the 32 * following text is materialized as a `HPhi`. 33 * 34 * (a) Dex registers that do not require merging (that is, they do not 35 * have different values at a join block) are available to all their 36 * environment uses. Note that it does not imply the instruction will 37 * have a physical location after register allocation. See the 38 * SsaLivenessAnalysis phase. 39 * 40 * (b) Dex registers that require merging, and the merging gives 41 * incompatible types, will be killed for environment uses of that merge. 42 * 43 * (c) When the `debuggable` flag is passed to the compiler, Dex registers 44 * that require merging and have a proper type after the merge, are 45 * available to all their environment uses. If the `debuggable` flag 46 * is not set, values of Dex registers only used by environments 47 * are killed. 48 */ 49 class SsaBuilder : public HGraphVisitor { 50 public: SsaBuilder(HGraph * graph)51 explicit SsaBuilder(HGraph* graph) 52 : HGraphVisitor(graph), 53 current_locals_(nullptr), 54 loop_headers_(graph->GetArena(), kDefaultNumberOfLoops), 55 locals_for_(graph->GetArena(), graph->GetBlocks().Size()) { 56 locals_for_.SetSize(graph->GetBlocks().Size()); 57 } 58 59 void BuildSsa(); 60 GetLocalsFor(HBasicBlock * block)61 GrowableArray<HInstruction*>* GetLocalsFor(HBasicBlock* block) { 62 GrowableArray<HInstruction*>* locals = locals_for_.Get(block->GetBlockId()); 63 if (locals == nullptr) { 64 locals = new (GetGraph()->GetArena()) GrowableArray<HInstruction*>( 65 GetGraph()->GetArena(), GetGraph()->GetNumberOfVRegs()); 66 locals->SetSize(GetGraph()->GetNumberOfVRegs()); 67 locals_for_.Put(block->GetBlockId(), locals); 68 } 69 return locals; 70 } 71 72 HInstruction* ValueOfLocal(HBasicBlock* block, size_t local); 73 74 void VisitBasicBlock(HBasicBlock* block); 75 void VisitLoadLocal(HLoadLocal* load); 76 void VisitStoreLocal(HStoreLocal* store); 77 void VisitInstruction(HInstruction* instruction); 78 void VisitTemporary(HTemporary* instruction); 79 80 static HInstruction* GetFloatOrDoubleEquivalent(HInstruction* user, 81 HInstruction* instruction, 82 Primitive::Type type); 83 84 static HInstruction* GetReferenceTypeEquivalent(HInstruction* instruction); 85 86 static constexpr const char* kSsaBuilderPassName = "ssa_builder"; 87 88 private: 89 void FixNullConstantType(); 90 void EquivalentPhisCleanup(); 91 92 static HFloatConstant* GetFloatEquivalent(HIntConstant* constant); 93 static HDoubleConstant* GetDoubleEquivalent(HLongConstant* constant); 94 static HPhi* GetFloatDoubleOrReferenceEquivalentOfPhi(HPhi* phi, Primitive::Type type); 95 96 // Locals for the current block being visited. 97 GrowableArray<HInstruction*>* current_locals_; 98 99 // Keep track of loop headers found. The last phase of the analysis iterates 100 // over these blocks to set the inputs of their phis. 101 GrowableArray<HBasicBlock*> loop_headers_; 102 103 // HEnvironment for each block. 104 GrowableArray<GrowableArray<HInstruction*>*> locals_for_; 105 106 DISALLOW_COPY_AND_ASSIGN(SsaBuilder); 107 }; 108 109 } // namespace art 110 111 #endif // ART_COMPILER_OPTIMIZING_SSA_BUILDER_H_ 112