This is an archive of the discontinued LLVM Phabricator instance.

[LoopInterchange] Fix legality for triangular loops
ClosedPublic

Authored by congzhe on Apr 26 2021, 9:45 AM.

Details

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.

Diff Detail

Event Timeline

congzhe created this revision.Apr 26 2021, 9:45 AM
congzhe requested review of this revision.Apr 26 2021, 9:45 AM
congzhe updated this revision to Diff 340795.Apr 27 2021, 4:33 AM
congzhe updated this revision to Diff 340904.Apr 27 2021, 10:29 AM
congzhe updated this revision to Diff 340981.Apr 27 2021, 1:59 PM
bmahjour added inline comments.May 6 2021, 7:15 AM
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 added inline comments.May 9 2021, 7:02 PM
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 updated this revision to Diff 344068.May 10 2021, 8:31 AM

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

congzhe updated this revision to Diff 344073.May 10 2021, 8:47 AM
bmahjour added inline comments.May 10 2021, 9:59 AM
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
24

I don't see this being used!

108

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

144

%exitcond = icmp ne i64 %0, %j

congzhe updated this revision to Diff 344138.May 10 2021, 12:10 PM
congzhe added inline comments.
llvm/test/Transforms/LoopInterchange/inner-indvar-depend-on-outer-indvar.ll
24

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 added inline comments.May 10 2021, 12:33 PM
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 accepted this revision.May 10 2021, 1:29 PM

LGTM, with a minor nit-pick.

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

[nit] now this is unused too.

This revision is now accepted and ready to land.May 10 2021, 1:29 PM
congzhe updated this revision to Diff 344405.May 11 2021, 7:57 AM
This revision was landed with ongoing or failed builds.May 11 2021, 8:06 AM
This revision was automatically updated to reflect the committed changes.

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 added a comment.May 11 2021, 2:25 PM

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 reopened this revision.May 11 2021, 2:42 PM

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.

This revision is now accepted and ready to land.May 11 2021, 2:42 PM
congzhe updated this revision to Diff 344570.May 11 2021, 3:23 PM
This revision was landed with ongoing or failed builds.May 11 2021, 3:37 PM
This revision was automatically updated to reflect the committed changes.