<html><head><meta http-equiv="Content-Type" content="text/html charset=us-ascii"></head><body style="word-wrap: break-word; -webkit-nbsp-mode: space; -webkit-line-break: after-white-space;" class=""><br class=""><div><blockquote type="cite" class=""><div class="">On Jun 30, 2015, at 7:27 PM, Bjarke Roune <<a href="mailto:broune@google.com" class="">broune@google.com</a>> wrote:</div><br class="Apple-interchange-newline"><div class=""><div dir="ltr" class=""><div class="gmail_extra"><div class="gmail_quote">Hi Sanjoy, thanks for your thoughts on this.</div><div class="gmail_quote"><br class=""></div><div class="gmail_quote">On Sat, Jun 27, 2015 at 12:16 AM, Sanjoy Das <span dir="ltr" class=""><<a href="mailto:sanjoy@playingwithpointers.com" target="_blank" class="">sanjoy@playingwithpointers.com</a>></span> wrote:<blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-color:rgb(204,204,204);border-left-style:solid;padding-left:1ex">
First of all, going by the "poison causes UB only when observed", SCEV<br class="">
does not do the right thing currently: [...]<br class="">
<br class=""></blockquote><div class="">That seems like a bug? There's also <span style="font-size:12.8000001907349px" class="">bug 23527 for GEP. Sounds like there might be more such bugs.</span></div><div class=""><br class=""></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-color:rgb(204,204,204);border-left-style:solid;padding-left:1ex">
One way to get what you want and also fix this existing bug(?) is to<br class="">
make the no wrap flags part of a SCEV expression's identity (i.e. make<br class="">
{A,+,B}<nuw> a different expression from {A,+,B}). If you start with<br class="">
the precondition that every <nuw> [0] came from a <nuw> [1] present in<br class="">
the IR, then you don't really have to worry about control dependence<br class="">
-- you can always optimize under the assumption that the SCEV<br class="">
expression does not unsign-overflow; if such an optimization changes<br class="">
program behavior then that program has UB since it was data dependent<br class="">
on poison [2].</blockquote><div class=""><br class=""></div><div class="">To make sure that I understand correctly, are you suggesting making the nuw (and similar) flags part of the key when looking up an SCEV in the UniqueSCEVs member variable on ScalarEvolution? That way, an instruction with nuw and one without will not map to the same SCEV unless the nuw can be inferred in some other way. Sounds good to me, I'm happy to go with either one of that or inferring UB from poison.</div><div class=""><br class=""></div><div class="">Adding the flags to the key/identity does break the idea that mathematically equivalent expressions should cancel if subtracted. Andrew Trick wrote something about that previously:</div><div class=""><br class=""></div><div class=""> <a href="http://lists.cs.uiuc.edu/pipermail/llvm-commits/Week-of-Mon-20141215/249390.html" class="">http://lists.cs.uiuc.edu/pipermail/llvm-commits/Week-of-Mon-20141215/249390.html</a><br class=""></div><div class=""><br class=""></div><div class="">Andrew: I wonder what your view is on this?<br class=""></div><div class=""> </div></div></div></div>
</div></blockquote></div><br class=""><div class=""><div class="">In that thread I was pointing out that with no-wrap flags as part of the expression identity, SCEV loses the ability to reason about or reduce expressions that have a mix of flags. Trivial example:</div><div class="">{0,+,1}<nsw> - {1,+,1}</div><div class=""><br class=""></div><div class="">We can no longer reduce this to constant 1.</div><div class=""><br class=""></div><div class="">OTOH, I've never actually tried this. If the nsw key is limited to recurrences, it might not be terrible in practice. I'm guessing we would at least end up with redundant induction variables though. I won't rule out the idea of adding nsw to the SCEV key, but I'm afraid it will lead to more complexity in the long run.</div><div class=""><br class=""></div><div class="">I think your approach to strengthening SCEV by using a poison value analysis is legitimate. I've considered this approach in the past. I do think that it adds complexity, but is probably the best way to reuse existing LSR. I can see a few alternatives to solving your problem:</div><div class=""><br class=""></div><div class="">(1) Use poison value analysis to inform SCEV. SCEV now sees nsw flags on your recurrence and reduces the expression for you. LSR does the transformation you want.</div><div class=""><br class=""></div><div class="">(2) Add nsw flags to the SCEV key so we don't need poison value analysis. I think this could be problematic, but if Sanjoy really wants to go this route and support the work I won't get in the way.</div><div class=""><br class=""></div><div class="">(3) Write a *simple* IR-level analysis that refactors address expressions to hoist the loop invariant component, informed by the target's addressing mode. This could be a first step in replacing the LSR pass with something more efficient and predictable. This is the approach I would take if I were doing the work. But I can understand not wanting to design a new pass just to handle your case.</div></div><div class=""><br class=""></div><div class="">Andy</div></body></html>