diff options
Diffstat (limited to 'compiler/optimizing')
31 files changed, 595 insertions, 400 deletions
diff --git a/compiler/optimizing/builder.h b/compiler/optimizing/builder.h index 580ef72767..f896f1199e 100644 --- a/compiler/optimizing/builder.h +++ b/compiler/optimizing/builder.h @@ -43,7 +43,7 @@ class HGraphBuilder : public ValueObject { OptimizingCompilerStats* compiler_stats, const uint8_t* interpreter_metadata, Handle<mirror::DexCache> dex_cache, - StackHandleScopeCollection* handles) + VariableSizedHandleScope* handles) : graph_(graph), dex_file_(dex_file), code_item_(code_item), @@ -68,7 +68,7 @@ class HGraphBuilder : public ValueObject { // Only for unit testing. HGraphBuilder(HGraph* graph, const DexFile::CodeItem& code_item, - StackHandleScopeCollection* handles, + VariableSizedHandleScope* handles, Primitive::Type return_type = Primitive::kPrimInt) : graph_(graph), dex_file_(nullptr), diff --git a/compiler/optimizing/code_generator_arm.cc b/compiler/optimizing/code_generator_arm.cc index 9870876879..77d6f23fff 100644 --- a/compiler/optimizing/code_generator_arm.cc +++ b/compiler/optimizing/code_generator_arm.cc @@ -1129,7 +1129,13 @@ void CodeGeneratorARM::GenerateFrameEntry() { int adjust = GetFrameSize() - FrameEntrySpillSize(); __ AddConstant(SP, -adjust); __ cfi().AdjustCFAOffset(adjust); - __ StoreToOffset(kStoreWord, kMethodRegisterArgument, SP, 0); + + // Save the current method if we need it. Note that we do not + // do this in HCurrentMethod, as the instruction might have been removed + // in the SSA graph. + if (RequiresCurrentMethod()) { + __ StoreToOffset(kStoreWord, kMethodRegisterArgument, SP, 0); + } } void CodeGeneratorARM::GenerateFrameExit() { diff --git a/compiler/optimizing/code_generator_arm64.cc b/compiler/optimizing/code_generator_arm64.cc index 969d653f97..b1e4f5c763 100644 --- a/compiler/optimizing/code_generator_arm64.cc +++ b/compiler/optimizing/code_generator_arm64.cc @@ -1046,7 +1046,13 @@ void CodeGeneratorARM64::GenerateFrameEntry() { // ... : other preserved fp registers. // ... : reserved frame space. // sp[0] : current method. - __ Str(kArtMethodRegister, MemOperand(sp, -frame_size, PreIndex)); + + // Save the current method if we need it. Note that we do not + // do this in HCurrentMethod, as the instruction might have been removed + // in the SSA graph. + if (RequiresCurrentMethod()) { + __ Str(kArtMethodRegister, MemOperand(sp, -frame_size, PreIndex)); + } GetAssembler()->cfi().AdjustCFAOffset(frame_size); GetAssembler()->SpillRegisters(GetFramePreservedCoreRegisters(), frame_size - GetCoreSpillSize()); diff --git a/compiler/optimizing/code_generator_mips.cc b/compiler/optimizing/code_generator_mips.cc index 990bbcc85b..bc8bb480ec 100644 --- a/compiler/optimizing/code_generator_mips.cc +++ b/compiler/optimizing/code_generator_mips.cc @@ -743,9 +743,12 @@ void CodeGeneratorMIPS::GenerateFrameEntry() { // TODO: __ cfi().RelOffset(DWARFReg(reg), ofs); } - // Store the current method pointer. - // TODO: can we not do this if RequiresCurrentMethod() returns false? - __ StoreToOffset(kStoreWord, kMethodRegisterArgument, SP, kCurrentMethodStackOffset); + // Save the current method if we need it. Note that we do not + // do this in HCurrentMethod, as the instruction might have been removed + // in the SSA graph. + if (RequiresCurrentMethod()) { + __ StoreToOffset(kStoreWord, kMethodRegisterArgument, SP, kCurrentMethodStackOffset); + } } void CodeGeneratorMIPS::GenerateFrameExit() { diff --git a/compiler/optimizing/code_generator_mips64.cc b/compiler/optimizing/code_generator_mips64.cc index 02576bda67..010bf24232 100644 --- a/compiler/optimizing/code_generator_mips64.cc +++ b/compiler/optimizing/code_generator_mips64.cc @@ -556,9 +556,14 @@ void CodeGeneratorMIPS64::GenerateFrameEntry() { __ IncreaseFrameSize(GetFrameSize() - FrameEntrySpillSize()); - static_assert(IsInt<16>(kCurrentMethodStackOffset), - "kCurrentMethodStackOffset must fit into int16_t"); - __ Sd(kMethodRegisterArgument, SP, kCurrentMethodStackOffset); + // Save the current method if we need it. Note that we do not + // do this in HCurrentMethod, as the instruction might have been removed + // in the SSA graph. + if (RequiresCurrentMethod()) { + static_assert(IsInt<16>(kCurrentMethodStackOffset), + "kCurrentMethodStackOffset must fit into int16_t"); + __ Sd(kMethodRegisterArgument, SP, kCurrentMethodStackOffset); + } } void CodeGeneratorMIPS64::GenerateFrameExit() { diff --git a/compiler/optimizing/code_generator_x86.cc b/compiler/optimizing/code_generator_x86.cc index 0b23599665..960f01ce9d 100644 --- a/compiler/optimizing/code_generator_x86.cc +++ b/compiler/optimizing/code_generator_x86.cc @@ -898,7 +898,12 @@ void CodeGeneratorX86::GenerateFrameEntry() { int adjust = GetFrameSize() - FrameEntrySpillSize(); __ subl(ESP, Immediate(adjust)); __ cfi().AdjustCFAOffset(adjust); - __ movl(Address(ESP, kCurrentMethodStackOffset), kMethodRegisterArgument); + // Save the current method if we need it. Note that we do not + // do this in HCurrentMethod, as the instruction might have been removed + // in the SSA graph. + if (RequiresCurrentMethod()) { + __ movl(Address(ESP, kCurrentMethodStackOffset), kMethodRegisterArgument); + } } void CodeGeneratorX86::GenerateFrameExit() { diff --git a/compiler/optimizing/code_generator_x86_64.cc b/compiler/optimizing/code_generator_x86_64.cc index 28638d721d..665d028338 100644 --- a/compiler/optimizing/code_generator_x86_64.cc +++ b/compiler/optimizing/code_generator_x86_64.cc @@ -1140,8 +1140,13 @@ void CodeGeneratorX86_64::GenerateFrameEntry() { } } - __ movq(Address(CpuRegister(RSP), kCurrentMethodStackOffset), - CpuRegister(kMethodRegisterArgument)); + // Save the current method if we need it. Note that we do not + // do this in HCurrentMethod, as the instruction might have been removed + // in the SSA graph. + if (RequiresCurrentMethod()) { + __ movq(Address(CpuRegister(RSP), kCurrentMethodStackOffset), + CpuRegister(kMethodRegisterArgument)); + } } void CodeGeneratorX86_64::GenerateFrameExit() { diff --git a/compiler/optimizing/dead_code_elimination.cc b/compiler/optimizing/dead_code_elimination.cc index aa3f26809a..adfe09ba9f 100644 --- a/compiler/optimizing/dead_code_elimination.cc +++ b/compiler/optimizing/dead_code_elimination.cc @@ -343,14 +343,7 @@ void HDeadCodeElimination::RemoveDeadInstructions() { for (i.Advance(); !i.Done(); i.Advance()) { HInstruction* inst = i.Current(); DCHECK(!inst->IsControlFlow()); - if (!inst->HasSideEffects() - && !inst->CanThrow() - && !inst->IsSuspendCheck() - && !inst->IsNativeDebugInfo() - // If we added an explicit barrier then we should keep it. - && !inst->IsMemoryBarrier() - && !inst->IsParameterValue() - && !inst->HasUses()) { + if (inst->IsDeadAndRemovable()) { block->RemoveInstruction(inst); MaybeRecordStat(MethodCompilationStat::kRemovedDeadInstruction); } diff --git a/compiler/optimizing/induction_var_analysis.cc b/compiler/optimizing/induction_var_analysis.cc index c501ccf80f..55fcb12fa8 100644 --- a/compiler/optimizing/induction_var_analysis.cc +++ b/compiler/optimizing/induction_var_analysis.cc @@ -87,11 +87,12 @@ HInductionVarAnalysis::HInductionVarAnalysis(HGraph* graph) : HOptimization(graph, kInductionPassName), global_depth_(0), stack_(graph->GetArena()->Adapter(kArenaAllocInductionVarAnalysis)), - scc_(graph->GetArena()->Adapter(kArenaAllocInductionVarAnalysis)), map_(std::less<HInstruction*>(), graph->GetArena()->Adapter(kArenaAllocInductionVarAnalysis)), + scc_(graph->GetArena()->Adapter(kArenaAllocInductionVarAnalysis)), cycle_(std::less<HInstruction*>(), graph->GetArena()->Adapter(kArenaAllocInductionVarAnalysis)), + type_(Primitive::kPrimVoid), induction_(std::less<HLoopInformation*>(), graph->GetArena()->Adapter(kArenaAllocInductionVarAnalysis)) { } @@ -103,7 +104,6 @@ void HInductionVarAnalysis::Run() { for (HReversePostOrderIterator it_graph(*graph_); !it_graph.Done(); it_graph.Advance()) { HBasicBlock* graph_block = it_graph.Current(); // Don't analyze irreducible loops. - // TODO(ajcbik): could/should we remove this restriction? if (graph_block->IsLoopHeader() && !graph_block->GetLoopInformation()->IsIrreducible()) { VisitLoop(graph_block->GetLoopInformation()); } @@ -121,7 +121,7 @@ void HInductionVarAnalysis::VisitLoop(HLoopInformation* loop) { HBasicBlock* loop_block = it_loop.Current(); DCHECK(loop_block->IsInLoop()); if (loop_block->GetLoopInformation() != loop) { - continue; // Inner loops already visited. + continue; // Inner loops visited later. } // Visit phi-operations and instructions. for (HInstructionIterator it(loop_block->GetPhis()); !it.Done(); it.Advance()) { @@ -285,6 +285,9 @@ void HInductionVarAnalysis::ClassifyNonTrivial(HLoopInformation* loop) { } else if (instruction->IsSub()) { update = SolveAddSub( loop, phi, instruction, instruction->InputAt(0), instruction->InputAt(1), kSub, true); + } else if (instruction->IsXor()) { + update = SolveXor( + loop, phi, instruction, instruction->InputAt(0), instruction->InputAt(1), true); } else if (instruction->IsTypeConversion()) { update = SolveCnv(instruction->AsTypeConversion()); } @@ -553,6 +556,27 @@ HInductionVarAnalysis::InductionInfo* HInductionVarAnalysis::SolveAddSub(HLoopIn return nullptr; } +HInductionVarAnalysis::InductionInfo* HInductionVarAnalysis::SolveXor(HLoopInformation* loop, + HInstruction* entry_phi, + HInstruction* instruction, + HInstruction* x, + HInstruction* y, + bool is_first_call) { + InductionInfo* b = LookupInfo(loop, y); + // Solve within a tight cycle on x = x ^ c. + if (b != nullptr && b->induction_class == kInvariant) { + if (x == entry_phi && entry_phi->InputCount() == 2 && instruction == entry_phi->InputAt(1)) { + InductionInfo* initial = LookupInfo(loop, entry_phi->InputAt(0)); + return CreateInduction(kPeriodic, CreateInvariantOp(kXor, initial, b), initial, type_); + } + } + // Try the other way around if considered for first time. + if (is_first_call) { + return SolveXor(loop, entry_phi, instruction, y, x, false); + } + return nullptr; +} + HInductionVarAnalysis::InductionInfo* HInductionVarAnalysis::SolveCnv(HTypeConversion* conversion) { Primitive::Type from = conversion->GetInputType(); Primitive::Type to = conversion->GetResultType(); @@ -850,8 +874,8 @@ HInductionVarAnalysis::InductionInfo* HInductionVarAnalysis::CreateSimplifiedInv int64_t value = -1; if (IsExact(a, &value)) { if (value == 0) { - // Simplify 0 + b = b, 0 * b = 0. - if (op == kAdd) { + // Simplify 0 + b = b, 0 ^ b = b, 0 * b = 0. + if (op == kAdd || op == kXor) { return b; } else if (op == kMul) { return a; @@ -867,8 +891,8 @@ HInductionVarAnalysis::InductionInfo* HInductionVarAnalysis::CreateSimplifiedInv } if (IsExact(b, &value)) { if (value == 0) { - // Simplify a + 0 = a, a - 0 = a, a * 0 = 0, -0 = 0. - if (op == kAdd || op == kSub) { + // Simplify a + 0 = a, a - 0 = a, a ^ 0 = a, a * 0 = 0, -0 = 0. + if (op == kAdd || op == kSub || op == kXor) { return a; } else if (op == kMul || op == kNeg) { return b; @@ -939,6 +963,7 @@ std::string HInductionVarAnalysis::InductionToString(InductionInfo* info) { case kNeg: inv += " - "; break; case kMul: inv += " * "; break; case kDiv: inv += " / "; break; + case kXor: inv += " ^ "; break; case kLT: inv += " < "; break; case kLE: inv += " <= "; break; case kGT: inv += " > "; break; diff --git a/compiler/optimizing/induction_var_analysis.h b/compiler/optimizing/induction_var_analysis.h index cd4c830645..06aee31b88 100644 --- a/compiler/optimizing/induction_var_analysis.h +++ b/compiler/optimizing/induction_var_analysis.h @@ -64,6 +64,7 @@ class HInductionVarAnalysis : public HOptimization { kNeg, kMul, kDiv, + kXor, kFetch, // Trip-counts. kTripCountInLoop, // valid in full loop; loop is finite @@ -171,7 +172,13 @@ class HInductionVarAnalysis : public HOptimization { HInstruction* x, HInstruction* y, InductionOp op, - bool is_first_call); + bool is_first_call); // possibly swaps x and y to try again + InductionInfo* SolveXor(HLoopInformation* loop, + HInstruction* entry_phi, + HInstruction* instruction, + HInstruction* x, + HInstruction* y, + bool is_first_call); // possibly swaps x and y to try again InductionInfo* SolveCnv(HTypeConversion* conversion); // Trip count information. @@ -219,8 +226,8 @@ class HInductionVarAnalysis : public HOptimization { // Temporary book-keeping during the analysis. uint32_t global_depth_; ArenaVector<HInstruction*> stack_; - ArenaVector<HInstruction*> scc_; ArenaSafeMap<HInstruction*, NodeInfo> map_; + ArenaVector<HInstruction*> scc_; ArenaSafeMap<HInstruction*, InductionInfo*> cycle_; Primitive::Type type_; diff --git a/compiler/optimizing/induction_var_analysis_test.cc b/compiler/optimizing/induction_var_analysis_test.cc index 292bc4e06e..7c467f6c94 100644 --- a/compiler/optimizing/induction_var_analysis_test.cc +++ b/compiler/optimizing/induction_var_analysis_test.cc @@ -107,7 +107,7 @@ class InductionVarAnalysisTest : public CommonCompilerTest { } // Builds if-statement at depth d. - HPhi* BuildIf(int d, HBasicBlock** ifT, HBasicBlock **ifF) { + HPhi* BuildIf(int d, HBasicBlock** ifT, HBasicBlock** ifF) { HBasicBlock* cond = new (&allocator_) HBasicBlock(graph_); HBasicBlock* ifTrue = new (&allocator_) HBasicBlock(graph_); HBasicBlock* ifFalse = new (&allocator_) HBasicBlock(graph_); @@ -259,15 +259,15 @@ TEST_F(InductionVarAnalysisTest, FindDerivedInduction) { // k = - i; // } BuildLoopNest(1); - HInstruction *add = InsertInstruction( + HInstruction* add = InsertInstruction( new (&allocator_) HAdd(Primitive::kPrimInt, constant100_, basic_[0]), 0); - HInstruction *sub = InsertInstruction( + HInstruction* sub = InsertInstruction( new (&allocator_) HSub(Primitive::kPrimInt, constant100_, basic_[0]), 0); - HInstruction *mul = InsertInstruction( + HInstruction* mul = InsertInstruction( new (&allocator_) HMul(Primitive::kPrimInt, constant100_, basic_[0]), 0); - HInstruction *shl = InsertInstruction( + HInstruction* shl = InsertInstruction( new (&allocator_) HShl(Primitive::kPrimInt, basic_[0], constant1_), 0); - HInstruction *neg = InsertInstruction( + HInstruction* neg = InsertInstruction( new (&allocator_) HNeg(Primitive::kPrimInt, basic_[0]), 0); PerformInductionVarAnalysis(); @@ -291,10 +291,10 @@ TEST_F(InductionVarAnalysisTest, FindChainInduction) { HPhi* k = InsertLoopPhi(0, 0); k->AddInput(constant0_); - HInstruction *add = InsertInstruction( + HInstruction* add = InsertInstruction( new (&allocator_) HAdd(Primitive::kPrimInt, k, constant100_), 0); HInstruction* store1 = InsertArrayStore(add, 0); - HInstruction *sub = InsertInstruction( + HInstruction* sub = InsertInstruction( new (&allocator_) HSub(Primitive::kPrimInt, add, constant1_), 0); HInstruction* store2 = InsertArrayStore(sub, 0); k->AddInput(sub); @@ -381,7 +381,7 @@ TEST_F(InductionVarAnalysisTest, FindFirstOrderWrapAroundInduction) { k->AddInput(constant0_); HInstruction* store = InsertArrayStore(k, 0); - HInstruction *sub = InsertInstruction( + HInstruction* sub = InsertInstruction( new (&allocator_) HSub(Primitive::kPrimInt, constant100_, basic_[0]), 0); k->AddInput(sub); PerformInductionVarAnalysis(); @@ -407,7 +407,7 @@ TEST_F(InductionVarAnalysisTest, FindSecondOrderWrapAroundInduction) { HInstruction* store = InsertArrayStore(k, 0); k->AddInput(t); - HInstruction *sub = InsertInstruction( + HInstruction* sub = InsertInstruction( new (&allocator_) HSub(Primitive::kPrimInt, constant100_, basic_[0], 0), 0); t->AddInput(sub); PerformInductionVarAnalysis(); @@ -431,15 +431,15 @@ TEST_F(InductionVarAnalysisTest, FindWrapAroundDerivedInduction) { HPhi* k = InsertLoopPhi(0, 0); k->AddInput(constant0_); - HInstruction *add = InsertInstruction( + HInstruction* add = InsertInstruction( new (&allocator_) HAdd(Primitive::kPrimInt, k, constant100_), 0); - HInstruction *sub = InsertInstruction( + HInstruction* sub = InsertInstruction( new (&allocator_) HSub(Primitive::kPrimInt, k, constant100_), 0); - HInstruction *mul = InsertInstruction( + HInstruction* mul = InsertInstruction( new (&allocator_) HMul(Primitive::kPrimInt, k, constant100_), 0); - HInstruction *shl = InsertInstruction( + HInstruction* shl = InsertInstruction( new (&allocator_) HShl(Primitive::kPrimInt, k, constant1_), 0); - HInstruction *neg = InsertInstruction( + HInstruction* neg = InsertInstruction( new (&allocator_) HNeg(Primitive::kPrimInt, k), 0); k->AddInput( InsertInstruction(new (&allocator_) HShl(Primitive::kPrimInt, basic_[0], constant1_), 0)); @@ -497,7 +497,7 @@ TEST_F(InductionVarAnalysisTest, FindIdiomaticPeriodicInduction) { k->AddInput(constant0_); HInstruction* store = InsertArrayStore(k, 0); - HInstruction *sub = InsertInstruction( + HInstruction* sub = InsertInstruction( new (&allocator_) HSub(Primitive::kPrimInt, constant1_, k), 0); k->AddInput(sub); PerformInductionVarAnalysis(); @@ -506,6 +506,45 @@ TEST_F(InductionVarAnalysisTest, FindIdiomaticPeriodicInduction) { EXPECT_STREQ("periodic((1), (0)):PrimInt", GetInductionInfo(sub, 0).c_str()); } +TEST_F(InductionVarAnalysisTest, FindXorPeriodicInduction) { + // Setup: + // k = 0; + // for (int i = 0; i < 100; i++) { + // a[k] = 0; + // k = k ^ 1; + // } + BuildLoopNest(1); + HPhi* k = InsertLoopPhi(0, 0); + k->AddInput(constant0_); + + HInstruction* store = InsertArrayStore(k, 0); + HInstruction* x = InsertInstruction( + new (&allocator_) HXor(Primitive::kPrimInt, k, constant1_), 0); + k->AddInput(x); + PerformInductionVarAnalysis(); + + EXPECT_STREQ("periodic((0), (1)):PrimInt", GetInductionInfo(store->InputAt(1), 0).c_str()); + EXPECT_STREQ("periodic((1), (0)):PrimInt", GetInductionInfo(x, 0).c_str()); +} + +TEST_F(InductionVarAnalysisTest, FindXor100PeriodicInduction) { + // Setup: + // k = 100; + // for (int i = 0; i < 100; i++) { + // k = k ^ 100; + // } + BuildLoopNest(1); + HPhi* k = InsertLoopPhi(0, 0); + k->AddInput(constant100_); + + HInstruction* x = InsertInstruction( + new (&allocator_) HXor(Primitive::kPrimInt, k, constant100_), 0); + k->AddInput(x); + PerformInductionVarAnalysis(); + + EXPECT_STREQ("periodic(((100) ^ (100)), (100)):PrimInt", GetInductionInfo(x, 0).c_str()); +} + TEST_F(InductionVarAnalysisTest, FindDerivedPeriodicInduction) { // Setup: // k = 0; @@ -526,15 +565,15 @@ TEST_F(InductionVarAnalysisTest, FindDerivedPeriodicInduction) { k_header->AddInput(k_body); // Derived expressions. - HInstruction *add = InsertInstruction( + HInstruction* add = InsertInstruction( new (&allocator_) HAdd(Primitive::kPrimInt, k_body, constant100_), 0); - HInstruction *sub = InsertInstruction( + HInstruction* sub = InsertInstruction( new (&allocator_) HSub(Primitive::kPrimInt, k_body, constant100_), 0); - HInstruction *mul = InsertInstruction( + HInstruction* mul = InsertInstruction( new (&allocator_) HMul(Primitive::kPrimInt, k_body, constant100_), 0); - HInstruction *shl = InsertInstruction( + HInstruction* shl = InsertInstruction( new (&allocator_) HShl(Primitive::kPrimInt, k_body, constant1_), 0); - HInstruction *neg = InsertInstruction( + HInstruction* neg = InsertInstruction( new (&allocator_) HNeg(Primitive::kPrimInt, k_body), 0); PerformInductionVarAnalysis(); @@ -563,7 +602,7 @@ TEST_F(InductionVarAnalysisTest, FindDeepLoopInduction) { k[d] = InsertLoopPhi(0, d); } - HInstruction *inc = InsertInstruction( + HInstruction* inc = InsertInstruction( new (&allocator_) HAdd(Primitive::kPrimInt, constant1_, k[9]), 9); HInstruction* store = InsertArrayStore(inc, 9); @@ -597,7 +636,7 @@ TEST_F(InductionVarAnalysisTest, ByteInductionIntLoopControl) { // a[i] = 0; // } BuildLoopNest(1); - HInstruction *conv = InsertInstruction( + HInstruction* conv = InsertInstruction( new (&allocator_) HTypeConversion(Primitive::kPrimByte, basic_[0], -1), 0); HInstruction* store1 = InsertArrayStore(conv, 0); HInstruction* store2 = InsertArrayStore(basic_[0], 0); diff --git a/compiler/optimizing/induction_var_range.cc b/compiler/optimizing/induction_var_range.cc index cd8b7c7960..140c7f0c40 100644 --- a/compiler/optimizing/induction_var_range.cc +++ b/compiler/optimizing/induction_var_range.cc @@ -525,6 +525,8 @@ InductionVarRange::Value InductionVarRange::GetVal(HInductionVarAnalysis::Induct return GetMul(info->op_a, info->op_b, trip, in_body, is_min); case HInductionVarAnalysis::kDiv: return GetDiv(info->op_a, info->op_b, trip, in_body, is_min); + case HInductionVarAnalysis::kXor: + return GetXor(info->op_a, info->op_b); case HInductionVarAnalysis::kFetch: return GetFetch(info->fetch, trip, in_body, is_min); case HInductionVarAnalysis::kTripCountInLoop: @@ -626,6 +628,21 @@ InductionVarRange::Value InductionVarRange::GetDiv(HInductionVarAnalysis::Induct return Value(); } +InductionVarRange::Value InductionVarRange::GetXor( + HInductionVarAnalysis::InductionInfo* info1, + HInductionVarAnalysis::InductionInfo* info2) const { + int64_t v1 = 0; + int64_t v2 = 0; + // Only accept exact values. + if (IsConstant(info1, kExact, &v1) && IsConstant(info2, kExact, &v2)) { + int64_t value = v1 ^ v2; + if (CanLongValueFitIntoInt(value)) { + return Value(static_cast<int32_t>(value)); + } + } + return Value(); +} + InductionVarRange::Value InductionVarRange::MulRangeAndConstant( int64_t value, HInductionVarAnalysis::InductionInfo* info, diff --git a/compiler/optimizing/induction_var_range.h b/compiler/optimizing/induction_var_range.h index 63850b34b8..895130064a 100644 --- a/compiler/optimizing/induction_var_range.h +++ b/compiler/optimizing/induction_var_range.h @@ -131,6 +131,14 @@ class InductionVarRange { */ void Replace(HInstruction* instruction, HInstruction* fetch, HInstruction* replacement); + /** + * Incrementally updates induction information for just the given loop. + */ + void ReVisit(HLoopInformation* loop) { + induction_analysis_->induction_.erase(loop); + induction_analysis_->VisitLoop(loop); + } + private: /* * Enum used in IsConstant() request. @@ -185,6 +193,8 @@ class InductionVarRange { HInductionVarAnalysis::InductionInfo* trip, bool in_body, bool is_min) const; + Value GetXor(HInductionVarAnalysis::InductionInfo* info1, + HInductionVarAnalysis::InductionInfo* info2) const; Value MulRangeAndConstant(int64_t value, HInductionVarAnalysis::InductionInfo* info, diff --git a/compiler/optimizing/inliner.h b/compiler/optimizing/inliner.h index 486626b1fe..a1dcd58a84 100644 --- a/compiler/optimizing/inliner.h +++ b/compiler/optimizing/inliner.h @@ -38,7 +38,7 @@ class HInliner : public HOptimization { const DexCompilationUnit& outer_compilation_unit, const DexCompilationUnit& caller_compilation_unit, CompilerDriver* compiler_driver, - StackHandleScopeCollection* handles, + VariableSizedHandleScope* handles, OptimizingCompilerStats* stats, size_t total_number_of_dex_registers, size_t depth) @@ -197,7 +197,7 @@ class HInliner : public HOptimization { const size_t total_number_of_dex_registers_; const size_t depth_; size_t number_of_inlined_instructions_; - StackHandleScopeCollection* const handles_; + VariableSizedHandleScope* const handles_; DISALLOW_COPY_AND_ASSIGN(HInliner); }; diff --git a/compiler/optimizing/linear_order.cc b/compiler/optimizing/linear_order.cc new file mode 100644 index 0000000000..3af212fa48 --- /dev/null +++ b/compiler/optimizing/linear_order.cc @@ -0,0 +1,129 @@ +/* + * Copyright (C) 2016 The Android Open Source Project + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +#include "linear_order.h" + +namespace art { + +static bool InSameLoop(HLoopInformation* first_loop, HLoopInformation* second_loop) { + return first_loop == second_loop; +} + +static bool IsLoop(HLoopInformation* info) { + return info != nullptr; +} + +static bool IsInnerLoop(HLoopInformation* outer, HLoopInformation* inner) { + return (inner != outer) + && (inner != nullptr) + && (outer != nullptr) + && inner->IsIn(*outer); +} + +// Helper method to update work list for linear order. +static void AddToListForLinearization(ArenaVector<HBasicBlock*>* worklist, HBasicBlock* block) { + HLoopInformation* block_loop = block->GetLoopInformation(); + auto insert_pos = worklist->rbegin(); // insert_pos.base() will be the actual position. + for (auto end = worklist->rend(); insert_pos != end; ++insert_pos) { + HBasicBlock* current = *insert_pos; + HLoopInformation* current_loop = current->GetLoopInformation(); + if (InSameLoop(block_loop, current_loop) + || !IsLoop(current_loop) + || IsInnerLoop(current_loop, block_loop)) { + // The block can be processed immediately. + break; + } + } + worklist->insert(insert_pos.base(), block); +} + +// Helper method to validate linear order. +static bool IsLinearOrderWellFormed(const HGraph* graph, ArenaVector<HBasicBlock*>* linear_order) { + for (HBasicBlock* header : graph->GetBlocks()) { + if (header == nullptr || !header->IsLoopHeader()) { + continue; + } + HLoopInformation* loop = header->GetLoopInformation(); + size_t num_blocks = loop->GetBlocks().NumSetBits(); + size_t found_blocks = 0u; + for (HBasicBlock* block : *linear_order) { + if (loop->Contains(*block)) { + found_blocks++; + if (found_blocks == 1u && block != header) { + // First block is not the header. + return false; + } else if (found_blocks == num_blocks && !loop->IsBackEdge(*block)) { + // Last block is not a back edge. + return false; + } + } else if (found_blocks != 0u && found_blocks != num_blocks) { + // Blocks are not adjacent. + return false; + } + } + DCHECK_EQ(found_blocks, num_blocks); + } + return true; +} + +void LinearizeGraph(const HGraph* graph, + ArenaAllocator* allocator, + ArenaVector<HBasicBlock*>* linear_order) { + DCHECK(linear_order->empty()); + // Create a reverse post ordering with the following properties: + // - Blocks in a loop are consecutive, + // - Back-edge is the last block before loop exits. + // + // (1): Record the number of forward predecessors for each block. This is to + // ensure the resulting order is reverse post order. We could use the + // current reverse post order in the graph, but it would require making + // order queries to a GrowableArray, which is not the best data structure + // for it. + ArenaVector<uint32_t> forward_predecessors(graph->GetBlocks().size(), + allocator->Adapter(kArenaAllocLinearOrder)); + for (HReversePostOrderIterator it(*graph); !it.Done(); it.Advance()) { + HBasicBlock* block = it.Current(); + size_t number_of_forward_predecessors = block->GetPredecessors().size(); + if (block->IsLoopHeader()) { + number_of_forward_predecessors -= block->GetLoopInformation()->NumberOfBackEdges(); + } + forward_predecessors[block->GetBlockId()] = number_of_forward_predecessors; + } + // (2): Following a worklist approach, first start with the entry block, and + // iterate over the successors. When all non-back edge predecessors of a + // successor block are visited, the successor block is added in the worklist + // following an order that satisfies the requirements to build our linear graph. + linear_order->reserve(graph->GetReversePostOrder().size()); + ArenaVector<HBasicBlock*> worklist(allocator->Adapter(kArenaAllocLinearOrder)); + worklist.push_back(graph->GetEntryBlock()); + do { + HBasicBlock* current = worklist.back(); + worklist.pop_back(); + linear_order->push_back(current); + for (HBasicBlock* successor : current->GetSuccessors()) { + int block_id = successor->GetBlockId(); + size_t number_of_remaining_predecessors = forward_predecessors[block_id]; + if (number_of_remaining_predecessors == 1) { + AddToListForLinearization(&worklist, successor); + } + forward_predecessors[block_id] = number_of_remaining_predecessors - 1; + } + } while (!worklist.empty()); + + DCHECK(graph->HasIrreducibleLoops() || IsLinearOrderWellFormed(graph, linear_order)); +} + +} // namespace art diff --git a/compiler/optimizing/linear_order.h b/compiler/optimizing/linear_order.h new file mode 100644 index 0000000000..cdbdd0714b --- /dev/null +++ b/compiler/optimizing/linear_order.h @@ -0,0 +1,45 @@ +/* + * Copyright (C) 2016 The Android Open Source Project + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +#ifndef ART_COMPILER_OPTIMIZING_LINEAR_ORDER_H_ +#define ART_COMPILER_OPTIMIZING_LINEAR_ORDER_H_ + +#include "nodes.h" + +namespace art { + +// Linearizes the 'graph' such that: +// (1): a block is always after its dominator, +// (2): blocks of loops are contiguous. +// +// Storage is obtained through 'allocator' and the linear order it computed +// into 'linear_order'. Once computed, iteration can be expressed as: +// +// for (HBasicBlock* block : linear_order) // linear order +// +// for (HBasicBlock* block : LinearPostOrder(linear_order)) // linear post order +// +void LinearizeGraph(const HGraph* graph, + ArenaAllocator* allocator, + ArenaVector<HBasicBlock*>* linear_order); + +inline auto LinearPostOrder(const ArenaVector<HBasicBlock*>& linear_order) { + return MakeIterationRange(linear_order.rbegin(), linear_order.rend()); +} + +} // namespace art + +#endif // ART_COMPILER_OPTIMIZING_LINEAR_ORDER_H_ diff --git a/compiler/optimizing/loop_optimization.cc b/compiler/optimizing/loop_optimization.cc index b12a7f76c6..33fa87d568 100644 --- a/compiler/optimizing/loop_optimization.cc +++ b/compiler/optimizing/loop_optimization.cc @@ -16,21 +16,20 @@ #include "loop_optimization.h" -#include "base/arena_containers.h" -#include "induction_var_range.h" -#include "ssa_liveness_analysis.h" -#include "nodes.h" +#include "linear_order.h" namespace art { // TODO: Generalize to cycles, as found by induction analysis? -static bool IsPhiAddSub(HPhi* phi, /*out*/ HInstruction** addsub_out) { +static bool IsPhiInduction(HPhi* phi, ArenaSet<HInstruction*>* iset) { + DCHECK(iset->empty()); HInputsRef inputs = phi->GetInputs(); if (inputs.size() == 2 && (inputs[1]->IsAdd() || inputs[1]->IsSub())) { HInstruction* addsub = inputs[1]; if (addsub->InputAt(0) == phi || addsub->InputAt(1) == phi) { if (addsub->GetUses().HasExactlyOneElement()) { - *addsub_out = addsub; + iset->insert(phi); + iset->insert(addsub); return true; } } @@ -38,39 +37,23 @@ static bool IsPhiAddSub(HPhi* phi, /*out*/ HInstruction** addsub_out) { return false; } -static bool IsOnlyUsedAfterLoop(const HLoopInformation& loop_info, - HPhi* phi, HInstruction* addsub) { - for (const HUseListNode<HInstruction*>& use : phi->GetUses()) { - if (use.GetUser() != addsub) { - HLoopInformation* other_loop_info = use.GetUser()->GetBlock()->GetLoopInformation(); - if (other_loop_info != nullptr && other_loop_info->IsIn(loop_info)) { - return false; - } - } - } - return true; -} - // Find: phi: Phi(init, addsub) // s: SuspendCheck // c: Condition(phi, bound) // i: If(c) // TODO: Find a less pattern matching approach? -static bool IsEmptyHeader(HBasicBlock* block, /*out*/ HInstruction** addsub) { +static bool IsEmptyHeader(HBasicBlock* block, ArenaSet<HInstruction*>* iset) { + DCHECK(iset->empty()); HInstruction* phi = block->GetFirstPhi(); - if (phi != nullptr && phi->GetNext() == nullptr && IsPhiAddSub(phi->AsPhi(), addsub)) { + if (phi != nullptr && phi->GetNext() == nullptr && IsPhiInduction(phi->AsPhi(), iset)) { HInstruction* s = block->GetFirstInstruction(); if (s != nullptr && s->IsSuspendCheck()) { HInstruction* c = s->GetNext(); if (c != nullptr && c->IsCondition() && c->GetUses().HasExactlyOneElement()) { HInstruction* i = c->GetNext(); if (i != nullptr && i->IsIf() && i->InputAt(0) == c) { - // Check that phi is only used inside loop as expected. - for (const HUseListNode<HInstruction*>& use : phi->GetUses()) { - if (use.GetUser() != *addsub && use.GetUser() != c) { - return false; - } - } + iset->insert(c); + iset->insert(s); return true; } } @@ -79,37 +62,11 @@ static bool IsEmptyHeader(HBasicBlock* block, /*out*/ HInstruction** addsub) { return false; } -static bool IsEmptyBody(HBasicBlock* block, HInstruction* addsub) { +static bool IsEmptyBody(HBasicBlock* block, ArenaSet<HInstruction*>* iset) { HInstruction* phi = block->GetFirstPhi(); HInstruction* i = block->GetFirstInstruction(); - return phi == nullptr && i == addsub && i->GetNext() != nullptr && i->GetNext()->IsGoto(); -} - -static HBasicBlock* TryRemovePreHeader(HBasicBlock* preheader, HBasicBlock* entry_block) { - if (preheader->GetPredecessors().size() == 1) { - HBasicBlock* entry = preheader->GetSinglePredecessor(); - HInstruction* anchor = entry->GetLastInstruction(); - // If the pre-header has a single predecessor we can remove it too if - // either the pre-header just contains a goto, or if the predecessor - // is not the entry block so we can push instructions backward - // (moving computation into the entry block is too dangerous!). - if (preheader->GetFirstInstruction() == nullptr || - preheader->GetFirstInstruction()->IsGoto() || - (entry != entry_block && anchor->IsGoto())) { - // Push non-goto statements backward to empty the pre-header. - for (HInstructionIterator it(preheader->GetInstructions()); !it.Done(); it.Advance()) { - HInstruction* instruction = it.Current(); - if (!instruction->IsGoto()) { - if (!instruction->CanBeMoved()) { - return nullptr; // pushing failed to move all - } - it.Current()->MoveBefore(anchor); - } - } - return entry; - } - } - return nullptr; + return phi == nullptr && iset->find(i) != iset->end() && + i->GetNext() != nullptr && i->GetNext()->IsGoto(); } static void RemoveFromCycle(HInstruction* instruction) { @@ -126,46 +83,56 @@ static void RemoveFromCycle(HInstruction* instruction) { HLoopOptimization::HLoopOptimization(HGraph* graph, HInductionVarAnalysis* induction_analysis) - : HLoopOptimization(graph, induction_analysis, nullptr) {} - -HLoopOptimization::HLoopOptimization(HGraph* graph, - HInductionVarAnalysis* induction_analysis, - ArenaAllocator* allocator) : HOptimization(graph, kLoopOptimizationPassName), induction_range_(induction_analysis), - loop_allocator_(allocator), + loop_allocator_(nullptr), top_loop_(nullptr), - last_loop_(nullptr) { + last_loop_(nullptr), + iset_(nullptr), + induction_simplication_count_(0) { } void HLoopOptimization::Run() { // Well-behaved loops only. // TODO: make this less of a sledgehammer. - if (graph_-> HasTryCatch() || graph_->HasIrreducibleLoops()) { + if (graph_->HasTryCatch() || graph_->HasIrreducibleLoops()) { return; } + // Phase-local allocator that draws from the global pool. Since the allocator + // itself resides on the stack, it is destructed on exiting Run(), which + // implies its underlying memory is released immediately. ArenaAllocator allocator(graph_->GetArena()->GetArenaPool()); - if (loop_allocator_ == nullptr) { - loop_allocator_ = &allocator; - } + loop_allocator_ = &allocator; + + // Perform loop optimizations. + LocalRun(); + + // Detach. + loop_allocator_ = nullptr; + last_loop_ = top_loop_ = nullptr; +} + +void HLoopOptimization::LocalRun() { + // Build the linear order using the phase-local allocator. This step enables building + // a loop hierarchy that properly reflects the outer-inner and previous-next relation. + ArenaVector<HBasicBlock*> linear_order(loop_allocator_->Adapter(kArenaAllocLinearOrder)); + LinearizeGraph(graph_, loop_allocator_, &linear_order); - // Build the linear order. This step enables building a loop hierarchy that - // properly reflects the outer-inner and previous-next relation. - graph_->Linearize(); // Build the loop hierarchy. - for (HLinearOrderIterator it_graph(*graph_); !it_graph.Done(); it_graph.Advance()) { - HBasicBlock* block = it_graph.Current(); + for (HBasicBlock* block : linear_order) { if (block->IsLoopHeader()) { AddLoop(block->GetLoopInformation()); } } + + // Traverse the loop hierarchy inner-to-outer and optimize. Traversal can use + // a temporary set that stores instructions using the phase-local allocator. if (top_loop_ != nullptr) { - // Traverse the loop hierarchy inner-to-outer and optimize. + ArenaSet<HInstruction*> iset(loop_allocator_->Adapter(kArenaAllocLoopOptimization)); + iset_ = &iset; TraverseLoopsInnerToOuter(top_loop_); - } - if (loop_allocator_ == &allocator) { - loop_allocator_ = nullptr; + iset_ = nullptr; // detach } } @@ -195,18 +162,40 @@ void HLoopOptimization::AddLoop(HLoopInformation* loop_info) { void HLoopOptimization::RemoveLoop(LoopNode* node) { DCHECK(node != nullptr); - // TODO: implement when needed (for current set of optimizations, we don't - // need to keep recorded loop hierarchy up to date, but as we get different - // traversal, we may want to remove the node from the hierarchy here. + DCHECK(node->inner == nullptr); + if (node->previous != nullptr) { + // Within sequence. + node->previous->next = node->next; + if (node->next != nullptr) { + node->next->previous = node->previous; + } + } else { + // First of sequence. + if (node->outer != nullptr) { + node->outer->inner = node->next; + } else { + top_loop_ = node->next; + } + if (node->next != nullptr) { + node->next->outer = node->outer; + node->next->previous = nullptr; + } + } } void HLoopOptimization::TraverseLoopsInnerToOuter(LoopNode* node) { for ( ; node != nullptr; node = node->next) { + int current_induction_simplification_count = induction_simplication_count_; if (node->inner != nullptr) { TraverseLoopsInnerToOuter(node->inner); } - // Visit loop after its inner loops have been visited. + // Visit loop after its inner loops have been visited. If the induction of any inner + // loop has been simplified, recompute the induction information of this loop first. + if (current_induction_simplification_count != induction_simplication_count_) { + induction_range_.ReVisit(node->loop_info); + } SimplifyInduction(node); + SimplifyBlocks(node); RemoveIfEmptyLoop(node); } } @@ -214,34 +203,50 @@ void HLoopOptimization::TraverseLoopsInnerToOuter(LoopNode* node) { void HLoopOptimization::SimplifyInduction(LoopNode* node) { HBasicBlock* header = node->loop_info->GetHeader(); HBasicBlock* preheader = node->loop_info->GetPreHeader(); - // Scan the phis in the header to find opportunities to optimize induction. + // Scan the phis in the header to find opportunities to simplify an induction + // cycle that is only used outside the loop. Replace these uses, if any, with + // the last value and remove the induction cycle. + // Examples: for (int i = 0; x != null; i++) { .... no i .... } + // for (int i = 0; i < 10; i++, k++) { .... no k .... } return k; for (HInstructionIterator it(header->GetPhis()); !it.Done(); it.Advance()) { HPhi* phi = it.Current()->AsPhi(); - HInstruction* addsub = nullptr; - // Find phi-add/sub cycle. - if (IsPhiAddSub(phi, &addsub)) { - // Simple case, the induction is only used by itself. Although redundant, - // later phases do not easily detect this property. Thus, eliminate here. - // Example: for (int i = 0; x != null; i++) { .... no i .... } - if (phi->GetUses().HasExactlyOneElement()) { - // Remove the cycle, including all uses. Even environment uses can be removed, - // since these computations have no effect at all. - RemoveFromCycle(phi); // removes environment uses too - RemoveFromCycle(addsub); - continue; + iset_->clear(); + int32_t use_count = 0; + if (IsPhiInduction(phi, iset_) && + IsOnlyUsedAfterLoop(node->loop_info, phi, &use_count) && + TryReplaceWithLastValue(phi, use_count, preheader)) { + for (HInstruction* i : *iset_) { + RemoveFromCycle(i); } - // Closed form case. Only the last value of the induction is needed. Remove all - // overhead from the loop, and replace subsequent uses with the last value. - // Example: for (int i = 0; i < 10; i++, k++) { .... no k .... } return k; - if (IsOnlyUsedAfterLoop(*node->loop_info, phi, addsub) && - induction_range_.CanGenerateLastValue(phi)) { - HInstruction* last = induction_range_.GenerateLastValue(phi, graph_, preheader); - // Remove the cycle, replacing all uses. Even environment uses can consume the final - // value, since any first real use is outside the loop (although this may imply - // that deopting may look "ahead" a bit on the phi value). - ReplaceAllUses(phi, last, addsub); - RemoveFromCycle(phi); // removes environment uses too - RemoveFromCycle(addsub); + induction_simplication_count_++; + } + } +} + +void HLoopOptimization::SimplifyBlocks(LoopNode* node) { + for (HBlocksInLoopIterator it(*node->loop_info); !it.Done(); it.Advance()) { + HBasicBlock* block = it.Current(); + // Remove instructions that are dead, usually resulting from eliminating induction cycles. + for (HBackwardInstructionIterator i(block->GetInstructions()); !i.Done(); i.Advance()) { + HInstruction* instruction = i.Current(); + if (instruction->IsDeadAndRemovable()) { + block->RemoveInstruction(instruction); + } + } + // Remove trivial control flow blocks from the loop body, again usually resulting + // from eliminating induction cycles. + if (block->GetPredecessors().size() == 1 && + block->GetSuccessors().size() == 1 && + block->GetFirstInstruction()->IsGoto()) { + HBasicBlock* pred = block->GetSinglePredecessor(); + HBasicBlock* succ = block->GetSingleSuccessor(); + if (succ->GetPredecessors().size() == 1) { + pred->ReplaceSuccessor(block, succ); + block->ClearDominanceInformation(); + block->SetDominator(pred); // needed by next disconnect. + block->DisconnectAndDelete(); + pred->AddDominatedBlock(succ); + succ->SetDominator(pred); } } } @@ -267,48 +272,56 @@ void HLoopOptimization::RemoveIfEmptyLoop(LoopNode* node) { HBasicBlock* exit = (header->GetSuccessors()[0] == body) ? header->GetSuccessors()[1] : header->GetSuccessors()[0]; - // Ensure exit can only be reached by exiting loop (this seems typically the - // case anyway, and simplifies code generation below; TODO: perhaps relax?). + // Ensure exit can only be reached by exiting loop. if (exit->GetPredecessors().size() != 1) { return; } - // Detect an empty loop: no side effects other than plain iteration. - HInstruction* addsub = nullptr; - if (IsEmptyHeader(header, &addsub) && IsEmptyBody(body, addsub)) { - HBasicBlock* entry = TryRemovePreHeader(preheader, graph_->GetEntryBlock()); + // Detect an empty loop: no side effects other than plain iteration. Replace + // subsequent index uses, if any, with the last value and remove the loop. + iset_->clear(); + int32_t use_count = 0; + if (IsEmptyHeader(header, iset_) && + IsEmptyBody(body, iset_) && + IsOnlyUsedAfterLoop(node->loop_info, header->GetFirstPhi(), &use_count) && + TryReplaceWithLastValue(header->GetFirstPhi(), use_count, preheader)) { body->DisconnectAndDelete(); exit->RemovePredecessor(header); header->RemoveSuccessor(exit); header->ClearDominanceInformation(); header->SetDominator(preheader); // needed by next disconnect. header->DisconnectAndDelete(); - // If allowed, remove preheader too, which may expose next outer empty loop - // Otherwise, link preheader directly to exit to restore the flow graph. - if (entry != nullptr) { - entry->ReplaceSuccessor(preheader, exit); - entry->AddDominatedBlock(exit); - exit->SetDominator(entry); - preheader->DisconnectAndDelete(); - } else { - preheader->AddSuccessor(exit); - preheader->AddInstruction(new (graph_->GetArena()) HGoto()); // global allocator - preheader->AddDominatedBlock(exit); - exit->SetDominator(preheader); - } + preheader->AddSuccessor(exit); + preheader->AddInstruction(new (graph_->GetArena()) HGoto()); // global allocator + preheader->AddDominatedBlock(exit); + exit->SetDominator(preheader); // Update hierarchy. RemoveLoop(node); } } -void HLoopOptimization::ReplaceAllUses(HInstruction* instruction, - HInstruction* replacement, - HInstruction* exclusion) { +bool HLoopOptimization::IsOnlyUsedAfterLoop(HLoopInformation* loop_info, + HInstruction* instruction, + /*out*/ int32_t* use_count) { + for (const HUseListNode<HInstruction*>& use : instruction->GetUses()) { + HInstruction* user = use.GetUser(); + if (iset_->find(user) == iset_->end()) { // not excluded? + HLoopInformation* other_loop_info = user->GetBlock()->GetLoopInformation(); + if (other_loop_info != nullptr && other_loop_info->IsIn(*loop_info)) { + return false; + } + ++*use_count; + } + } + return true; +} + +void HLoopOptimization::ReplaceAllUses(HInstruction* instruction, HInstruction* replacement) { const HUseList<HInstruction*>& uses = instruction->GetUses(); for (auto it = uses.begin(), end = uses.end(); it != end;) { HInstruction* user = it->GetUser(); size_t index = it->GetIndex(); ++it; // increment before replacing - if (user != exclusion) { + if (iset_->find(user) == iset_->end()) { // not excluded? user->ReplaceInput(replacement, index); induction_range_.Replace(user, instruction, replacement); // update induction } @@ -318,7 +331,7 @@ void HLoopOptimization::ReplaceAllUses(HInstruction* instruction, HEnvironment* user = it->GetUser(); size_t index = it->GetIndex(); ++it; // increment before replacing - if (user->GetHolder() != exclusion) { + if (iset_->find(user->GetHolder()) == iset_->end()) { // not excluded? user->RemoveAsUserOfInput(index); user->SetRawEnvAt(index, replacement); replacement->AddEnvUseAt(user, index); @@ -326,4 +339,20 @@ void HLoopOptimization::ReplaceAllUses(HInstruction* instruction, } } +bool HLoopOptimization::TryReplaceWithLastValue(HInstruction* instruction, + int32_t use_count, + HBasicBlock* block) { + // If true uses appear after the loop, replace these uses with the last value. Environment + // uses can consume this value too, since any first true use is outside the loop (although + // this may imply that de-opting may look "ahead" a bit on the phi value). If there are only + // environment uses, the value is dropped altogether, since the computations have no effect. + if (use_count > 0) { + if (!induction_range_.CanGenerateLastValue(instruction)) { + return false; + } + ReplaceAllUses(instruction, induction_range_.GenerateLastValue(instruction, graph_, block)); + } + return true; +} + } // namespace art diff --git a/compiler/optimizing/loop_optimization.h b/compiler/optimizing/loop_optimization.h index 591e45a7fb..9c4b462a1f 100644 --- a/compiler/optimizing/loop_optimization.h +++ b/compiler/optimizing/loop_optimization.h @@ -17,8 +17,6 @@ #ifndef ART_COMPILER_OPTIMIZING_LOOP_OPTIMIZATION_H_ #define ART_COMPILER_OPTIMIZING_LOOP_OPTIMIZATION_H_ -#include <string> - #include "induction_var_range.h" #include "nodes.h" #include "optimization.h" @@ -32,9 +30,6 @@ namespace art { class HLoopOptimization : public HOptimization { public: HLoopOptimization(HGraph* graph, HInductionVarAnalysis* induction_analysis); - HLoopOptimization(HGraph* graph, - HInductionVarAnalysis* induction_analysis, - ArenaAllocator* allocator); void Run() OVERRIDE; @@ -44,43 +39,60 @@ class HLoopOptimization : public HOptimization { /** * A single loop inside the loop hierarchy representation. */ - struct LoopNode : public ArenaObject<kArenaAllocInductionVarAnalysis> { + struct LoopNode : public ArenaObject<kArenaAllocLoopOptimization> { explicit LoopNode(HLoopInformation* lp_info) : loop_info(lp_info), outer(nullptr), inner(nullptr), previous(nullptr), next(nullptr) {} - const HLoopInformation* const loop_info; + HLoopInformation* const loop_info; LoopNode* outer; LoopNode* inner; LoopNode* previous; LoopNode* next; }; + void LocalRun(); + void AddLoop(HLoopInformation* loop_info); void RemoveLoop(LoopNode* node); void TraverseLoopsInnerToOuter(LoopNode* node); void SimplifyInduction(LoopNode* node); + void SimplifyBlocks(LoopNode* node); void RemoveIfEmptyLoop(LoopNode* node); - void ReplaceAllUses(HInstruction* instruction, - HInstruction* replacement, - HInstruction* exclusion); + bool IsOnlyUsedAfterLoop(HLoopInformation* loop_info, + HInstruction* instruction, + /*out*/ int32_t* use_count); + void ReplaceAllUses(HInstruction* instruction, HInstruction* replacement); + bool TryReplaceWithLastValue(HInstruction* instruction, + int32_t use_count, + HBasicBlock* block); - // Range analysis based on induction variables. + // Range information based on prior induction variable analysis. InductionVarRange induction_range_; // Phase-local heap memory allocator for the loop optimizer. Storage obtained - // through this allocator is released when the loop optimizer is done. + // through this allocator is immediately released when the loop optimizer is done. ArenaAllocator* loop_allocator_; - // Entries into the loop hierarchy representation. + // Entries into the loop hierarchy representation. The hierarchy resides + // in phase-local heap memory. LoopNode* top_loop_; LoopNode* last_loop_; + // Temporary bookkeeping of a set of instructions. + // Contents reside in phase-local heap memory. + ArenaSet<HInstruction*>* iset_; + + // Counter that tracks how many induction cycles have been simplified. Useful + // to trigger incremental updates of induction variable analysis of outer loops + // when the induction of inner loops has changed. + int32_t induction_simplication_count_; + friend class LoopOptimizationTest; DISALLOW_COPY_AND_ASSIGN(HLoopOptimization); diff --git a/compiler/optimizing/loop_optimization_test.cc b/compiler/optimizing/loop_optimization_test.cc index 4d54afd14d..7805a69a06 100644 --- a/compiler/optimizing/loop_optimization_test.cc +++ b/compiler/optimizing/loop_optimization_test.cc @@ -31,7 +31,7 @@ class LoopOptimizationTest : public CommonCompilerTest { allocator_(&pool_), graph_(CreateGraph(&allocator_)), iva_(new (&allocator_) HInductionVarAnalysis(graph_)), - loop_opt_(new (&allocator_) HLoopOptimization(graph_, iva_, &allocator_)) { + loop_opt_(new (&allocator_) HLoopOptimization(graph_, iva_)) { BuildGraph(); } @@ -76,7 +76,9 @@ class LoopOptimizationTest : public CommonCompilerTest { void PerformAnalysis() { graph_->BuildDominatorTree(); iva_->Run(); - loop_opt_->Run(); + // Do not release the loop hierarchy. + loop_opt_->loop_allocator_ = &allocator_; + loop_opt_->LocalRun(); } /** Constructs string representation of computed loop hierarchy. */ diff --git a/compiler/optimizing/nodes.cc b/compiler/optimizing/nodes.cc index 1ff2252348..1e69966b98 100644 --- a/compiler/optimizing/nodes.cc +++ b/compiler/optimizing/nodes.cc @@ -35,7 +35,7 @@ namespace art { // double). static constexpr bool kEnableFloatingPointStaticEvaluation = (FLT_EVAL_METHOD == 0); -void HGraph::InitializeInexactObjectRTI(StackHandleScopeCollection* handles) { +void HGraph::InitializeInexactObjectRTI(VariableSizedHandleScope* handles) { ScopedObjectAccess soa(Thread::Current()); // Create the inexact Object reference type and store it in the HGraph. ClassLinker* linker = Runtime::Current()->GetClassLinker(); @@ -460,116 +460,6 @@ GraphAnalysisResult HGraph::AnalyzeLoops() const { return kAnalysisSuccess; } -static bool InSameLoop(HLoopInformation* first_loop, HLoopInformation* second_loop) { - return first_loop == second_loop; -} - -static bool IsLoop(HLoopInformation* info) { - return info != nullptr; -} - -static bool IsInnerLoop(HLoopInformation* outer, HLoopInformation* inner) { - return (inner != outer) - && (inner != nullptr) - && (outer != nullptr) - && inner->IsIn(*outer); -} - -// Helper method to update work list for linear order. -static void AddToListForLinearization(ArenaVector<HBasicBlock*>* worklist, HBasicBlock* block) { - HLoopInformation* block_loop = block->GetLoopInformation(); - auto insert_pos = worklist->rbegin(); // insert_pos.base() will be the actual position. - for (auto end = worklist->rend(); insert_pos != end; ++insert_pos) { - HBasicBlock* current = *insert_pos; - HLoopInformation* current_loop = current->GetLoopInformation(); - if (InSameLoop(block_loop, current_loop) - || !IsLoop(current_loop) - || IsInnerLoop(current_loop, block_loop)) { - // The block can be processed immediately. - break; - } - } - worklist->insert(insert_pos.base(), block); -} - -// Helper method to validate linear order. -static bool IsLinearOrderWellFormed(const HGraph& graph) { - for (HBasicBlock* header : graph.GetBlocks()) { - if (header == nullptr || !header->IsLoopHeader()) { - continue; - } - HLoopInformation* loop = header->GetLoopInformation(); - size_t num_blocks = loop->GetBlocks().NumSetBits(); - size_t found_blocks = 0u; - for (HLinearOrderIterator it(graph); !it.Done(); it.Advance()) { - HBasicBlock* current = it.Current(); - if (loop->Contains(*current)) { - found_blocks++; - if (found_blocks == 1u && current != header) { - // First block is not the header. - return false; - } else if (found_blocks == num_blocks && !loop->IsBackEdge(*current)) { - // Last block is not a back edge. - return false; - } - } else if (found_blocks != 0u && found_blocks != num_blocks) { - // Blocks are not adjacent. - return false; - } - } - DCHECK_EQ(found_blocks, num_blocks); - } - return true; -} - -// TODO: return order, and give only liveness analysis ownership of graph's linear_order_? -void HGraph::Linearize() { - linear_order_.clear(); - - // Create a reverse post ordering with the following properties: - // - Blocks in a loop are consecutive, - // - Back-edge is the last block before loop exits. - - // (1): Record the number of forward predecessors for each block. This is to - // ensure the resulting order is reverse post order. We could use the - // current reverse post order in the graph, but it would require making - // order queries to a GrowableArray, which is not the best data structure - // for it. - ArenaVector<uint32_t> forward_predecessors(blocks_.size(), - arena_->Adapter(kArenaAllocSsaLiveness)); - for (HReversePostOrderIterator it(*this); !it.Done(); it.Advance()) { - HBasicBlock* block = it.Current(); - size_t number_of_forward_predecessors = block->GetPredecessors().size(); - if (block->IsLoopHeader()) { - number_of_forward_predecessors -= block->GetLoopInformation()->NumberOfBackEdges(); - } - forward_predecessors[block->GetBlockId()] = number_of_forward_predecessors; - } - - // (2): Following a worklist approach, first start with the entry block, and - // iterate over the successors. When all non-back edge predecessors of a - // successor block are visited, the successor block is added in the worklist - // following an order that satisfies the requirements to build our linear graph. - linear_order_.reserve(GetReversePostOrder().size()); - ArenaVector<HBasicBlock*> worklist(arena_->Adapter(kArenaAllocSsaLiveness)); - worklist.push_back(GetEntryBlock()); - do { - HBasicBlock* current = worklist.back(); - worklist.pop_back(); - linear_order_.push_back(current); - for (HBasicBlock* successor : current->GetSuccessors()) { - int block_id = successor->GetBlockId(); - size_t number_of_remaining_predecessors = forward_predecessors[block_id]; - if (number_of_remaining_predecessors == 1) { - AddToListForLinearization(&worklist, successor); - } - forward_predecessors[block_id] = number_of_remaining_predecessors - 1; - } - } while (!worklist.empty()); - - DCHECK(HasIrreducibleLoops() || IsLinearOrderWellFormed(*this)); -} - void HLoopInformation::Dump(std::ostream& os) { os << "header: " << header_->GetBlockId() << std::endl; os << "pre header: " << GetPreHeader()->GetBlockId() << std::endl; diff --git a/compiler/optimizing/nodes.h b/compiler/optimizing/nodes.h index 5cfbf4249e..6f4f3c9505 100644 --- a/compiler/optimizing/nodes.h +++ b/compiler/optimizing/nodes.h @@ -336,7 +336,7 @@ class HGraph : public ArenaObject<kArenaAllocGraph> { } // Acquires and stores RTI of inexact Object to be used when creating HNullConstant. - void InitializeInexactObjectRTI(StackHandleScopeCollection* handles); + void InitializeInexactObjectRTI(VariableSizedHandleScope* handles); ArenaAllocator* GetArena() const { return arena_; } const ArenaVector<HBasicBlock*>& GetBlocks() const { return blocks_; } @@ -366,13 +366,6 @@ class HGraph : public ArenaObject<kArenaAllocGraph> { // is a throw-catch loop, i.e. the header is a catch block. GraphAnalysisResult AnalyzeLoops() const; - // Computes a linear order for the current graph (should be called before - // using HLinearOrderIterator). Linearizes the graph such that: - // (1): a block is always after its dominator, - // (2): blocks of loops are contiguous. - // This creates a natural and efficient ordering when visualizing live ranges. - void Linearize(); - // Iterate over blocks to compute try block membership. Needs reverse post // order and loop information. void ComputeTryBlockInformation(); @@ -1938,6 +1931,19 @@ class HInstruction : public ArenaObject<kArenaAllocInstruction> { return !HasEnvironmentUses() && GetUses().HasExactlyOneElement(); } + bool IsDeadAndRemovable() const { + return + !HasSideEffects() && + !CanThrow() && + !IsSuspendCheck() && + !IsControlFlow() && + !IsNativeDebugInfo() && + !IsParameterValue() && + !HasUses() && + // If we added an explicit barrier then we should keep it. + !IsMemoryBarrier(); + } + // Does this instruction strictly dominate `other_instruction`? // Returns false if this instruction and `other_instruction` are the same. // Aborts if this instruction and `other_instruction` are both phis. @@ -2087,10 +2093,10 @@ class HInstruction : public ArenaObject<kArenaAllocInstruction> { // to the current method. Such instructions are: // (1): Instructions that require an environment, as calling the runtime requires // to walk the stack and have the current method stored at a specific stack address. - // (2): Object literals like classes and strings, that are loaded from the dex cache - // fields of the current method. + // (2): HCurrentMethod, potentially used by HInvokeStaticOrDirect, HLoadString, or HLoadClass + // to access the dex cache. bool NeedsCurrentMethod() const { - return NeedsEnvironment() || IsLoadClass() || IsLoadString(); + return NeedsEnvironment() || IsCurrentMethod(); } // Returns whether the code generation of the instruction will require to have access @@ -6661,43 +6667,6 @@ class HPostOrderIterator : public ValueObject { DISALLOW_COPY_AND_ASSIGN(HPostOrderIterator); }; -class HLinearPostOrderIterator : public ValueObject { - public: - explicit HLinearPostOrderIterator(const HGraph& graph) - : order_(graph.GetLinearOrder()), index_(graph.GetLinearOrder().size()) {} - - bool Done() const { return index_ == 0; } - - HBasicBlock* Current() const { return order_[index_ - 1u]; } - - void Advance() { - --index_; - DCHECK_GE(index_, 0U); - } - - private: - const ArenaVector<HBasicBlock*>& order_; - size_t index_; - - DISALLOW_COPY_AND_ASSIGN(HLinearPostOrderIterator); -}; - -class HLinearOrderIterator : public ValueObject { - public: - explicit HLinearOrderIterator(const HGraph& graph) - : order_(graph.GetLinearOrder()), index_(0) {} - - bool Done() const { return index_ == order_.size(); } - HBasicBlock* Current() const { return order_[index_]; } - void Advance() { ++index_; } - - private: - const ArenaVector<HBasicBlock*>& order_; - size_t index_; - - DISALLOW_COPY_AND_ASSIGN(HLinearOrderIterator); -}; - // Iterator over the blocks that art part of the loop. Includes blocks part // of an inner loop. The order in which the blocks are iterated is on their // block id. diff --git a/compiler/optimizing/optimizing_compiler.cc b/compiler/optimizing/optimizing_compiler.cc index d6f8307ac2..4370a84bd2 100644 --- a/compiler/optimizing/optimizing_compiler.cc +++ b/compiler/optimizing/optimizing_compiler.cc @@ -319,7 +319,7 @@ class OptimizingCompiler FINAL : public Compiler { CompilerDriver* driver, const DexCompilationUnit& dex_compilation_unit, PassObserver* pass_observer, - StackHandleScopeCollection* handles) const; + VariableSizedHandleScope* handles) const; void RunOptimizations(HOptimization* optimizations[], size_t length, @@ -358,7 +358,7 @@ class OptimizingCompiler FINAL : public Compiler { CompilerDriver* driver, const DexCompilationUnit& dex_compilation_unit, PassObserver* pass_observer, - StackHandleScopeCollection* handles) const; + VariableSizedHandleScope* handles) const; void RunArchOptimizations(InstructionSet instruction_set, HGraph* graph, @@ -442,7 +442,7 @@ static HOptimization* BuildOptimization( CodeGenerator* codegen, CompilerDriver* driver, const DexCompilationUnit& dex_compilation_unit, - StackHandleScopeCollection* handles, + VariableSizedHandleScope* handles, SideEffectsAnalysis* most_recent_side_effects, HInductionVarAnalysis* most_recent_induction) { std::string opt_name = ConvertPassNameToOptimizationName(pass_name); @@ -524,7 +524,7 @@ static ArenaVector<HOptimization*> BuildOptimizations( CodeGenerator* codegen, CompilerDriver* driver, const DexCompilationUnit& dex_compilation_unit, - StackHandleScopeCollection* handles) { + VariableSizedHandleScope* handles) { // Few HOptimizations constructors require SideEffectsAnalysis or HInductionVarAnalysis // instances. This method assumes that each of them expects the nearest instance preceeding it // in the pass name list. @@ -570,7 +570,7 @@ void OptimizingCompiler::MaybeRunInliner(HGraph* graph, CompilerDriver* driver, const DexCompilationUnit& dex_compilation_unit, PassObserver* pass_observer, - StackHandleScopeCollection* handles) const { + VariableSizedHandleScope* handles) const { OptimizingCompilerStats* stats = compilation_stats_.get(); const CompilerOptions& compiler_options = driver->GetCompilerOptions(); bool should_inline = (compiler_options.GetInlineDepthLimit() > 0) @@ -707,7 +707,7 @@ void OptimizingCompiler::RunOptimizations(HGraph* graph, CompilerDriver* driver, const DexCompilationUnit& dex_compilation_unit, PassObserver* pass_observer, - StackHandleScopeCollection* handles) const { + VariableSizedHandleScope* handles) const { OptimizingCompilerStats* stats = compilation_stats_.get(); ArenaAllocator* arena = graph->GetArena(); if (driver->GetCompilerOptions().GetPassesToRun() != nullptr) { @@ -949,7 +949,7 @@ CodeGenerator* OptimizingCompiler::TryCompile(ArenaAllocator* arena, { ScopedObjectAccess soa(Thread::Current()); - StackHandleScopeCollection handles(soa.Self()); + VariableSizedHandleScope handles(soa.Self()); // Do not hold `mutator_lock_` between optimizations. ScopedThreadSuspension sts(soa.Self(), kNative); diff --git a/compiler/optimizing/optimizing_unit_test.h b/compiler/optimizing/optimizing_unit_test.h index 2a23c92f1f..58d90176cd 100644 --- a/compiler/optimizing/optimizing_unit_test.h +++ b/compiler/optimizing/optimizing_unit_test.h @@ -90,7 +90,7 @@ inline HGraph* CreateCFG(ArenaAllocator* allocator, { ScopedObjectAccess soa(Thread::Current()); - StackHandleScopeCollection handles(soa.Self()); + VariableSizedHandleScope handles(soa.Self()); HGraphBuilder builder(graph, *item, &handles, return_type); bool graph_built = (builder.BuildGraph() == kAnalysisSuccess); return graph_built ? graph : nullptr; diff --git a/compiler/optimizing/reference_type_propagation.cc b/compiler/optimizing/reference_type_propagation.cc index 45a3ce411e..83698adba4 100644 --- a/compiler/optimizing/reference_type_propagation.cc +++ b/compiler/optimizing/reference_type_propagation.cc @@ -35,7 +35,7 @@ static inline mirror::DexCache* FindDexCacheWithHint(Thread* self, } } -static inline ReferenceTypeInfo::TypeHandle GetRootHandle(StackHandleScopeCollection* handles, +static inline ReferenceTypeInfo::TypeHandle GetRootHandle(VariableSizedHandleScope* handles, ClassLinker::ClassRoot class_root, ReferenceTypeInfo::TypeHandle* cache) { if (!ReferenceTypeInfo::IsValidHandle(*cache)) { @@ -109,7 +109,7 @@ class ReferenceTypePropagation::RTPVisitor : public HGraphDelegateVisitor { ReferenceTypePropagation::ReferenceTypePropagation(HGraph* graph, Handle<mirror::DexCache> hint_dex_cache, - StackHandleScopeCollection* handles, + VariableSizedHandleScope* handles, bool is_first_run, const char* name) : HOptimization(graph, name), diff --git a/compiler/optimizing/reference_type_propagation.h b/compiler/optimizing/reference_type_propagation.h index 61428b2a45..4663471729 100644 --- a/compiler/optimizing/reference_type_propagation.h +++ b/compiler/optimizing/reference_type_propagation.h @@ -34,7 +34,7 @@ class ReferenceTypePropagation : public HOptimization { public: ReferenceTypePropagation(HGraph* graph, Handle<mirror::DexCache> hint_dex_cache, - StackHandleScopeCollection* handles, + VariableSizedHandleScope* handles, bool is_first_run, const char* name = kReferenceTypePropagationPassName); @@ -56,7 +56,7 @@ class ReferenceTypePropagation : public HOptimization { private: class HandleCache { public: - explicit HandleCache(StackHandleScopeCollection* handles) : handles_(handles) { } + explicit HandleCache(VariableSizedHandleScope* handles) : handles_(handles) { } template <typename T> MutableHandle<T> NewHandle(T* object) REQUIRES_SHARED(Locks::mutator_lock_) { @@ -74,7 +74,7 @@ class ReferenceTypePropagation : public HOptimization { ReferenceTypeInfo::TypeHandle GetThrowableClassHandle(); private: - StackHandleScopeCollection* handles_; + VariableSizedHandleScope* handles_; ReferenceTypeInfo::TypeHandle object_class_handle_; ReferenceTypeInfo::TypeHandle class_class_handle_; diff --git a/compiler/optimizing/reference_type_propagation_test.cc b/compiler/optimizing/reference_type_propagation_test.cc index 75a4eac538..b061c871b0 100644 --- a/compiler/optimizing/reference_type_propagation_test.cc +++ b/compiler/optimizing/reference_type_propagation_test.cc @@ -35,7 +35,7 @@ class ReferenceTypePropagationTest : public CommonCompilerTest { ~ReferenceTypePropagationTest() { } - void SetupPropagation(StackHandleScopeCollection* handles) { + void SetupPropagation(VariableSizedHandleScope* handles) { graph_->InitializeInexactObjectRTI(handles); propagation_ = new (&allocator_) ReferenceTypePropagation(graph_, Handle<mirror::DexCache>(), @@ -79,7 +79,7 @@ class ReferenceTypePropagationTest : public CommonCompilerTest { TEST_F(ReferenceTypePropagationTest, ProperSetup) { ScopedObjectAccess soa(Thread::Current()); - StackHandleScopeCollection handles(soa.Self()); + VariableSizedHandleScope handles(soa.Self()); SetupPropagation(&handles); EXPECT_TRUE(propagation_ != nullptr); @@ -88,7 +88,7 @@ TEST_F(ReferenceTypePropagationTest, ProperSetup) { TEST_F(ReferenceTypePropagationTest, MergeInvalidTypes) { ScopedObjectAccess soa(Thread::Current()); - StackHandleScopeCollection handles(soa.Self()); + VariableSizedHandleScope handles(soa.Self()); SetupPropagation(&handles); // Two invalid types. @@ -120,7 +120,7 @@ TEST_F(ReferenceTypePropagationTest, MergeInvalidTypes) { TEST_F(ReferenceTypePropagationTest, MergeValidTypes) { ScopedObjectAccess soa(Thread::Current()); - StackHandleScopeCollection handles(soa.Self()); + VariableSizedHandleScope handles(soa.Self()); SetupPropagation(&handles); // Same types. diff --git a/compiler/optimizing/register_allocation_resolver.cc b/compiler/optimizing/register_allocation_resolver.cc index ad7a8a393e..caf66474eb 100644 --- a/compiler/optimizing/register_allocation_resolver.cc +++ b/compiler/optimizing/register_allocation_resolver.cc @@ -17,6 +17,7 @@ #include "register_allocation_resolver.h" #include "code_generator.h" +#include "linear_order.h" #include "ssa_liveness_analysis.h" namespace art { @@ -141,8 +142,7 @@ void RegisterAllocationResolver::Resolve(ArrayRef<HInstruction* const> safepoint } // Resolve non-linear control flow across branches. Order does not matter. - for (HLinearOrderIterator it(*codegen_->GetGraph()); !it.Done(); it.Advance()) { - HBasicBlock* block = it.Current(); + for (HBasicBlock* block : codegen_->GetGraph()->GetLinearOrder()) { if (block->IsCatchBlock() || (block->IsLoopHeader() && block->GetLoopInformation()->IsIrreducible())) { // Instructions live at the top of catch blocks or irreducible loop header @@ -172,15 +172,14 @@ void RegisterAllocationResolver::Resolve(ArrayRef<HInstruction* const> safepoint } // Resolve phi inputs. Order does not matter. - for (HLinearOrderIterator it(*codegen_->GetGraph()); !it.Done(); it.Advance()) { - HBasicBlock* current = it.Current(); - if (current->IsCatchBlock()) { + for (HBasicBlock* block : codegen_->GetGraph()->GetLinearOrder()) { + if (block->IsCatchBlock()) { // Catch phi values are set at runtime by the exception delivery mechanism. } else { - for (HInstructionIterator inst_it(current->GetPhis()); !inst_it.Done(); inst_it.Advance()) { + for (HInstructionIterator inst_it(block->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->GetPredecessors()[i]; + for (size_t i = 0, e = block->GetPredecessors().size(); i < e; ++i) { + HBasicBlock* predecessor = block->GetPredecessors()[i]; DCHECK_EQ(predecessor->GetNormalSuccessors().size(), 1u); HInstruction* input = phi->InputAt(i); Location source = input->GetLiveInterval()->GetLocationAt( diff --git a/compiler/optimizing/register_allocator_graph_color.cc b/compiler/optimizing/register_allocator_graph_color.cc index 717839914d..961077419e 100644 --- a/compiler/optimizing/register_allocator_graph_color.cc +++ b/compiler/optimizing/register_allocator_graph_color.cc @@ -17,6 +17,7 @@ #include "register_allocator_graph_color.h" #include "code_generator.h" +#include "linear_order.h" #include "register_allocation_resolver.h" #include "ssa_liveness_analysis.h" #include "thread-inl.h" @@ -757,9 +758,7 @@ bool RegisterAllocatorGraphColor::Validate(bool log_fatal_on_failure) { } void RegisterAllocatorGraphColor::ProcessInstructions() { - for (HLinearPostOrderIterator it(*codegen_->GetGraph()); !it.Done(); it.Advance()) { - HBasicBlock* block = it.Current(); - + for (HBasicBlock* block : LinearPostOrder(codegen_->GetGraph()->GetLinearOrder())) { // Note that we currently depend on this ordering, since some helper // code is designed for linear scan register allocation. for (HBackwardInstructionIterator instr_it(block->GetInstructions()); diff --git a/compiler/optimizing/register_allocator_linear_scan.cc b/compiler/optimizing/register_allocator_linear_scan.cc index 6910c71ead..4e69bc8999 100644 --- a/compiler/optimizing/register_allocator_linear_scan.cc +++ b/compiler/optimizing/register_allocator_linear_scan.cc @@ -22,6 +22,7 @@ #include "base/bit_vector-inl.h" #include "base/enums.h" #include "code_generator.h" +#include "linear_order.h" #include "register_allocation_resolver.h" #include "ssa_liveness_analysis.h" @@ -108,8 +109,7 @@ void RegisterAllocatorLinearScan::AllocateRegisters() { // Since only parallel moves have been inserted during the register allocation, // these checks are mostly for making sure these moves have been added correctly. size_t current_liveness = 0; - for (HLinearOrderIterator it(*codegen_->GetGraph()); !it.Done(); it.Advance()) { - HBasicBlock* block = it.Current(); + for (HBasicBlock* block : codegen_->GetGraph()->GetLinearOrder()) { for (HInstructionIterator inst_it(block->GetPhis()); !inst_it.Done(); inst_it.Advance()) { HInstruction* instruction = inst_it.Current(); DCHECK_LE(current_liveness, instruction->GetLifetimePosition()); @@ -163,8 +163,7 @@ void RegisterAllocatorLinearScan::BlockRegisters(size_t start, size_t end, bool void RegisterAllocatorLinearScan::AllocateRegistersInternal() { // Iterate post-order, to ensure the list is sorted, and the last added interval // is the one with the lowest start position. - for (HLinearPostOrderIterator it(*codegen_->GetGraph()); !it.Done(); it.Advance()) { - HBasicBlock* block = it.Current(); + for (HBasicBlock* block : LinearPostOrder(codegen_->GetGraph()->GetLinearOrder())) { for (HBackwardInstructionIterator back_it(block->GetInstructions()); !back_it.Done(); back_it.Advance()) { ProcessInstruction(back_it.Current()); diff --git a/compiler/optimizing/ssa_builder.h b/compiler/optimizing/ssa_builder.h index d7360adef8..45dac54115 100644 --- a/compiler/optimizing/ssa_builder.h +++ b/compiler/optimizing/ssa_builder.h @@ -49,7 +49,7 @@ class SsaBuilder : public ValueObject { public: SsaBuilder(HGraph* graph, Handle<mirror::DexCache> dex_cache, - StackHandleScopeCollection* handles) + VariableSizedHandleScope* handles) : graph_(graph), dex_cache_(dex_cache), handles_(handles), @@ -116,7 +116,7 @@ class SsaBuilder : public ValueObject { HGraph* graph_; Handle<mirror::DexCache> dex_cache_; - StackHandleScopeCollection* const handles_; + VariableSizedHandleScope* const handles_; // True if types of ambiguous ArrayGets have been resolved. bool agets_fixed_; diff --git a/compiler/optimizing/ssa_liveness_analysis.cc b/compiler/optimizing/ssa_liveness_analysis.cc index 9ce34aa80b..76cf8fe1ae 100644 --- a/compiler/optimizing/ssa_liveness_analysis.cc +++ b/compiler/optimizing/ssa_liveness_analysis.cc @@ -18,12 +18,17 @@ #include "base/bit_vector-inl.h" #include "code_generator.h" +#include "linear_order.h" #include "nodes.h" namespace art { void SsaLivenessAnalysis::Analyze() { - graph_->Linearize(); + // Compute the linear order directly in the graph's data structure + // (there are no more following graph mutations). + LinearizeGraph(graph_, graph_->GetArena(), &graph_->linear_order_); + + // Liveness analysis. NumberInstructions(); ComputeLiveness(); } @@ -40,8 +45,7 @@ void SsaLivenessAnalysis::NumberInstructions() { // to differentiate between the start and end of an instruction. Adding 2 to // the lifetime position for each instruction ensures the start of an // instruction is different than the end of the previous instruction. - for (HLinearOrderIterator it(*graph_); !it.Done(); it.Advance()) { - HBasicBlock* block = it.Current(); + for (HBasicBlock* block : graph_->GetLinearOrder()) { block->SetLifetimeStart(lifetime_position); for (HInstructionIterator inst_it(block->GetPhis()); !inst_it.Done(); inst_it.Advance()) { @@ -83,8 +87,7 @@ void SsaLivenessAnalysis::NumberInstructions() { } void SsaLivenessAnalysis::ComputeLiveness() { - for (HLinearOrderIterator it(*graph_); !it.Done(); it.Advance()) { - HBasicBlock* block = it.Current(); + for (HBasicBlock* block : graph_->GetLinearOrder()) { block_infos_[block->GetBlockId()] = new (graph_->GetArena()) BlockInfo(graph_->GetArena(), *block, number_of_ssa_values_); } @@ -136,9 +139,7 @@ static void RecursivelyProcessInputs(HInstruction* current, void SsaLivenessAnalysis::ComputeLiveRanges() { // Do a post order visit, adding inputs of instructions live in the block where // that instruction is defined, and killing instructions that are being visited. - for (HLinearPostOrderIterator it(*graph_); !it.Done(); it.Advance()) { - HBasicBlock* block = it.Current(); - + for (HBasicBlock* block : LinearPostOrder(graph_->GetLinearOrder())) { BitVector* kill = GetKillSet(*block); BitVector* live_in = GetLiveInSet(*block); |