From 7f15907acc90284706310843b6a712641b00bf1d Mon Sep 17 00:00:00 2001 From: Ramkrishnan Narayanan Komala Date: Wed, 11 Jan 2023 23:13:33 -0500 Subject: [PATCH] [LoopFusion] Sorting of undominated FusionCandidates crashes This patch tries to fix [[ https://github.com/llvm/llvm-project/issues/56263 | issue ]]. If two **FusionCandidates** are in same level of dominator tree then, they will not be dominates each other. But they are control flow equivalent. To sort those FusionCandidates **nonStrictlyPostDominate** check is needed. Reviewed By: Narutoworld Differential Revision: https://reviews.llvm.org/D139993 --- llvm/lib/Transforms/Scalar/LoopFuse.cpp | 34 +++++++++++-- .../Transforms/LoopFusion/undominated_loops.ll | 55 ++++++++++++++++++++++ 2 files changed, 85 insertions(+), 4 deletions(-) create mode 100644 llvm/test/Transforms/LoopFusion/undominated_loops.ll diff --git a/llvm/lib/Transforms/Scalar/LoopFuse.cpp b/llvm/lib/Transforms/Scalar/LoopFuse.cpp index 34bb165..714bb94 100644 --- a/llvm/lib/Transforms/Scalar/LoopFuse.cpp +++ b/llvm/lib/Transforms/Scalar/LoopFuse.cpp @@ -389,7 +389,13 @@ struct FusionCandidateCompare { /// Comparison functor to sort two Control Flow Equivalent fusion candidates /// into dominance order. /// If LHS dominates RHS and RHS post-dominates LHS, return true; - /// IF RHS dominates LHS and LHS post-dominates RHS, return false; + /// If RHS dominates LHS and LHS post-dominates RHS, return false; + /// If both LHS and RHS are not dominating each other then, non-strictly + /// post dominate check will decide the order of candidates. If RHS + /// non-strictly post dominates LHS then, return true. If LHS non-strictly + /// post dominates RHS then, return false. If both are non-strictly post + /// dominate each other then, level in the post dominator tree will decide + /// the order of candidates. bool operator()(const FusionCandidate &LHS, const FusionCandidate &RHS) const { const DominatorTree *DT = &(LHS.DT); @@ -415,9 +421,29 @@ struct FusionCandidateCompare { return true; } - // If LHS does not dominate RHS and RHS does not dominate LHS then there is - // no dominance relationship between the two FusionCandidates. Thus, they - // should not be in the same set together. + // If two FusionCandidates are in the same level of dominator tree, + // they will not dominate each other, but may still be control flow + // equivalent. To sort those FusionCandidates, nonStrictlyPostDominate() + // function is needed. + bool WrongOrder = + nonStrictlyPostDominate(LHSEntryBlock, RHSEntryBlock, DT, LHS.PDT); + bool RightOrder = + nonStrictlyPostDominate(RHSEntryBlock, LHSEntryBlock, DT, LHS.PDT); + if (WrongOrder && RightOrder) { + // If common predecessor of LHS and RHS post dominates both + // FusionCandidates then, Order of FusionCandidate can be + // identified by its level in post dominator tree. + DomTreeNode *LNode = LHS.PDT->getNode(LHSEntryBlock); + DomTreeNode *RNode = LHS.PDT->getNode(RHSEntryBlock); + return LNode->getLevel() > RNode->getLevel(); + } else if (WrongOrder) + return false; + else if (RightOrder) + return true; + + // If LHS does not non-strict Postdominate RHS and RHS does not non-strict + // Postdominate LHS then, there is no dominance relationship between the + // two FusionCandidates. Thus, they should not be in the same set together. llvm_unreachable( "No dominance relationship between these fusion candidates!"); } diff --git a/llvm/test/Transforms/LoopFusion/undominated_loops.ll b/llvm/test/Transforms/LoopFusion/undominated_loops.ll new file mode 100644 index 0000000..5d688cf --- /dev/null +++ b/llvm/test/Transforms/LoopFusion/undominated_loops.ll @@ -0,0 +1,55 @@ +; NOTE: Assertions have been autogenerated by utils/update_test_checks.py +; RUN: opt < %s -passes=loop-fusion -S | FileCheck %s +define void @test_long_1() { +; CHECK-LABEL: @test_long_1( +; CHECK-NEXT: entry: +; CHECK-NEXT: br i1 true, label [[FOR_BODY6_PREHEADER:%.*]], label [[ENTRY_VECTOR_BODY_CRIT_EDGE:%.*]] +; CHECK: entry.vector.body_crit_edge: +; CHECK-NEXT: br label [[VECTOR_BODY:%.*]] +; CHECK: vector.body: +; CHECK-NEXT: br i1 true, label [[VECTOR_BODY_FOR_COND_CLEANUP5_CRIT_EDGE:%.*]], label [[VECTOR_BODY]] +; CHECK: vector.body.for.cond.cleanup5_crit_edge: +; CHECK-NEXT: br label [[FOR_COND_CLEANUP5:%.*]] +; CHECK: for.body6.preheader: +; CHECK-NEXT: br label [[FOR_COND_CLEANUP5]] +; CHECK: for.cond.cleanup5: +; CHECK-NEXT: br i1 true, label [[FOR_BODY17_PREHEADER:%.*]], label [[FOR_COND_CLEANUP5_VECTOR_BODY23_CRIT_EDGE:%.*]] +; CHECK: for.cond.cleanup5.vector.body23_crit_edge: +; CHECK-NEXT: br label [[VECTOR_BODY23:%.*]] +; CHECK: vector.body23: +; CHECK-NEXT: br i1 true, label [[MIDDLE_BLOCK15:%.*]], label [[VECTOR_BODY23]] +; CHECK: middle.block15: +; CHECK-NEXT: br label [[ENTRY_VECTOR_BODY_CRIT_EDGE]] +; CHECK: for.body17.preheader: +; CHECK-NEXT: unreachable +; +entry: + br i1 true, label %for.body6.preheader, label %entry.vector.body_crit_edge + +entry.vector.body_crit_edge: ; preds = %entry + br label %vector.body + +vector.body: ; preds = %entry.vector.body_crit_edge, %vector.body + br i1 true, label %vector.body.for.cond.cleanup5_crit_edge, label %vector.body + +vector.body.for.cond.cleanup5_crit_edge: ; preds = %vector.body + br label %for.cond.cleanup5 + +for.body6.preheader: ; preds = %entry + br label %for.cond.cleanup5 + +for.cond.cleanup5: ; preds = %vector.body.for.cond.cleanup5_crit_edge, %for.body6.preheader + br i1 true, label %for.body17.preheader, label %for.cond.cleanup5.vector.body23_crit_edge + +for.cond.cleanup5.vector.body23_crit_edge: ; preds = %for.cond.cleanup5 + br label %vector.body23 + +vector.body23: ; preds = %for.cond.cleanup5.vector.body23_crit_edge, %vector.body23 + br i1 true, label %middle.block15, label %vector.body23 + +middle.block15: ; preds = %vector.body23 + br label %entry.vector.body_crit_edge + +for.body17.preheader: ; preds = %for.cond.cleanup5 + unreachable +} -- 2.7.4