(original) (raw)
Thanks.
So if I understand correctly, this works because we deduce a property that is guaranteed by the fact that else a poison value (thanks to ) would become observable (thanks to the store)? In the code base, where would that info taken into consideration?
My issue is that I have a custom intrinsic that take an address as an argument (and I consider doing so guarantee the address is valid, as I actually preload it). How would I add semantic so that SCEV do the same kind of reasoning as for a store?
I don't see where that dark magic is performed. :-)
On Mon, Oct 29, 2018 at 10:52 PM Sanjoy Das <sanjoy@playingwithpointers.com> wrote:
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@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}<%loop.body> U: \[0,2147483647) S: \[0,2147483647)
\> Exits: (-1 + %x) LoopDispositions: { %loop.body: Computable }
\> ; %i.next = add nsw i32 %i, 1
\> ; --> {1,+,1}<%loop.body> U: \[1,-2147483648) S: \[1,-2147483648)
\> Exits: %x LoopDispositions: { %loop.body: Computable }
\> ; %i.96 = add nsw i32 %i, 96
\> ; --> {96,+,1}<%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}<%loop.body> U: \[0,2147483647) S: \[0,2147483647)
\> Exits: (-1 + %x) LoopDispositions: { %loop.body: Computable }
\> ; %i.next = add nsw i32 %i, 1
\> ; --> {1,+,1}<%loop.body> U: \[1,-2147483648) S: \[1,-2147483648)
\> Exits: %x LoopDispositions: { %loop.body: Computable }
\> ; %i.96 = add nsw i32 %i, 96
\> ; --> {96,+,1}<%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@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}<%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}<%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}<%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 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}<%loop.body> U: \[0,2147483647) S: \[0,2147483647)
\>> Exits: (-1 + %x) LoopDispositions: { %loop.body: Computable }
\>> %i.next = add nsw i32 %i, 1
\>> --> {1,+,1}<%loop.body> U: \[1,-2147483648) S: \[1,-2147483648)
\>> Exits: %x LoopDispositions: { %loop.body: Computable }
\>> %i.96 = add nsw i32 %i, 96
\>> --> {96,+,1}<%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@lists.llvm.org
\> http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
\>
Alexandre Isoard