[LoopFusion] sink second loop PHIs

[caojoshua]

Summary

Fixes https://github.com/llvm/llvm-project/issues/59023

PHI nodes that are in the second loop only have the first loop as its
predecessor. These PHI nodes should be sunk to the end of the fused
loop. If the second loop uses the PHI, then the loops cannot be fused.

I don't think this should happen in typical compilation workflows.
The PHI will be in a dedicated exit block of the first loop following
LCSSA transformations.

[aeubanks]

not very familiar with the pass, but seems reasonable

[caojoshua]

Thanks for the review. I am not a committer. Can I get help merging this? I have the commit in https://github.com/caojoshua/llvm-project/commit/8c5290e665a5e0c9276d6dcc0a1a56e3e23da27c

llvm/lib/Transforms/Scalar/LoopFuse.cpp

for (Use &Op : I.operands()) {
         // Check if we have already decided to hoist this operand. In this
         // case, it does not dominate FC0 *yet*, but will after we hoist it.
         if (!(OpHoisted || DT.dominates(OpInst, FC0PreheaderTarget))) {
           return false;
         }
       }
     }
 
+    // PHIs in FC1's header only have FC0 blocks as predecessors. PHIs
+    // cannot be hoisted and should be sunk to the exit of the fused loop.
+    if (isa<PHINode>(I))
+      return false;
+
     // If this isn't a memory inst, hoisting is safe
     if (!I.mayReadOrWriteMemory())
       return true;
 
     LLVM_DEBUG(dbgs() << "Checking if this mem inst can be hoisted.\n");
     for (Instruction *NotHoistedInst : NotHoisting) {
       if (auto D = DI.depends(&I, NotHoistedInst, true)) {
         // Dependency is not read-before-write, write-before-read or

llvm/test/Transforms/LoopFusion/lcssa.ll

+; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
+; RUN: opt -S -passes=loop-fusion < %s 2>&1 | FileCheck %s
+
+; Tests when the second loop preheader has a phi coming from the first loop
+; exit. If the phi is not used in the second loop, the loops can be fused and
+; the phi is sunk to the fused loop exit. If the phi is used in the second loop,
+; the loops cannot be fused.
+
+define void @test1() {
+; CHECK-LABEL: @test1(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    br label [[VECTOR_PH:%.*]]
+; CHECK:       vector.ph:
+; CHECK-NEXT:    br label [[MIDDLE_BLOCK:%.*]]
+; CHECK:       middle.block:
+; CHECK-NEXT:    br i1 true, label [[FOR_END41:%.*]], label [[VECTOR_PH]]
+; CHECK:       for.end41:
+; CHECK-NEXT:    [[DOTLCSSA92:%.*]] = phi i16 [ 1, [[MIDDLE_BLOCK]] ]
+; CHECK-NEXT:    ret void
+;
+entry:
+  br label %vector.ph
+
+vector.ph:                                        ; preds = %middle.block, %entry
+  br label %middle.block
+
+middle.block:                                     ; preds = %vector.ph
+  br i1 true, label %for.cond17.preheader, label %vector.ph
+
+for.cond17.preheader:                             ; preds = %middle.block
+  %.lcssa92 = phi i16 [ 1, %middle.block ]
+  br label %vector.ph61
+
+vector.ph61:                                      ; preds = %middle.block59, %for.cond17.preheader
+  br i1 true, label %for.end41, label %vector.ph61
+
+for.end41:                                        ; preds = %middle.block59
+  ret void
+}
+
+define void @test2() {
+; CHECK-LABEL: @test2(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    br label [[VECTOR_PH:%.*]]
+; CHECK:       vector.ph:
+; CHECK-NEXT:    br label [[MIDDLE_BLOCK:%.*]]
+; CHECK:       middle.block:
+; CHECK-NEXT:    br i1 true, label [[FOR_COND17_PREHEADER:%.*]], label [[VECTOR_PH]]
+; CHECK:       for.cond17.preheader:
+; CHECK-NEXT:    [[DOTLCSSA92:%.*]] = phi i16 [ 1, [[MIDDLE_BLOCK]] ]
+; CHECK-NEXT:    br label [[VECTOR_PH61:%.*]]
+; CHECK:       vector.ph61:
+; CHECK-NEXT:    call void @a(i16 [[DOTLCSSA92]])
+; CHECK-NEXT:    br i1 true, label [[FOR_END41:%.*]], label [[VECTOR_PH61]]
+; CHECK:       for.end41:
+; CHECK-NEXT:    ret void
+;
+entry:
+  br label %vector.ph
+
+vector.ph:                                        ; preds = %middle.block, %entry
+  br label %middle.block
+
+middle.block:                                     ; preds = %vector.ph
+  br i1 true, label %for.cond17.preheader, label %vector.ph
+
+for.cond17.preheader:                             ; preds = %middle.block
+  %.lcssa92 = phi i16 [ 1, %middle.block ]
+  br label %vector.ph61
+
+vector.ph61:                                      ; preds = %middle.block59, %for.cond17.preheader
+  call void @a(i16 %.lcssa92)
+  br i1 true, label %for.end41, label %vector.ph61
+
+for.end41:                                        ; preds = %middle.block59
+  ret void
+}
+
+declare void @a(i16);