Home | History | Annotate | Download | only in optimizing 
      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:
     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 
     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