diff options
| -rw-r--r-- | compiler/optimizing/loop_optimization.cc | 8 | ||||
| -rw-r--r-- | compiler/optimizing/superblock_cloner.cc | 137 | ||||
| -rw-r--r-- | compiler/optimizing/superblock_cloner.h | 137 | ||||
| -rw-r--r-- | compiler/optimizing/superblock_cloner_test.cc | 109 |
4 files changed, 280 insertions, 111 deletions
diff --git a/compiler/optimizing/loop_optimization.cc b/compiler/optimizing/loop_optimization.cc index 8dead2f564..4c9b01c97e 100644 --- a/compiler/optimizing/loop_optimization.cc +++ b/compiler/optimizing/loop_optimization.cc @@ -431,7 +431,7 @@ static void PeelByCount(HLoopInformation* loop_info, 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 @@ bool HLoopOptimization::TryUnrollingForBranchPenaltyReduction(LoopAnalysisInfo* // 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 @@ bool HLoopOptimization::TryPeelingForLoopInvariantExitsElimination(LoopAnalysisI 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 @@ bool HLoopOptimization::TryPeelingAndUnrolling(LoopNode* node) { } // 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 9f7a316b50..b9684917f1 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 @@ void SuperblockCloner::RemapCopyInternalEdge(HBasicBlock* orig_block, } } +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::FindAndSetLocalAreaForAdjustments() { } 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 @@ void DumpBB(HGraph* graph) { 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 @@ void SuperblockCloner::VerifyGraph() { 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 @@ bool SuperblockCloner::IsSubgraphClonable() const { 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 @@ bool SuperblockCloner::IsFastCase() const { } } - // 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 @@ void SuperblockCloner::CloneBasicBlocks() { 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 @@ HLoopInformation* FindCommonLoop(HLoopInformation* loop1, HLoopInformation* loop 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 @@ HBasicBlock* PeelUnrollHelper::DoPeelUnrollImpl(bool to_unroll) { 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 @@ HBasicBlock* PeelUnrollHelper::DoPeelUnrollImpl(bool to_unroll) { 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 @@ HBasicBlock* PeelUnrollHelper::DoPeelUnrollImpl(bool to_unroll) { 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 5af1e4d856..1f6ee74fbd 100644 --- a/compiler/optimizing/superblock_cloner.h +++ b/compiler/optimizing/superblock_cloner.h @@ -89,7 +89,8 @@ inline bool IsEdgeValid(HEdge edge, HGraph* graph) { // 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 @@ class SuperblockCloner : public ValueObject { // // 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 @@ class SuperblockCloner : public ValueObject { // 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 @@ class SuperblockCloner : public ValueObject { 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 @@ class PeelUnrollHelper : public ValueObject { // 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 @@ class PeelUnrollSimpleHelper : public ValueObject { 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 ddcf154f99..a46334bfca 100644 --- a/compiler/optimizing/superblock_cloner_test.cc +++ b/compiler/optimizing/superblock_cloner_test.cc @@ -292,29 +292,7 @@ TEST_F(SuperblockClonerTest, IsGraphConnected) { // 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 @@ TEST_F(SuperblockClonerTest, LoopPeeling) { 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 @@ TEST_F(SuperblockClonerTest, LoopPeeling) { // 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 @@ TEST_F(SuperblockClonerTest, LoopUnrolling) { 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 @@ TEST_F(SuperblockClonerTest, LoopUnrolling) { 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 @@ TEST_F(SuperblockClonerTest, LoopPeelingMultipleBackEdges) { 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 @@ TEST_F(SuperblockClonerTest, LoopPeelingNested) { // 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 @@ TEST_F(SuperblockClonerTest, OuterLoopPopulationAfterInnerPeeled) { 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 @@ 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(), /* induction_range= */ nullptr); + LoopClonerSimpleHelper helper(loop3_header->GetLoopInformation(), /* induction_range= */ nullptr); helper.DoPeeling(); HLoopInformation* loop1 = loop1_header->GetLoopInformation(); |