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

[Chandler Carruth]

On Mon, Feb 3, 2014 at 10:42 AM, Andrew Trick <atrick at apple.com> wrote:

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

Just for clarification, LoopSimplify is not a loop pass, and just creates
the canonical loop nest structure with preheaders and exit blocks. LCSSA
requires this to have a place for its PHI nodes, not the other way around.

Also, full unrolling already runs as part of the early rounds of the IR
loop optimizations just as you say it should.

Why did I suggest avoiding LCSSA?
> (1) Unnecessary overhead.
> (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].
>

Do you have any measurement of this? I have no evidence that LCSSA is a
remotely significant optimization time cost, but I've not gone looking.


>
> (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, we never re-run domtree here. It is preserved throughout, and it is
required for LoopInfo, so there is nothing to be saved on that front.
AFAICT, there is no analysis dependency cost of LCSSA given the other loop
optimizer.

Also, LCSSA *doesn't* need to be re-run between passes. If a pass has LCSSA
coming into it, then it is extremely easy to preserve it in place rather
than re-running things. We just have a *lot* of bugs because the old
loop-pass-manager setup just blindly re-ran LCSSA for us, papering over all
manner of badness.


>
> (2) Phi nodes "in the way".
> (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.
>

Ok, I think this would be the more serious issue if it comes up in
practice. I don't have any cases where it comes up in practice for early
loop opts either though.


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

<snip>

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

LICM. There is already a fast path in LICM that is the exact path that
LCSSA guarantees exists when sinking code into the exit blocks. The only
thing missing is for LICM to actually *use* LCSSA instead of just trying to
patch it up if it happens to find it in the loop. I think it would
dramatically simplify the entire sinking code.

A good use of SSAUpdater: re-forming SSA values *within* a loop body due to
mem2reg essentially. LICM has a little mini mem2reg pass in it that uses
SSAUpdater. This is a great use and I can't imagine something simpler. The
fact that we have LCSSA also makes it faster by bounding the space where it
has to rewrite uses (to the edge of the current loop).

But if we have LCSSA, we should never need SSAUpdater for updating SSA form
across the loop boundary in the way LICM does. Instead we should be able to
place an instruction, RAUW it, and insert a PHI node for each operand. Done.

Maybe a patch would be better to explain matters? As it happens, fixing
LICM this way will also fix PR18753 and a host of other latent bugs where
LICM invalidates LCSSA in some far-off loop and we crash later.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20140207/f42d8586/attachment.html>