blob: 3cc573b9c93950af6385fdd42d933d8306fb7fc6 [file] [log] [blame]
buzbee67bf8852011-08-17 17:51:35 -07001/*
2 * Copyright (C) 2011 The Android Open Source Project
3 *
4 * Licensed under the Apache License, Version 2.0 (the "License");
5 * you may not use this file except in compliance with the License.
6 * You may obtain a copy of the License at
7 *
8 * http://www.apache.org/licenses/LICENSE-2.0
9 *
10 * Unless required by applicable law or agreed to in writing, software
11 * distributed under the License is distributed on an "AS IS" BASIS,
12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 * See the License for the specific language governing permissions and
14 * limitations under the License.
15 */
16
Ian Rogerse77493c2014-08-20 15:08:45 -070017#include "base/bit_vector-inl.h"
buzbeeeaf09bc2012-11-15 14:51:41 -080018#include "compiler_internals.h"
Ian Rogers8d3a1172013-06-04 01:13:28 -070019#include "dataflow_iterator-inl.h"
Vladimir Markoc9360ce2014-06-05 20:09:47 +010020#include "utils/scoped_arena_containers.h"
buzbee67bf8852011-08-17 17:51:35 -070021
buzbee1fd33462013-03-25 13:40:45 -070022#define NOTVISITED (-1)
23
Elliott Hughes11d1b0c2012-01-23 16:57:47 -080024namespace art {
25
buzbeea5abf702013-04-12 14:39:29 -070026void MIRGraph::ClearAllVisitedFlags() {
buzbee56c71782013-09-05 17:13:19 -070027 AllNodesIterator iter(this);
buzbeea5abf702013-04-12 14:39:29 -070028 for (BasicBlock* bb = iter.Next(); bb != NULL; bb = iter.Next()) {
29 bb->visited = false;
30 }
31}
32
buzbee311ca162013-02-28 15:56:43 -080033BasicBlock* MIRGraph::NeedsVisit(BasicBlock* bb) {
buzbeee5f01222012-06-14 15:19:35 -070034 if (bb != NULL) {
35 if (bb->visited || bb->hidden) {
36 bb = NULL;
37 }
38 }
39 return bb;
40}
41
Brian Carlstrom2ce745c2013-07-17 17:44:30 -070042BasicBlock* MIRGraph::NextUnvisitedSuccessor(BasicBlock* bb) {
buzbee0d829482013-10-11 15:24:55 -070043 BasicBlock* res = NeedsVisit(GetBasicBlock(bb->fall_through));
buzbeee5f01222012-06-14 15:19:35 -070044 if (res == NULL) {
buzbee0d829482013-10-11 15:24:55 -070045 res = NeedsVisit(GetBasicBlock(bb->taken));
buzbeee5f01222012-06-14 15:19:35 -070046 if (res == NULL) {
buzbee0d829482013-10-11 15:24:55 -070047 if (bb->successor_block_list_type != kNotUsed) {
Vladimir Markoe39c54e2014-09-22 14:50:02 +010048 for (SuccessorBlockInfo* sbi : bb->successor_blocks) {
buzbee0d829482013-10-11 15:24:55 -070049 res = NeedsVisit(GetBasicBlock(sbi->block));
Brian Carlstrom0cd7ec22013-07-17 23:40:20 -070050 if (res != NULL) {
51 break;
52 }
buzbeee5f01222012-06-14 15:19:35 -070053 }
54 }
55 }
56 }
57 return res;
58}
59
Brian Carlstrom2ce745c2013-07-17 17:44:30 -070060void MIRGraph::MarkPreOrder(BasicBlock* block) {
buzbeee5f01222012-06-14 15:19:35 -070061 block->visited = true;
buzbeefa57c472012-11-21 12:06:18 -080062 /* Enqueue the pre_order block id */
buzbee0d829482013-10-11 15:24:55 -070063 if (block->id != NullBasicBlockId) {
Vladimir Markoe39c54e2014-09-22 14:50:02 +010064 dfs_order_.push_back(block->id);
buzbee0d829482013-10-11 15:24:55 -070065 }
buzbeee5f01222012-06-14 15:19:35 -070066}
67
Brian Carlstrom2ce745c2013-07-17 17:44:30 -070068void MIRGraph::RecordDFSOrders(BasicBlock* block) {
Vladimir Markoc9360ce2014-06-05 20:09:47 +010069 DCHECK(temp_scoped_alloc_.get() != nullptr);
70 ScopedArenaVector<BasicBlock*> succ(temp_scoped_alloc_->Adapter());
buzbee311ca162013-02-28 15:56:43 -080071 MarkPreOrder(block);
buzbeee5f01222012-06-14 15:19:35 -070072 succ.push_back(block);
73 while (!succ.empty()) {
74 BasicBlock* curr = succ.back();
buzbeefa57c472012-11-21 12:06:18 -080075 BasicBlock* next_successor = NextUnvisitedSuccessor(curr);
76 if (next_successor != NULL) {
buzbee311ca162013-02-28 15:56:43 -080077 MarkPreOrder(next_successor);
buzbeefa57c472012-11-21 12:06:18 -080078 succ.push_back(next_successor);
buzbeee5f01222012-06-14 15:19:35 -070079 continue;
80 }
Vladimir Markoe39c54e2014-09-22 14:50:02 +010081 curr->dfs_id = dfs_post_order_.size();
buzbee0d829482013-10-11 15:24:55 -070082 if (curr->id != NullBasicBlockId) {
Vladimir Markoe39c54e2014-09-22 14:50:02 +010083 dfs_post_order_.push_back(curr->id);
buzbee0d829482013-10-11 15:24:55 -070084 }
buzbeee5f01222012-06-14 15:19:35 -070085 succ.pop_back();
86 }
87}
88
buzbee5b537102012-01-17 17:33:47 -080089/* Sort the blocks by the Depth-First-Search */
Brian Carlstrom2ce745c2013-07-17 17:44:30 -070090void MIRGraph::ComputeDFSOrders() {
Vladimir Markoe39c54e2014-09-22 14:50:02 +010091 /* Clear the DFS pre-order and post-order lists. */
92 dfs_order_.clear();
93 dfs_order_.reserve(GetNumBlocks());
94 dfs_post_order_.clear();
95 dfs_post_order_.reserve(GetNumBlocks());
buzbee5b537102012-01-17 17:33:47 -080096
buzbeee5f01222012-06-14 15:19:35 -070097 // Reset visited flags from all nodes
buzbeea5abf702013-04-12 14:39:29 -070098 ClearAllVisitedFlags();
99
buzbeee5f01222012-06-14 15:19:35 -0700100 // Record dfs orders
buzbee311ca162013-02-28 15:56:43 -0800101 RecordDFSOrders(GetEntryBlock());
buzbeee5f01222012-06-14 15:19:35 -0700102
Vladimir Markoe39c54e2014-09-22 14:50:02 +0100103 num_reachable_blocks_ = dfs_order_.size();
Andreas Gampe44395962014-06-13 13:44:40 -0700104
105 if (num_reachable_blocks_ != num_blocks_) {
106 // Hide all unreachable blocks.
107 AllNodesIterator iter(this);
108 for (BasicBlock* bb = iter.Next(); bb != NULL; bb = iter.Next()) {
109 if (!bb->visited) {
110 bb->Hide(cu_);
111 }
112 }
113 }
buzbee67bf8852011-08-17 17:51:35 -0700114}
115
116/*
117 * Mark block bit on the per-Dalvik register vector to denote that Dalvik
118 * register idx is defined in BasicBlock bb.
119 */
Brian Carlstrom2ce745c2013-07-17 17:44:30 -0700120bool MIRGraph::FillDefBlockMatrix(BasicBlock* bb) {
Brian Carlstrom0cd7ec22013-07-17 23:40:20 -0700121 if (bb->data_flow_info == NULL) {
122 return false;
123 }
buzbee67bf8852011-08-17 17:51:35 -0700124
Vladimir Markoa5b8fde2014-05-23 15:16:44 +0100125 for (uint32_t idx : bb->data_flow_info->def_v->Indexes()) {
Bill Buzbeea114add2012-05-03 15:00:40 -0700126 /* Block bb defines register idx */
buzbee862a7602013-04-05 10:58:54 -0700127 def_block_matrix_[idx]->SetBit(bb->id);
Bill Buzbeea114add2012-05-03 15:00:40 -0700128 }
129 return true;
buzbee67bf8852011-08-17 17:51:35 -0700130}
131
Brian Carlstrom2ce745c2013-07-17 17:44:30 -0700132void MIRGraph::ComputeDefBlockMatrix() {
Razvan A Lupusoru8d0d03e2014-06-06 17:04:52 -0700133 int num_registers = GetNumOfCodeAndTempVRs();
134 /* Allocate num_registers bit vector pointers */
buzbee311ca162013-02-28 15:56:43 -0800135 def_block_matrix_ = static_cast<ArenaBitVector**>
Mathieu Chartierf6c4b3b2013-08-24 16:11:37 -0700136 (arena_->Alloc(sizeof(ArenaBitVector *) * num_registers,
Vladimir Marko83cc7ae2014-02-12 18:02:05 +0000137 kArenaAllocDFInfo));
Bill Buzbeea114add2012-05-03 15:00:40 -0700138 int i;
buzbee67bf8852011-08-17 17:51:35 -0700139
buzbeefa57c472012-11-21 12:06:18 -0800140 /* Initialize num_register vectors with num_blocks bits each */
141 for (i = 0; i < num_registers; i++) {
buzbee862a7602013-04-05 10:58:54 -0700142 def_block_matrix_[i] =
143 new (arena_) ArenaBitVector(arena_, GetNumBlocks(), false, kBitMapBMatrix);
Bill Buzbeea114add2012-05-03 15:00:40 -0700144 }
Razvan A Lupusoru8d0d03e2014-06-06 17:04:52 -0700145
buzbee56c71782013-09-05 17:13:19 -0700146 AllNodesIterator iter(this);
buzbee311ca162013-02-28 15:56:43 -0800147 for (BasicBlock* bb = iter.Next(); bb != NULL; bb = iter.Next()) {
148 FindLocalLiveIn(bb);
149 }
buzbee56c71782013-09-05 17:13:19 -0700150 AllNodesIterator iter2(this);
buzbee311ca162013-02-28 15:56:43 -0800151 for (BasicBlock* bb = iter2.Next(); bb != NULL; bb = iter2.Next()) {
152 FillDefBlockMatrix(bb);
153 }
buzbee67bf8852011-08-17 17:51:35 -0700154
Bill Buzbeea114add2012-05-03 15:00:40 -0700155 /*
156 * Also set the incoming parameters as defs in the entry block.
157 * Only need to handle the parameters for the outer method.
158 */
Razvan A Lupusoru8d0d03e2014-06-06 17:04:52 -0700159 int num_regs = GetNumOfCodeVRs();
160 int in_reg = GetFirstInVR();
buzbeefa57c472012-11-21 12:06:18 -0800161 for (; in_reg < num_regs; in_reg++) {
buzbee862a7602013-04-05 10:58:54 -0700162 def_block_matrix_[in_reg]->SetBit(GetEntryBlock()->id);
Bill Buzbeea114add2012-05-03 15:00:40 -0700163 }
buzbee67bf8852011-08-17 17:51:35 -0700164}
165
buzbeea5abf702013-04-12 14:39:29 -0700166void MIRGraph::ComputeDomPostOrderTraversal(BasicBlock* bb) {
Vladimir Markoe39c54e2014-09-22 14:50:02 +0100167 // Clear the dominator post-order list.
168 dom_post_order_traversal_.clear();
169 dom_post_order_traversal_.reserve(num_reachable_blocks_);
170
buzbeea5abf702013-04-12 14:39:29 -0700171 ClearAllVisitedFlags();
Vladimir Markoc9360ce2014-06-05 20:09:47 +0100172 DCHECK(temp_scoped_alloc_.get() != nullptr);
173 ScopedArenaVector<std::pair<BasicBlock*, ArenaBitVector::IndexIterator>> work_stack(
174 temp_scoped_alloc_->Adapter());
buzbeea5abf702013-04-12 14:39:29 -0700175 bb->visited = true;
Vladimir Markoa5b8fde2014-05-23 15:16:44 +0100176 work_stack.push_back(std::make_pair(bb, bb->i_dominated->Indexes().begin()));
buzbeea5abf702013-04-12 14:39:29 -0700177 while (!work_stack.empty()) {
Vladimir Markoa5b8fde2014-05-23 15:16:44 +0100178 std::pair<BasicBlock*, ArenaBitVector::IndexIterator>* curr = &work_stack.back();
179 BasicBlock* curr_bb = curr->first;
180 ArenaBitVector::IndexIterator* curr_idom_iter = &curr->second;
181 while (!curr_idom_iter->Done() && (NeedsVisit(GetBasicBlock(**curr_idom_iter)) == nullptr)) {
182 ++*curr_idom_iter;
buzbeea5abf702013-04-12 14:39:29 -0700183 }
Vladimir Markoa5b8fde2014-05-23 15:16:44 +0100184 // NOTE: work_stack.push_back()/pop_back() invalidate curr and curr_idom_iter.
185 if (!curr_idom_iter->Done()) {
186 BasicBlock* new_bb = GetBasicBlock(**curr_idom_iter);
187 ++*curr_idom_iter;
buzbeea5abf702013-04-12 14:39:29 -0700188 new_bb->visited = true;
Vladimir Markoa5b8fde2014-05-23 15:16:44 +0100189 work_stack.push_back(std::make_pair(new_bb, new_bb->i_dominated->Indexes().begin()));
buzbeea5abf702013-04-12 14:39:29 -0700190 } else {
191 // no successor/next
buzbee0d829482013-10-11 15:24:55 -0700192 if (curr_bb->id != NullBasicBlockId) {
Vladimir Markoe39c54e2014-09-22 14:50:02 +0100193 dom_post_order_traversal_.push_back(curr_bb->id);
buzbee0d829482013-10-11 15:24:55 -0700194 }
buzbeea5abf702013-04-12 14:39:29 -0700195 work_stack.pop_back();
buzbee67bf8852011-08-17 17:51:35 -0700196
buzbeea5abf702013-04-12 14:39:29 -0700197 /* hacky loop detection */
buzbee0d829482013-10-11 15:24:55 -0700198 if ((curr_bb->taken != NullBasicBlockId) && curr_bb->dominators->IsBitSet(curr_bb->taken)) {
Bill Buzbee0b1191c2013-10-28 22:11:59 +0000199 curr_bb->nesting_depth++;
buzbeea5abf702013-04-12 14:39:29 -0700200 attributes_ |= METHOD_HAS_LOOP;
201 }
202 }
Bill Buzbeea114add2012-05-03 15:00:40 -0700203 }
buzbee67bf8852011-08-17 17:51:35 -0700204}
205
buzbee311ca162013-02-28 15:56:43 -0800206void MIRGraph::CheckForDominanceFrontier(BasicBlock* dom_bb,
Brian Carlstrom2ce745c2013-07-17 17:44:30 -0700207 const BasicBlock* succ_bb) {
Bill Buzbeea114add2012-05-03 15:00:40 -0700208 /*
209 * TODO - evaluate whether phi will ever need to be inserted into exit
210 * blocks.
211 */
buzbee0d829482013-10-11 15:24:55 -0700212 if (succ_bb->i_dom != dom_bb->id &&
buzbeefa57c472012-11-21 12:06:18 -0800213 succ_bb->block_type == kDalvikByteCode &&
214 succ_bb->hidden == false) {
buzbee862a7602013-04-05 10:58:54 -0700215 dom_bb->dom_frontier->SetBit(succ_bb->id);
Bill Buzbeea114add2012-05-03 15:00:40 -0700216 }
buzbee67bf8852011-08-17 17:51:35 -0700217}
218
219/* Worker function to compute the dominance frontier */
Brian Carlstrom2ce745c2013-07-17 17:44:30 -0700220bool MIRGraph::ComputeDominanceFrontier(BasicBlock* bb) {
Bill Buzbeea114add2012-05-03 15:00:40 -0700221 /* Calculate DF_local */
buzbee0d829482013-10-11 15:24:55 -0700222 if (bb->taken != NullBasicBlockId) {
223 CheckForDominanceFrontier(bb, GetBasicBlock(bb->taken));
Bill Buzbeea114add2012-05-03 15:00:40 -0700224 }
buzbee0d829482013-10-11 15:24:55 -0700225 if (bb->fall_through != NullBasicBlockId) {
226 CheckForDominanceFrontier(bb, GetBasicBlock(bb->fall_through));
Bill Buzbeea114add2012-05-03 15:00:40 -0700227 }
buzbee0d829482013-10-11 15:24:55 -0700228 if (bb->successor_block_list_type != kNotUsed) {
Vladimir Markoe39c54e2014-09-22 14:50:02 +0100229 for (SuccessorBlockInfo* successor_block_info : bb->successor_blocks) {
230 BasicBlock* succ_bb = GetBasicBlock(successor_block_info->block);
231 CheckForDominanceFrontier(bb, succ_bb);
232 }
Bill Buzbeea114add2012-05-03 15:00:40 -0700233 }
buzbee67bf8852011-08-17 17:51:35 -0700234
Bill Buzbeea114add2012-05-03 15:00:40 -0700235 /* Calculate DF_up */
Vladimir Markoa5b8fde2014-05-23 15:16:44 +0100236 for (uint32_t dominated_idx : bb->i_dominated->Indexes()) {
Jean Christophe Beyler2469e602014-05-06 20:36:55 -0700237 BasicBlock* dominated_bb = GetBasicBlock(dominated_idx);
Vladimir Markoa5b8fde2014-05-23 15:16:44 +0100238 for (uint32_t df_up_block_idx : dominated_bb->dom_frontier->Indexes()) {
Jean Christophe Beyler2469e602014-05-06 20:36:55 -0700239 BasicBlock* df_up_block = GetBasicBlock(df_up_block_idx);
buzbee311ca162013-02-28 15:56:43 -0800240 CheckForDominanceFrontier(bb, df_up_block);
buzbee67bf8852011-08-17 17:51:35 -0700241 }
Bill Buzbeea114add2012-05-03 15:00:40 -0700242 }
buzbee67bf8852011-08-17 17:51:35 -0700243
Bill Buzbeea114add2012-05-03 15:00:40 -0700244 return true;
buzbee67bf8852011-08-17 17:51:35 -0700245}
246
247/* Worker function for initializing domination-related data structures */
Brian Carlstrom2ce745c2013-07-17 17:44:30 -0700248void MIRGraph::InitializeDominationInfo(BasicBlock* bb) {
buzbee311ca162013-02-28 15:56:43 -0800249 int num_total_blocks = GetBasicBlockListCount();
buzbee67bf8852011-08-17 17:51:35 -0700250
Brian Carlstromdf629502013-07-17 22:39:56 -0700251 if (bb->dominators == NULL) {
buzbee862a7602013-04-05 10:58:54 -0700252 bb->dominators = new (arena_) ArenaBitVector(arena_, num_total_blocks,
Jean Christophe Beyler007a0652014-09-05 16:06:42 -0700253 true /* expandable */, kBitMapDominators);
buzbee862a7602013-04-05 10:58:54 -0700254 bb->i_dominated = new (arena_) ArenaBitVector(arena_, num_total_blocks,
Jean Christophe Beyler007a0652014-09-05 16:06:42 -0700255 true /* expandable */, kBitMapIDominated);
buzbee862a7602013-04-05 10:58:54 -0700256 bb->dom_frontier = new (arena_) ArenaBitVector(arena_, num_total_blocks,
Jean Christophe Beyler007a0652014-09-05 16:06:42 -0700257 true /* expandable */, kBitMapDomFrontier);
Bill Buzbeea114add2012-05-03 15:00:40 -0700258 } else {
buzbee862a7602013-04-05 10:58:54 -0700259 bb->dominators->ClearAllBits();
260 bb->i_dominated->ClearAllBits();
261 bb->dom_frontier->ClearAllBits();
Bill Buzbeea114add2012-05-03 15:00:40 -0700262 }
263 /* Set all bits in the dominator vector */
buzbee862a7602013-04-05 10:58:54 -0700264 bb->dominators->SetInitialBits(num_total_blocks);
buzbee67bf8852011-08-17 17:51:35 -0700265
buzbee862a7602013-04-05 10:58:54 -0700266 return;
buzbee67bf8852011-08-17 17:51:35 -0700267}
268
buzbee5b537102012-01-17 17:33:47 -0800269/*
buzbeefa57c472012-11-21 12:06:18 -0800270 * Walk through the ordered i_dom list until we reach common parent.
271 * Given the ordering of i_dom_list, this common parent represents the
buzbee5b537102012-01-17 17:33:47 -0800272 * last element of the intersection of block1 and block2 dominators.
273 */
Brian Carlstrom2ce745c2013-07-17 17:44:30 -0700274int MIRGraph::FindCommonParent(int block1, int block2) {
Bill Buzbeea114add2012-05-03 15:00:40 -0700275 while (block1 != block2) {
276 while (block1 < block2) {
buzbee311ca162013-02-28 15:56:43 -0800277 block1 = i_dom_list_[block1];
Bill Buzbeea114add2012-05-03 15:00:40 -0700278 DCHECK_NE(block1, NOTVISITED);
buzbee5b537102012-01-17 17:33:47 -0800279 }
Bill Buzbeea114add2012-05-03 15:00:40 -0700280 while (block2 < block1) {
buzbee311ca162013-02-28 15:56:43 -0800281 block2 = i_dom_list_[block2];
Bill Buzbeea114add2012-05-03 15:00:40 -0700282 DCHECK_NE(block2, NOTVISITED);
283 }
284 }
285 return block1;
buzbee5b537102012-01-17 17:33:47 -0800286}
287
288/* Worker function to compute each block's immediate dominator */
Brian Carlstrom2ce745c2013-07-17 17:44:30 -0700289bool MIRGraph::ComputeblockIDom(BasicBlock* bb) {
Bill Buzbeea114add2012-05-03 15:00:40 -0700290 /* Special-case entry block */
buzbee0d829482013-10-11 15:24:55 -0700291 if ((bb->id == NullBasicBlockId) || (bb == GetEntryBlock())) {
buzbee5b537102012-01-17 17:33:47 -0800292 return false;
Bill Buzbeea114add2012-05-03 15:00:40 -0700293 }
294
295 /* Iterate through the predecessors */
Vladimir Markoe39c54e2014-09-22 14:50:02 +0100296 auto it = bb->predecessors.begin(), end = bb->predecessors.end();
Bill Buzbeea114add2012-05-03 15:00:40 -0700297
298 /* Find the first processed predecessor */
buzbee862a7602013-04-05 10:58:54 -0700299 int idom = -1;
Vladimir Markoe39c54e2014-09-22 14:50:02 +0100300 for ( ; ; ++it) {
301 CHECK(it != end);
302 BasicBlock* pred_bb = GetBasicBlock(*it);
303 DCHECK(pred_bb != nullptr);
buzbee311ca162013-02-28 15:56:43 -0800304 if (i_dom_list_[pred_bb->dfs_id] != NOTVISITED) {
buzbeefa57c472012-11-21 12:06:18 -0800305 idom = pred_bb->dfs_id;
Bill Buzbeea114add2012-05-03 15:00:40 -0700306 break;
307 }
308 }
309
310 /* Scan the rest of the predecessors */
Vladimir Markoe39c54e2014-09-22 14:50:02 +0100311 for ( ; it != end; ++it) {
312 BasicBlock* pred_bb = GetBasicBlock(*it);
313 DCHECK(pred_bb != nullptr);
buzbee311ca162013-02-28 15:56:43 -0800314 if (i_dom_list_[pred_bb->dfs_id] == NOTVISITED) {
Bill Buzbeea114add2012-05-03 15:00:40 -0700315 continue;
316 } else {
buzbee311ca162013-02-28 15:56:43 -0800317 idom = FindCommonParent(pred_bb->dfs_id, idom);
Bill Buzbeea114add2012-05-03 15:00:40 -0700318 }
319 }
320
321 DCHECK_NE(idom, NOTVISITED);
322
323 /* Did something change? */
buzbee311ca162013-02-28 15:56:43 -0800324 if (i_dom_list_[bb->dfs_id] != idom) {
325 i_dom_list_[bb->dfs_id] = idom;
Bill Buzbeea114add2012-05-03 15:00:40 -0700326 return true;
327 }
328 return false;
buzbee5b537102012-01-17 17:33:47 -0800329}
330
331/* Worker function to compute each block's domintors */
Brian Carlstrom2ce745c2013-07-17 17:44:30 -0700332bool MIRGraph::ComputeBlockDominators(BasicBlock* bb) {
buzbee311ca162013-02-28 15:56:43 -0800333 if (bb == GetEntryBlock()) {
buzbee862a7602013-04-05 10:58:54 -0700334 bb->dominators->ClearAllBits();
Bill Buzbeea114add2012-05-03 15:00:40 -0700335 } else {
buzbee0d829482013-10-11 15:24:55 -0700336 bb->dominators->Copy(GetBasicBlock(bb->i_dom)->dominators);
Bill Buzbeea114add2012-05-03 15:00:40 -0700337 }
buzbee862a7602013-04-05 10:58:54 -0700338 bb->dominators->SetBit(bb->id);
Bill Buzbeea114add2012-05-03 15:00:40 -0700339 return false;
buzbee5b537102012-01-17 17:33:47 -0800340}
341
Brian Carlstrom2ce745c2013-07-17 17:44:30 -0700342bool MIRGraph::SetDominators(BasicBlock* bb) {
buzbee311ca162013-02-28 15:56:43 -0800343 if (bb != GetEntryBlock()) {
344 int idom_dfs_idx = i_dom_list_[bb->dfs_id];
buzbeefa57c472012-11-21 12:06:18 -0800345 DCHECK_NE(idom_dfs_idx, NOTVISITED);
Vladimir Markoe39c54e2014-09-22 14:50:02 +0100346 int i_dom_idx = dfs_post_order_[idom_dfs_idx];
buzbee311ca162013-02-28 15:56:43 -0800347 BasicBlock* i_dom = GetBasicBlock(i_dom_idx);
buzbee0d829482013-10-11 15:24:55 -0700348 bb->i_dom = i_dom->id;
buzbeefa57c472012-11-21 12:06:18 -0800349 /* Add bb to the i_dominated set of the immediate dominator block */
buzbee862a7602013-04-05 10:58:54 -0700350 i_dom->i_dominated->SetBit(bb->id);
Bill Buzbeea114add2012-05-03 15:00:40 -0700351 }
352 return false;
buzbee5b537102012-01-17 17:33:47 -0800353}
354
buzbee67bf8852011-08-17 17:51:35 -0700355/* Compute dominators, immediate dominator, and dominance fronter */
Brian Carlstrom2ce745c2013-07-17 17:44:30 -0700356void MIRGraph::ComputeDominators() {
buzbee311ca162013-02-28 15:56:43 -0800357 int num_reachable_blocks = num_reachable_blocks_;
buzbee67bf8852011-08-17 17:51:35 -0700358
Bill Buzbeea114add2012-05-03 15:00:40 -0700359 /* Initialize domination-related data structures */
buzbee56c71782013-09-05 17:13:19 -0700360 PreOrderDfsIterator iter(this);
buzbee311ca162013-02-28 15:56:43 -0800361 for (BasicBlock* bb = iter.Next(); bb != NULL; bb = iter.Next()) {
362 InitializeDominationInfo(bb);
363 }
buzbee67bf8852011-08-17 17:51:35 -0700364
Jean Christophe Beyler4896d7b2014-05-01 15:36:22 -0700365 /* Initialize & Clear i_dom_list */
366 if (max_num_reachable_blocks_ < num_reachable_blocks_) {
Mathieu Chartierf6c4b3b2013-08-24 16:11:37 -0700367 i_dom_list_ = static_cast<int*>(arena_->Alloc(sizeof(int) * num_reachable_blocks,
Vladimir Marko83cc7ae2014-02-12 18:02:05 +0000368 kArenaAllocDFInfo));
Bill Buzbeea114add2012-05-03 15:00:40 -0700369 }
buzbeefa57c472012-11-21 12:06:18 -0800370 for (int i = 0; i < num_reachable_blocks; i++) {
buzbee311ca162013-02-28 15:56:43 -0800371 i_dom_list_[i] = NOTVISITED;
Bill Buzbeea114add2012-05-03 15:00:40 -0700372 }
buzbee5b537102012-01-17 17:33:47 -0800373
buzbeefa57c472012-11-21 12:06:18 -0800374 /* For post-order, last block is entry block. Set its i_dom to istelf */
buzbee311ca162013-02-28 15:56:43 -0800375 DCHECK_EQ(GetEntryBlock()->dfs_id, num_reachable_blocks-1);
376 i_dom_list_[GetEntryBlock()->dfs_id] = GetEntryBlock()->dfs_id;
buzbee5b537102012-01-17 17:33:47 -0800377
Bill Buzbeea114add2012-05-03 15:00:40 -0700378 /* Compute the immediate dominators */
buzbee56c71782013-09-05 17:13:19 -0700379 RepeatingReversePostOrderDfsIterator iter2(this);
buzbee311ca162013-02-28 15:56:43 -0800380 bool change = false;
381 for (BasicBlock* bb = iter2.Next(false); bb != NULL; bb = iter2.Next(change)) {
382 change = ComputeblockIDom(bb);
383 }
Bill Buzbeea114add2012-05-03 15:00:40 -0700384
385 /* Set the dominator for the root node */
buzbee862a7602013-04-05 10:58:54 -0700386 GetEntryBlock()->dominators->ClearAllBits();
387 GetEntryBlock()->dominators->SetBit(GetEntryBlock()->id);
Bill Buzbeea114add2012-05-03 15:00:40 -0700388
buzbee0d829482013-10-11 15:24:55 -0700389 GetEntryBlock()->i_dom = 0;
Bill Buzbeea114add2012-05-03 15:00:40 -0700390
buzbee56c71782013-09-05 17:13:19 -0700391 PreOrderDfsIterator iter3(this);
buzbee311ca162013-02-28 15:56:43 -0800392 for (BasicBlock* bb = iter3.Next(); bb != NULL; bb = iter3.Next()) {
393 SetDominators(bb);
Bill Buzbeea114add2012-05-03 15:00:40 -0700394 }
buzbee67bf8852011-08-17 17:51:35 -0700395
buzbee56c71782013-09-05 17:13:19 -0700396 ReversePostOrderDfsIterator iter4(this);
buzbee311ca162013-02-28 15:56:43 -0800397 for (BasicBlock* bb = iter4.Next(); bb != NULL; bb = iter4.Next()) {
398 ComputeBlockDominators(bb);
399 }
buzbee5b537102012-01-17 17:33:47 -0800400
buzbeea5abf702013-04-12 14:39:29 -0700401 // Compute the dominance frontier for each block.
buzbee311ca162013-02-28 15:56:43 -0800402 ComputeDomPostOrderTraversal(GetEntryBlock());
buzbee56c71782013-09-05 17:13:19 -0700403 PostOrderDOMIterator iter5(this);
buzbee311ca162013-02-28 15:56:43 -0800404 for (BasicBlock* bb = iter5.Next(); bb != NULL; bb = iter5.Next()) {
405 ComputeDominanceFrontier(bb);
406 }
buzbee67bf8852011-08-17 17:51:35 -0700407}
408
409/*
410 * Perform dest U= src1 ^ ~src2
411 * This is probably not general enough to be placed in BitVector.[ch].
412 */
buzbee311ca162013-02-28 15:56:43 -0800413void MIRGraph::ComputeSuccLineIn(ArenaBitVector* dest, const ArenaBitVector* src1,
Brian Carlstrom2ce745c2013-07-17 17:44:30 -0700414 const ArenaBitVector* src2) {
buzbee862a7602013-04-05 10:58:54 -0700415 if (dest->GetStorageSize() != src1->GetStorageSize() ||
416 dest->GetStorageSize() != src2->GetStorageSize() ||
417 dest->IsExpandable() != src1->IsExpandable() ||
418 dest->IsExpandable() != src2->IsExpandable()) {
Bill Buzbeea114add2012-05-03 15:00:40 -0700419 LOG(FATAL) << "Incompatible set properties";
420 }
buzbee67bf8852011-08-17 17:51:35 -0700421
Bill Buzbeea114add2012-05-03 15:00:40 -0700422 unsigned int idx;
buzbee862a7602013-04-05 10:58:54 -0700423 for (idx = 0; idx < dest->GetStorageSize(); idx++) {
424 dest->GetRawStorage()[idx] |= src1->GetRawStorageWord(idx) & ~(src2->GetRawStorageWord(idx));
Bill Buzbeea114add2012-05-03 15:00:40 -0700425 }
buzbee67bf8852011-08-17 17:51:35 -0700426}
427
428/*
429 * Iterate through all successor blocks and propagate up the live-in sets.
430 * The calculated result is used for phi-node pruning - where we only need to
431 * insert a phi node if the variable is live-in to the block.
432 */
Brian Carlstrom2ce745c2013-07-17 17:44:30 -0700433bool MIRGraph::ComputeBlockLiveIns(BasicBlock* bb) {
Razvan A Lupusoru8d0d03e2014-06-06 17:04:52 -0700434 DCHECK_EQ(temp_bit_vector_size_, cu_->mir_graph.get()->GetNumOfCodeAndTempVRs());
Vladimir Markoa5b8fde2014-05-23 15:16:44 +0100435 ArenaBitVector* temp_dalvik_register_v = temp_bit_vector_;
buzbee67bf8852011-08-17 17:51:35 -0700436
Brian Carlstrom0cd7ec22013-07-17 23:40:20 -0700437 if (bb->data_flow_info == NULL) {
438 return false;
439 }
buzbee862a7602013-04-05 10:58:54 -0700440 temp_dalvik_register_v->Copy(bb->data_flow_info->live_in_v);
buzbee0d829482013-10-11 15:24:55 -0700441 BasicBlock* bb_taken = GetBasicBlock(bb->taken);
442 BasicBlock* bb_fall_through = GetBasicBlock(bb->fall_through);
443 if (bb_taken && bb_taken->data_flow_info)
444 ComputeSuccLineIn(temp_dalvik_register_v, bb_taken->data_flow_info->live_in_v,
buzbeefa57c472012-11-21 12:06:18 -0800445 bb->data_flow_info->def_v);
buzbee0d829482013-10-11 15:24:55 -0700446 if (bb_fall_through && bb_fall_through->data_flow_info)
447 ComputeSuccLineIn(temp_dalvik_register_v, bb_fall_through->data_flow_info->live_in_v,
buzbeefa57c472012-11-21 12:06:18 -0800448 bb->data_flow_info->def_v);
buzbee0d829482013-10-11 15:24:55 -0700449 if (bb->successor_block_list_type != kNotUsed) {
Vladimir Markoe39c54e2014-09-22 14:50:02 +0100450 for (SuccessorBlockInfo* successor_block_info : bb->successor_blocks) {
buzbee0d829482013-10-11 15:24:55 -0700451 BasicBlock* succ_bb = GetBasicBlock(successor_block_info->block);
buzbeefa57c472012-11-21 12:06:18 -0800452 if (succ_bb->data_flow_info) {
buzbee311ca162013-02-28 15:56:43 -0800453 ComputeSuccLineIn(temp_dalvik_register_v, succ_bb->data_flow_info->live_in_v,
buzbeefa57c472012-11-21 12:06:18 -0800454 bb->data_flow_info->def_v);
Bill Buzbeea114add2012-05-03 15:00:40 -0700455 }
buzbee67bf8852011-08-17 17:51:35 -0700456 }
Bill Buzbeea114add2012-05-03 15:00:40 -0700457 }
buzbee862a7602013-04-05 10:58:54 -0700458 if (!temp_dalvik_register_v->Equal(bb->data_flow_info->live_in_v)) {
459 bb->data_flow_info->live_in_v->Copy(temp_dalvik_register_v);
Bill Buzbeea114add2012-05-03 15:00:40 -0700460 return true;
461 }
462 return false;
buzbee67bf8852011-08-17 17:51:35 -0700463}
464
465/* Insert phi nodes to for each variable to the dominance frontiers */
Brian Carlstrom2ce745c2013-07-17 17:44:30 -0700466void MIRGraph::InsertPhiNodes() {
buzbeefa57c472012-11-21 12:06:18 -0800467 int dalvik_reg;
Vladimir Markoa5b8fde2014-05-23 15:16:44 +0100468 ArenaBitVector* phi_blocks = new (temp_scoped_alloc_.get()) ArenaBitVector(
469 temp_scoped_alloc_.get(), GetNumBlocks(), false, kBitMapPhi);
470 ArenaBitVector* input_blocks = new (temp_scoped_alloc_.get()) ArenaBitVector(
471 temp_scoped_alloc_.get(), GetNumBlocks(), false, kBitMapInputBlocks);
buzbee67bf8852011-08-17 17:51:35 -0700472
buzbee56c71782013-09-05 17:13:19 -0700473 RepeatingPostOrderDfsIterator iter(this);
buzbee311ca162013-02-28 15:56:43 -0800474 bool change = false;
475 for (BasicBlock* bb = iter.Next(false); bb != NULL; bb = iter.Next(change)) {
476 change = ComputeBlockLiveIns(bb);
477 }
buzbee67bf8852011-08-17 17:51:35 -0700478
Bill Buzbeea114add2012-05-03 15:00:40 -0700479 /* Iterate through each Dalvik register */
Razvan A Lupusoru8d0d03e2014-06-06 17:04:52 -0700480 for (dalvik_reg = GetNumOfCodeAndTempVRs() - 1; dalvik_reg >= 0; dalvik_reg--) {
buzbee862a7602013-04-05 10:58:54 -0700481 input_blocks->Copy(def_block_matrix_[dalvik_reg]);
482 phi_blocks->ClearAllBits();
Bill Buzbeea114add2012-05-03 15:00:40 -0700483 do {
Vladimir Markoa5b8fde2014-05-23 15:16:44 +0100484 // TUNING: When we repeat this, we could skip indexes from the previous pass.
485 for (uint32_t idx : input_blocks->Indexes()) {
Brian Carlstrom0cd7ec22013-07-17 23:40:20 -0700486 BasicBlock* def_bb = GetBasicBlock(idx);
Vladimir Markoa5b8fde2014-05-23 15:16:44 +0100487 if (def_bb->dom_frontier != nullptr) {
488 phi_blocks->Union(def_bb->dom_frontier);
Brian Carlstrom0cd7ec22013-07-17 23:40:20 -0700489 }
490 }
Vladimir Markoa5b8fde2014-05-23 15:16:44 +0100491 } while (input_blocks->Union(phi_blocks));
Bill Buzbeea114add2012-05-03 15:00:40 -0700492
493 /*
buzbeefa57c472012-11-21 12:06:18 -0800494 * Insert a phi node for dalvik_reg in the phi_blocks if the Dalvik
Bill Buzbeea114add2012-05-03 15:00:40 -0700495 * register is in the live-in set.
496 */
Vladimir Markoa5b8fde2014-05-23 15:16:44 +0100497 for (uint32_t idx : phi_blocks->Indexes()) {
buzbee311ca162013-02-28 15:56:43 -0800498 BasicBlock* phi_bb = GetBasicBlock(idx);
Bill Buzbeea114add2012-05-03 15:00:40 -0700499 /* Variable will be clobbered before being used - no need for phi */
Brian Carlstrom0cd7ec22013-07-17 23:40:20 -0700500 if (!phi_bb->data_flow_info->live_in_v->IsBitSet(dalvik_reg)) {
501 continue;
502 }
Jean Christophe Beyler3aa57732014-04-17 12:47:24 -0700503 MIR *phi = NewMIR();
buzbeecbd6d442012-11-17 14:11:25 -0800504 phi->dalvikInsn.opcode = static_cast<Instruction::Code>(kMirOpPhi);
buzbeefa57c472012-11-21 12:06:18 -0800505 phi->dalvikInsn.vA = dalvik_reg;
506 phi->offset = phi_bb->start_offset;
Brian Carlstrom7934ac22013-07-26 10:54:15 -0700507 phi->m_unit_index = 0; // Arbitrarily assign all Phi nodes to outermost method.
Jean Christophe Beylercdacac42014-03-13 14:54:59 -0700508 phi_bb->PrependMIR(phi);
buzbee67bf8852011-08-17 17:51:35 -0700509 }
Bill Buzbeea114add2012-05-03 15:00:40 -0700510 }
buzbee67bf8852011-08-17 17:51:35 -0700511}
512
513/*
514 * Worker function to insert phi-operands with latest SSA names from
515 * predecessor blocks
516 */
Brian Carlstrom2ce745c2013-07-17 17:44:30 -0700517bool MIRGraph::InsertPhiNodeOperands(BasicBlock* bb) {
Bill Buzbeea114add2012-05-03 15:00:40 -0700518 /* Phi nodes are at the beginning of each block */
buzbee0d829482013-10-11 15:24:55 -0700519 for (MIR* mir = bb->first_mir_insn; mir != NULL; mir = mir->next) {
buzbeecbd6d442012-11-17 14:11:25 -0800520 if (mir->dalvikInsn.opcode != static_cast<Instruction::Code>(kMirOpPhi))
Bill Buzbeea114add2012-05-03 15:00:40 -0700521 return true;
buzbeefa57c472012-11-21 12:06:18 -0800522 int ssa_reg = mir->ssa_rep->defs[0];
523 DCHECK_GE(ssa_reg, 0); // Shouldn't see compiler temps here
buzbee311ca162013-02-28 15:56:43 -0800524 int v_reg = SRegToVReg(ssa_reg);
buzbee67bf8852011-08-17 17:51:35 -0700525
Bill Buzbeea114add2012-05-03 15:00:40 -0700526 /* Iterate through the predecessors */
Vladimir Markoe39c54e2014-09-22 14:50:02 +0100527 size_t num_uses = bb->predecessors.size();
Jean Christophe Beyler4896d7b2014-05-01 15:36:22 -0700528 AllocateSSAUseData(mir, num_uses);
529 int* uses = mir->ssa_rep->uses;
buzbee0d829482013-10-11 15:24:55 -0700530 BasicBlockId* incoming =
531 static_cast<BasicBlockId*>(arena_->Alloc(sizeof(BasicBlockId) * num_uses,
Vladimir Marko83cc7ae2014-02-12 18:02:05 +0000532 kArenaAllocDFInfo));
buzbee0d829482013-10-11 15:24:55 -0700533 mir->meta.phi_incoming = incoming;
534 int idx = 0;
Vladimir Markoe39c54e2014-09-22 14:50:02 +0100535 for (BasicBlockId pred_id : bb->predecessors) {
536 BasicBlock* pred_bb = GetBasicBlock(pred_id);
537 DCHECK(pred_bb != nullptr);
Jean Christophe Beyler4896d7b2014-05-01 15:36:22 -0700538 int ssa_reg = pred_bb->data_flow_info->vreg_to_ssa_map_exit[v_reg];
buzbee0d829482013-10-11 15:24:55 -0700539 uses[idx] = ssa_reg;
Vladimir Markoe39c54e2014-09-22 14:50:02 +0100540 incoming[idx] = pred_id;
buzbee0d829482013-10-11 15:24:55 -0700541 idx++;
Bill Buzbeea114add2012-05-03 15:00:40 -0700542 }
543 }
544
545 return true;
buzbee67bf8852011-08-17 17:51:35 -0700546}
547
Brian Carlstrom2ce745c2013-07-17 17:44:30 -0700548void MIRGraph::DoDFSPreOrderSSARename(BasicBlock* block) {
Brian Carlstrom0cd7ec22013-07-17 23:40:20 -0700549 if (block->visited || block->hidden) {
550 return;
551 }
Bill Buzbeea114add2012-05-03 15:00:40 -0700552 block->visited = true;
buzbeef0cde542011-09-13 14:55:02 -0700553
Bill Buzbeea114add2012-05-03 15:00:40 -0700554 /* Process this block */
buzbee311ca162013-02-28 15:56:43 -0800555 DoSSAConversion(block);
Razvan A Lupusoru8d0d03e2014-06-06 17:04:52 -0700556 int map_size = sizeof(int) * GetNumOfCodeAndTempVRs();
buzbeef0cde542011-09-13 14:55:02 -0700557
Bill Buzbeea114add2012-05-03 15:00:40 -0700558 /* Save SSA map snapshot */
Vladimir Marko5d474472014-03-21 17:10:58 +0000559 ScopedArenaAllocator allocator(&cu_->arena_stack);
buzbee862a7602013-04-05 10:58:54 -0700560 int* saved_ssa_map =
Vladimir Marko5d474472014-03-21 17:10:58 +0000561 static_cast<int*>(allocator.Alloc(map_size, kArenaAllocDalvikToSSAMap));
buzbee311ca162013-02-28 15:56:43 -0800562 memcpy(saved_ssa_map, vreg_to_ssa_map_, map_size);
buzbeef0cde542011-09-13 14:55:02 -0700563
buzbee0d829482013-10-11 15:24:55 -0700564 if (block->fall_through != NullBasicBlockId) {
565 DoDFSPreOrderSSARename(GetBasicBlock(block->fall_through));
Bill Buzbeea114add2012-05-03 15:00:40 -0700566 /* Restore SSA map snapshot */
buzbee311ca162013-02-28 15:56:43 -0800567 memcpy(vreg_to_ssa_map_, saved_ssa_map, map_size);
Bill Buzbeea114add2012-05-03 15:00:40 -0700568 }
buzbee0d829482013-10-11 15:24:55 -0700569 if (block->taken != NullBasicBlockId) {
570 DoDFSPreOrderSSARename(GetBasicBlock(block->taken));
Bill Buzbeea114add2012-05-03 15:00:40 -0700571 /* Restore SSA map snapshot */
buzbee311ca162013-02-28 15:56:43 -0800572 memcpy(vreg_to_ssa_map_, saved_ssa_map, map_size);
Bill Buzbeea114add2012-05-03 15:00:40 -0700573 }
buzbee0d829482013-10-11 15:24:55 -0700574 if (block->successor_block_list_type != kNotUsed) {
Vladimir Markoe39c54e2014-09-22 14:50:02 +0100575 for (SuccessorBlockInfo* successor_block_info : block->successor_blocks) {
buzbee0d829482013-10-11 15:24:55 -0700576 BasicBlock* succ_bb = GetBasicBlock(successor_block_info->block);
buzbee311ca162013-02-28 15:56:43 -0800577 DoDFSPreOrderSSARename(succ_bb);
Bill Buzbeea114add2012-05-03 15:00:40 -0700578 /* Restore SSA map snapshot */
buzbee311ca162013-02-28 15:56:43 -0800579 memcpy(vreg_to_ssa_map_, saved_ssa_map, map_size);
buzbeef0cde542011-09-13 14:55:02 -0700580 }
Bill Buzbeea114add2012-05-03 15:00:40 -0700581 }
Bill Buzbeea114add2012-05-03 15:00:40 -0700582 return;
buzbeef0cde542011-09-13 14:55:02 -0700583}
584
Elliott Hughes11d1b0c2012-01-23 16:57:47 -0800585} // namespace art