[LAA] Missing dependence due to AddRec wrap #160912
Description
Reproducer and results when running opt --passes='print<access-info> (godbolt: https://godbolt.org/z/rGY5Kcfba)
; unsigned long long s0 = 0, s1 = 0;
; for (int i = 0; i < 100; i++) {
; if (i % 4 == 0) {
; A[s0] = 2; // A[0], A[4], A[8], A[12], ...
; A[s1] = 1; // A[0], A[8], A[16], A[24], ...
; }
; s0 += (1ULL << 62) + 1;
; s1 += (1ULL << 62) + 2;
; }
define void @f(ptr %A) {
entry:
br label %loop.header
loop.header:
%i = phi i64 [ 0, %entry ], [ %i.next, %loop.latch ]
%offset.0 = phi i64 [ 0, %entry ], [ %offset.0.next, %loop.latch ]
%offset.1 = phi i64 [ 0, %entry ], [ %offset.1.next, %loop.latch ]
%idx.0 = getelementptr inbounds i8, ptr %A, i64 %offset.0
%idx.1 = getelementptr inbounds i8, ptr %A, i64 %offset.1
%mask = and i64 %i, 3
%cond = icmp eq i64 %mask, 0
br i1 %cond, label %if.then, label %loop.latch
if.then:
store i8 2, ptr %idx.0
store i8 1, ptr %idx.1
br label %loop.latch
loop.latch:
%i.next = add nuw nsw i64 %i, 1
%offset.0.next = add i64 %offset.0, 4611686018427387905 ; 2^62 + 1
%offset.1.next = add i64 %offset.1, 4611686018427387906 ; 2^62 + 2
%cond.exit = icmp eq i64 %i.next, 100
br i1 %cond.exit, label %exit, label %loop.header
exit:
ret void
}Printing analysis 'Loop Access Analysis' for function 'f':
loop.header:
Memory dependences are safe
Dependences:
Run-time memory checks:
Grouped accesses:
Non vectorizable stores to invariant address were not found in loop.
SCEV assumptions:
Expressions re-written:
The root cause appears to be the inference from nusw in isNoWrap. I think this inference is valid only if the load/store is guaranteed to be executed in every iteration of the loop.
For the following "equivalent" input, LAA reports Unknown (godbolt: https://godbolt.org/z/a7dPvGT4x).
; for (int i = 0; i < 100; i++) {
; if (i % 4 == 0) {
; A[i] = 2; // A[0], A[4], A[8], A[12], ...
; A[i * 2] = 1; // A[0], A[8], A[16], A[24], ...
; }
; }
define void @f(ptr %A) {
entry:
br label %loop.header
loop.header:
%i = phi i64 [ 0, %entry ], [ %i.next, %loop.latch ]
%offset.0 = phi i64 [ 0, %entry ], [ %offset.0.next, %loop.latch ]
%offset.1 = phi i64 [ 0, %entry ], [ %offset.1.next, %loop.latch ]
%idx.0 = getelementptr inbounds nuw i8, ptr %A, i64 %offset.0
%idx.1 = getelementptr inbounds nuw i8, ptr %A, i64 %offset.1
%mask = and i64 %i, 3
%cond = icmp eq i64 %mask, 0
br i1 %cond, label %if.then, label %loop.latch
if.then:
store i8 2, ptr %idx.0
store i8 1, ptr %idx.1
br label %loop.latch
loop.latch:
%i.next = add nuw nsw i64 %i, 1
%offset.0.next = add nuw nsw i64 %offset.0, 1
%offset.1.next = add nuw nsw i64 %offset.1, 2
%cond.exit = icmp eq i64 %i.next, 100
br i1 %cond.exit, label %exit, label %loop.header
exit:
ret void
}Printing analysis 'Loop Access Analysis' for function 'f':
loop.header:
Report: unsafe dependent memory operations in loop. Use #pragma clang loop distribute(enable) to allow loop distribution to attempt to isolate the offending operations into a separate loop
Unknown data dependence.
Dependences:
Unknown:
store i8 2, ptr %idx.0, align 1 ->
store i8 1, ptr %idx.1, align 1
Run-time memory checks:
Grouped accesses:
Non vectorizable stores to invariant address were not found in loop.
SCEV assumptions:
Expressions re-written: