Home | History | Annotate | Download | only in ir
      1 /*
      2  * Copyright (C) 2013 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 #include "base/stringprintf.h"
     17 #include "sea_ir/ir/instruction_tools.h"
     18 #include "sea_ir/ir/sea.h"
     19 #include "sea_ir/code_gen/code_gen.h"
     20 #include "sea_ir/types/type_inference.h"
     21 
     22 #define MAX_REACHING_DEF_ITERERATIONS (10)
     23 // TODO: When development is done, this define should not
     24 // be needed, it is currently used as a cutoff
     25 // for cases where the iterative fixed point algorithm
     26 // does not reach a fixed point because of a bug.
     27 
     28 namespace sea_ir {
     29 
     30 int SeaNode::current_max_node_id_ = 0;
     31 
     32 void IRVisitor::Traverse(Region* region) {
     33   std::vector<PhiInstructionNode*>* phis = region->GetPhiNodes();
     34   for (std::vector<PhiInstructionNode*>::const_iterator cit = phis->begin();
     35       cit != phis->end(); cit++) {
     36     (*cit)->Accept(this);
     37   }
     38   std::vector<InstructionNode*>* instructions = region->GetInstructions();
     39   for (std::vector<InstructionNode*>::const_iterator cit = instructions->begin();
     40       cit != instructions->end(); cit++) {
     41     (*cit)->Accept(this);
     42   }
     43 }
     44 
     45 void IRVisitor::Traverse(SeaGraph* graph) {
     46   for (std::vector<Region*>::const_iterator cit = ordered_regions_.begin();
     47           cit != ordered_regions_.end(); cit++ ) {
     48     (*cit)->Accept(this);
     49   }
     50 }
     51 
     52 SeaGraph* SeaGraph::GetGraph(const art::DexFile& dex_file) {
     53   return new SeaGraph(dex_file);
     54 }
     55 
     56 void SeaGraph::AddEdge(Region* src, Region* dst) const {
     57   src->AddSuccessor(dst);
     58   dst->AddPredecessor(src);
     59 }
     60 
     61 void SeaGraph::ComputeRPO(Region* current_region, int& current_rpo) {
     62   current_region->SetRPO(VISITING);
     63   std::vector<sea_ir::Region*>* succs = current_region->GetSuccessors();
     64   for (std::vector<sea_ir::Region*>::iterator succ_it = succs->begin();
     65       succ_it != succs->end(); ++succ_it) {
     66     if (NOT_VISITED == (*succ_it)->GetRPO()) {
     67       SeaGraph::ComputeRPO(*succ_it, current_rpo);
     68     }
     69   }
     70   current_region->SetRPO(current_rpo--);
     71 }
     72 
     73 void SeaGraph::ComputeIDominators() {
     74   bool changed = true;
     75   while (changed) {
     76     changed = false;
     77     // Entry node has itself as IDOM.
     78     std::vector<Region*>::iterator crt_it;
     79     std::set<Region*> processedNodes;
     80     // Find and mark the entry node(s).
     81     for (crt_it = regions_.begin(); crt_it != regions_.end(); ++crt_it) {
     82       if ((*crt_it)->GetPredecessors()->size() == 0) {
     83         processedNodes.insert(*crt_it);
     84         (*crt_it)->SetIDominator(*crt_it);
     85       }
     86     }
     87     for (crt_it = regions_.begin(); crt_it != regions_.end(); ++crt_it) {
     88       if ((*crt_it)->GetPredecessors()->size() == 0) {
     89         continue;
     90       }
     91       // NewIDom = first (processed) predecessor of b.
     92       Region* new_dom = NULL;
     93       std::vector<Region*>* preds = (*crt_it)->GetPredecessors();
     94       DCHECK(NULL != preds);
     95       Region* root_pred = NULL;
     96       for (std::vector<Region*>::iterator pred_it = preds->begin();
     97           pred_it != preds->end(); ++pred_it) {
     98         if (processedNodes.end() != processedNodes.find((*pred_it))) {
     99           root_pred = *pred_it;
    100           new_dom = root_pred;
    101           break;
    102         }
    103       }
    104       // For all other predecessors p of b, if idom is not set,
    105       // then NewIdom = Intersect(p, NewIdom)
    106       for (std::vector<Region*>::const_iterator pred_it = preds->begin();
    107           pred_it != preds->end(); ++pred_it) {
    108         DCHECK(NULL != *pred_it);
    109         // if IDOMS[p] != UNDEFINED
    110         if ((*pred_it != root_pred) && (*pred_it)->GetIDominator() != NULL) {
    111           DCHECK(NULL != new_dom);
    112           new_dom = SeaGraph::Intersect(*pred_it, new_dom);
    113         }
    114       }
    115       DCHECK(NULL != *crt_it);
    116       if ((*crt_it)->GetIDominator() != new_dom) {
    117         (*crt_it)->SetIDominator(new_dom);
    118         changed = true;
    119       }
    120       processedNodes.insert(*crt_it);
    121     }
    122   }
    123 
    124   // For easily ordering of regions we need edges dominator->dominated.
    125   for (std::vector<Region*>::iterator region_it = regions_.begin();
    126       region_it != regions_.end(); region_it++) {
    127     Region* idom = (*region_it)->GetIDominator();
    128     if (idom != *region_it) {
    129       idom->AddToIDominatedSet(*region_it);
    130     }
    131   }
    132 }
    133 
    134 Region* SeaGraph::Intersect(Region* i, Region* j) {
    135   Region* finger1 = i;
    136   Region* finger2 = j;
    137   while (finger1 != finger2) {
    138     while (finger1->GetRPO() > finger2->GetRPO()) {
    139       DCHECK(NULL != finger1);
    140       finger1 = finger1->GetIDominator();  // should have: finger1 != NULL
    141       DCHECK(NULL != finger1);
    142     }
    143     while (finger1->GetRPO() < finger2->GetRPO()) {
    144       DCHECK(NULL != finger2);
    145       finger2 = finger2->GetIDominator();  // should have: finger1 != NULL
    146       DCHECK(NULL != finger2);
    147     }
    148   }
    149   return finger1;  // finger1 should be equal to finger2 at this point.
    150 }
    151 
    152 void SeaGraph::ComputeDownExposedDefs() {
    153   for (std::vector<Region*>::iterator region_it = regions_.begin();
    154         region_it != regions_.end(); region_it++) {
    155       (*region_it)->ComputeDownExposedDefs();
    156     }
    157 }
    158 
    159 void SeaGraph::ComputeReachingDefs() {
    160   // Iterate until the reaching definitions set doesn't change anymore.
    161   // (See Cooper & Torczon, "Engineering a Compiler", second edition, page 487)
    162   bool changed = true;
    163   int iteration = 0;
    164   while (changed && (iteration < MAX_REACHING_DEF_ITERERATIONS)) {
    165     iteration++;
    166     changed = false;
    167     // TODO: optimize the ordering if this becomes performance bottleneck.
    168     for (std::vector<Region*>::iterator regions_it = regions_.begin();
    169         regions_it != regions_.end();
    170         regions_it++) {
    171       changed |= (*regions_it)->UpdateReachingDefs();
    172     }
    173   }
    174   DCHECK(!changed) << "Reaching definitions computation did not reach a fixed point.";
    175 }
    176 
    177 void SeaGraph::InsertSignatureNodes(const art::DexFile::CodeItem* code_item, Region* r) {
    178   // Insert a fake SignatureNode for the first parameter.
    179   // TODO: Provide a register enum value for the fake parameter.
    180   SignatureNode* parameter_def_node = new sea_ir::SignatureNode(0, 0);
    181   AddParameterNode(parameter_def_node);
    182   r->AddChild(parameter_def_node);
    183   // Insert SignatureNodes for each Dalvik register parameter.
    184   for (unsigned int crt_offset = 0; crt_offset < code_item->ins_size_; crt_offset++) {
    185     int register_no = code_item->registers_size_ - crt_offset - 1;
    186     int position = crt_offset + 1;
    187     SignatureNode* parameter_def_node = new sea_ir::SignatureNode(register_no, position);
    188     AddParameterNode(parameter_def_node);
    189     r->AddChild(parameter_def_node);
    190   }
    191 }
    192 
    193 void SeaGraph::BuildMethodSeaGraph(const art::DexFile::CodeItem* code_item,
    194     const art::DexFile& dex_file, uint16_t class_def_idx,
    195     uint32_t method_idx, uint32_t method_access_flags) {
    196   code_item_ = code_item;
    197   class_def_idx_ = class_def_idx;
    198   method_idx_ = method_idx;
    199   method_access_flags_ = method_access_flags;
    200   const uint16_t* code = code_item->insns_;
    201   const size_t size_in_code_units = code_item->insns_size_in_code_units_;
    202   // This maps target instruction pointers to their corresponding region objects.
    203   std::map<const uint16_t*, Region*> target_regions;
    204   size_t i = 0;
    205   // Pass: Find the start instruction of basic blocks
    206   //         by locating targets and flow-though instructions of branches.
    207   while (i < size_in_code_units) {
    208     const art::Instruction* inst = art::Instruction::At(&code[i]);
    209     if (inst->IsBranch() || inst->IsUnconditional()) {
    210       int32_t offset = inst->GetTargetOffset();
    211       if (target_regions.end() == target_regions.find(&code[i + offset])) {
    212         Region* region = GetNewRegion();
    213         target_regions.insert(std::pair<const uint16_t*, Region*>(&code[i + offset], region));
    214       }
    215       if (inst->CanFlowThrough()
    216           && (target_regions.end() == target_regions.find(&code[i + inst->SizeInCodeUnits()]))) {
    217         Region* region = GetNewRegion();
    218         target_regions.insert(
    219             std::pair<const uint16_t*, Region*>(&code[i + inst->SizeInCodeUnits()], region));
    220       }
    221     }
    222     i += inst->SizeInCodeUnits();
    223   }
    224 
    225 
    226   Region* r = GetNewRegion();
    227 
    228   InsertSignatureNodes(code_item, r);
    229   // Pass: Assign instructions to region nodes and
    230   //         assign branches their control flow successors.
    231   i = 0;
    232   sea_ir::InstructionNode* last_node = NULL;
    233   sea_ir::InstructionNode* node = NULL;
    234   while (i < size_in_code_units) {
    235     const art::Instruction* inst = art::Instruction::At(&code[i]);
    236     std::vector<InstructionNode*> sea_instructions_for_dalvik =
    237         sea_ir::InstructionNode::Create(inst);
    238     for (std::vector<InstructionNode*>::const_iterator cit = sea_instructions_for_dalvik.begin();
    239         sea_instructions_for_dalvik.end() != cit; ++cit) {
    240       last_node = node;
    241       node = *cit;
    242 
    243       if (inst->IsBranch() || inst->IsUnconditional()) {
    244         int32_t offset = inst->GetTargetOffset();
    245         std::map<const uint16_t*, Region*>::iterator it = target_regions.find(&code[i + offset]);
    246         DCHECK(it != target_regions.end());
    247         AddEdge(r, it->second);  // Add edge to branch target.
    248       }
    249       std::map<const uint16_t*, Region*>::iterator it = target_regions.find(&code[i]);
    250       if (target_regions.end() != it) {
    251         // Get the already created region because this is a branch target.
    252         Region* nextRegion = it->second;
    253         if (last_node->GetInstruction()->IsBranch()
    254             && last_node->GetInstruction()->CanFlowThrough()) {
    255           AddEdge(r, it->second);  // Add flow-through edge.
    256         }
    257         r = nextRegion;
    258       }
    259       r->AddChild(node);
    260     }
    261     i += inst->SizeInCodeUnits();
    262   }
    263 }
    264 
    265 void SeaGraph::ComputeRPO() {
    266   int rpo_id = regions_.size() - 1;
    267   for (std::vector<Region*>::const_iterator crt_it = regions_.begin(); crt_it != regions_.end();
    268       ++crt_it) {
    269     if ((*crt_it)->GetPredecessors()->size() == 0) {
    270       ComputeRPO(*crt_it, rpo_id);
    271     }
    272   }
    273 }
    274 
    275 // Performs the renaming phase in traditional SSA transformations.
    276 // See: Cooper & Torczon, "Engineering a Compiler", second edition, page 505.)
    277 void SeaGraph::RenameAsSSA() {
    278   utils::ScopedHashtable<int, InstructionNode*> scoped_table;
    279   scoped_table.OpenScope();
    280   for (std::vector<Region*>::iterator region_it = regions_.begin(); region_it != regions_.end();
    281       region_it++) {
    282     if ((*region_it)->GetIDominator() == *region_it) {
    283       RenameAsSSA(*region_it, &scoped_table);
    284     }
    285   }
    286   scoped_table.CloseScope();
    287 }
    288 
    289 void SeaGraph::ConvertToSSA() {
    290   // Pass: find global names.
    291   // The map @block maps registers to the blocks in which they are defined.
    292   std::map<int, std::set<Region*> > blocks;
    293   // The set @globals records registers whose use
    294   // is in a different block than the corresponding definition.
    295   std::set<int> globals;
    296   for (std::vector<Region*>::iterator region_it = regions_.begin(); region_it != regions_.end();
    297       region_it++) {
    298     std::set<int> var_kill;
    299     std::vector<InstructionNode*>* instructions = (*region_it)->GetInstructions();
    300     for (std::vector<InstructionNode*>::iterator inst_it = instructions->begin();
    301         inst_it != instructions->end(); inst_it++) {
    302       std::vector<int> used_regs = (*inst_it)->GetUses();
    303       for (std::size_t i = 0; i < used_regs.size(); i++) {
    304         int used_reg = used_regs[i];
    305         if (var_kill.find(used_reg) == var_kill.end()) {
    306           globals.insert(used_reg);
    307         }
    308       }
    309       const int reg_def = (*inst_it)->GetResultRegister();
    310       if (reg_def != NO_REGISTER) {
    311         var_kill.insert(reg_def);
    312       }
    313 
    314       blocks.insert(std::pair<int, std::set<Region*> >(reg_def, std::set<Region*>()));
    315       std::set<Region*>* reg_def_blocks = &(blocks.find(reg_def)->second);
    316       reg_def_blocks->insert(*region_it);
    317     }
    318   }
    319 
    320   // Pass: Actually add phi-nodes to regions.
    321   for (std::set<int>::const_iterator globals_it = globals.begin();
    322       globals_it != globals.end(); globals_it++) {
    323     int global = *globals_it;
    324     // Copy the set, because we will modify the worklist as we go.
    325     std::set<Region*> worklist((*(blocks.find(global))).second);
    326     for (std::set<Region*>::const_iterator b_it = worklist.begin();
    327         b_it != worklist.end(); b_it++) {
    328       std::set<Region*>* df = (*b_it)->GetDominanceFrontier();
    329       for (std::set<Region*>::const_iterator df_it = df->begin(); df_it != df->end(); df_it++) {
    330         if ((*df_it)->InsertPhiFor(global)) {
    331           // Check that the dominance frontier element is in the worklist already
    332           // because we only want to break if the element is actually not there yet.
    333           if (worklist.find(*df_it) == worklist.end()) {
    334             worklist.insert(*df_it);
    335             b_it = worklist.begin();
    336             break;
    337           }
    338         }
    339       }
    340     }
    341   }
    342   // Pass: Build edges to the definition corresponding to each use.
    343   // (This corresponds to the renaming phase in traditional SSA transformations.
    344   // See: Cooper & Torczon, "Engineering a Compiler", second edition, page 505.)
    345   RenameAsSSA();
    346 }
    347 
    348 void SeaGraph::RenameAsSSA(Region* crt_region,
    349     utils::ScopedHashtable<int, InstructionNode*>* scoped_table) {
    350   scoped_table->OpenScope();
    351   // Rename phi nodes defined in the current region.
    352   std::vector<PhiInstructionNode*>* phis = crt_region->GetPhiNodes();
    353   for (std::vector<PhiInstructionNode*>::iterator phi_it = phis->begin();
    354       phi_it != phis->end(); phi_it++) {
    355     int reg_no = (*phi_it)->GetRegisterNumber();
    356     scoped_table->Add(reg_no, (*phi_it));
    357   }
    358   // Rename operands of instructions from the current region.
    359   std::vector<InstructionNode*>* instructions = crt_region->GetInstructions();
    360   for (std::vector<InstructionNode*>::const_iterator instructions_it = instructions->begin();
    361       instructions_it != instructions->end(); instructions_it++) {
    362     InstructionNode* current_instruction = (*instructions_it);
    363     // Rename uses.
    364     std::vector<int> used_regs = current_instruction->GetUses();
    365     for (std::vector<int>::const_iterator reg_it = used_regs.begin();
    366         reg_it != used_regs.end(); reg_it++) {
    367       int current_used_reg = (*reg_it);
    368       InstructionNode* definition = scoped_table->Lookup(current_used_reg);
    369       current_instruction->RenameToSSA(current_used_reg, definition);
    370     }
    371     // Update scope table with latest definitions.
    372     std::vector<int> def_regs = current_instruction->GetDefinitions();
    373     for (std::vector<int>::const_iterator reg_it = def_regs.begin();
    374             reg_it != def_regs.end(); reg_it++) {
    375       int current_defined_reg = (*reg_it);
    376       scoped_table->Add(current_defined_reg, current_instruction);
    377     }
    378   }
    379   // Fill in uses of phi functions in CFG successor regions.
    380   const std::vector<Region*>* successors = crt_region->GetSuccessors();
    381   for (std::vector<Region*>::const_iterator successors_it = successors->begin();
    382       successors_it != successors->end(); successors_it++) {
    383     Region* successor = (*successors_it);
    384     successor->SetPhiDefinitionsForUses(scoped_table, crt_region);
    385   }
    386 
    387   // Rename all successors in the dominators tree.
    388   const std::set<Region*>* dominated_nodes = crt_region->GetIDominatedSet();
    389   for (std::set<Region*>::const_iterator dominated_nodes_it = dominated_nodes->begin();
    390       dominated_nodes_it != dominated_nodes->end(); dominated_nodes_it++) {
    391     Region* dominated_node = (*dominated_nodes_it);
    392     RenameAsSSA(dominated_node, scoped_table);
    393   }
    394   scoped_table->CloseScope();
    395 }
    396 
    397 CodeGenData* SeaGraph::GenerateLLVM(const std::string& function_name,
    398     const art::DexFile& dex_file) {
    399   // Pass: Generate LLVM IR.
    400   CodeGenPrepassVisitor code_gen_prepass_visitor(function_name);
    401   std::cout << "Generating code..." << std::endl;
    402   Accept(&code_gen_prepass_visitor);
    403   CodeGenVisitor code_gen_visitor(code_gen_prepass_visitor.GetData(),  dex_file);
    404   Accept(&code_gen_visitor);
    405   CodeGenPostpassVisitor code_gen_postpass_visitor(code_gen_visitor.GetData());
    406   Accept(&code_gen_postpass_visitor);
    407   return code_gen_postpass_visitor.GetData();
    408 }
    409 
    410 CodeGenData* SeaGraph::CompileMethod(
    411     const std::string& function_name,
    412     const art::DexFile::CodeItem* code_item, uint16_t class_def_idx,
    413     uint32_t method_idx, uint32_t method_access_flags, const art::DexFile& dex_file) {
    414   // Two passes: Builds the intermediate structure (non-SSA) of the sea-ir for the function.
    415   BuildMethodSeaGraph(code_item, dex_file, class_def_idx, method_idx, method_access_flags);
    416   // Pass: Compute reverse post-order of regions.
    417   ComputeRPO();
    418   // Multiple passes: compute immediate dominators.
    419   ComputeIDominators();
    420   // Pass: compute downward-exposed definitions.
    421   ComputeDownExposedDefs();
    422   // Multiple Passes (iterative fixed-point algorithm): Compute reaching definitions
    423   ComputeReachingDefs();
    424   // Pass (O(nlogN)): Compute the dominance frontier for region nodes.
    425   ComputeDominanceFrontier();
    426   // Two Passes: Phi node insertion.
    427   ConvertToSSA();
    428   // Pass: type inference
    429   ti_->ComputeTypes(this);
    430   // Pass: Generate LLVM IR.
    431   CodeGenData* cgd = GenerateLLVM(function_name, dex_file);
    432   return cgd;
    433 }
    434 
    435 void SeaGraph::ComputeDominanceFrontier() {
    436   for (std::vector<Region*>::iterator region_it = regions_.begin();
    437       region_it != regions_.end(); region_it++) {
    438     std::vector<Region*>* preds = (*region_it)->GetPredecessors();
    439     if (preds->size() > 1) {
    440       for (std::vector<Region*>::iterator pred_it = preds->begin();
    441           pred_it != preds->end(); pred_it++) {
    442         Region* runner = *pred_it;
    443         while (runner != (*region_it)->GetIDominator()) {
    444           runner->AddToDominanceFrontier(*region_it);
    445           runner = runner->GetIDominator();
    446         }
    447       }
    448     }
    449   }
    450 }
    451 
    452 Region* SeaGraph::GetNewRegion() {
    453   Region* new_region = new Region();
    454   AddRegion(new_region);
    455   return new_region;
    456 }
    457 
    458 void SeaGraph::AddRegion(Region* r) {
    459   DCHECK(r) << "Tried to add NULL region to SEA graph.";
    460   regions_.push_back(r);
    461 }
    462 
    463 SeaGraph::SeaGraph(const art::DexFile& df)
    464     :ti_(new TypeInference()), class_def_idx_(0), method_idx_(0),  method_access_flags_(),
    465      regions_(), parameters_(), dex_file_(df), code_item_(NULL) { }
    466 
    467 void Region::AddChild(sea_ir::InstructionNode* instruction) {
    468   DCHECK(instruction) << "Tried to add NULL instruction to region node.";
    469   instructions_.push_back(instruction);
    470   instruction->SetRegion(this);
    471 }
    472 
    473 SeaNode* Region::GetLastChild() const {
    474   if (instructions_.size() > 0) {
    475     return instructions_.back();
    476   }
    477   return NULL;
    478 }
    479 
    480 void Region::ComputeDownExposedDefs() {
    481   for (std::vector<InstructionNode*>::const_iterator inst_it = instructions_.begin();
    482       inst_it != instructions_.end(); inst_it++) {
    483     int reg_no = (*inst_it)->GetResultRegister();
    484     std::map<int, InstructionNode*>::iterator res = de_defs_.find(reg_no);
    485     if ((reg_no != NO_REGISTER) && (res == de_defs_.end())) {
    486       de_defs_.insert(std::pair<int, InstructionNode*>(reg_no, *inst_it));
    487     } else {
    488       res->second = *inst_it;
    489     }
    490   }
    491   for (std::map<int, sea_ir::InstructionNode*>::const_iterator cit = de_defs_.begin();
    492       cit != de_defs_.end(); cit++) {
    493     (*cit).second->MarkAsDEDef();
    494   }
    495 }
    496 
    497 const std::map<int, sea_ir::InstructionNode*>* Region::GetDownExposedDefs() const {
    498   return &de_defs_;
    499 }
    500 
    501 std::map<int, std::set<sea_ir::InstructionNode*>* >* Region::GetReachingDefs() {
    502   return &reaching_defs_;
    503 }
    504 
    505 bool Region::UpdateReachingDefs() {
    506   std::map<int, std::set<sea_ir::InstructionNode*>* > new_reaching;
    507   for (std::vector<Region*>::const_iterator pred_it = predecessors_.begin();
    508       pred_it != predecessors_.end(); pred_it++) {
    509     // The reaching_defs variable will contain reaching defs __for current predecessor only__
    510     std::map<int, std::set<sea_ir::InstructionNode*>* > reaching_defs;
    511     std::map<int, std::set<sea_ir::InstructionNode*>* >* pred_reaching =
    512         (*pred_it)->GetReachingDefs();
    513     const std::map<int, InstructionNode*>* de_defs = (*pred_it)->GetDownExposedDefs();
    514 
    515     // The definitions from the reaching set of the predecessor
    516     // may be shadowed by downward exposed definitions from the predecessor,
    517     // otherwise the defs from the reaching set are still good.
    518     for (std::map<int, InstructionNode*>::const_iterator de_def = de_defs->begin();
    519         de_def != de_defs->end(); de_def++) {
    520       std::set<InstructionNode*>* solo_def;
    521       solo_def = new std::set<InstructionNode*>();
    522       solo_def->insert(de_def->second);
    523       reaching_defs.insert(
    524           std::pair<int const, std::set<InstructionNode*>*>(de_def->first, solo_def));
    525     }
    526     reaching_defs.insert(pred_reaching->begin(), pred_reaching->end());
    527 
    528     // Now we combine the reaching map coming from the current predecessor (reaching_defs)
    529     // with the accumulated set from all predecessors so far (from new_reaching).
    530     std::map<int, std::set<sea_ir::InstructionNode*>*>::iterator reaching_it =
    531         reaching_defs.begin();
    532     for (; reaching_it != reaching_defs.end(); reaching_it++) {
    533       std::map<int, std::set<sea_ir::InstructionNode*>*>::iterator crt_entry =
    534           new_reaching.find(reaching_it->first);
    535       if (new_reaching.end() != crt_entry) {
    536         crt_entry->second->insert(reaching_it->second->begin(), reaching_it->second->end());
    537       } else {
    538         new_reaching.insert(
    539             std::pair<int, std::set<sea_ir::InstructionNode*>*>(
    540                 reaching_it->first,
    541                 reaching_it->second) );
    542       }
    543     }
    544   }
    545   bool changed = false;
    546   // Because the sets are monotonically increasing,
    547   // we can compare sizes instead of using set comparison.
    548   // TODO: Find formal proof.
    549   int old_size = 0;
    550   if (-1 == reaching_defs_size_) {
    551     std::map<int, std::set<sea_ir::InstructionNode*>*>::iterator reaching_it =
    552         reaching_defs_.begin();
    553     for (; reaching_it != reaching_defs_.end(); reaching_it++) {
    554       old_size += (*reaching_it).second->size();
    555     }
    556   } else {
    557     old_size = reaching_defs_size_;
    558   }
    559   int new_size = 0;
    560   std::map<int, std::set<sea_ir::InstructionNode*>*>::iterator reaching_it = new_reaching.begin();
    561   for (; reaching_it != new_reaching.end(); reaching_it++) {
    562     new_size += (*reaching_it).second->size();
    563   }
    564   if (old_size != new_size) {
    565     changed = true;
    566   }
    567   if (changed) {
    568     reaching_defs_ = new_reaching;
    569     reaching_defs_size_ = new_size;
    570   }
    571   return changed;
    572 }
    573 
    574 bool Region::InsertPhiFor(int reg_no) {
    575   if (!ContainsPhiFor(reg_no)) {
    576     phi_set_.insert(reg_no);
    577     PhiInstructionNode* new_phi = new PhiInstructionNode(reg_no);
    578     new_phi->SetRegion(this);
    579     phi_instructions_.push_back(new_phi);
    580     return true;
    581   }
    582   return false;
    583 }
    584 
    585 void Region::SetPhiDefinitionsForUses(
    586     const utils::ScopedHashtable<int, InstructionNode*>* scoped_table, Region* predecessor) {
    587   int predecessor_id = -1;
    588   for (unsigned int crt_pred_id = 0; crt_pred_id < predecessors_.size(); crt_pred_id++) {
    589     if (predecessors_.at(crt_pred_id) == predecessor) {
    590       predecessor_id = crt_pred_id;
    591     }
    592   }
    593   DCHECK_NE(-1, predecessor_id);
    594   for (std::vector<PhiInstructionNode*>::iterator phi_it = phi_instructions_.begin();
    595       phi_it != phi_instructions_.end(); phi_it++) {
    596     PhiInstructionNode* phi = (*phi_it);
    597     int reg_no = phi->GetRegisterNumber();
    598     InstructionNode* definition = scoped_table->Lookup(reg_no);
    599     phi->RenameToSSA(reg_no, definition, predecessor_id);
    600   }
    601 }
    602 
    603 std::vector<InstructionNode*> InstructionNode::Create(const art::Instruction* in) {
    604   std::vector<InstructionNode*> sea_instructions;
    605   switch (in->Opcode()) {
    606     case art::Instruction::CONST_4:
    607       sea_instructions.push_back(new ConstInstructionNode(in));
    608       break;
    609     case art::Instruction::RETURN:
    610       sea_instructions.push_back(new ReturnInstructionNode(in));
    611       break;
    612     case art::Instruction::IF_NE:
    613       sea_instructions.push_back(new IfNeInstructionNode(in));
    614       break;
    615     case art::Instruction::ADD_INT_LIT8:
    616       sea_instructions.push_back(new UnnamedConstInstructionNode(in, in->VRegC_22b()));
    617       sea_instructions.push_back(new AddIntLitInstructionNode(in));
    618       break;
    619     case art::Instruction::MOVE_RESULT:
    620       sea_instructions.push_back(new MoveResultInstructionNode(in));
    621       break;
    622     case art::Instruction::INVOKE_STATIC:
    623       sea_instructions.push_back(new InvokeStaticInstructionNode(in));
    624       break;
    625     case art::Instruction::ADD_INT:
    626       sea_instructions.push_back(new AddIntInstructionNode(in));
    627       break;
    628     case art::Instruction::GOTO:
    629       sea_instructions.push_back(new GotoInstructionNode(in));
    630       break;
    631     case art::Instruction::IF_EQZ:
    632       sea_instructions.push_back(new IfEqzInstructionNode(in));
    633       break;
    634     default:
    635       // Default, generic IR instruction node; default case should never be reached
    636       // when support for all instructions ahs been added.
    637       sea_instructions.push_back(new InstructionNode(in));
    638   }
    639   return sea_instructions;
    640 }
    641 
    642 void InstructionNode::MarkAsDEDef() {
    643   de_def_ = true;
    644 }
    645 
    646 int InstructionNode::GetResultRegister() const {
    647   if (instruction_->HasVRegA() && InstructionTools::IsDefinition(instruction_)) {
    648     return instruction_->VRegA();
    649   }
    650   return NO_REGISTER;
    651 }
    652 
    653 std::vector<int> InstructionNode::GetDefinitions() const {
    654   // TODO: Extend this to handle instructions defining more than one register (if any)
    655   // The return value should be changed to pointer to field then; for now it is an object
    656   // so that we avoid possible memory leaks from allocating objects dynamically.
    657   std::vector<int> definitions;
    658   int result = GetResultRegister();
    659   if (NO_REGISTER != result) {
    660     definitions.push_back(result);
    661   }
    662   return definitions;
    663 }
    664 
    665 std::vector<int> InstructionNode::GetUses() const {
    666   std::vector<int> uses;  // Using vector<> instead of set<> because order matters.
    667   if (!InstructionTools::IsDefinition(instruction_) && (instruction_->HasVRegA())) {
    668     int vA = instruction_->VRegA();
    669     uses.push_back(vA);
    670   }
    671   if (instruction_->HasVRegB()) {
    672     int vB = instruction_->VRegB();
    673     uses.push_back(vB);
    674   }
    675   if (instruction_->HasVRegC()) {
    676     int vC = instruction_->VRegC();
    677     uses.push_back(vC);
    678   }
    679   return uses;
    680 }
    681 }  // namespace sea_ir
    682