<div dir="ltr"><div class="gmail_extra"><br><div class="gmail_quote">On Mon, Feb 3, 2014 at 10:42 AM, Andrew Trick <span dir="ltr"><<a href="mailto:atrick@apple.com" target="_blank">atrick@apple.com</a>></span> wrote:<br>
<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"><div id=":542" style="overflow:hidden">I also don't want to get rid of <span class="">LCSSA</span> (if I said that before, I retract the statement). It can be useful to summarize the loop live-out values.<br>

<br>
I think the question is: do we want to be in <span class="">LCSSA</span> during the early/canonical rounds of IR loop optimization? This is, LoopSimplify, Rotate, LICM, Unswitch, full unrolling (I think full unrolling should run earlier).<br>
</div></blockquote><div><br></div><div>Just for clarification, LoopSimplify is not a loop pass, and just creates the canonical loop nest structure with preheaders and exit blocks. LCSSA requires this to have a place for its PHI nodes, not the other way around.</div>
<div><br></div><div>Also, full unrolling already runs as part of the early rounds of the IR loop optimizations just as you say it should. </div><div><br></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">
<div id=":542" style="overflow:hidden">Why did I suggest avoiding <span class="">LCSSA</span>?<br>
(1) Unnecessary overhead.<br>(3) Awkward pass dependencies.<br>
<br>
(1) We're forcing a significant analysis to run between passes to make it easier to update SSA after transformation. But we don't even know if any transformations are needed. I would prefer to use SSAUpdater to handle the transformations as they occur. We could save 1-2% of opt time [1].<br>
</div></blockquote><div><br></div><div>Do you have any measurement of this? I have no evidence that LCSSA is a remotely significant optimization time cost, but I've not gone looking.</div><div> </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">
<div id=":542" style="overflow:hidden">
<br>(3) As you know <span class="">LCSSA</span> needs to be rerun between passes, which in turn requires the domtree. Generally removing dependence on analysis is a good thing.<br></div></blockquote><div><br></div><div>So, we never re-run domtree here. It is preserved throughout, and it is required for LoopInfo, so there is nothing to be saved on that front. AFAICT, there is no analysis dependency cost of LCSSA given the other loop optimizer.</div>
<div><br></div><div>Also, LCSSA *doesn't* need to be re-run between passes. If a pass has LCSSA coming into it, then it is extremely easy to preserve it in place rather than re-running things. We just have a *lot* of bugs because the old loop-pass-manager setup just blindly re-ran LCSSA for us, papering over all manner of badness.</div>
<div> </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"><div id=":542" style="overflow:hidden">
<br>(2) Phi nodes "in the way".<br>(2) SSA based analysis are way simpler when they don't handle phis. They could be adapted to handle single operand phis, but we don't usually bother to check. I don't have a specific issue in mind that would impact the early loop opts.<br>
</div></blockquote><div><br></div><div>Ok, I think this would be the more serious issue if it comes up in practice. I don't have any cases where it comes up in practice for early loop opts either though.</div><div> </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"><div id=":542" style="overflow:hidden"><br>So, what's the benefit of <span class="">LCSSA</span>? I'm told that it makes SSA update easier. I don't understand what could be easier than using an SSAUpdater utility. LoopRotate and LICM already use the updater.</div>
</blockquote><div><br></div><div><snip></div><div><br></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">
<div id=":542" style="overflow:hidden">If <span class="">LCSSA</span> actually makes writing transformations easier, then I'm all for it. Could you point to some specific transformations that are easier with <span class="">LCSSA</span>?</div>
</blockquote></div><br>LICM. There is already a fast path in LICM that is the exact path that LCSSA guarantees exists when sinking code into the exit blocks. The only thing missing is for LICM to actually *use* LCSSA instead of just trying to patch it up if it happens to find it in the loop. I think it would dramatically simplify the entire sinking code.</div>
<div class="gmail_extra"><br></div><div class="gmail_extra">A good use of SSAUpdater: re-forming SSA values *within* a loop body due to mem2reg essentially. LICM has a little mini mem2reg pass in it that uses SSAUpdater. This is a great use and I can't imagine something simpler. The fact that we have LCSSA also makes it faster by bounding the space where it has to rewrite uses (to the edge of the current loop).</div>
<div class="gmail_extra"><br></div><div class="gmail_extra">But if we have LCSSA, we should never need SSAUpdater for updating SSA form across the loop boundary in the way LICM does. Instead we should be able to place an instruction, RAUW it, and insert a PHI node for each operand. Done.</div>
<div class="gmail_extra"><br></div><div class="gmail_extra">Maybe a patch would be better to explain matters? As it happens, fixing LICM this way will also fix PR18753 and a host of other latent bugs where LICM invalidates LCSSA in some far-off loop and we crash later.</div>
</div>