167bf885d62b1473c833bece1c9e0bb624e6ba391buzbee/* 267bf885d62b1473c833bece1c9e0bb624e6ba391buzbee * Copyright (C) 2011 The Android Open Source Project 367bf885d62b1473c833bece1c9e0bb624e6ba391buzbee * 467bf885d62b1473c833bece1c9e0bb624e6ba391buzbee * Licensed under the Apache License, Version 2.0 (the "License"); 567bf885d62b1473c833bece1c9e0bb624e6ba391buzbee * you may not use this file except in compliance with the License. 667bf885d62b1473c833bece1c9e0bb624e6ba391buzbee * You may obtain a copy of the License at 767bf885d62b1473c833bece1c9e0bb624e6ba391buzbee * 867bf885d62b1473c833bece1c9e0bb624e6ba391buzbee * http://www.apache.org/licenses/LICENSE-2.0 967bf885d62b1473c833bece1c9e0bb624e6ba391buzbee * 1067bf885d62b1473c833bece1c9e0bb624e6ba391buzbee * Unless required by applicable law or agreed to in writing, software 1167bf885d62b1473c833bece1c9e0bb624e6ba391buzbee * distributed under the License is distributed on an "AS IS" BASIS, 1267bf885d62b1473c833bece1c9e0bb624e6ba391buzbee * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 1367bf885d62b1473c833bece1c9e0bb624e6ba391buzbee * See the License for the specific language governing permissions and 1467bf885d62b1473c833bece1c9e0bb624e6ba391buzbee * limitations under the License. 1567bf885d62b1473c833bece1c9e0bb624e6ba391buzbee */ 1667bf885d62b1473c833bece1c9e0bb624e6ba391buzbee 17eaf09bc65f9a10d12befcdb239156938c9bceef2buzbee#include "compiler_internals.h" 188d3a117b374352a1853fae9b7306afeaaa9e3b91Ian Rogers#include "dataflow_iterator-inl.h" 1967bf885d62b1473c833bece1c9e0bb624e6ba391buzbee 201fd3346740dfb7f47be9922312b68a4227fada96buzbee#define NOTVISITED (-1) 211fd3346740dfb7f47be9922312b68a4227fada96buzbee 2211d1b0c31ddd710d26068da8e0e4621002205b4bElliott Hughesnamespace art { 2311d1b0c31ddd710d26068da8e0e4621002205b4bElliott Hughes 24a5abf7091711eed1e9f1d0e1538fe9963ebdf31cbuzbeevoid MIRGraph::ClearAllVisitedFlags() { 25a5abf7091711eed1e9f1d0e1538fe9963ebdf31cbuzbee AllNodesIterator iter(this, false /* not iterative */); 26a5abf7091711eed1e9f1d0e1538fe9963ebdf31cbuzbee for (BasicBlock* bb = iter.Next(); bb != NULL; bb = iter.Next()) { 27a5abf7091711eed1e9f1d0e1538fe9963ebdf31cbuzbee bb->visited = false; 28a5abf7091711eed1e9f1d0e1538fe9963ebdf31cbuzbee } 29a5abf7091711eed1e9f1d0e1538fe9963ebdf31cbuzbee} 30a5abf7091711eed1e9f1d0e1538fe9963ebdf31cbuzbee 31311ca169f4727d46a55bdc8dfa0059719fa72b65buzbeeBasicBlock* MIRGraph::NeedsVisit(BasicBlock* bb) { 32e5f01223ae03b89767dc7881d75dca061121ee36buzbee if (bb != NULL) { 33e5f01223ae03b89767dc7881d75dca061121ee36buzbee if (bb->visited || bb->hidden) { 34e5f01223ae03b89767dc7881d75dca061121ee36buzbee bb = NULL; 35e5f01223ae03b89767dc7881d75dca061121ee36buzbee } 36e5f01223ae03b89767dc7881d75dca061121ee36buzbee } 37e5f01223ae03b89767dc7881d75dca061121ee36buzbee return bb; 38e5f01223ae03b89767dc7881d75dca061121ee36buzbee} 39e5f01223ae03b89767dc7881d75dca061121ee36buzbee 402ce745c06271d5223d57dbf08117b20d5b60694aBrian CarlstromBasicBlock* MIRGraph::NextUnvisitedSuccessor(BasicBlock* bb) { 41fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee BasicBlock* res = NeedsVisit(bb->fall_through); 42e5f01223ae03b89767dc7881d75dca061121ee36buzbee if (res == NULL) { 4352a77fc135f0e0df57ee24641c3f5ae415ff7bd6buzbee res = NeedsVisit(bb->taken); 44e5f01223ae03b89767dc7881d75dca061121ee36buzbee if (res == NULL) { 45fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee if (bb->successor_block_list.block_list_type != kNotUsed) { 46862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee GrowableArray<SuccessorBlockInfo*>::Iterator iterator(bb->successor_block_list.blocks); 47e5f01223ae03b89767dc7881d75dca061121ee36buzbee while (true) { 48862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee SuccessorBlockInfo *sbi = iterator.Next(); 490cd7ec2dcd8d7ba30bf3ca420b40dac52849876cBrian Carlstrom if (sbi == NULL) { 500cd7ec2dcd8d7ba30bf3ca420b40dac52849876cBrian Carlstrom break; 510cd7ec2dcd8d7ba30bf3ca420b40dac52849876cBrian Carlstrom } 5252a77fc135f0e0df57ee24641c3f5ae415ff7bd6buzbee res = NeedsVisit(sbi->block); 530cd7ec2dcd8d7ba30bf3ca420b40dac52849876cBrian Carlstrom if (res != NULL) { 540cd7ec2dcd8d7ba30bf3ca420b40dac52849876cBrian Carlstrom break; 550cd7ec2dcd8d7ba30bf3ca420b40dac52849876cBrian Carlstrom } 56e5f01223ae03b89767dc7881d75dca061121ee36buzbee } 57e5f01223ae03b89767dc7881d75dca061121ee36buzbee } 58e5f01223ae03b89767dc7881d75dca061121ee36buzbee } 59e5f01223ae03b89767dc7881d75dca061121ee36buzbee } 60e5f01223ae03b89767dc7881d75dca061121ee36buzbee return res; 61e5f01223ae03b89767dc7881d75dca061121ee36buzbee} 62e5f01223ae03b89767dc7881d75dca061121ee36buzbee 632ce745c06271d5223d57dbf08117b20d5b60694aBrian Carlstromvoid MIRGraph::MarkPreOrder(BasicBlock* block) { 64e5f01223ae03b89767dc7881d75dca061121ee36buzbee block->visited = true; 65fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee /* Enqueue the pre_order block id */ 66862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee dfs_order_->Insert(block->id); 67e5f01223ae03b89767dc7881d75dca061121ee36buzbee} 68e5f01223ae03b89767dc7881d75dca061121ee36buzbee 692ce745c06271d5223d57dbf08117b20d5b60694aBrian Carlstromvoid MIRGraph::RecordDFSOrders(BasicBlock* block) { 70e5f01223ae03b89767dc7881d75dca061121ee36buzbee std::vector<BasicBlock*> succ; 71311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee MarkPreOrder(block); 72e5f01223ae03b89767dc7881d75dca061121ee36buzbee succ.push_back(block); 73e5f01223ae03b89767dc7881d75dca061121ee36buzbee while (!succ.empty()) { 74e5f01223ae03b89767dc7881d75dca061121ee36buzbee BasicBlock* curr = succ.back(); 75fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee BasicBlock* next_successor = NextUnvisitedSuccessor(curr); 76fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee if (next_successor != NULL) { 77311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee MarkPreOrder(next_successor); 78fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee succ.push_back(next_successor); 79e5f01223ae03b89767dc7881d75dca061121ee36buzbee continue; 80e5f01223ae03b89767dc7881d75dca061121ee36buzbee } 81862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee curr->dfs_id = dfs_post_order_->Size(); 82862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee dfs_post_order_->Insert(curr->id); 83e5f01223ae03b89767dc7881d75dca061121ee36buzbee succ.pop_back(); 84e5f01223ae03b89767dc7881d75dca061121ee36buzbee } 85e5f01223ae03b89767dc7881d75dca061121ee36buzbee} 86e5f01223ae03b89767dc7881d75dca061121ee36buzbee 875b53710b4abcf8f35c91a963a475b72cb34757e6buzbee/* Sort the blocks by the Depth-First-Search */ 882ce745c06271d5223d57dbf08117b20d5b60694aBrian Carlstromvoid MIRGraph::ComputeDFSOrders() { 89fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee /* Initialize or reset the DFS pre_order list */ 90862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee if (dfs_order_ == NULL) { 91862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee dfs_order_ = new (arena_) GrowableArray<int>(arena_, GetNumBlocks(), kGrowableArrayDfsOrder); 92a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee } else { 93a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee /* Just reset the used length on the counter */ 94862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee dfs_order_->Reset(); 95a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee } 96a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee 97fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee /* Initialize or reset the DFS post_order list */ 98862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee if (dfs_post_order_ == NULL) { 99862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee dfs_post_order_ = new (arena_) GrowableArray<int>(arena_, GetNumBlocks(), kGrowableArrayDfsPostOrder); 100a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee } else { 101a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee /* Just reset the used length on the counter */ 102862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee dfs_post_order_->Reset(); 103311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee } 104a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee 105e5f01223ae03b89767dc7881d75dca061121ee36buzbee // Reset visited flags from all nodes 106a5abf7091711eed1e9f1d0e1538fe9963ebdf31cbuzbee ClearAllVisitedFlags(); 107a5abf7091711eed1e9f1d0e1538fe9963ebdf31cbuzbee 108311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee // Record dfs orders 109311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee RecordDFSOrders(GetEntryBlock()); 110e5f01223ae03b89767dc7881d75dca061121ee36buzbee 111862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee num_reachable_blocks_ = dfs_order_->Size(); 11267bf885d62b1473c833bece1c9e0bb624e6ba391buzbee} 11367bf885d62b1473c833bece1c9e0bb624e6ba391buzbee 11467bf885d62b1473c833bece1c9e0bb624e6ba391buzbee/* 11567bf885d62b1473c833bece1c9e0bb624e6ba391buzbee * Mark block bit on the per-Dalvik register vector to denote that Dalvik 11667bf885d62b1473c833bece1c9e0bb624e6ba391buzbee * register idx is defined in BasicBlock bb. 11767bf885d62b1473c833bece1c9e0bb624e6ba391buzbee */ 1182ce745c06271d5223d57dbf08117b20d5b60694aBrian Carlstrombool MIRGraph::FillDefBlockMatrix(BasicBlock* bb) { 1190cd7ec2dcd8d7ba30bf3ca420b40dac52849876cBrian Carlstrom if (bb->data_flow_info == NULL) { 1200cd7ec2dcd8d7ba30bf3ca420b40dac52849876cBrian Carlstrom return false; 1210cd7ec2dcd8d7ba30bf3ca420b40dac52849876cBrian Carlstrom } 122a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee 123862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee ArenaBitVector::Iterator iterator(bb->data_flow_info->def_v); 124a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee while (true) { 125862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee int idx = iterator.Next(); 1260cd7ec2dcd8d7ba30bf3ca420b40dac52849876cBrian Carlstrom if (idx == -1) { 1270cd7ec2dcd8d7ba30bf3ca420b40dac52849876cBrian Carlstrom break; 1280cd7ec2dcd8d7ba30bf3ca420b40dac52849876cBrian Carlstrom } 129a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee /* Block bb defines register idx */ 130862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee def_block_matrix_[idx]->SetBit(bb->id); 131a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee } 132a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee return true; 13367bf885d62b1473c833bece1c9e0bb624e6ba391buzbee} 13467bf885d62b1473c833bece1c9e0bb624e6ba391buzbee 1352ce745c06271d5223d57dbf08117b20d5b60694aBrian Carlstromvoid MIRGraph::ComputeDefBlockMatrix() { 136311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee int num_registers = cu_->num_dalvik_registers; 137fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee /* Allocate num_dalvik_registers bit vector pointers */ 138311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee def_block_matrix_ = static_cast<ArenaBitVector**> 139f6c4b3ba3825de1dbb3e747a68b809c6cc8eb4dbMathieu Chartier (arena_->Alloc(sizeof(ArenaBitVector *) * num_registers, 140f6c4b3ba3825de1dbb3e747a68b809c6cc8eb4dbMathieu Chartier ArenaAllocator::kAllocDFInfo)); 141a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee int i; 142a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee 143fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee /* Initialize num_register vectors with num_blocks bits each */ 144fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee for (i = 0; i < num_registers; i++) { 145862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee def_block_matrix_[i] = 146862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee new (arena_) ArenaBitVector(arena_, GetNumBlocks(), false, kBitMapBMatrix); 147311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee } 1480665fe0966d9591c5378a5d598c6eb6cab67e74abuzbee AllNodesIterator iter(this, false /* not iterative */); 149311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee for (BasicBlock* bb = iter.Next(); bb != NULL; bb = iter.Next()) { 150311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee FindLocalLiveIn(bb); 151311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee } 1520665fe0966d9591c5378a5d598c6eb6cab67e74abuzbee AllNodesIterator iter2(this, false /* not iterative */); 153311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee for (BasicBlock* bb = iter2.Next(); bb != NULL; bb = iter2.Next()) { 154311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee FillDefBlockMatrix(bb); 155a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee } 156a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee 157a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee /* 158a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee * Also set the incoming parameters as defs in the entry block. 159a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee * Only need to handle the parameters for the outer method. 160a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee */ 161311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee int num_regs = cu_->num_dalvik_registers; 162311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee int in_reg = num_regs - cu_->num_ins; 163fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee for (; in_reg < num_regs; in_reg++) { 164862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee def_block_matrix_[in_reg]->SetBit(GetEntryBlock()->id); 165a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee } 16667bf885d62b1473c833bece1c9e0bb624e6ba391buzbee} 16767bf885d62b1473c833bece1c9e0bb624e6ba391buzbee 168a5abf7091711eed1e9f1d0e1538fe9963ebdf31cbuzbeevoid MIRGraph::ComputeDomPostOrderTraversal(BasicBlock* bb) { 169a5abf7091711eed1e9f1d0e1538fe9963ebdf31cbuzbee if (dom_post_order_traversal_ == NULL) { 170a5abf7091711eed1e9f1d0e1538fe9963ebdf31cbuzbee // First time - create the array. 171a5abf7091711eed1e9f1d0e1538fe9963ebdf31cbuzbee dom_post_order_traversal_ = 172a5abf7091711eed1e9f1d0e1538fe9963ebdf31cbuzbee new (arena_) GrowableArray<int>(arena_, num_reachable_blocks_, 173a5abf7091711eed1e9f1d0e1538fe9963ebdf31cbuzbee kGrowableArrayDomPostOrderTraversal); 174a5abf7091711eed1e9f1d0e1538fe9963ebdf31cbuzbee } else { 175a5abf7091711eed1e9f1d0e1538fe9963ebdf31cbuzbee dom_post_order_traversal_->Reset(); 176a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee } 177a5abf7091711eed1e9f1d0e1538fe9963ebdf31cbuzbee ClearAllVisitedFlags(); 178a5abf7091711eed1e9f1d0e1538fe9963ebdf31cbuzbee std::vector<std::pair<BasicBlock*, ArenaBitVector::Iterator*> > work_stack; 179a5abf7091711eed1e9f1d0e1538fe9963ebdf31cbuzbee bb->visited = true; 180a5abf7091711eed1e9f1d0e1538fe9963ebdf31cbuzbee work_stack.push_back(std::make_pair(bb, new (arena_) ArenaBitVector::Iterator(bb->i_dominated))); 181a5abf7091711eed1e9f1d0e1538fe9963ebdf31cbuzbee while (!work_stack.empty()) { 182a5abf7091711eed1e9f1d0e1538fe9963ebdf31cbuzbee std::pair<BasicBlock*, ArenaBitVector::Iterator*> curr = work_stack.back(); 183a5abf7091711eed1e9f1d0e1538fe9963ebdf31cbuzbee BasicBlock* curr_bb = curr.first; 184a5abf7091711eed1e9f1d0e1538fe9963ebdf31cbuzbee ArenaBitVector::Iterator* curr_idom_iter = curr.second; 185a5abf7091711eed1e9f1d0e1538fe9963ebdf31cbuzbee int bb_idx = curr_idom_iter->Next(); 186a5abf7091711eed1e9f1d0e1538fe9963ebdf31cbuzbee while ((bb_idx != -1) && (NeedsVisit(GetBasicBlock(bb_idx)) == NULL)) { 187a5abf7091711eed1e9f1d0e1538fe9963ebdf31cbuzbee bb_idx = curr_idom_iter->Next(); 188a5abf7091711eed1e9f1d0e1538fe9963ebdf31cbuzbee } 189a5abf7091711eed1e9f1d0e1538fe9963ebdf31cbuzbee if (bb_idx != -1) { 190a5abf7091711eed1e9f1d0e1538fe9963ebdf31cbuzbee BasicBlock* new_bb = GetBasicBlock(bb_idx); 191a5abf7091711eed1e9f1d0e1538fe9963ebdf31cbuzbee new_bb->visited = true; 192a5abf7091711eed1e9f1d0e1538fe9963ebdf31cbuzbee work_stack.push_back( 193a5abf7091711eed1e9f1d0e1538fe9963ebdf31cbuzbee std::make_pair(new_bb, new (arena_) ArenaBitVector::Iterator(new_bb->i_dominated))); 194a5abf7091711eed1e9f1d0e1538fe9963ebdf31cbuzbee } else { 195a5abf7091711eed1e9f1d0e1538fe9963ebdf31cbuzbee // no successor/next 196a5abf7091711eed1e9f1d0e1538fe9963ebdf31cbuzbee dom_post_order_traversal_->Insert(curr_bb->id); 197a5abf7091711eed1e9f1d0e1538fe9963ebdf31cbuzbee work_stack.pop_back(); 198a5abf7091711eed1e9f1d0e1538fe9963ebdf31cbuzbee 199a5abf7091711eed1e9f1d0e1538fe9963ebdf31cbuzbee /* hacky loop detection */ 200a5abf7091711eed1e9f1d0e1538fe9963ebdf31cbuzbee if (curr_bb->taken && curr_bb->dominators->IsBitSet(curr_bb->taken->id)) { 201a5abf7091711eed1e9f1d0e1538fe9963ebdf31cbuzbee attributes_ |= METHOD_HAS_LOOP; 202a5abf7091711eed1e9f1d0e1538fe9963ebdf31cbuzbee } 203a5abf7091711eed1e9f1d0e1538fe9963ebdf31cbuzbee } 204a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee } 20567bf885d62b1473c833bece1c9e0bb624e6ba391buzbee} 20667bf885d62b1473c833bece1c9e0bb624e6ba391buzbee 207311ca169f4727d46a55bdc8dfa0059719fa72b65buzbeevoid MIRGraph::CheckForDominanceFrontier(BasicBlock* dom_bb, 2082ce745c06271d5223d57dbf08117b20d5b60694aBrian Carlstrom const BasicBlock* succ_bb) { 209a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee /* 210a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee * TODO - evaluate whether phi will ever need to be inserted into exit 211a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee * blocks. 212a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee */ 213fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee if (succ_bb->i_dom != dom_bb && 214fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee succ_bb->block_type == kDalvikByteCode && 215fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee succ_bb->hidden == false) { 216862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee dom_bb->dom_frontier->SetBit(succ_bb->id); 217a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee } 21867bf885d62b1473c833bece1c9e0bb624e6ba391buzbee} 21967bf885d62b1473c833bece1c9e0bb624e6ba391buzbee 22067bf885d62b1473c833bece1c9e0bb624e6ba391buzbee/* Worker function to compute the dominance frontier */ 2212ce745c06271d5223d57dbf08117b20d5b60694aBrian Carlstrombool MIRGraph::ComputeDominanceFrontier(BasicBlock* bb) { 222a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee /* Calculate DF_local */ 223a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee if (bb->taken) { 224311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee CheckForDominanceFrontier(bb, bb->taken); 225a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee } 226fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee if (bb->fall_through) { 227311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee CheckForDominanceFrontier(bb, bb->fall_through); 228a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee } 229fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee if (bb->successor_block_list.block_list_type != kNotUsed) { 230862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee GrowableArray<SuccessorBlockInfo*>::Iterator iterator(bb->successor_block_list.blocks); 231a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee while (true) { 232862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee SuccessorBlockInfo *successor_block_info = iterator.Next(); 2330cd7ec2dcd8d7ba30bf3ca420b40dac52849876cBrian Carlstrom if (successor_block_info == NULL) { 2340cd7ec2dcd8d7ba30bf3ca420b40dac52849876cBrian Carlstrom break; 2350cd7ec2dcd8d7ba30bf3ca420b40dac52849876cBrian Carlstrom } 236fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee BasicBlock* succ_bb = successor_block_info->block; 237311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee CheckForDominanceFrontier(bb, succ_bb); 238a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee } 239a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee } 240a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee 241a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee /* Calculate DF_up */ 242862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee ArenaBitVector::Iterator bv_iterator(bb->i_dominated); 243a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee while (true) { 2447934ac288acfb2552bb0b06ec1f61e5820d924a4Brian Carlstrom // TUNING: hot call to BitVectorIteratorNext 245862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee int dominated_idx = bv_iterator.Next(); 2460cd7ec2dcd8d7ba30bf3ca420b40dac52849876cBrian Carlstrom if (dominated_idx == -1) { 2470cd7ec2dcd8d7ba30bf3ca420b40dac52849876cBrian Carlstrom break; 2480cd7ec2dcd8d7ba30bf3ca420b40dac52849876cBrian Carlstrom } 249311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee BasicBlock* dominated_bb = GetBasicBlock(dominated_idx); 250862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee ArenaBitVector::Iterator df_iterator(dominated_bb->dom_frontier); 25167bf885d62b1473c833bece1c9e0bb624e6ba391buzbee while (true) { 2527934ac288acfb2552bb0b06ec1f61e5820d924a4Brian Carlstrom // TUNING: hot call to BitVectorIteratorNext 253862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee int df_up_idx = df_iterator.Next(); 2540cd7ec2dcd8d7ba30bf3ca420b40dac52849876cBrian Carlstrom if (df_up_idx == -1) { 2550cd7ec2dcd8d7ba30bf3ca420b40dac52849876cBrian Carlstrom break; 2560cd7ec2dcd8d7ba30bf3ca420b40dac52849876cBrian Carlstrom } 257311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee BasicBlock* df_up_block = GetBasicBlock(df_up_idx); 258311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee CheckForDominanceFrontier(bb, df_up_block); 25967bf885d62b1473c833bece1c9e0bb624e6ba391buzbee } 260a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee } 26167bf885d62b1473c833bece1c9e0bb624e6ba391buzbee 262a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee return true; 26367bf885d62b1473c833bece1c9e0bb624e6ba391buzbee} 26467bf885d62b1473c833bece1c9e0bb624e6ba391buzbee 26567bf885d62b1473c833bece1c9e0bb624e6ba391buzbee/* Worker function for initializing domination-related data structures */ 2662ce745c06271d5223d57dbf08117b20d5b60694aBrian Carlstromvoid MIRGraph::InitializeDominationInfo(BasicBlock* bb) { 267311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee int num_total_blocks = GetBasicBlockListCount(); 268a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee 269df62950e7a32031b82360c407d46a37b94188fbbBrian Carlstrom if (bb->dominators == NULL) { 270862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee bb->dominators = new (arena_) ArenaBitVector(arena_, num_total_blocks, 271862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee false /* expandable */, kBitMapDominators); 272862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee bb->i_dominated = new (arena_) ArenaBitVector(arena_, num_total_blocks, 273862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee false /* expandable */, kBitMapIDominated); 274862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee bb->dom_frontier = new (arena_) ArenaBitVector(arena_, num_total_blocks, 275862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee false /* expandable */, kBitMapDomFrontier); 276a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee } else { 277862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee bb->dominators->ClearAllBits(); 278862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee bb->i_dominated->ClearAllBits(); 279862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee bb->dom_frontier->ClearAllBits(); 280a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee } 281a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee /* Set all bits in the dominator vector */ 282862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee bb->dominators->SetInitialBits(num_total_blocks); 283a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee 284862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee return; 28567bf885d62b1473c833bece1c9e0bb624e6ba391buzbee} 28667bf885d62b1473c833bece1c9e0bb624e6ba391buzbee 2875b53710b4abcf8f35c91a963a475b72cb34757e6buzbee/* 288fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee * Walk through the ordered i_dom list until we reach common parent. 289fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee * Given the ordering of i_dom_list, this common parent represents the 2905b53710b4abcf8f35c91a963a475b72cb34757e6buzbee * last element of the intersection of block1 and block2 dominators. 2915b53710b4abcf8f35c91a963a475b72cb34757e6buzbee */ 2922ce745c06271d5223d57dbf08117b20d5b60694aBrian Carlstromint MIRGraph::FindCommonParent(int block1, int block2) { 293a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee while (block1 != block2) { 294a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee while (block1 < block2) { 295311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee block1 = i_dom_list_[block1]; 296a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee DCHECK_NE(block1, NOTVISITED); 297a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee } 298a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee while (block2 < block1) { 299311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee block2 = i_dom_list_[block2]; 300a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee DCHECK_NE(block2, NOTVISITED); 3015b53710b4abcf8f35c91a963a475b72cb34757e6buzbee } 302a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee } 303a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee return block1; 3045b53710b4abcf8f35c91a963a475b72cb34757e6buzbee} 3055b53710b4abcf8f35c91a963a475b72cb34757e6buzbee 3065b53710b4abcf8f35c91a963a475b72cb34757e6buzbee/* Worker function to compute each block's immediate dominator */ 3072ce745c06271d5223d57dbf08117b20d5b60694aBrian Carlstrombool MIRGraph::ComputeblockIDom(BasicBlock* bb) { 308a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee /* Special-case entry block */ 309311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee if (bb == GetEntryBlock()) { 3105b53710b4abcf8f35c91a963a475b72cb34757e6buzbee return false; 311a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee } 312a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee 313a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee /* Iterate through the predecessors */ 314862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee GrowableArray<BasicBlock*>::Iterator iter(bb->predecessors); 315a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee 316a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee /* Find the first processed predecessor */ 317862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee int idom = -1; 318a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee while (true) { 319862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee BasicBlock* pred_bb = iter.Next(); 320fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee CHECK(pred_bb != NULL); 321311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee if (i_dom_list_[pred_bb->dfs_id] != NOTVISITED) { 322fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee idom = pred_bb->dfs_id; 323a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee break; 324a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee } 325a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee } 326a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee 327a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee /* Scan the rest of the predecessors */ 328a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee while (true) { 329862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee BasicBlock* pred_bb = iter.Next(); 3300cd7ec2dcd8d7ba30bf3ca420b40dac52849876cBrian Carlstrom if (!pred_bb) { 3310cd7ec2dcd8d7ba30bf3ca420b40dac52849876cBrian Carlstrom break; 3320cd7ec2dcd8d7ba30bf3ca420b40dac52849876cBrian Carlstrom } 333311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee if (i_dom_list_[pred_bb->dfs_id] == NOTVISITED) { 334a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee continue; 335a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee } else { 336311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee idom = FindCommonParent(pred_bb->dfs_id, idom); 337a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee } 338a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee } 339a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee 340a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee DCHECK_NE(idom, NOTVISITED); 341a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee 342a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee /* Did something change? */ 343311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee if (i_dom_list_[bb->dfs_id] != idom) { 344311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee i_dom_list_[bb->dfs_id] = idom; 345a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee return true; 346a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee } 347a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee return false; 3485b53710b4abcf8f35c91a963a475b72cb34757e6buzbee} 3495b53710b4abcf8f35c91a963a475b72cb34757e6buzbee 3505b53710b4abcf8f35c91a963a475b72cb34757e6buzbee/* Worker function to compute each block's domintors */ 3512ce745c06271d5223d57dbf08117b20d5b60694aBrian Carlstrombool MIRGraph::ComputeBlockDominators(BasicBlock* bb) { 352311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee if (bb == GetEntryBlock()) { 353862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee bb->dominators->ClearAllBits(); 354a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee } else { 355862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee bb->dominators->Copy(bb->i_dom->dominators); 356a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee } 357862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee bb->dominators->SetBit(bb->id); 358a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee return false; 3595b53710b4abcf8f35c91a963a475b72cb34757e6buzbee} 3605b53710b4abcf8f35c91a963a475b72cb34757e6buzbee 3612ce745c06271d5223d57dbf08117b20d5b60694aBrian Carlstrombool MIRGraph::SetDominators(BasicBlock* bb) { 362311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee if (bb != GetEntryBlock()) { 363311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee int idom_dfs_idx = i_dom_list_[bb->dfs_id]; 364fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee DCHECK_NE(idom_dfs_idx, NOTVISITED); 365862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee int i_dom_idx = dfs_post_order_->Get(idom_dfs_idx); 366311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee BasicBlock* i_dom = GetBasicBlock(i_dom_idx); 367fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee bb->i_dom = i_dom; 368fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee /* Add bb to the i_dominated set of the immediate dominator block */ 369862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee i_dom->i_dominated->SetBit(bb->id); 370a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee } 371a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee return false; 3725b53710b4abcf8f35c91a963a475b72cb34757e6buzbee} 3735b53710b4abcf8f35c91a963a475b72cb34757e6buzbee 37467bf885d62b1473c833bece1c9e0bb624e6ba391buzbee/* Compute dominators, immediate dominator, and dominance fronter */ 3752ce745c06271d5223d57dbf08117b20d5b60694aBrian Carlstromvoid MIRGraph::ComputeDominators() { 376311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee int num_reachable_blocks = num_reachable_blocks_; 377311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee int num_total_blocks = GetBasicBlockListCount(); 378a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee 379a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee /* Initialize domination-related data structures */ 3800665fe0966d9591c5378a5d598c6eb6cab67e74abuzbee ReachableNodesIterator iter(this, false /* not iterative */); 381311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee for (BasicBlock* bb = iter.Next(); bb != NULL; bb = iter.Next()) { 382311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee InitializeDominationInfo(bb); 383311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee } 384a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee 385fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee /* Initalize & Clear i_dom_list */ 386311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee if (i_dom_list_ == NULL) { 387f6c4b3ba3825de1dbb3e747a68b809c6cc8eb4dbMathieu Chartier i_dom_list_ = static_cast<int*>(arena_->Alloc(sizeof(int) * num_reachable_blocks, 388f6c4b3ba3825de1dbb3e747a68b809c6cc8eb4dbMathieu Chartier ArenaAllocator::kAllocDFInfo)); 389a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee } 390fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee for (int i = 0; i < num_reachable_blocks; i++) { 391311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee i_dom_list_[i] = NOTVISITED; 392a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee } 393a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee 394fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee /* For post-order, last block is entry block. Set its i_dom to istelf */ 395311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee DCHECK_EQ(GetEntryBlock()->dfs_id, num_reachable_blocks-1); 396311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee i_dom_list_[GetEntryBlock()->dfs_id] = GetEntryBlock()->dfs_id; 397a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee 398a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee /* Compute the immediate dominators */ 3990665fe0966d9591c5378a5d598c6eb6cab67e74abuzbee ReversePostOrderDfsIterator iter2(this, true /* iterative */); 400311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee bool change = false; 401311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee for (BasicBlock* bb = iter2.Next(false); bb != NULL; bb = iter2.Next(change)) { 402311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee change = ComputeblockIDom(bb); 403311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee } 404a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee 405a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee /* Set the dominator for the root node */ 406862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee GetEntryBlock()->dominators->ClearAllBits(); 407862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee GetEntryBlock()->dominators->SetBit(GetEntryBlock()->id); 408a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee 409311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee if (temp_block_v_ == NULL) { 410862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee temp_block_v_ = new (arena_) ArenaBitVector(arena_, num_total_blocks, 411862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee false /* expandable */, kBitMapTmpBlockV); 412a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee } else { 413862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee temp_block_v_->ClearAllBits(); 414a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee } 415311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee GetEntryBlock()->i_dom = NULL; 4165b53710b4abcf8f35c91a963a475b72cb34757e6buzbee 4170665fe0966d9591c5378a5d598c6eb6cab67e74abuzbee ReachableNodesIterator iter3(this, false /* not iterative */); 418311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee for (BasicBlock* bb = iter3.Next(); bb != NULL; bb = iter3.Next()) { 419311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee SetDominators(bb); 420a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee } 421a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee 4220665fe0966d9591c5378a5d598c6eb6cab67e74abuzbee ReversePostOrderDfsIterator iter4(this, false /* not iterative */); 423311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee for (BasicBlock* bb = iter4.Next(); bb != NULL; bb = iter4.Next()) { 424311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee ComputeBlockDominators(bb); 425311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee } 426a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee 427a5abf7091711eed1e9f1d0e1538fe9963ebdf31cbuzbee // Compute the dominance frontier for each block. 428311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee ComputeDomPostOrderTraversal(GetEntryBlock()); 4290665fe0966d9591c5378a5d598c6eb6cab67e74abuzbee PostOrderDOMIterator iter5(this, false /* not iterative */); 430311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee for (BasicBlock* bb = iter5.Next(); bb != NULL; bb = iter5.Next()) { 431311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee ComputeDominanceFrontier(bb); 432311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee } 43367bf885d62b1473c833bece1c9e0bb624e6ba391buzbee} 43467bf885d62b1473c833bece1c9e0bb624e6ba391buzbee 43567bf885d62b1473c833bece1c9e0bb624e6ba391buzbee/* 43667bf885d62b1473c833bece1c9e0bb624e6ba391buzbee * Perform dest U= src1 ^ ~src2 43767bf885d62b1473c833bece1c9e0bb624e6ba391buzbee * This is probably not general enough to be placed in BitVector.[ch]. 43867bf885d62b1473c833bece1c9e0bb624e6ba391buzbee */ 439311ca169f4727d46a55bdc8dfa0059719fa72b65buzbeevoid MIRGraph::ComputeSuccLineIn(ArenaBitVector* dest, const ArenaBitVector* src1, 4402ce745c06271d5223d57dbf08117b20d5b60694aBrian Carlstrom const ArenaBitVector* src2) { 441862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee if (dest->GetStorageSize() != src1->GetStorageSize() || 442862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee dest->GetStorageSize() != src2->GetStorageSize() || 443862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee dest->IsExpandable() != src1->IsExpandable() || 444862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee dest->IsExpandable() != src2->IsExpandable()) { 445a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee LOG(FATAL) << "Incompatible set properties"; 446a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee } 447a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee 448a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee unsigned int idx; 449862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee for (idx = 0; idx < dest->GetStorageSize(); idx++) { 450862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee dest->GetRawStorage()[idx] |= src1->GetRawStorageWord(idx) & ~(src2->GetRawStorageWord(idx)); 451a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee } 45267bf885d62b1473c833bece1c9e0bb624e6ba391buzbee} 45367bf885d62b1473c833bece1c9e0bb624e6ba391buzbee 45467bf885d62b1473c833bece1c9e0bb624e6ba391buzbee/* 45567bf885d62b1473c833bece1c9e0bb624e6ba391buzbee * Iterate through all successor blocks and propagate up the live-in sets. 45667bf885d62b1473c833bece1c9e0bb624e6ba391buzbee * The calculated result is used for phi-node pruning - where we only need to 45767bf885d62b1473c833bece1c9e0bb624e6ba391buzbee * insert a phi node if the variable is live-in to the block. 45867bf885d62b1473c833bece1c9e0bb624e6ba391buzbee */ 4592ce745c06271d5223d57dbf08117b20d5b60694aBrian Carlstrombool MIRGraph::ComputeBlockLiveIns(BasicBlock* bb) { 460311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee ArenaBitVector* temp_dalvik_register_v = temp_dalvik_register_v_; 461fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee 4620cd7ec2dcd8d7ba30bf3ca420b40dac52849876cBrian Carlstrom if (bb->data_flow_info == NULL) { 4630cd7ec2dcd8d7ba30bf3ca420b40dac52849876cBrian Carlstrom return false; 4640cd7ec2dcd8d7ba30bf3ca420b40dac52849876cBrian Carlstrom } 465862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee temp_dalvik_register_v->Copy(bb->data_flow_info->live_in_v); 466fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee if (bb->taken && bb->taken->data_flow_info) 467fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee ComputeSuccLineIn(temp_dalvik_register_v, bb->taken->data_flow_info->live_in_v, 468fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee bb->data_flow_info->def_v); 469fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee if (bb->fall_through && bb->fall_through->data_flow_info) 470311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee ComputeSuccLineIn(temp_dalvik_register_v, bb->fall_through->data_flow_info->live_in_v, 471fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee bb->data_flow_info->def_v); 472fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee if (bb->successor_block_list.block_list_type != kNotUsed) { 473862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee GrowableArray<SuccessorBlockInfo*>::Iterator iterator(bb->successor_block_list.blocks); 474a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee while (true) { 475862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee SuccessorBlockInfo *successor_block_info = iterator.Next(); 4760cd7ec2dcd8d7ba30bf3ca420b40dac52849876cBrian Carlstrom if (successor_block_info == NULL) { 4770cd7ec2dcd8d7ba30bf3ca420b40dac52849876cBrian Carlstrom break; 4780cd7ec2dcd8d7ba30bf3ca420b40dac52849876cBrian Carlstrom } 479fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee BasicBlock* succ_bb = successor_block_info->block; 480fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee if (succ_bb->data_flow_info) { 481311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee ComputeSuccLineIn(temp_dalvik_register_v, succ_bb->data_flow_info->live_in_v, 482fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee bb->data_flow_info->def_v); 483a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee } 48467bf885d62b1473c833bece1c9e0bb624e6ba391buzbee } 485a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee } 486862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee if (!temp_dalvik_register_v->Equal(bb->data_flow_info->live_in_v)) { 487862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee bb->data_flow_info->live_in_v->Copy(temp_dalvik_register_v); 488a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee return true; 489a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee } 490a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee return false; 49167bf885d62b1473c833bece1c9e0bb624e6ba391buzbee} 49267bf885d62b1473c833bece1c9e0bb624e6ba391buzbee 49367bf885d62b1473c833bece1c9e0bb624e6ba391buzbee/* Insert phi nodes to for each variable to the dominance frontiers */ 4942ce745c06271d5223d57dbf08117b20d5b60694aBrian Carlstromvoid MIRGraph::InsertPhiNodes() { 495fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee int dalvik_reg; 496862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee ArenaBitVector* phi_blocks = 497862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee new (arena_) ArenaBitVector(arena_, GetNumBlocks(), false, kBitMapPhi); 498862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee ArenaBitVector* tmp_blocks = 499862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee new (arena_) ArenaBitVector(arena_, GetNumBlocks(), false, kBitMapTmpBlocks); 500862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee ArenaBitVector* input_blocks = 501862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee new (arena_) ArenaBitVector(arena_, GetNumBlocks(), false, kBitMapInputBlocks); 502fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee 503311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee temp_dalvik_register_v_ = 504862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee new (arena_) ArenaBitVector(arena_, cu_->num_dalvik_registers, false, kBitMapRegisterV); 505a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee 5060665fe0966d9591c5378a5d598c6eb6cab67e74abuzbee PostOrderDfsIterator iter(this, true /* iterative */); 507311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee bool change = false; 508311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee for (BasicBlock* bb = iter.Next(false); bb != NULL; bb = iter.Next(change)) { 509311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee change = ComputeBlockLiveIns(bb); 510311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee } 511a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee 512a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee /* Iterate through each Dalvik register */ 513311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee for (dalvik_reg = cu_->num_dalvik_registers - 1; dalvik_reg >= 0; dalvik_reg--) { 514a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee bool change; 515a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee 516862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee input_blocks->Copy(def_block_matrix_[dalvik_reg]); 517862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee phi_blocks->ClearAllBits(); 518a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee 519a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee /* Calculate the phi blocks for each Dalvik register */ 520a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee do { 521a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee change = false; 522862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee tmp_blocks->ClearAllBits(); 523862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee ArenaBitVector::Iterator iterator(input_blocks); 524a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee 525a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee while (true) { 526862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee int idx = iterator.Next(); 5270cd7ec2dcd8d7ba30bf3ca420b40dac52849876cBrian Carlstrom if (idx == -1) { 5280cd7ec2dcd8d7ba30bf3ca420b40dac52849876cBrian Carlstrom break; 5290cd7ec2dcd8d7ba30bf3ca420b40dac52849876cBrian Carlstrom } 5300cd7ec2dcd8d7ba30bf3ca420b40dac52849876cBrian Carlstrom BasicBlock* def_bb = GetBasicBlock(idx); 531a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee 5320cd7ec2dcd8d7ba30bf3ca420b40dac52849876cBrian Carlstrom /* Merge the dominance frontier to tmp_blocks */ 5337934ac288acfb2552bb0b06ec1f61e5820d924a4Brian Carlstrom // TUNING: hot call to Union(). 5340cd7ec2dcd8d7ba30bf3ca420b40dac52849876cBrian Carlstrom if (def_bb->dom_frontier != NULL) { 5350cd7ec2dcd8d7ba30bf3ca420b40dac52849876cBrian Carlstrom tmp_blocks->Union(def_bb->dom_frontier); 53667bf885d62b1473c833bece1c9e0bb624e6ba391buzbee } 5370cd7ec2dcd8d7ba30bf3ca420b40dac52849876cBrian Carlstrom } 5380cd7ec2dcd8d7ba30bf3ca420b40dac52849876cBrian Carlstrom if (!phi_blocks->Equal(tmp_blocks)) { 5390cd7ec2dcd8d7ba30bf3ca420b40dac52849876cBrian Carlstrom change = true; 5400cd7ec2dcd8d7ba30bf3ca420b40dac52849876cBrian Carlstrom phi_blocks->Copy(tmp_blocks); 5410cd7ec2dcd8d7ba30bf3ca420b40dac52849876cBrian Carlstrom 5420cd7ec2dcd8d7ba30bf3ca420b40dac52849876cBrian Carlstrom /* 5430cd7ec2dcd8d7ba30bf3ca420b40dac52849876cBrian Carlstrom * Iterate through the original blocks plus the new ones in 5440cd7ec2dcd8d7ba30bf3ca420b40dac52849876cBrian Carlstrom * the dominance frontier. 5450cd7ec2dcd8d7ba30bf3ca420b40dac52849876cBrian Carlstrom */ 5460cd7ec2dcd8d7ba30bf3ca420b40dac52849876cBrian Carlstrom input_blocks->Copy(phi_blocks); 5470cd7ec2dcd8d7ba30bf3ca420b40dac52849876cBrian Carlstrom input_blocks->Union(def_block_matrix_[dalvik_reg]); 548a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee } 549a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee } while (change); 550a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee 551a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee /* 552fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee * Insert a phi node for dalvik_reg in the phi_blocks if the Dalvik 553a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee * register is in the live-in set. 554a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee */ 555862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee ArenaBitVector::Iterator iterator(phi_blocks); 556a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee while (true) { 557862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee int idx = iterator.Next(); 5580cd7ec2dcd8d7ba30bf3ca420b40dac52849876cBrian Carlstrom if (idx == -1) { 5590cd7ec2dcd8d7ba30bf3ca420b40dac52849876cBrian Carlstrom break; 5600cd7ec2dcd8d7ba30bf3ca420b40dac52849876cBrian Carlstrom } 561311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee BasicBlock* phi_bb = GetBasicBlock(idx); 562a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee /* Variable will be clobbered before being used - no need for phi */ 5630cd7ec2dcd8d7ba30bf3ca420b40dac52849876cBrian Carlstrom if (!phi_bb->data_flow_info->live_in_v->IsBitSet(dalvik_reg)) { 5640cd7ec2dcd8d7ba30bf3ca420b40dac52849876cBrian Carlstrom continue; 5650cd7ec2dcd8d7ba30bf3ca420b40dac52849876cBrian Carlstrom } 566862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee MIR *phi = 567f6c4b3ba3825de1dbb3e747a68b809c6cc8eb4dbMathieu Chartier static_cast<MIR*>(arena_->Alloc(sizeof(MIR), ArenaAllocator::kAllocDFInfo)); 568cbd6d44c0a94f3d26671b5325aa21bbf1335ffe8buzbee phi->dalvikInsn.opcode = static_cast<Instruction::Code>(kMirOpPhi); 569fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee phi->dalvikInsn.vA = dalvik_reg; 570fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee phi->offset = phi_bb->start_offset; 5717934ac288acfb2552bb0b06ec1f61e5820d924a4Brian Carlstrom phi->m_unit_index = 0; // Arbitrarily assign all Phi nodes to outermost method. 572fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee PrependMIR(phi_bb, phi); 573a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee } 574a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee } 57567bf885d62b1473c833bece1c9e0bb624e6ba391buzbee} 57667bf885d62b1473c833bece1c9e0bb624e6ba391buzbee 57767bf885d62b1473c833bece1c9e0bb624e6ba391buzbee/* 57867bf885d62b1473c833bece1c9e0bb624e6ba391buzbee * Worker function to insert phi-operands with latest SSA names from 57967bf885d62b1473c833bece1c9e0bb624e6ba391buzbee * predecessor blocks 58067bf885d62b1473c833bece1c9e0bb624e6ba391buzbee */ 5812ce745c06271d5223d57dbf08117b20d5b60694aBrian Carlstrombool MIRGraph::InsertPhiNodeOperands(BasicBlock* bb) { 582a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee MIR *mir; 5836969d50c820bd63043940b0e0f0ddc6e6ac763b0buzbee std::vector<int> uses; 584fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee std::vector<int> incoming_arc; 585a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee 586a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee /* Phi nodes are at the beginning of each block */ 58728c9a83398a6e48eefb9b79a390920629bbb8519buzbee for (mir = bb->first_mir_insn; mir != NULL; mir = mir->next) { 588cbd6d44c0a94f3d26671b5325aa21bbf1335ffe8buzbee if (mir->dalvikInsn.opcode != static_cast<Instruction::Code>(kMirOpPhi)) 589a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee return true; 590fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee int ssa_reg = mir->ssa_rep->defs[0]; 591fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee DCHECK_GE(ssa_reg, 0); // Shouldn't see compiler temps here 592311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee int v_reg = SRegToVReg(ssa_reg); 59367bf885d62b1473c833bece1c9e0bb624e6ba391buzbee 5946969d50c820bd63043940b0e0f0ddc6e6ac763b0buzbee uses.clear(); 595fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee incoming_arc.clear(); 59667bf885d62b1473c833bece1c9e0bb624e6ba391buzbee 597a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee /* Iterate through the predecessors */ 598862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee GrowableArray<BasicBlock*>::Iterator iter(bb->predecessors); 599a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee while (true) { 600862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee BasicBlock* pred_bb = iter.Next(); 6010cd7ec2dcd8d7ba30bf3ca420b40dac52849876cBrian Carlstrom if (!pred_bb) { 6020cd7ec2dcd8d7ba30bf3ca420b40dac52849876cBrian Carlstrom break; 6030cd7ec2dcd8d7ba30bf3ca420b40dac52849876cBrian Carlstrom } 604fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee int ssa_reg = pred_bb->data_flow_info->vreg_to_ssa_map[v_reg]; 605fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee uses.push_back(ssa_reg); 606fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee incoming_arc.push_back(pred_bb->id); 607a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee } 60867bf885d62b1473c833bece1c9e0bb624e6ba391buzbee 609a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee /* Count the number of SSA registers for a Dalvik register */ 610fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee int num_uses = uses.size(); 611fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee mir->ssa_rep->num_uses = num_uses; 612fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee mir->ssa_rep->uses = 613f6c4b3ba3825de1dbb3e747a68b809c6cc8eb4dbMathieu Chartier static_cast<int*>(arena_->Alloc(sizeof(int) * num_uses, ArenaAllocator::kAllocDFInfo)); 614fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee mir->ssa_rep->fp_use = 615f6c4b3ba3825de1dbb3e747a68b809c6cc8eb4dbMathieu Chartier static_cast<bool*>(arena_->Alloc(sizeof(bool) * num_uses, ArenaAllocator::kAllocDFInfo)); 6162cfc639fc803bf67e3d2a961f2b637220c86d5f7buzbee int* incoming = 617f6c4b3ba3825de1dbb3e747a68b809c6cc8eb4dbMathieu Chartier static_cast<int*>(arena_->Alloc(sizeof(int) * num_uses, ArenaAllocator::kAllocDFInfo)); 6182cfc639fc803bf67e3d2a961f2b637220c86d5f7buzbee // TODO: Ugly, rework (but don't burden each MIR/LIR for Phi-only needs) 619cbd6d44c0a94f3d26671b5325aa21bbf1335ffe8buzbee mir->dalvikInsn.vB = reinterpret_cast<uintptr_t>(incoming); 62067bf885d62b1473c833bece1c9e0bb624e6ba391buzbee 621a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee /* Set the uses array for the phi node */ 622fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee int *use_ptr = mir->ssa_rep->uses; 623fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee for (int i = 0; i < num_uses; i++) { 624fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee *use_ptr++ = uses[i]; 625fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee *incoming++ = incoming_arc[i]; 62667bf885d62b1473c833bece1c9e0bb624e6ba391buzbee } 627a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee } 62867bf885d62b1473c833bece1c9e0bb624e6ba391buzbee 629a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee return true; 63067bf885d62b1473c833bece1c9e0bb624e6ba391buzbee} 63167bf885d62b1473c833bece1c9e0bb624e6ba391buzbee 6322ce745c06271d5223d57dbf08117b20d5b60694aBrian Carlstromvoid MIRGraph::DoDFSPreOrderSSARename(BasicBlock* block) { 6330cd7ec2dcd8d7ba30bf3ca420b40dac52849876cBrian Carlstrom if (block->visited || block->hidden) { 6340cd7ec2dcd8d7ba30bf3ca420b40dac52849876cBrian Carlstrom return; 6350cd7ec2dcd8d7ba30bf3ca420b40dac52849876cBrian Carlstrom } 636a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee block->visited = true; 637a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee 638a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee /* Process this block */ 639311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee DoSSAConversion(block); 640311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee int map_size = sizeof(int) * cu_->num_dalvik_registers; 641a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee 642a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee /* Save SSA map snapshot */ 643862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee int* saved_ssa_map = 644f6c4b3ba3825de1dbb3e747a68b809c6cc8eb4dbMathieu Chartier static_cast<int*>(arena_->Alloc(map_size, ArenaAllocator::kAllocDalvikToSSAMap)); 645311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee memcpy(saved_ssa_map, vreg_to_ssa_map_, map_size); 646a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee 647fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee if (block->fall_through) { 648311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee DoDFSPreOrderSSARename(block->fall_through); 649a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee /* Restore SSA map snapshot */ 650311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee memcpy(vreg_to_ssa_map_, saved_ssa_map, map_size); 651a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee } 652a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee if (block->taken) { 653311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee DoDFSPreOrderSSARename(block->taken); 654a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee /* Restore SSA map snapshot */ 655311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee memcpy(vreg_to_ssa_map_, saved_ssa_map, map_size); 656a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee } 657fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee if (block->successor_block_list.block_list_type != kNotUsed) { 658862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee GrowableArray<SuccessorBlockInfo*>::Iterator iterator(block->successor_block_list.blocks); 659a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee while (true) { 660862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee SuccessorBlockInfo *successor_block_info = iterator.Next(); 6610cd7ec2dcd8d7ba30bf3ca420b40dac52849876cBrian Carlstrom if (successor_block_info == NULL) { 6620cd7ec2dcd8d7ba30bf3ca420b40dac52849876cBrian Carlstrom break; 6630cd7ec2dcd8d7ba30bf3ca420b40dac52849876cBrian Carlstrom } 664fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee BasicBlock* succ_bb = successor_block_info->block; 665311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee DoDFSPreOrderSSARename(succ_bb); 666a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee /* Restore SSA map snapshot */ 667311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee memcpy(vreg_to_ssa_map_, saved_ssa_map, map_size); 668a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee } 669a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee } 670311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee vreg_to_ssa_map_ = saved_ssa_map; 671a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee return; 672f0cde549bed96e16401a347a4511b59130c61e84buzbee} 673f0cde549bed96e16401a347a4511b59130c61e84buzbee 67467bf885d62b1473c833bece1c9e0bb624e6ba391buzbee/* Perform SSA transformation for the whole method */ 6752ce745c06271d5223d57dbf08117b20d5b60694aBrian Carlstromvoid MIRGraph::SSATransformation() { 676a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee /* Compute the DFS order */ 677311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee ComputeDFSOrders(); 67867bf885d62b1473c833bece1c9e0bb624e6ba391buzbee 6791fd3346740dfb7f47be9922312b68a4227fada96buzbee /* Compute the dominator info */ 6801fd3346740dfb7f47be9922312b68a4227fada96buzbee ComputeDominators(); 68167bf885d62b1473c833bece1c9e0bb624e6ba391buzbee 682a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee /* Allocate data structures in preparation for SSA conversion */ 683311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee CompilerInitializeSSAConversion(); 68467bf885d62b1473c833bece1c9e0bb624e6ba391buzbee 6851fd3346740dfb7f47be9922312b68a4227fada96buzbee /* Find out the "Dalvik reg def x block" relation */ 6861fd3346740dfb7f47be9922312b68a4227fada96buzbee ComputeDefBlockMatrix(); 68767bf885d62b1473c833bece1c9e0bb624e6ba391buzbee 6881fd3346740dfb7f47be9922312b68a4227fada96buzbee /* Insert phi nodes to dominance frontiers for all variables */ 6891fd3346740dfb7f47be9922312b68a4227fada96buzbee InsertPhiNodes(); 69067bf885d62b1473c833bece1c9e0bb624e6ba391buzbee 691a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee /* Rename register names by local defs and phi nodes */ 692a5abf7091711eed1e9f1d0e1538fe9963ebdf31cbuzbee ClearAllVisitedFlags(); 693311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee DoDFSPreOrderSSARename(GetEntryBlock()); 694a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee 6951fd3346740dfb7f47be9922312b68a4227fada96buzbee /* 6961fd3346740dfb7f47be9922312b68a4227fada96buzbee * Shared temp bit vector used by each block to count the number of defs 6971fd3346740dfb7f47be9922312b68a4227fada96buzbee * from all the predecessor blocks. 6981fd3346740dfb7f47be9922312b68a4227fada96buzbee */ 699862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee temp_ssa_register_v_ = 700862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee new (arena_) ArenaBitVector(arena_, GetNumSSARegs(), false, kBitMapTempSSARegisterV); 7012cfc639fc803bf67e3d2a961f2b637220c86d5f7buzbee 7021fd3346740dfb7f47be9922312b68a4227fada96buzbee /* Insert phi-operands with latest SSA names from predecessor blocks */ 7031fd3346740dfb7f47be9922312b68a4227fada96buzbee ReachableNodesIterator iter2(this, false /* not iterative */); 7041fd3346740dfb7f47be9922312b68a4227fada96buzbee for (BasicBlock* bb = iter2.Next(); bb != NULL; bb = iter2.Next()) { 7051fd3346740dfb7f47be9922312b68a4227fada96buzbee InsertPhiNodeOperands(bb); 706311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee } 7071fd3346740dfb7f47be9922312b68a4227fada96buzbee 708311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee if (cu_->enable_debug & (1 << kDebugDumpCFG)) { 709311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee DumpCFG("/sdcard/3_post_ssa_cfg/", false); 710a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee } 7111fd3346740dfb7f47be9922312b68a4227fada96buzbee if (cu_->enable_debug & (1 << kDebugVerifyDataflow)) { 7121fd3346740dfb7f47be9922312b68a4227fada96buzbee VerifyDataflow(); 7131fd3346740dfb7f47be9922312b68a4227fada96buzbee } 71467bf885d62b1473c833bece1c9e0bb624e6ba391buzbee} 71511d1b0c31ddd710d26068da8e0e4621002205b4bElliott Hughes 71611d1b0c31ddd710d26068da8e0e4621002205b4bElliott Hughes} // namespace art 717