From 256c94b568f35f8f23feaaf9ea0d64ed1edab1d4 Mon Sep 17 00:00:00 2001 From: Nicolas Geoffray Date: Mon, 29 Apr 2019 10:55:09 +0100 Subject: Update induction ranges in superblock cloner. Because loop unrolling is part of a general loop optimization pass, it needs to update induction ranges as it will invalidate its instruction cache with new instructions. Bug: 131174583 Test: 696-loop Change-Id: Id3628efe316b58f69abbd9ebd43e891a8e42529f --- compiler/optimizing/loop_optimization.cc | 12 +++++++----- compiler/optimizing/superblock_cloner.cc | 21 +++++++++++++++++---- compiler/optimizing/superblock_cloner.h | 23 +++++++++++++++++------ compiler/optimizing/superblock_cloner_test.cc | 23 +++++++++++++---------- 4 files changed, 54 insertions(+), 25 deletions(-) (limited to 'compiler/optimizing') diff --git a/compiler/optimizing/loop_optimization.cc b/compiler/optimizing/loop_optimization.cc index 12b180d5ff..6c76ab858b 100644 --- a/compiler/optimizing/loop_optimization.cc +++ b/compiler/optimizing/loop_optimization.cc @@ -426,10 +426,12 @@ static void TryToEvaluateIfCondition(HIf* instruction, HGraph* graph) { } // Peel the first 'count' iterations of the loop. -static void PeelByCount(HLoopInformation* loop_info, int count) { +static void PeelByCount(HLoopInformation* loop_info, + int count, + InductionVarRange* induction_range) { for (int i = 0; i < count; i++) { // Perform peeling. - PeelUnrollSimpleHelper helper(loop_info); + PeelUnrollSimpleHelper helper(loop_info, induction_range); helper.DoPeeling(); } } @@ -799,7 +801,7 @@ bool HLoopOptimization::TryUnrollingForBranchPenaltyReduction(LoopAnalysisInfo* // Perform unrolling. HLoopInformation* loop_info = analysis_info->GetLoopInfo(); - PeelUnrollSimpleHelper helper(loop_info); + PeelUnrollSimpleHelper helper(loop_info, &induction_range_); helper.DoUnrolling(); // Remove the redundant loop check after unrolling. @@ -824,7 +826,7 @@ bool HLoopOptimization::TryPeelingForLoopInvariantExitsElimination(LoopAnalysisI if (generate_code) { // Perform peeling. - PeelUnrollSimpleHelper helper(loop_info); + PeelUnrollSimpleHelper helper(loop_info, &induction_range_); helper.DoPeeling(); // Statically evaluate loop check after peeling for loop invariant condition. @@ -870,7 +872,7 @@ bool HLoopOptimization::TryFullUnrolling(LoopAnalysisInfo* analysis_info, bool g // loop_body _/ loop_body _/ // HLoopInformation* loop_info = analysis_info->GetLoopInfo(); - PeelByCount(loop_info, trip_count); + PeelByCount(loop_info, trip_count, &induction_range_); HIf* loop_hif = loop_info->GetHeader()->GetLastInstruction()->AsIf(); int32_t constant = loop_info->Contains(*loop_hif->IfTrueSuccessor()) ? 0 : 1; loop_hif->ReplaceInput(graph_->GetIntConstant(constant), 0u); diff --git a/compiler/optimizing/superblock_cloner.cc b/compiler/optimizing/superblock_cloner.cc index 878967cc6e..dc433feb51 100644 --- a/compiler/optimizing/superblock_cloner.cc +++ b/compiler/optimizing/superblock_cloner.cc @@ -17,6 +17,7 @@ #include "superblock_cloner.h" #include "common_dominator.h" +#include "induction_var_range.h" #include "graph_checker.h" #include @@ -556,6 +557,13 @@ bool SuperblockCloner::CollectLiveOutsAndCheckClonable(HInstructionMap* live_out return true; } +void SuperblockCloner::UpdateInductionRangeInfoOf( + HInstruction* user, HInstruction* old_instruction, HInstruction* replacement) { + if (induction_range_ != nullptr) { + induction_range_->Replace(user, old_instruction, replacement); + } +} + void SuperblockCloner::ConstructSubgraphClosedSSA() { if (live_outs_.empty()) { return; @@ -599,6 +607,7 @@ void SuperblockCloner::ConstructSubgraphClosedSSA() { ++it; if (!IsInOrigBBSet(user->GetBlock())) { user->ReplaceInput(phi, index); + UpdateInductionRangeInfoOf(user, value, phi); } } @@ -776,7 +785,8 @@ void SuperblockCloner::DumpInputSets() { SuperblockCloner::SuperblockCloner(HGraph* graph, const HBasicBlockSet* orig_bb_set, HBasicBlockMap* bb_map, - HInstructionMap* hir_map) + HInstructionMap* hir_map, + InductionVarRange* induction_range) : graph_(graph), arena_(graph->GetAllocator()), orig_bb_set_(arena_, orig_bb_set->GetSizeOf(), true, kArenaAllocSuperblockCloner), @@ -785,6 +795,7 @@ SuperblockCloner::SuperblockCloner(HGraph* graph, remap_incoming_(nullptr), bb_map_(bb_map), hir_map_(hir_map), + induction_range_(induction_range), outer_loop_(nullptr), outer_loop_bb_set_(arena_, orig_bb_set->GetSizeOf(), true, kArenaAllocSuperblockCloner), live_outs_(std::less(), @@ -1078,7 +1089,8 @@ HLoopInformation* FindCommonLoop(HLoopInformation* loop1, HLoopInformation* loop } bool PeelUnrollHelper::IsLoopClonable(HLoopInformation* loop_info) { - PeelUnrollHelper helper(loop_info, nullptr, nullptr); + PeelUnrollHelper helper( + loop_info, /* bb_map= */ nullptr, /* hir_map= */ nullptr, /* induction_range= */ nullptr); return helper.IsLoopClonable(); } @@ -1119,12 +1131,13 @@ HBasicBlock* PeelUnrollHelper::DoPeelUnrollImpl(bool to_unroll) { return loop_header; } -PeelUnrollSimpleHelper::PeelUnrollSimpleHelper(HLoopInformation* info) +PeelUnrollSimpleHelper::PeelUnrollSimpleHelper(HLoopInformation* info, + InductionVarRange* induction_range) : bb_map_(std::less(), info->GetHeader()->GetGraph()->GetAllocator()->Adapter(kArenaAllocSuperblockCloner)), hir_map_(std::less(), info->GetHeader()->GetGraph()->GetAllocator()->Adapter(kArenaAllocSuperblockCloner)), - helper_(info, &bb_map_, &hir_map_) {} + helper_(info, &bb_map_, &hir_map_, induction_range) {} } // namespace art diff --git a/compiler/optimizing/superblock_cloner.h b/compiler/optimizing/superblock_cloner.h index dbe9008e92..ece0914ddb 100644 --- a/compiler/optimizing/superblock_cloner.h +++ b/compiler/optimizing/superblock_cloner.h @@ -24,6 +24,8 @@ namespace art { +class InductionVarRange; + static const bool kSuperblockClonerLogging = false; // Represents an edge between two HBasicBlocks. @@ -140,7 +142,8 @@ class SuperblockCloner : public ValueObject { SuperblockCloner(HGraph* graph, const HBasicBlockSet* orig_bb_set, HBasicBlockMap* bb_map, - HInstructionMap* hir_map); + HInstructionMap* hir_map, + InductionVarRange* induction_range); // Sets edge successor remapping info specified by corresponding edge sets. void SetSuccessorRemappingInfo(const HEdgeSet* remap_orig_internal, @@ -309,6 +312,10 @@ class SuperblockCloner : public ValueObject { // Resolves the inputs of the phi. void ResolvePhi(HPhi* phi); + // Update induction range after when fixing SSA. + void UpdateInductionRangeInfoOf( + HInstruction* user, HInstruction* old_instruction, HInstruction* replacement); + // // Debug and logging methods. // @@ -339,6 +346,9 @@ class SuperblockCloner : public ValueObject { HBasicBlockMap* bb_map_; // Correspondence map for instructions: (original HInstruction, copy HInstruction). HInstructionMap* hir_map_; + // As a result of cloning, the induction range analysis information can be invalidated + // and must be updated. If not null, the cloner updates it for changed instructions. + InductionVarRange* induction_range_; // Area in the graph for which control flow (back edges, loops, dominators) needs to be adjusted. HLoopInformation* outer_loop_; HBasicBlockSet outer_loop_bb_set_; @@ -357,11 +367,12 @@ class SuperblockCloner : public ValueObject { // basic blocks/instructions are demanded. class PeelUnrollHelper : public ValueObject { public: - explicit PeelUnrollHelper(HLoopInformation* info, - SuperblockCloner::HBasicBlockMap* bb_map, - SuperblockCloner::HInstructionMap* hir_map) : + PeelUnrollHelper(HLoopInformation* info, + SuperblockCloner::HBasicBlockMap* bb_map, + SuperblockCloner::HInstructionMap* hir_map, + InductionVarRange* induction_range) : loop_info_(info), - cloner_(info->GetHeader()->GetGraph(), &info->GetBlocks(), bb_map, hir_map) { + cloner_(info->GetHeader()->GetGraph(), &info->GetBlocks(), bb_map, hir_map, induction_range) { // For now do peeling/unrolling only for natural loops. DCHECK(!info->IsIrreducible()); } @@ -395,7 +406,7 @@ class PeelUnrollHelper : public ValueObject { // original and copied basic blocks/instructions. class PeelUnrollSimpleHelper : public ValueObject { public: - explicit PeelUnrollSimpleHelper(HLoopInformation* info); + PeelUnrollSimpleHelper(HLoopInformation* info, InductionVarRange* induction_range); bool IsLoopClonable() const { return helper_.IsLoopClonable(); } HBasicBlock* DoPeeling() { return helper_.DoPeeling(); } HBasicBlock* DoUnrolling() { return helper_.DoUnrolling(); } diff --git a/compiler/optimizing/superblock_cloner_test.cc b/compiler/optimizing/superblock_cloner_test.cc index 31114b6dcc..aa19de683f 100644 --- a/compiler/optimizing/superblock_cloner_test.cc +++ b/compiler/optimizing/superblock_cloner_test.cc @@ -162,7 +162,8 @@ TEST_F(SuperblockClonerTest, CloneBasicBlocks) { SuperblockCloner cloner(graph_, &orig_bb_set, &bb_map, - &hir_map); + &hir_map, + /* induction_range= */ nullptr); EXPECT_TRUE(cloner.IsSubgraphClonable()); cloner.CloneBasicBlocks(); @@ -239,8 +240,9 @@ TEST_F(SuperblockClonerTest, AdjustControlFlowInfo) { SuperblockCloner cloner(graph_, &orig_bb_set, - nullptr, - nullptr); + /* bb_map= */ nullptr, + /* hir_map= */ nullptr, + /* induction_range= */ nullptr); EXPECT_TRUE(cloner.IsSubgraphClonable()); cloner.FindAndSetLocalAreaForAdjustments(); @@ -321,7 +323,7 @@ TEST_F(SuperblockClonerTest, LoopPeeling) { std::less(), graph_->GetAllocator()->Adapter(kArenaAllocSuperblockCloner)); HLoopInformation* loop_info = header->GetLoopInformation(); - PeelUnrollHelper helper(loop_info, &bb_map, &hir_map); + PeelUnrollHelper helper(loop_info, &bb_map, &hir_map, /* induction_range= */ nullptr); EXPECT_TRUE(helper.IsLoopClonable()); HBasicBlock* new_header = helper.DoPeeling(); HLoopInformation* new_loop_info = new_header->GetLoopInformation(); @@ -380,7 +382,7 @@ TEST_F(SuperblockClonerTest, LoopUnrolling) { std::less(), graph_->GetAllocator()->Adapter(kArenaAllocSuperblockCloner)); HLoopInformation* loop_info = header->GetLoopInformation(); - PeelUnrollHelper helper(loop_info, &bb_map, &hir_map); + PeelUnrollHelper helper(loop_info, &bb_map, &hir_map, /* induction_range= */ nullptr); EXPECT_TRUE(helper.IsLoopClonable()); HBasicBlock* new_header = helper.DoUnrolling(); @@ -435,7 +437,7 @@ TEST_F(SuperblockClonerTest, LoopPeelingMultipleBackEdges) { EXPECT_TRUE(CheckGraph()); HLoopInformation* loop_info = header->GetLoopInformation(); - PeelUnrollSimpleHelper helper(loop_info); + PeelUnrollSimpleHelper helper(loop_info, /* induction_range= */ nullptr); HBasicBlock* new_header = helper.DoPeeling(); EXPECT_EQ(header, new_header); @@ -484,7 +486,7 @@ TEST_F(SuperblockClonerTest, LoopPeelingNested) { // Check nested loops structure. CheckLoopStructureForLoopPeelingNested(loop1_header, loop2_header, loop3_header); - PeelUnrollSimpleHelper helper(loop1_header->GetLoopInformation()); + PeelUnrollSimpleHelper helper(loop1_header->GetLoopInformation(), /* induction_range= */ nullptr); helper.DoPeeling(); // Check that nested loops structure has not changed after the transformation. CheckLoopStructureForLoopPeelingNested(loop1_header, loop2_header, loop3_header); @@ -530,7 +532,7 @@ TEST_F(SuperblockClonerTest, OuterLoopPopulationAfterInnerPeeled) { graph_->BuildDominatorTree(); EXPECT_TRUE(CheckGraph()); - PeelUnrollSimpleHelper helper(loop3_header->GetLoopInformation()); + PeelUnrollSimpleHelper helper(loop3_header->GetLoopInformation(), /* induction_range= */ nullptr); helper.DoPeeling(); HLoopInformation* loop1 = loop1_header->GetLoopInformation(); HLoopInformation* loop2 = loop2_header->GetLoopInformation(); @@ -596,7 +598,7 @@ TEST_F(SuperblockClonerTest, NestedCaseExitToOutermost) { HBasicBlock* loop3_long_exit = loop3_extra_if_block->GetSuccessors()[0]; EXPECT_TRUE(loop1_header->GetLoopInformation()->Contains(*loop3_long_exit)); - PeelUnrollSimpleHelper helper(loop3_header->GetLoopInformation()); + PeelUnrollSimpleHelper helper(loop3_header->GetLoopInformation(), /* induction_range= */ nullptr); helper.DoPeeling(); HLoopInformation* loop1 = loop1_header->GetLoopInformation(); @@ -653,7 +655,8 @@ TEST_F(SuperblockClonerTest, FastCaseCheck) { SuperblockCloner cloner(graph_, &orig_bb_set, &bb_map, - &hir_map); + &hir_map, + /* induction_range= */ nullptr); cloner.SetSuccessorRemappingInfo(&remap_orig_internal, &remap_copy_internal, &remap_incoming); EXPECT_FALSE(cloner.IsFastCase()); -- cgit v1.2.3-59-g8ed1b