diff options
27 files changed, 331 insertions, 312 deletions
diff --git a/compiler/dex/global_value_numbering_test.cc b/compiler/dex/global_value_numbering_test.cc index f2c2e22d6a..c8aa9902c3 100644 --- a/compiler/dex/global_value_numbering_test.cc +++ b/compiler/dex/global_value_numbering_test.cc @@ -202,7 +202,7 @@ class GlobalValueNumberingTest : public testing::Test { for (size_t j = 0u; j != def->num_successors; ++j) { SuccessorBlockInfo* successor_block_info = static_cast<SuccessorBlockInfo*>(cu_.arena.Alloc(sizeof(SuccessorBlockInfo), - kArenaAllocSuccessors)); + kArenaAllocSuccessor)); successor_block_info->block = j; successor_block_info->key = 0u; // Not used by class init check elimination. bb->successor_blocks.push_back(successor_block_info); @@ -474,7 +474,7 @@ GlobalValueNumberingTestCatch::GlobalValueNumberingTestCatch() BasicBlock* check_bb = cu_.mir_graph->GetBasicBlock(3u); check_bb->successor_block_list_type = kCatch; SuccessorBlockInfo* successor_block_info = reinterpret_cast<SuccessorBlockInfo*> - (cu_.arena.Alloc(sizeof(SuccessorBlockInfo), kArenaAllocSuccessors)); + (cu_.arena.Alloc(sizeof(SuccessorBlockInfo), kArenaAllocSuccessor)); successor_block_info->block = catch_handler->id; check_bb->successor_blocks.push_back(successor_block_info); } @@ -2284,7 +2284,7 @@ TEST_F(GlobalValueNumberingTest, NormalPathToCatchEntry) { BasicBlock* check_bb = cu_.mir_graph->GetBasicBlock(3u); check_bb->successor_block_list_type = kCatch; SuccessorBlockInfo* successor_block_info = reinterpret_cast<SuccessorBlockInfo*> - (cu_.arena.Alloc(sizeof(SuccessorBlockInfo), kArenaAllocSuccessors)); + (cu_.arena.Alloc(sizeof(SuccessorBlockInfo), kArenaAllocSuccessor)); successor_block_info->block = catch_handler->id; check_bb->successor_blocks.push_back(successor_block_info); BasicBlock* merge_block = cu_.mir_graph->GetBasicBlock(4u); diff --git a/compiler/dex/gvn_dead_code_elimination_test.cc b/compiler/dex/gvn_dead_code_elimination_test.cc index 28c61a8fca..4df0a8b98d 100644 --- a/compiler/dex/gvn_dead_code_elimination_test.cc +++ b/compiler/dex/gvn_dead_code_elimination_test.cc @@ -209,7 +209,7 @@ class GvnDeadCodeEliminationTest : public testing::Test { for (size_t j = 0u; j != def->num_successors; ++j) { SuccessorBlockInfo* successor_block_info = static_cast<SuccessorBlockInfo*>(cu_.arena.Alloc(sizeof(SuccessorBlockInfo), - kArenaAllocSuccessors)); + kArenaAllocSuccessor)); successor_block_info->block = j; successor_block_info->key = 0u; // Not used by class init check elimination. bb->successor_blocks.push_back(successor_block_info); diff --git a/compiler/dex/mir_graph.cc b/compiler/dex/mir_graph.cc index 40600558ac..38342420ac 100644 --- a/compiler/dex/mir_graph.cc +++ b/compiler/dex/mir_graph.cc @@ -572,7 +572,7 @@ BasicBlock* MIRGraph::ProcessCanSwitch(BasicBlock* cur_block, MIR* insn, DexOffs DCHECK(case_block != nullptr); SuccessorBlockInfo* successor_block_info = static_cast<SuccessorBlockInfo*>(arena_->Alloc(sizeof(SuccessorBlockInfo), - kArenaAllocSuccessors)); + kArenaAllocSuccessor)); successor_block_info->block = case_block->id; successor_block_info->key = (insn->dalvikInsn.opcode == Instruction::PACKED_SWITCH) ? @@ -627,7 +627,7 @@ BasicBlock* MIRGraph::ProcessCanThrow(BasicBlock* cur_block, MIR* insn, DexOffse catches_.insert(catch_block->start_offset); } SuccessorBlockInfo* successor_block_info = reinterpret_cast<SuccessorBlockInfo*> - (arena_->Alloc(sizeof(SuccessorBlockInfo), kArenaAllocSuccessors)); + (arena_->Alloc(sizeof(SuccessorBlockInfo), kArenaAllocSuccessor)); successor_block_info->block = catch_block->id; successor_block_info->key = iterator.GetHandlerTypeIndex(); cur_block->successor_blocks.push_back(successor_block_info); @@ -2177,7 +2177,7 @@ BasicBlock* BasicBlock::Copy(MIRGraph* mir_graph) { result_bb->successor_blocks.reserve(successor_blocks.size()); for (SuccessorBlockInfo* sbi_old : successor_blocks) { SuccessorBlockInfo* sbi_new = static_cast<SuccessorBlockInfo*>( - arena->Alloc(sizeof(SuccessorBlockInfo), kArenaAllocSuccessors)); + arena->Alloc(sizeof(SuccessorBlockInfo), kArenaAllocSuccessor)); memcpy(sbi_new, sbi_old, sizeof(SuccessorBlockInfo)); result_bb->successor_blocks.push_back(sbi_new); } diff --git a/compiler/dex/mir_graph.h b/compiler/dex/mir_graph.h index 29f772d267..bcfd4405cb 100644 --- a/compiler/dex/mir_graph.h +++ b/compiler/dex/mir_graph.h @@ -379,7 +379,7 @@ class BasicBlock : public DeletableArenaObject<kArenaAllocBasicBlock> { terminated_by_return(), dominates_return(), use_lvn(), first_mir_insn(), last_mir_insn(), data_flow_info(), dominators(), i_dominated(), dom_frontier(), predecessors(allocator->Adapter(kArenaAllocBBPredecessors)), - successor_blocks(allocator->Adapter(kArenaAllocSuccessors)) { + successor_blocks(allocator->Adapter(kArenaAllocSuccessor)) { } BasicBlockId id; BasicBlockId dfs_id; diff --git a/compiler/dex/mir_graph_test.cc b/compiler/dex/mir_graph_test.cc index 7858681e00..49b7511b42 100644 --- a/compiler/dex/mir_graph_test.cc +++ b/compiler/dex/mir_graph_test.cc @@ -79,7 +79,7 @@ class TopologicalSortOrderTest : public testing::Test { for (size_t j = 0u; j != def->num_successors; ++j) { SuccessorBlockInfo* successor_block_info = static_cast<SuccessorBlockInfo*>(cu_.arena.Alloc(sizeof(SuccessorBlockInfo), - kArenaAllocSuccessors)); + kArenaAllocSuccessor)); successor_block_info->block = j; successor_block_info->key = 0u; // Not used by class init check elimination. bb->successor_blocks.push_back(successor_block_info); diff --git a/compiler/dex/mir_optimization_test.cc b/compiler/dex/mir_optimization_test.cc index a0cedff9b8..47123ba28c 100644 --- a/compiler/dex/mir_optimization_test.cc +++ b/compiler/dex/mir_optimization_test.cc @@ -118,7 +118,7 @@ class MirOptimizationTest : public testing::Test { for (size_t j = 0u; j != def->num_successors; ++j) { SuccessorBlockInfo* successor_block_info = static_cast<SuccessorBlockInfo*>(cu_.arena.Alloc(sizeof(SuccessorBlockInfo), - kArenaAllocSuccessors)); + kArenaAllocSuccessor)); successor_block_info->block = j; successor_block_info->key = 0u; // Not used by class init check elimination. bb->successor_blocks.push_back(successor_block_info); @@ -244,7 +244,7 @@ class MirOptimizationTest : public testing::Test { BasicBlock* check_bb = cu_.mir_graph->GetBasicBlock(3u); check_bb->successor_block_list_type = kCatch; SuccessorBlockInfo* successor_block_info = reinterpret_cast<SuccessorBlockInfo*> - (cu_.arena.Alloc(sizeof(SuccessorBlockInfo), kArenaAllocSuccessors)); + (cu_.arena.Alloc(sizeof(SuccessorBlockInfo), kArenaAllocSuccessor)); successor_block_info->block = catch_handler->id; check_bb->successor_blocks.push_back(successor_block_info); } diff --git a/compiler/dex/type_inference_test.cc b/compiler/dex/type_inference_test.cc index 669963cb03..eaa2bfac93 100644 --- a/compiler/dex/type_inference_test.cc +++ b/compiler/dex/type_inference_test.cc @@ -321,7 +321,7 @@ class TypeInferenceTest : public testing::Test { for (size_t j = 0u; j != def->num_successors; ++j) { SuccessorBlockInfo* successor_block_info = static_cast<SuccessorBlockInfo*>(cu_.arena.Alloc(sizeof(SuccessorBlockInfo), - kArenaAllocSuccessors)); + kArenaAllocSuccessor)); successor_block_info->block = j; successor_block_info->key = 0u; // Not used by class init check elimination. bb->successor_blocks.push_back(successor_block_info); diff --git a/compiler/optimizing/boolean_simplifier.cc b/compiler/optimizing/boolean_simplifier.cc index b0e83b0058..84201c39a7 100644 --- a/compiler/optimizing/boolean_simplifier.cc +++ b/compiler/optimizing/boolean_simplifier.cc @@ -42,9 +42,9 @@ void HBooleanSimplifier::TryRemovingNegatedCondition(HBasicBlock* block) { // successor and the successor can only be reached from them. static bool BlocksDoMergeTogether(HBasicBlock* block1, HBasicBlock* block2) { if (!block1->IsSingleGoto() || !block2->IsSingleGoto()) return false; - HBasicBlock* succ1 = block1->GetSuccessor(0); - HBasicBlock* succ2 = block2->GetSuccessor(0); - return succ1 == succ2 && succ1->GetPredecessors().size() == 2u; + HBasicBlock* succ1 = block1->GetSuccessors().Get(0); + HBasicBlock* succ2 = block2->GetSuccessors().Get(0); + return succ1 == succ2 && succ1->GetPredecessors().Size() == 2u; } // Returns true if the outcome of the branching matches the boolean value of @@ -108,7 +108,7 @@ void HBooleanSimplifier::TryRemovingBooleanSelection(HBasicBlock* block) { if (!BlocksDoMergeTogether(true_block, false_block)) { return; } - HBasicBlock* merge_block = true_block->GetSuccessor(0); + HBasicBlock* merge_block = true_block->GetSuccessors().Get(0); if (!merge_block->HasSinglePhi()) { return; } diff --git a/compiler/optimizing/bounds_check_elimination.cc b/compiler/optimizing/bounds_check_elimination.cc index 70ad408fdf..ebc0adc64a 100644 --- a/compiler/optimizing/bounds_check_elimination.cc +++ b/compiler/optimizing/bounds_check_elimination.cc @@ -275,8 +275,9 @@ class ArrayAccessInsideLoopFinder : public ValueObject { // Loop header of loop_info. Exiting loop is normal. return false; } - for (HBasicBlock* successor : block->GetSuccessors()) { - if (!loop_info->Contains(*successor)) { + const GrowableArray<HBasicBlock*>& successors = block->GetSuccessors(); + for (size_t i = 0; i < successors.Size(); i++) { + if (!loop_info->Contains(*successors.Get(i))) { // One of the successors exits the loop. return true; } @@ -796,8 +797,8 @@ class MonotonicValueRange : public ValueRange { HBasicBlock* new_pre_header = header->GetDominator(); DCHECK(new_pre_header == header->GetLoopInformation()->GetPreHeader()); HBasicBlock* if_block = new_pre_header->GetDominator(); - HBasicBlock* dummy_block = if_block->GetSuccessor(0); // True successor. - HBasicBlock* deopt_block = if_block->GetSuccessor(1); // False successor. + HBasicBlock* dummy_block = if_block->GetSuccessors().Get(0); // True successor. + HBasicBlock* deopt_block = if_block->GetSuccessors().Get(1); // False successor. dummy_block->AddInstruction(new (graph->GetArena()) HGoto()); deopt_block->AddInstruction(new (graph->GetArena()) HGoto()); @@ -844,14 +845,14 @@ class MonotonicValueRange : public ValueRange { DCHECK(header->IsLoopHeader()); HBasicBlock* pre_header = header->GetDominator(); if (loop_entry_test_block_added) { - DCHECK(deopt_block->GetSuccessor(0) == pre_header); + DCHECK(deopt_block->GetSuccessors().Get(0) == pre_header); } else { DCHECK(deopt_block == pre_header); } HGraph* graph = header->GetGraph(); HSuspendCheck* suspend_check = header->GetLoopInformation()->GetSuspendCheck(); if (loop_entry_test_block_added) { - DCHECK_EQ(deopt_block, header->GetDominator()->GetDominator()->GetSuccessor(1)); + DCHECK_EQ(deopt_block, header->GetDominator()->GetDominator()->GetSuccessors().Get(1)); } HIntConstant* const_instr = graph->GetIntConstant(constant); @@ -925,7 +926,7 @@ class MonotonicValueRange : public ValueRange { DCHECK(header->IsLoopHeader()); HBasicBlock* pre_header = header->GetDominator(); if (loop_entry_test_block_added) { - DCHECK(deopt_block->GetSuccessor(0) == pre_header); + DCHECK(deopt_block->GetSuccessors().Get(0) == pre_header); } else { DCHECK(deopt_block == pre_header); } @@ -1255,11 +1256,11 @@ class BCEVisitor : public HGraphVisitor { HBasicBlock* true_successor = instruction->IfTrueSuccessor(); // There should be no critical edge at this point. - DCHECK_EQ(true_successor->GetPredecessors().size(), 1u); + DCHECK_EQ(true_successor->GetPredecessors().Size(), 1u); HBasicBlock* false_successor = instruction->IfFalseSuccessor(); // There should be no critical edge at this point. - DCHECK_EQ(false_successor->GetPredecessors().size(), 1u); + DCHECK_EQ(false_successor->GetPredecessors().Size(), 1u); ValueRange* left_range = LookupValueRange(left, block); MonotonicValueRange* left_monotonic_range = nullptr; @@ -1467,10 +1468,10 @@ class BCEVisitor : public HGraphVisitor { // Start with input 1. Input 0 is from the incoming block. HInstruction* input1 = phi->InputAt(1); DCHECK(phi->GetBlock()->GetLoopInformation()->IsBackEdge( - *phi->GetBlock()->GetPredecessor(1))); + *phi->GetBlock()->GetPredecessors().Get(1))); for (size_t i = 2, e = phi->InputCount(); i < e; ++i) { DCHECK(phi->GetBlock()->GetLoopInformation()->IsBackEdge( - *phi->GetBlock()->GetPredecessor(i))); + *phi->GetBlock()->GetPredecessors().Get(i))); if (input1 != phi->InputAt(i)) { return false; } diff --git a/compiler/optimizing/builder.cc b/compiler/optimizing/builder.cc index 4a9dcdf001..23ab94e5fe 100644 --- a/compiler/optimizing/builder.cc +++ b/compiler/optimizing/builder.cc @@ -396,8 +396,8 @@ void HGraphBuilder::InsertTryBoundaryBlocks(const DexFile::CodeItem& code_item) // Find predecessors which are not covered by the same TryItem range. Such // edges enter the try block and will have a TryBoundary inserted. - for (size_t i = 0; i < try_block->GetPredecessors().size(); ++i) { - HBasicBlock* predecessor = try_block->GetPredecessor(i); + for (size_t i = 0; i < try_block->GetPredecessors().Size(); ++i) { + HBasicBlock* predecessor = try_block->GetPredecessors().Get(i); if (predecessor->IsSingleTryBoundary()) { // The edge was already split because of an exit from a neighbouring // TryItem. We split it again and insert an entry point. @@ -424,7 +424,8 @@ void HGraphBuilder::InsertTryBoundaryBlocks(const DexFile::CodeItem& code_item) // Find successors which are not covered by the same TryItem range. Such // edges exit the try block and will have a TryBoundary inserted. - for (HBasicBlock* successor : try_block->GetSuccessors()) { + for (size_t i = 0; i < try_block->GetSuccessors().Size(); ++i) { + HBasicBlock* successor = try_block->GetSuccessors().Get(i); if (successor->IsCatchBlock()) { // A catch block is always considered an entry point into its TryItem. // We therefore assume this is an exit point, regardless of whether diff --git a/compiler/optimizing/code_generator.cc b/compiler/optimizing/code_generator.cc index bb780dc2bd..3f69270f17 100644 --- a/compiler/optimizing/code_generator.cc +++ b/compiler/optimizing/code_generator.cc @@ -171,7 +171,7 @@ HBasicBlock* CodeGenerator::GetNextBlockToEmit() const { HBasicBlock* CodeGenerator::FirstNonEmptyBlock(HBasicBlock* block) const { while (block->IsSingleJump()) { - block = block->GetSuccessor(0); + block = block->GetSuccessors().Get(0); } return block; } diff --git a/compiler/optimizing/codegen_test.cc b/compiler/optimizing/codegen_test.cc index 72c67f5651..4fbb51d43c 100644 --- a/compiler/optimizing/codegen_test.cc +++ b/compiler/optimizing/codegen_test.cc @@ -561,7 +561,7 @@ TEST(CodegenTest, NonMaterializedCondition) { ASSERT_FALSE(equal->NeedsMaterialization()); auto hook_before_codegen = [](HGraph* graph_in) { - HBasicBlock* block = graph_in->GetEntryBlock()->GetSuccessor(0); + HBasicBlock* block = graph_in->GetEntryBlock()->GetSuccessors().Get(0); HParallelMove* move = new (graph_in->GetArena()) HParallelMove(graph_in->GetArena()); block->InsertInstructionBefore(move, block->GetLastInstruction()); }; @@ -667,7 +667,7 @@ TEST(CodegenTest, MaterializedCondition1) { code_block->AddInstruction(&ret); auto hook_before_codegen = [](HGraph* graph_in) { - HBasicBlock* block = graph_in->GetEntryBlock()->GetSuccessor(0); + HBasicBlock* block = graph_in->GetEntryBlock()->GetSuccessors().Get(0); HParallelMove* move = new (graph_in->GetArena()) HParallelMove(graph_in->GetArena()); block->InsertInstructionBefore(move, block->GetLastInstruction()); }; @@ -733,7 +733,7 @@ TEST(CodegenTest, MaterializedCondition2) { if_false_block->AddInstruction(&ret_ge); auto hook_before_codegen = [](HGraph* graph_in) { - HBasicBlock* block = graph_in->GetEntryBlock()->GetSuccessor(0); + HBasicBlock* block = graph_in->GetEntryBlock()->GetSuccessors().Get(0); HParallelMove* move = new (graph_in->GetArena()) HParallelMove(graph_in->GetArena()); block->InsertInstructionBefore(move, block->GetLastInstruction()); }; diff --git a/compiler/optimizing/dead_code_elimination.cc b/compiler/optimizing/dead_code_elimination.cc index 509478cfad..50cbf5ca77 100644 --- a/compiler/optimizing/dead_code_elimination.cc +++ b/compiler/optimizing/dead_code_elimination.cc @@ -42,8 +42,8 @@ static void MarkReachableBlocks(HBasicBlock* block, ArenaBitVector* visited) { MarkReachableBlocks(if_instruction->IfFalseSuccessor(), visited); } } else { - for (HBasicBlock* successor : block->GetSuccessors()) { - MarkReachableBlocks(successor, visited); + for (size_t i = 0, e = block->GetSuccessors().Size(); i < e; ++i) { + MarkReachableBlocks(block->GetSuccessors().Get(i), visited); } } } @@ -99,12 +99,12 @@ void HDeadCodeElimination::RemoveDeadBlocks() { // Connect successive blocks created by dead branches. Order does not matter. for (HReversePostOrderIterator it(*graph_); !it.Done();) { HBasicBlock* block = it.Current(); - if (block->IsEntryBlock() || block->GetSuccessors().size() != 1u) { + if (block->IsEntryBlock() || block->GetSuccessors().Size() != 1u) { it.Advance(); continue; } - HBasicBlock* successor = block->GetSuccessor(0); - if (successor->IsExitBlock() || successor->GetPredecessors().size() != 1u) { + HBasicBlock* successor = block->GetSuccessors().Get(0); + if (successor->IsExitBlock() || successor->GetPredecessors().Size() != 1u) { it.Advance(); continue; } diff --git a/compiler/optimizing/graph_checker.cc b/compiler/optimizing/graph_checker.cc index 3e358358ae..847d5a4e9e 100644 --- a/compiler/optimizing/graph_checker.cc +++ b/compiler/optimizing/graph_checker.cc @@ -29,16 +29,19 @@ void GraphChecker::VisitBasicBlock(HBasicBlock* block) { current_block_ = block; // Check consistency with respect to predecessors of `block`. + const GrowableArray<HBasicBlock*>& predecessors = block->GetPredecessors(); std::map<HBasicBlock*, size_t> predecessors_count; - for (HBasicBlock* p : block->GetPredecessors()) { + for (size_t i = 0, e = predecessors.Size(); i < e; ++i) { + HBasicBlock* p = predecessors.Get(i); ++predecessors_count[p]; } for (auto& pc : predecessors_count) { HBasicBlock* p = pc.first; size_t p_count_in_block_predecessors = pc.second; + const GrowableArray<HBasicBlock*>& p_successors = p->GetSuccessors(); size_t block_count_in_p_successors = 0; - for (HBasicBlock* p_successor : p->GetSuccessors()) { - if (p_successor == block) { + for (size_t j = 0, f = p_successors.Size(); j < f; ++j) { + if (p_successors.Get(j) == block) { ++block_count_in_p_successors; } } @@ -52,16 +55,19 @@ void GraphChecker::VisitBasicBlock(HBasicBlock* block) { } // Check consistency with respect to successors of `block`. + const GrowableArray<HBasicBlock*>& successors = block->GetSuccessors(); std::map<HBasicBlock*, size_t> successors_count; - for (HBasicBlock* s : block->GetSuccessors()) { + for (size_t i = 0, e = successors.Size(); i < e; ++i) { + HBasicBlock* s = successors.Get(i); ++successors_count[s]; } for (auto& sc : successors_count) { HBasicBlock* s = sc.first; size_t s_count_in_block_successors = sc.second; + const GrowableArray<HBasicBlock*>& s_predecessors = s->GetPredecessors(); size_t block_count_in_s_predecessors = 0; - for (HBasicBlock* s_predecessor : s->GetPredecessors()) { - if (s_predecessor == block) { + for (size_t j = 0, f = s_predecessors.Size(); j < f; ++j) { + if (s_predecessors.Get(j) == block) { ++block_count_in_s_predecessors; } } @@ -86,7 +92,8 @@ void GraphChecker::VisitBasicBlock(HBasicBlock* block) { // Ensure that only Return(Void) and Throw jump to Exit. An exiting // TryBoundary may be between a Throw and the Exit if the Throw is in a try. if (block->IsExitBlock()) { - for (HBasicBlock* predecessor : block->GetPredecessors()) { + for (size_t i = 0, e = block->GetPredecessors().Size(); i < e; ++i) { + HBasicBlock* predecessor = block->GetPredecessors().Get(i); if (predecessor->IsSingleTryBoundary() && !predecessor->GetLastInstruction()->AsTryBoundary()->IsEntry()) { HBasicBlock* real_predecessor = predecessor->GetSinglePredecessor(); @@ -171,7 +178,8 @@ void GraphChecker::VisitTryBoundary(HTryBoundary* try_boundary) { try_boundary->GetId(), handler->GetBlockId())); } - if (current_block_->HasSuccessor(handler, it.CurrentSuccessorIndex() + 1)) { + if (current_block_->GetSuccessors().Contains( + handler, /* start_from */ it.CurrentSuccessorIndex() + 1)) { AddError(StringPrintf("Exception handler block %d of %s:%d is listed multiple times.", handler->GetBlockId(), try_boundary->DebugName(), @@ -351,15 +359,15 @@ void SSAChecker::VisitBasicBlock(HBasicBlock* block) { // never exceptional successors. const size_t num_normal_successors = block->NumberOfNormalSuccessors(); for (size_t j = 0; j < num_normal_successors; ++j) { - HBasicBlock* successor = block->GetSuccessor(j); + HBasicBlock* successor = block->GetSuccessors().Get(j); if (successor->IsCatchBlock()) { AddError(StringPrintf("Catch block %d is a normal successor of block %d.", successor->GetBlockId(), block->GetBlockId())); } } - for (size_t j = num_normal_successors, e = block->GetSuccessors().size(); j < e; ++j) { - HBasicBlock* successor = block->GetSuccessor(j); + for (size_t j = num_normal_successors, e = block->GetSuccessors().Size(); j < e; ++j) { + HBasicBlock* successor = block->GetSuccessors().Get(j); if (!successor->IsCatchBlock()) { AddError(StringPrintf("Normal block %d is an exceptional successor of block %d.", successor->GetBlockId(), @@ -373,8 +381,8 @@ void SSAChecker::VisitBasicBlock(HBasicBlock* block) { // not accounted for. if (block->NumberOfNormalSuccessors() > 1) { for (size_t j = 0, e = block->NumberOfNormalSuccessors(); j < e; ++j) { - HBasicBlock* successor = block->GetSuccessor(j); - if (successor->GetPredecessors().size() > 1) { + HBasicBlock* successor = block->GetSuccessors().Get(j); + if (successor->GetPredecessors().Size() > 1) { AddError(StringPrintf("Critical edge between blocks %d and %d.", block->GetBlockId(), successor->GetBlockId())); @@ -409,7 +417,8 @@ void SSAChecker::VisitBasicBlock(HBasicBlock* block) { block->GetBlockId())); } } else { - for (HBasicBlock* predecessor : block->GetPredecessors()) { + for (size_t i = 0; i < block->GetPredecessors().Size(); ++i) { + HBasicBlock* predecessor = block->GetPredecessors().Get(i); const HTryBoundary* incoming_try_entry = predecessor->ComputeTryEntryOfSuccessors(); if (block->IsTryBlock()) { const HTryBoundary& stored_try_entry = block->GetTryCatchInformation()->GetTryEntry(); @@ -460,21 +469,21 @@ void SSAChecker::CheckLoop(HBasicBlock* loop_header) { // Ensure the loop header has only one incoming branch and the remaining // predecessors are back edges. - size_t num_preds = loop_header->GetPredecessors().size(); + size_t num_preds = loop_header->GetPredecessors().Size(); if (num_preds < 2) { AddError(StringPrintf( "Loop header %d has less than two predecessors: %zu.", id, num_preds)); } else { - HBasicBlock* first_predecessor = loop_header->GetPredecessor(0); + HBasicBlock* first_predecessor = loop_header->GetPredecessors().Get(0); if (loop_information->IsBackEdge(*first_predecessor)) { AddError(StringPrintf( "First predecessor of loop header %d is a back edge.", id)); } - for (size_t i = 1, e = loop_header->GetPredecessors().size(); i < e; ++i) { - HBasicBlock* predecessor = loop_header->GetPredecessor(i); + for (size_t i = 1, e = loop_header->GetPredecessors().Size(); i < e; ++i) { + HBasicBlock* predecessor = loop_header->GetPredecessors().Get(i); if (!loop_information->IsBackEdge(*predecessor)) { AddError(StringPrintf( "Loop header %d has multiple incoming (non back edge) blocks.", @@ -612,19 +621,20 @@ void SSAChecker::VisitPhi(HPhi* phi) { } else { // Ensure the number of inputs of a non-catch phi is the same as the number // of its predecessors. - const ArenaVector<HBasicBlock*>& predecessors = phi->GetBlock()->GetPredecessors(); - if (phi->InputCount() != predecessors.size()) { + const GrowableArray<HBasicBlock*>& predecessors = + phi->GetBlock()->GetPredecessors(); + if (phi->InputCount() != predecessors.Size()) { AddError(StringPrintf( "Phi %d in block %d has %zu inputs, " "but block %d has %zu predecessors.", phi->GetId(), phi->GetBlock()->GetBlockId(), phi->InputCount(), - phi->GetBlock()->GetBlockId(), predecessors.size())); + phi->GetBlock()->GetBlockId(), predecessors.Size())); } else { // Ensure phi input at index I either comes from the Ith // predecessor or from a block that dominates this predecessor. for (size_t i = 0, e = phi->InputCount(); i < e; ++i) { HInstruction* input = phi->InputAt(i); - HBasicBlock* predecessor = predecessors[i]; + HBasicBlock* predecessor = predecessors.Get(i); if (!(input->GetBlock() == predecessor || input->GetBlock()->Dominates(predecessor))) { AddError(StringPrintf( diff --git a/compiler/optimizing/graph_test.cc b/compiler/optimizing/graph_test.cc index 7968e88117..59d50926ad 100644 --- a/compiler/optimizing/graph_test.cc +++ b/compiler/optimizing/graph_test.cc @@ -99,7 +99,7 @@ TEST(GraphTest, IfSuccessorSimpleJoinBlock1) { ASSERT_NE(false_block, return_block); // Ensure the new block branches to the join block. - ASSERT_EQ(false_block->GetSuccessor(0), return_block); + ASSERT_EQ(false_block->GetSuccessors().Get(0), return_block); } // Test that the successors of an if block stay consistent after a SimplifyCFG. @@ -134,7 +134,7 @@ TEST(GraphTest, IfSuccessorSimpleJoinBlock2) { ASSERT_NE(true_block, return_block); // Ensure the new block branches to the join block. - ASSERT_EQ(true_block->GetSuccessor(0), return_block); + ASSERT_EQ(true_block->GetSuccessors().Get(0), return_block); } // Test that the successors of an if block stay consistent after a SimplifyCFG. @@ -163,12 +163,12 @@ TEST(GraphTest, IfSuccessorMultipleBackEdges1) { ASSERT_EQ(if_block->GetLastInstruction()->AsIf()->IfFalseSuccessor(), return_block); // Ensure there is only one back edge. - ASSERT_EQ(if_block->GetPredecessors().size(), 2u); - ASSERT_EQ(if_block->GetPredecessor(0), entry_block); - ASSERT_NE(if_block->GetPredecessor(1), if_block); + ASSERT_EQ(if_block->GetPredecessors().Size(), 2u); + ASSERT_EQ(if_block->GetPredecessors().Get(0), entry_block); + ASSERT_NE(if_block->GetPredecessors().Get(1), if_block); // Ensure the new block is the back edge. - ASSERT_EQ(if_block->GetPredecessor(1), + ASSERT_EQ(if_block->GetPredecessors().Get(1), if_block->GetLastInstruction()->AsIf()->IfTrueSuccessor()); } @@ -198,12 +198,12 @@ TEST(GraphTest, IfSuccessorMultipleBackEdges2) { ASSERT_EQ(if_block->GetLastInstruction()->AsIf()->IfTrueSuccessor(), return_block); // Ensure there is only one back edge. - ASSERT_EQ(if_block->GetPredecessors().size(), 2u); - ASSERT_EQ(if_block->GetPredecessor(0), entry_block); - ASSERT_NE(if_block->GetPredecessor(1), if_block); + ASSERT_EQ(if_block->GetPredecessors().Size(), 2u); + ASSERT_EQ(if_block->GetPredecessors().Get(0), entry_block); + ASSERT_NE(if_block->GetPredecessors().Get(1), if_block); // Ensure the new block is the back edge. - ASSERT_EQ(if_block->GetPredecessor(1), + ASSERT_EQ(if_block->GetPredecessors().Get(1), if_block->GetLastInstruction()->AsIf()->IfFalseSuccessor()); } @@ -238,11 +238,11 @@ TEST(GraphTest, IfSuccessorMultiplePreHeaders1) { ASSERT_EQ(if_instr->IfFalseSuccessor(), return_block); // Ensure there is only one pre header.. - ASSERT_EQ(loop_block->GetPredecessors().size(), 2u); + ASSERT_EQ(loop_block->GetPredecessors().Size(), 2u); // Ensure the new block is the successor of the true block. - ASSERT_EQ(if_instr->IfTrueSuccessor()->GetSuccessors().size(), 1u); - ASSERT_EQ(if_instr->IfTrueSuccessor()->GetSuccessor(0), + ASSERT_EQ(if_instr->IfTrueSuccessor()->GetSuccessors().Size(), 1u); + ASSERT_EQ(if_instr->IfTrueSuccessor()->GetSuccessors().Get(0), loop_block->GetLoopInformation()->GetPreHeader()); } @@ -276,11 +276,11 @@ TEST(GraphTest, IfSuccessorMultiplePreHeaders2) { ASSERT_EQ(if_instr->IfTrueSuccessor(), return_block); // Ensure there is only one pre header.. - ASSERT_EQ(loop_block->GetPredecessors().size(), 2u); + ASSERT_EQ(loop_block->GetPredecessors().Size(), 2u); // Ensure the new block is the successor of the false block. - ASSERT_EQ(if_instr->IfFalseSuccessor()->GetSuccessors().size(), 1u); - ASSERT_EQ(if_instr->IfFalseSuccessor()->GetSuccessor(0), + ASSERT_EQ(if_instr->IfFalseSuccessor()->GetSuccessors().Size(), 1u); + ASSERT_EQ(if_instr->IfFalseSuccessor()->GetSuccessors().Get(0), loop_block->GetLoopInformation()->GetPreHeader()); } diff --git a/compiler/optimizing/graph_visualizer.cc b/compiler/optimizing/graph_visualizer.cc index 5b8e386fae..069a7a460b 100644 --- a/compiler/optimizing/graph_visualizer.cc +++ b/compiler/optimizing/graph_visualizer.cc @@ -240,7 +240,8 @@ class HGraphVisualizerPrinter : public HGraphDelegateVisitor { void PrintPredecessors(HBasicBlock* block) { AddIndent(); output_ << "predecessors"; - for (HBasicBlock* predecessor : block->GetPredecessors()) { + for (size_t i = 0, e = block->GetPredecessors().Size(); i < e; ++i) { + HBasicBlock* predecessor = block->GetPredecessors().Get(i); output_ << " \"B" << predecessor->GetBlockId() << "\" "; } if (block->IsEntryBlock() && (disasm_info_ != nullptr)) { @@ -253,7 +254,7 @@ class HGraphVisualizerPrinter : public HGraphDelegateVisitor { AddIndent(); output_ << "successors"; for (size_t i = 0; i < block->NumberOfNormalSuccessors(); ++i) { - HBasicBlock* successor = block->GetSuccessor(i); + HBasicBlock* successor = block->GetSuccessors().Get(i); output_ << " \"B" << successor->GetBlockId() << "\" "; } output_<< std::endl; @@ -262,8 +263,8 @@ class HGraphVisualizerPrinter : public HGraphDelegateVisitor { void PrintExceptionHandlers(HBasicBlock* block) { AddIndent(); output_ << "xhandlers"; - for (size_t i = block->NumberOfNormalSuccessors(); i < block->GetSuccessors().size(); ++i) { - HBasicBlock* handler = block->GetSuccessor(i); + for (size_t i = block->NumberOfNormalSuccessors(); i < block->GetSuccessors().Size(); ++i) { + HBasicBlock* handler = block->GetSuccessors().Get(i); output_ << " \"B" << handler->GetBlockId() << "\" "; } if (block->IsExitBlock() && diff --git a/compiler/optimizing/gvn.cc b/compiler/optimizing/gvn.cc index 5bb4e8e099..833dfb00a1 100644 --- a/compiler/optimizing/gvn.cc +++ b/compiler/optimizing/gvn.cc @@ -340,8 +340,8 @@ void GlobalValueNumberer::Run() { void GlobalValueNumberer::VisitBasicBlock(HBasicBlock* block) { ValueSet* set = nullptr; - const ArenaVector<HBasicBlock*>& predecessors = block->GetPredecessors(); - if (predecessors.size() == 0 || predecessors[0]->IsEntryBlock()) { + const GrowableArray<HBasicBlock*>& predecessors = block->GetPredecessors(); + if (predecessors.Size() == 0 || predecessors.Get(0)->IsEntryBlock()) { // The entry block should only accumulate constant instructions, and // the builder puts constants only in the entry block. // Therefore, there is no need to propagate the value set to the next block. @@ -349,8 +349,8 @@ void GlobalValueNumberer::VisitBasicBlock(HBasicBlock* block) { } else { HBasicBlock* dominator = block->GetDominator(); ValueSet* dominator_set = sets_.Get(dominator->GetBlockId()); - if (dominator->GetSuccessors().size() == 1) { - DCHECK_EQ(dominator->GetSuccessor(0), block); + if (dominator->GetSuccessors().Size() == 1) { + DCHECK_EQ(dominator->GetSuccessors().Get(0), block); set = dominator_set; } else { // We have to copy if the dominator has other successors, or `block` is not a successor @@ -361,9 +361,9 @@ void GlobalValueNumberer::VisitBasicBlock(HBasicBlock* block) { if (block->IsLoopHeader()) { DCHECK_EQ(block->GetDominator(), block->GetLoopInformation()->GetPreHeader()); set->Kill(side_effects_.GetLoopEffects(block)); - } else if (predecessors.size() > 1) { - for (HBasicBlock* predecessor : predecessors) { - set->IntersectWith(sets_.Get(predecessor->GetBlockId())); + } else if (predecessors.Size() > 1) { + for (size_t i = 0, e = predecessors.Size(); i < e; ++i) { + set->IntersectWith(sets_.Get(predecessors.Get(i)->GetBlockId())); if (set->IsEmpty()) { break; } diff --git a/compiler/optimizing/inliner.cc b/compiler/optimizing/inliner.cc index 2c23d075d5..112d42e904 100644 --- a/compiler/optimizing/inliner.cc +++ b/compiler/optimizing/inliner.cc @@ -417,8 +417,8 @@ bool HInliner::TryBuildAndInline(ArtMethod* resolved_method, } bool has_throw_predecessor = false; - for (HBasicBlock* predecessor : exit_block->GetPredecessors()) { - if (predecessor->GetLastInstruction()->IsThrow()) { + for (size_t i = 0, e = exit_block->GetPredecessors().Size(); i < e; ++i) { + if (exit_block->GetPredecessors().Get(i)->GetLastInstruction()->IsThrow()) { has_throw_predecessor = true; break; } diff --git a/compiler/optimizing/nodes.cc b/compiler/optimizing/nodes.cc index 9444ff5f9f..4332d7ed02 100644 --- a/compiler/optimizing/nodes.cc +++ b/compiler/optimizing/nodes.cc @@ -68,8 +68,8 @@ void HGraph::RemoveDeadBlocks(const ArenaBitVector& visited) { if (!visited.IsBitSet(i)) { HBasicBlock* block = blocks_.Get(i); // We only need to update the successor, which might be live. - for (HBasicBlock* successor : block->GetSuccessors()) { - successor->RemovePredecessor(block); + for (size_t j = 0; j < block->GetSuccessors().Size(); ++j) { + block->GetSuccessors().Get(j)->RemovePredecessor(block); } // Remove the block from the list of blocks, so that further analyses // never see it. @@ -86,7 +86,8 @@ void HGraph::VisitBlockForBackEdges(HBasicBlock* block, visited->SetBit(id); visiting->SetBit(id); - for (HBasicBlock* successor : block->GetSuccessors()) { + for (size_t i = 0; i < block->GetSuccessors().Size(); i++) { + HBasicBlock* successor = block->GetSuccessors().Get(i); if (visiting->IsBitSet(successor->GetBlockId())) { successor->AddBackEdge(block); } else { @@ -133,7 +134,7 @@ void HGraph::ClearDominanceInformation() { } void HBasicBlock::ClearDominanceInformation() { - dominated_blocks_.clear(); + dominated_blocks_.Reset(); dominator_ = nullptr; } @@ -142,8 +143,8 @@ void HGraph::ComputeDominanceInformation() { GrowableArray<size_t> visits(arena_, blocks_.Size()); visits.SetSize(blocks_.Size()); reverse_post_order_.Add(entry_block_); - for (HBasicBlock* successor : entry_block_->GetSuccessors()) { - VisitBlockForDominatorTree(successor, entry_block_, &visits); + for (size_t i = 0; i < entry_block_->GetSuccessors().Size(); i++) { + VisitBlockForDominatorTree(entry_block_->GetSuccessors().Get(i), entry_block_, &visits); } } @@ -178,11 +179,11 @@ void HGraph::VisitBlockForDominatorTree(HBasicBlock* block, // Once all the forward edges have been visited, we know the immediate // dominator of the block. We can then start visiting its successors. if (visits->Get(block->GetBlockId()) == - block->GetPredecessors().size() - block->NumberOfBackEdges()) { + block->GetPredecessors().Size() - block->NumberOfBackEdges()) { block->GetDominator()->AddDominatedBlock(block); reverse_post_order_.Add(block); - for (HBasicBlock* successor : block->GetSuccessors()) { - VisitBlockForDominatorTree(successor, block, visits); + for (size_t i = 0; i < block->GetSuccessors().Size(); i++) { + VisitBlockForDominatorTree(block->GetSuccessors().Get(i), block, visits); } } } @@ -223,14 +224,14 @@ void HGraph::SimplifyLoop(HBasicBlock* header) { // Make sure the loop has only one pre header. This simplifies SSA building by having // to just look at the pre header to know which locals are initialized at entry of the // loop. - size_t number_of_incomings = header->GetPredecessors().size() - info->NumberOfBackEdges(); + size_t number_of_incomings = header->GetPredecessors().Size() - info->NumberOfBackEdges(); if (number_of_incomings != 1) { HBasicBlock* pre_header = new (arena_) HBasicBlock(this, header->GetDexPc()); AddBlock(pre_header); pre_header->AddInstruction(new (arena_) HGoto()); - for (size_t pred = 0; pred < header->GetPredecessors().size(); ++pred) { - HBasicBlock* predecessor = header->GetPredecessor(pred); + for (size_t pred = 0; pred < header->GetPredecessors().Size(); ++pred) { + HBasicBlock* predecessor = header->GetPredecessors().Get(pred); if (!info->IsBackEdge(*predecessor)) { predecessor->ReplaceSuccessor(header, pre_header); pred--; @@ -240,13 +241,13 @@ void HGraph::SimplifyLoop(HBasicBlock* header) { } // Make sure the first predecessor of a loop header is the incoming block. - if (info->IsBackEdge(*header->GetPredecessor(0))) { - HBasicBlock* to_swap = header->GetPredecessor(0); - for (size_t pred = 1, e = header->GetPredecessors().size(); pred < e; ++pred) { - HBasicBlock* predecessor = header->GetPredecessor(pred); + if (info->IsBackEdge(*header->GetPredecessors().Get(0))) { + HBasicBlock* to_swap = header->GetPredecessors().Get(0); + for (size_t pred = 1, e = header->GetPredecessors().Size(); pred < e; ++pred) { + HBasicBlock* predecessor = header->GetPredecessors().Get(pred); if (!info->IsBackEdge(*predecessor)) { - header->predecessors_[pred] = to_swap; - header->predecessors_[0] = predecessor; + header->predecessors_.Put(pred, to_swap); + header->predecessors_.Put(0, predecessor); break; } } @@ -266,7 +267,7 @@ void HGraph::SimplifyLoop(HBasicBlock* header) { } static bool CheckIfPredecessorAtIsExceptional(const HBasicBlock& block, size_t pred_idx) { - HBasicBlock* predecessor = block.GetPredecessor(pred_idx); + HBasicBlock* predecessor = block.GetPredecessors().Get(pred_idx); if (!predecessor->EndsWithTryBoundary()) { // Only edges from HTryBoundary can be exceptional. return false; @@ -295,7 +296,7 @@ void HGraph::SimplifyCatchBlocks() { } bool exceptional_predecessors_only = true; - for (size_t j = 0; j < catch_block->GetPredecessors().size(); ++j) { + for (size_t j = 0; j < catch_block->GetPredecessors().Size(); ++j) { if (!CheckIfPredecessorAtIsExceptional(*catch_block, j)) { exceptional_predecessors_only = false; break; @@ -312,9 +313,9 @@ void HGraph::SimplifyCatchBlocks() { // a MOVE_EXCEPTION instruction, as guaranteed by the verifier. DCHECK(!catch_block->GetFirstInstruction()->IsLoadException()); HBasicBlock* normal_block = catch_block->SplitBefore(catch_block->GetFirstInstruction()); - for (size_t j = 0; j < catch_block->GetPredecessors().size(); ++j) { + for (size_t j = 0; j < catch_block->GetPredecessors().Size(); ++j) { if (!CheckIfPredecessorAtIsExceptional(*catch_block, j)) { - catch_block->GetPredecessor(j)->ReplaceSuccessor(catch_block, normal_block); + catch_block->GetPredecessors().Get(j)->ReplaceSuccessor(catch_block, normal_block); --j; } } @@ -336,7 +337,7 @@ void HGraph::ComputeTryBlockInformation() { // Infer try membership from the first predecessor. Having simplified loops, // the first predecessor can never be a back edge and therefore it must have // been visited already and had its try membership set. - HBasicBlock* first_predecessor = block->GetPredecessor(0); + HBasicBlock* first_predecessor = block->GetPredecessors().Get(0); DCHECK(!block->IsLoopHeader() || !block->GetLoopInformation()->IsBackEdge(*first_predecessor)); const HTryBoundary* try_entry = first_predecessor->ComputeTryEntryOfSuccessors(); if (try_entry != nullptr) { @@ -363,10 +364,10 @@ void HGraph::SimplifyCFG() { HBasicBlock* block = blocks_.Get(i); if (block == nullptr) continue; if (block->NumberOfNormalSuccessors() > 1) { - for (size_t j = 0; j < block->GetSuccessors().size(); ++j) { - HBasicBlock* successor = block->GetSuccessor(j); + for (size_t j = 0; j < block->GetSuccessors().Size(); ++j) { + HBasicBlock* successor = block->GetSuccessors().Get(j); DCHECK(!successor->IsCatchBlock()); - if (successor->GetPredecessors().size() > 1) { + if (successor->GetPredecessors().Size() > 1) { SplitCriticalEdge(block, successor); --j; } @@ -484,8 +485,8 @@ void HLoopInformation::PopulateRecursive(HBasicBlock* block) { blocks_.SetBit(block->GetBlockId()); block->SetInLoop(this); - for (HBasicBlock* predecessor : block->GetPredecessors()) { - PopulateRecursive(predecessor); + for (size_t i = 0, e = block->GetPredecessors().Size(); i < e; ++i) { + PopulateRecursive(block->GetPredecessors().Get(i)); } } @@ -1135,11 +1136,12 @@ HBasicBlock* HBasicBlock::SplitBefore(HInstruction* cursor) { new_block->instructions_.SetBlockOfInstructions(new_block); AddInstruction(new (GetGraph()->GetArena()) HGoto()); - for (HBasicBlock* successor : GetSuccessors()) { - new_block->successors_.push_back(successor); - successor->predecessors_[successor->GetPredecessorIndexOf(this)] = new_block; + for (size_t i = 0, e = GetSuccessors().Size(); i < e; ++i) { + HBasicBlock* successor = GetSuccessors().Get(i); + new_block->successors_.Add(successor); + successor->predecessors_.Put(successor->GetPredecessorIndexOf(this), new_block); } - successors_.clear(); + successors_.Reset(); AddSuccessor(new_block); GetGraph()->AddBlock(new_block); @@ -1159,17 +1161,19 @@ HBasicBlock* HBasicBlock::SplitAfter(HInstruction* cursor) { instructions_.last_instruction_ = cursor; new_block->instructions_.SetBlockOfInstructions(new_block); - for (HBasicBlock* successor : GetSuccessors()) { - new_block->successors_.push_back(successor); - successor->predecessors_[successor->GetPredecessorIndexOf(this)] = new_block; + for (size_t i = 0, e = GetSuccessors().Size(); i < e; ++i) { + HBasicBlock* successor = GetSuccessors().Get(i); + new_block->successors_.Add(successor); + successor->predecessors_.Put(successor->GetPredecessorIndexOf(this), new_block); } - successors_.clear(); + successors_.Reset(); - for (HBasicBlock* dominated : GetDominatedBlocks()) { + for (size_t i = 0, e = GetDominatedBlocks().Size(); i < e; ++i) { + HBasicBlock* dominated = GetDominatedBlocks().Get(i); dominated->dominator_ = new_block; - new_block->dominated_blocks_.push_back(dominated); + new_block->dominated_blocks_.Add(dominated); } - dominated_blocks_.clear(); + dominated_blocks_.Reset(); return new_block; } @@ -1222,7 +1226,7 @@ bool HBasicBlock::HasSinglePhi() const { } bool HTryBoundary::HasSameExceptionHandlersAs(const HTryBoundary& other) const { - if (GetBlock()->GetSuccessors().size() != other.GetBlock()->GetSuccessors().size()) { + if (GetBlock()->GetSuccessors().Size() != other.GetBlock()->GetSuccessors().Size()) { return false; } @@ -1282,7 +1286,7 @@ void HBasicBlock::DisconnectAndDelete() { // Dominators must be removed after all the blocks they dominate. This way // a loop header is removed last, a requirement for correct loop information // iteration. - DCHECK(dominated_blocks_.empty()); + DCHECK(dominated_blocks_.IsEmpty()); // Remove the block from all loops it is included in. for (HLoopInformationOutwardIterator it(*this); !it.Done(); it.Advance()) { @@ -1298,34 +1302,36 @@ void HBasicBlock::DisconnectAndDelete() { // Disconnect the block from its predecessors and update their control-flow // instructions. - for (HBasicBlock* predecessor : predecessors_) { + for (size_t i = 0, e = predecessors_.Size(); i < e; ++i) { + HBasicBlock* predecessor = predecessors_.Get(i); HInstruction* last_instruction = predecessor->GetLastInstruction(); predecessor->RemoveInstruction(last_instruction); predecessor->RemoveSuccessor(this); - if (predecessor->GetSuccessors().size() == 1u) { + if (predecessor->GetSuccessors().Size() == 1u) { DCHECK(last_instruction->IsIf()); predecessor->AddInstruction(new (graph_->GetArena()) HGoto()); } else { // The predecessor has no remaining successors and therefore must be dead. // We deliberately leave it without a control-flow instruction so that the // SSAChecker fails unless it is not removed during the pass too. - DCHECK_EQ(predecessor->GetSuccessors().size(), 0u); + DCHECK_EQ(predecessor->GetSuccessors().Size(), 0u); } } - predecessors_.clear(); + predecessors_.Reset(); // Disconnect the block from its successors and update their phis. - for (HBasicBlock* successor : successors_) { + for (size_t i = 0, e = successors_.Size(); i < e; ++i) { + HBasicBlock* successor = successors_.Get(i); // Delete this block from the list of predecessors. size_t this_index = successor->GetPredecessorIndexOf(this); - successor->predecessors_.erase(successor->predecessors_.begin() + this_index); + successor->predecessors_.DeleteAt(this_index); // Check that `successor` has other predecessors, otherwise `this` is the // dominator of `successor` which violates the order DCHECKed at the top. - DCHECK(!successor->predecessors_.empty()); + DCHECK(!successor->predecessors_.IsEmpty()); // Remove this block's entries in the successor's phis. - if (successor->predecessors_.size() == 1u) { + if (successor->predecessors_.Size() == 1u) { // The successor has just one predecessor left. Replace phis with the only // remaining input. for (HInstructionIterator phi_it(successor->GetPhis()); !phi_it.Done(); phi_it.Advance()) { @@ -1339,7 +1345,7 @@ void HBasicBlock::DisconnectAndDelete() { } } } - successors_.clear(); + successors_.Reset(); // Disconnect from the dominator. dominator_->RemoveDominatedBlock(this); @@ -1353,10 +1359,11 @@ void HBasicBlock::DisconnectAndDelete() { void HBasicBlock::MergeWith(HBasicBlock* other) { DCHECK_EQ(GetGraph(), other->GetGraph()); - DCHECK(std::find(dominated_blocks_.begin(), dominated_blocks_.end(), other) != - dominated_blocks_.end()); - DCHECK_EQ(GetSingleSuccessor(), other); - DCHECK_EQ(other->GetSinglePredecessor(), this); + DCHECK(GetDominatedBlocks().Contains(other)); + DCHECK_EQ(GetSuccessors().Size(), 1u); + DCHECK_EQ(GetSuccessors().Get(0), other); + DCHECK_EQ(other->GetPredecessors().Size(), 1u); + DCHECK_EQ(other->GetPredecessors().Get(0), this); DCHECK(other->GetPhis().IsEmpty()); // Move instructions from `other` to `this`. @@ -1376,23 +1383,24 @@ void HBasicBlock::MergeWith(HBasicBlock* other) { } // Update links to the successors of `other`. - successors_.clear(); - while (!other->successors_.empty()) { - HBasicBlock* successor = other->GetSuccessor(0); + successors_.Reset(); + while (!other->successors_.IsEmpty()) { + HBasicBlock* successor = other->successors_.Get(0); successor->ReplacePredecessor(other, this); } // Update the dominator tree. - RemoveDominatedBlock(other); - for (HBasicBlock* dominated : other->GetDominatedBlocks()) { - dominated_blocks_.push_back(dominated); + dominated_blocks_.Delete(other); + for (size_t i = 0, e = other->GetDominatedBlocks().Size(); i < e; ++i) { + HBasicBlock* dominated = other->GetDominatedBlocks().Get(i); + dominated_blocks_.Add(dominated); dominated->SetDominator(this); } - other->dominated_blocks_.clear(); + other->dominated_blocks_.Reset(); other->dominator_ = nullptr; // Clear the list of predecessors of `other` in preparation of deleting it. - other->predecessors_.clear(); + other->predecessors_.Reset(); // Delete `other` from the graph. The function updates reverse post order. graph_->DeleteDeadBlock(other); @@ -1401,10 +1409,11 @@ void HBasicBlock::MergeWith(HBasicBlock* other) { void HBasicBlock::MergeWithInlined(HBasicBlock* other) { DCHECK_NE(GetGraph(), other->GetGraph()); - DCHECK(GetDominatedBlocks().empty()); - DCHECK(GetSuccessors().empty()); + DCHECK(GetDominatedBlocks().IsEmpty()); + DCHECK(GetSuccessors().IsEmpty()); DCHECK(!EndsWithControlFlowInstruction()); - DCHECK(other->GetSinglePredecessor()->IsEntryBlock()); + DCHECK_EQ(other->GetPredecessors().Size(), 1u); + DCHECK(other->GetPredecessors().Get(0)->IsEntryBlock()); DCHECK(other->GetPhis().IsEmpty()); DCHECK(!other->IsInLoop()); @@ -1413,33 +1422,34 @@ void HBasicBlock::MergeWithInlined(HBasicBlock* other) { other->instructions_.SetBlockOfInstructions(this); // Update links to the successors of `other`. - successors_.clear(); - while (!other->successors_.empty()) { - HBasicBlock* successor = other->GetSuccessor(0); + successors_.Reset(); + while (!other->successors_.IsEmpty()) { + HBasicBlock* successor = other->successors_.Get(0); successor->ReplacePredecessor(other, this); } // Update the dominator tree. - for (HBasicBlock* dominated : other->GetDominatedBlocks()) { - dominated_blocks_.push_back(dominated); + for (size_t i = 0, e = other->GetDominatedBlocks().Size(); i < e; ++i) { + HBasicBlock* dominated = other->GetDominatedBlocks().Get(i); + dominated_blocks_.Add(dominated); dominated->SetDominator(this); } - other->dominated_blocks_.clear(); + other->dominated_blocks_.Reset(); other->dominator_ = nullptr; other->graph_ = nullptr; } void HBasicBlock::ReplaceWith(HBasicBlock* other) { - while (!GetPredecessors().empty()) { - HBasicBlock* predecessor = GetPredecessor(0); + while (!GetPredecessors().IsEmpty()) { + HBasicBlock* predecessor = GetPredecessors().Get(0); predecessor->ReplaceSuccessor(this, other); } - while (!GetSuccessors().empty()) { - HBasicBlock* successor = GetSuccessor(0); + while (!GetSuccessors().IsEmpty()) { + HBasicBlock* successor = GetSuccessors().Get(0); successor->ReplacePredecessor(this, other); } - for (HBasicBlock* dominated : GetDominatedBlocks()) { - other->AddDominatedBlock(dominated); + for (size_t i = 0; i < dominated_blocks_.Size(); ++i) { + other->AddDominatedBlock(dominated_blocks_.Get(i)); } GetDominator()->ReplaceDominatedBlock(this, other); other->SetDominator(GetDominator()); @@ -1462,9 +1472,9 @@ static void MakeRoomFor(GrowableArray<HBasicBlock*>* blocks, void HGraph::DeleteDeadBlock(HBasicBlock* block) { DCHECK_EQ(block->GetGraph(), this); - DCHECK(block->GetSuccessors().empty()); - DCHECK(block->GetPredecessors().empty()); - DCHECK(block->GetDominatedBlocks().empty()); + DCHECK(block->GetSuccessors().IsEmpty()); + DCHECK(block->GetPredecessors().IsEmpty()); + DCHECK(block->GetDominatedBlocks().IsEmpty()); DCHECK(block->GetDominator() == nullptr); for (HBackwardInstructionIterator it(block->GetInstructions()); !it.Done(); it.Advance()) { @@ -1538,16 +1548,16 @@ HInstruction* HGraph::InlineInto(HGraph* outer_graph, HInvoke* invoke) { HBasicBlock* at = invoke->GetBlock(); HBasicBlock* to = at->SplitAfter(invoke); - HBasicBlock* first = entry_block_->GetSuccessor(0); + HBasicBlock* first = entry_block_->GetSuccessors().Get(0); DCHECK(!first->IsInLoop()); at->MergeWithInlined(first); exit_block_->ReplaceWith(to); // Update all predecessors of the exit block (now the `to` block) // to not `HReturn` but `HGoto` instead. - bool returns_void = to->GetPredecessor(0)->GetLastInstruction()->IsReturnVoid(); - if (to->GetPredecessors().size() == 1) { - HBasicBlock* predecessor = to->GetPredecessor(0); + bool returns_void = to->GetPredecessors().Get(0)->GetLastInstruction()->IsReturnVoid(); + if (to->GetPredecessors().Size() == 1) { + HBasicBlock* predecessor = to->GetPredecessors().Get(0); HInstruction* last = predecessor->GetLastInstruction(); if (!returns_void) { return_value = last->InputAt(0); @@ -1561,7 +1571,8 @@ HInstruction* HGraph::InlineInto(HGraph* outer_graph, HInvoke* invoke) { allocator, kNoRegNumber, 0, HPhi::ToPhiType(invoke->GetType())); to->AddPhi(return_value->AsPhi()); } - for (HBasicBlock* predecessor : to->GetPredecessors()) { + for (size_t i = 0, e = to->GetPredecessors().Size(); i < e; ++i) { + HBasicBlock* predecessor = to->GetPredecessors().Get(i); HInstruction* last = predecessor->GetLastInstruction(); if (!returns_void) { return_value->AsPhi()->AddInput(last->InputAt(0)); @@ -1709,8 +1720,8 @@ void HGraph::TransformLoopHeaderForBCE(HBasicBlock* header) { AddBlock(new_pre_header); header->ReplacePredecessor(pre_header, new_pre_header); - pre_header->successors_.clear(); - pre_header->dominated_blocks_.clear(); + pre_header->successors_.Reset(); + pre_header->dominated_blocks_.Reset(); pre_header->AddSuccessor(if_block); if_block->AddSuccessor(dummy_block); // True successor @@ -1718,15 +1729,15 @@ void HGraph::TransformLoopHeaderForBCE(HBasicBlock* header) { dummy_block->AddSuccessor(new_pre_header); deopt_block->AddSuccessor(new_pre_header); - pre_header->dominated_blocks_.push_back(if_block); + pre_header->dominated_blocks_.Add(if_block); if_block->SetDominator(pre_header); - if_block->dominated_blocks_.push_back(dummy_block); + if_block->dominated_blocks_.Add(dummy_block); dummy_block->SetDominator(if_block); - if_block->dominated_blocks_.push_back(deopt_block); + if_block->dominated_blocks_.Add(deopt_block); deopt_block->SetDominator(if_block); - if_block->dominated_blocks_.push_back(new_pre_header); + if_block->dominated_blocks_.Add(new_pre_header); new_pre_header->SetDominator(if_block); - new_pre_header->dominated_blocks_.push_back(header); + new_pre_header->dominated_blocks_.Add(header); header->SetDominator(new_pre_header); size_t index_of_header = 0; diff --git a/compiler/optimizing/nodes.h b/compiler/optimizing/nodes.h index 768658ee05..ee82fda6c8 100644 --- a/compiler/optimizing/nodes.h +++ b/compiler/optimizing/nodes.h @@ -17,7 +17,6 @@ #ifndef ART_COMPILER_OPTIMIZING_NODES_H_ #define ART_COMPILER_OPTIMIZING_NODES_H_ -#include <algorithm> #include <array> #include <type_traits> @@ -625,46 +624,26 @@ class HBasicBlock : public ArenaObject<kArenaAllocBasicBlock> { public: explicit HBasicBlock(HGraph* graph, uint32_t dex_pc = kNoDexPc) : graph_(graph), - predecessors_(graph->GetArena()->Adapter(kArenaAllocPredecessors)), - successors_(graph->GetArena()->Adapter(kArenaAllocSuccessors)), + predecessors_(graph->GetArena(), kDefaultNumberOfPredecessors), + successors_(graph->GetArena(), kDefaultNumberOfSuccessors), loop_information_(nullptr), dominator_(nullptr), - dominated_blocks_(graph->GetArena()->Adapter(kArenaAllocDominated)), + dominated_blocks_(graph->GetArena(), kDefaultNumberOfDominatedBlocks), block_id_(-1), dex_pc_(dex_pc), lifetime_start_(kNoLifetime), lifetime_end_(kNoLifetime), - try_catch_information_(nullptr) { - predecessors_.reserve(kDefaultNumberOfPredecessors); - successors_.reserve(kDefaultNumberOfSuccessors); - dominated_blocks_.reserve(kDefaultNumberOfDominatedBlocks); - } + try_catch_information_(nullptr) {} - const ArenaVector<HBasicBlock*>& GetPredecessors() const { + const GrowableArray<HBasicBlock*>& GetPredecessors() const { return predecessors_; } - HBasicBlock* GetPredecessor(size_t pred_idx) const { - DCHECK_LT(pred_idx, predecessors_.size()); - return predecessors_[pred_idx]; - } - - const ArenaVector<HBasicBlock*>& GetSuccessors() const { + const GrowableArray<HBasicBlock*>& GetSuccessors() const { return successors_; } - bool HasSuccessor(const HBasicBlock* block, size_t start_from = 0u) { - DCHECK_LE(start_from, successors_.size()); - auto it = std::find(successors_.begin() + start_from, successors_.end(), block); - return it != successors_.end(); - } - - HBasicBlock* GetSuccessor(size_t succ_idx) const { - DCHECK_LT(succ_idx, successors_.size()); - return successors_[succ_idx]; - } - - const ArenaVector<HBasicBlock*>& GetDominatedBlocks() const { + const GrowableArray<HBasicBlock*>& GetDominatedBlocks() const { return dominated_blocks_; } @@ -703,20 +682,18 @@ class HBasicBlock : public ArenaObject<kArenaAllocBasicBlock> { HBasicBlock* GetDominator() const { return dominator_; } void SetDominator(HBasicBlock* dominator) { dominator_ = dominator; } - void AddDominatedBlock(HBasicBlock* block) { dominated_blocks_.push_back(block); } - - void RemoveDominatedBlock(HBasicBlock* block) { - auto it = std::find(dominated_blocks_.begin(), dominated_blocks_.end(), block); - DCHECK(it != dominated_blocks_.end()); - dominated_blocks_.erase(it); - } - + void AddDominatedBlock(HBasicBlock* block) { dominated_blocks_.Add(block); } + void RemoveDominatedBlock(HBasicBlock* block) { dominated_blocks_.Delete(block); } void ReplaceDominatedBlock(HBasicBlock* existing, HBasicBlock* new_block) { - auto it = std::find(dominated_blocks_.begin(), dominated_blocks_.end(), existing); - DCHECK(it != dominated_blocks_.end()); - *it = new_block; + for (size_t i = 0, e = dominated_blocks_.Size(); i < e; ++i) { + if (dominated_blocks_.Get(i) == existing) { + dominated_blocks_.Put(i, new_block); + return; + } + } + LOG(FATAL) << "Unreachable"; + UNREACHABLE(); } - void ClearDominanceInformation(); int NumberOfBackEdges() const { @@ -731,22 +708,24 @@ class HBasicBlock : public ArenaObject<kArenaAllocBasicBlock> { const HInstructionList& GetPhis() const { return phis_; } void AddSuccessor(HBasicBlock* block) { - successors_.push_back(block); - block->predecessors_.push_back(this); + successors_.Add(block); + block->predecessors_.Add(this); } void ReplaceSuccessor(HBasicBlock* existing, HBasicBlock* new_block) { size_t successor_index = GetSuccessorIndexOf(existing); + DCHECK_NE(successor_index, static_cast<size_t>(-1)); existing->RemovePredecessor(this); - new_block->predecessors_.push_back(this); - successors_[successor_index] = new_block; + new_block->predecessors_.Add(this); + successors_.Put(successor_index, new_block); } void ReplacePredecessor(HBasicBlock* existing, HBasicBlock* new_block) { size_t predecessor_index = GetPredecessorIndexOf(existing); + DCHECK_NE(predecessor_index, static_cast<size_t>(-1)); existing->RemoveSuccessor(this); - new_block->successors_.push_back(this); - predecessors_[predecessor_index] = new_block; + new_block->successors_.Add(this); + predecessors_.Put(predecessor_index, new_block); } // Insert `this` between `predecessor` and `successor. This method @@ -754,73 +733,85 @@ class HBasicBlock : public ArenaObject<kArenaAllocBasicBlock> { // `predecessor` and `successor`. void InsertBetween(HBasicBlock* predecessor, HBasicBlock* successor) { size_t predecessor_index = successor->GetPredecessorIndexOf(predecessor); + DCHECK_NE(predecessor_index, static_cast<size_t>(-1)); size_t successor_index = predecessor->GetSuccessorIndexOf(successor); - successor->predecessors_[predecessor_index] = this; - predecessor->successors_[successor_index] = this; - successors_.push_back(successor); - predecessors_.push_back(predecessor); + DCHECK_NE(successor_index, static_cast<size_t>(-1)); + successor->predecessors_.Put(predecessor_index, this); + predecessor->successors_.Put(successor_index, this); + successors_.Add(successor); + predecessors_.Add(predecessor); } void RemovePredecessor(HBasicBlock* block) { - predecessors_.erase(predecessors_.begin() + GetPredecessorIndexOf(block)); + predecessors_.Delete(block); } void RemoveSuccessor(HBasicBlock* block) { - successors_.erase(successors_.begin() + GetSuccessorIndexOf(block)); + successors_.Delete(block); } void ClearAllPredecessors() { - predecessors_.clear(); + predecessors_.Reset(); } void AddPredecessor(HBasicBlock* block) { - predecessors_.push_back(block); - block->successors_.push_back(this); + predecessors_.Add(block); + block->successors_.Add(this); } void SwapPredecessors() { - DCHECK_EQ(predecessors_.size(), 2u); - std::swap(predecessors_[0], predecessors_[1]); + DCHECK_EQ(predecessors_.Size(), 2u); + HBasicBlock* temp = predecessors_.Get(0); + predecessors_.Put(0, predecessors_.Get(1)); + predecessors_.Put(1, temp); } void SwapSuccessors() { - DCHECK_EQ(successors_.size(), 2u); - std::swap(successors_[0], successors_[1]); + DCHECK_EQ(successors_.Size(), 2u); + HBasicBlock* temp = successors_.Get(0); + successors_.Put(0, successors_.Get(1)); + successors_.Put(1, temp); } size_t GetPredecessorIndexOf(HBasicBlock* predecessor) const { - auto it = std::find(predecessors_.begin(), predecessors_.end(), predecessor); - DCHECK(it != predecessors_.end()); - return std::distance(predecessors_.begin(), it); + for (size_t i = 0, e = predecessors_.Size(); i < e; ++i) { + if (predecessors_.Get(i) == predecessor) { + return i; + } + } + return -1; } size_t GetSuccessorIndexOf(HBasicBlock* successor) const { - auto it = std::find(successors_.begin(), successors_.end(), successor); - DCHECK(it != successors_.end()); - return std::distance(successors_.begin(), it); + for (size_t i = 0, e = successors_.Size(); i < e; ++i) { + if (successors_.Get(i) == successor) { + return i; + } + } + return -1; } HBasicBlock* GetSinglePredecessor() const { - DCHECK_EQ(GetPredecessors().size(), 1u); - return GetPredecessor(0); + DCHECK_EQ(GetPredecessors().Size(), 1u); + return GetPredecessors().Get(0); } HBasicBlock* GetSingleSuccessor() const { - DCHECK_EQ(GetSuccessors().size(), 1u); - return GetSuccessor(0); + DCHECK_EQ(GetSuccessors().Size(), 1u); + return GetSuccessors().Get(0); } // Returns whether the first occurrence of `predecessor` in the list of // predecessors is at index `idx`. bool IsFirstIndexOfPredecessor(HBasicBlock* predecessor, size_t idx) const { - DCHECK_EQ(GetPredecessor(idx), predecessor); + DCHECK_EQ(GetPredecessors().Get(idx), predecessor); return GetPredecessorIndexOf(predecessor) == idx; } // Returns the number of non-exceptional successors. SsaChecker ensures that // these are stored at the beginning of the successor list. size_t NumberOfNormalSuccessors() const { - return EndsWithTryBoundary() ? 1 : GetSuccessors().size(); + return EndsWithTryBoundary() ? 1 : GetSuccessors().Size(); } // Split the block into two blocks just before `cursor`. Returns the newly @@ -885,7 +876,8 @@ class HBasicBlock : public ArenaObject<kArenaAllocBasicBlock> { bool IsLoopPreHeaderFirstPredecessor() const { DCHECK(IsLoopHeader()); - return GetPredecessor(0) == GetLoopInformation()->GetPreHeader(); + DCHECK(!GetPredecessors().IsEmpty()); + return GetPredecessors().Get(0) == GetLoopInformation()->GetPreHeader(); } HLoopInformation* GetLoopInformation() const { @@ -956,13 +948,13 @@ class HBasicBlock : public ArenaObject<kArenaAllocBasicBlock> { private: HGraph* graph_; - ArenaVector<HBasicBlock*> predecessors_; - ArenaVector<HBasicBlock*> successors_; + GrowableArray<HBasicBlock*> predecessors_; + GrowableArray<HBasicBlock*> successors_; HInstructionList instructions_; HInstructionList phis_; HLoopInformation* loop_information_; HBasicBlock* dominator_; - ArenaVector<HBasicBlock*> dominated_blocks_; + GrowableArray<HBasicBlock*> dominated_blocks_; int block_id_; // The dex program counter of the first instruction of this block. const uint32_t dex_pc_; @@ -2274,11 +2266,11 @@ class HIf : public HTemplateInstruction<1> { bool IsControlFlow() const OVERRIDE { return true; } HBasicBlock* IfTrueSuccessor() const { - return GetBlock()->GetSuccessor(0); + return GetBlock()->GetSuccessors().Get(0); } HBasicBlock* IfFalseSuccessor() const { - return GetBlock()->GetSuccessor(1); + return GetBlock()->GetSuccessors().Get(1); } DECLARE_INSTRUCTION(If); @@ -2306,13 +2298,14 @@ class HTryBoundary : public HTemplateInstruction<0> { bool IsControlFlow() const OVERRIDE { return true; } // Returns the block's non-exceptional successor (index zero). - HBasicBlock* GetNormalFlowSuccessor() const { return GetBlock()->GetSuccessor(0); } + HBasicBlock* GetNormalFlowSuccessor() const { return GetBlock()->GetSuccessors().Get(0); } // Returns whether `handler` is among its exception handlers (non-zero index // successors). bool HasExceptionHandler(const HBasicBlock& handler) const { DCHECK(handler.IsCatchBlock()); - return GetBlock()->HasSuccessor(&handler, 1u /* Skip first successor. */); + return GetBlock()->GetSuccessors().Contains( + const_cast<HBasicBlock*>(&handler), /* start_from */ 1); } // If not present already, adds `handler` to its block's list of exception @@ -2342,8 +2335,8 @@ class HExceptionHandlerIterator : public ValueObject { explicit HExceptionHandlerIterator(const HTryBoundary& try_boundary) : block_(*try_boundary.GetBlock()), index_(block_.NumberOfNormalSuccessors()) {} - bool Done() const { return index_ == block_.GetSuccessors().size(); } - HBasicBlock* Current() const { return block_.GetSuccessor(index_); } + bool Done() const { return index_ == block_.GetSuccessors().Size(); } + HBasicBlock* Current() const { return block_.GetSuccessors().Get(index_); } size_t CurrentSuccessorIndex() const { return index_; } void Advance() { ++index_; } diff --git a/compiler/optimizing/pretty_printer.h b/compiler/optimizing/pretty_printer.h index 34850a564c..934514eeda 100644 --- a/compiler/optimizing/pretty_printer.h +++ b/compiler/optimizing/pretty_printer.h @@ -71,23 +71,23 @@ class HPrettyPrinter : public HGraphVisitor { void VisitBasicBlock(HBasicBlock* block) OVERRIDE { PrintString("BasicBlock "); PrintInt(block->GetBlockId()); - const ArenaVector<HBasicBlock*>& predecessors = block->GetPredecessors(); - if (!predecessors.empty()) { + const GrowableArray<HBasicBlock*>& predecessors = block->GetPredecessors(); + if (!predecessors.IsEmpty()) { PrintString(", pred: "); - for (size_t i = 0; i < predecessors.size() -1; i++) { - PrintInt(predecessors[i]->GetBlockId()); + for (size_t i = 0; i < predecessors.Size() -1; i++) { + PrintInt(predecessors.Get(i)->GetBlockId()); PrintString(", "); } - PrintInt(predecessors.back()->GetBlockId()); + PrintInt(predecessors.Peek()->GetBlockId()); } - const ArenaVector<HBasicBlock*>& successors = block->GetSuccessors(); - if (!successors.empty()) { + const GrowableArray<HBasicBlock*>& successors = block->GetSuccessors(); + if (!successors.IsEmpty()) { PrintString(", succ: "); - for (size_t i = 0; i < successors.size() - 1; i++) { - PrintInt(successors[i]->GetBlockId()); + for (size_t i = 0; i < successors.Size() - 1; i++) { + PrintInt(successors.Get(i)->GetBlockId()); PrintString(", "); } - PrintInt(successors.back()->GetBlockId()); + PrintInt(successors.Peek()->GetBlockId()); } PrintNewLine(); HGraphVisitor::VisitBasicBlock(block); @@ -131,7 +131,7 @@ class StringPrettyPrinter : public HPrettyPrinter { PrintString(" "); PrintInt(gota->GetId()); PrintString(": Goto "); - PrintInt(current_block_->GetSuccessor(0)->GetBlockId()); + PrintInt(current_block_->GetSuccessors().Get(0)->GetBlockId()); PrintNewLine(); } diff --git a/compiler/optimizing/register_allocator.cc b/compiler/optimizing/register_allocator.cc index 6f1f6af62d..37c8bc5f51 100644 --- a/compiler/optimizing/register_allocator.cc +++ b/compiler/optimizing/register_allocator.cc @@ -1212,13 +1212,14 @@ LiveInterval* RegisterAllocator::SplitBetween(LiveInterval* interval, size_t fro * moves in B3. */ if (block_from->GetDominator() != nullptr) { - for (HBasicBlock* dominated : block_from->GetDominator()->GetDominatedBlocks()) { - size_t position = dominated->GetLifetimeStart(); + const GrowableArray<HBasicBlock*>& dominated = block_from->GetDominator()->GetDominatedBlocks(); + for (size_t i = 0; i < dominated.Size(); ++i) { + size_t position = dominated.Get(i)->GetLifetimeStart(); if ((position > from) && (block_to->GetLifetimeStart() > position)) { // Even if we found a better block, we continue iterating in case // a dominated block is closer. // Note that dominated blocks are not sorted in liveness order. - block_to = dominated; + block_to = dominated.Get(i); DCHECK_NE(block_to, block_from); } } @@ -1497,7 +1498,7 @@ void RegisterAllocator::InsertParallelMoveAtExitOf(HBasicBlock* block, DCHECK(IsValidDestination(destination)) << destination; if (source.Equals(destination)) return; - DCHECK_EQ(block->GetSuccessors().size(), 1u); + DCHECK_EQ(block->GetSuccessors().Size(), 1u); HInstruction* last = block->GetLastInstruction(); // We insert moves at exit for phi predecessors and connecting blocks. // A block ending with an if cannot branch to a block with phis because @@ -1724,13 +1725,13 @@ void RegisterAllocator::ConnectSplitSiblings(LiveInterval* interval, // If `from` has only one successor, we can put the moves at the exit of it. Otherwise // we need to put the moves at the entry of `to`. - if (from->GetSuccessors().size() == 1) { + if (from->GetSuccessors().Size() == 1) { InsertParallelMoveAtExitOf(from, interval->GetParent()->GetDefinedBy(), source->ToLocation(), destination->ToLocation()); } else { - DCHECK_EQ(to->GetPredecessors().size(), 1u); + DCHECK_EQ(to->GetPredecessors().Size(), 1u); InsertParallelMoveAtEntryOf(to, interval->GetParent()->GetDefinedBy(), source->ToLocation(), @@ -1832,8 +1833,8 @@ void RegisterAllocator::Resolve() { for (uint32_t idx : live->Indexes()) { HInstruction* current = liveness_.GetInstructionFromSsaIndex(idx); LiveInterval* interval = current->GetLiveInterval(); - for (HBasicBlock* predecessor : block->GetPredecessors()) { - ConnectSplitSiblings(interval, predecessor, block); + for (size_t i = 0, e = block->GetPredecessors().Size(); i < e; ++i) { + ConnectSplitSiblings(interval, block->GetPredecessors().Get(i), block); } } } @@ -1843,9 +1844,9 @@ void RegisterAllocator::Resolve() { HBasicBlock* current = it.Current(); for (HInstructionIterator inst_it(current->GetPhis()); !inst_it.Done(); inst_it.Advance()) { HInstruction* phi = inst_it.Current(); - for (size_t i = 0, e = current->GetPredecessors().size(); i < e; ++i) { - HBasicBlock* predecessor = current->GetPredecessor(i); - DCHECK_EQ(predecessor->GetSuccessors().size(), 1u); + for (size_t i = 0, e = current->GetPredecessors().Size(); i < e; ++i) { + HBasicBlock* predecessor = current->GetPredecessors().Get(i); + DCHECK_EQ(predecessor->GetSuccessors().Size(), 1u); HInstruction* input = phi->InputAt(i); Location source = input->GetLiveInterval()->GetLocationAt( predecessor->GetLifetimeEnd() - 1); diff --git a/compiler/optimizing/ssa_builder.cc b/compiler/optimizing/ssa_builder.cc index e6209b9583..561c3b4964 100644 --- a/compiler/optimizing/ssa_builder.cc +++ b/compiler/optimizing/ssa_builder.cc @@ -241,8 +241,8 @@ void SsaBuilder::BuildSsa() { HBasicBlock* block = loop_headers_.Get(i); for (HInstructionIterator it(block->GetPhis()); !it.Done(); it.Advance()) { HPhi* phi = it.Current()->AsPhi(); - for (HBasicBlock* predecessor : block->GetPredecessors()) { - HInstruction* input = ValueOfLocal(predecessor, phi->GetRegNumber()); + for (size_t pred = 0; pred < block->GetPredecessors().Size(); pred++) { + HInstruction* input = ValueOfLocal(block->GetPredecessors().Get(pred), phi->GetRegNumber()); phi->AddInput(input); } } @@ -369,16 +369,16 @@ void SsaBuilder::VisitBasicBlock(HBasicBlock* block) { // Save the loop header so that the last phase of the analysis knows which // blocks need to be updated. loop_headers_.Add(block); - } else if (block->GetPredecessors().size() > 0) { + } else if (block->GetPredecessors().Size() > 0) { // All predecessors have already been visited because we are visiting in reverse post order. // We merge the values of all locals, creating phis if those values differ. for (size_t local = 0; local < current_locals_->Size(); local++) { bool one_predecessor_has_no_value = false; bool is_different = false; - HInstruction* value = ValueOfLocal(block->GetPredecessor(0), local); + HInstruction* value = ValueOfLocal(block->GetPredecessors().Get(0), local); - for (HBasicBlock* predecessor : block->GetPredecessors()) { - HInstruction* current = ValueOfLocal(predecessor, local); + for (size_t i = 0, e = block->GetPredecessors().Size(); i < e; ++i) { + HInstruction* current = ValueOfLocal(block->GetPredecessors().Get(i), local); if (current == nullptr) { one_predecessor_has_no_value = true; break; @@ -395,9 +395,9 @@ void SsaBuilder::VisitBasicBlock(HBasicBlock* block) { if (is_different) { HPhi* phi = new (GetGraph()->GetArena()) HPhi( - GetGraph()->GetArena(), local, block->GetPredecessors().size(), Primitive::kPrimVoid); - for (size_t i = 0; i < block->GetPredecessors().size(); i++) { - HInstruction* pred_value = ValueOfLocal(block->GetPredecessor(i), local); + GetGraph()->GetArena(), local, block->GetPredecessors().Size(), Primitive::kPrimVoid); + for (size_t i = 0; i < block->GetPredecessors().Size(); i++) { + HInstruction* pred_value = ValueOfLocal(block->GetPredecessors().Get(i), local); phi->SetRawInputAt(i, pred_value); } block->AddPhi(phi); diff --git a/compiler/optimizing/ssa_liveness_analysis.cc b/compiler/optimizing/ssa_liveness_analysis.cc index 0c1831b45f..40502c173b 100644 --- a/compiler/optimizing/ssa_liveness_analysis.cc +++ b/compiler/optimizing/ssa_liveness_analysis.cc @@ -73,7 +73,7 @@ void SsaLivenessAnalysis::LinearizeGraph() { forward_predecessors.SetSize(graph_->GetBlocks().Size()); for (HReversePostOrderIterator it(*graph_); !it.Done(); it.Advance()) { HBasicBlock* block = it.Current(); - size_t number_of_forward_predecessors = block->GetPredecessors().size(); + size_t number_of_forward_predecessors = block->GetPredecessors().Size(); if (block->IsLoopHeader()) { number_of_forward_predecessors -= block->GetLoopInformation()->NumberOfBackEdges(); } @@ -89,7 +89,8 @@ void SsaLivenessAnalysis::LinearizeGraph() { do { HBasicBlock* current = worklist.Pop(); graph_->linear_order_.Add(current); - for (HBasicBlock* successor : current->GetSuccessors()) { + for (size_t i = 0, e = current->GetSuccessors().Size(); i < e; ++i) { + HBasicBlock* successor = current->GetSuccessors().Get(i); int block_id = successor->GetBlockId(); size_t number_of_remaining_predecessors = forward_predecessors.Get(block_id); if (number_of_remaining_predecessors == 1) { @@ -184,7 +185,8 @@ void SsaLivenessAnalysis::ComputeLiveRanges() { // Set phi inputs of successors of this block corresponding to this block // as live_in. - for (HBasicBlock* successor : block->GetSuccessors()) { + for (size_t i = 0, e = block->GetSuccessors().Size(); i < e; ++i) { + HBasicBlock* successor = block->GetSuccessors().Get(i); live_in->Union(GetLiveInSet(*successor)); size_t phi_input_index = successor->GetPredecessorIndexOf(block); for (HInstructionIterator inst_it(successor->GetPhis()); !inst_it.Done(); inst_it.Advance()) { @@ -294,7 +296,8 @@ bool SsaLivenessAnalysis::UpdateLiveOut(const HBasicBlock& block) { BitVector* live_out = GetLiveOutSet(block); bool changed = false; // The live_out set of a block is the union of live_in sets of its successors. - for (HBasicBlock* successor : block.GetSuccessors()) { + for (size_t i = 0, e = block.GetSuccessors().Size(); i < e; ++i) { + HBasicBlock* successor = block.GetSuccessors().Get(i); if (live_out->Union(GetLiveInSet(*successor))) { changed = true; } @@ -339,8 +342,8 @@ int LiveInterval::FindFirstRegisterHint(size_t* free_until, // will avoid a move between the two blocks. HBasicBlock* block = liveness.GetBlockFromPosition(GetStart() / 2); size_t next_register_use = FirstRegisterUse(); - for (HBasicBlock* predecessor : block->GetPredecessors()) { - size_t position = predecessor->GetLifetimeEnd() - 1; + for (size_t i = 0; i < block->GetPredecessors().Size(); ++i) { + size_t position = block->GetPredecessors().Get(i)->GetLifetimeEnd() - 1; // We know positions above GetStart() do not have a location yet. if (position < GetStart()) { LiveInterval* existing = GetParent()->GetSiblingAt(position); @@ -373,16 +376,17 @@ int LiveInterval::FindFirstRegisterHint(size_t* free_until, return reg; } } + const GrowableArray<HBasicBlock*>& predecessors = user->GetBlock()->GetPredecessors(); // If the instruction dies at the phi assignment, we can try having the // same register. - if (end == user->GetBlock()->GetPredecessor(input_index)->GetLifetimeEnd()) { + if (end == predecessors.Get(input_index)->GetLifetimeEnd()) { for (size_t i = 0, e = user->InputCount(); i < e; ++i) { if (i == input_index) { continue; } HInstruction* input = user->InputAt(i); Location location = input->GetLiveInterval()->GetLocationAt( - user->GetBlock()->GetPredecessor(i)->GetLifetimeEnd() - 1); + predecessors.Get(i)->GetLifetimeEnd() - 1); if (location.IsRegisterKind()) { int reg = RegisterOrLowRegister(location); if (free_until[reg] >= use_position) { @@ -416,11 +420,10 @@ int LiveInterval::FindFirstRegisterHint(size_t* free_until, int LiveInterval::FindHintAtDefinition() const { if (defined_by_->IsPhi()) { // Try to use the same register as one of the inputs. - const ArenaVector<HBasicBlock*>& predecessors = defined_by_->GetBlock()->GetPredecessors(); + const GrowableArray<HBasicBlock*>& predecessors = defined_by_->GetBlock()->GetPredecessors(); for (size_t i = 0, e = defined_by_->InputCount(); i < e; ++i) { HInstruction* input = defined_by_->InputAt(i); - DCHECK_LT(i, predecessors.size()); - size_t end = predecessors[i]->GetLifetimeEnd(); + size_t end = predecessors.Get(i)->GetLifetimeEnd(); LiveInterval* input_interval = input->GetLiveInterval()->GetSiblingAt(end - 1); if (input_interval->GetEnd() == end) { // If the input dies at the end of the predecessor, we know its register can diff --git a/compiler/optimizing/suspend_check_test.cc b/compiler/optimizing/suspend_check_test.cc index e745d94b89..5ca66a1de6 100644 --- a/compiler/optimizing/suspend_check_test.cc +++ b/compiler/optimizing/suspend_check_test.cc @@ -36,7 +36,7 @@ static void TestCode(const uint16_t* data) { bool graph_built = builder.BuildGraph(*item); ASSERT_TRUE(graph_built); - HBasicBlock* first_block = graph->GetEntryBlock()->GetSuccessor(0); + HBasicBlock* first_block = graph->GetEntryBlock()->GetSuccessors().Get(0); HInstruction* first_instruction = first_block->GetFirstInstruction(); // Account for some tests having a store local as first instruction. ASSERT_TRUE(first_instruction->IsSuspendCheck() diff --git a/runtime/base/arena_allocator.cc b/runtime/base/arena_allocator.cc index a36b0fbb93..3a4bccd94c 100644 --- a/runtime/base/arena_allocator.cc +++ b/runtime/base/arena_allocator.cc @@ -52,14 +52,13 @@ const char* const ArenaAllocatorStatsImpl<kCount>::kAllocNames[] = { "SSA2Dalvik ", "Dalvik2SSA ", "DebugInfo ", + "Successor ", "RegAlloc ", "Data ", + "Preds ", "STL ", "Graph ", "BasicBlock ", - "Predecessors ", - "Successors ", - "Dominated ", "Instruction ", "LoopInfo ", "TryCatchInf ", diff --git a/runtime/base/arena_allocator.h b/runtime/base/arena_allocator.h index 47defb4ba2..af2bfbc944 100644 --- a/runtime/base/arena_allocator.h +++ b/runtime/base/arena_allocator.h @@ -62,14 +62,13 @@ enum ArenaAllocKind { kArenaAllocSSAToDalvikMap, kArenaAllocDalvikToSSAMap, kArenaAllocDebugInfo, + kArenaAllocSuccessor, kArenaAllocRegAlloc, kArenaAllocData, + kArenaAllocPredecessors, kArenaAllocSTL, kArenaAllocGraph, kArenaAllocBasicBlock, - kArenaAllocPredecessors, - kArenaAllocSuccessors, - kArenaAllocDominated, kArenaAllocInstruction, kArenaAllocLoopInfo, kArenaAllocTryCatchInfo, |