[LoopInterchange] Fix legality for triangular loops

[congzhe]

Summary

This is a bug fix in legality check.

When we encounter triangular loops such as the following form:

for (int i = 0; i < m; i++)
  for (int j = 0; j < i; j++), or

for (int i = 0; i < m; i++)
  for (int j = 0; j*i < n; j++),

we should not perform interchange since the number of executions of the loop body
will be different before and after interchange, resulting in incorrect results.

[bmahjour]

llvm/lib/Transforms/Scalar/LoopInterchange.cpp

714

isLoopInvariant considers any instruction that is not known to SCEV as invariant only if that instruction is not in the loop. I believe most of the interchange test cases use constant upper bounds....did you try some with non-constant upper bounds (eg. loading a global, where the global is not LICMed out of the outer loop) to make sure we can still interchange them?

llvm/test/Transforms/LoopInterchange/inner-indvar-depend-on-outer-indvar.ll

5

do we have coverage elsewhere for cases where the operands of the compare are reversed? If not please add one here:

negative test:

;;  for(int i=0;i<100;i++)
;;    for(int j=0;i>j;j++)
;;      A[j][i] = A[j][i]+k;

positive test:

;;  for(int i=0;i<100;i++)
;;    for(int j=0;N>j;j++)
;;      A[j][i] = A[j][i]+k;

21

name this "i" to be consistent with the example above.

58

name this "i"

[congzhe]

llvm/lib/Transforms/Scalar/LoopInterchange.cpp

714

Thanks for the comment! I see your concern and I checked that if we use an upper bound that is a global loaded inside the loop body and not LICMed out of the loop, SCEV would determine this upper bound to be non-constant and hence we would not do interchange.

I'd like to mention that in this function isLoopStructureUnderstood(), on line 655 which is right before my added code, when we try to detect for(int j=i; ; ), this pass used isLoopInvariant() which has the same problem as you mentioned. I'm guessing maybe at least to some extend, loop interchange has the assumption that loop-invariants are already hoisted outside the loop, so we are just fine in the sense that we are aligned with the previous logic?

Still I agree that Loop Interchange is sensitive to dependencies created by LICM hoisting code out of the inner loop. This might be a 'phase ordering' problem and unfortunately there might be no satisfying solution. I'm wondering if what I described above makes sense to you? If not, I'm entirely open to any suggestions you have, i.e., other approaches to determine whether the inner loop upper bounds are out loop invariant..

llvm/test/Transforms/LoopInterchange/inner-indvar-depend-on-outer-indvar.ll

5

Thanks for the comment, will update the test cases soon.

[congzhe]

@bmahjour thanks again for the comments, updated and added test cases accordingly.

[bmahjour]

llvm/lib/Transforms/Scalar/LoopInterchange.cpp

714

That's true. We already have dependency on LICM today, although the existing code only checks for the initial value of the induction variable. With this patch that dependency is a bit expanded to a more common case where the loop upper bound is a variable. Having said that, since LICM already runs before interchange this is not going to be a problem in practice. The real deficiency is in SCEV's isLoopInvariant and how various passes rely on it. Not sure if this is feasible but theoretically one could factor out the decision logic from LICM and put it in a utility that can be called by transforms that need to check for invariance but don't want to rely on LICM. We can look into that if the need arises.

llvm/test/Transforms/LoopInterchange/inner-indvar-depend-on-outer-indvar.ll

25

I don't see this being used!

109

This should be changed to %exitcond = icmp ne i64 %i, %j to be different from interchange_01.

145

%exitcond = icmp ne i64 %0, %j

[congzhe]

llvm/test/Transforms/LoopInterchange/inner-indvar-depend-on-outer-indvar.ll

25

Thanks, updated all tests accordingly.
This %upperbound is a leftover when I was experimenting the non-constant upper bound you mentioned. Now deleted it.

[congzhe]

llvm/lib/Transforms/Scalar/LoopInterchange.cpp

714

Thanks, I entirely agree with you. SCEV's isLoopInvariant is indeed not perfect, e.g., SCEV does not have an scCMP type and hence could not detect loop-invariant cmp instructions inside the loop. I guess the assumption is that loop-invariant cmp instructions would already be hoisted by LICM or GVN and hence SCEV is not concerned about them. But I agree with you that the decision logic can be factored out into a utility if needed.

[bmahjour]

LGTM, with a minor nit-pick.

llvm/test/Transforms/LoopInterchange/inner-indvar-depend-on-outer-indvar.ll

6

[nit] now this is unused too.

[leonardchan]

Looks like this patch might be leading to the test failure we're seeing on our two-stage-builders (https://luci-milo.appspot.com/p/fuchsia/builders/prod/clang-linux-x64/b8847508232983084096):

FAIL: LLVM :: Transforms/LoopInterchange/inner-indvar-depend-on-outer-indvar.ll (31462 of 43640)
******************** TEST 'LLVM :: Transforms/LoopInterchange/inner-indvar-depend-on-outer-indvar.ll' FAILED ********************
Script:
--
: 'RUN: at line 1';   /b/s/w/ir/x/w/staging/llvm_build/tools/clang/stage2-bins/bin/opt < /b/s/w/ir/x/w/llvm-project/llvm/test/Transforms/LoopInterchange/inner-indvar-depend-on-outer-indvar.ll -basic-aa -loop-interchange -verify-dom-info -verify-loop-info      -S -debug 2>&1 | /b/s/w/ir/x/w/staging/llvm_build/tools/clang/stage2-bins/bin/FileCheck /b/s/w/ir/x/w/llvm-project/llvm/test/Transforms/LoopInterchange/inner-indvar-depend-on-outer-indvar.ll
--
Exit Code: 1

Command Output (stderr):
--
/b/s/w/ir/x/w/llvm-project/llvm/test/Transforms/LoopInterchange/inner-indvar-depend-on-outer-indvar.ll:14:10: error: CHECK: expected string not found in input
; CHECK: Loop structure not understood by pass
         ^
<stdin>:1:1: note: scanning from here
opt: Unknown command line argument '-debug'. Try: '/b/s/w/ir/x/w/staging/llvm_build/tools/clang/stage2-bins/bin/opt --help'
^
<stdin>:1:19: note: possible intended match here
opt: Unknown command line argument '-debug'. Try: '/b/s/w/ir/x/w/staging/llvm_build/tools/clang/stage2-bins/bin/opt --help'
                  ^

Input file: <stdin>
Check file: /b/s/w/ir/x/w/llvm-project/llvm/test/Transforms/LoopInterchange/inner-indvar-depend-on-outer-indvar.ll

-dump-input=help explains the following input dump.

Input was:
<<<<<<
            1: opt: Unknown command line argument '-debug'. Try: '/b/s/w/ir/x/w/staging/llvm_build/tools/clang/stage2-bins/bin/opt --help' 
check:14'0     X~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ error: no match found
check:14'1                       ?                                                                                                          possible intended match
            2: opt: Did you mean '--debugify'? 
check:14'0     ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
>>>>>>

--

********************
Testing:  0.. 10.. 20.. 30.. 40.. 50.. 60.. 70.. 80.. 90.. 
********************
Failed Tests (1):
  LLVM :: Transforms/LoopInterchange/inner-indvar-depend-on-outer-indvar.ll


Testing Time: 47.05s
  Unsupported      : 11360
  Passed           : 32216
  Expectedly Failed:    63
  Failed           :     1

Is this a known issue?

[fhahn]

In D101305#2752096, @leonardchan wrote:

Looks like this patch might be leading to the test failure we're seeing on our two-stage-builders (https://luci-milo.appspot.com/p/fuchsia/builders/prod/clang-linux-x64/b8847508232983084096):

FAIL: LLVM :: Transforms/LoopInterchange/inner-indvar-depend-on-outer-indvar.ll (31462 of 43640)
******************** TEST 'LLVM :: Transforms/LoopInterchange/inner-indvar-depend-on-outer-indvar.ll' FAILED ********************
Script:
--
: 'RUN: at line 1';   /b/s/w/ir/x/w/staging/llvm_build/tools/clang/stage2-bins/bin/opt < /b/s/w/ir/x/w/llvm-project/llvm/test/Transforms/LoopInterchange/inner-indvar-depend-on-outer-indvar.ll -basic-aa -loop-interchange -verify-dom-info -verify-loop-info      -S -debug 2>&1 | /b/s/w/ir/x/w/staging/llvm_build/tools/clang/stage2-bins/bin/FileCheck /b/s/w/ir/x/w/llvm-project/llvm/test/Transforms/LoopInterchange/inner-indvar-depend-on-outer-indvar.ll
--
Exit Code: 1

Command Output (stderr):
--
/b/s/w/ir/x/w/llvm-project/llvm/test/Transforms/LoopInterchange/inner-indvar-depend-on-outer-indvar.ll:14:10: error: CHECK: expected string not found in input
; CHECK: Loop structure not understood by pass
         ^
<stdin>:1:1: note: scanning from here
opt: Unknown command line argument '-debug'. Try: '/b/s/w/ir/x/w/staging/llvm_build/tools/clang/stage2-bins/bin/opt --help'
^
<stdin>:1:19: note: possible intended match here
opt: Unknown command line argument '-debug'. Try: '/b/s/w/ir/x/w/staging/llvm_build/tools/clang/stage2-bins/bin/opt --help'
                  ^

Input file: <stdin>
Check file: /b/s/w/ir/x/w/llvm-project/llvm/test/Transforms/LoopInterchange/inner-indvar-depend-on-outer-indvar.ll

-dump-input=help explains the following input dump.

Input was:
<<<<<<
            1: opt: Unknown command line argument '-debug'. Try: '/b/s/w/ir/x/w/staging/llvm_build/tools/clang/stage2-bins/bin/opt --help' 
check:14'0     X~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ error: no match found
check:14'1                       ?                                                                                                          possible intended match
            2: opt: Did you mean '--debugify'? 
check:14'0     ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
>>>>>>

--

********************
Testing:  0.. 10.. 20.. 30.. 40.. 50.. 60.. 70.. 80.. 90.. 
********************
Failed Tests (1):
  LLVM :: Transforms/LoopInterchange/inner-indvar-depend-on-outer-indvar.ll


Testing Time: 47.05s
  Unsupported      : 11360
  Passed           : 32216
  Expectedly Failed:    63
  Failed           :     1

Is this a known issue?

Sounds like this test needs to either require an assert build or not use -debug (or using remarks instead)

[congzhe]

In D101305#2752100, @fhahn wrote:

In D101305#2752096, @leonardchan wrote:

Looks like this patch might be leading to the test failure we're seeing on our two-stage-builders (https://luci-milo.appspot.com/p/fuchsia/builders/prod/clang-linux-x64/b8847508232983084096):

FAIL: LLVM :: Transforms/LoopInterchange/inner-indvar-depend-on-outer-indvar.ll (31462 of 43640)
******************** TEST 'LLVM :: Transforms/LoopInterchange/inner-indvar-depend-on-outer-indvar.ll' FAILED ********************
Script:
--
: 'RUN: at line 1';   /b/s/w/ir/x/w/staging/llvm_build/tools/clang/stage2-bins/bin/opt < /b/s/w/ir/x/w/llvm-project/llvm/test/Transforms/LoopInterchange/inner-indvar-depend-on-outer-indvar.ll -basic-aa -loop-interchange -verify-dom-info -verify-loop-info      -S -debug 2>&1 | /b/s/w/ir/x/w/staging/llvm_build/tools/clang/stage2-bins/bin/FileCheck /b/s/w/ir/x/w/llvm-project/llvm/test/Transforms/LoopInterchange/inner-indvar-depend-on-outer-indvar.ll
--
Exit Code: 1

Command Output (stderr):
--
/b/s/w/ir/x/w/llvm-project/llvm/test/Transforms/LoopInterchange/inner-indvar-depend-on-outer-indvar.ll:14:10: error: CHECK: expected string not found in input
; CHECK: Loop structure not understood by pass
         ^
<stdin>:1:1: note: scanning from here
opt: Unknown command line argument '-debug'. Try: '/b/s/w/ir/x/w/staging/llvm_build/tools/clang/stage2-bins/bin/opt --help'
^
<stdin>:1:19: note: possible intended match here
opt: Unknown command line argument '-debug'. Try: '/b/s/w/ir/x/w/staging/llvm_build/tools/clang/stage2-bins/bin/opt --help'
                  ^

Input file: <stdin>
Check file: /b/s/w/ir/x/w/llvm-project/llvm/test/Transforms/LoopInterchange/inner-indvar-depend-on-outer-indvar.ll

-dump-input=help explains the following input dump.

Input was:
<<<<<<
            1: opt: Unknown command line argument '-debug'. Try: '/b/s/w/ir/x/w/staging/llvm_build/tools/clang/stage2-bins/bin/opt --help' 
check:14'0     X~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ error: no match found
check:14'1                       ?                                                                                                          possible intended match
            2: opt: Did you mean '--debugify'? 
check:14'0     ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
>>>>>>

--

********************
Testing:  0.. 10.. 20.. 30.. 40.. 50.. 60.. 70.. 80.. 90.. 
********************
Failed Tests (1):
  LLVM :: Transforms/LoopInterchange/inner-indvar-depend-on-outer-indvar.ll


Testing Time: 47.05s
  Unsupported      : 11360
  Passed           : 32216
  Expectedly Failed:    63
  Failed           :     1

Is this a known issue?

Sounds like this test needs to either require an assert build or not use -debug (or using remarks instead)

Thanks for pointing it out. I guess I'll revert this patch and re-commit after I add ; REQUIRES: asserts or use remarks.

llvm/lib/Transforms/Scalar/LoopInterchange.cpp

for (unsigned i = 0; i < Num; ++i) {
     //        for(int j=i;j<N;j++)
     unsigned IncomBlockIndx = PHINode::getIncomingValueNumForOperand(i);
     if (InnerInduction->getIncomingBlock(IncomBlockIndx) ==
             InnerLoopPreheader &&
         !OuterLoop->isLoopInvariant(I)) {
       return false;
     }
   }
+
+  // TODO: Handle triangular loops of another form.
+  // e.g. for(int i=0;i<N;i++)
+  //        for(int j=0;j<i;j++)
+  // or,
+  //      for(int i=0;i<N;i++)
+  //        for(int j=0;j*i<N;j++)
+  BasicBlock *InnerLoopLatch = InnerLoop->getLoopLatch();
+  BranchInst *InnerLoopLatchBI =
+      dyn_cast<BranchInst>(InnerLoopLatch->getTerminator());
+  if (!InnerLoopLatchBI->isConditional())
+    return false;
+  if (CmpInst *InnerLoopCmp =
+          dyn_cast<CmpInst>(InnerLoopLatchBI->getCondition())) {
+    Value *Op0 = InnerLoopCmp->getOperand(0);
+    Value *Op1 = InnerLoopCmp->getOperand(1);
+
+    // LHS and RHS of the inner loop exit condition, e.g.,
+    // in "for(int j=0;j<i;j++)", LHS is j and RHS is i.
+    Value *Left = nullptr;
+    Value *Right = nullptr;
+
+    // Check if V only involves inner loop induction variable.
+    // Return true if V is InnerInduction, or a cast from
+    // InnerInduction, or a binary operator that involves
+    // InnerInduction and a constant.
+    std::function<bool(Value *)> IsPathToIndVar;
+    IsPathToIndVar = [&InnerInduction, &IsPathToIndVar](Value *V) -> bool {
+      if (V == InnerInduction)
+        return true;
+      if (isa<Constant>(V))
+        return true;
+      Instruction *I = dyn_cast<Instruction>(V);
+      if (!I)
+        return false;
+      if (isa<CastInst>(I))
+        return IsPathToIndVar(I->getOperand(0));
+      if (isa<BinaryOperator>(I))
+        return IsPathToIndVar(I->getOperand(0)) &&
+               IsPathToIndVar(I->getOperand(1));
+      return false;
+    };
+
+    if (IsPathToIndVar(Op0) && !isa<Constant>(Op0)) {
+      Left = Op0;
+      Right = Op1;
+    } else if (IsPathToIndVar(Op1) && !isa<Constant>(Op1)) {
+      Left = Op1;
+      Right = Op0;
+    }
+
+    if (Left == nullptr)
+      return false;
+
+    const SCEV *S = SE->getSCEV(Right);
+    if (!SE->isLoopInvariant(S, OuterLoop))
+      return false;
+  }
+
   return true;
 }
 
 // If SV is a LCSSA PHI node with a single incoming value, return the incoming
 // value.
 static Value *followLCSSA(Value *SV) {
   PHINode *PHI = dyn_cast<PHINode>(SV);
   if (!PHI)

llvm/test/Transforms/LoopInterchange/inner-indvar-depend-on-outer-indvar.ll

+; RUN: opt < %s -basic-aa -loop-interchange -verify-dom-info -verify-loop-info \
+; RUN:     -S -debug 2>&1 | FileCheck %s
+
+@A = common global [100 x [100 x i64]] zeroinitializer
+@N = dso_local local_unnamed_addr global i64 100, align 8
+
+
+;;  for(int i=0;i<100;i++)
+;;    for(int j=0;j<i;j++)
+;;      A[j][i] = A[j][i]+k;
+
+;; Inner loop induction variable exit condition depends on the
+;; outer loop induction variable, i.e., triangular loops.
+; CHECK: Loop structure not understood by pass
+; CHECK: Not interchanging loops. Cannot prove legality.
+
+define void @interchange_01(i64 %k) {
+entry:
+  br label %for1.header
+
+for1.header:
+  %i = phi i64 [ 0, %entry ], [ %i.next, %for1.inc10 ]
+  br label %for2
+
+for2:
+  %j = phi i64 [ %j.next, %for2 ], [ 0, %for1.header ]
+  %arrayidx5 = getelementptr inbounds [100 x [100 x i64]], [100 x [100 x i64]]* @A, i64 0, i64 %j, i64 %i
+  %lv = load i64, i64* %arrayidx5
+  %add = add nsw i64 %lv, %k
+  store i64 %add, i64* %arrayidx5
+  %j.next = add nuw nsw i64 %j, 1
+  %exitcond = icmp eq i64 %j, %i
+  br i1 %exitcond, label %for1.inc10, label %for2
+
+for1.inc10:
+  %i.next = add nuw nsw i64 %i, 1
+  %exitcond26 = icmp eq i64 %i, 99
+  br i1 %exitcond26, label %for.end12, label %for1.header
+
+for.end12:
+  ret void
+}
+
+
+;;  for(int i=0;i<100;i++)
+;;    for(int j=0;j+i<100;j++)
+;;      A[j][i] = A[j][i]+k;
+
+;; Inner loop induction variable exit condition depends on the
+;; outer loop induction variable, i.e., triangular loops.
+; CHECK: Loop structure not understood by pass
+; CHECK: Not interchanging loops. Cannot prove legality.
+
+define void @interchange_02(i64 %k) {
+entry:
+  br label %for1.header
+
+for1.header:
+  %i = phi i64 [ 0, %entry ], [ %i.next, %for1.inc10 ]
+  br label %for2
+
+for2:
+  %j = phi i64 [ %j.next, %for2 ], [ 0, %for1.header ]
+  %arrayidx5 = getelementptr inbounds [100 x [100 x i64]], [100 x [100 x i64]]* @A, i64 0, i64 %j, i64 %i
+  %lv = load i64, i64* %arrayidx5
+  %add = add nsw i64 %lv, %k
+  store i64 %add, i64* %arrayidx5
+  %0 = add nuw nsw i64 %j, %i
+  %j.next = add nuw nsw i64 %j, 1
+  %exitcond = icmp eq i64 %0, 100
+  br i1 %exitcond, label %for1.inc10, label %for2
+
+for1.inc10:
+  %i.next = add nuw nsw i64 %i, 1
+  %exitcond26 = icmp eq i64 %i, 99
+  br i1 %exitcond26, label %for.end12, label %for1.header
+
+for.end12:
+  ret void
+}
+
+;;  for(int i=0;i<100;i++)
+;;    for(int j=0;i>j;j++)
+;;      A[j][i] = A[j][i]+k;
+
+;; Inner loop induction variable exit condition depends on the
+;; outer loop induction variable, i.e., triangular loops.
+; CHECK: Loop structure not understood by pass
+; CHECK: Not interchanging loops. Cannot prove legality.
+
+define void @interchange_03(i64 %k) {
+entry:
+  br label %for1.header
+
+for1.header:
+  %i = phi i64 [ 0, %entry ], [ %i.next, %for1.inc10 ]
+  br label %for2
+
+for2:
+  %j = phi i64 [ %j.next, %for2 ], [ 0, %for1.header ]
+  %arrayidx5 = getelementptr inbounds [100 x [100 x i64]], [100 x [100 x i64]]* @A, i64 0, i64 %j, i64 %i
+  %lv = load i64, i64* %arrayidx5
+  %add = add nsw i64 %lv, %k
+  store i64 %add, i64* %arrayidx5
+  %j.next = add nuw nsw i64 %j, 1
+  %exitcond = icmp ne i64 %i, %j
+  br i1 %exitcond, label %for2, label %for1.inc10
+
+for1.inc10:
+  %i.next = add nuw nsw i64 %i, 1
+  %exitcond26 = icmp eq i64 %i, 99
+  br i1 %exitcond26, label %for.end12, label %for1.header
+
+for.end12:
+  ret void
+}
+
+;;  for(int i=0;i<100;i++)
+;;    for(int j=0;N>j;j++)
+;;      A[j][i] = A[j][i]+k;
+
+;; Inner loop induction variable exit condition depends on
+;; an outer loop invariant, can do interchange.
+; CHECK: Loops interchanged
+
+define void @interchange_04(i64 %k) {
+entry:
+  %0 = load i64, i64* @N, align 4
+  br label %for1.header
+
+for1.header:
+  %i = phi i64 [ 0, %entry ], [ %i.next, %for1.inc10 ]
+  br label %for2
+
+for2:
+  %j = phi i64 [ %j.next, %for2 ], [ 0, %for1.header ]
+  %arrayidx5 = getelementptr inbounds [100 x [100 x i64]], [100 x [100 x i64]]* @A, i64 0, i64 %j, i64 %i
+  %lv = load i64, i64* %arrayidx5
+  %add = add nsw i64 %lv, %k
+  store i64 %add, i64* %arrayidx5
+  %j.next = add nuw nsw i64 %j, 1
+  %exitcond = icmp ne i64 %0, %j
+  br i1 %exitcond, label %for2, label %for1.inc10
+
+for1.inc10:
+  %i.next = add nuw nsw i64 %i, 1
+  %exitcond26 = icmp eq i64 %i, 99
+  br i1 %exitcond26, label %for.end12, label %for1.header
+
+for.end12:
+  ret void
+}