[LoopFusion] Ensure that both loops are guarded or neither are guarded.

[kbarton]

Summary

This patch modifies the current conditions for loop fusion by ensuring that
either both fusion candidates have a guard, or neither have a guard. This
prevents us from inadvertantly attempting to fuse a guarded loop with a
non-guarded loop.

[Whitney]

llvm/test/Transforms/LoopFusion/cannot_fuse.ll

421

optional:
define void @only_one_guarded(i32* noalias %A, i32* noalias %B, i1 zeroext %cond) {

[Whitney]

llvm/lib/Transforms/Scalar/LoopFuse.cpp

1070

haveIdenticalGuards() is not called with both candidates unguarded, so (!FC0.GuardBranch && !FC1.GuardBranch) is impossible.

[Meinersbur]

LGTM. @Whitney?

llvm/lib/Transforms/Scalar/LoopFuse.cpp

738–739

[style] (FC0->GuardBranch || FC1->GuardBranch) && !haveIdenticalGuards(*FC0, *FC1)

1069–1070

The check can still make sense for defensive programming (or replaced by an assertion).

[style] !FC0.GuardBranch != !FC1.GuardBranch

[Whitney]

LGTM. @Whitney?

I know that @kbarton is working on a patch which allow guarded loops fuse with unguarded loops as long as they are control flow equivalent.
I think that's a better solution. And with that, this patch is no longer needed.
However, I don't mind having this patch committed in the meantime.

[Meinersbur]

OK then; Kit may either abandon or commit this patch.

[xusx595]

I wonder if this issue still exists in llvm trunk.

// Ensure that FC0 and FC1 have identical guards.
// If one (or both) are not guarded, this check is not necessary.
if (FC0->GuardBranch && FC1->GuardBranch &&
    !haveIdenticalGuards(*FC0, *FC1) && !TCDifference) {
  LLVM_DEBUG(dbgs() << "Fusion candidates do not have identical "
                       "guards. Not Fusing.\n");
  reportLoopFusion<OptimizationRemarkMissed>(*FC0, *FC1,
                                             NonIdenticalGuards);
  continue;
}

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

if (FC0->GuardBranch) {
  assert(FC1->GuardBranch && "Expecting valid FC1 guard branch");

It seems we still need add checks to make sure both loops are guarded or neither are guarded. I enabled loop fusion in our compiler for Xtensa at Cadence, and encountered this issue (our llvm base is 10.0.1 at the moment).

llvm/lib/Transforms/Scalar/LoopFuse.cpp

for (auto &CandidateSet : FusionCandidates) {
           if (!isAdjacent(*FC0, *FC1)) {
             LLVM_DEBUG(dbgs()
                        << "Fusion candidates are not adjacent. Not fusing.\n");
             reportLoopFusion<OptimizationRemarkMissed>(*FC0, *FC1, NonAdjacent);
             continue;
           }
 
           // Ensure that FC0 and FC1 have identical guards.
-          // If one (or both) are not guarded, this check is not necessary.
-          if (FC0->GuardBranch && FC1->GuardBranch &&
-              !haveIdenticalGuards(*FC0, *FC1)) {
+          if (FC0->GuardBranch || FC1->GuardBranch)
+            if (!haveIdenticalGuards(*FC0, *FC1)) {
               LLVM_DEBUG(dbgs() << "Fusion candidates do not have identical "
                                    "guards. Not Fusing.\n");
               reportLoopFusion<OptimizationRemarkMissed>(*FC0, *FC1,
                                                          NonIdenticalGuards);
               continue;
             }
 
           // The following three 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 (!isEmptyPreheader(*FC1)) {
             LLVM_DEBUG(dbgs() << "Fusion candidate does not have empty "
#endif
   ///   1. The instructions to compute the condition used in the compare are
   ///      identical.
   ///   2. The successors of the guard have the same flow into/around the loop.
   /// If the compare instructions are identical, then the first successor of the
   /// guard must go to the same place (either the preheader of the loop or the
   /// NonLoopBlock). In other words, the the first successor of both loops must
   /// both go into the loop (i.e., the preheader) or go around the loop (i.e.,
   /// the NonLoopBlock). The same must be true for the second successor.
+  /// If one of the loops has a guard, but the other loop does not, they do not
+  /// have identical guards.
   bool haveIdenticalGuards(const FusionCandidate &FC0,
                            const FusionCandidate &FC1) const {
+    // Either both loops should have a guard or neither loop should have a
+    // guard.
+    if (!((FC0.GuardBranch && FC1.GuardBranch) ||
+          (!FC0.GuardBranch && !FC1.GuardBranch)))
+      return false;
+
     assert(FC0.GuardBranch && FC1.GuardBranch &&
            "Expecting FC0 and FC1 to be guarded loops.");
 
     if (auto FC0CmpInst =
             dyn_cast<Instruction>(FC0.GuardBranch->getCondition()))
       if (auto FC1CmpInst =
               dyn_cast<Instruction>(FC1.GuardBranch->getCondition()))
         if (!FC0CmpInst->isIdenticalTo(FC1CmpInst))

llvm/test/Transforms/LoopFusion/cannot_fuse.ll

 bb27:                                             ; preds = %bb19
   %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1
   %tmp28 = add nuw nsw i32 %.0, 1
   br label %bb17
 
 bb29:                                             ; preds = %bb18
   ret void
 }
+
+; Check that a guarded loop and a non-guarded loop are not fused.
+; CHECK: Performing Loop Fusion on function _Z3fooPiS_b
+; CHECK: Fusion candidates do not have identical guards. Not Fusing.
+define dso_local void @_Z3fooPiS_b(i32* noalias %A, i32* noalias %B, i1 zeroext %cond) #0 {
+entry:
+  %frombool = zext i1 %cond to i8
+  %tobool = trunc i8 %frombool to i1
+  br i1 %tobool, label %for.body.preheader, label %if.end
+for.body.preheader:                               ; preds = %entry
+  br label %for.body
+for.body:                                         ; preds = %for.body.preheader, %for.body
+  %i.02 = phi i64 [ %inc, %for.body ], [ 0, %for.body.preheader ]
+  %arrayidx = getelementptr inbounds i32, i32* %A, i64 %i.02
+  store i32 0, i32* %arrayidx, align 4
+  %inc = add nsw i64 %i.02, 1
+  %cmp = icmp slt i64 %inc, 100
+  br i1 %cmp, label %for.body, label %if.end.loopexit
+if.end.loopexit:                                  ; preds = %for.body
+  br label %if.end
+if.end:                                           ; preds = %if.end.loopexit, %entry
+  br label %for.body4
+for.body4:                                        ; preds = %if.end, %for.body4
+  %i1.01 = phi i64 [ 0, %if.end ], [ %inc7, %for.body4 ]
+  %arrayidx5 = getelementptr inbounds i32, i32* %B, i64 %i1.01
+  store i32 0, i32* %arrayidx5, align 4
+  %inc7 = add nsw i64 %i1.01, 1
+  %cmp3 = icmp slt i64 %inc7, 100
+  br i1 %cmp3, label %for.body4, label %for.end8
+for.end8:                                         ; preds = %for.body4
+  ret void
+}