LCSSA recomputed too many times

[llvmbot]

Bugzilla Link	2377
Resolution	FIXED
Resolved on	Feb 11, 2014 19:10
Version	trunk
OS	All
Reporter	LLVM Bugzilla Contributor
CC	@chandlerc,@sunfishcode

Extended Description

Because ScalarEvolution is a FunctionPass, it kills the LoopPassManager when it is run. This creates overhead because it require the re-instantiation of the LPM, as well as forcing LCSSA to be recomputed repeatedly. As of right now, we compute LCSSA no less than five times in -std-compile-opts, mostly because of this. If SCEV were a loop pass, this could probably be reduced to one or two.

[sunfishcode]

ScalarEvolution does use AU.setPreservesAll(), so there's no fundamental
reason why LCSSA would need to be recomputed. Would it be difficult to
improve the pass manager logic to handle this? That would seem to
have advantages in other areas as well (AliasAnalysis passes come to
mind).

[llvmbot]

The issue, as Devang explained it to me, is due to the fact that the LoopPassManager runs things one loop at a time. It only guarantees that a loop is in LCSSA form at the time that the LPM processes that loop. So some inner loop could be in LCSSA form at the time it is processed, and then be taken out by transformations applied to some outer loop, resulting in it not being in LCSSA form at the time that the LPM ends.

[lattner]

This sounds like a passmgr bug. If you have:

LoopPassA
LoopPassB

and both depend on and preserve SCEV, SCEV should be scheduled as a functionpass before either:

SCEV
LoopPassA
LoopPassB

-Chris

[llvmbot]

The loop pass manager is, for reasons I don't completely understand, being torn down. After instantiating a new one, it doesn't know that LCSSA was preserved at the end of the old one, so it recomputes it.

[llvmbot]

LoopUnswitch and LICM are not explicitly saying that they preserve SCEV. This inserts SCEV in the sequence of loop passes when a loop pass requires SCEV. Since SCEV is a function pass, all loop level info is lost between two Loop Pass Managers.

Owen, see if updating LoopUnswitch and LICM to preserve SCEV helps or not.

[lattner]

We have two runs of lcssa in the loop-pass-mgr-before-instcombine:

   Loop Pass Manager
     Canonicalize natural loops
     Loop-Closed SSA Form Pass
     Rotate Loops
     Loop Invariant Code Motion
     Loop-Closed SSA Form Pass
     Unswitch loops

Do you know why?

[sunfishcode]

Do you know why?

LICM doesn't preserve LCSSA.

[chandlerc]

This was fixed by my recent work to restructure the loop optimizations in LLVM.

Now, both LoopSimplify and LCSSA are function passes that arrange all of the loop nests in their "canonical" form. SCEV as an analysis doesn't disrupt this and the loop pass manager doesn't have to be re-built which needlessly re-ran these passes.

Also, LICM now preserves LCSSA which further reduces the re-runs.

Currently, we compute LCSSA only 3 times, twice in the CGSCC pipeline, and once afterward for vectorization. This is minimal until we have a loop-instcombine pass and thus only a single loop pass pipeline in the CGSCC pipeline.

There are still problems where LICM reforms LCSSA too often after mutating the function body, but that should be tracked separately. There is nothing else to do here w.r.t. the pass manager.