<html>
<head>
<meta http-equiv="Content-Type" content="text/html; charset=UTF-8">
</head>
<body>
<p>Alexandre,</p>
<p>You've stumbled into one of the dark ugly corners of SCEV.
Welcome!</p>
<p>There's actually some related discussion happening on this right
now. <a class="moz-txt-link-freetext" href="https://reviews.llvm.org/D106852">https://reviews.llvm.org/D106852</a> is a good starting place.
Depending on your interest level, you might find my writeup
(linked from comments on the review) helpful.</p>
<p>The short summary here is that SCEV's handling of flags is
demonstrateably broken. There's no firm agreement on what the
semantics should be, and all of the options have serious
downsides. At the moment, the focus is on avoiding miscompiles,
but finding a way to expose additional optimization potential in
the process is definitely in scope as well.</p>
<p>Philip<br>
</p>
<div class="moz-cite-prefix">On 9/8/21 7:00 PM, Alexandre Isoard via
llvm-dev wrote:<br>
</div>
<blockquote type="cite"
cite="mid:CANLM5LeXJBVazHM5X3hZxPQdBP1XTG9H4Ovueo=t3bv2OH3Pzw@mail.gmail.com">
<meta http-equiv="content-type" content="text/html; charset=UTF-8">
<div dir="ltr">Hello,
<div><br>
</div>
<div>We recently came into an issue in indvars that made it
generate relatively poor IR (we are still working on making a
minimal example) but we tracked it down to a ScalarEvolution
limitation.</div>
<div>Namely, when we uniquify SCEVs we do not account for
NSW/NUW flags.</div>
<div><br>
</div>
<div>A typical example, let's say, when producing the SCEV for a
zext, we will first check if we already produced one of the
same kind:</div>
<div><br>
</div>
<div>const SCEV *ScalarEvolution::getZeroExtendExpr(const SCEV
*Op, Type *Ty, unsigned Depth) {</div>
<div>...</div>
<div> // Before doing any expensive analysis, check to see if
we've already<br>
// computed a SCEV for this Op and Ty.<br>
</div>
<div> ID.AddInteger(scZeroExtend);<br>
ID.AddPointer(Op);<br>
ID.AddPointer(Ty);<br>
<br>
void *IP = nullptr;<br>
if (const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(ID, IP))
return S;<br>
</div>
<div>...</div>
<div>}</div>
<div><br>
</div>
<div>So as to always produce the exact same pointer, and also
speed-up the computation. That is, we do not try to simplify
that SCEV as the only way it is in the table, is if an earlier
attempt didn't succeed in simplifying it. But in the case of
zext, there are simplification patterns that depends on the
presence (or absence) of NSW/NUW in the SCEV of the operand,
so this has some consequences.</div>
<div><br>
</div>
<div>A typical scenario is:</div>
<div>1) we compute the a zext on an expression that doesn't have
any NUW/NSW flag, it can't be simplified, and we produce the
SCEVZeroExtendExpr(Op);</div>
<div>2) we compute the zext on an expression that does have
NUW/NSW flags, we get the same SCEV pointer on that Op (as we
don't account for NUW/NSW flags in uniquification), and the
quick check return that we already have a
SCEVZeroExtendExpr(Op) available, and we don't even try to
simplify it<br>
<br>
On the other hand, if we build the SCEV of the 2) case first,
we will simplify the expression, and build a simpler SCEV...
until we build the one for case 1).</div>
<div><br>
</div>
<div>A small modification of the above code, as follow:</div>
<div><br>
</div>
<div>
<div>const SCEV *ScalarEvolution::getZeroExtendExpr(const SCEV
*Op, Type *Ty, unsigned Depth) {</div>
<div>...</div>
<div> // Before doing any expensive analysis, check to see if
we've already<br>
// computed a SCEV for this Op and Ty.<br>
</div>
<div> ID.AddInteger(scZeroExtend);<br>
ID.AddPointer(Op);<br>
ID.AddPointer(Ty);<br>
<b> if (const SCEVNAryExpr *NAE =
dyn_cast<SCEVNAryExpr>(Op))<br>
ID.AddInteger(NAE->getNoWrapFlags());</b><br>
void *IP = nullptr;<br>
if (const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(ID,
IP)) return S;<br>
</div>
<div>...</div>
<div>}</div>
<div><br>
</div>
</div>
<div>Make this specific issue disappear. But I have a few
questions:</div>
<div>A) Is this safe? Does this break some implicit assumption
about SCEV uniquification?</div>
<div>B) Are we okay with that issue? Is that a known compile
time / analysis quality trade-off?</div>
<div><br>
</div>
<div>Note that this was an issue seen in 7.0, we are going to
try to reproduce it in an up-to-date version. It's quite
tricky to "show" the problem because it depends heavily on the
order in which ScalarEvolution is queried.</div>
<div><br>
</div>
<div>Thanks in advance.</div>
<div>
<div><br>
</div>
-- <br>
<div dir="ltr" class="gmail_signature"
data-smartmail="gmail_signature">
<div dir="ltr"><b>Alexandre Isoard</b><br>
</div>
</div>
</div>
</div>
<br>
<fieldset class="mimeAttachmentHeader"></fieldset>
<pre class="moz-quote-pre" wrap="">_______________________________________________
LLVM Developers mailing list
<a class="moz-txt-link-abbreviated" href="mailto:llvm-dev@lists.llvm.org">llvm-dev@lists.llvm.org</a>
<a class="moz-txt-link-freetext" href="https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev">https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev</a>
</pre>
</blockquote>
</body>
</html>