From 15bd22849ee6a1ffb3fb3630f686c2870bdf1bbc Mon Sep 17 00:00:00 2001 From: Nicolas Geoffray Date: Tue, 5 Jan 2016 15:55:41 +0000 Subject: Implement irreducible loop support in optimizing. So we don't fallback to the interpreter in the presence of irreducible loops. Implications: - A loop pre-header does not necessarily dominate a loop header. - Non-constant redundant phis will be kept in loop headers, to satisfy our linear scan register allocation algorithm. - while-graph optimizations, such as gvn, licm, lse, and dce need to know when they are dealing with irreducible loops. Change-Id: I2cea8934ce0b40162d215353497c7f77d6c9137e --- compiler/optimizing/nodes.h | 55 ++++++++++++++++++++++++++++----------------- 1 file changed, 34 insertions(+), 21 deletions(-) (limited to 'compiler/optimizing/nodes.h') diff --git a/compiler/optimizing/nodes.h b/compiler/optimizing/nodes.h index 1a7cbdeb5a..59c07690b1 100644 --- a/compiler/optimizing/nodes.h +++ b/compiler/optimizing/nodes.h @@ -98,11 +98,10 @@ enum IfCondition { kCondAE, // >= }; -enum BuildSsaResult { - kBuildSsaFailNonNaturalLoop, - kBuildSsaFailThrowCatchLoop, - kBuildSsaFailAmbiguousArrayOp, - kBuildSsaSuccess, +enum GraphAnalysisResult { + kAnalysisFailThrowCatchLoop, + kAnalysisFailAmbiguousArrayOp, + kAnalysisSuccess, }; class HInstructionList : public ValueObject { @@ -289,6 +288,7 @@ class HGraph : public ArenaObject { temporaries_vreg_slots_(0), has_bounds_checks_(false), has_try_catch_(false), + has_irreducible_loops_(false), debuggable_(debuggable), current_instruction_id_(start_instruction_id), dex_file_(dex_file), @@ -324,20 +324,20 @@ class HGraph : public ArenaObject { // Try building the SSA form of this graph, with dominance computation and // loop recognition. Returns a code specifying that it was successful or the // reason for failure. - BuildSsaResult TryBuildingSsa(StackHandleScopeCollection* handles); + GraphAnalysisResult TryBuildingSsa(StackHandleScopeCollection* handles); void ComputeDominanceInformation(); void ClearDominanceInformation(); - - void BuildDominatorTree(); + void ClearLoopInformation(); + void FindBackEdges(ArenaBitVector* visited); + GraphAnalysisResult BuildDominatorTree(); void SimplifyCFG(); void SimplifyCatchBlocks(); // Analyze all natural loops in this graph. Returns a code specifying that it // was successful or the reason for failure. The method will fail if a loop - // is not natural, that is the header does not dominate a back edge, or if it // is a throw-catch loop, i.e. the header is a catch block. - BuildSsaResult AnalyzeNaturalLoops() const; + GraphAnalysisResult AnalyzeLoops() const; // Iterate over blocks to compute try block membership. Needs reverse post // order and loop information. @@ -482,6 +482,9 @@ class HGraph : public ArenaObject { bool HasTryCatch() const { return has_try_catch_; } void SetHasTryCatch(bool value) { has_try_catch_ = value; } + bool HasIrreducibleLoops() const { return has_irreducible_loops_; } + void SetHasIrreducibleLoops(bool value) { has_irreducible_loops_ = value; } + ArtMethod* GetArtMethod() const { return art_method_; } void SetArtMethod(ArtMethod* method) { art_method_ = method; } @@ -491,7 +494,6 @@ class HGraph : public ArenaObject { HInstruction* InsertOppositeCondition(HInstruction* cond, HInstruction* cursor); private: - void FindBackEdges(ArenaBitVector* visited); void RemoveInstructionsAsUsersFromDeadBlocks(const ArenaBitVector& visited) const; void RemoveDeadBlocks(const ArenaBitVector& visited); @@ -558,6 +560,9 @@ class HGraph : public ArenaObject { // try/catch-related passes if false. bool has_try_catch_; + // Flag whether there are any irreducible loops in the graph. + bool has_irreducible_loops_; + // Indicates whether the graph should be compiled in a way that // ensures full debuggability. If false, we can apply more // aggressive optimizations that may limit the level of debugging. @@ -613,12 +618,17 @@ class HLoopInformation : public ArenaObject { HLoopInformation(HBasicBlock* header, HGraph* graph) : header_(header), suspend_check_(nullptr), + irreducible_(false), back_edges_(graph->GetArena()->Adapter(kArenaAllocLoopInfoBackEdges)), // Make bit vector growable, as the number of blocks may change. blocks_(graph->GetArena(), graph->GetBlocks().size(), true) { back_edges_.reserve(kDefaultNumberOfBackEdges); } + bool IsIrreducible() const { return irreducible_; } + + void Dump(std::ostream& os); + HBasicBlock* GetHeader() const { return header_; } @@ -661,15 +671,8 @@ class HLoopInformation : public ArenaObject { ReplaceElement(back_edges_, existing, new_back_edge); } - // Finds blocks that are part of this loop. Returns whether the loop is a natural loop, - // that is the header dominates the back edge. - bool Populate(); - - // Reanalyzes the loop by removing loop info from its blocks and re-running - // Populate(). If there are no back edges left, the loop info is completely - // removed as well as its SuspendCheck instruction. It must be run on nested - // inner loops first. - void Update(); + // Finds blocks that are part of this loop. + void Populate(); // Returns whether this loop information contains `block`. // Note that this loop information *must* be populated before entering this function. @@ -690,9 +693,11 @@ class HLoopInformation : public ArenaObject { private: // Internal recursive implementation of `Populate`. void PopulateRecursive(HBasicBlock* block); + void PopulateIrreducibleRecursive(HBasicBlock* block); HBasicBlock* header_; HSuspendCheck* suspend_check_; + bool irreducible_; ArenaVector back_edges_; ArenaBitVector blocks_; @@ -1019,6 +1024,11 @@ class HBasicBlock : public ArenaObject { return GetPredecessors()[0] == GetLoopInformation()->GetPreHeader(); } + bool IsFirstPredecessorBackEdge() const { + DCHECK(IsLoopHeader()); + return GetLoopInformation()->IsBackEdge(*GetPredecessors()[0]); + } + HLoopInformation* GetLoopInformation() const { return loop_information_; } @@ -1831,7 +1841,10 @@ class HInstruction : public ArenaObject { void SetBlock(HBasicBlock* block) { block_ = block; } bool IsInBlock() const { return block_ != nullptr; } bool IsInLoop() const { return block_->IsInLoop(); } - bool IsLoopHeaderPhi() { return IsPhi() && block_->IsLoopHeader(); } + bool IsLoopHeaderPhi() const { return IsPhi() && block_->IsLoopHeader(); } + bool IsIrreducibleLoopHeaderPhi() const { + return IsLoopHeaderPhi() && GetBlock()->GetLoopInformation()->IsIrreducible(); + } virtual size_t InputCount() const = 0; HInstruction* InputAt(size_t i) const { return InputRecordAt(i).GetInstruction(); } -- cgit v1.2.3-59-g8ed1b