[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

424–447

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.

433

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

435–438

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

428

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

3

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

43

are those needed?

[fhahn]

llvm/test/Transforms/LoopFusion/undominated_loops.ll

8

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

8

+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–398

this comment needs to be updated

428

nit: these local variables should still be capitalized

435–438

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

432

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

[ram-NK]

llvm/lib/Transforms/Scalar/LoopFuse.cpp

432

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;
+  /// 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);
 
     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

+; 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
+}