[LoopFusion] Move instructions from FC1.GuardBlock to FC0.GuardBlock and from FC0.ExitBlock to FC1.ExitBlock when proven safe.

[Whitney]

Summary

Currently LoopFusion give up when the second loop nest guard
block or the first loop nest exit block is not empty. For example:

if (0 < N) {
  for (int i = 0; i < N; ++i) {}
  x+=1;
}
y+=1;
if (0 < N) {
  for (int i = 0; i < N; ++i) {}
}

The above example should be safe to fuse.
This PR moves instructions in FC1 guard block (e.g. y+=1;) to
FC0 guard block, or instructions in FC0 exit block (e.g. x+=1;) to
FC1 exit block, which then LoopFusion is able to fuse them.

[jdoerfert]

llvm/lib/Transforms/Scalar/LoopFuse.cpp

761

Do we still need these isEmptyXXXBlock methods?

774

What happens now if there is a FC1 guard branch with non-movable instructions but no fc0 guard branch. I think we now miss that case and do sth? Could you add a test if we don't have one?

[Whitney]

Removed isEmptyXXXBlock methods.

llvm/lib/Transforms/Scalar/LoopFuse.cpp

761

Good catch!

774

I think that's not allowed in https://reviews.llvm.org/D71569.

[jdoerfert]

llvm/lib/Transforms/Scalar/LoopFuse.cpp

774

Fair, then you didn't need to change FC1->GuardBranch && into FC0->GuardBranch && FC1->GuardBranch &&, right? At least that is what confused me here.
Maybe we do an outer if (FC0->GuardBranch) {...} and an assertion that both are set or none is? That makes the two conditionals also simpler as they only check isSafeToMoveBefore.

[Whitney]

Addressed latest review comment.

[jdoerfert]

LGTM with the caveat that the last change didn't do what I hoped for, see below.

llvm/lib/Transforms/Scalar/LoopFuse.cpp

774

Now you check FC1->GuardBranch twice. What I meant was:

if (FC0->GuardBranch) {
           assert(FC1->GuardBranch && "Expecting valid FC1 guard branch");
            if (!isSafeToMoveBefore(*FC0->ExitBlock,
                                 *FC1->ExitBlock->getFirstNonPHIOrDbg(), DT,
                                 PDT, DI)) {
           LLVM_DEBUG(dbgs() << "Fusion candidate contains unsafe "
                                "instructions in exit block. Not fusing.\n");


           reportLoopFusion<OptimizationRemarkMissed>(*FC0, *FC1,
                                                      NonEmptyExitBlock);
           continue;
         }

           if (!isSafeToMoveBefore(
                   *FC1->GuardBranch->getParent(),
                   *FC0->GuardBranch->getParent()->getTerminator(), DT, PDT,
                   DI)) {
             LLVM_DEBUG(dbgs()
                        << "Fusion candidate contains unsafe "
                           "instructions in guard block. Not fusing.\n");
             reportLoopFusion<OptimizationRemarkMissed>(*FC0, *FC1,
                                                        NonEmptyGuardBlock);
             continue;
           }
    }

[Whitney]

Addressed review comment.

[xusx595]

It seems isSafeToMoveBefore() on basic blocks is quite limited. It doesn't handle cases like

for.body3.lr.ph: ; preds = %for.cond1.preheader

%mul4 = mul nsw i32 %j.0123, %N, !dbg !14
%add20 = add nsw i32 %mul4, %j.0123, !dbg !14
%arrayidx21 = getelementptr inbounds float, float* %A, i32 %add20, !dbg !14
%arrayidx21.promoted = load float, float* %arrayidx21, align 4, !dbg !15, !tbaa !16

It stops at '%arrayidx21 = getelementptr inbounds float, float* %A, i32 %add20, !dbg !14', which uses 'add20'.

llvm/lib/Transforms/Scalar/LoopFuse.cpp

 STATISTIC(UncomputableTripCount, "SCEV cannot compute trip count of loop");
 STATISTIC(NonEqualTripCount, "Loop trip counts are not the same");
 STATISTIC(NonAdjacent, "Loops are not adjacent");
 STATISTIC(
     NonEmptyPreheader,
     "Loop has a non-empty preheader with instructions that cannot be moved");
 STATISTIC(FusionNotBeneficial, "Fusion is not beneficial");
 STATISTIC(NonIdenticalGuards, "Candidates have different guards");
-STATISTIC(NonEmptyExitBlock, "Candidate has a non-empty exit block");
-STATISTIC(NonEmptyGuardBlock, "Candidate has a non-empty guard block");
+STATISTIC(NonEmptyExitBlock, "Candidate has a non-empty exit block with "
+                             "instructions that cannot be moved");
+STATISTIC(NonEmptyGuardBlock, "Candidate has a non-empty guard block with "
+                              "instructions that cannot be moved");
 STATISTIC(NotRotated, "Candidate is not rotated");
 
 enum FusionDependenceAnalysisChoice {
   FUSION_DEPENDENCE_ANALYSIS_SCEV,
   FUSION_DEPENDENCE_ANALYSIS_DA,
   FUSION_DEPENDENCE_ANALYSIS_ALL,
 };
 
for (auto &CandidateSet : FusionCandidates) {
                                   DI)) {
             LLVM_DEBUG(dbgs() << "Fusion candidate contains unsafe "
                                  "instructions in preheader. Not fusing.\n");
             reportLoopFusion<OptimizationRemarkMissed>(*FC0, *FC1,
                                                        NonEmptyPreheader);
             continue;
           }
 
-          // The following two checks look for empty blocks in FC0 and FC1. If
-          // any of these blocks are non-empty, we do not fuse. This is done
-          // because we currently do not have the safety checks to determine if
-          // it is safe to move the blocks past other blocks in the loop. Once
-          // these checks are added, these conditions can be relaxed.
-          if (FC0->GuardBranch && !isEmptyExitBlock(*FC0)) {
-            LLVM_DEBUG(dbgs() << "Fusion candidate does not have empty exit "
-                                 "block. Not fusing.\n");
+          if (FC0->GuardBranch &&
+              !isSafeToMoveBefore(*FC0->ExitBlock,
+                                  *FC1->ExitBlock->getFirstNonPHIOrDbg(), DT,
+                                  PDT, DI)) {
+            LLVM_DEBUG(dbgs() << "Fusion candidate contains unsafe "
+                                 "instructions in exit block. Not fusing.\n");
             reportLoopFusion<OptimizationRemarkMissed>(*FC0, *FC1,
                                                        NonEmptyExitBlock);
             continue;
           }
 
-          if (FC1->GuardBranch && !isEmptyGuardBlock(*FC1)) {
-            LLVM_DEBUG(dbgs() << "Fusion candidate does not have empty guard "
-                                 "block. Not fusing.\n");
+          if (FC1->GuardBranch) {
+            assert(FC1->GuardBranch && "Expecting valid FC1 guard branch");
+            if (!isSafeToMoveBefore(
+                    *FC1->GuardBranch->getParent(),
+                    *FC0->GuardBranch->getParent()->getTerminator(), DT, PDT,
+                    DI)) {
+              LLVM_DEBUG(dbgs()
+                         << "Fusion candidate contains unsafe "
+                            "instructions in guard block. Not fusing.\n");
               reportLoopFusion<OptimizationRemarkMissed>(*FC0, *FC1,
                                                          NonEmptyGuardBlock);
               continue;
             }
+          }
 
           // Check the dependencies across the loops and do not fuse if it would
           // violate them.
           if (!dependencesAllowFusion(*FC0, *FC1)) {
             LLVM_DEBUG(dbgs() << "Memory dependencies do not allow fusion!\n");
             reportLoopFusion<OptimizationRemarkMissed>(*FC0, *FC1,
                                                        InvalidDependencies);
             continue;
bool haveIdenticalGuards(const FusionCandidate &FC0,
     // Now make sure the successor of the guards have the same flow into/around
     // the loop
     if (FC0.GuardBranch->getSuccessor(0) == FC0.Preheader)
       return (FC1.GuardBranch->getSuccessor(0) == FC1.Preheader);
     else
       return (FC1.GuardBranch->getSuccessor(1) == FC1.Preheader);
   }
 
-  /// Check that the guard for \p FC *only* contains the cmp/branch for the
-  /// guard.
-  /// Once we are able to handle intervening code, any code in the guard block
-  /// for FC1 will need to be treated as intervening code and checked whether
-  /// it can safely move around the loops.
-  bool isEmptyGuardBlock(const FusionCandidate &FC) const {
-    assert(FC.GuardBranch && "Expecting a fusion candidate with guard branch.");
-    if (auto *CmpInst = dyn_cast<Instruction>(FC.GuardBranch->getCondition())) {
-      auto *GuardBlock = FC.GuardBranch->getParent();
-      // If the generation of the cmp value is in GuardBlock, then the size of
-      // the guard block should be 2 (cmp + branch). If the generation of the
-      // cmp value is in a different block, then the size of the guard block
-      // should only be 1.
-      if (CmpInst->getParent() == GuardBlock)
-        return GuardBlock->size() == 2;
-      else
-        return GuardBlock->size() == 1;
-    }
-
-    return false;
-  }
-
-  bool isEmptyPreheader(const FusionCandidate &FC) const {
-    assert(FC.Preheader && "Expecting a valid preheader");
-    return FC.Preheader->size() == 1;
-  }
-
-  bool isEmptyExitBlock(const FusionCandidate &FC) const {
-    assert(FC.ExitBlock && "Expecting a valid exit block");
-    return FC.ExitBlock->size() == 1;
-  }
-
   /// Simplify the condition of the latch branch of \p FC to true, when both of
   /// its successors are the same.
   void simplifyLatchBranch(const FusionCandidate &FC) const {
     BranchInst *FCLatchBranch = dyn_cast<BranchInst>(FC.Latch->getTerminator());
     if (FCLatchBranch) {
       assert(FCLatchBranch->isConditional() &&
              FCLatchBranch->getSuccessor(0) == FCLatchBranch->getSuccessor(1) &&
              "Expecting the two successors of FCLatchBranch to be the same");
Loop *fuseGuardedLoops(const FusionCandidate &FC0,
                          const FusionCandidate &FC1) {
     assert(FC0.GuardBranch && FC1.GuardBranch && "Expecting guarded loops");
 
     BasicBlock *FC0GuardBlock = FC0.GuardBranch->getParent();
     BasicBlock *FC1GuardBlock = FC1.GuardBranch->getParent();
     BasicBlock *FC0NonLoopBlock = FC0.getNonLoopBlock();
     BasicBlock *FC1NonLoopBlock = FC1.getNonLoopBlock();
 
+    // Move instructions from the exit block of FC0 to the beginning of the exit
+    // block of FC1.
+    moveInstructionsToTheBeginning(*FC0.ExitBlock, *FC1.ExitBlock, DT, PDT, DI);
+
+    // Move instructions from the guard block of FC1 to the end of the guard
+    // block of FC0.
+    moveInstructionsToTheEnd(*FC1GuardBlock, *FC0GuardBlock, DT, PDT, DI);
+
     assert(FC0NonLoopBlock == FC1GuardBlock && "Loops are not adjacent");
 
     SmallVector<DominatorTree::UpdateType, 8> TreeUpdates;
 
     ////////////////////////////////////////////////////////////////////////////
     // Update the Loop Guard
     ////////////////////////////////////////////////////////////////////////////
     // The guard for FC0 is updated to guard both FC0 and FC1. This is done by

llvm/test/Transforms/LoopFusion/diagnostics_missed.ll

for.second:
   store i32 0, i32* %arrayidx4, align 4
   %inc6 = add nsw i64 %j.01, 1
   %cmp2 = icmp slt i64 %inc6, 100
   br i1 %cmp2, label %for.second, label %for.end
 
 for.end:
   ret void
 }
+
+; CHECK: remark: diagnostics_missed.c:67:3: [unsafe_exitblock]: for.first.preheader and for.second.preheader: Candidate has a non-empty exit block with instructions that cannot be moved
+define void @unsafe_exitblock(i32* noalias %A, i32* noalias %B, i64 %N) {
+for.first.guard:
+  %cmp3 = icmp slt i64 0, %N
+  br i1 %cmp3, label %for.first.preheader, label %for.second.guard
+
+for.first.preheader:
+  br label %for.first, !dbg !83
+
+for.first:
+  %i.04 = phi i64 [ %inc, %for.first ], [ 0, %for.first.preheader ]
+  %arrayidx = getelementptr inbounds i32, i32* %A, i64 %i.04
+  store i32 0, i32* %arrayidx, align 4
+  %inc = add nsw i64 %i.04, 1
+  %cmp = icmp slt i64 %inc, %N
+  br i1 %cmp, label %for.first, label %for.first.exit
+
+for.first.exit:
+  call void @bar()
+  br label %for.second.guard
+
+for.second.guard:
+  %cmp21 = icmp slt i64 0, %N
+  br i1 %cmp21, label %for.second.preheader, label %for.end
+
+for.second.preheader:
+  br label %for.second
+
+for.second:
+  %j.02 = phi i64 [ %inc6, %for.second ], [ 0, %for.second.preheader ]
+  %arrayidx4 = getelementptr inbounds i32, i32* %B, i64 %j.02
+  store i32 0, i32* %arrayidx4, align 4
+  %inc6 = add nsw i64 %j.02, 1
+  %cmp2 = icmp slt i64 %inc6, %N
+  br i1 %cmp2, label %for.second, label %for.second.exit
+
+for.second.exit:
+  br label %for.end
+
+for.end:
+  ret void
+}
+
+; CHECK: remark: diagnostics_missed.c:72:3: [unsafe_guardblock]: for.first.preheader and for.second.preheader: Candidate has a non-empty guard block with instructions that cannot be moved
+define void @unsafe_guardblock(i32* noalias %A, i32* noalias %B, i64 %N) {
+for.first.guard:
+  %cmp3 = icmp slt i64 0, %N
+  br i1 %cmp3, label %for.first.preheader, label %for.second.guard
+
+for.first.preheader:
+  br label %for.first, !dbg !86
+
+for.first:
+  %i.04 = phi i64 [ %inc, %for.first ], [ 0, %for.first.preheader ]
+  %arrayidx = getelementptr inbounds i32, i32* %A, i64 %i.04
+  store i32 0, i32* %arrayidx, align 4
+  %inc = add nsw i64 %i.04, 1
+  %cmp = icmp slt i64 %inc, %N
+  br i1 %cmp, label %for.first, label %for.first.exit
+
+for.first.exit:
+  br label %for.second.guard
+
+for.second.guard:
+  call void @bar()
+  %cmp21 = icmp slt i64 0, %N
+  br i1 %cmp21, label %for.second.preheader, label %for.end
+
+for.second.preheader:
+  br label %for.second
+
+for.second:
+  %j.02 = phi i64 [ %inc6, %for.second ], [ 0, %for.second.preheader ]
+  %arrayidx4 = getelementptr inbounds i32, i32* %B, i64 %j.02
+  store i32 0, i32* %arrayidx4, align 4
+  %inc6 = add nsw i64 %j.02, 1
+  %cmp2 = icmp slt i64 %inc6, %N
+  br i1 %cmp2, label %for.second, label %for.second.exit
+
+for.second.exit:
+  br label %for.end
+
+for.end:
+  ret void
+}
+
 declare void @bar()
 
 attributes #0 = { nounwind readnone speculatable willreturn }
 
 !llvm.dbg.cu = !{!2}
 !llvm.module.flags = !{!10, !11, !12, !13}
 
 !0 = !DIGlobalVariableExpression(var: !1, expr: !DIExpression())

 !73 = distinct !{!73, !74, !75}
 !74 = !DILocation(line: 51, column: 3, scope: !70)
 !75 = !DILocation(line: 52, column: 15, scope: !70)
 !76 = !DILocation(line: 57, column: 3, scope: !63)
 !77 = distinct !DISubprogram(name: "unsafe_preheader", scope: !3, file: !3, line: 60, type: !15, scopeLine: 60, flags: DIFlagPrototyped, spFlags: DISPFlagDefinition, unit: !2, retainedNodes: !78)
 !78 = !{}
 !79 = distinct !DILexicalBlock(scope: !77, file: !3, line: 3, column: 5)
 !80 = !DILocation(line: 62, column: 3, scope: !79)
+!81 = distinct !DISubprogram(name: "unsafe_exitblock", scope: !3, file: !3, line: 65, type: !15, scopeLine: 60, flags: DIFlagPrototyped, spFlags: DISPFlagDefinition, unit: !2, retainedNodes: !78)
+!82 = distinct !DILexicalBlock(scope: !81, file: !3, line: 3, column: 5)
+!83 = !DILocation(line: 67, column: 3, scope: !82)
+!84 = distinct !DISubprogram(name: "unsafe_guardblock", scope: !3, file: !3, line: 70, type: !15, scopeLine: 60, flags: DIFlagPrototyped, spFlags: DISPFlagDefinition, unit: !2, retainedNodes: !78)
+!85 = distinct !DILexicalBlock(scope: !84, file: !3, line: 3, column: 5)
+!86 = !DILocation(line: 72, column: 3, scope: !85)

llvm/test/Transforms/LoopFusion/guarded.ll

for.second:
   br i1 %cmp.j, label %for.second, label %for.second.exit
 
 for.second.exit:
   br label %for.end
 
 for.end:
   ret void
 }
+
+; Test that `%add` is moved in for.second.exit, and the two loops for.first
+; and for.second are fused.
+
+; CHECK: void @moveinsts_exitblock
+; CHECK-LABEL: for.first.guard:
+; CHECK: br i1 %cmp.guard, label %for.first.preheader, label %for.end
+; CHECK-LABEL: for.first.preheader:
+; CHECK-NEXT:  br label %for.first
+; CHECK-LABEL: for.first:
+; CHECK:   br i1 %cmp.j, label %for.first, label %for.second.exit
+; CHECK-LABEL: for.second.exit:
+; CHECK-NEXT:  %add = add nsw i32 %x, 1
+; CHECK-NEXT:   br label %for.end
+; CHECK-LABEL: for.end:
+; CHECK-NEXT:   ret void
+define void @moveinsts_exitblock(i32* noalias %A, i32* noalias %B, i64 %N, i32 %x) {
+for.first.guard:
+  %cmp.guard = icmp slt i64 0, %N
+  br i1 %cmp.guard, label %for.first.preheader, label %for.second.guard
+
+for.first.preheader:
+  br label %for.first
+
+for.first:
+  %i.04 = phi i64 [ %inc, %for.first ], [ 0, %for.first.preheader ]
+  %arrayidx = getelementptr inbounds i32, i32* %A, i64 %i.04
+  store i32 0, i32* %arrayidx, align 4
+  %inc = add nsw i64 %i.04, 1
+  %cmp = icmp slt i64 %inc, %N
+  br i1 %cmp, label %for.first, label %for.first.exit
+
+for.first.exit:
+  %add = add nsw i32 %x, 1
+  br label %for.second.guard
+
+for.second.guard:
+  br i1 %cmp.guard, label %for.second.preheader, label %for.end
+
+for.second.preheader:
+  br label %for.second
+
+for.second:
+  %j.02 = phi i64 [ %inc6, %for.second ], [ 0, %for.second.preheader ]
+  %arrayidx4 = getelementptr inbounds i32, i32* %B, i64 %j.02
+  store i32 0, i32* %arrayidx4, align 4
+  %inc6 = add nsw i64 %j.02, 1
+  %cmp.j = icmp slt i64 %inc6, %N
+  br i1 %cmp.j, label %for.second, label %for.second.exit
+
+for.second.exit:
+  br label %for.end
+
+for.end:
+  ret void
+}
+
+; Test that `%add` is moved in for.first.guard, and the two loops for.first
+; and for.second are fused.
+
+; CHECK: void @moveinsts_guardblock
+; CHECK-LABEL: for.first.guard:
+; CHECK-NEXT: %cmp.guard = icmp slt i64 0, %N
+; CHECK-NEXT:  %add = add nsw i32 %x, 1
+; CHECK: br i1 %cmp.guard, label %for.first.preheader, label %for.end
+; CHECK-LABEL: for.first.preheader:
+; CHECK-NEXT:  br label %for.first
+; CHECK-LABEL: for.first:
+; CHECK:   br i1 %cmp.j, label %for.first, label %for.second.exit
+; CHECK-LABEL: for.second.exit:
+; CHECK-NEXT:   br label %for.end
+; CHECK-LABEL: for.end:
+; CHECK-NEXT:   ret void
+define void @moveinsts_guardblock(i32* noalias %A, i32* noalias %B, i64 %N, i32 %x) {
+for.first.guard:
+  %cmp.guard = icmp slt i64 0, %N
+  br i1 %cmp.guard, label %for.first.preheader, label %for.second.guard
+
+for.first.preheader:
+  br label %for.first
+
+for.first:
+  %i.04 = phi i64 [ %inc, %for.first ], [ 0, %for.first.preheader ]
+  %arrayidx = getelementptr inbounds i32, i32* %A, i64 %i.04
+  store i32 0, i32* %arrayidx, align 4
+  %inc = add nsw i64 %i.04, 1
+  %cmp = icmp slt i64 %inc, %N
+  br i1 %cmp, label %for.first, label %for.first.exit
+
+for.first.exit:
+  br label %for.second.guard
+
+for.second.guard:
+  %add = add nsw i32 %x, 1
+  br i1 %cmp.guard, label %for.second.preheader, label %for.end
+
+for.second.preheader:
+  br label %for.second
+
+for.second:
+  %j.02 = phi i64 [ %inc6, %for.second ], [ 0, %for.second.preheader ]
+  %arrayidx4 = getelementptr inbounds i32, i32* %B, i64 %j.02
+  store i32 0, i32* %arrayidx4, align 4
+  %inc6 = add nsw i64 %j.02, 1
+  %cmp.j = icmp slt i64 %inc6, %N
+  br i1 %cmp.j, label %for.second, label %for.second.exit
+
+for.second.exit:
+  br label %for.end
+
+for.end:
+  ret void
+}