[llvm-dev] SCEV and <nsw>
Alexandre Isoard via llvm-dev
llvm-dev at lists.llvm.org
Wed Oct 31 19:36:04 PDT 2018
Thanks a lot!
On Wed, Oct 31, 2018, 19:27 Sanjoy Das <sanjoy at playingwithpointers.com>
wrote:
> The magic happens in ScalarEvolution::isSCEVExprNeverPoison. You
> should be able to add your special intrinsic to
> llvm::getGuaranteedNonFullPoisonOp for SCEV to pick it up.
>
> -- Sanjoy
>
> On Wed, Oct 31, 2018 at 3:25 PM, Alexandre Isoard
> <alexandre.isoard at gmail.com> wrote:
> > 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/ade714f8/attachment.html>
More information about the llvm-dev
mailing list