<div dir="ltr">I'm not sure I understand the poison/undef/UB distinctions.<div><br></div><div>But on this example:</div><div><br></div><div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex">define i32 @func(i1 zeroext %b, i32 %x, i32 %y) {<br>entry:<br> %adds = add nsw i32 %x, %y<br> %addu = add nuw i32 %x, %y<br> %cond = select i1 %b, i32 %adds, i32 %addu<br> ret i32 %cond<br>}</blockquote></div><div><br></div><div>It is important to not propagate the nsw/nuw between the two SCEV expressions (which unification would do today, can I consider that a bug or is it a feature?).</div><div>So we work-around it by not informing SCEV of the flags:</div><div><br></div><div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex">Printing analysis 'Scalar Evolution Analysis' for function 'func':<br>Classifying expressions for: @func<br> %adds = add nsw i32 %x, %y<br> --> (%x + %y) U: full-set S: full-set<br> %addu = add nuw i32 %x, %y<br> --> (%x + %y) U: full-set S: full-set<br> %cond = select i1 %b, i32 %adds, i32 %addu<br> --> %cond U: full-set S: full-set<br>Determining loop execution counts for: @func</blockquote></div><div><br></div><div>Would there be problems if we properly considered nuw/nsw flags when unifying SCEVs?</div></div><br><div class="gmail_quote"><div dir="ltr">On Wed, Aug 15, 2018 at 1:59 PM Friedman, Eli <<a href="mailto:efriedma@codeaurora.org">efriedma@codeaurora.org</a>> wrote:<br></div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
<div text="#000000" bgcolor="#FFFFFF">
<div class="m_-5001341794010270531moz-cite-prefix">On 8/15/2018 1:31 PM, Alexandre Isoard
wrote:<br>
</div>
<blockquote type="cite">
<div dir="ltr">Is that why we do not deduce +<nsw> from "add
nsw" either?</div>
</blockquote>
<br>
Essentially, yes.<br>
<br>
<blockquote type="cite">
<div dir="ltr">
<div>Is that an intrinsic limitation of creating a
context-invariant expressions from a Value* or is that a
limitation of our implementation (our unification not
considering the nsw flags)?</div>
</div>
</blockquote>
<br>
It's a consequence of unification not considering nsw. (nsw on an
instruction is naturally invariant because violating nsw produces
poison, not UB.)<br>
<br>
-Eli<br>
<br>
<blockquote type="cite"><br>
<div class="gmail_quote">
<div dir="ltr">On Wed, Aug 15, 2018 at 12:39 PM Friedman, Eli
<<a href="mailto:efriedma@codeaurora.org" target="_blank">efriedma@codeaurora.org</a>>
wrote:<br>
</div>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
<div text="#000000" bgcolor="#FFFFFF">
<div class="m_-5001341794010270531m_-6181515349790066455m_-6236410721431341120moz-cite-prefix">On
8/15/2018 12:21 PM, Alexandre Isoard via llvm-dev wrote:<br>
</div>
<blockquote type="cite">
<div dir="ltr">Hello,
<div><br>
</div>
<div>If I run clang on the following code:</div>
<div><br>
</div>
<div>
<blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex">void
func(unsigned n) {<br>
for (unsigned long x = 1; x < n; ++x)<br>
dummy(x);<br>
}</blockquote>
<div><br>
</div>
<div>I get the following llvm ir:</div>
<div><br>
</div>
<div>
<blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex">define void
@func(i32 %n) {<br>
entry:<br>
%conv = zext i32 %n to i64<br>
%cmp5 = icmp ugt i32 %n, 1<br>
br i1 %cmp5, label %for.body, label
%for.cond.cleanup<br>
for.cond.cleanup:
; preds = %for.body, %entry<br>
ret void<br>
for.body:
; preds = %entry, %for.body<br>
%x.06 = phi i64 [ %inc, %for.body ], [ 1, %entry
]<br>
tail call void @dummy(i64 %x.06) #2<br>
%inc = add nuw nsw i64 %x.06, 1<br>
%exitcond = icmp eq i64 %inc, %conv<br>
br i1 %exitcond, label %for.cond.cleanup, label
%for.body<br>
}</blockquote>
</div>
<div><br>
</div>
<div>Over which, SCEV will provide the following
analysis:</div>
<div><br>
</div>
<div>
<blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex">Printing
analysis 'Scalar Evolution Analysis' for function
'func':<br>
Classifying expressions for: @func<br>
%conv = zext i32 %n to i64<br>
--> (zext i32 %n to i64) U: [0,4294967296)
S: [0,4294967296)<br>
%x.06 = phi i64 [ %inc, %for.body ], [ 1, %entry
]<br>
-->
{1,+,1}<nuw><nsw><%for.body> U:
[1,-9223372036854775808) S:
[1,-9223372036854775808)<span style="white-space:pre-wrap"> </span>Exits:
(-1 + (zext i32 %n to i64))<span style="white-space:pre-wrap"> </span>LoopDispositions:
{ %for.body: Computable }<br>
%inc = add nuw nsw i64 %x.06, 1<br>
--> {2,+,1}<nuw><%for.body> U:
[2,0) S: [2,0)<span style="white-space:pre-wrap"> </span>Exits:
(zext i32 %n to i64)<span style="white-space:pre-wrap"> </span>LoopDispositions:
{ %for.body: Computable }<br>
Determining loop execution counts for: @func<br>
Loop %for.body: backedge-taken count is (-2 +
(zext i32 %n to i64))<nsw><br>
Loop %for.body: max backedge-taken count is -2<br>
Loop %for.body: Predicated backedge-taken count is
(-2 + (zext i32 %n to i64))<nsw><br>
Predicates:<br>
Loop %for.body: Trip multiple is 1</blockquote>
</div>
<div><br>
</div>
<div>Now, I was surprised by the max backedge-taken
count being -2, and I suspect it is due to the
backedge-taken count being marked as <nsw>
instead of <nuw>.</div>
<div><br>
</div>
<div>Is that on purpose, is that a bug, or is my
analysis incorrect? I am not sure where to fix that
issue.</div>
</div>
</div>
</blockquote>
<br>
The backedge-taken count isn't nuw because nsw/nuw markings
aren't flow-sensitive: there isn't any way to mark the trip
count as nuw without marking every computation of
`(long)n-2` as nuw.<br>
<br>
There's some code in ScalarEvolution::howFarToZero to try to
refine the max backedge-taken count in some cases, but it
isn't very general. See <a class="m_-5001341794010270531m_-6181515349790066455m_-6236410721431341120moz-txt-link-freetext" href="https://reviews.llvm.org/D28536" target="_blank">https://reviews.llvm.org/D28536</a>
.<br>
<br>
-Eli<br>
<pre class="m_-5001341794010270531m_-6181515349790066455m_-6236410721431341120moz-signature" cols="72">--
Employee of Qualcomm Innovation Center, Inc.
Qualcomm Innovation Center, Inc. is a member of Code Aurora Forum, a Linux Foundation Collaborative Project</pre>
</div>
</blockquote>
</div>
<br clear="all">
<div><br>
</div>
-- <br>
<div dir="ltr" class="m_-5001341794010270531m_-6181515349790066455gmail_signature" data-smartmail="gmail_signature">
<div dir="ltr"><b>Alexandre Isoard</b><br>
</div>
</div>
</blockquote>
<p><br>
</p>
<pre class="m_-5001341794010270531moz-signature" cols="72">--
Employee of Qualcomm Innovation Center, Inc.
Qualcomm Innovation Center, Inc. is a member of Code Aurora Forum, a Linux Foundation Collaborative Project</pre>
</div>
</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>