<div dir="ltr"><div class="gmail_extra"><br><div class="gmail_quote">On Fri, Feb 7, 2014 at 11:29 AM, Chris Lattner <span dir="ltr"><<a href="mailto:clattner@apple.com" target="_blank">clattner@apple.com</a>></span> wrote:<br>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div class="">On Feb 1, 2014, at 4:33 AM, Chandler Carruth <<a href="mailto:chandlerc@gmail.com">chandlerc@gmail.com</a>> wrote:<br>

<br>
> So, there are two primary ideas behind SSA form management in the loop optimizers of LLVM:<br>
><br>
> - Require LCSSA form input, leverage its (very powerful) guarantees to simplify maintaining SSA form, and also maintain LCSSA form.<br>
><br>
> - Don't bother with LCSSA form input, assume the worst, and use powerful incremental SSA formation utilities built on SSAUpdater to form SSA on demand when needed.<br>
><br>
> (Note, there are plenty of places where SSAUpdater makes sense, so this isn't really about doing away with it at all.)<br>
<br>
</div>It’s worth noting that LCSSA predates SSAUpdater.  If I went back in time and knew what I knew now, I wouldn’t have gone with LCSSA.<br>
<br>
My gripes are three fold: </blockquote><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">1) SSAUpdater can handle anything that LCSSA simplifies</blockquote><div><br></div>
<div>Yes, it can, but it is *significantly* less simple. I think the simplicity of reasoning and handling things with LCSSA is not without value.</div><div> </div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
2) that LCSSA is annoying to keep up to date</blockquote><div><br></div><div>I have not found that to be the case. There are many places where we fail to keep it up to date that have to be fixed, but as far as I can tell none of these are due to the complexity, slowness, or challenge of keeping it up to date. We just "forgot" (in that the loop pass manager made everything work without any effort but with considerable compile time cost).</div>
<div> </div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">3) LCSSA burns compile time optimistically rewriting loop values, which are then later collapsed away even if nothing cares about those values.<br>
</blockquote><div><br></div><div>Sure. Put another way though, LCSSA puts the SSA graph into the "canonical form" that simplifies the model of writing loop passes. I'm not really disagreeing with you here, just saying that there is a tradeoff.</div>
<div><br></div><div>My suspicion having worked on this quite a bit now is that about 80% of the compile time we are burning on LCSSA is due to failures to update LCSSA appropriately in places where it is both convenient and simple to do so.</div>
<div> </div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
<br>
My personal preference would be to get rid of LCSSA completely, but I don’t know how to stage that.</blockquote></div><br></div><div class="gmail_extra">OK, I'm not *really* invested one way or the other. But having hacked on the loop optimizer somewhat over the past 3 weeks, I have to say LCSSA form has always been easier to reason about, debug, and transform. Perhaps I'll run out of that warm fuzzy feeling, but so far its holding. And several others have seemed to like LCSSA when I talked to them, so I don't want it to be dismissed out of hand.</div>
<div class="gmail_extra"><br></div><div class="gmail_extra"><br></div><div class="gmail_extra">Either way, we *must* make a decision. The current state is untenable as passes flagrantly destroy LCSSA making it very expensive indeed to recompute. And we have to recompute it because a decent number of passes really do rely on it. Interestingly, many of the *users* of LCSSA are not rebuilding SSA form! They're using it to capture loop live-out values very quickly, which is a very useful property IMO. As I mentioned in the thread to Andy, there seem to still be clear uses for SSAUpdater to update SSA values, and it merely needs to be able to incrementally preserve LCSSA rather than breaking it. That doesn't seem like a ton of code to me, so I think we can reasonably go either way. The tradeoff is in complexity of loop passes' analysis and transforms of live-out values vs. the complexity of canonicalizing to LCSSA and preserving it through the loop pass pipeline.</div>
</div>