[llvm-dev] SCEV and (original) (raw)

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 ) 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}<%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 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}<%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 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