[llvm-dev] SCEV and <nsw>
Sanjoy Das via llvm-dev
llvm-dev at lists.llvm.org
Mon Oct 29 22:52:25 PDT 2018
The problem here is that SCEV expressions are keyed on their operands
but not on the no-wrap flags. So if we have
%i = phi i32 [ 0, %loop.prehead ], [ %i.next, %loop.body ]
%i.96 = add nsw i32 %i, 96
%i.96.wrapping = add i32 %i, 96
then both %i.96 and %i.96.wrapping will be mapped to the SCEV*. Ergo
that common SCEV* cannot have the NSW bit set.
Now if the IR is actually
%i = phi i32 [ 0, %loop.prehead ], [ %i.next, %loop.body ]
%i.96 = add nsw i32 %i, 96
%i.96.wrapping = add i32 %i, 96
%store.addr = getelementptr i32, i32* %A, i32 %i.96
store i32 %i, i32* %store.addr, align 4
then if %i.96 overflows the program has undefined behavior since we'll
try to store *to* poison. So in this case we can map both %i.96 and
%i.96.wrapping to a NSW SCEV*
Does that help?
-- Sanjoy
On Fri, Oct 26, 2018 at 11:12 AM, Alexandre Isoard via llvm-dev
<llvm-dev at lists.llvm.org> wrote:
> I finally managed to reproduce the issue:
>
> define void @bad(i32* %A, i32 %x) {
> entry:
> %do = icmp slt i32 0, %x
> br i1 %do, label %loop.prehead, label %exit
>
> loop.prehead: ; preds = %entry
> br label %loop.body
>
> loop.body: ; preds = %loop.body,
> %loop.prehead
> %i = phi i32 [ 0, %loop.prehead ], [ %i.next, %loop.body ]
> %i.next = add nsw i32 %i, 1
> %i.96 = add nsw i32 %i, 96
> %store.addr = getelementptr i32, i32* %A, i32 %i.next
> store i32 %i, i32* %store.addr, align 4
> %cmp = icmp slt i32 %i.next, %x
> br i1 %cmp, label %loop.body, label %loop.exit
>
> loop.exit: ; preds = %loop.body
> br label %exit
>
> exit: ; preds = %loop.exit,
> %entry
> ret void
> }
>
> ; Printing analysis 'Scalar Evolution Analysis' for function 'bad':
> ; Classifying expressions for: @bad
> ; %i = phi i32 [ 0, %loop.prehead ], [ %i.next, %loop.body ]
> ; --> {0,+,1}<nuw><nsw><%loop.body> U: [0,2147483647) S: [0,2147483647)
> Exits: (-1 + %x) LoopDispositions: { %loop.body: Computable }
> ; %i.next = add nsw i32 %i, 1
> ; --> {1,+,1}<nuw><nsw><%loop.body> U: [1,-2147483648) S: [1,-2147483648)
> Exits: %x LoopDispositions: { %loop.body: Computable }
> ; %i.96 = add nsw i32 %i, 96
> ; --> {96,+,1}<nuw><%loop.body> U: [96,-2147483553) S: [96,-2147483553)
> Exits: (95 + %x) LoopDispositions: { %loop.body: Computable }
> ; %store.addr = getelementptr i32, i32* %A, i32 %i.next
> ; --> {(8 + %A),+,8}<%loop.body> U: full-set S: full-set Exits: (8 + (8 *
> (zext i32 (-1 + %x) to i64)) + %A) LoopDispositions: { %loop.body:
> Computable }
> ; Determining loop execution counts for: @bad
> ; Loop %loop.body: backedge-taken count is (-1 + %x)
> ; Loop %loop.body: max backedge-taken count is 2147483646
> ; Loop %loop.body: Predicated backedge-taken count is (-1 + %x)
> ; Predicates:
> ;
> ; Loop %loop.body: Trip multiple is 1
>
> define void @good(i32* %A, i32 %x) {
> entry:
> %do = icmp slt i32 0, %x
> br i1 %do, label %loop.prehead, label %exit
>
> loop.prehead: ; preds = %entry
> br label %loop.body
>
> loop.body: ; preds = %loop.body,
> %loop.prehead
> %i = phi i32 [ 0, %loop.prehead ], [ %i.next, %loop.body ]
> %i.next = add nsw i32 %i, 1
> %i.96 = add nsw i32 %i, 96
> %store.addr = getelementptr i32, i32* %A, i32 %i.96
> store i32 %i, i32* %store.addr, align 4
> %cmp = icmp slt i32 %i.next, %x
> br i1 %cmp, label %loop.body, label %loop.exit
>
> loop.exit: ; preds = %loop.body
> br label %exit
>
> exit: ; preds = %loop.exit,
> %entry
> ret void
> }
>
> ; Printing analysis 'Scalar Evolution Analysis' for function 'good':
> ; Classifying expressions for: @good
> ; %i = phi i32 [ 0, %loop.prehead ], [ %i.next, %loop.body ]
> ; --> {0,+,1}<nuw><nsw><%loop.body> U: [0,2147483647) S: [0,2147483647)
> Exits: (-1 + %x) LoopDispositions: { %loop.body: Computable }
> ; %i.next = add nsw i32 %i, 1
> ; --> {1,+,1}<nuw><nsw><%loop.body> U: [1,-2147483648) S: [1,-2147483648)
> Exits: %x LoopDispositions: { %loop.body: Computable }
> ; %i.96 = add nsw i32 %i, 96
> ; --> {96,+,1}<nuw><nsw><%loop.body> U: [96,-2147483648) S:
> [96,-2147483648) Exits: (95 + %x) LoopDispositions: { %loop.body: Computable
> }
> ; %store.addr = getelementptr i32, i32* %A, i32 %i.96
> ; --> {(768 + %A),+,8}<%loop.body> U: full-set S: full-set Exits: (768 +
> (8 * (zext i32 (-1 + %x) to i64)) + %A) LoopDispositions: { %loop.body:
> Computable }
> ; Determining loop execution counts for: @good
> ; Loop %loop.body: backedge-taken count is (-1 + %x)
> ; Loop %loop.body: max backedge-taken count is 2147483646
> ; Loop %loop.body: Predicated backedge-taken count is (-1 + %x)
> ; Predicates:
> ;
> ; Loop %loop.body: Trip multiple is 1
>
> Notice the only difference is on the gep (in bold). Can somebody shed some
> light?
>
> I attached the test file.
>
> On Fri, Oct 26, 2018 at 10:41 AM Alexandre Isoard
> <alexandre.isoard at gmail.com> wrote:
>>
>> Hello,
>>
>> I'm running into an issue where SCEV misses explicit nsw flags on the
>> following expressions:
>>
>> %mm.07 = phi i32 [ 0, %for.body.lr.ph ], [ %add, %for.inc30 ]
>> --> {0,+,1}<nuw><nsw><%for.body> U: [0,2147483647) S: [0,2147483647)
>> Exits: (-1 + %m) LoopDispositions: { %for.body: Computable, %for.body5:
>> Invariant, %for.inc: Invariant }
>> %add = add nsw i32 %mm.07, 1
>> --> {1,+,1}<nuw><nsw><%for.body> U: [1,-2147483648) S: [1,-2147483648)
>> Exits: %m LoopDispositions: { %for.body: Computable, %for.body5: Invariant,
>> %for.inc: Invariant }
>> %add2 = add nsw i32 %mm.07, 96
>> --> {96,+,1}<nuw><%for.body> U: [96,-2147483553) S: [96,-2147483553)
>> Exits: (95 + %m) LoopDispositions: { %for.body: Computable, %for.body5:
>> Invariant, %for.inc: Invariant }
>>
>> My problem is with the later one, where the <nsw> is missing (which cause
>> me problems down the line with gep computation on 64 bit address space).
>>
>> Any clue as to what could be the source of that disappearance? I tried to
>> reproduce the issue on simple cases but to no avail. I get the following
>> expected result:
>>
>> %i = phi i32 [ 0, %loop.prehead ], [ %i.next, %loop.body ]
>> --> {0,+,1}<nuw><nsw><%loop.body> U: [0,2147483647) S: [0,2147483647)
>> Exits: (-1 + %x) LoopDispositions: { %loop.body: Computable }
>> %i.next = add nsw i32 %i, 1
>> --> {1,+,1}<nuw><nsw><%loop.body> U: [1,-2147483648) S: [1,-2147483648)
>> Exits: %x LoopDispositions: { %loop.body: Computable }
>> %i.96 = add nsw i32 %i, 96
>> --> {96,+,1}<nuw><nsw><%loop.body> U: [96,-2147483648) S:
>> [96,-2147483648) Exits: (95 + %x) LoopDispositions: { %loop.body: Computable
>> }
>>
>> Help?
>>
>> --
>> Alexandre Isoard
>
>
>
> --
> Alexandre Isoard
>
> _______________________________________________
> LLVM Developers mailing list
> llvm-dev at lists.llvm.org
> http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
>
More information about the llvm-dev
mailing list