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
diff --git a/compiler/optimizing/loop_optimization.cc b/compiler/optimizing/loop_optimization.cc
index 12b180d..6c76ab8 100644
--- a/compiler/optimizing/loop_optimization.cc
+++ b/compiler/optimizing/loop_optimization.cc
@@ -426,10 +426,12 @@
}
// 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 @@
// 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 @@
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 @@
// 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 878967c..dc433fe 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 <iostream>
@@ -556,6 +557,13 @@
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 @@
++it;
if (!IsInOrigBBSet(user->GetBlock())) {
user->ReplaceInput(phi, index);
+ UpdateInductionRangeInfoOf(user, value, phi);
}
}
@@ -776,7 +785,8 @@
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 @@
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<HInstruction*>(),
@@ -1078,7 +1089,8 @@
}
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 @@
return loop_header;
}
-PeelUnrollSimpleHelper::PeelUnrollSimpleHelper(HLoopInformation* info)
+PeelUnrollSimpleHelper::PeelUnrollSimpleHelper(HLoopInformation* info,
+ InductionVarRange* induction_range)
: bb_map_(std::less<HBasicBlock*>(),
info->GetHeader()->GetGraph()->GetAllocator()->Adapter(kArenaAllocSuperblockCloner)),
hir_map_(std::less<HInstruction*>(),
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 dbe9008..ece0914 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 @@
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 @@
// 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 @@
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 @@
// 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 @@
// 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 31114b6..aa19de6 100644
--- a/compiler/optimizing/superblock_cloner_test.cc
+++ b/compiler/optimizing/superblock_cloner_test.cc
@@ -162,7 +162,8 @@
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 @@
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 @@
std::less<HInstruction*>(), 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 @@
std::less<HInstruction*>(), 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 @@
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 @@
// 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 @@
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 @@
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 @@
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());