[llvm-dev] SCEV and <nsw>
Alexandre Isoard via llvm-dev
llvm-dev at lists.llvm.org
Wed Oct 31 15:25:56 PDT 2018
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 <nsw>) 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 at 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 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
> >
>
--
*Alexandre Isoard*
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20181031/8e27b623/attachment.html>
More information about the llvm-dev
mailing list