Require Dominator Tree For SROA, improve compile-time
authorMehdi Amini <mehdi.amini@apple.com>
Sun, 23 Aug 2015 22:15:49 +0000 (22:15 +0000)
committerMehdi Amini <mehdi.amini@apple.com>
Sun, 23 Aug 2015 22:15:49 +0000 (22:15 +0000)
TL-DR: SROA is followed by EarlyCSE which requires the DominatorTree.
There is no reason not to require it up-front for SROA.

Some history is necessary to understand why we ended-up here.

r123437 switched the second (Legacy)SROA in the optimizer pipeline to
use SSAUpdater in order to avoid recomputing the costly
DominanceFrontier. The purpose was to speed-up the compile-time.

Later r123609 removed the need for the DominanceFrontier in
(Legacy)SROA.

Right after, some cleanup was made in r123724 to remove any reference
to the DominanceFrontier. SROA existed in two flavors: SROA_SSAUp and
SROA_DT (the latter replacing SROA_DF).
The second argument of `createScalarReplAggregatesPass` was renamed
from `UseDomFrontier` to `UseDomTree`.
I believe this is were a mistake was made. The pipeline was not
updated and the call site was still:
    PM->add(createScalarReplAggregatesPass(-1, false));

At that time, SROA was immediately followed in the pipeline by
EarlyCSE which required alread the DominatorTree. Not requiring
the DominatorTree in SROA didn't save anything, but unfortunately
it was lost at this point.

When the new SROA Pass was introduced in r163965, I believe the goal
was to have an exact replacement of the existing SROA, this bug
slipped through.

You can see currently:

$ echo "" | clang -x c++  -O3 -c - -mllvm -debug-pass=Structure
...
...
      FunctionPass Manager
        SROA
        Dominator Tree Construction
        Early CSE

After this patch:

$ echo "" | clang -x c++  -O3 -c - -mllvm -debug-pass=Structure
...
...
      FunctionPass Manager
        Dominator Tree Construction
        SROA
        Early CSE

This improves the compile time from 88s to 23s for PR17855.
https://llvm.org/bugs/show_bug.cgi?id=17855

And from 113s to 12s for PR16756
https://llvm.org/bugs/show_bug.cgi?id=16756

Reviewers: chandlerc

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

From: Mehdi Amini <mehdi.amini@apple.com>

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@245820 91177308-0d34-0410-b5e6-96231b3b80d8

lib/Transforms/IPO/PassManagerBuilder.cpp

index edf3baf..936ca13 100644 (file)
@@ -244,7 +244,7 @@ void PassManagerBuilder::populateModulePassManager(
   // Start of function pass.
   // Break up aggregate allocas, using SSAUpdater.
   if (UseNewSROA)
   // Start of function pass.
   // Break up aggregate allocas, using SSAUpdater.
   if (UseNewSROA)
-    MPM.add(createSROAPass(/*RequiresDomTree*/ false));
+    MPM.add(createSROAPass());
   else
     MPM.add(createScalarReplAggregatesPass(-1, false));
   MPM.add(createEarlyCSEPass());              // Catch trivial redundancies
   else
     MPM.add(createScalarReplAggregatesPass(-1, false));
   MPM.add(createEarlyCSEPass());              // Catch trivial redundancies