ssa_transformation.cc revision 700a402244a1a423da4f3ba8032459f4b65fa18f 
1/*
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
17#include "bit_vector_block_iterator.h"
18#include "compiler_internals.h"
19#include "dataflow_iterator-inl.h"
20
21#define NOTVISITED (-1)
22
23namespace art {
24
25void MIRGraph::ClearAllVisitedFlags() {
26  AllNodesIterator iter(this);
27  for (BasicBlock* bb = iter.Next(); bb != NULL; bb = iter.Next()) {
28    bb->visited = false;
29  }
30}
31
32BasicBlock* MIRGraph::NeedsVisit(BasicBlock* bb) {
33  if (bb != NULL) {
34    if (bb->visited || bb->hidden) {
35      bb = NULL;
36    }
37  }
38  return bb;
39}
40
41BasicBlock* MIRGraph::NextUnvisitedSuccessor(BasicBlock* bb) {
42  BasicBlock* res = NeedsVisit(GetBasicBlock(bb->fall_through));
43  if (res == NULL) {
44    res = NeedsVisit(GetBasicBlock(bb->taken));
45    if (res == NULL) {
46      if (bb->successor_block_list_type != kNotUsed) {
47        GrowableArray<SuccessorBlockInfo*>::Iterator iterator(bb->successor_blocks);
48        while (true) {
49          SuccessorBlockInfo *sbi = iterator.Next();
50          if (sbi == NULL) {
51            break;
52          }
53          res = NeedsVisit(GetBasicBlock(sbi->block));
54          if (res != NULL) {
55            break;
56          }
57        }
58      }
59    }
60  }
61  return res;
62}
63
64void MIRGraph::MarkPreOrder(BasicBlock* block) {
65  block->visited = true;
66  /* Enqueue the pre_order block id */
67  if (block->id != NullBasicBlockId) {
68    dfs_order_->Insert(block->id);
69  }
70}
71
72void MIRGraph::RecordDFSOrders(BasicBlock* block) {
73  std::vector<BasicBlock*> succ;
74  MarkPreOrder(block);
75  succ.push_back(block);
76  while (!succ.empty()) {
77    BasicBlock* curr = succ.back();
78    BasicBlock* next_successor = NextUnvisitedSuccessor(curr);
79    if (next_successor != NULL) {
80      MarkPreOrder(next_successor);
81      succ.push_back(next_successor);
82      continue;
83    }
84    curr->dfs_id = dfs_post_order_->Size();
85    if (curr->id != NullBasicBlockId) {
86      dfs_post_order_->Insert(curr->id);
87    }
88    succ.pop_back();
89  }
90}
91
92/* Sort the blocks by the Depth-First-Search */
93void MIRGraph::ComputeDFSOrders() {
94  /* Initialize or reset the DFS pre_order list */
95  if (dfs_order_ == NULL) {
96    dfs_order_ = new (arena_) GrowableArray<BasicBlockId>(arena_, GetNumBlocks(),
97                                                          kGrowableArrayDfsOrder);
98  } else {
99    /* Just reset the used length on the counter */
100    dfs_order_->Reset();
101  }
102
103  /* Initialize or reset the DFS post_order list */
104  if (dfs_post_order_ == NULL) {
105    dfs_post_order_ = new (arena_) GrowableArray<BasicBlockId>(arena_, GetNumBlocks(),
106                                                               kGrowableArrayDfsPostOrder);
107  } else {
108    /* Just reset the used length on the counter */
109    dfs_post_order_->Reset();
110  }
111
112  // Reset visited flags from all nodes
113  ClearAllVisitedFlags();
114
115  // Record dfs orders
116  RecordDFSOrders(GetEntryBlock());
117
118  num_reachable_blocks_ = dfs_order_->Size();
119}
120
121/*
122 * Mark block bit on the per-Dalvik register vector to denote that Dalvik
123 * register idx is defined in BasicBlock bb.
124 */
125bool MIRGraph::FillDefBlockMatrix(BasicBlock* bb) {
126  if (bb->data_flow_info == NULL) {
127    return false;
128  }
129
130  ArenaBitVector::Iterator iterator(bb->data_flow_info->def_v);
131  while (true) {
132    int idx = iterator.Next();
133    if (idx == -1) {
134      break;
135    }
136    /* Block bb defines register idx */
137    def_block_matrix_[idx]->SetBit(bb->id);
138  }
139  return true;
140}
141
142void MIRGraph::ComputeDefBlockMatrix() {
143  int num_registers = cu_->num_dalvik_registers;
144  /* Allocate num_dalvik_registers bit vector pointers */
145  def_block_matrix_ = static_cast<ArenaBitVector**>
146      (arena_->Alloc(sizeof(ArenaBitVector *) * num_registers,
147                     kArenaAllocDFInfo));
148  int i;
149
150  /* Initialize num_register vectors with num_blocks bits each */
151  for (i = 0; i < num_registers; i++) {
152    def_block_matrix_[i] =
153        new (arena_) ArenaBitVector(arena_, GetNumBlocks(), false, kBitMapBMatrix);
154  }
155  AllNodesIterator iter(this);
156  for (BasicBlock* bb = iter.Next(); bb != NULL; bb = iter.Next()) {
157    FindLocalLiveIn(bb);
158  }
159  AllNodesIterator iter2(this);
160  for (BasicBlock* bb = iter2.Next(); bb != NULL; bb = iter2.Next()) {
161    FillDefBlockMatrix(bb);
162  }
163
164  /*
165   * Also set the incoming parameters as defs in the entry block.
166   * Only need to handle the parameters for the outer method.
167   */
168  int num_regs = cu_->num_dalvik_registers;
169  int in_reg = num_regs - cu_->num_ins;
170  for (; in_reg < num_regs; in_reg++) {
171    def_block_matrix_[in_reg]->SetBit(GetEntryBlock()->id);
172  }
173}
174
175void MIRGraph::ComputeDomPostOrderTraversal(BasicBlock* bb) {
176  if (dom_post_order_traversal_ == NULL) {
177    // First time - create the array.
178    dom_post_order_traversal_ =
179        new (arena_) GrowableArray<BasicBlockId>(arena_, num_reachable_blocks_,
180                                        kGrowableArrayDomPostOrderTraversal);
181  } else {
182    dom_post_order_traversal_->Reset();
183  }
184  ClearAllVisitedFlags();
185  std::vector<std::pair<BasicBlock*, ArenaBitVector::Iterator*>> work_stack;
186  bb->visited = true;
187  work_stack.push_back(std::make_pair(bb, bb->i_dominated->GetIterator()));
188  while (!work_stack.empty()) {
189    const std::pair<BasicBlock*, ArenaBitVector::Iterator*>& curr = work_stack.back();
190    BasicBlock* curr_bb = curr.first;
191    ArenaBitVector::Iterator* curr_idom_iter = curr.second;
192    int bb_idx = curr_idom_iter->Next();
193    while ((bb_idx != -1) && (NeedsVisit(GetBasicBlock(bb_idx)) == NULL)) {
194      bb_idx = curr_idom_iter->Next();
195    }
196    if (bb_idx != -1) {
197      BasicBlock* new_bb = GetBasicBlock(bb_idx);
198      new_bb->visited = true;
199      work_stack.push_back(
200          std::make_pair(new_bb, new_bb->i_dominated->GetIterator()));
201    } else {
202      // no successor/next
203      if (curr_bb->id != NullBasicBlockId) {
204        dom_post_order_traversal_->Insert(curr_bb->id);
205      }
206      work_stack.pop_back();
207
208      /* hacky loop detection */
209      if ((curr_bb->taken != NullBasicBlockId) && curr_bb->dominators->IsBitSet(curr_bb->taken)) {
210        curr_bb->nesting_depth++;
211        attributes_ |= METHOD_HAS_LOOP;
212      }
213    }
214  }
215}
216
217void MIRGraph::CheckForDominanceFrontier(BasicBlock* dom_bb,
218                                         const BasicBlock* succ_bb) {
219  /*
220   * TODO - evaluate whether phi will ever need to be inserted into exit
221   * blocks.
222   */
223  if (succ_bb->i_dom != dom_bb->id &&
224    succ_bb->block_type == kDalvikByteCode &&
225    succ_bb->hidden == false) {
226    dom_bb->dom_frontier->SetBit(succ_bb->id);
227  }
228}
229
230/* Worker function to compute the dominance frontier */
231bool MIRGraph::ComputeDominanceFrontier(BasicBlock* bb) {
232  /* Calculate DF_local */
233  if (bb->taken != NullBasicBlockId) {
234    CheckForDominanceFrontier(bb, GetBasicBlock(bb->taken));
235  }
236  if (bb->fall_through != NullBasicBlockId) {
237    CheckForDominanceFrontier(bb, GetBasicBlock(bb->fall_through));
238  }
239  if (bb->successor_block_list_type != kNotUsed) {
240    GrowableArray<SuccessorBlockInfo*>::Iterator iterator(bb->successor_blocks);
241      while (true) {
242        SuccessorBlockInfo *successor_block_info = iterator.Next();
243        if (successor_block_info == NULL) {
244          break;
245        }
246        BasicBlock* succ_bb = GetBasicBlock(successor_block_info->block);
247        CheckForDominanceFrontier(bb, succ_bb);
248      }
249  }
250
251  /* Calculate DF_up */
252  BitVectorBlockIterator it(bb->i_dominated, cu_);
253  for (BasicBlock *dominated_bb = it.Next(); dominated_bb != nullptr; dominated_bb = it.Next()) {
254    BitVectorBlockIterator inner_it(dominated_bb->dom_frontier, cu_);
255    for (BasicBlock *df_up_block = inner_it.Next(); df_up_block != nullptr;
256         df_up_block = inner_it.Next()) {
257      CheckForDominanceFrontier(bb, df_up_block);
258    }
259  }
260
261  return true;
262}
263
264/* Worker function for initializing domination-related data structures */
265void MIRGraph::InitializeDominationInfo(BasicBlock* bb) {
266  int num_total_blocks = GetBasicBlockListCount();
267
268  if (bb->dominators == NULL) {
269    bb->dominators = new (arena_) ArenaBitVector(arena_, num_total_blocks,
270                                                 false /* expandable */, kBitMapDominators);
271    bb->i_dominated = new (arena_) ArenaBitVector(arena_, num_total_blocks,
272                                                  false /* expandable */, kBitMapIDominated);
273    bb->dom_frontier = new (arena_) ArenaBitVector(arena_, num_total_blocks,
274                                                   false /* expandable */, kBitMapDomFrontier);
275  } else {
276    bb->dominators->ClearAllBits();
277    bb->i_dominated->ClearAllBits();
278    bb->dom_frontier->ClearAllBits();
279  }
280  /* Set all bits in the dominator vector */
281  bb->dominators->SetInitialBits(num_total_blocks);
282
283  return;
284}
285
286/*
287 * Walk through the ordered i_dom list until we reach common parent.
288 * Given the ordering of i_dom_list, this common parent represents the
289 * last element of the intersection of block1 and block2 dominators.
290  */
291int MIRGraph::FindCommonParent(int block1, int block2) {
292  while (block1 != block2) {
293    while (block1 < block2) {
294      block1 = i_dom_list_[block1];
295      DCHECK_NE(block1, NOTVISITED);
296    }
297    while (block2 < block1) {
298      block2 = i_dom_list_[block2];
299      DCHECK_NE(block2, NOTVISITED);
300    }
301  }
302  return block1;
303}
304
305/* Worker function to compute each block's immediate dominator */
306bool MIRGraph::ComputeblockIDom(BasicBlock* bb) {
307  /* Special-case entry block */
308  if ((bb->id == NullBasicBlockId) || (bb == GetEntryBlock())) {
309    return false;
310  }
311
312  /* Iterate through the predecessors */
313  GrowableArray<BasicBlockId>::Iterator iter(bb->predecessors);
314
315  /* Find the first processed predecessor */
316  int idom = -1;
317  while (true) {
318    BasicBlock* pred_bb = GetBasicBlock(iter.Next());
319    CHECK(pred_bb != NULL);
320    if (i_dom_list_[pred_bb->dfs_id] != NOTVISITED) {
321      idom = pred_bb->dfs_id;
322      break;
323    }
324  }
325
326  /* Scan the rest of the predecessors */
327  while (true) {
328      BasicBlock* pred_bb = GetBasicBlock(iter.Next());
329      if (!pred_bb) {
330        break;
331      }
332      if (i_dom_list_[pred_bb->dfs_id] == NOTVISITED) {
333        continue;
334      } else {
335        idom = FindCommonParent(pred_bb->dfs_id, idom);
336      }
337  }
338
339  DCHECK_NE(idom, NOTVISITED);
340
341  /* Did something change? */
342  if (i_dom_list_[bb->dfs_id] != idom) {
343    i_dom_list_[bb->dfs_id] = idom;
344    return true;
345  }
346  return false;
347}
348
349/* Worker function to compute each block's domintors */
350bool MIRGraph::ComputeBlockDominators(BasicBlock* bb) {
351  if (bb == GetEntryBlock()) {
352    bb->dominators->ClearAllBits();
353  } else {
354    bb->dominators->Copy(GetBasicBlock(bb->i_dom)->dominators);
355  }
356  bb->dominators->SetBit(bb->id);
357  return false;
358}
359
360bool MIRGraph::SetDominators(BasicBlock* bb) {
361  if (bb != GetEntryBlock()) {
362    int idom_dfs_idx = i_dom_list_[bb->dfs_id];
363    DCHECK_NE(idom_dfs_idx, NOTVISITED);
364    int i_dom_idx = dfs_post_order_->Get(idom_dfs_idx);
365    BasicBlock* i_dom = GetBasicBlock(i_dom_idx);
366    bb->i_dom = i_dom->id;
367    /* Add bb to the i_dominated set of the immediate dominator block */
368    i_dom->i_dominated->SetBit(bb->id);
369  }
370  return false;
371}
372
373/* Compute dominators, immediate dominator, and dominance fronter */
374void MIRGraph::ComputeDominators() {
375  int num_reachable_blocks = num_reachable_blocks_;
376
377  /* Initialize domination-related data structures */
378  PreOrderDfsIterator iter(this);
379  for (BasicBlock* bb = iter.Next(); bb != NULL; bb = iter.Next()) {
380    InitializeDominationInfo(bb);
381  }
382
383  /* Initalize & Clear i_dom_list */
384  if (i_dom_list_ == NULL) {
385    i_dom_list_ = static_cast<int*>(arena_->Alloc(sizeof(int) * num_reachable_blocks,
386                                                  kArenaAllocDFInfo));
387  }
388  for (int i = 0; i < num_reachable_blocks; i++) {
389    i_dom_list_[i] = NOTVISITED;
390  }
391
392  /* For post-order, last block is entry block.  Set its i_dom to istelf */
393  DCHECK_EQ(GetEntryBlock()->dfs_id, num_reachable_blocks-1);
394  i_dom_list_[GetEntryBlock()->dfs_id] = GetEntryBlock()->dfs_id;
395
396  /* Compute the immediate dominators */
397  RepeatingReversePostOrderDfsIterator iter2(this);
398  bool change = false;
399  for (BasicBlock* bb = iter2.Next(false); bb != NULL; bb = iter2.Next(change)) {
400    change = ComputeblockIDom(bb);
401  }
402
403  /* Set the dominator for the root node */
404  GetEntryBlock()->dominators->ClearAllBits();
405  GetEntryBlock()->dominators->SetBit(GetEntryBlock()->id);
406
407  GetEntryBlock()->i_dom = 0;
408
409  PreOrderDfsIterator iter3(this);
410  for (BasicBlock* bb = iter3.Next(); bb != NULL; bb = iter3.Next()) {
411    SetDominators(bb);
412  }
413
414  ReversePostOrderDfsIterator iter4(this);
415  for (BasicBlock* bb = iter4.Next(); bb != NULL; bb = iter4.Next()) {
416    ComputeBlockDominators(bb);
417  }
418
419  // Compute the dominance frontier for each block.
420  ComputeDomPostOrderTraversal(GetEntryBlock());
421  PostOrderDOMIterator iter5(this);
422  for (BasicBlock* bb = iter5.Next(); bb != NULL; bb = iter5.Next()) {
423    ComputeDominanceFrontier(bb);
424  }
425}
426
427/*
428 * Perform dest U= src1 ^ ~src2
429 * This is probably not general enough to be placed in BitVector.[ch].
430 */
431void MIRGraph::ComputeSuccLineIn(ArenaBitVector* dest, const ArenaBitVector* src1,
432                                 const ArenaBitVector* src2) {
433  if (dest->GetStorageSize() != src1->GetStorageSize() ||
434      dest->GetStorageSize() != src2->GetStorageSize() ||
435      dest->IsExpandable() != src1->IsExpandable() ||
436      dest->IsExpandable() != src2->IsExpandable()) {
437    LOG(FATAL) << "Incompatible set properties";
438  }
439
440  unsigned int idx;
441  for (idx = 0; idx < dest->GetStorageSize(); idx++) {
442    dest->GetRawStorage()[idx] |= src1->GetRawStorageWord(idx) & ~(src2->GetRawStorageWord(idx));
443  }
444}
445
446/*
447 * Iterate through all successor blocks and propagate up the live-in sets.
448 * The calculated result is used for phi-node pruning - where we only need to
449 * insert a phi node if the variable is live-in to the block.
450 */
451bool MIRGraph::ComputeBlockLiveIns(BasicBlock* bb) {
452  ArenaBitVector* temp_dalvik_register_v = temp_dalvik_register_v_;
453
454  if (bb->data_flow_info == NULL) {
455    return false;
456  }
457  temp_dalvik_register_v->Copy(bb->data_flow_info->live_in_v);
458  BasicBlock* bb_taken = GetBasicBlock(bb->taken);
459  BasicBlock* bb_fall_through = GetBasicBlock(bb->fall_through);
460  if (bb_taken && bb_taken->data_flow_info)
461    ComputeSuccLineIn(temp_dalvik_register_v, bb_taken->data_flow_info->live_in_v,
462                      bb->data_flow_info->def_v);
463  if (bb_fall_through && bb_fall_through->data_flow_info)
464    ComputeSuccLineIn(temp_dalvik_register_v, bb_fall_through->data_flow_info->live_in_v,
465                      bb->data_flow_info->def_v);
466  if (bb->successor_block_list_type != kNotUsed) {
467    GrowableArray<SuccessorBlockInfo*>::Iterator iterator(bb->successor_blocks);
468    while (true) {
469      SuccessorBlockInfo *successor_block_info = iterator.Next();
470      if (successor_block_info == NULL) {
471        break;
472      }
473      BasicBlock* succ_bb = GetBasicBlock(successor_block_info->block);
474      if (succ_bb->data_flow_info) {
475        ComputeSuccLineIn(temp_dalvik_register_v, succ_bb->data_flow_info->live_in_v,
476                          bb->data_flow_info->def_v);
477      }
478    }
479  }
480  if (!temp_dalvik_register_v->Equal(bb->data_flow_info->live_in_v)) {
481    bb->data_flow_info->live_in_v->Copy(temp_dalvik_register_v);
482    return true;
483  }
484  return false;
485}
486
487/* Insert phi nodes to for each variable to the dominance frontiers */
488void MIRGraph::InsertPhiNodes() {
489  int dalvik_reg;
490  ArenaBitVector* phi_blocks =
491      new (arena_) ArenaBitVector(arena_, GetNumBlocks(), false, kBitMapPhi);
492  ArenaBitVector* tmp_blocks =
493      new (arena_) ArenaBitVector(arena_, GetNumBlocks(), false, kBitMapTmpBlocks);
494  ArenaBitVector* input_blocks =
495      new (arena_) ArenaBitVector(arena_, GetNumBlocks(), false, kBitMapInputBlocks);
496
497  temp_dalvik_register_v_ =
498      new (arena_) ArenaBitVector(arena_, cu_->num_dalvik_registers, false, kBitMapRegisterV);
499
500  RepeatingPostOrderDfsIterator iter(this);
501  bool change = false;
502  for (BasicBlock* bb = iter.Next(false); bb != NULL; bb = iter.Next(change)) {
503    change = ComputeBlockLiveIns(bb);
504  }
505
506  /* Iterate through each Dalvik register */
507  for (dalvik_reg = cu_->num_dalvik_registers - 1; dalvik_reg >= 0; dalvik_reg--) {
508    bool change;
509
510    input_blocks->Copy(def_block_matrix_[dalvik_reg]);
511    phi_blocks->ClearAllBits();
512
513    /* Calculate the phi blocks for each Dalvik register */
514    do {
515      change = false;
516      tmp_blocks->ClearAllBits();
517      ArenaBitVector::Iterator iterator(input_blocks);
518
519      while (true) {
520        int idx = iterator.Next();
521        if (idx == -1) {
522          break;
523        }
524        BasicBlock* def_bb = GetBasicBlock(idx);
525
526        /* Merge the dominance frontier to tmp_blocks */
527        // TUNING: hot call to Union().
528        if (def_bb->dom_frontier != NULL) {
529          tmp_blocks->Union(def_bb->dom_frontier);
530        }
531      }
532      if (!phi_blocks->Equal(tmp_blocks)) {
533        change = true;
534        phi_blocks->Copy(tmp_blocks);
535
536        /*
537         * Iterate through the original blocks plus the new ones in
538         * the dominance frontier.
539         */
540        input_blocks->Copy(phi_blocks);
541        input_blocks->Union(def_block_matrix_[dalvik_reg]);
542      }
543    } while (change);
544
545    /*
546     * Insert a phi node for dalvik_reg in the phi_blocks if the Dalvik
547     * register is in the live-in set.
548     */
549    ArenaBitVector::Iterator iterator(phi_blocks);
550    while (true) {
551      int idx = iterator.Next();
552      if (idx == -1) {
553        break;
554      }
555      BasicBlock* phi_bb = GetBasicBlock(idx);
556      /* Variable will be clobbered before being used - no need for phi */
557      if (!phi_bb->data_flow_info->live_in_v->IsBitSet(dalvik_reg)) {
558        continue;
559      }
560      MIR *phi =
561          static_cast<MIR*>(arena_->Alloc(sizeof(MIR), kArenaAllocDFInfo));
562      phi->dalvikInsn.opcode = static_cast<Instruction::Code>(kMirOpPhi);
563      phi->dalvikInsn.vA = dalvik_reg;
564      phi->offset = phi_bb->start_offset;
565      phi->m_unit_index = 0;  // Arbitrarily assign all Phi nodes to outermost method.
566      phi_bb->PrependMIR(phi);
567    }
568  }
569}
570
571/*
572 * Worker function to insert phi-operands with latest SSA names from
573 * predecessor blocks
574 */
575bool MIRGraph::InsertPhiNodeOperands(BasicBlock* bb) {
576  /* Phi nodes are at the beginning of each block */
577  for (MIR* mir = bb->first_mir_insn; mir != NULL; mir = mir->next) {
578    if (mir->dalvikInsn.opcode != static_cast<Instruction::Code>(kMirOpPhi))
579      return true;
580    int ssa_reg = mir->ssa_rep->defs[0];
581    DCHECK_GE(ssa_reg, 0);   // Shouldn't see compiler temps here
582    int v_reg = SRegToVReg(ssa_reg);
583
584    /* Iterate through the predecessors */
585    GrowableArray<BasicBlockId>::Iterator iter(bb->predecessors);
586    size_t num_uses = bb->predecessors->Size();
587    mir->ssa_rep->num_uses = num_uses;
588    int* uses = static_cast<int*>(arena_->Alloc(sizeof(int) * num_uses,
589                                                kArenaAllocDFInfo));
590    mir->ssa_rep->uses = uses;
591    mir->ssa_rep->fp_use =
592        static_cast<bool*>(arena_->Alloc(sizeof(bool) * num_uses, kArenaAllocDFInfo));
593    BasicBlockId* incoming =
594        static_cast<BasicBlockId*>(arena_->Alloc(sizeof(BasicBlockId) * num_uses,
595                                                 kArenaAllocDFInfo));
596    mir->meta.phi_incoming = incoming;
597    int idx = 0;
598    while (true) {
599      BasicBlock* pred_bb = GetBasicBlock(iter.Next());
600      if (!pred_bb) {
601        break;
602      }
603      int ssa_reg = pred_bb->data_flow_info->vreg_to_ssa_map[v_reg];
604      uses[idx] = ssa_reg;
605      incoming[idx] = pred_bb->id;
606      idx++;
607    }
608  }
609
610  return true;
611}
612
613void MIRGraph::DoDFSPreOrderSSARename(BasicBlock* block) {
614  if (block->visited || block->hidden) {
615    return;
616  }
617  block->visited = true;
618
619  /* Process this block */
620  DoSSAConversion(block);
621  int map_size = sizeof(int) * cu_->num_dalvik_registers;
622
623  /* Save SSA map snapshot */
624  ScopedArenaAllocator allocator(&cu_->arena_stack);
625  int* saved_ssa_map =
626      static_cast<int*>(allocator.Alloc(map_size, kArenaAllocDalvikToSSAMap));
627  memcpy(saved_ssa_map, vreg_to_ssa_map_, map_size);
628
629  if (block->fall_through != NullBasicBlockId) {
630    DoDFSPreOrderSSARename(GetBasicBlock(block->fall_through));
631    /* Restore SSA map snapshot */
632    memcpy(vreg_to_ssa_map_, saved_ssa_map, map_size);
633  }
634  if (block->taken != NullBasicBlockId) {
635    DoDFSPreOrderSSARename(GetBasicBlock(block->taken));
636    /* Restore SSA map snapshot */
637    memcpy(vreg_to_ssa_map_, saved_ssa_map, map_size);
638  }
639  if (block->successor_block_list_type != kNotUsed) {
640    GrowableArray<SuccessorBlockInfo*>::Iterator iterator(block->successor_blocks);
641    while (true) {
642      SuccessorBlockInfo *successor_block_info = iterator.Next();
643      if (successor_block_info == NULL) {
644        break;
645      }
646      BasicBlock* succ_bb = GetBasicBlock(successor_block_info->block);
647      DoDFSPreOrderSSARename(succ_bb);
648      /* Restore SSA map snapshot */
649      memcpy(vreg_to_ssa_map_, saved_ssa_map, map_size);
650    }
651  }
652  return;
653}
654
655}  // namespace art
656