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

[Andrew Trick]

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.)
> 
> 
> In discussions, Andy had expressed a desire to move entirely away from LCSSA and Nick had expressed a desire to do the opposite, so I'd like to start a proper discusison of what people think and why.
> 
> 
> I've worked a lot of preserving both LCSSA and LoopSimplify form in all of our loop passes recently thanks to yanking off the bandaid we've been relying on for the past N years of letting the LoopPassManager simply re-create these at all loop nest levels on the fly as necessary. During the course of that I'm starting to form an opinion on the subject as well.
> 
> I think that SSAUpdater works *great* for passes like GVN and friends that need to fast, incremental patching of the SSA graph. I also think it is completely incompatible with LCSSA in its current form. It just isn't built in a way that would be friendly to preserving this kind of information. I think that's OK, but it means that I think we *can't* mix the two solutions effectively long term. PR18688 is the current manifestation of this madness.
> 
> Consistently, I am finding that doing incremental update and maintaining canonical form for loops is *substantially* simpler with LoopSimplify+LCSSA. The combination is just incredibly powerful. It also has a huge advantage in the way it is structures the updates: they avoid perturbing nested or enclosing loops. This property makes them ideal for working inside-out and iteratively across the loop nest as it is simplified.
> 
> So I would personally want to see a really strong argument against relying on LCSSA. But I'm open to that argument existing, and sending this email to tease it out. =] If we decide to go forward with LCSSA as the canonical form for loops, I'd like to merge LCSSA and LoopSimplify into a single canonicalization pass, and then I'll work harder at re-casting the existing loop optimizations to leverage LCSSA more heavily and simplify their preservation of it as a consequence. Right now, we're just brute-force recomputing LCSSA because we don't really rely on it coming into the pass. It's kind of the worst of both worlds. =/
> 
> -Chandler

I also don't want to get rid of LCSSA (if I said that before, I retract the statement). It can be useful to summarize the loop live-out values.

I think the question is: do we want to be in LCSSA during the early/canonical rounds of IR loop optimization? This is, LoopSimplify, Rotate, LICM, Unswitch, full unrolling (I think full unrolling should run earlier).

Why did I suggest avoiding LCSSA?
(1) Unnecessary overhead.
(2) Phi nodes "in the way".
(3) Awkward pass dependencies.

(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].

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

(3) As you know LCSSA needs to be rerun between passes, which in turn requires the domtree. Generally removing dependence on analysis is a good thing.

So, what's the benefit of LCSSA? 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. LoopUnroll requires LCSSA [2][3]. I don't understand the impact on LoopSimplify.

If LCSSA actually makes writing transformations easier, then I'm all for it. Could you point to some specific transformations that are easier with LCSSA?

-Andy

[1] I admit that LCSSA could be greatly speeding up our implementation of SSAUpdater by restricting the use lists of loop values.

[2] LoopUnroll does an incremental SSA update using LCSSA. SSAUpdater would probably be a batch update after unrolling. SSAUpdater might be a little simpler by separating concerns.

[3] We could make a much more efficient SSAUpdater that works with loop unrolling and the domtree by making use of the information that the old values always dominate the new ones. It is really dumb that our unroller invalidates the domtree.