<div dir="ltr">Thanks.<div><br></div><div>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?</div><div><br></div><div>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?</div><div><br></div><div>I don't see where that dark magic is performed. :-)</div></div><br><div class="gmail_quote"><div dir="ltr">On Mon, Oct 29, 2018 at 10:52 PM Sanjoy Das <<a href="mailto:sanjoy@playingwithpointers.com">sanjoy@playingwithpointers.com</a>> wrote:<br></div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">The problem here is that SCEV expressions are keyed on their operands<br>
but not on the no-wrap flags. So if we have<br>
<br>
%i = phi i32 [ 0, %loop.prehead ], [ %i.next, %loop.body ]<br>
%i.96 = add nsw i32 %i, 96<br>
%i.96.wrapping = add i32 %i, 96<br>
<br>
then both %i.96 and %i.96.wrapping will be mapped to the SCEV*. Ergo<br>
that common SCEV* cannot have the NSW bit set.<br>
<br>
Now if the IR is actually<br>
<br>
%i = phi i32 [ 0, %loop.prehead ], [ %i.next, %loop.body ]<br>
%i.96 = add nsw i32 %i, 96<br>
%i.96.wrapping = add i32 %i, 96<br>
%store.addr = getelementptr i32, i32* %A, i32 %i.96<br>
store i32 %i, i32* %store.addr, align 4<br>
<br>
then if %i.96 overflows the program has undefined behavior since we'll<br>
try to store *to* poison. So in this case we can map both %i.96 and<br>
%i.96.wrapping to a NSW SCEV*<br>
<br>
Does that help?<br>
-- Sanjoy<br>
<br>
On Fri, Oct 26, 2018 at 11:12 AM, Alexandre Isoard via llvm-dev<br>
<<a href="mailto:llvm-dev@lists.llvm.org" target="_blank">llvm-dev@lists.llvm.org</a>> wrote:<br>
> I finally managed to reproduce the issue:<br>
><br>
> define void @bad(i32* %A, i32 %x) {<br>
> entry:<br>
> %do = icmp slt i32 0, %x<br>
> br i1 %do, label %loop.prehead, label %exit<br>
><br>
> loop.prehead: ; preds = %entry<br>
> br label %loop.body<br>
><br>
> loop.body: ; preds = %loop.body,<br>
> %loop.prehead<br>
> %i = phi i32 [ 0, %loop.prehead ], [ %i.next, %loop.body ]<br>
> %i.next = add nsw i32 %i, 1<br>
> %i.96 = add nsw i32 %i, 96<br>
> %store.addr = getelementptr i32, i32* %A, i32 %i.next<br>
> store i32 %i, i32* %store.addr, align 4<br>
> %cmp = icmp slt i32 %i.next, %x<br>
> br i1 %cmp, label %loop.body, label %loop.exit<br>
><br>
> loop.exit: ; preds = %loop.body<br>
> br label %exit<br>
><br>
> exit: ; preds = %loop.exit,<br>
> %entry<br>
> ret void<br>
> }<br>
><br>
> ; Printing analysis 'Scalar Evolution Analysis' for function 'bad':<br>
> ; Classifying expressions for: @bad<br>
> ; %i = phi i32 [ 0, %loop.prehead ], [ %i.next, %loop.body ]<br>
> ; --> {0,+,1}<nuw><nsw><%loop.body> U: [0,2147483647) S: [0,2147483647)<br>
> Exits: (-1 + %x) LoopDispositions: { %loop.body: Computable }<br>
> ; %i.next = add nsw i32 %i, 1<br>
> ; --> {1,+,1}<nuw><nsw><%loop.body> U: [1,-2147483648) S: [1,-2147483648)<br>
> Exits: %x LoopDispositions: { %loop.body: Computable }<br>
> ; %i.96 = add nsw i32 %i, 96<br>
> ; --> {96,+,1}<nuw><%loop.body> U: [96,-2147483553) S: [96,-2147483553)<br>
> Exits: (95 + %x) LoopDispositions: { %loop.body: Computable }<br>
> ; %store.addr = getelementptr i32, i32* %A, i32 %i.next<br>
> ; --> {(8 + %A),+,8}<%loop.body> U: full-set S: full-set Exits: (8 + (8 *<br>
> (zext i32 (-1 + %x) to i64)) + %A) LoopDispositions: { %loop.body:<br>
> Computable }<br>
> ; Determining loop execution counts for: @bad<br>
> ; Loop %loop.body: backedge-taken count is (-1 + %x)<br>
> ; Loop %loop.body: max backedge-taken count is 2147483646<br>
> ; Loop %loop.body: Predicated backedge-taken count is (-1 + %x)<br>
> ; Predicates:<br>
> ;<br>
> ; Loop %loop.body: Trip multiple is 1<br>
><br>
> define void @good(i32* %A, i32 %x) {<br>
> entry:<br>
> %do = icmp slt i32 0, %x<br>
> br i1 %do, label %loop.prehead, label %exit<br>
><br>
> loop.prehead: ; preds = %entry<br>
> br label %loop.body<br>
><br>
> loop.body: ; preds = %loop.body,<br>
> %loop.prehead<br>
> %i = phi i32 [ 0, %loop.prehead ], [ %i.next, %loop.body ]<br>
> %i.next = add nsw i32 %i, 1<br>
> %i.96 = add nsw i32 %i, 96<br>
> %store.addr = getelementptr i32, i32* %A, i32 %i.96<br>
> store i32 %i, i32* %store.addr, align 4<br>
> %cmp = icmp slt i32 %i.next, %x<br>
> br i1 %cmp, label %loop.body, label %loop.exit<br>
><br>
> loop.exit: ; preds = %loop.body<br>
> br label %exit<br>
><br>
> exit: ; preds = %loop.exit,<br>
> %entry<br>
> ret void<br>
> }<br>
><br>
> ; Printing analysis 'Scalar Evolution Analysis' for function 'good':<br>
> ; Classifying expressions for: @good<br>
> ; %i = phi i32 [ 0, %loop.prehead ], [ %i.next, %loop.body ]<br>
> ; --> {0,+,1}<nuw><nsw><%loop.body> U: [0,2147483647) S: [0,2147483647)<br>
> Exits: (-1 + %x) LoopDispositions: { %loop.body: Computable }<br>
> ; %i.next = add nsw i32 %i, 1<br>
> ; --> {1,+,1}<nuw><nsw><%loop.body> U: [1,-2147483648) S: [1,-2147483648)<br>
> Exits: %x LoopDispositions: { %loop.body: Computable }<br>
> ; %i.96 = add nsw i32 %i, 96<br>
> ; --> {96,+,1}<nuw><nsw><%loop.body> U: [96,-2147483648) S:<br>
> [96,-2147483648) Exits: (95 + %x) LoopDispositions: { %loop.body: Computable<br>
> }<br>
> ; %store.addr = getelementptr i32, i32* %A, i32 %i.96<br>
> ; --> {(768 + %A),+,8}<%loop.body> U: full-set S: full-set Exits: (768 +<br>
> (8 * (zext i32 (-1 + %x) to i64)) + %A) LoopDispositions: { %loop.body:<br>
> Computable }<br>
> ; Determining loop execution counts for: @good<br>
> ; Loop %loop.body: backedge-taken count is (-1 + %x)<br>
> ; Loop %loop.body: max backedge-taken count is 2147483646<br>
> ; Loop %loop.body: Predicated backedge-taken count is (-1 + %x)<br>
> ; Predicates:<br>
> ;<br>
> ; Loop %loop.body: Trip multiple is 1<br>
><br>
> Notice the only difference is on the gep (in bold). Can somebody shed some<br>
> light?<br>
><br>
> I attached the test file.<br>
><br>
> On Fri, Oct 26, 2018 at 10:41 AM Alexandre Isoard<br>
> <<a href="mailto:alexandre.isoard@gmail.com" target="_blank">alexandre.isoard@gmail.com</a>> wrote:<br>
>><br>
>> Hello,<br>
>><br>
>> I'm running into an issue where SCEV misses explicit nsw flags on the<br>
>> following expressions:<br>
>><br>
>> %mm.07 = phi i32 [ 0, %<a href="http://for.body.lr.ph" rel="noreferrer" target="_blank">for.body.lr.ph</a> ], [ %add, %for.inc30 ]<br>
>> --> {0,+,1}<nuw><nsw><%for.body> U: [0,2147483647) S: [0,2147483647)<br>
>> Exits: (-1 + %m) LoopDispositions: { %for.body: Computable, %for.body5:<br>
>> Invariant, %for.inc: Invariant }<br>
>> %add = add nsw i32 %mm.07, 1<br>
>> --> {1,+,1}<nuw><nsw><%for.body> U: [1,-2147483648) S: [1,-2147483648)<br>
>> Exits: %m LoopDispositions: { %for.body: Computable, %for.body5: Invariant,<br>
>> %for.inc: Invariant }<br>
>> %add2 = add nsw i32 %mm.07, 96<br>
>> --> {96,+,1}<nuw><%for.body> U: [96,-2147483553) S: [96,-2147483553)<br>
>> Exits: (95 + %m) LoopDispositions: { %for.body: Computable, %for.body5:<br>
>> Invariant, %for.inc: Invariant }<br>
>><br>
>> My problem is with the later one, where the <nsw> is missing (which cause<br>
>> me problems down the line with gep computation on 64 bit address space).<br>
>><br>
>> Any clue as to what could be the source of that disappearance? I tried to<br>
>> reproduce the issue on simple cases but to no avail. I get the following<br>
>> expected result:<br>
>><br>
>> %i = phi i32 [ 0, %loop.prehead ], [ %i.next, %loop.body ]<br>
>> --> {0,+,1}<nuw><nsw><%loop.body> U: [0,2147483647) S: [0,2147483647)<br>
>> Exits: (-1 + %x) LoopDispositions: { %loop.body: Computable }<br>
>> %i.next = add nsw i32 %i, 1<br>
>> --> {1,+,1}<nuw><nsw><%loop.body> U: [1,-2147483648) S: [1,-2147483648)<br>
>> Exits: %x LoopDispositions: { %loop.body: Computable }<br>
>> %i.96 = add nsw i32 %i, 96<br>
>> --> {96,+,1}<nuw><nsw><%loop.body> U: [96,-2147483648) S:<br>
>> [96,-2147483648) Exits: (95 + %x) LoopDispositions: { %loop.body: Computable<br>
>> }<br>
>><br>
>> Help?<br>
>><br>
>> --<br>
>> Alexandre Isoard<br>
><br>
><br>
><br>
> --<br>
> Alexandre Isoard<br>
><br>
> _______________________________________________<br>
> LLVM Developers mailing list<br>
> <a href="mailto:llvm-dev@lists.llvm.org" target="_blank">llvm-dev@lists.llvm.org</a><br>
> <a href="http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev" rel="noreferrer" target="_blank">http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev</a><br>
><br>
</blockquote></div><br clear="all"><div><br></div>-- <br><div dir="ltr" class="gmail_signature" data-smartmail="gmail_signature"><div dir="ltr"><b>Alexandre Isoard</b><br></div></div>