| Issue |
202401
|
| Summary |
[LoopInterchange] Miscompilation when a value-carrying inner induction has an outer-IV-dependent step
|
| Labels |
miscompilation,
loopoptim
|
| Assignees |
kasuga-fj
|
| Reporter |
kasuga-fj
|
```llvm
; for (i = 1; i < 6; i++)
; for (j = 0, k = 0; j < 30; j++, k += i) // latch tests the CLEAN IV %j (constant step)
; A[i][j] = k; // store the value IV %k, which equals j*i
@A = global [6 x [40 x i64]] zeroinitializer
define void @f(ptr %A) {
entry:
br label %oh
oh: ; outer (i)
%i = phi i64 [ 1, %entry ], [ %i.next, %ol ]
br label %ih
ih: ; inner
%j = phi i64 [ 0, %oh ], [ %j.next, %il ] ; clean trip IV, constant step 1
%k = phi i64 [ 0, %oh ], [ %k.next, %il ] ; value IV, step = OUTER %i
%gep = getelementptr inbounds [6 x [40 x i64]], ptr %A, i64 0, i64 %i, i64 %j
store i64 %k, ptr %gep ; A[i][j] = k (= j*i)
%j.next = add nuw nsw i64 %j, 1
%k.next = add nuw nsw i64 %k, %i ; outer-IV-dependent step
br label %il
il:
%cond = icmp slt i64 %j, 30 ; latch on the CLEAN IV -> rectangular
br i1 %cond, label %ih, label %ie
ie:
br label %ol
ol:
%i.next = add nuw nsw i64 %i, 1
%ci = icmp slt i64 %i.next, 6
br i1 %ci, label %oh, label %ex
ex:
ret void
}
define i32 @main() {
entry:
call void @f(ptr @A)
br label %loop
loop:
%m = phi i64 [ 0, %entry ], [ %m.next, %loop ]
%acc = phi i64 [ 0, %entry ], [ %acc.next, %loop ]
%g = getelementptr inbounds i64, ptr @A, i64 %m
%v = load i64, ptr %g
%acc3 = mul i64 %acc, 31
%acc.next = add i64 %acc3, %v
%m.next = add i64 %m, 1
%c = icmp slt i64 %m.next, 240
br i1 %c, label %loop, label %done
done:
%r = trunc i64 %acc.next to i32
%r2 = and i32 %r, 65535
ret i32 %r2
}
```
```console
$ lli repro.ll
$ echo $?
31
$ opt --passes=loop-interchange --loop-interchange-profitabilities=ignore repro.ll -S -o tmp.ll
$ lli tmp.ll
$ echo $?
137
```
Note that this is similar to the case of #202383, but the root cause may be
different.
Analysis by Claude Code (not checked carefully, but looks plausible):
> The inner IV `%k` has a step (`%k.next = %k + %i`) that is the outer IV, so it
> is not really an induction of the inner loop, but `isInductionPHI` accepts it
> because only the inner-loop-invariance of the step is checked. Since the latch
> tests the clean IV `%j`, the nest is rectangular and the iteration set is not
> changed by interchange. Instead, when the loops are swapped the moved increment
> `%k.next = %k + %i` is cloned into the new inner latch, where `%i` is now the
> inner loop and only its final (LCSSA) value is available; the clone reads
> `%i.lcssa`, so `%k` effectively steps by the constant final `%i` and the stored
> values become `j * final_i` instead of `j * i`. A fix that only rejects nests
> whose inner trip count is not outer-invariant (the trapezoidal case) does not
> cover this; rejecting an inner induction whose step is not invariant in the
> outer loop in `findInductions` would address both.
Disclosure: The test case is generated by AI
![]()
_______________________________________________
llvm-bugs mailing list
[email protected]
https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-bugs
