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

[Chandler Carruth]

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