ART: Introduce Loop Versioning in SuberblockCloner.
Support Loop Versioning in SuberblockCloner as a tool to
enable further optimization (e.g. Dynamic Loop Unrolling).
The patch brings the feature in without enabling it.
Replace std::cout with LOG(INFO) for debug dumps.
Test: superblock_cloner_test.
Test: test-art-target.
Change-Id: I303cabfb752b8c3c8597abfc0ac261e8616e8cee
diff --git a/compiler/optimizing/loop_optimization.cc b/compiler/optimizing/loop_optimization.cc
index 8dead2f..4c9b01c 100644
--- a/compiler/optimizing/loop_optimization.cc
+++ b/compiler/optimizing/loop_optimization.cc
@@ -431,7 +431,7 @@
InductionVarRange* induction_range) {
for (int i = 0; i < count; i++) {
// Perform peeling.
- PeelUnrollSimpleHelper helper(loop_info, induction_range);
+ LoopClonerSimpleHelper helper(loop_info, induction_range);
helper.DoPeeling();
}
}
@@ -807,7 +807,7 @@
// Perform unrolling.
HLoopInformation* loop_info = analysis_info->GetLoopInfo();
- PeelUnrollSimpleHelper helper(loop_info, &induction_range_);
+ LoopClonerSimpleHelper helper(loop_info, &induction_range_);
helper.DoUnrolling();
// Remove the redundant loop check after unrolling.
@@ -832,7 +832,7 @@
if (generate_code) {
// Perform peeling.
- PeelUnrollSimpleHelper helper(loop_info, &induction_range_);
+ LoopClonerSimpleHelper helper(loop_info, &induction_range_);
helper.DoPeeling();
// Statically evaluate loop check after peeling for loop invariant condition.
@@ -905,7 +905,7 @@
}
// Run 'IsLoopClonable' the last as it might be time-consuming.
- if (!PeelUnrollHelper::IsLoopClonable(loop_info)) {
+ if (!LoopClonerHelper::IsLoopClonable(loop_info)) {
return false;
}
diff --git a/compiler/optimizing/superblock_cloner.cc b/compiler/optimizing/superblock_cloner.cc
index 9f7a316..b968491 100644
--- a/compiler/optimizing/superblock_cloner.cc
+++ b/compiler/optimizing/superblock_cloner.cc
@@ -20,7 +20,7 @@
#include "induction_var_range.h"
#include "graph_checker.h"
-#include <iostream>
+#include <sstream>
namespace art {
@@ -227,6 +227,40 @@
}
}
+bool SuperblockCloner::IsRemapInfoForVersioning() const {
+ return remap_incoming_->empty() &&
+ remap_orig_internal_->empty() &&
+ remap_copy_internal_->empty();
+}
+
+void SuperblockCloner::CopyIncomingEdgesForVersioning() {
+ for (uint32_t orig_block_id : orig_bb_set_.Indexes()) {
+ HBasicBlock* orig_block = GetBlockById(orig_block_id);
+ size_t incoming_edge_count = 0;
+ for (HBasicBlock* orig_pred : orig_block->GetPredecessors()) {
+ uint32_t orig_pred_id = orig_pred->GetBlockId();
+ if (IsInOrigBBSet(orig_pred_id)) {
+ continue;
+ }
+
+ HBasicBlock* copy_block = GetBlockCopy(orig_block);
+ // This corresponds to the requirement on the order of predecessors: all the incoming
+ // edges must be seen before the internal ones. This is always true for natural loops.
+ // TODO: remove this requirement.
+ DCHECK_EQ(orig_block->GetPredecessorIndexOf(orig_pred), incoming_edge_count);
+ for (HInstructionIterator it(orig_block->GetPhis()); !it.Done(); it.Advance()) {
+ HPhi* orig_phi = it.Current()->AsPhi();
+ HPhi* copy_phi = GetInstrCopy(orig_phi)->AsPhi();
+ HInstruction* orig_phi_input = orig_phi->InputAt(incoming_edge_count);
+ // Add the corresponding input of the original phi to the copy one.
+ copy_phi->AddInput(orig_phi_input);
+ }
+ copy_block->AddPredecessor(orig_pred);
+ incoming_edge_count++;
+ }
+ }
+}
+
//
// Local versions of CF calculation/adjustment routines.
//
@@ -452,6 +486,12 @@
}
void SuperblockCloner::RemapEdgesSuccessors() {
+ // By this stage all the blocks have been copied, copy phis - created with no inputs;
+ // no copy edges have been created so far.
+ if (IsRemapInfoForVersioning()) {
+ CopyIncomingEdgesForVersioning();
+ }
+
// Redirect incoming edges.
for (HEdge e : *remap_incoming_) {
HBasicBlock* orig_block = GetBlockById(e.GetFrom());
@@ -646,25 +686,26 @@
if (bb == nullptr) {
continue;
}
- std::cout << bb->GetBlockId();
- std::cout << " <- ";
+ std::ostringstream oss;
+ oss << bb->GetBlockId();
+ oss << " <- ";
for (HBasicBlock* pred : bb->GetPredecessors()) {
- std::cout << pred->GetBlockId() << " ";
+ oss << pred->GetBlockId() << " ";
}
- std::cout << " -> ";
+ oss << " -> ";
for (HBasicBlock* succ : bb->GetSuccessors()) {
- std::cout << succ->GetBlockId() << " ";
+ oss << succ->GetBlockId() << " ";
}
if (bb->GetDominator()) {
- std::cout << " dom " << bb->GetDominator()->GetBlockId();
+ oss << " dom " << bb->GetDominator()->GetBlockId();
}
if (bb->GetLoopInformation()) {
- std::cout << "\tloop: " << bb->GetLoopInformation()->GetHeader()->GetBlockId();
+ oss << "\tloop: " << bb->GetLoopInformation()->GetHeader()->GetBlockId();
}
- std::cout << std::endl;
+ LOG(INFO) << oss.str();
}
}
@@ -747,35 +788,35 @@
checker.Run();
if (!checker.IsValid()) {
for (const std::string& error : checker.GetErrors()) {
- std::cout << error << std::endl;
+ LOG(ERROR) << error;
}
- LOG(FATAL) << "GraphChecker failed: superblock cloner\n";
+ LOG(FATAL) << "GraphChecker failed: superblock cloner";
}
}
}
void DumpBBSet(const ArenaBitVector* set) {
for (uint32_t idx : set->Indexes()) {
- std::cout << idx << "\n";
+ LOG(INFO) << idx;
}
}
void SuperblockCloner::DumpInputSets() {
- std::cout << "orig_bb_set:\n";
+ LOG(INFO) << "orig_bb_set:";
for (uint32_t idx : orig_bb_set_.Indexes()) {
- std::cout << idx << "\n";
+ LOG(INFO) << idx;
}
- std::cout << "remap_orig_internal:\n";
+ LOG(INFO) << "remap_orig_internal:";
for (HEdge e : *remap_orig_internal_) {
- std::cout << e << "\n";
+ LOG(INFO) << e;
}
- std::cout << "remap_copy_internal:\n";
+ LOG(INFO) << "remap_copy_internal:";
for (auto e : *remap_copy_internal_) {
- std::cout << e << "\n";
+ LOG(INFO) << e;
}
- std::cout << "remap_incoming:\n";
+ LOG(INFO) << "remap_incoming:";
for (auto e : *remap_incoming_) {
- std::cout << e << "\n";
+ LOG(INFO) << e;
}
}
@@ -837,8 +878,8 @@
return true;
}
+// Checks that loop unrolling/peeling/versioning is being conducted.
bool SuperblockCloner::IsFastCase() const {
- // Check that loop unrolling/loop peeling is being conducted.
// Check that all the basic blocks belong to the same loop.
bool flag = false;
HLoopInformation* common_loop_info = nullptr;
@@ -854,11 +895,15 @@
}
}
- // Check that orig_bb_set_ corresponds to loop peeling/unrolling.
+ // Check that orig_bb_set_ corresponds to loop peeling/unrolling/versioning.
if (common_loop_info == nullptr || !orig_bb_set_.SameBitsSet(&common_loop_info->GetBlocks())) {
return false;
}
+ if (IsRemapInfoForVersioning()) {
+ return true;
+ }
+
bool peeling_or_unrolling = false;
HEdgeSet remap_orig_internal(graph_->GetAllocator()->Adapter(kArenaAllocSuperblockCloner));
HEdgeSet remap_copy_internal(graph_->GetAllocator()->Adapter(kArenaAllocSuperblockCloner));
@@ -1012,8 +1057,7 @@
HBasicBlock* copy_block = CloneBasicBlock(orig_block);
bb_map_->Put(orig_block, copy_block);
if (kSuperblockClonerLogging) {
- std::cout << "new block :" << copy_block->GetBlockId() << ": " << orig_block->GetBlockId() <<
- std::endl;
+ LOG(INFO) << "new block :" << copy_block->GetBlockId() << ": " << orig_block->GetBlockId();
}
}
}
@@ -1089,14 +1133,14 @@
return current;
}
-bool PeelUnrollHelper::IsLoopClonable(HLoopInformation* loop_info) {
- PeelUnrollHelper helper(
+bool LoopClonerHelper::IsLoopClonable(HLoopInformation* loop_info) {
+ LoopClonerHelper helper(
loop_info, /* bb_map= */ nullptr, /* hir_map= */ nullptr, /* induction_range= */ nullptr);
return helper.IsLoopClonable();
}
-HBasicBlock* PeelUnrollHelper::DoPeelUnrollImpl(bool to_unroll) {
- // For now do peeling only for natural loops.
+HBasicBlock* LoopClonerHelper::DoLoopTransformationImpl(TransformationKind transformation) {
+ // For now do transformations only for natural loops.
DCHECK(!loop_info_->IsIrreducible());
HBasicBlock* loop_header = loop_info_->GetHeader();
@@ -1105,9 +1149,25 @@
HGraph* graph = loop_header->GetGraph();
if (kSuperblockClonerLogging) {
- std::cout << "Method: " << graph->PrettyMethod() << std::endl;
- std::cout << "Scalar loop " << (to_unroll ? "unrolling" : "peeling") <<
- " was applied to the loop <" << loop_header->GetBlockId() << ">." << std::endl;
+ LOG(INFO) << "Method: " << graph->PrettyMethod();
+ std::ostringstream oss;
+ oss << "Scalar loop ";
+ switch (transformation) {
+ case TransformationKind::kPeeling:
+ oss << "peeling";
+ break;
+ case TransformationKind::kUnrolling:
+ oss<< "unrolling";
+ break;
+ case TransformationKind::kVersioning:
+ oss << "versioning";
+ break;
+ default:
+ LOG(FATAL) << "Unreachable";
+ UNREACHABLE();
+ }
+ oss << " was applied to the loop <" << loop_header->GetBlockId() << ">.";
+ LOG(INFO) << oss.str();
}
ArenaAllocator allocator(graph->GetAllocator()->GetArenaPool());
@@ -1116,11 +1176,14 @@
HEdgeSet remap_copy_internal(graph->GetAllocator()->Adapter(kArenaAllocSuperblockCloner));
HEdgeSet remap_incoming(graph->GetAllocator()->Adapter(kArenaAllocSuperblockCloner));
- CollectRemappingInfoForPeelUnroll(to_unroll,
- loop_info_,
- &remap_orig_internal,
- &remap_copy_internal,
- &remap_incoming);
+ // No remapping needed for loop versioning.
+ if (transformation != TransformationKind::kVersioning) {
+ CollectRemappingInfoForPeelUnroll(transformation == TransformationKind::kUnrolling,
+ loop_info_,
+ &remap_orig_internal,
+ &remap_copy_internal,
+ &remap_incoming);
+ }
cloner_.SetSuccessorRemappingInfo(&remap_orig_internal, &remap_copy_internal, &remap_incoming);
cloner_.Run();
@@ -1132,7 +1195,7 @@
return loop_header;
}
-PeelUnrollSimpleHelper::PeelUnrollSimpleHelper(HLoopInformation* info,
+LoopClonerSimpleHelper::LoopClonerSimpleHelper(HLoopInformation* info,
InductionVarRange* induction_range)
: bb_map_(std::less<HBasicBlock*>(),
info->GetHeader()->GetGraph()->GetAllocator()->Adapter(kArenaAllocSuperblockCloner)),
diff --git a/compiler/optimizing/superblock_cloner.h b/compiler/optimizing/superblock_cloner.h
index 5af1e4d8..1f6ee74 100644
--- a/compiler/optimizing/superblock_cloner.h
+++ b/compiler/optimizing/superblock_cloner.h
@@ -89,7 +89,8 @@
// fine grain manipulation with IR; data flow and graph properties are resolved/adjusted
// automatically. The clone transformation is defined by specifying a set of basic blocks to copy
// and a set of rules how to treat edges, remap their successors. By using this approach such
-// optimizations as Branch Target Expansion, Loop Peeling, Loop Unrolling can be implemented.
+// optimizations as Branch Target Expansion, Loop Peeling, Loop Unrolling, Loop Versioning can be
+// implemented.
//
// The idea of the transformation is based on "Superblock cloning" technique described in the book
// "Engineering a Compiler. Second Edition", Keith D. Cooper, Linda Torczon, Rice University
@@ -161,7 +162,7 @@
//
// TODO: formally describe the criteria.
//
- // Loop peeling and unrolling satisfy the criteria.
+ // Loop peeling, unrolling and versioning satisfy the criteria.
bool IsFastCase() const;
// Runs the copy algorithm according to the description.
@@ -297,6 +298,18 @@
// Remaps copy internal edge to its origin, adjusts the phi inputs in orig_succ.
void RemapCopyInternalEdge(HBasicBlock* orig_block, HBasicBlock* orig_succ);
+ // Checks whether the edges remapping info corresponds to the subgraph versioning case:
+ // - none of the incoming edges are to be remapped (they are being duplicated).
+ // - none of the internal edges are to be remapped.
+ bool IsRemapInfoForVersioning() const;
+
+ // Processes incoming edges for subgraph versioning case: for each incoming edge (X, Y) adds
+ // an edge (X, Y_1) where Y_1 = Copy(Y) and add corresponding phi input to copy phi.
+ //
+ // Note: such node X will now have two successors, its unconditional branch instruction
+ // will be invalid and should be adjusted to some conditional branch by the client code.
+ void CopyIncomingEdgesForVersioning();
+
//
// Local versions of control flow calculation/adjustment routines.
//
@@ -362,19 +375,19 @@
DISALLOW_COPY_AND_ASSIGN(SuperblockCloner);
};
-// Helper class to perform loop peeling/unrolling.
+// Helper class to perform loop peeling/unrolling/versioning.
//
// This helper should be used when correspondence map between original and copied
// basic blocks/instructions are demanded.
-class PeelUnrollHelper : public ValueObject {
+class LoopClonerHelper : public ValueObject {
public:
- PeelUnrollHelper(HLoopInformation* info,
+ LoopClonerHelper(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, induction_range) {
- // For now do peeling/unrolling only for natural loops.
+ // For now do transformations only for natural loops.
DCHECK(!info->IsIrreducible());
}
@@ -384,33 +397,121 @@
// Returns whether the loop can be peeled/unrolled.
bool IsLoopClonable() const { return cloner_.IsSubgraphClonable(); }
- HBasicBlock* DoPeeling() { return DoPeelUnrollImpl(/* to_unroll= */ false); }
- HBasicBlock* DoUnrolling() { return DoPeelUnrollImpl(/* to_unroll= */ true); }
+ // Perform loop peeling.
+ //
+ // Control flow of an example (ignoring critical edges splitting).
+ //
+ // Before After
+ //
+ // |B| |B|
+ // | |
+ // v v
+ // |1| |1|
+ // | |
+ // v v
+ // |2|<-\ |2A|
+ // / \ / / \
+ // v v/ / v
+ // |4| |3| / |3A|
+ // | / /
+ // v | v
+ // |E| \ |2|<-\
+ // \ / \ /
+ // v v /
+ // |4| |3|
+ // |
+ // v
+ // |E|
+ HBasicBlock* DoPeeling() {
+ return DoLoopTransformationImpl(TransformationKind::kPeeling);
+ }
+
+ // Perform loop unrolling.
+ //
+ // Control flow of an example (ignoring critical edges splitting).
+ //
+ // Before After
+ //
+ // |B| |B|
+ // | |
+ // v v
+ // |1| |1|
+ // | |
+ // v v
+ // |2|<-\ |2A|<-\
+ // / \ / / \ \
+ // v v/ / v \
+ // |4| |3| / |3A| |
+ // | / / /
+ // v | v /
+ // |E| \ |2| /
+ // \ / \ /
+ // v v/
+ // |4| |3|
+ // |
+ // v
+ // |E|
+ HBasicBlock* DoUnrolling() {
+ return DoLoopTransformationImpl(TransformationKind::kUnrolling);
+ }
+
+ // Perform loop versioning.
+ //
+ // Control flow of an example (ignoring critical edges splitting).
+ //
+ // Before After
+ //
+ // |B| |B|
+ // | |
+ // v v
+ // |1| |1|_________
+ // | | |
+ // v v v
+ // |2|<-\ |2|<-\ |2A|<-\
+ // / \ / / \ / / \ /
+ // v v/ | v/ | v/
+ // | |3| | |3| | |3A|
+ // | | __________|
+ // | ||
+ // v vv
+ // |4| |4|
+ // | |
+ // v v
+ // |E| |E|
+ HBasicBlock* DoVersioning() {
+ return DoLoopTransformationImpl(TransformationKind::kVersioning);
+ }
+
HLoopInformation* GetRegionToBeAdjusted() const { return cloner_.GetRegionToBeAdjusted(); }
protected:
- // Applies loop peeling/unrolling for the loop specified by 'loop_info'.
- //
- // Depending on 'do_unroll' either unrolls loop by 2 or peels one iteration from it.
- HBasicBlock* DoPeelUnrollImpl(bool to_unroll);
+ enum class TransformationKind {
+ kPeeling,
+ kUnrolling,
+ kVersioning,
+ };
+
+ // Applies a specific loop transformation to the loop.
+ HBasicBlock* DoLoopTransformationImpl(TransformationKind transformation);
private:
HLoopInformation* loop_info_;
SuperblockCloner cloner_;
- DISALLOW_COPY_AND_ASSIGN(PeelUnrollHelper);
+ DISALLOW_COPY_AND_ASSIGN(LoopClonerHelper);
};
-// Helper class to perform loop peeling/unrolling.
+// Helper class to perform loop peeling/unrolling/versioning.
//
// This helper should be used when there is no need to get correspondence information between
// original and copied basic blocks/instructions.
-class PeelUnrollSimpleHelper : public ValueObject {
+class LoopClonerSimpleHelper : public ValueObject {
public:
- PeelUnrollSimpleHelper(HLoopInformation* info, InductionVarRange* induction_range);
+ LoopClonerSimpleHelper(HLoopInformation* info, InductionVarRange* induction_range);
bool IsLoopClonable() const { return helper_.IsLoopClonable(); }
HBasicBlock* DoPeeling() { return helper_.DoPeeling(); }
HBasicBlock* DoUnrolling() { return helper_.DoUnrolling(); }
+ HBasicBlock* DoVersioning() { return helper_.DoVersioning(); }
HLoopInformation* GetRegionToBeAdjusted() const { return helper_.GetRegionToBeAdjusted(); }
const SuperblockCloner::HBasicBlockMap* GetBasicBlockMap() const { return &bb_map_; }
@@ -419,9 +520,9 @@
private:
SuperblockCloner::HBasicBlockMap bb_map_;
SuperblockCloner::HInstructionMap hir_map_;
- PeelUnrollHelper helper_;
+ LoopClonerHelper helper_;
- DISALLOW_COPY_AND_ASSIGN(PeelUnrollSimpleHelper);
+ DISALLOW_COPY_AND_ASSIGN(LoopClonerSimpleHelper);
};
// Collects edge remapping info for loop peeling/unrolling for the loop specified by loop info.
diff --git a/compiler/optimizing/superblock_cloner_test.cc b/compiler/optimizing/superblock_cloner_test.cc
index ddcf154..a46334b 100644
--- a/compiler/optimizing/superblock_cloner_test.cc
+++ b/compiler/optimizing/superblock_cloner_test.cc
@@ -292,29 +292,7 @@
// Tests SuperblockCloner for loop peeling case.
//
-// Control Flow of the example (ignoring critical edges splitting).
-//
-// Before After
-//
-// |B| |B|
-// | |
-// v v
-// |1| |1|
-// | |
-// v v
-// |2|<-\ (6) |2A|
-// / \ / / \
-// v v/ / v
-// |4| |3| / |3A| (7)
-// | / /
-// v | v
-// |E| \ |2|<-\
-// \ / \ /
-// v v /
-// |4| |3|
-// |
-// v
-// |E|
+// See an ASCII graphics example near LoopClonerHelper::DoPeeling.
TEST_F(SuperblockClonerTest, LoopPeeling) {
HBasicBlock* header = nullptr;
HBasicBlock* loop_body = nullptr;
@@ -331,7 +309,7 @@
std::less<HInstruction*>(), graph_->GetAllocator()->Adapter(kArenaAllocSuperblockCloner));
HLoopInformation* loop_info = header->GetLoopInformation();
- PeelUnrollHelper helper(loop_info, &bb_map, &hir_map, /* induction_range= */ nullptr);
+ LoopClonerHelper 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();
@@ -351,29 +329,7 @@
// Tests SuperblockCloner for loop unrolling case.
//
-// Control Flow of the example (ignoring critical edges splitting).
-//
-// Before After
-//
-// |B| |B|
-// | |
-// v v
-// |1| |1|
-// | |
-// v v
-// |2|<-\ (6) |2A|<-\
-// / \ / / \ \
-// v v/ / v \
-// |4| |3| /(7)|3A| |
-// | / / /
-// v | v /
-// |E| \ |2| /
-// \ / \ /
-// v v/
-// |4| |3|
-// |
-// v
-// |E|
+// See an ASCII graphics example near LoopClonerHelper::DoUnrolling.
TEST_F(SuperblockClonerTest, LoopUnrolling) {
HBasicBlock* header = nullptr;
HBasicBlock* loop_body = nullptr;
@@ -390,7 +346,7 @@
std::less<HInstruction*>(), graph_->GetAllocator()->Adapter(kArenaAllocSuperblockCloner));
HLoopInformation* loop_info = header->GetLoopInformation();
- PeelUnrollHelper helper(loop_info, &bb_map, &hir_map, /* induction_range= */ nullptr);
+ LoopClonerHelper helper(loop_info, &bb_map, &hir_map, /* induction_range= */ nullptr);
EXPECT_TRUE(helper.IsLoopClonable());
HBasicBlock* new_header = helper.DoUnrolling();
@@ -408,6 +364,55 @@
EXPECT_EQ(loop_info->GetBackEdges()[0], bb_map.Get(loop_body));
}
+// Tests SuperblockCloner for loop versioning case.
+//
+// See an ASCII graphics example near LoopClonerHelper::DoVersioning.
+TEST_F(SuperblockClonerTest, LoopVersioning) {
+ HBasicBlock* header = nullptr;
+ HBasicBlock* loop_body = nullptr;
+
+ InitGraph();
+ CreateBasicLoopControlFlow(entry_block_, return_block_, &header, &loop_body);
+ CreateBasicLoopDataFlow(header, loop_body);
+ graph_->BuildDominatorTree();
+ EXPECT_TRUE(CheckGraph());
+
+ HBasicBlockMap bb_map(
+ std::less<HBasicBlock*>(), graph_->GetAllocator()->Adapter(kArenaAllocSuperblockCloner));
+ HInstructionMap hir_map(
+ std::less<HInstruction*>(), graph_->GetAllocator()->Adapter(kArenaAllocSuperblockCloner));
+
+ HLoopInformation* loop_info = header->GetLoopInformation();
+ HBasicBlock* original_preheader = loop_info->GetPreHeader();
+ LoopClonerHelper helper(loop_info, &bb_map, &hir_map, /* induction_range= */ nullptr);
+ EXPECT_TRUE(helper.IsLoopClonable());
+ HBasicBlock* new_header = helper.DoVersioning();
+ EXPECT_EQ(header, new_header);
+
+ EXPECT_TRUE(CheckGraph());
+
+ HBasicBlock* second_header = bb_map.Get(header);
+ HBasicBlock* second_body = bb_map.Get(loop_body);
+ HLoopInformation* second_loop_info = second_header->GetLoopInformation();
+
+ // Check loop body successors.
+ EXPECT_EQ(loop_body->GetSingleSuccessor(), header);
+ EXPECT_EQ(second_body->GetSingleSuccessor(), second_header);
+
+ // Check loop structure.
+ EXPECT_EQ(loop_info, header->GetLoopInformation());
+ EXPECT_EQ(loop_info->GetHeader(), header);
+ EXPECT_EQ(second_loop_info->GetHeader(), second_header);
+
+ EXPECT_EQ(loop_info->GetBackEdges().size(), 1u);
+ EXPECT_EQ(second_loop_info->GetBackEdges().size(), 1u);
+
+ EXPECT_EQ(loop_info->GetBackEdges()[0], loop_body);
+ EXPECT_EQ(second_loop_info->GetBackEdges()[0], second_body);
+
+ EXPECT_EQ(original_preheader->GetSuccessors().size(), 2u);
+}
+
// Checks that loop unrolling works fine for a loop with multiple back edges. Tests that after
// the transformation the loop has a single preheader.
TEST_F(SuperblockClonerTest, LoopPeelingMultipleBackEdges) {
@@ -445,7 +450,7 @@
EXPECT_TRUE(CheckGraph());
HLoopInformation* loop_info = header->GetLoopInformation();
- PeelUnrollSimpleHelper helper(loop_info, /* induction_range= */ nullptr);
+ LoopClonerSimpleHelper helper(loop_info, /* induction_range= */ nullptr);
HBasicBlock* new_header = helper.DoPeeling();
EXPECT_EQ(header, new_header);
@@ -494,7 +499,7 @@
// Check nested loops structure.
CheckLoopStructureForLoopPeelingNested(loop1_header, loop2_header, loop3_header);
- PeelUnrollSimpleHelper helper(loop1_header->GetLoopInformation(), /* induction_range= */ nullptr);
+ LoopClonerSimpleHelper 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);
@@ -540,7 +545,7 @@
graph_->BuildDominatorTree();
EXPECT_TRUE(CheckGraph());
- PeelUnrollSimpleHelper helper(loop3_header->GetLoopInformation(), /* induction_range= */ nullptr);
+ LoopClonerSimpleHelper helper(loop3_header->GetLoopInformation(), /* induction_range= */ nullptr);
helper.DoPeeling();
HLoopInformation* loop1 = loop1_header->GetLoopInformation();
HLoopInformation* loop2 = loop2_header->GetLoopInformation();
@@ -606,7 +611,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(), /* induction_range= */ nullptr);
+ LoopClonerSimpleHelper helper(loop3_header->GetLoopInformation(), /* induction_range= */ nullptr);
helper.DoPeeling();
HLoopInformation* loop1 = loop1_header->GetLoopInformation();