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

Sanjoy Das via llvm-dev llvm-dev at lists.llvm.org
Wed Oct 31 19:27:38 PDT 2018

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

More information about the llvm-dev mailing list