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" 19c9360ce1f1dabb4075b09dd6db49ee6d4212a6fcVladimir Marko#include "utils/scoped_arena_containers.h" 2067bf885d62b1473c833bece1c9e0bb624e6ba391buzbee 211fd3346740dfb7f47be9922312b68a4227fada96buzbee#define NOTVISITED (-1) 221fd3346740dfb7f47be9922312b68a4227fada96buzbee 2311d1b0c31ddd710d26068da8e0e4621002205b4bElliott Hughesnamespace art { 2411d1b0c31ddd710d26068da8e0e4621002205b4bElliott Hughes 25a5abf7091711eed1e9f1d0e1538fe9963ebdf31cbuzbeevoid MIRGraph::ClearAllVisitedFlags() { 2656c717860df2d71d66fb77aa77f29dd346e559d3buzbee AllNodesIterator iter(this); 27a5abf7091711eed1e9f1d0e1538fe9963ebdf31cbuzbee for (BasicBlock* bb = iter.Next(); bb != NULL; bb = iter.Next()) { 28a5abf7091711eed1e9f1d0e1538fe9963ebdf31cbuzbee bb->visited = false; 29a5abf7091711eed1e9f1d0e1538fe9963ebdf31cbuzbee } 30a5abf7091711eed1e9f1d0e1538fe9963ebdf31cbuzbee} 31a5abf7091711eed1e9f1d0e1538fe9963ebdf31cbuzbee 32311ca169f4727d46a55bdc8dfa0059719fa72b65buzbeeBasicBlock* MIRGraph::NeedsVisit(BasicBlock* bb) { 33e5f01223ae03b89767dc7881d75dca061121ee36buzbee if (bb != NULL) { 34e5f01223ae03b89767dc7881d75dca061121ee36buzbee if (bb->visited || bb->hidden) { 35e5f01223ae03b89767dc7881d75dca061121ee36buzbee bb = NULL; 36e5f01223ae03b89767dc7881d75dca061121ee36buzbee } 37e5f01223ae03b89767dc7881d75dca061121ee36buzbee } 38e5f01223ae03b89767dc7881d75dca061121ee36buzbee return bb; 39e5f01223ae03b89767dc7881d75dca061121ee36buzbee} 40e5f01223ae03b89767dc7881d75dca061121ee36buzbee 412ce745c06271d5223d57dbf08117b20d5b60694aBrian CarlstromBasicBlock* MIRGraph::NextUnvisitedSuccessor(BasicBlock* bb) { 420d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee BasicBlock* res = NeedsVisit(GetBasicBlock(bb->fall_through)); 43e5f01223ae03b89767dc7881d75dca061121ee36buzbee if (res == NULL) { 440d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee res = NeedsVisit(GetBasicBlock(bb->taken)); 45e5f01223ae03b89767dc7881d75dca061121ee36buzbee if (res == NULL) { 460d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee if (bb->successor_block_list_type != kNotUsed) { 470d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee GrowableArray<SuccessorBlockInfo*>::Iterator iterator(bb->successor_blocks); 48e5f01223ae03b89767dc7881d75dca061121ee36buzbee while (true) { 49862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee SuccessorBlockInfo *sbi = iterator.Next(); 500cd7ec2dcd8d7ba30bf3ca420b40dac52849876cBrian Carlstrom if (sbi == NULL) { 510cd7ec2dcd8d7ba30bf3ca420b40dac52849876cBrian Carlstrom break; 520cd7ec2dcd8d7ba30bf3ca420b40dac52849876cBrian Carlstrom } 530d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee res = NeedsVisit(GetBasicBlock(sbi->block)); 540cd7ec2dcd8d7ba30bf3ca420b40dac52849876cBrian Carlstrom if (res != NULL) { 550cd7ec2dcd8d7ba30bf3ca420b40dac52849876cBrian Carlstrom break; 560cd7ec2dcd8d7ba30bf3ca420b40dac52849876cBrian Carlstrom } 57e5f01223ae03b89767dc7881d75dca061121ee36buzbee } 58e5f01223ae03b89767dc7881d75dca061121ee36buzbee } 59e5f01223ae03b89767dc7881d75dca061121ee36buzbee } 60e5f01223ae03b89767dc7881d75dca061121ee36buzbee } 61e5f01223ae03b89767dc7881d75dca061121ee36buzbee return res; 62e5f01223ae03b89767dc7881d75dca061121ee36buzbee} 63e5f01223ae03b89767dc7881d75dca061121ee36buzbee 642ce745c06271d5223d57dbf08117b20d5b60694aBrian Carlstromvoid MIRGraph::MarkPreOrder(BasicBlock* block) { 65e5f01223ae03b89767dc7881d75dca061121ee36buzbee block->visited = true; 66fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee /* Enqueue the pre_order block id */ 670d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee if (block->id != NullBasicBlockId) { 680d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee dfs_order_->Insert(block->id); 690d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee } 70e5f01223ae03b89767dc7881d75dca061121ee36buzbee} 71e5f01223ae03b89767dc7881d75dca061121ee36buzbee 722ce745c06271d5223d57dbf08117b20d5b60694aBrian Carlstromvoid MIRGraph::RecordDFSOrders(BasicBlock* block) { 73c9360ce1f1dabb4075b09dd6db49ee6d4212a6fcVladimir Marko DCHECK(temp_scoped_alloc_.get() != nullptr); 74c9360ce1f1dabb4075b09dd6db49ee6d4212a6fcVladimir Marko ScopedArenaVector<BasicBlock*> succ(temp_scoped_alloc_->Adapter()); 75311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee MarkPreOrder(block); 76e5f01223ae03b89767dc7881d75dca061121ee36buzbee succ.push_back(block); 77e5f01223ae03b89767dc7881d75dca061121ee36buzbee while (!succ.empty()) { 78e5f01223ae03b89767dc7881d75dca061121ee36buzbee BasicBlock* curr = succ.back(); 79fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee BasicBlock* next_successor = NextUnvisitedSuccessor(curr); 80fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee if (next_successor != NULL) { 81311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee MarkPreOrder(next_successor); 82fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee succ.push_back(next_successor); 83e5f01223ae03b89767dc7881d75dca061121ee36buzbee continue; 84e5f01223ae03b89767dc7881d75dca061121ee36buzbee } 85862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee curr->dfs_id = dfs_post_order_->Size(); 860d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee if (curr->id != NullBasicBlockId) { 870d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee dfs_post_order_->Insert(curr->id); 880d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee } 89e5f01223ae03b89767dc7881d75dca061121ee36buzbee succ.pop_back(); 90e5f01223ae03b89767dc7881d75dca061121ee36buzbee } 91e5f01223ae03b89767dc7881d75dca061121ee36buzbee} 92e5f01223ae03b89767dc7881d75dca061121ee36buzbee 935b53710b4abcf8f35c91a963a475b72cb34757e6buzbee/* Sort the blocks by the Depth-First-Search */ 942ce745c06271d5223d57dbf08117b20d5b60694aBrian Carlstromvoid MIRGraph::ComputeDFSOrders() { 95fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee /* Initialize or reset the DFS pre_order list */ 96862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee if (dfs_order_ == NULL) { 970d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee dfs_order_ = new (arena_) GrowableArray<BasicBlockId>(arena_, GetNumBlocks(), 980d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee kGrowableArrayDfsOrder); 99a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee } else { 100a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee /* Just reset the used length on the counter */ 101862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee dfs_order_->Reset(); 102a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee } 103a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee 104fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee /* Initialize or reset the DFS post_order list */ 105862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee if (dfs_post_order_ == NULL) { 1060d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee dfs_post_order_ = new (arena_) GrowableArray<BasicBlockId>(arena_, GetNumBlocks(), 1070d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee kGrowableArrayDfsPostOrder); 108a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee } else { 109a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee /* Just reset the used length on the counter */ 110862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee dfs_post_order_->Reset(); 111311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee } 112a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee 113e5f01223ae03b89767dc7881d75dca061121ee36buzbee // Reset visited flags from all nodes 114a5abf7091711eed1e9f1d0e1538fe9963ebdf31cbuzbee ClearAllVisitedFlags(); 115a5abf7091711eed1e9f1d0e1538fe9963ebdf31cbuzbee 116311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee // Record dfs orders 117311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee RecordDFSOrders(GetEntryBlock()); 118e5f01223ae03b89767dc7881d75dca061121ee36buzbee 119862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee num_reachable_blocks_ = dfs_order_->Size(); 1204439596b00c91f565370bf0813cc2f9165093693Andreas Gampe 1214439596b00c91f565370bf0813cc2f9165093693Andreas Gampe if (num_reachable_blocks_ != num_blocks_) { 1224439596b00c91f565370bf0813cc2f9165093693Andreas Gampe // Hide all unreachable blocks. 1234439596b00c91f565370bf0813cc2f9165093693Andreas Gampe AllNodesIterator iter(this); 1244439596b00c91f565370bf0813cc2f9165093693Andreas Gampe for (BasicBlock* bb = iter.Next(); bb != NULL; bb = iter.Next()) { 1254439596b00c91f565370bf0813cc2f9165093693Andreas Gampe if (!bb->visited) { 1264439596b00c91f565370bf0813cc2f9165093693Andreas Gampe bb->Hide(cu_); 1274439596b00c91f565370bf0813cc2f9165093693Andreas Gampe } 1284439596b00c91f565370bf0813cc2f9165093693Andreas Gampe } 1294439596b00c91f565370bf0813cc2f9165093693Andreas Gampe } 13067bf885d62b1473c833bece1c9e0bb624e6ba391buzbee} 13167bf885d62b1473c833bece1c9e0bb624e6ba391buzbee 13267bf885d62b1473c833bece1c9e0bb624e6ba391buzbee/* 13367bf885d62b1473c833bece1c9e0bb624e6ba391buzbee * Mark block bit on the per-Dalvik register vector to denote that Dalvik 13467bf885d62b1473c833bece1c9e0bb624e6ba391buzbee * register idx is defined in BasicBlock bb. 13567bf885d62b1473c833bece1c9e0bb624e6ba391buzbee */ 1362ce745c06271d5223d57dbf08117b20d5b60694aBrian Carlstrombool MIRGraph::FillDefBlockMatrix(BasicBlock* bb) { 1370cd7ec2dcd8d7ba30bf3ca420b40dac52849876cBrian Carlstrom if (bb->data_flow_info == NULL) { 1380cd7ec2dcd8d7ba30bf3ca420b40dac52849876cBrian Carlstrom return false; 1390cd7ec2dcd8d7ba30bf3ca420b40dac52849876cBrian Carlstrom } 140a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee 141a5b8fde2d2bc3167078694fad417fddfe442a6fdVladimir Marko for (uint32_t idx : bb->data_flow_info->def_v->Indexes()) { 142a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee /* Block bb defines register idx */ 143862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee def_block_matrix_[idx]->SetBit(bb->id); 144a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee } 145a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee return true; 14667bf885d62b1473c833bece1c9e0bb624e6ba391buzbee} 14767bf885d62b1473c833bece1c9e0bb624e6ba391buzbee 1482ce745c06271d5223d57dbf08117b20d5b60694aBrian Carlstromvoid MIRGraph::ComputeDefBlockMatrix() { 149311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee int num_registers = cu_->num_dalvik_registers; 150fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee /* Allocate num_dalvik_registers bit vector pointers */ 151311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee def_block_matrix_ = static_cast<ArenaBitVector**> 152f6c4b3ba3825de1dbb3e747a68b809c6cc8eb4dbMathieu Chartier (arena_->Alloc(sizeof(ArenaBitVector *) * num_registers, 15383cc7ae96d4176533dd0391a1591d321b0a87f4fVladimir Marko kArenaAllocDFInfo)); 154a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee int i; 155a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee 156fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee /* Initialize num_register vectors with num_blocks bits each */ 157fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee for (i = 0; i < num_registers; i++) { 158862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee def_block_matrix_[i] = 159862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee new (arena_) ArenaBitVector(arena_, GetNumBlocks(), false, kBitMapBMatrix); 160311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee } 16156c717860df2d71d66fb77aa77f29dd346e559d3buzbee AllNodesIterator iter(this); 162311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee for (BasicBlock* bb = iter.Next(); bb != NULL; bb = iter.Next()) { 163311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee FindLocalLiveIn(bb); 164311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee } 16556c717860df2d71d66fb77aa77f29dd346e559d3buzbee AllNodesIterator iter2(this); 166311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee for (BasicBlock* bb = iter2.Next(); bb != NULL; bb = iter2.Next()) { 167311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee FillDefBlockMatrix(bb); 168a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee } 169a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee 170a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee /* 171a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee * Also set the incoming parameters as defs in the entry block. 172a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee * Only need to handle the parameters for the outer method. 173a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee */ 174311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee int num_regs = cu_->num_dalvik_registers; 175311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee int in_reg = num_regs - cu_->num_ins; 176fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee for (; in_reg < num_regs; in_reg++) { 177862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee def_block_matrix_[in_reg]->SetBit(GetEntryBlock()->id); 178a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee } 17967bf885d62b1473c833bece1c9e0bb624e6ba391buzbee} 18067bf885d62b1473c833bece1c9e0bb624e6ba391buzbee 181a5abf7091711eed1e9f1d0e1538fe9963ebdf31cbuzbeevoid MIRGraph::ComputeDomPostOrderTraversal(BasicBlock* bb) { 1824896d7b6fb75add25f2d6ba84346ac83d8ba9d51Jean Christophe Beyler if (dom_post_order_traversal_ == NULL || max_num_reachable_blocks_ < num_reachable_blocks_) { 1834896d7b6fb75add25f2d6ba84346ac83d8ba9d51Jean Christophe Beyler // First time or too small - create the array. 184a5abf7091711eed1e9f1d0e1538fe9963ebdf31cbuzbee dom_post_order_traversal_ = 1850d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee new (arena_) GrowableArray<BasicBlockId>(arena_, num_reachable_blocks_, 186a5abf7091711eed1e9f1d0e1538fe9963ebdf31cbuzbee kGrowableArrayDomPostOrderTraversal); 187a5abf7091711eed1e9f1d0e1538fe9963ebdf31cbuzbee } else { 188a5abf7091711eed1e9f1d0e1538fe9963ebdf31cbuzbee dom_post_order_traversal_->Reset(); 189a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee } 190a5abf7091711eed1e9f1d0e1538fe9963ebdf31cbuzbee ClearAllVisitedFlags(); 191c9360ce1f1dabb4075b09dd6db49ee6d4212a6fcVladimir Marko DCHECK(temp_scoped_alloc_.get() != nullptr); 192c9360ce1f1dabb4075b09dd6db49ee6d4212a6fcVladimir Marko ScopedArenaVector<std::pair<BasicBlock*, ArenaBitVector::IndexIterator>> work_stack( 193c9360ce1f1dabb4075b09dd6db49ee6d4212a6fcVladimir Marko temp_scoped_alloc_->Adapter()); 194a5abf7091711eed1e9f1d0e1538fe9963ebdf31cbuzbee bb->visited = true; 195a5b8fde2d2bc3167078694fad417fddfe442a6fdVladimir Marko work_stack.push_back(std::make_pair(bb, bb->i_dominated->Indexes().begin())); 196a5abf7091711eed1e9f1d0e1538fe9963ebdf31cbuzbee while (!work_stack.empty()) { 197a5b8fde2d2bc3167078694fad417fddfe442a6fdVladimir Marko std::pair<BasicBlock*, ArenaBitVector::IndexIterator>* curr = &work_stack.back(); 198a5b8fde2d2bc3167078694fad417fddfe442a6fdVladimir Marko BasicBlock* curr_bb = curr->first; 199a5b8fde2d2bc3167078694fad417fddfe442a6fdVladimir Marko ArenaBitVector::IndexIterator* curr_idom_iter = &curr->second; 200a5b8fde2d2bc3167078694fad417fddfe442a6fdVladimir Marko while (!curr_idom_iter->Done() && (NeedsVisit(GetBasicBlock(**curr_idom_iter)) == nullptr)) { 201a5b8fde2d2bc3167078694fad417fddfe442a6fdVladimir Marko ++*curr_idom_iter; 202a5abf7091711eed1e9f1d0e1538fe9963ebdf31cbuzbee } 203a5b8fde2d2bc3167078694fad417fddfe442a6fdVladimir Marko // NOTE: work_stack.push_back()/pop_back() invalidate curr and curr_idom_iter. 204a5b8fde2d2bc3167078694fad417fddfe442a6fdVladimir Marko if (!curr_idom_iter->Done()) { 205a5b8fde2d2bc3167078694fad417fddfe442a6fdVladimir Marko BasicBlock* new_bb = GetBasicBlock(**curr_idom_iter); 206a5b8fde2d2bc3167078694fad417fddfe442a6fdVladimir Marko ++*curr_idom_iter; 207a5abf7091711eed1e9f1d0e1538fe9963ebdf31cbuzbee new_bb->visited = true; 208a5b8fde2d2bc3167078694fad417fddfe442a6fdVladimir Marko work_stack.push_back(std::make_pair(new_bb, new_bb->i_dominated->Indexes().begin())); 209a5abf7091711eed1e9f1d0e1538fe9963ebdf31cbuzbee } else { 210a5abf7091711eed1e9f1d0e1538fe9963ebdf31cbuzbee // no successor/next 2110d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee if (curr_bb->id != NullBasicBlockId) { 2120d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee dom_post_order_traversal_->Insert(curr_bb->id); 2130d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee } 214a5abf7091711eed1e9f1d0e1538fe9963ebdf31cbuzbee work_stack.pop_back(); 215a5abf7091711eed1e9f1d0e1538fe9963ebdf31cbuzbee 216a5abf7091711eed1e9f1d0e1538fe9963ebdf31cbuzbee /* hacky loop detection */ 2170d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee if ((curr_bb->taken != NullBasicBlockId) && curr_bb->dominators->IsBitSet(curr_bb->taken)) { 2180b1191cfece83f6f8d4101575a06555a2d13387aBill Buzbee curr_bb->nesting_depth++; 219a5abf7091711eed1e9f1d0e1538fe9963ebdf31cbuzbee attributes_ |= METHOD_HAS_LOOP; 220a5abf7091711eed1e9f1d0e1538fe9963ebdf31cbuzbee } 221a5abf7091711eed1e9f1d0e1538fe9963ebdf31cbuzbee } 222a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee } 22367bf885d62b1473c833bece1c9e0bb624e6ba391buzbee} 22467bf885d62b1473c833bece1c9e0bb624e6ba391buzbee 225311ca169f4727d46a55bdc8dfa0059719fa72b65buzbeevoid MIRGraph::CheckForDominanceFrontier(BasicBlock* dom_bb, 2262ce745c06271d5223d57dbf08117b20d5b60694aBrian Carlstrom const BasicBlock* succ_bb) { 227a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee /* 228a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee * TODO - evaluate whether phi will ever need to be inserted into exit 229a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee * blocks. 230a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee */ 2310d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee if (succ_bb->i_dom != dom_bb->id && 232fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee succ_bb->block_type == kDalvikByteCode && 233fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee succ_bb->hidden == false) { 234862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee dom_bb->dom_frontier->SetBit(succ_bb->id); 235a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee } 23667bf885d62b1473c833bece1c9e0bb624e6ba391buzbee} 23767bf885d62b1473c833bece1c9e0bb624e6ba391buzbee 23867bf885d62b1473c833bece1c9e0bb624e6ba391buzbee/* Worker function to compute the dominance frontier */ 2392ce745c06271d5223d57dbf08117b20d5b60694aBrian Carlstrombool MIRGraph::ComputeDominanceFrontier(BasicBlock* bb) { 240a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee /* Calculate DF_local */ 2410d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee if (bb->taken != NullBasicBlockId) { 2420d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee CheckForDominanceFrontier(bb, GetBasicBlock(bb->taken)); 243a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee } 2440d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee if (bb->fall_through != NullBasicBlockId) { 2450d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee CheckForDominanceFrontier(bb, GetBasicBlock(bb->fall_through)); 246a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee } 2470d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee if (bb->successor_block_list_type != kNotUsed) { 2480d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee GrowableArray<SuccessorBlockInfo*>::Iterator iterator(bb->successor_blocks); 249a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee while (true) { 250862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee SuccessorBlockInfo *successor_block_info = iterator.Next(); 2510cd7ec2dcd8d7ba30bf3ca420b40dac52849876cBrian Carlstrom if (successor_block_info == NULL) { 2520cd7ec2dcd8d7ba30bf3ca420b40dac52849876cBrian Carlstrom break; 2530cd7ec2dcd8d7ba30bf3ca420b40dac52849876cBrian Carlstrom } 2540d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee BasicBlock* succ_bb = GetBasicBlock(successor_block_info->block); 255311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee CheckForDominanceFrontier(bb, succ_bb); 256a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee } 257a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee } 258a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee 259a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee /* Calculate DF_up */ 260a5b8fde2d2bc3167078694fad417fddfe442a6fdVladimir Marko for (uint32_t dominated_idx : bb->i_dominated->Indexes()) { 2612469e60e6ff08c2a0b4cd1e209246c5d91027679Jean Christophe Beyler BasicBlock* dominated_bb = GetBasicBlock(dominated_idx); 262a5b8fde2d2bc3167078694fad417fddfe442a6fdVladimir Marko for (uint32_t df_up_block_idx : dominated_bb->dom_frontier->Indexes()) { 2632469e60e6ff08c2a0b4cd1e209246c5d91027679Jean Christophe Beyler BasicBlock* df_up_block = GetBasicBlock(df_up_block_idx); 264311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee CheckForDominanceFrontier(bb, df_up_block); 26567bf885d62b1473c833bece1c9e0bb624e6ba391buzbee } 266a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee } 26767bf885d62b1473c833bece1c9e0bb624e6ba391buzbee 268a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee return true; 26967bf885d62b1473c833bece1c9e0bb624e6ba391buzbee} 27067bf885d62b1473c833bece1c9e0bb624e6ba391buzbee 27167bf885d62b1473c833bece1c9e0bb624e6ba391buzbee/* Worker function for initializing domination-related data structures */ 2722ce745c06271d5223d57dbf08117b20d5b60694aBrian Carlstromvoid MIRGraph::InitializeDominationInfo(BasicBlock* bb) { 273311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee int num_total_blocks = GetBasicBlockListCount(); 274a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee 275df62950e7a32031b82360c407d46a37b94188fbbBrian Carlstrom if (bb->dominators == NULL) { 276862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee bb->dominators = new (arena_) ArenaBitVector(arena_, num_total_blocks, 277862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee false /* expandable */, kBitMapDominators); 278862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee bb->i_dominated = new (arena_) ArenaBitVector(arena_, num_total_blocks, 279862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee false /* expandable */, kBitMapIDominated); 280862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee bb->dom_frontier = new (arena_) ArenaBitVector(arena_, num_total_blocks, 281862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee false /* expandable */, kBitMapDomFrontier); 282a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee } else { 283862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee bb->dominators->ClearAllBits(); 284862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee bb->i_dominated->ClearAllBits(); 285862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee bb->dom_frontier->ClearAllBits(); 286a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee } 287a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee /* Set all bits in the dominator vector */ 288862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee bb->dominators->SetInitialBits(num_total_blocks); 289a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee 290862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee return; 29167bf885d62b1473c833bece1c9e0bb624e6ba391buzbee} 29267bf885d62b1473c833bece1c9e0bb624e6ba391buzbee 2935b53710b4abcf8f35c91a963a475b72cb34757e6buzbee/* 294fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee * Walk through the ordered i_dom list until we reach common parent. 295fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee * Given the ordering of i_dom_list, this common parent represents the 2965b53710b4abcf8f35c91a963a475b72cb34757e6buzbee * last element of the intersection of block1 and block2 dominators. 2975b53710b4abcf8f35c91a963a475b72cb34757e6buzbee */ 2982ce745c06271d5223d57dbf08117b20d5b60694aBrian Carlstromint MIRGraph::FindCommonParent(int block1, int block2) { 299a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee while (block1 != block2) { 300a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee while (block1 < block2) { 301311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee block1 = i_dom_list_[block1]; 302a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee DCHECK_NE(block1, NOTVISITED); 303a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee } 304a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee while (block2 < block1) { 305311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee block2 = i_dom_list_[block2]; 306a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee DCHECK_NE(block2, NOTVISITED); 3075b53710b4abcf8f35c91a963a475b72cb34757e6buzbee } 308a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee } 309a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee return block1; 3105b53710b4abcf8f35c91a963a475b72cb34757e6buzbee} 3115b53710b4abcf8f35c91a963a475b72cb34757e6buzbee 3125b53710b4abcf8f35c91a963a475b72cb34757e6buzbee/* Worker function to compute each block's immediate dominator */ 3132ce745c06271d5223d57dbf08117b20d5b60694aBrian Carlstrombool MIRGraph::ComputeblockIDom(BasicBlock* bb) { 314a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee /* Special-case entry block */ 3150d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee if ((bb->id == NullBasicBlockId) || (bb == GetEntryBlock())) { 3165b53710b4abcf8f35c91a963a475b72cb34757e6buzbee return false; 317a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee } 318a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee 319a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee /* Iterate through the predecessors */ 3200d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee GrowableArray<BasicBlockId>::Iterator iter(bb->predecessors); 321a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee 322a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee /* Find the first processed predecessor */ 323862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee int idom = -1; 324a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee while (true) { 3250d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee BasicBlock* pred_bb = GetBasicBlock(iter.Next()); 326fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee CHECK(pred_bb != NULL); 327311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee if (i_dom_list_[pred_bb->dfs_id] != NOTVISITED) { 328fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee idom = pred_bb->dfs_id; 329a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee break; 330a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee } 331a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee } 332a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee 333a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee /* Scan the rest of the predecessors */ 334a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee while (true) { 3350d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee BasicBlock* pred_bb = GetBasicBlock(iter.Next()); 3360cd7ec2dcd8d7ba30bf3ca420b40dac52849876cBrian Carlstrom if (!pred_bb) { 3370cd7ec2dcd8d7ba30bf3ca420b40dac52849876cBrian Carlstrom break; 3380cd7ec2dcd8d7ba30bf3ca420b40dac52849876cBrian Carlstrom } 339311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee if (i_dom_list_[pred_bb->dfs_id] == NOTVISITED) { 340a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee continue; 341a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee } else { 342311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee idom = FindCommonParent(pred_bb->dfs_id, idom); 343a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee } 344a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee } 345a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee 346a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee DCHECK_NE(idom, NOTVISITED); 347a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee 348a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee /* Did something change? */ 349311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee if (i_dom_list_[bb->dfs_id] != idom) { 350311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee i_dom_list_[bb->dfs_id] = idom; 351a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee return true; 352a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee } 353a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee return false; 3545b53710b4abcf8f35c91a963a475b72cb34757e6buzbee} 3555b53710b4abcf8f35c91a963a475b72cb34757e6buzbee 3565b53710b4abcf8f35c91a963a475b72cb34757e6buzbee/* Worker function to compute each block's domintors */ 3572ce745c06271d5223d57dbf08117b20d5b60694aBrian Carlstrombool MIRGraph::ComputeBlockDominators(BasicBlock* bb) { 358311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee if (bb == GetEntryBlock()) { 359862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee bb->dominators->ClearAllBits(); 360a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee } else { 3610d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee bb->dominators->Copy(GetBasicBlock(bb->i_dom)->dominators); 362a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee } 363862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee bb->dominators->SetBit(bb->id); 364a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee return false; 3655b53710b4abcf8f35c91a963a475b72cb34757e6buzbee} 3665b53710b4abcf8f35c91a963a475b72cb34757e6buzbee 3672ce745c06271d5223d57dbf08117b20d5b60694aBrian Carlstrombool MIRGraph::SetDominators(BasicBlock* bb) { 368311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee if (bb != GetEntryBlock()) { 369311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee int idom_dfs_idx = i_dom_list_[bb->dfs_id]; 370fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee DCHECK_NE(idom_dfs_idx, NOTVISITED); 371862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee int i_dom_idx = dfs_post_order_->Get(idom_dfs_idx); 372311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee BasicBlock* i_dom = GetBasicBlock(i_dom_idx); 3730d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee bb->i_dom = i_dom->id; 374fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee /* Add bb to the i_dominated set of the immediate dominator block */ 375862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee i_dom->i_dominated->SetBit(bb->id); 376a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee } 377a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee return false; 3785b53710b4abcf8f35c91a963a475b72cb34757e6buzbee} 3795b53710b4abcf8f35c91a963a475b72cb34757e6buzbee 38067bf885d62b1473c833bece1c9e0bb624e6ba391buzbee/* Compute dominators, immediate dominator, and dominance fronter */ 3812ce745c06271d5223d57dbf08117b20d5b60694aBrian Carlstromvoid MIRGraph::ComputeDominators() { 382311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee int num_reachable_blocks = num_reachable_blocks_; 383a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee 384a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee /* Initialize domination-related data structures */ 38556c717860df2d71d66fb77aa77f29dd346e559d3buzbee PreOrderDfsIterator iter(this); 386311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee for (BasicBlock* bb = iter.Next(); bb != NULL; bb = iter.Next()) { 387311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee InitializeDominationInfo(bb); 388311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee } 389a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee 3904896d7b6fb75add25f2d6ba84346ac83d8ba9d51Jean Christophe Beyler /* Initialize & Clear i_dom_list */ 3914896d7b6fb75add25f2d6ba84346ac83d8ba9d51Jean Christophe Beyler if (max_num_reachable_blocks_ < num_reachable_blocks_) { 392f6c4b3ba3825de1dbb3e747a68b809c6cc8eb4dbMathieu Chartier i_dom_list_ = static_cast<int*>(arena_->Alloc(sizeof(int) * num_reachable_blocks, 39383cc7ae96d4176533dd0391a1591d321b0a87f4fVladimir Marko kArenaAllocDFInfo)); 394a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee } 395fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee for (int i = 0; i < num_reachable_blocks; i++) { 396311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee i_dom_list_[i] = NOTVISITED; 397a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee } 398a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee 399fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee /* For post-order, last block is entry block. Set its i_dom to istelf */ 400311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee DCHECK_EQ(GetEntryBlock()->dfs_id, num_reachable_blocks-1); 401311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee i_dom_list_[GetEntryBlock()->dfs_id] = GetEntryBlock()->dfs_id; 402a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee 403a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee /* Compute the immediate dominators */ 40456c717860df2d71d66fb77aa77f29dd346e559d3buzbee RepeatingReversePostOrderDfsIterator iter2(this); 405311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee bool change = false; 406311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee for (BasicBlock* bb = iter2.Next(false); bb != NULL; bb = iter2.Next(change)) { 407311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee change = ComputeblockIDom(bb); 408311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee } 409a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee 410a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee /* Set the dominator for the root node */ 411862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee GetEntryBlock()->dominators->ClearAllBits(); 412862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee GetEntryBlock()->dominators->SetBit(GetEntryBlock()->id); 413a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee 4140d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee GetEntryBlock()->i_dom = 0; 4155b53710b4abcf8f35c91a963a475b72cb34757e6buzbee 41656c717860df2d71d66fb77aa77f29dd346e559d3buzbee PreOrderDfsIterator iter3(this); 417311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee for (BasicBlock* bb = iter3.Next(); bb != NULL; bb = iter3.Next()) { 418311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee SetDominators(bb); 419a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee } 420a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee 42156c717860df2d71d66fb77aa77f29dd346e559d3buzbee ReversePostOrderDfsIterator iter4(this); 422311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee for (BasicBlock* bb = iter4.Next(); bb != NULL; bb = iter4.Next()) { 423311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee ComputeBlockDominators(bb); 424311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee } 425a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee 426a5abf7091711eed1e9f1d0e1538fe9963ebdf31cbuzbee // Compute the dominance frontier for each block. 427311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee ComputeDomPostOrderTraversal(GetEntryBlock()); 42856c717860df2d71d66fb77aa77f29dd346e559d3buzbee PostOrderDOMIterator iter5(this); 429311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee for (BasicBlock* bb = iter5.Next(); bb != NULL; bb = iter5.Next()) { 430311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee ComputeDominanceFrontier(bb); 431311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee } 43267bf885d62b1473c833bece1c9e0bb624e6ba391buzbee} 43367bf885d62b1473c833bece1c9e0bb624e6ba391buzbee 43467bf885d62b1473c833bece1c9e0bb624e6ba391buzbee/* 43567bf885d62b1473c833bece1c9e0bb624e6ba391buzbee * Perform dest U= src1 ^ ~src2 43667bf885d62b1473c833bece1c9e0bb624e6ba391buzbee * This is probably not general enough to be placed in BitVector.[ch]. 43767bf885d62b1473c833bece1c9e0bb624e6ba391buzbee */ 438311ca169f4727d46a55bdc8dfa0059719fa72b65buzbeevoid MIRGraph::ComputeSuccLineIn(ArenaBitVector* dest, const ArenaBitVector* src1, 4392ce745c06271d5223d57dbf08117b20d5b60694aBrian Carlstrom const ArenaBitVector* src2) { 440862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee if (dest->GetStorageSize() != src1->GetStorageSize() || 441862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee dest->GetStorageSize() != src2->GetStorageSize() || 442862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee dest->IsExpandable() != src1->IsExpandable() || 443862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee dest->IsExpandable() != src2->IsExpandable()) { 444a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee LOG(FATAL) << "Incompatible set properties"; 445a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee } 446a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee 447a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee unsigned int idx; 448862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee for (idx = 0; idx < dest->GetStorageSize(); idx++) { 449862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee dest->GetRawStorage()[idx] |= src1->GetRawStorageWord(idx) & ~(src2->GetRawStorageWord(idx)); 450a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee } 45167bf885d62b1473c833bece1c9e0bb624e6ba391buzbee} 45267bf885d62b1473c833bece1c9e0bb624e6ba391buzbee 45367bf885d62b1473c833bece1c9e0bb624e6ba391buzbee/* 45467bf885d62b1473c833bece1c9e0bb624e6ba391buzbee * Iterate through all successor blocks and propagate up the live-in sets. 45567bf885d62b1473c833bece1c9e0bb624e6ba391buzbee * The calculated result is used for phi-node pruning - where we only need to 45667bf885d62b1473c833bece1c9e0bb624e6ba391buzbee * insert a phi node if the variable is live-in to the block. 45767bf885d62b1473c833bece1c9e0bb624e6ba391buzbee */ 4582ce745c06271d5223d57dbf08117b20d5b60694aBrian Carlstrombool MIRGraph::ComputeBlockLiveIns(BasicBlock* bb) { 459a5b8fde2d2bc3167078694fad417fddfe442a6fdVladimir Marko DCHECK_EQ(temp_bit_vector_size_, cu_->num_dalvik_registers); 460a5b8fde2d2bc3167078694fad417fddfe442a6fdVladimir Marko ArenaBitVector* temp_dalvik_register_v = temp_bit_vector_; 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); 4660d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee BasicBlock* bb_taken = GetBasicBlock(bb->taken); 4670d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee BasicBlock* bb_fall_through = GetBasicBlock(bb->fall_through); 4680d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee if (bb_taken && bb_taken->data_flow_info) 4690d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee ComputeSuccLineIn(temp_dalvik_register_v, bb_taken->data_flow_info->live_in_v, 470fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee bb->data_flow_info->def_v); 4710d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee if (bb_fall_through && bb_fall_through->data_flow_info) 4720d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee ComputeSuccLineIn(temp_dalvik_register_v, bb_fall_through->data_flow_info->live_in_v, 473fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee bb->data_flow_info->def_v); 4740d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee if (bb->successor_block_list_type != kNotUsed) { 4750d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee GrowableArray<SuccessorBlockInfo*>::Iterator iterator(bb->successor_blocks); 476a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee while (true) { 477862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee SuccessorBlockInfo *successor_block_info = iterator.Next(); 4780cd7ec2dcd8d7ba30bf3ca420b40dac52849876cBrian Carlstrom if (successor_block_info == NULL) { 4790cd7ec2dcd8d7ba30bf3ca420b40dac52849876cBrian Carlstrom break; 4800cd7ec2dcd8d7ba30bf3ca420b40dac52849876cBrian Carlstrom } 4810d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee BasicBlock* succ_bb = GetBasicBlock(successor_block_info->block); 482fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee if (succ_bb->data_flow_info) { 483311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee ComputeSuccLineIn(temp_dalvik_register_v, succ_bb->data_flow_info->live_in_v, 484fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee bb->data_flow_info->def_v); 485a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee } 48667bf885d62b1473c833bece1c9e0bb624e6ba391buzbee } 487a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee } 488862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee if (!temp_dalvik_register_v->Equal(bb->data_flow_info->live_in_v)) { 489862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee bb->data_flow_info->live_in_v->Copy(temp_dalvik_register_v); 490a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee return true; 491a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee } 492a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee return false; 49367bf885d62b1473c833bece1c9e0bb624e6ba391buzbee} 49467bf885d62b1473c833bece1c9e0bb624e6ba391buzbee 49567bf885d62b1473c833bece1c9e0bb624e6ba391buzbee/* Insert phi nodes to for each variable to the dominance frontiers */ 4962ce745c06271d5223d57dbf08117b20d5b60694aBrian Carlstromvoid MIRGraph::InsertPhiNodes() { 497fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee int dalvik_reg; 498a5b8fde2d2bc3167078694fad417fddfe442a6fdVladimir Marko ArenaBitVector* phi_blocks = new (temp_scoped_alloc_.get()) ArenaBitVector( 499a5b8fde2d2bc3167078694fad417fddfe442a6fdVladimir Marko temp_scoped_alloc_.get(), GetNumBlocks(), false, kBitMapPhi); 500a5b8fde2d2bc3167078694fad417fddfe442a6fdVladimir Marko ArenaBitVector* input_blocks = new (temp_scoped_alloc_.get()) ArenaBitVector( 501a5b8fde2d2bc3167078694fad417fddfe442a6fdVladimir Marko temp_scoped_alloc_.get(), GetNumBlocks(), false, kBitMapInputBlocks); 502a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee 50356c717860df2d71d66fb77aa77f29dd346e559d3buzbee RepeatingPostOrderDfsIterator iter(this); 504311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee bool change = false; 505311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee for (BasicBlock* bb = iter.Next(false); bb != NULL; bb = iter.Next(change)) { 506311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee change = ComputeBlockLiveIns(bb); 507311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee } 508a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee 509a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee /* Iterate through each Dalvik register */ 510311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee for (dalvik_reg = cu_->num_dalvik_registers - 1; dalvik_reg >= 0; dalvik_reg--) { 511862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee input_blocks->Copy(def_block_matrix_[dalvik_reg]); 512862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee phi_blocks->ClearAllBits(); 513a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee do { 514a5b8fde2d2bc3167078694fad417fddfe442a6fdVladimir Marko // TUNING: When we repeat this, we could skip indexes from the previous pass. 515a5b8fde2d2bc3167078694fad417fddfe442a6fdVladimir Marko for (uint32_t idx : input_blocks->Indexes()) { 5160cd7ec2dcd8d7ba30bf3ca420b40dac52849876cBrian Carlstrom BasicBlock* def_bb = GetBasicBlock(idx); 517a5b8fde2d2bc3167078694fad417fddfe442a6fdVladimir Marko if (def_bb->dom_frontier != nullptr) { 518a5b8fde2d2bc3167078694fad417fddfe442a6fdVladimir Marko phi_blocks->Union(def_bb->dom_frontier); 51967bf885d62b1473c833bece1c9e0bb624e6ba391buzbee } 5200cd7ec2dcd8d7ba30bf3ca420b40dac52849876cBrian Carlstrom } 521a5b8fde2d2bc3167078694fad417fddfe442a6fdVladimir Marko } while (input_blocks->Union(phi_blocks)); 522a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee 523a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee /* 524fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee * Insert a phi node for dalvik_reg in the phi_blocks if the Dalvik 525a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee * register is in the live-in set. 526a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee */ 527a5b8fde2d2bc3167078694fad417fddfe442a6fdVladimir Marko for (uint32_t idx : phi_blocks->Indexes()) { 528311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee BasicBlock* phi_bb = GetBasicBlock(idx); 529a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee /* Variable will be clobbered before being used - no need for phi */ 5300cd7ec2dcd8d7ba30bf3ca420b40dac52849876cBrian Carlstrom if (!phi_bb->data_flow_info->live_in_v->IsBitSet(dalvik_reg)) { 5310cd7ec2dcd8d7ba30bf3ca420b40dac52849876cBrian Carlstrom continue; 5320cd7ec2dcd8d7ba30bf3ca420b40dac52849876cBrian Carlstrom } 5333aa57730e2aec451bb836918d936c6862598d8d6Jean Christophe Beyler MIR *phi = NewMIR(); 534cbd6d44c0a94f3d26671b5325aa21bbf1335ffe8buzbee phi->dalvikInsn.opcode = static_cast<Instruction::Code>(kMirOpPhi); 535fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee phi->dalvikInsn.vA = dalvik_reg; 536fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee phi->offset = phi_bb->start_offset; 5377934ac288acfb2552bb0b06ec1f61e5820d924a4Brian Carlstrom phi->m_unit_index = 0; // Arbitrarily assign all Phi nodes to outermost method. 538cdacac4a8196bdc620185079ec9e886329606f3dJean Christophe Beyler phi_bb->PrependMIR(phi); 539a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee } 540a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee } 54167bf885d62b1473c833bece1c9e0bb624e6ba391buzbee} 54267bf885d62b1473c833bece1c9e0bb624e6ba391buzbee 54367bf885d62b1473c833bece1c9e0bb624e6ba391buzbee/* 54467bf885d62b1473c833bece1c9e0bb624e6ba391buzbee * Worker function to insert phi-operands with latest SSA names from 54567bf885d62b1473c833bece1c9e0bb624e6ba391buzbee * predecessor blocks 54667bf885d62b1473c833bece1c9e0bb624e6ba391buzbee */ 5472ce745c06271d5223d57dbf08117b20d5b60694aBrian Carlstrombool MIRGraph::InsertPhiNodeOperands(BasicBlock* bb) { 548a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee /* Phi nodes are at the beginning of each block */ 5490d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee for (MIR* mir = bb->first_mir_insn; mir != NULL; mir = mir->next) { 550cbd6d44c0a94f3d26671b5325aa21bbf1335ffe8buzbee if (mir->dalvikInsn.opcode != static_cast<Instruction::Code>(kMirOpPhi)) 551a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee return true; 552fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee int ssa_reg = mir->ssa_rep->defs[0]; 553fa57c47f1b72916371a9c2d5c1389219bce655b4buzbee DCHECK_GE(ssa_reg, 0); // Shouldn't see compiler temps here 554311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee int v_reg = SRegToVReg(ssa_reg); 55567bf885d62b1473c833bece1c9e0bb624e6ba391buzbee 556a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee /* Iterate through the predecessors */ 5570d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee GrowableArray<BasicBlockId>::Iterator iter(bb->predecessors); 5580d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee size_t num_uses = bb->predecessors->Size(); 5594896d7b6fb75add25f2d6ba84346ac83d8ba9d51Jean Christophe Beyler AllocateSSAUseData(mir, num_uses); 5604896d7b6fb75add25f2d6ba84346ac83d8ba9d51Jean Christophe Beyler int* uses = mir->ssa_rep->uses; 5610d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee BasicBlockId* incoming = 5620d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee static_cast<BasicBlockId*>(arena_->Alloc(sizeof(BasicBlockId) * num_uses, 56383cc7ae96d4176533dd0391a1591d321b0a87f4fVladimir Marko kArenaAllocDFInfo)); 5640d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee mir->meta.phi_incoming = incoming; 5650d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee int idx = 0; 566a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee while (true) { 5670d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee BasicBlock* pred_bb = GetBasicBlock(iter.Next()); 5680cd7ec2dcd8d7ba30bf3ca420b40dac52849876cBrian Carlstrom if (!pred_bb) { 5694896d7b6fb75add25f2d6ba84346ac83d8ba9d51Jean Christophe Beyler break; 5700cd7ec2dcd8d7ba30bf3ca420b40dac52849876cBrian Carlstrom } 5714896d7b6fb75add25f2d6ba84346ac83d8ba9d51Jean Christophe Beyler int ssa_reg = pred_bb->data_flow_info->vreg_to_ssa_map_exit[v_reg]; 5720d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee uses[idx] = ssa_reg; 5730d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee incoming[idx] = pred_bb->id; 5740d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee idx++; 57567bf885d62b1473c833bece1c9e0bb624e6ba391buzbee } 576a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee } 57767bf885d62b1473c833bece1c9e0bb624e6ba391buzbee 578a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee return true; 57967bf885d62b1473c833bece1c9e0bb624e6ba391buzbee} 58067bf885d62b1473c833bece1c9e0bb624e6ba391buzbee 5812ce745c06271d5223d57dbf08117b20d5b60694aBrian Carlstromvoid MIRGraph::DoDFSPreOrderSSARename(BasicBlock* block) { 5820cd7ec2dcd8d7ba30bf3ca420b40dac52849876cBrian Carlstrom if (block->visited || block->hidden) { 5830cd7ec2dcd8d7ba30bf3ca420b40dac52849876cBrian Carlstrom return; 5840cd7ec2dcd8d7ba30bf3ca420b40dac52849876cBrian Carlstrom } 585a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee block->visited = true; 586a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee 587a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee /* Process this block */ 588311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee DoSSAConversion(block); 589311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee int map_size = sizeof(int) * cu_->num_dalvik_registers; 590a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee 591a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee /* Save SSA map snapshot */ 5925d47447e1d0cd18cf91a189f7a08e65c8d43ea5aVladimir Marko ScopedArenaAllocator allocator(&cu_->arena_stack); 593862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee int* saved_ssa_map = 5945d47447e1d0cd18cf91a189f7a08e65c8d43ea5aVladimir Marko static_cast<int*>(allocator.Alloc(map_size, kArenaAllocDalvikToSSAMap)); 595311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee memcpy(saved_ssa_map, vreg_to_ssa_map_, map_size); 596a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee 5970d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee if (block->fall_through != NullBasicBlockId) { 5980d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee DoDFSPreOrderSSARename(GetBasicBlock(block->fall_through)); 599a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee /* Restore SSA map snapshot */ 600311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee memcpy(vreg_to_ssa_map_, saved_ssa_map, map_size); 601a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee } 6020d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee if (block->taken != NullBasicBlockId) { 6030d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee DoDFSPreOrderSSARename(GetBasicBlock(block->taken)); 604a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee /* Restore SSA map snapshot */ 605311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee memcpy(vreg_to_ssa_map_, saved_ssa_map, map_size); 606a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee } 6070d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee if (block->successor_block_list_type != kNotUsed) { 6080d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee GrowableArray<SuccessorBlockInfo*>::Iterator iterator(block->successor_blocks); 609a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee while (true) { 610862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee SuccessorBlockInfo *successor_block_info = iterator.Next(); 6110cd7ec2dcd8d7ba30bf3ca420b40dac52849876cBrian Carlstrom if (successor_block_info == NULL) { 6120cd7ec2dcd8d7ba30bf3ca420b40dac52849876cBrian Carlstrom break; 6130cd7ec2dcd8d7ba30bf3ca420b40dac52849876cBrian Carlstrom } 6140d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee BasicBlock* succ_bb = GetBasicBlock(successor_block_info->block); 615311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee DoDFSPreOrderSSARename(succ_bb); 616a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee /* Restore SSA map snapshot */ 617311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee memcpy(vreg_to_ssa_map_, saved_ssa_map, map_size); 618a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee } 619a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee } 620a114add0300b95eeaae7465493f39144e07324e8Bill Buzbee return; 621f0cde549bed96e16401a347a4511b59130c61e84buzbee} 622f0cde549bed96e16401a347a4511b59130c61e84buzbee 62311d1b0c31ddd710d26068da8e0e4621002205b4bElliott Hughes} // namespace art 624