ART: Implement loop peeling/unrolling routines.
Implement loop peeling/unrolling routines using SuperblockCloner.
Fixes bug b/74198030 and provides tests for it.
Bug: b/74198030
Test: superblock_cloner_test.cc, loop_optimization_test.cc.
Change-Id: Id0d9a91575c88f8e45186441b14e903b89b007dd
diff --git a/compiler/optimizing/superblock_cloner.h b/compiler/optimizing/superblock_cloner.h
index 23de692..19c9dd4 100644
--- a/compiler/optimizing/superblock_cloner.h
+++ b/compiler/optimizing/superblock_cloner.h
@@ -152,6 +152,15 @@
// TODO: Start from small range of graph patterns then extend it.
bool IsSubgraphClonable() const;
+ // Returns whether selected subgraph satisfies the criteria for fast data flow resolution
+ // when iterative DF algorithm is not required and dominators/instructions inputs can be
+ // trivially adjusted.
+ //
+ // TODO: formally describe the criteria.
+ //
+ // Loop peeling and unrolling satisfy the criteria.
+ bool IsFastCase() const;
+
// Runs the copy algorithm according to the description.
void Run();
@@ -202,11 +211,17 @@
return IsInOrigBBSet(block->GetBlockId());
}
+ // Returns the area (the most outer loop) in the graph for which control flow (back edges, loops,
+ // dominators) needs to be adjusted.
+ HLoopInformation* GetRegionToBeAdjusted() const {
+ return outer_loop_;
+ }
+
private:
// Fills the 'exits' vector with the subgraph exits.
void SearchForSubgraphExits(ArenaVector<HBasicBlock*>* exits);
- // Finds and records information about the area in the graph for which control-flow (back edges,
+ // Finds and records information about the area in the graph for which control flow (back edges,
// loops, dominators) needs to be adjusted.
void FindAndSetLocalAreaForAdjustments();
@@ -217,7 +232,7 @@
// phis' nor instructions' inputs values are resolved.
void RemapEdgesSuccessors();
- // Adjusts control-flow (back edges, loops, dominators) for the local area defined by
+ // Adjusts control flow (back edges, loops, dominators) for the local area defined by
// FindAndSetLocalAreaForAdjustments.
void AdjustControlFlowInfo();
@@ -272,6 +287,9 @@
// Debug and logging methods.
//
void CheckInstructionInputsRemapping(HInstruction* orig_instr);
+ bool CheckRemappingInfoIsValid();
+ void VerifyGraph();
+ void DumpInputSets();
HBasicBlock* GetBlockById(uint32_t block_id) const {
DCHECK(block_id < graph_->GetBlocks().size());
@@ -295,15 +313,94 @@
HBasicBlockMap* bb_map_;
// Correspondence map for instructions: (original HInstruction, copy HInstruction).
HInstructionMap* hir_map_;
- // Area in the graph for which control-flow (back edges, loops, dominators) needs to be adjusted.
+ // Area in the graph for which control flow (back edges, loops, dominators) needs to be adjusted.
HLoopInformation* outer_loop_;
HBasicBlockSet outer_loop_bb_set_;
ART_FRIEND_TEST(SuperblockClonerTest, AdjustControlFlowInfo);
+ ART_FRIEND_TEST(SuperblockClonerTest, IsGraphConnected);
DISALLOW_COPY_AND_ASSIGN(SuperblockCloner);
};
+// Helper class to perform loop peeling/unrolling.
+//
+// This helper should be used when correspondence map between original and copied
+// basic blocks/instructions are demanded.
+class PeelUnrollHelper : public ValueObject {
+ public:
+ explicit PeelUnrollHelper(HLoopInformation* info,
+ SuperblockCloner::HBasicBlockMap* bb_map,
+ SuperblockCloner::HInstructionMap* hir_map) :
+ loop_info_(info),
+ cloner_(info->GetHeader()->GetGraph(), &info->GetBlocks(), bb_map, hir_map) {
+ // For now do peeling/unrolling only for natural loops.
+ DCHECK(!info->IsIrreducible());
+ }
+
+ // Returns whether the loop can be peeled/unrolled (static function).
+ static bool IsLoopClonable(HLoopInformation* loop_info);
+
+ // 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); }
+ 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);
+
+ private:
+ HLoopInformation* loop_info_;
+ SuperblockCloner cloner_;
+
+ DISALLOW_COPY_AND_ASSIGN(PeelUnrollHelper);
+};
+
+// Helper class to perform loop peeling/unrolling.
+//
+// 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 {
+ public:
+ explicit PeelUnrollSimpleHelper(HLoopInformation* info);
+ bool IsLoopClonable() const { return helper_.IsLoopClonable(); }
+ HBasicBlock* DoPeeling() { return helper_.DoPeeling(); }
+ HBasicBlock* DoUnrolling() { return helper_.DoUnrolling(); }
+ HLoopInformation* GetRegionToBeAdjusted() const { return helper_.GetRegionToBeAdjusted(); }
+
+ private:
+ SuperblockCloner::HBasicBlockMap bb_map_;
+ SuperblockCloner::HInstructionMap hir_map_;
+ PeelUnrollHelper helper_;
+
+ DISALLOW_COPY_AND_ASSIGN(PeelUnrollSimpleHelper);
+};
+
+// Collects edge remapping info for loop peeling/unrolling for the loop specified by loop info.
+void CollectRemappingInfoForPeelUnroll(bool to_unroll,
+ HLoopInformation* loop_info,
+ SuperblockCloner::HEdgeSet* remap_orig_internal,
+ SuperblockCloner::HEdgeSet* remap_copy_internal,
+ SuperblockCloner::HEdgeSet* remap_incoming);
+
+// Returns whether blocks from 'work_set' are reachable from the rest of the graph.
+//
+// Returns whether such a set 'outer_entries' of basic blocks exists that:
+// - each block from 'outer_entries' is not from 'work_set'.
+// - each block from 'work_set' is reachable from at least one block from 'outer_entries'.
+//
+// After the function returns work_set contains only blocks from the original 'work_set'
+// which are unreachable from the rest of the graph.
+bool IsSubgraphConnected(SuperblockCloner::HBasicBlockSet* work_set, HGraph* graph);
+
+// Returns a common predecessor of loop1 and loop2 in the loop tree or nullptr if it is the whole
+// graph.
+HLoopInformation* FindCommonLoop(HLoopInformation* loop1, HLoopInformation* loop2);
} // namespace art
namespace std {
@@ -312,11 +409,12 @@
struct hash<art::HEdge> {
size_t operator()(art::HEdge const& x) const noexcept {
// Use Cantor pairing function as the hash function.
- uint32_t a = x.GetFrom();
- uint32_t b = x.GetTo();
+ size_t a = x.GetFrom();
+ size_t b = x.GetTo();
return (a + b) * (a + b + 1) / 2 + b;
}
};
+ostream& operator<<(ostream& os, const art::HEdge& e);
} // namespace std