<html>
<head>
<meta http-equiv="Content-Type" content="text/html; charset=utf-8">
</head>
<body text="#000000" bgcolor="#FFFFFF">
<div class="moz-cite-prefix">On 8/15/2018 2:27 PM, Alexandre Isoard
wrote:<br>
</div>
<blockquote type="cite"
cite="mid:CANLM5LdW2AytatPZtADh1+MM-fGaKo3Ydz04_sPfRUznT-B7nA@mail.gmail.com">
<meta http-equiv="content-type" content="text/html; charset=utf-8">
<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>
</blockquote>
<br>
It's an intentional design choice.<br>
<br>
<blockquote type="cite"
cite="mid:CANLM5LdW2AytatPZtADh1+MM-fGaKo3Ydz04_sPfRUznT-B7nA@mail.gmail.com">
<div dir="ltr">
<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>
</blockquote>
<br>
There would be other consequences. For example, `(%x +
%y)<nsw>` and `(%x + %y)<nuw>` wouldn't compare equal
for other simplifications, and all the places that call
setNoWrapFlags would have to be rewritten. It's probably possible
to come up with some workable design, but nobody has actually tried
it, so it's not clear how much work it would be to implement, or
whether it would improve the generated code overall.<br>
<br>
-Eli<br>
<br>
<blockquote type="cite"
cite="mid:CANLM5LdW2AytatPZtADh1+MM-fGaKo3Ydz04_sPfRUznT-B7nA@mail.gmail.com"><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"
moz-do-not-send="true">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" moz-do-not-send="true">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" moz-do-not-send="true">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>
</blockquote>
<p><br>
</p>
<pre class="moz-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>
</body>
</html>