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

[Hal Finkel]

----- Original Message -----
> From: "Chandler Carruth" <chandlerc at gmail.com>
> To: "Andy Trick" <atrick at apple.com>, nicholas at mxc.ca, "LLVM Developers Mailing List" <llvmdev at cs.uiuc.edu>
> Sent: Saturday, February 1, 2014 6:33:26 AM
> Subject: [LLVMdev] [RFC] LCSSA vs. SSAUpdater ... FIGHT!
> 
> 
> 
> 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,

What is the benefit of merging them? LoopSimplify is certainly useful without LCSSA, and LCSSA is certainly useful without LoopSimplify's canonicalization. Also, and I don't know if this matters, but LoopSimplify can "fail" (for non-natural loops, at least), LCSSA cannot fail.

 -Hal

> 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
> _______________________________________________
> LLVM Developers mailing list
> LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
> 

-- 
Hal Finkel
Assistant Computational Scientist
Leadership Computing Facility
Argonne National Laboratory