[LCSSA] Simplify a loop. NFCI.

llvm-svn: 300433

[LCSSA] Fix non-determinism due to iterating over a SmallPtrSet.

Use a SmallSetVector instead.

llvm-svn: 300431

[LCSSA] Efficiently compute blocks dominating at least one exit.

For LCSSA purposes, loop BBs not dominating any of the exits aren't
interesting, as none of the values defined in these blocks can be

[LCSSA] Efficiently compute blocks dominating at least one exit.

For LCSSA purposes, loop BBs not dominating any of the exits aren't
interesting, as none of the values defined in these blocks can be
used outside the loop.

The way the code computed this information was by comparing each
BB of the loop with each of the exit blocks and ask the dominator tree
about their dominance relation. This is slow.

A more efficient way, implemented here, is that of starting from the
exit blocks and walking the dom upwards until we hit an header. By
transitivity, all the blocks we encounter in our path dominate an exit.

For the testcase provided in PR31851, this reduces compile time on
`opt -O2` by ~25%, going from 1m47s to 1m22s.

Thanks to Dan/MichaelZ for discussions/suggesting the approach/review.

Differential Revision: https://reviews.llvm.org/D31843

llvm-svn: 300255

show more ...

[LCSSA] Assert that we always have a valid loop.

We could otherwise add BBs not belonging to a loop in `formLCSSA`
and later crash when trying to iterate the loop blocks.

llvm-svn: 300244

[LCSSA] Remove spurious whitespaces. NFCI.

llvm-svn: 300243

[LCSSA] Use `auto` when the type is obvious. NFCI.

llvm-svn: 300242

[PM] Introduce an analysis set used to preserve all analyses over
a function's CFG when that CFG is unchanged.

This allows transformation passes to simply claim they preserve the CFG
and analysis pa

[PM] Introduce an analysis set used to preserve all analyses over
a function's CFG when that CFG is unchanged.

This allows transformation passes to simply claim they preserve the CFG
and analysis passes to check for the CFG being preserved to remove the
fanout of all analyses being listed in all passes.

I've gone through and removed or cleaned up as many of the comments
reminding us to do this as I could.

Differential Revision: https://reviews.llvm.org/D28627

llvm-svn: 292054

show more ...

[LCSSA] Perform LCSSA verification only for the current loop nest.

Now LPPassManager will run LCSSA verification only for the top-level loop
which was processed on the current iteration.

Differenti

[LCSSA] Perform LCSSA verification only for the current loop nest.

Now LPPassManager will run LCSSA verification only for the top-level loop
which was processed on the current iteration.

Differential Revision: https://reviews.llvm.org/D25873

llvm-svn: 285394

show more ...

[LCSSA] Implement linear algorithm for the isRecursivelyLCSSAForm

For each block check that it doesn't have any uses outside of it's innermost loop.

Differential Revision: https://reviews.llvm.org/

[LCSSA] Implement linear algorithm for the isRecursivelyLCSSAForm

For each block check that it doesn't have any uses outside of it's innermost loop.

Differential Revision: https://reviews.llvm.org/D25364

llvm-svn: 283877

show more ...

[LCSSA] Cache LoopExits to avoid wasted work

When looking at the scribus_1.3 example from https://llvm.org/bugs/show_bug.cgi?id=10584, I noticed that we were spending a large amount of time computin

[LCSSA] Cache LoopExits to avoid wasted work

When looking at the scribus_1.3 example from https://llvm.org/bugs/show_bug.cgi?id=10584, I noticed that we were spending a large amount of time computing loop exits in LCSSA. This code appears to be written with the assumption that LoopExits are stored in the Loop and thus cheap to query. This is not true, so we should cache the result across the potentially long running loop which tends to visit a small handful of Loops.

On the particular example from 10584, this change drops the time spent in LCSSA computation by about 80%.

Differential Revision: https://reviews.llvm.org/D24509

llvm-svn: 281949

show more ...

Use the range variant of find instead of unpacking begin/end

If the result of the find is only used to compare against end(), just
use is_contained instead.

No functionality change is intended.

ll

Use the range variant of find instead of unpacking begin/end

If the result of the find is only used to compare against end(), just
use is_contained instead.

No functionality change is intended.

llvm-svn: 278433

show more ...

Use range algorithms instead of unpacking begin/end

No functionality change is intended.

llvm-svn: 278417

Fix LCSSA increased compile time

We are seeing r276077 drastically increasing compiler time for our larger
benchmarks in PGO profile generation build (both clang based and IR based
mode) -- it can b

Fix LCSSA increased compile time

We are seeing r276077 drastically increasing compiler time for our larger
benchmarks in PGO profile generation build (both clang based and IR based
mode) -- it can be 20x slower than without the patch (like from 30 secs to
780 secs)

The increased time are all in pass LCSSA. The problematic code is about
PostProcessPHIs after use-rewrite. Note that the InsertedPhis from ssa_updater
is accumulating (never been cleared). Since the inserted PHIs are added to the
candidate for each rewrite, The earlier ones will be repeatedly added. Later
when adding the new PHIs to the work-list, we don't check the duplication
either. This can result in extremely long work-list that containing tons of
duplicated PHIs.

This patch fixes the issue by hoisting the code out of the loop.

Differential Revision: http://reviews.llvm.org/D23344

llvm-svn: 278250

show more ...

Consistently use FunctionAnalysisManager

Besides a general consistently benefit, the extra layer of indirection
allows the mechanical part of https://reviews.llvm.org/D23256 that
requires touching e

Consistently use FunctionAnalysisManager

Besides a general consistently benefit, the extra layer of indirection
allows the mechanical part of https://reviews.llvm.org/D23256 that
requires touching every transformation and analysis to be factored out
cleanly.

Thanks to David for the suggestion.

llvm-svn: 278077

show more ...

Add verifyAnalysis for LCSSA.

Summary:
LCSSAWrapperPass currently doesn't override verifyAnalysis method, so pass
manager doesn't verify LCSSA. This patch adds the method so that we start
verifying

Add verifyAnalysis for LCSSA.

Summary:
LCSSAWrapperPass currently doesn't override verifyAnalysis method, so pass
manager doesn't verify LCSSA. This patch adds the method so that we start
verifying LCSSA between loop passes.

Reviewers: chandlerc, sanjoy, hfinkel

Subscribers: llvm-commits

Differential Revision: https://reviews.llvm.org/D22888

llvm-svn: 276941

show more ...

Revert "Revert r275883 and r275891. They seem to cause PR28608."

This reverts commit r276064, and thus reapplies r275891 and r275883 with
a fix for PR28608.

llvm-svn: 276077

Revert r275883 and r275891. They seem to cause PR28608.

Revert "[LoopSimplify] Update LCSSA after separating nested loops."

This reverts commit r275891.

Revert "[LCSSA] Post-process PHI-nodes crea

Revert r275883 and r275891. They seem to cause PR28608.

Revert "[LoopSimplify] Update LCSSA after separating nested loops."

This reverts commit r275891.

Revert "[LCSSA] Post-process PHI-nodes created by SSAUpdate when constructing LCSSA form."

This reverts commit r275883.

llvm-svn: 276064

show more ...

[LCSSA] Post-process PHI-nodes created by SSAUpdate when constructing LCSSA form.

Summary:
SSAUpdate might insert PHI-nodes inside loops, which can break LCSSA
form unless we fix it up.

This fixes

[LCSSA] Post-process PHI-nodes created by SSAUpdate when constructing LCSSA form.

Summary:
SSAUpdate might insert PHI-nodes inside loops, which can break LCSSA
form unless we fix it up.

This fixes PR28424.

Reviewers: sanjoy, chandlerc, hfinkel

Subscribers: uabelho, llvm-commits

Differential Revision: http://reviews.llvm.org/D21997

llvm-svn: 275883

show more ...

Make processInstruction from LCSSA.cpp externally available.

Summary:
When a pass tries to keep LCSSA form it's often convenient to be able to update
LCSSA for a set of instructions rather than for

Make processInstruction from LCSSA.cpp externally available.

Summary:
When a pass tries to keep LCSSA form it's often convenient to be able to update
LCSSA for a set of instructions rather than for the entire loop. This patch makes the
processInstruction from LCSSA externally available under a name
formLCSSAForInstruction.

Reviewers: chandlerc, sanjoy, hfinkel

Subscribers: llvm-commits

Differential Revision: https://reviews.llvm.org/D22378

llvm-svn: 275613

show more ...

[PM] Normalize FIXMEs for missing PreserveCFG to have the same wording.

llvm-svn: 273974

[PM] Port LCSSA to the new PM.

Differential Revision: http://reviews.llvm.org/D21090

llvm-svn: 272294

[LCSSA] Simplify. Suggested by Sanjoy.

llvm-svn: 271041

[LCSSA] Use llvm::any_of instead of std::size_of.

The API is simpler. Suggested by David Blaikie!

llvm-svn: 269800

[PM/LCSSA] Fix dependency list. Some passes are preserved, not required.

llvm-svn: 269768

[LCSSA] Use any_of() to simplify the code. NFCI.

llvm-svn: 269767