diff options
Diffstat (limited to 'compiler/dex/mir_graph.cc')
| -rw-r--r-- | compiler/dex/mir_graph.cc | 337 |
1 files changed, 137 insertions, 200 deletions
diff --git a/compiler/dex/mir_graph.cc b/compiler/dex/mir_graph.cc index ce5625533e..7c0a996a43 100644 --- a/compiler/dex/mir_graph.cc +++ b/compiler/dex/mir_graph.cc @@ -76,23 +76,23 @@ MIRGraph::MIRGraph(CompilationUnit* cu, ArenaAllocator* arena) : reg_location_(NULL), block_id_map_(std::less<unsigned int>(), arena->Adapter()), cu_(cu), - ssa_base_vregs_(NULL), - ssa_subscripts_(NULL), + ssa_base_vregs_(arena->Adapter(kArenaAllocSSAToDalvikMap)), + ssa_subscripts_(arena->Adapter(kArenaAllocSSAToDalvikMap)), vreg_to_ssa_map_(NULL), ssa_last_defs_(NULL), is_constant_v_(NULL), constant_values_(NULL), - use_counts_(arena, 256, kGrowableArrayMisc), - raw_use_counts_(arena, 256, kGrowableArrayMisc), + use_counts_(arena->Adapter()), + raw_use_counts_(arena->Adapter()), num_reachable_blocks_(0), max_num_reachable_blocks_(0), - dfs_order_(NULL), - dfs_post_order_(NULL), - dom_post_order_traversal_(NULL), - topological_order_(nullptr), - topological_order_loop_ends_(nullptr), - topological_order_indexes_(nullptr), - topological_order_loop_head_stack_(nullptr), + dfs_order_(arena->Adapter(kArenaAllocDfsPreOrder)), + dfs_post_order_(arena->Adapter(kArenaAllocDfsPostOrder)), + dom_post_order_traversal_(arena->Adapter(kArenaAllocDomPostOrder)), + topological_order_(arena->Adapter(kArenaAllocTopologicalSortOrder)), + topological_order_loop_ends_(arena->Adapter(kArenaAllocTopologicalSortOrder)), + topological_order_indexes_(arena->Adapter(kArenaAllocTopologicalSortOrder)), + topological_order_loop_head_stack_(arena->Adapter(kArenaAllocTopologicalSortOrder)), i_dom_list_(NULL), def_block_matrix_(NULL), temp_scoped_alloc_(), @@ -100,13 +100,13 @@ MIRGraph::MIRGraph(CompilationUnit* cu, ArenaAllocator* arena) temp_bit_vector_size_(0u), temp_bit_vector_(nullptr), temp_gvn_(), - block_list_(arena, 100, kGrowableArrayBlockList), + block_list_(arena->Adapter(kArenaAllocBBList)), try_block_addr_(NULL), entry_block_(NULL), exit_block_(NULL), num_blocks_(0), current_code_item_(NULL), - dex_pc_to_block_map_(arena, 0, kGrowableArrayMisc), + dex_pc_to_block_map_(arena->Adapter()), m_units_(arena->Adapter()), method_stack_(arena->Adapter()), current_method_(kInvalidEntry), @@ -127,10 +127,13 @@ MIRGraph::MIRGraph(CompilationUnit* cu, ArenaAllocator* arena) compiler_temps_committed_(false), punt_to_interpreter_(false), merged_df_flags_(0u), - ifield_lowering_infos_(arena, 0u), - sfield_lowering_infos_(arena, 0u), - method_lowering_infos_(arena, 0u), - gen_suspend_test_list_(arena, 0u) { + ifield_lowering_infos_(arena->Adapter(kArenaAllocLoweringInfo)), + sfield_lowering_infos_(arena->Adapter(kArenaAllocLoweringInfo)), + method_lowering_infos_(arena->Adapter(kArenaAllocLoweringInfo)), + gen_suspend_test_list_(arena->Adapter()) { + use_counts_.reserve(256); + raw_use_counts_.reserve(256); + block_list_.reserve(100); try_block_addr_ = new (arena_) ArenaBitVector(arena_, 0, true /* expandable */); @@ -149,6 +152,7 @@ MIRGraph::MIRGraph(CompilationUnit* cu, ArenaAllocator* arena) } MIRGraph::~MIRGraph() { + STLDeleteElements(&block_list_); STLDeleteElements(&m_units_); } @@ -183,8 +187,7 @@ BasicBlock* MIRGraph::SplitBlock(DexOffset code_offset, if (insn == NULL) { LOG(FATAL) << "Break split failed"; } - BasicBlock* bottom_block = NewMemBB(kDalvikByteCode, num_blocks_++); - block_list_.Insert(bottom_block); + BasicBlock* bottom_block = CreateNewBB(kDalvikByteCode); bottom_block->start_offset = code_offset; bottom_block->first_mir_insn = insn; @@ -207,34 +210,31 @@ BasicBlock* MIRGraph::SplitBlock(DexOffset code_offset, if (bottom_block->taken != NullBasicBlockId) { orig_block->taken = NullBasicBlockId; BasicBlock* bb_taken = GetBasicBlock(bottom_block->taken); - bb_taken->predecessors->Delete(orig_block->id); - bb_taken->predecessors->Insert(bottom_block->id); + bb_taken->ErasePredecessor(orig_block->id); + bb_taken->predecessors.push_back(bottom_block->id); } /* Handle the fallthrough path */ bottom_block->fall_through = orig_block->fall_through; orig_block->fall_through = bottom_block->id; - bottom_block->predecessors->Insert(orig_block->id); + bottom_block->predecessors.push_back(orig_block->id); if (bottom_block->fall_through != NullBasicBlockId) { BasicBlock* bb_fall_through = GetBasicBlock(bottom_block->fall_through); - bb_fall_through->predecessors->Delete(orig_block->id); - bb_fall_through->predecessors->Insert(bottom_block->id); + bb_fall_through->ErasePredecessor(orig_block->id); + bb_fall_through->predecessors.push_back(bottom_block->id); } /* Handle the successor list */ if (orig_block->successor_block_list_type != kNotUsed) { bottom_block->successor_block_list_type = orig_block->successor_block_list_type; - bottom_block->successor_blocks = orig_block->successor_blocks; + bottom_block->successor_blocks.swap(orig_block->successor_blocks); orig_block->successor_block_list_type = kNotUsed; - orig_block->successor_blocks = nullptr; - GrowableArray<SuccessorBlockInfo*>::Iterator iterator(bottom_block->successor_blocks); - while (true) { - SuccessorBlockInfo* successor_block_info = iterator.Next(); - if (successor_block_info == nullptr) break; + DCHECK(orig_block->successor_blocks.empty()); // Empty after the swap() above. + for (SuccessorBlockInfo* successor_block_info : bottom_block->successor_blocks) { BasicBlock* bb = GetBasicBlock(successor_block_info->block); if (bb != nullptr) { - bb->predecessors->Delete(orig_block->id); - bb->predecessors->Insert(bottom_block->id); + bb->ErasePredecessor(orig_block->id); + bb->predecessors.push_back(bottom_block->id); } } } @@ -258,9 +258,9 @@ BasicBlock* MIRGraph::SplitBlock(DexOffset code_offset, DCHECK_EQ(insn->offset, bottom_block->start_offset); DCHECK(static_cast<int>(insn->dalvikInsn.opcode) == kMirOpCheck || !MIR::DecodedInstruction::IsPseudoMirOp(insn->dalvikInsn.opcode)); - DCHECK_EQ(dex_pc_to_block_map_.Get(insn->offset), orig_block->id); + DCHECK_EQ(dex_pc_to_block_map_[insn->offset], orig_block->id); MIR* p = insn; - dex_pc_to_block_map_.Put(p->offset, bottom_block->id); + dex_pc_to_block_map_[p->offset] = bottom_block->id; while (p != bottom_block->last_mir_insn) { p = p->next; DCHECK(p != nullptr); @@ -273,8 +273,8 @@ BasicBlock* MIRGraph::SplitBlock(DexOffset code_offset, * the first in a BasicBlock, we can't hit it here. */ if ((opcode == kMirOpCheck) || !MIR::DecodedInstruction::IsPseudoMirOp(opcode)) { - DCHECK_EQ(dex_pc_to_block_map_.Get(p->offset), orig_block->id); - dex_pc_to_block_map_.Put(p->offset, bottom_block->id); + DCHECK_EQ(dex_pc_to_block_map_[p->offset], orig_block->id); + dex_pc_to_block_map_[p->offset] = bottom_block->id; } } @@ -295,8 +295,8 @@ BasicBlock* MIRGraph::FindBlock(DexOffset code_offset, bool split, bool create, return NULL; } - int block_id = dex_pc_to_block_map_.Get(code_offset); - BasicBlock* bb = (block_id == 0) ? NULL : block_list_.Get(block_id); + int block_id = dex_pc_to_block_map_[code_offset]; + BasicBlock* bb = GetBasicBlock(block_id); if ((bb != NULL) && (bb->start_offset == code_offset)) { // Does this containing block start with the desired instruction? @@ -314,10 +314,9 @@ BasicBlock* MIRGraph::FindBlock(DexOffset code_offset, bool split, bool create, } // Create a new block. - bb = NewMemBB(kDalvikByteCode, num_blocks_++); - block_list_.Insert(bb); + bb = CreateNewBB(kDalvikByteCode); bb->start_offset = code_offset; - dex_pc_to_block_map_.Put(bb->start_offset, bb->id); + dex_pc_to_block_map_[bb->start_offset] = bb->id; return bb; } @@ -457,7 +456,7 @@ BasicBlock* MIRGraph::ProcessCanBranch(BasicBlock* cur_block, MIR* insn, DexOffs BasicBlock* taken_block = FindBlock(target, /* split */ true, /* create */ true, /* immed_pred_block_p */ &cur_block); cur_block->taken = taken_block->id; - taken_block->predecessors->Insert(cur_block->id); + taken_block->predecessors.push_back(cur_block->id); /* Always terminate the current block for conditional branches */ if (flags & Instruction::kContinue) { @@ -480,7 +479,7 @@ BasicBlock* MIRGraph::ProcessCanBranch(BasicBlock* cur_block, MIR* insn, DexOffs /* immed_pred_block_p */ &cur_block); cur_block->fall_through = fallthrough_block->id; - fallthrough_block->predecessors->Insert(cur_block->id); + fallthrough_block->predecessors.push_back(cur_block->id); } else if (code_ptr < code_end) { FindBlock(cur_offset + width, /* split */ false, /* create */ true, /* immed_pred_block_p */ NULL); @@ -539,8 +538,7 @@ BasicBlock* MIRGraph::ProcessCanSwitch(BasicBlock* cur_block, MIR* insn, DexOffs } cur_block->successor_block_list_type = (insn->dalvikInsn.opcode == Instruction::PACKED_SWITCH) ? kPackedSwitch : kSparseSwitch; - cur_block->successor_blocks = - new (arena_) GrowableArray<SuccessorBlockInfo*>(arena_, size, kGrowableArraySuccessorBlocks); + cur_block->successor_blocks.reserve(size); for (i = 0; i < size; i++) { BasicBlock* case_block = FindBlock(cur_offset + target_table[i], /* split */ true, @@ -552,15 +550,15 @@ BasicBlock* MIRGraph::ProcessCanSwitch(BasicBlock* cur_block, MIR* insn, DexOffs successor_block_info->key = (insn->dalvikInsn.opcode == Instruction::PACKED_SWITCH) ? first_key + i : keyTable[i]; - cur_block->successor_blocks->Insert(successor_block_info); - case_block->predecessors->Insert(cur_block->id); + cur_block->successor_blocks.push_back(successor_block_info); + case_block->predecessors.push_back(cur_block->id); } /* Fall-through case */ BasicBlock* fallthrough_block = FindBlock(cur_offset + width, /* split */ false, /* create */ true, /* immed_pred_block_p */ NULL); cur_block->fall_through = fallthrough_block->id; - fallthrough_block->predecessors->Insert(cur_block->id); + fallthrough_block->predecessors.push_back(cur_block->id); return cur_block; } @@ -593,8 +591,6 @@ BasicBlock* MIRGraph::ProcessCanThrow(BasicBlock* cur_block, MIR* insn, DexOffse } if (cur_block->successor_block_list_type == kNotUsed) { cur_block->successor_block_list_type = kCatch; - cur_block->successor_blocks = new (arena_) GrowableArray<SuccessorBlockInfo*>( - arena_, 2, kGrowableArraySuccessorBlocks); } catch_block->catch_entry = true; if (kIsDebugBuild) { @@ -604,17 +600,16 @@ BasicBlock* MIRGraph::ProcessCanThrow(BasicBlock* cur_block, MIR* insn, DexOffse (arena_->Alloc(sizeof(SuccessorBlockInfo), kArenaAllocSuccessor)); successor_block_info->block = catch_block->id; successor_block_info->key = iterator.GetHandlerTypeIndex(); - cur_block->successor_blocks->Insert(successor_block_info); - catch_block->predecessors->Insert(cur_block->id); + cur_block->successor_blocks.push_back(successor_block_info); + catch_block->predecessors.push_back(cur_block->id); } in_try_block = (cur_block->successor_block_list_type != kNotUsed); } if (!in_try_block && build_all_edges) { - BasicBlock* eh_block = NewMemBB(kExceptionHandling, num_blocks_++); + BasicBlock* eh_block = CreateNewBB(kExceptionHandling); cur_block->taken = eh_block->id; - block_list_.Insert(eh_block); eh_block->start_offset = cur_offset; - eh_block->predecessors->Insert(cur_block->id); + eh_block->predecessors.push_back(cur_block->id); } if (is_throw) { @@ -657,11 +652,10 @@ BasicBlock* MIRGraph::ProcessCanThrow(BasicBlock* cur_block, MIR* insn, DexOffse * Note also that the dex_pc_to_block_map_ entry for the potentially * throwing instruction will refer to the original basic block. */ - BasicBlock* new_block = NewMemBB(kDalvikByteCode, num_blocks_++); - block_list_.Insert(new_block); + BasicBlock* new_block = CreateNewBB(kDalvikByteCode); new_block->start_offset = insn->offset; cur_block->fall_through = new_block->id; - new_block->predecessors->Insert(cur_block->id); + new_block->predecessors.push_back(cur_block->id); MIR* new_insn = NewMIR(); *new_insn = *insn; insn->dalvikInsn.opcode = static_cast<Instruction::Code>(kMirOpCheck); @@ -689,8 +683,8 @@ void MIRGraph::InlineMethod(const DexFile::CodeItem* code_item, uint32_t access_ // TODO: need to rework expansion of block list & try_block_addr when inlining activated. // TUNING: use better estimate of basic blocks for following resize. - block_list_.Resize(block_list_.Size() + current_code_item_->insns_size_in_code_units_); - dex_pc_to_block_map_.SetSize(dex_pc_to_block_map_.Size() + current_code_item_->insns_size_in_code_units_); + block_list_.reserve(block_list_.size() + current_code_item_->insns_size_in_code_units_); + dex_pc_to_block_map_.resize(dex_pc_to_block_map_.size() + current_code_item_->insns_size_in_code_units_); // TODO: replace with explicit resize routine. Using automatic extension side effect for now. try_block_addr_->SetBit(current_code_item_->insns_size_in_code_units_); @@ -702,14 +696,11 @@ void MIRGraph::InlineMethod(const DexFile::CodeItem* code_item, uint32_t access_ DCHECK(exit_block_ == NULL); DCHECK_EQ(num_blocks_, 0U); // Use id 0 to represent a null block. - BasicBlock* null_block = NewMemBB(kNullBlock, num_blocks_++); + BasicBlock* null_block = CreateNewBB(kNullBlock); DCHECK_EQ(null_block->id, NullBasicBlockId); null_block->hidden = true; - block_list_.Insert(null_block); - entry_block_ = NewMemBB(kEntryBlock, num_blocks_++); - block_list_.Insert(entry_block_); - exit_block_ = NewMemBB(kExitBlock, num_blocks_++); - block_list_.Insert(exit_block_); + entry_block_ = CreateNewBB(kEntryBlock); + exit_block_ = CreateNewBB(kExitBlock); // TODO: deprecate all "cu->" fields; move what's left to wherever CompilationUnit is allocated. cu_->dex_file = &dex_file; cu_->class_def_idx = class_def_idx; @@ -727,13 +718,12 @@ void MIRGraph::InlineMethod(const DexFile::CodeItem* code_item, uint32_t access_ } /* Current block to record parsed instructions */ - BasicBlock* cur_block = NewMemBB(kDalvikByteCode, num_blocks_++); + BasicBlock* cur_block = CreateNewBB(kDalvikByteCode); DCHECK_EQ(current_offset_, 0U); cur_block->start_offset = current_offset_; - block_list_.Insert(cur_block); // TODO: for inlining support, insert at the insert point rather than entry block. entry_block_->fall_through = cur_block->id; - cur_block->predecessors->Insert(entry_block_->id); + cur_block->predecessors.push_back(entry_block_->id); /* Identify code range in try blocks and set up the empty catch blocks */ ProcessTryCatchBlocks(); @@ -791,7 +781,7 @@ void MIRGraph::InlineMethod(const DexFile::CodeItem* code_item, uint32_t access_ } // Associate the starting dex_pc for this opcode with its containing basic block. - dex_pc_to_block_map_.Put(insn->offset, cur_block->id); + dex_pc_to_block_map_[insn->offset] = cur_block->id; code_ptr += width; @@ -801,7 +791,7 @@ void MIRGraph::InlineMethod(const DexFile::CodeItem* code_item, uint32_t access_ } else if (flags & Instruction::kReturn) { cur_block->terminated_by_return = true; cur_block->fall_through = exit_block_->id; - exit_block_->predecessors->Insert(cur_block->id); + exit_block_->predecessors.push_back(cur_block->id); /* * Terminate the current block if there are instructions * afterwards. @@ -850,7 +840,7 @@ void MIRGraph::InlineMethod(const DexFile::CodeItem* code_item, uint32_t access_ if ((cur_block->fall_through == NullBasicBlockId) && (flags & Instruction::kContinue)) { cur_block->fall_through = next_block->id; - next_block->predecessors->Insert(cur_block->id); + next_block->predecessors.push_back(cur_block->id); } cur_block = next_block; } @@ -915,7 +905,7 @@ void MIRGraph::DumpCFG(const char* dir_prefix, bool all_blocks, const char *suff int idx; for (idx = 0; idx < num_blocks; idx++) { - int block_idx = all_blocks ? idx : dfs_order_->Get(idx); + int block_idx = all_blocks ? idx : dfs_order_[idx]; BasicBlock* bb = GetBasicBlock(block_idx); if (bb == NULL) continue; if (bb->block_type == kDead) continue; @@ -971,23 +961,17 @@ void MIRGraph::DumpCFG(const char* dir_prefix, bool all_blocks, const char *suff fprintf(file, " succ%04x_%d [shape=%s,label = \"{ \\\n", bb->start_offset, bb->id, (bb->successor_block_list_type == kCatch) ? "Mrecord" : "record"); - GrowableArray<SuccessorBlockInfo*>::Iterator iterator(bb->successor_blocks); - SuccessorBlockInfo* successor_block_info = iterator.Next(); + int last_succ_id = static_cast<int>(bb->successor_blocks.size() - 1u); int succ_id = 0; - while (true) { - if (successor_block_info == NULL) break; - + for (SuccessorBlockInfo* successor_block_info : bb->successor_blocks) { BasicBlock* dest_block = GetBasicBlock(successor_block_info->block); - SuccessorBlockInfo *next_successor_block_info = iterator.Next(); - fprintf(file, " {<f%d> %04x: %04x\\l}%s\\\n", - succ_id++, + succ_id, successor_block_info->key, dest_block->start_offset, - (next_successor_block_info != NULL) ? " | " : " "); - - successor_block_info = next_successor_block_info; + (succ_id != last_succ_id) ? " | " : " "); + ++succ_id; } fprintf(file, " }\"];\n\n"); @@ -996,13 +980,8 @@ void MIRGraph::DumpCFG(const char* dir_prefix, bool all_blocks, const char *suff block_name1, bb->start_offset, bb->id); // Link the successor pseudo-block with all of its potential targets. - GrowableArray<SuccessorBlockInfo*>::Iterator iter(bb->successor_blocks); - succ_id = 0; - while (true) { - SuccessorBlockInfo* successor_block_info = iter.Next(); - if (successor_block_info == NULL) break; - + for (SuccessorBlockInfo* successor_block_info : bb->successor_blocks) { BasicBlock* dest_block = GetBasicBlock(successor_block_info->block); GetBlockName(dest_block, block_name2); @@ -1603,7 +1582,6 @@ const char* MIRGraph::GetShortyFromTargetIdx(int target_idx) { /* Debug Utility - dump a compilation unit */ void MIRGraph::DumpMIRGraph() { - BasicBlock* bb; const char* block_type_names[] = { "Null Block", "Entry Block", @@ -1616,11 +1594,8 @@ void MIRGraph::DumpMIRGraph() { LOG(INFO) << "Compiling " << PrettyMethod(cu_->method_idx, *cu_->dex_file); LOG(INFO) << GetInsns(0) << " insns"; LOG(INFO) << GetNumBlocks() << " blocks in total"; - GrowableArray<BasicBlock*>::Iterator iterator(&block_list_); - while (true) { - bb = iterator.Next(); - if (bb == NULL) break; + for (BasicBlock* bb : block_list_) { LOG(INFO) << StringPrintf("Block %d (%s) (insn %04x - %04x%s)", bb->id, block_type_names[bb->block_type], @@ -1678,15 +1653,10 @@ MIR* MIRGraph::NewMIR() { // Allocate a new basic block. BasicBlock* MIRGraph::NewMemBB(BBType block_type, int block_id) { - BasicBlock* bb = new (arena_) BasicBlock(); + BasicBlock* bb = new (arena_) BasicBlock(block_id, block_type, arena_); - bb->block_type = block_type; - bb->id = block_id; // TUNING: better estimate of the exit block predecessors? - bb->predecessors = new (arena_) GrowableArray<BasicBlockId>(arena_, - (block_type == kExitBlock) ? 2048 : 2, - kGrowableArrayPredecessors); - bb->successor_block_list_type = kNotUsed; + bb->predecessors.reserve((block_type == kExitBlock) ? 2048 : 2); block_id_map_.Put(block_id, block_id); return bb; } @@ -1699,16 +1669,12 @@ void MIRGraph::InitializeConstantPropagation() { void MIRGraph::InitializeMethodUses() { // The gate starts by initializing the use counts. int num_ssa_regs = GetNumSSARegs(); - use_counts_.Resize(num_ssa_regs + 32); - raw_use_counts_.Resize(num_ssa_regs + 32); - // Resize does not actually reset the number of used, so reset before initialization. - use_counts_.Reset(); - raw_use_counts_.Reset(); - // Initialize list. - for (int i = 0; i < num_ssa_regs; i++) { - use_counts_.Insert(0); - raw_use_counts_.Insert(0); - } + use_counts_.clear(); + use_counts_.reserve(num_ssa_regs + 32); + use_counts_.resize(num_ssa_regs, 0u); + raw_use_counts_.clear(); + raw_use_counts_.reserve(num_ssa_regs + 32); + raw_use_counts_.resize(num_ssa_regs, 0u); } void MIRGraph::SSATransformationStart() { @@ -1800,9 +1766,9 @@ static void ComputeUnvisitedReachableFrom(MIRGraph* mir_graph, BasicBlockId bb_i tmp_stack->pop_back(); BasicBlock* current_bb = mir_graph->GetBasicBlock(current_id); DCHECK(current_bb != nullptr); - GrowableArray<BasicBlockId>::Iterator iter(current_bb->predecessors); - BasicBlock* pred_bb = mir_graph->GetBasicBlock(iter.Next()); - for ( ; pred_bb != nullptr; pred_bb = mir_graph->GetBasicBlock(iter.Next())) { + for (BasicBlockId pred_id : current_bb->predecessors) { + BasicBlock* pred_bb = mir_graph->GetBasicBlock(pred_id); + DCHECK(pred_bb != nullptr); if (!pred_bb->visited && !reachable->IsBitSet(pred_bb->id)) { reachable->SetBit(pred_bb->id); tmp_stack->push_back(pred_bb->id); @@ -1823,36 +1789,27 @@ void MIRGraph::ComputeTopologicalSortOrder() { loop_exit_blocks.ClearAllBits(); // Count the number of blocks to process and add the entry block(s). - GrowableArray<BasicBlock*>::Iterator iterator(&block_list_); unsigned int num_blocks_to_process = 0u; - for (BasicBlock* bb = iterator.Next(); bb != nullptr; bb = iterator.Next()) { + for (BasicBlock* bb : block_list_) { if (bb->hidden == true) { continue; } num_blocks_to_process += 1u; - if (bb->predecessors->Size() == 0u) { + if (bb->predecessors.size() == 0u) { // Add entry block to the queue. q.push(bb); } } - // Create the topological order if need be. - if (topological_order_ == nullptr) { - topological_order_ = new (arena_) GrowableArray<BasicBlockId>(arena_, num_blocks); - topological_order_loop_ends_ = new (arena_) GrowableArray<uint16_t>(arena_, num_blocks); - topological_order_indexes_ = new (arena_) GrowableArray<uint16_t>(arena_, num_blocks); - } - topological_order_->Reset(); - topological_order_loop_ends_->Reset(); - topological_order_indexes_->Reset(); - topological_order_loop_ends_->Resize(num_blocks); - topological_order_indexes_->Resize(num_blocks); - for (BasicBlockId i = 0; i != num_blocks; ++i) { - topological_order_loop_ends_->Insert(0u); - topological_order_indexes_->Insert(static_cast<uint16_t>(-1)); - } + // Clear the topological order arrays. + topological_order_.clear(); + topological_order_.reserve(num_blocks); + topological_order_loop_ends_.clear(); + topological_order_loop_ends_.resize(num_blocks, 0u); + topological_order_indexes_.clear(); + topological_order_indexes_.resize(num_blocks, static_cast<uint16_t>(-1)); // Mark all blocks as unvisited. ClearAllVisitedFlags(); @@ -1875,8 +1832,8 @@ void MIRGraph::ComputeTopologicalSortOrder() { if (bb->visited) { // Loop head: it was already processed, mark end and copy exit blocks to the queue. DCHECK(q.empty()) << PrettyMethod(cu_->method_idx, *cu_->dex_file); - uint16_t idx = static_cast<uint16_t>(topological_order_->Size()); - topological_order_loop_ends_->Put(topological_order_indexes_->Get(bb->id), idx); + uint16_t idx = static_cast<uint16_t>(topological_order_.size()); + topological_order_loop_ends_[topological_order_indexes_[bb->id]] = idx; DCHECK_EQ(loop_head_stack.back(), bb->id); loop_head_stack.pop_back(); ArenaBitVector* reachable = @@ -1919,15 +1876,16 @@ void MIRGraph::ComputeTopologicalSortOrder() { continue; } - GrowableArray<BasicBlockId>::Iterator pred_iter(candidate->predecessors); - BasicBlock* pred_bb = GetBasicBlock(pred_iter.Next()); - for ( ; pred_bb != nullptr; pred_bb = GetBasicBlock(pred_iter.Next())) { + for (BasicBlockId pred_id : candidate->predecessors) { + BasicBlock* pred_bb = GetBasicBlock(pred_id); + DCHECK(pred_bb != nullptr); if (pred_bb != candidate && !pred_bb->visited && !pred_bb->dominators->IsBitSet(candidate->id)) { - break; // Keep non-null pred_bb to indicate failure. + candidate = nullptr; // Set candidate to null to indicate failure. + break; } } - if (pred_bb == nullptr) { + if (candidate != nullptr) { bb = candidate; break; } @@ -1947,9 +1905,9 @@ void MIRGraph::ComputeTopologicalSortOrder() { bb->visited = true; // Now add the basic block. - uint16_t idx = static_cast<uint16_t>(topological_order_->Size()); - topological_order_indexes_->Put(bb->id, idx); - topological_order_->Insert(bb->id); + uint16_t idx = static_cast<uint16_t>(topological_order_.size()); + topological_order_indexes_[bb->id] = idx; + topological_order_.push_back(bb->id); // Update visited_cnt_values for children. ChildBlockIterator succIter(bb, this); @@ -1961,7 +1919,7 @@ void MIRGraph::ComputeTopologicalSortOrder() { // One more predecessor was visited. visited_cnt_values[successor->id] += 1u; - if (visited_cnt_values[successor->id] == successor->predecessors->Size()) { + if (visited_cnt_values[successor->id] == successor->predecessors.size()) { if (loop_head_stack.empty() || loop_head_reachable_from[loop_head_stack.back()]->IsBitSet(successor->id)) { q.push(successor); @@ -1974,8 +1932,8 @@ void MIRGraph::ComputeTopologicalSortOrder() { } // Prepare the loop head stack for iteration. - topological_order_loop_head_stack_ = - new (arena_) GrowableArray<std::pair<uint16_t, bool>>(arena_, max_nested_loops); + topological_order_loop_head_stack_.clear(); + topological_order_loop_head_stack_.reserve(max_nested_loops); } bool BasicBlock::IsExceptionBlock() const { @@ -1992,8 +1950,8 @@ bool MIRGraph::HasSuspendTestBetween(BasicBlock* source, BasicBlockId target_id) return false; int idx; - for (idx = gen_suspend_test_list_.Size() - 1; idx >= 0; idx--) { - BasicBlock* bb = gen_suspend_test_list_.Get(idx); + for (idx = gen_suspend_test_list_.size() - 1; idx >= 0; idx--) { + BasicBlock* bb = gen_suspend_test_list_[idx]; if (bb == source) return true; // The block has been inserted by a suspend check before. if (source->dominators->IsBitSet(bb->id) && bb->dominators->IsBitSet(target_id)) @@ -2009,7 +1967,7 @@ ChildBlockIterator::ChildBlockIterator(BasicBlock* bb, MIRGraph* mir_graph) // Check if we actually do have successors. if (basic_block_ != 0 && basic_block_->successor_block_list_type != kNotUsed) { have_successors_ = true; - successor_iter_.Reset(basic_block_->successor_blocks); + successor_iter_ = basic_block_->successor_blocks.cbegin(); } } @@ -2042,9 +2000,10 @@ BasicBlock* ChildBlockIterator::Next() { // We visited both taken and fallthrough. Now check if we have successors we need to visit. if (have_successors_ == true) { // Get information about next successor block. - for (SuccessorBlockInfo* successor_block_info = successor_iter_.Next(); - successor_block_info != nullptr; - successor_block_info = successor_iter_.Next()) { + auto end = basic_block_->successor_blocks.cend(); + while (successor_iter_ != end) { + SuccessorBlockInfo* successor_block_info = *successor_iter_; + ++successor_iter_; // If block was replaced by zero block, take next one. if (successor_block_info->block != NullBasicBlockId) { return mir_graph_->GetBasicBlock(successor_block_info->block); @@ -2075,17 +2034,12 @@ BasicBlock* BasicBlock::Copy(MIRGraph* mir_graph) { result_bb->successor_block_list_type = successor_block_list_type; if (result_bb->successor_block_list_type != kNotUsed) { - size_t size = successor_blocks->Size(); - result_bb->successor_blocks = new (arena) GrowableArray<SuccessorBlockInfo*>(arena, size, kGrowableArraySuccessorBlocks); - GrowableArray<SuccessorBlockInfo*>::Iterator iterator(successor_blocks); - while (true) { - SuccessorBlockInfo* sbi_old = iterator.Next(); - if (sbi_old == nullptr) { - break; - } - SuccessorBlockInfo* sbi_new = static_cast<SuccessorBlockInfo*>(arena->Alloc(sizeof(SuccessorBlockInfo), kArenaAllocSuccessor)); + result_bb->successor_blocks.reserve(successor_blocks.size()); + for (SuccessorBlockInfo* sbi_old : successor_blocks) { + SuccessorBlockInfo* sbi_new = static_cast<SuccessorBlockInfo*>( + arena->Alloc(sizeof(SuccessorBlockInfo), kArenaAllocSuccessor)); memcpy(sbi_new, sbi_old, sizeof(SuccessorBlockInfo)); - result_bb->successor_blocks->Insert(sbi_new); + result_bb->successor_blocks.push_back(sbi_new); } } @@ -2244,14 +2198,10 @@ void BasicBlock::Hide(CompilationUnit* c_unit) { first_mir_insn = nullptr; last_mir_insn = nullptr; - GrowableArray<BasicBlockId>::Iterator iterator(predecessors); - MIRGraph* mir_graph = c_unit->mir_graph.get(); - while (true) { - BasicBlock* pred_bb = mir_graph->GetBasicBlock(iterator.Next()); - if (pred_bb == nullptr) { - break; - } + for (BasicBlockId pred_id : predecessors) { + BasicBlock* pred_bb = mir_graph->GetBasicBlock(pred_id); + DCHECK(pred_bb != nullptr); // Sadly we have to go through the children by hand here. pred_bb->ReplaceChild(id, NullBasicBlockId); @@ -2261,8 +2211,8 @@ void BasicBlock::Hide(CompilationUnit* c_unit) { ChildBlockIterator successorChildIter(this, mir_graph); for (BasicBlock* childPtr = successorChildIter.Next(); childPtr != 0; childPtr = successorChildIter.Next()) { - // Replace child with null child. - childPtr->predecessors->Delete(id); + // Erase this predecessor from child. + childPtr->ErasePredecessor(id); } // Remove link to children. @@ -2328,12 +2278,7 @@ bool BasicBlock::ReplaceChild(BasicBlockId old_bb, BasicBlockId new_bb) { } if (successor_block_list_type != kNotUsed) { - GrowableArray<SuccessorBlockInfo*>::Iterator iterator(successor_blocks); - while (true) { - SuccessorBlockInfo* successor_block_info = iterator.Next(); - if (successor_block_info == nullptr) { - break; - } + for (SuccessorBlockInfo* successor_block_info : successor_blocks) { if (successor_block_info->block == old_bb) { successor_block_info->block = new_bb; found = true; @@ -2344,28 +2289,20 @@ bool BasicBlock::ReplaceChild(BasicBlockId old_bb, BasicBlockId new_bb) { return found; } -void BasicBlock::UpdatePredecessor(BasicBlockId old_parent, BasicBlockId new_parent) { - GrowableArray<BasicBlockId>::Iterator iterator(predecessors); - bool found = false; - - while (true) { - BasicBlockId pred_bb_id = iterator.Next(); - - if (pred_bb_id == NullBasicBlockId) { - break; - } - - if (pred_bb_id == old_parent) { - size_t idx = iterator.GetIndex() - 1; - predecessors->Put(idx, new_parent); - found = true; - break; - } - } +void BasicBlock::ErasePredecessor(BasicBlockId old_pred) { + auto pos = std::find(predecessors.begin(), predecessors.end(), old_pred); + DCHECK(pos != predecessors.end()); + predecessors.erase(pos); +} - // If not found, add it. - if (found == false) { - predecessors->Insert(new_parent); +void BasicBlock::UpdatePredecessor(BasicBlockId old_pred, BasicBlockId new_pred) { + DCHECK_NE(new_pred, NullBasicBlockId); + auto pos = std::find(predecessors.begin(), predecessors.end(), old_pred); + if (pos != predecessors.end()) { + *pos = new_pred; + } else { + // If not found, add it. + predecessors.push_back(new_pred); } } @@ -2373,7 +2310,7 @@ void BasicBlock::UpdatePredecessor(BasicBlockId old_parent, BasicBlockId new_par // post-incremented. BasicBlock* MIRGraph::CreateNewBB(BBType block_type) { BasicBlock* res = NewMemBB(block_type, num_blocks_++); - block_list_.Insert(res); + block_list_.push_back(res); return res; } @@ -2383,7 +2320,7 @@ void MIRGraph::CalculateBasicBlockInformation() { } void MIRGraph::InitializeBasicBlockData() { - num_blocks_ = block_list_.Size(); + num_blocks_ = block_list_.size(); } int MIR::DecodedInstruction::FlagsOf() const { |