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

[Andrew Trick]

> On Feb 1, 2014, at 10:51 PM, Hal Finkel <hfinkel at anl.gov> wrote:
> 
> ----- 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.

Right. One of my issues with LCSSA is that it has to be completely maintained for correctness.

OTOH. It is not hard to compute LCSSA correctly and problems will probably be caught by verification. I have seen bugs in SCEV caused by LCSSA update. But not bugs in LCSSA itself  (probably because it is recomputed from scratch)

I'll respond to the other points later. 

Andy

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