[LLVMdev] [RFC] LCSSA vs. SSAUpdater ... FIGHT!

[Chandler Carruth]

On Fri, Feb 7, 2014 at 11:29 AM, Chris Lattner <clattner at apple.com> wrote:

> On Feb 1, 2014, at 4:33 AM, Chandler Carruth <chandlerc at gmail.com> wrote:
>
> > So, there are two primary ideas behind SSA form management in the loop
> optimizers of LLVM:
> >
> > - Require LCSSA form input, leverage its (very powerful) guarantees to
> simplify maintaining SSA form, and also maintain LCSSA form.
> >
> > - 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.
> >
> > (Note, there are plenty of places where SSAUpdater makes sense, so this
> isn't really about doing away with it at all.)
>
> 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.
>
> My gripes are three fold:

1) SSAUpdater can handle anything that LCSSA simplifies


Yes, it can, but it is *significantly* less simple. I think the simplicity
of reasoning and handling things with LCSSA is not without value.


> 2) that LCSSA is annoying to keep up to date


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).


> 3) LCSSA burns compile time optimistically rewriting loop values, which
> are then later collapsed away even if nothing cares about those values.
>

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.

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.


>
> My personal preference would be to get rid of LCSSA completely, but I
> don’t know how to stage that.


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.


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.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20140207/73e98ac0/attachment.html>