[LoopFusion] Sorting of undominated FusionCandidates crashes

[ram-NK]

Summary

This patch tries to fix 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.

[Narutoworld]

llvm/lib/Transforms/Scalar/LoopFuse.cpp

418–441

Some suggestions about grammer.

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 shose FusionCandidates, nonStrictlyPostDominate() function is needed.

427

I think you also need to add comments on this. When "nonStrictlyPostDominate()" is not useful, using the level of PostDominateTree to compare two candidates.

429–432

A more simplified version.

return (LNode->getLevel() > RNode->getLevel() );

llvm/test/Transforms/LoopFusion/undominated_loops.ll

4

I am not sure if it is good to leave remarks inside a testcase. I perfer to not include the remarks since they are not relevant.

20

Maybe try to use true or false instead. I remembered I recevied a comment before saying limit the use of undef

[aeubanks]

llvm/lib/Transforms/Scalar/LoopFuse.cpp

422

please use LLVM coding style, local variables are CamelCase without a prefix

llvm/test/Transforms/LoopFusion/undominated_loops.ll

2

can you get the IR right before loop-fusion? generally we don't want to run multiple passes in a test because that makes it more confusing
(this smells like newgvn isn't properly returning when it invalidates the domtree rather than a loop-fusion issue, but I could be wrong)

[StephenFan]

llvm/test/Transforms/LoopFusion/undominated_loops.ll

17

Can bb_4 be deleted?

[uabelho]

llvm/test/Transforms/LoopFusion/undominated_loops.ll

2

Note that there are two reproducers in the ticket. The one I added in
https://github.com/llvm/llvm-project/issues/56263#issuecomment-1316748908
just requires

opt -passes="loop-fusion"

[ram-NK]

@Narutoworld, @aeubanks, Comments in code are corrected.

[ram-NK]

Replace with the second test sample from the reported issue. It is simpler and only one pass than the first one. Thanks to @uabelho to pointed out this.

[ram-NK]

@uabelho , @aeubanks, @Narutoworld, @StephenFan All comments are updated.

[ram-NK]

format issue fixed.

[fhahn]

llvm/test/Transforms/LoopFusion/undominated_loops.ll

2

If you are checking debug output, you need to add ; REQUIRES: asserts.

42

are those needed?

[fhahn]

llvm/test/Transforms/LoopFusion/undominated_loops.ll

7

If this now fuses loops we didn't fuse before (because it was crashing), it would probably be good to check the generated IR

[aeubanks]

llvm/test/Transforms/LoopFusion/undominated_loops.ll

7

+1, instead of checking the debug output, you can use update_test_checks.py

[ram-NK]

test verification updated using update_test_checks.py

[ram-NK]

Comments are updated. @fhahn This test cases will not fuse the loops. But this type of FusionCandidates will not allow to proceed the loop fusion.

[aeubanks]

looks fine, collectFusionCandidates does check isControlFlowEquivalent rather than dominance

llvm/lib/Transforms/Scalar/LoopFuse.cpp

391–392

this comment needs to be updated

422

nit: these local variables should still be capitalized

429–432

no need for parens

[ram-NK]

@aeubanks All comments are updated.

[ram-NK]

@fhahn,

If this now fuses loops we didn't fuse before (because it was crashing), it would probably be good to check the generated IR

Corrected the IR with generated IR. Loops in the test IR will not fuse. Before, loops are not fused because of crash. Now the loops are not fused based on the proper profitable check.

[Narutoworld]

LGTM, please wait a little bit to have other reviewers' opinions.

[aeubanks]

llvm/lib/Transforms/Scalar/LoopFuse.cpp

426

actually, do we have tests for all the WrongOrder/RightOrder combinations?

[ram-NK]

llvm/lib/Transforms/Scalar/LoopFuse.cpp

426

In the test case, added new predecessor for entry.vector.body_crit_edge from middle.block15 to satisfy this condition.

[ram-NK]

corrected test case.

llvm/lib/Transforms/Scalar/LoopFuse.cpp

 #endif
     return false;
   }
 };
 
 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;
   bool operator()(const FusionCandidate &LHS,
                   const FusionCandidate &RHS) const {
     const DominatorTree *DT = &(LHS.DT);
 
     BasicBlock *LHSEntryBlock = LHS.getEntryBlock();
     BasicBlock *RHSEntryBlock = RHS.getEntryBlock();
 
     // Do not save PDT to local variable as it is only used in asserts and thus
bool operator()(const FusionCandidate &LHS,
     }
 
     if (DT->dominates(LHSEntryBlock, RHSEntryBlock)) {
       // Verify RHS Postdominates LHS
       assert(LHS.PDT->dominates(RHSEntryBlock, LHSEntryBlock));
       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!");
   }
 };
 
 using LoopVector = SmallVector<Loop *, 4>;
 
 // Set of Control Flow Equivalent (CFE) Fusion Candidates, sorted in dominance
 // order. Thus, if FC0 comes *before* FC1 in a FusionCandidateSet, then FC0

llvm/test/Transforms/LoopFusion/undominated_loops.ll

+; RUN: opt -S -passes=loop-fusion -debug-only=loop-fusion -disable-output < %s 2>&1 | FileCheck %s
+
+define void @test_long_1() {
+; CHECK: Performing Loop Fusion on function test_long_1
+; CHECK: Fusion Candidates:
+; CHECK: *** Fusion Candidate Set ***
+; CHECK: entry.vector.body_crit_edge
+; CHECK: for.cond.cleanup5.vector.body23_crit_edge
+; CHECK: ****************************
+; CHECK: Loop Fusion complete
+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
+  unreachable
+
+for.body17.preheader:                             ; preds = %for.cond.cleanup5
+  unreachable
+
+; uselistorder directives
+  uselistorder label %vector.body, { 1, 0 }
+  uselistorder label %for.cond.cleanup5, { 1, 0 }
+  uselistorder label %vector.body23, { 1, 0 }
+}