Require Dominator Tree For SROA, improve compile-time

[mehdi_amini]

Summary

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

[mzolotukhin]

Hi Mehdi,

Could you please explain why does it save compile time in the end? Why does SROA work slower when DT isn’t available? While your logic to construct DT before SROA seems legit, could that be that there is another bug in SROA itself (and we’re just papering it over now)?

Thanks,
Michael

[mehdi_amini]

As discussed on IRC: apparently it is a known limitation of SSAUpdater. It tries to compute dominance on the fly and does not cope well with large CFGs.
That said I'm looking independently if something trivial can be done there.

After this patch SROA will never be used with SSAUpdater in the current pipeline, but it is used by other places so we might encounter the same kind of issue with it in the future.

Chandler might comment here if it makes sense to keep the option to run SROA without the DominatorTree?

[• dberlin]

Ssaupdater is not a linear time algorithm, there one using domtree is

[chandlerc]

I've been wanting to kill the SSAUpdater path in SROA since i started rewriting it. I could swear that when I was rewriting it, adding it here forced a second run of DomTree.... But your analysis is clearly correct, and we no longer need this. I'll proceed with ripping out all the complexity SSAUpdater imposes later. There are still more compile time wins when we *know* that we have domtree here.

[mehdi_amini]

r245820

lib/Transforms/IPO/PassManagerBuilder.cpp

void PassManagerBuilder::populateModulePassManager(
   if (!DisableUnitAtATime)
     MPM.add(createFunctionAttrsPass());       // Set readonly/readnone attrs
   if (OptLevel > 2)
     MPM.add(createArgumentPromotionPass());   // Scalarize uninlined fn args
 
   // 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
   MPM.add(createJumpThreadingPass());         // Thread jumps.
   MPM.add(createCorrelatedValuePropagationPass()); // Propagate conditionals
   MPM.add(createCFGSimplificationPass());     // Merge & remove BBs
   MPM.add(createInstructionCombiningPass());  // Combine silly seq's
   addExtensionsToPM(EP_Peephole, MPM);