[LoopInterchange] Remove a limitation in legality

[congzhe]

Summary

There was a limitation that in the inner loop latch, no instruction was allowed between induction variable increment and branch in the inner loop latch. This is because we used to split the inner latch at the induction variable increment instruction. Since now we have split at the inner latch branch instruction and have moved instructions properly, we remove this limitation.

As an example, please refer to interchange_10() in test/Transforms/LoopInterchange/interchangeable.ll for the interchanged loop generated after loop interchange:

The inner latch is BB for2. When this pass was introduced very early on, it would split for2 at %j.next = add nuw nsw i64 %j, 1, and all instructions after %j.next would go into the split BB which will become the new outer latch. This causes incorrectness and hence the limitation that
" no instruction was allowed between induction variable increment and branch in the inner loop latch" was introduced initially.

Right now we split at the branch instruction of for2, and we duplicate %j.next = add nuw nsw i64 %j, 1 and %exitcond = icmp eq i64 %j, 99 into for2.split which becomes the new outer latch. Instructions in the original inner latch stay where they are. Hence the limitation can be removed.

Hope my explanation is clear, if there is any confusion please feel free to comment.

[bmahjour]

Right now we split at the branch instruction of for2, and we duplicate %j.next = add nuw nsw i64 %j, 1 and %exitcond = icmp eq i64 %j, 99 into for2.split which becomes the new outer latch. Instructions in the original inner latch stay where they are. Hence the limitation can be removed.

Do we check to make sure duplicating instructions is safe (eg we are not duplicating side effects, etc)?

[congzhe]

In D115238#3208653, @bmahjour wrote:

Right now we split at the branch instruction of for2, and we duplicate %j.next = add nuw nsw i64 %j, 1 and %exitcond = icmp eq i64 %j, 99 into for2.split which becomes the new outer latch. Instructions in the original inner latch stay where they are. Hence the limitation can be removed.

Do we check to make sure duplicating instructions is safe (eg we are not duplicating side effects, etc)?

Thanks for the comment!

Yes we did. The check is at line 1314:

assert(!NewI->mayHaveSideEffects() &&
               "Moving instructions with side-effects may change behavior of "
               "the loop nest!");

Relevant comment: https://reviews.llvm.org/D67367?vs=219418&id=219529#1664596.

It is not very easy to come up with a test case that involves duplicating unsafe instructions though, because the instructions we duplicate are involved in the loop exit condition or the induction variable increment. If an unsafe instruction was involved in loop exit condition or the induction variable increment, SCEV would say it cannot compute the backedge count and we would bail out at the first place, not even reach this piece of code.

[bmahjour]

LGTM. Thanks!

llvm/lib/Transforms/Scalar/LoopInterchange.cpp

ORE->emit([&]() {
       return OptimizationRemarkMissed(DEBUG_TYPE, "UnsupportedStructureInner",
                                       InnerLoop->getStartLoc(),
                                       InnerLoop->getHeader())
              << "Inner loop structure not understood currently.";
     });
     return true;
   }
 
-  // TODO: Current limitation: Since we split the inner loop latch at the point
-  // were induction variable is incremented (induction.next); We cannot have
-  // more than 1 user of induction.next since it would result in broken code
-  // after split.
-  // e.g.
-  // for(i=0;i<N;i++) {
-  //    for(j = 0;j<M;j++) {
-  //      A[j+1][i+2] = A[j][i]+k;
-  //  }
-  // }
-  Instruction *InnerIndexVarInc = nullptr;
-  if (InnerInductionVar->getIncomingBlock(0) == InnerLoopPreHeader)
-    InnerIndexVarInc =
-        dyn_cast<Instruction>(InnerInductionVar->getIncomingValue(1));
-  else
-    InnerIndexVarInc =
-        dyn_cast<Instruction>(InnerInductionVar->getIncomingValue(0));
-
-  if (!InnerIndexVarInc) {
-    LLVM_DEBUG(
-        dbgs() << "Did not find an instruction to increment the induction "
-               << "variable.\n");
-    ORE->emit([&]() {
-      return OptimizationRemarkMissed(DEBUG_TYPE, "NoIncrementInInner",
-                                      InnerLoop->getStartLoc(),
-                                      InnerLoop->getHeader())
-             << "The inner loop does not increment the induction variable.";
-    });
-    return true;
-  }
-
-  // Since we split the inner loop latch on this induction variable. Make sure
-  // we do not have any instruction between the induction variable and branch
-  // instruction.
-
-  bool FoundInduction = false;
-  for (const Instruction &I :
-       llvm::reverse(InnerLoopLatch->instructionsWithoutDebug())) {
-    if (isa<BranchInst>(I) || isa<CmpInst>(I) || isa<TruncInst>(I) ||
-        isa<ZExtInst>(I))
-      continue;
-
-    // We found an instruction. If this is not induction variable then it is not
-    // safe to split this loop latch.
-    if (!I.isIdenticalTo(InnerIndexVarInc)) {
-      LLVM_DEBUG(dbgs() << "Found unsupported instructions between induction "
-                        << "variable increment and branch.\n");
-      ORE->emit([&]() {
-        return OptimizationRemarkMissed(
-                   DEBUG_TYPE, "UnsupportedInsBetweenInduction",
-                   InnerLoop->getStartLoc(), InnerLoop->getHeader())
-               << "Found unsupported instruction between induction variable "
-                  "increment and branch.";
-      });
-      return true;
-    }
-
-    FoundInduction = true;
-    break;
-  }
-  // The loop latch ended and we didn't find the induction variable return as
-  // current limitation.
-  if (!FoundInduction) {
-    LLVM_DEBUG(dbgs() << "Did not find the induction variable.\n");
-    ORE->emit([&]() {
-      return OptimizationRemarkMissed(DEBUG_TYPE, "NoIndutionVariable",
-                                      InnerLoop->getStartLoc(),
-                                      InnerLoop->getHeader())
-             << "Did not find the induction variable.";
-    });
-    return true;
-  }
   return false;
 }
 
 // We currently only support LCSSA PHI nodes in the inner loop exit, if their
 // users are either reduction PHIs or PHIs outside the outer loop (which means
 // the we are only interested in the final value after the loop).
 static bool
 areInnerLoopExitPHIsSupported(Loop *InnerL, Loop *OuterL,

llvm/test/Transforms/LoopInterchange/currentLimitation.ll

 target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
 target triple = "x86_64-unknown-linux-gnu"
  
 @A = common global [100 x [100 x i32]] zeroinitializer
 @B = common global [100 x [100 x [100 x i32]]] zeroinitializer
 @C = common global [100 x [100 x i64]] zeroinitializer
  
 ;;--------------------------------------Test case 01------------------------------------
-;; [FIXME] This loop though valid is currently not interchanged due to the limitation that we cannot split the inner loop latch due to multiple use of inner induction
-;; variable.(used to increment the loop counter and to access A[j+1][i+1]
+;; This loop can be interchanged with -da-disable-delinearization-checks, otherwise it cannot
+;; be interchanged due to dependence.
 ;;  for(int i=0;i<N-1;i++)
 ;;    for(int j=1;j<N-1;j++)
 ;;      A[j+1][i+1] = A[j+1][i+1] + k;
 
-; IR-LABEL: @interchange_01
-; IR-NOT: split
-
 ; CHECK:      Name:            Dependence
 ; CHECK-NEXT: Function:        interchange_01
 
-; DELIN:      Name:            UnsupportedInsBetweenInduction
+; DELIN:      Name:            Interchanged
 ; DELIN-NEXT: Function:        interchange_01
 define void @interchange_01(i32 %k, i32 %N) {
  entry:
    %sub = add nsw i32 %N, -1
    %cmp26 = icmp sgt i32 %N, 1
    br i1 %cmp26, label %for.cond1.preheader.lr.ph, label %for.end17
  
  for.cond1.preheader.lr.ph:

llvm/test/Transforms/LoopInterchange/interchangeable.ll

 ;;      A[j][i] = i;
 ;;      A[j][i+1] = j;
 ;;    }
 ;; FIXME: DA misses this case after D35430
 
 define void @interchange_10() {
 ; CHECK-LABEL: @interchange_10(
 ; CHECK-NEXT:  entry:
+; CHECK-NEXT:    br label [[FOR2_PREHEADER:%.*]]
+; CHECK:       for1.header.preheader:
 ; CHECK-NEXT:    br label [[FOR1_HEADER:%.*]]
 ; CHECK:       for1.header:
-; CHECK-NEXT:    [[J23:%.*]] = phi i64 [ 1, [[ENTRY:%.*]] ], [ [[J_NEXT24:%.*]], [[FOR1_INC10:%.*]] ]
+; CHECK-NEXT:    [[J23:%.*]] = phi i64 [ [[J_NEXT24:%.*]], [[FOR1_INC10:%.*]] ], [ 1, [[FOR1_HEADER_PREHEADER:%.*]] ]
 ; CHECK-NEXT:    [[J_NEXT24]] = add nuw nsw i64 [[J23]], 1
+; CHECK-NEXT:    br label [[FOR2_SPLIT1:%.*]]
+; CHECK:       for2.preheader:
 ; CHECK-NEXT:    br label [[FOR2:%.*]]
 ; CHECK:       for2:
-; CHECK-NEXT:    [[J:%.*]] = phi i64 [ [[J_NEXT:%.*]], [[FOR2]] ], [ 1, [[FOR1_HEADER]] ]
-; CHECK-NEXT:    [[J_NEXT]] = add nuw nsw i64 [[J]], 1
+; CHECK-NEXT:    [[J:%.*]] = phi i64 [ [[TMP0:%.*]], [[FOR2_SPLIT:%.*]] ], [ 1, [[FOR2_PREHEADER]] ]
+; CHECK-NEXT:    br label [[FOR1_HEADER_PREHEADER]]
+; CHECK:       for2.split1:
+; CHECK-NEXT:    [[J_NEXT:%.*]] = add nuw nsw i64 [[J]], 1
 ; CHECK-NEXT:    [[ARRAYIDX5:%.*]] = getelementptr inbounds [100 x [100 x i64]], [100 x [100 x i64]]* @A, i64 0, i64 [[J]], i64 [[J23]]
 ; CHECK-NEXT:    store i64 [[J]], i64* [[ARRAYIDX5]]
 ; CHECK-NEXT:    [[ARRAYIDX10:%.*]] = getelementptr inbounds [100 x [100 x i64]], [100 x [100 x i64]]* @A, i64 0, i64 [[J]], i64 [[J_NEXT24]]
 ; CHECK-NEXT:    store i64 [[J23]], i64* [[ARRAYIDX10]]
 ; CHECK-NEXT:    [[EXITCOND:%.*]] = icmp eq i64 [[J]], 99
-; CHECK-NEXT:    br i1 [[EXITCOND]], label [[FOR1_INC10]], label [[FOR2]]
+; CHECK-NEXT:    br label [[FOR1_INC10]]
+; CHECK:       for2.split:
+; CHECK-NEXT:    [[TMP0]] = add nuw nsw i64 [[J]], 1
+; CHECK-NEXT:    [[TMP1:%.*]] = icmp eq i64 [[J]], 99
+; CHECK-NEXT:    br i1 [[TMP1]], label [[FOR_END12:%.*]], label [[FOR2]]
 ; CHECK:       for1.inc10:
 ; CHECK-NEXT:    [[EXITCOND26:%.*]] = icmp eq i64 [[J23]], 98
-; CHECK-NEXT:    br i1 [[EXITCOND26]], label [[FOR_END12:%.*]], label [[FOR1_HEADER]]
+; CHECK-NEXT:    br i1 [[EXITCOND26]], label [[FOR2_SPLIT]], label [[FOR1_HEADER]]
 ; CHECK:       for.end12:
 ; CHECK-NEXT:    ret void
 ;
 entry:
   br label %for1.header
 
 for1.header:
   %j23 = phi i64 [ 1, %entry ], [ %j.next24, %for1.inc10 ]

llvm/test/Transforms/LoopInterchange/loop-interchange-optimization-remarks.ll

 ; CHECK: --- !Missed
 ; CHECK-NEXT: Pass:            loop-interchange
 ; CHECK-NEXT: Name:            Dependence
 ; CHECK-NEXT: Function:        test02
 ; CHECK-NEXT: Args:
 ; CHECK-NEXT:   - String:          Cannot interchange loops due to dependences.
 ; CHECK-NEXT: ...
 
-; DELIN: --- !Missed
+; DELIN: --- !Passed
 ; DELIN-NEXT: Pass:            loop-interchange
-; DELIN-NEXT: Name:            UnsupportedInsBetweenInduction
+; DELIN-NEXT: Name:            Interchanged
 ; DELIN-NEXT: Function:        test02
 ; DELIN-NEXT: Args:
-; DELIN-NEXT:   - String:          Found unsupported instruction between induction variable increment and branch.
+; DELIN-NEXT:   - String:           Loop interchanged with enclosing loop.
 ; DELIN-NEXT: ...
 
 ;;-----------------------------------Test case 03-------------------------------
 ;; Test to make sure we can handle output dependencies.
 ;;
 ;;  for (int i = 0; i < 2; ++i)
 ;;    for(int j = 0; j < 3; ++j) {
 ;;      A[j][i] = i;