[LoopRotate] Add explicit flag to require MSSA.

[asbirlea]

Summary

Add an explicit flag to require MSSA when LoopRotate is known to join a
loop pass pipeline with other passes that will require the anlysis.
This undoes the pipeline split from D74574, but keep the analysis from
being run when LoopRotate is run alone in the loop pipeline.

[fhahn]

llvm/lib/Transforms/Scalar/LoopRotation.cpp

80

nit: initialise directly in the initialiser list?

88

Would it be slightly simpler to just have RequireMSSA == true mean that we require and preserve it and RequireMSSA == false means neither require nor preserve it? I think both approaches are fine, but in the current pipeline the case we can preserve MSSA without requiring it is not going to happen I guess?

[asbirlea]

This re-regresses PR44408 and PR44889 at ToT today.
I am planning to resolve the underlying cause (a new DT being built when doing MSSA updates) before coming back to this. The regression will not occur when that work is done (I have tested this already).

[asbirlea]

Rebase at ToT.

[asbirlea]

Rebased after the fix to remove DT recomputation in MSSA. I'm still seeing a small regression on one of the tests in the original PRs (0.6% in instructions on mogrify.i), but it's nowhere near the regression that motivated the pipeline split.
I'm not sure if it's worth pushing this forward if the only motivation is re-merging the pipeline in the LPM, unless it's entirely performance neutral.

@nikic: Would you mind checking the compile-time impact for this patch?

[nikic]

Compile-time: https://llvm-compile-time-tracker.com/compare.php?from=553833958fdea48e41a11ee7e9c104c903deadf5&to=cfbffacf4188264ec40c0fcb7dbd92d0e23b1b74&stat=instructions Numbers are mixed with some improvements, some regressions. Largest individual regression is on libclamav_unsp.c with 1.8% at O3 and 4.2% for ThinLTO (pre-link).

[asbirlea]

Thank you for the results! Looking at libclamav_unsp.c, I'm seeing 3.96% in instructions for ThinLTO, which I'm guessing matches the results you see.
The fluctuations may make sense, since with the additional MSSA updates in LoopRotate it can do more or less work, depending on the updates. For instructions per cycle I'm seeing it neutral results (0.5%), and for wall time (average over 20 run), also neutral.

Again, I'm not convinced this is worth pushing forward due to it only affecting the LPM, but since the change I'm undoing here was a previous large release regression in clang9, I'm glad to see the DomTree work payed off and this is now showing mixed results.
I'm fine with whichever decisions the reviewers lean towards.

[lebedev.ri]

Rebased
Fresh perf numbers:
https://llvm-compile-time-tracker.com/compare.php?from=760f4c2069d53ace13d20424b7209759a9186090&to=418931903396b23c29131ffd5fa6fd6b54698272&stat=instructions

[nikic]

I believe this can be abandoned now, it's no longer relevant now that LICM runs before LoopRotate, so MSSA is required at that point anyway.

llvm/include/llvm/Transforms/Scalar.h

 // LoopReroll - This pass is a simple loop rerolling pass.
 //
 Pass *createLoopRerollPass();
 
 //===----------------------------------------------------------------------===//
 //
 // LoopRotate - This pass is a simple loop rotating pass.
 //
-Pass *createLoopRotatePass(int MaxHeaderSize = -1);
+Pass *createLoopRotatePass(int MaxHeaderSize = -1, bool RequiresMSSA = false);
 
 //===----------------------------------------------------------------------===//
 //
 // LoopIdiom - This pass recognizes and replaces idioms in loops.
 //
 Pass *createLoopIdiomPass();
 
 //===----------------------------------------------------------------------===//

llvm/lib/Transforms/IPO/PassManagerBuilder.cpp

void PassManagerBuilder::addFunctionSimplificationPasses(
   if (EnableSimpleLoopUnswitch) {
     // The simple loop unswitch pass relies on separate cleanup passes. Schedule
     // them first so when we re-process a loop they run before other loop
     // passes.
     MPM.add(createLoopInstSimplifyPass());
     MPM.add(createLoopSimplifyCFGPass());
   }
   // Rotate Loop - disable header duplication at -Oz
-  MPM.add(createLoopRotatePass(SizeLevel == 2 ? 0 : -1));
+  MPM.add(createLoopRotatePass(SizeLevel == 2 ? 0 : -1, true));
   // TODO: Investigate promotion cap for O1.
   MPM.add(createLICMPass(LicmMssaOptCap, LicmMssaNoAccForPromotionCap));
   if (EnableSimpleLoopUnswitch)
     MPM.add(createSimpleLoopUnswitchLegacyPass());
   else
     MPM.add(createLoopUnswitchPass(SizeLevel || OptLevel < 3, DivergentTarget));
   // FIXME: We break the loop pass pipeline here in order to do full
   // simplify-cfg. Eventually loop-simplifycfg should be enhanced to replace the

llvm/lib/Transforms/Scalar/LoopRotation.cpp

if (AR.MSSA)
     PA.preserve<MemorySSAAnalysis>();
   return PA;
 }
 
 namespace {
 
 class LoopRotateLegacyPass : public LoopPass {
   unsigned MaxHeaderSize;
+  bool RequiresMSSA;
 
 public:
   static char ID; // Pass ID, replacement for typeid
-  LoopRotateLegacyPass(int SpecifiedMaxHeaderSize = -1) : LoopPass(ID) {
+  LoopRotateLegacyPass(int SpecifiedMaxHeaderSize = -1, bool ReqMSSA = false)
+      : LoopPass(ID) {
     initializeLoopRotateLegacyPassPass(*PassRegistry::getPassRegistry());
     if (SpecifiedMaxHeaderSize == -1)
       MaxHeaderSize = DefaultRotationThreshold;
     else
       MaxHeaderSize = unsigned(SpecifiedMaxHeaderSize);
+    RequiresMSSA = ReqMSSA;
   }
 
   // LCSSA form makes instruction renaming easier.
   void getAnalysisUsage(AnalysisUsage &AU) const override {
     AU.addRequired<AssumptionCacheTracker>();
     AU.addRequired<TargetTransformInfoWrapperPass>();
-    if (EnableMSSALoopDependency)
+    if (EnableMSSALoopDependency) {
+      if (RequiresMSSA)
+        AU.addRequired<MemorySSAWrapperPass>();
       AU.addPreserved<MemorySSAWrapperPass>();
+    }
     getLoopAnalysisUsage(AU);
   }
 
   bool runOnLoop(Loop *L, LPPassManager &LPM) override {
     if (skipLoop(L))
       return false;
     Function &F = *L->getHeader()->getParent();
 
     auto *LI = &getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
     const auto *TTI = &getAnalysis<TargetTransformInfoWrapperPass>().getTTI(F);
     auto *AC = &getAnalysis<AssumptionCacheTracker>().getAssumptionCache(F);
     auto &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree();
     auto &SE = getAnalysis<ScalarEvolutionWrapperPass>().getSE();
     const SimplifyQuery SQ = getBestSimplifyQuery(*this, F);
     Optional<MemorySSAUpdater> MSSAU;
     if (EnableMSSALoopDependency) {
-      // Not requiring MemorySSA and getting it only if available will split
-      // the loop pass pipeline when LoopRotate is being run first.
       auto *MSSAA = getAnalysisIfAvailable<MemorySSAWrapperPass>();
       if (MSSAA)
         MSSAU = MemorySSAUpdater(&MSSAA->getMSSA());
     }
     return LoopRotation(L, LI, TTI, AC, &DT, &SE,
                         MSSAU.hasValue() ? MSSAU.getPointer() : nullptr, SQ,
                         false, MaxHeaderSize, false);
   }
 };
 } // end namespace
 
 char LoopRotateLegacyPass::ID = 0;
 INITIALIZE_PASS_BEGIN(LoopRotateLegacyPass, "loop-rotate", "Rotate Loops",
                       false, false)
 INITIALIZE_PASS_DEPENDENCY(AssumptionCacheTracker)
 INITIALIZE_PASS_DEPENDENCY(LoopPass)
 INITIALIZE_PASS_DEPENDENCY(TargetTransformInfoWrapperPass)
 INITIALIZE_PASS_DEPENDENCY(MemorySSAWrapperPass)
 INITIALIZE_PASS_END(LoopRotateLegacyPass, "loop-rotate", "Rotate Loops", false,
                     false)
 
-Pass *llvm::createLoopRotatePass(int MaxHeaderSize) {
-  return new LoopRotateLegacyPass(MaxHeaderSize);
+Pass *llvm::createLoopRotatePass(int MaxHeaderSize, bool RequiresMSSA) {
+  return new LoopRotateLegacyPass(MaxHeaderSize, RequiresMSSA);
 }

llvm/test/CodeGen/AMDGPU/opt-pipeline.ll

 ; GCN-O1-NEXT:       Block Frequency Analysis
 ; GCN-O1-NEXT:       Lazy Branch Probability Analysis
 ; GCN-O1-NEXT:       Lazy Block Frequency Analysis
 ; GCN-O1-NEXT:       Optimization Remark Emitter
 ; GCN-O1-NEXT:       PGOMemOPSize
 ; GCN-O1-NEXT:       Simplify the CFG
 ; GCN-O1-NEXT:       Reassociate expressions
 ; GCN-O1-NEXT:       Dominator Tree Construction
+; GCN-O1-NEXT:       Basic Alias Analysis (stateless AA impl)
+; GCN-O1-NEXT:       Function Alias Analysis Results
+; GCN-O1-NEXT:       Memory SSA
 ; GCN-O1-NEXT:       Natural Loop Information
 ; GCN-O1-NEXT:       Canonicalize natural loops
 ; GCN-O1-NEXT:       LCSSA Verifier
 ; GCN-O1-NEXT:       Loop-Closed SSA Form Pass
-; GCN-O1-NEXT:       Basic Alias Analysis (stateless AA impl)
-; GCN-O1-NEXT:       Function Alias Analysis Results
 ; GCN-O1-NEXT:       Scalar Evolution Analysis
 ; GCN-O1-NEXT:       Loop Pass Manager
 ; GCN-O1-NEXT:         Rotate Loops
-; GCN-O1-NEXT:       Memory SSA
-; GCN-O1-NEXT:       Loop Pass Manager
 ; GCN-O1-NEXT:         Loop Invariant Code Motion
 ; GCN-O1-NEXT:       Post-Dominator Tree Construction
 ; GCN-O1-NEXT:       Legacy Divergence Analysis
 ; GCN-O1-NEXT:       Loop Pass Manager
 ; GCN-O1-NEXT:         Unswitch loops
 ; GCN-O1-NEXT:       Simplify the CFG
 ; GCN-O1-NEXT:       Dominator Tree Construction
 ; GCN-O1-NEXT:       Basic Alias Analysis (stateless AA impl)

 ; GCN-O2-NEXT:       Natural Loop Information
 ; GCN-O2-NEXT:       Lazy Branch Probability Analysis
 ; GCN-O2-NEXT:       Lazy Block Frequency Analysis
 ; GCN-O2-NEXT:       Optimization Remark Emitter
 ; GCN-O2-NEXT:       Tail Call Elimination
 ; GCN-O2-NEXT:       Simplify the CFG
 ; GCN-O2-NEXT:       Reassociate expressions
 ; GCN-O2-NEXT:       Dominator Tree Construction
+; GCN-O2-NEXT:       Basic Alias Analysis (stateless AA impl)
+; GCN-O2-NEXT:       Function Alias Analysis Results
+; GCN-O2-NEXT:       Memory SSA
 ; GCN-O2-NEXT:       Natural Loop Information
 ; GCN-O2-NEXT:       Canonicalize natural loops
 ; GCN-O2-NEXT:       LCSSA Verifier
 ; GCN-O2-NEXT:       Loop-Closed SSA Form Pass
-; GCN-O2-NEXT:       Basic Alias Analysis (stateless AA impl)
-; GCN-O2-NEXT:       Function Alias Analysis Results
 ; GCN-O2-NEXT:       Scalar Evolution Analysis
 ; GCN-O2-NEXT:       Loop Pass Manager
 ; GCN-O2-NEXT:         Rotate Loops
-; GCN-O2-NEXT:       Memory SSA
-; GCN-O2-NEXT:       Loop Pass Manager
 ; GCN-O2-NEXT:         Loop Invariant Code Motion
 ; GCN-O2-NEXT:       Post-Dominator Tree Construction
 ; GCN-O2-NEXT:       Legacy Divergence Analysis
 ; GCN-O2-NEXT:       Loop Pass Manager
 ; GCN-O2-NEXT:         Unswitch loops
 ; GCN-O2-NEXT:       Simplify the CFG
 ; GCN-O2-NEXT:       Dominator Tree Construction
 ; GCN-O2-NEXT:       Basic Alias Analysis (stateless AA impl)

 ; GCN-O3-NEXT:       Natural Loop Information
 ; GCN-O3-NEXT:       Lazy Branch Probability Analysis
 ; GCN-O3-NEXT:       Lazy Block Frequency Analysis
 ; GCN-O3-NEXT:       Optimization Remark Emitter
 ; GCN-O3-NEXT:       Tail Call Elimination
 ; GCN-O3-NEXT:       Simplify the CFG
 ; GCN-O3-NEXT:       Reassociate expressions
 ; GCN-O3-NEXT:       Dominator Tree Construction
+; GCN-O3-NEXT:       Basic Alias Analysis (stateless AA impl)
+; GCN-O3-NEXT:       Function Alias Analysis Results
+; GCN-O3-NEXT:       Memory SSA
 ; GCN-O3-NEXT:       Natural Loop Information
 ; GCN-O3-NEXT:       Canonicalize natural loops
 ; GCN-O3-NEXT:       LCSSA Verifier
 ; GCN-O3-NEXT:       Loop-Closed SSA Form Pass
-; GCN-O3-NEXT:       Basic Alias Analysis (stateless AA impl)
-; GCN-O3-NEXT:       Function Alias Analysis Results
 ; GCN-O3-NEXT:       Scalar Evolution Analysis
 ; GCN-O3-NEXT:       Loop Pass Manager
 ; GCN-O3-NEXT:         Rotate Loops
-; GCN-O3-NEXT:       Memory SSA
-; GCN-O3-NEXT:       Loop Pass Manager
 ; GCN-O3-NEXT:         Loop Invariant Code Motion
 ; GCN-O3-NEXT:       Post-Dominator Tree Construction
 ; GCN-O3-NEXT:       Legacy Divergence Analysis
 ; GCN-O3-NEXT:       Loop Pass Manager
 ; GCN-O3-NEXT:         Unswitch loops
 ; GCN-O3-NEXT:       Simplify the CFG
 ; GCN-O3-NEXT:       Dominator Tree Construction
 ; GCN-O3-NEXT:       Basic Alias Analysis (stateless AA impl)

llvm/test/Other/opt-O2-pipeline.ll

 ; CHECK-NEXT:         Natural Loop Information
 ; CHECK-NEXT:         Lazy Branch Probability Analysis
 ; CHECK-NEXT:         Lazy Block Frequency Analysis
 ; CHECK-NEXT:         Optimization Remark Emitter
 ; CHECK-NEXT:         Tail Call Elimination
 ; CHECK-NEXT:         Simplify the CFG
 ; CHECK-NEXT:         Reassociate expressions
 ; CHECK-NEXT:         Dominator Tree Construction
+; CHECK-NEXT:         Basic Alias Analysis (stateless AA impl)
+; CHECK-NEXT:         Function Alias Analysis Results
+; CHECK-NEXT:         Memory SSA
 ; CHECK-NEXT:         Natural Loop Information
 ; CHECK-NEXT:         Canonicalize natural loops
 ; CHECK-NEXT:         LCSSA Verifier
 ; CHECK-NEXT:         Loop-Closed SSA Form Pass
-; CHECK-NEXT:         Basic Alias Analysis (stateless AA impl)
-; CHECK-NEXT:         Function Alias Analysis Results
 ; CHECK-NEXT:         Scalar Evolution Analysis
 ; CHECK-NEXT:         Loop Pass Manager
 ; CHECK-NEXT:           Rotate Loops
-; CHECK-NEXT:         Memory SSA
-; CHECK-NEXT:         Loop Pass Manager
 ; CHECK-NEXT:           Loop Invariant Code Motion
 ; CHECK-NEXT:           Unswitch loops
 ; CHECK-NEXT:         Simplify the CFG
 ; CHECK-NEXT:         Dominator Tree Construction
 ; CHECK-NEXT:         Basic Alias Analysis (stateless AA impl)
 ; CHECK-NEXT:         Function Alias Analysis Results
 ; CHECK-NEXT:         Natural Loop Information
 ; CHECK-NEXT:         Lazy Branch Probability Analysis

llvm/test/Other/opt-O3-pipeline-enable-matrix.ll

 ; CHECK-NEXT:         Natural Loop Information
 ; CHECK-NEXT:         Lazy Branch Probability Analysis
 ; CHECK-NEXT:         Lazy Block Frequency Analysis
 ; CHECK-NEXT:         Optimization Remark Emitter
 ; CHECK-NEXT:         Tail Call Elimination
 ; CHECK-NEXT:         Simplify the CFG
 ; CHECK-NEXT:         Reassociate expressions
 ; CHECK-NEXT:         Dominator Tree Construction
+; CHECK-NEXT:         Basic Alias Analysis (stateless AA impl)
+; CHECK-NEXT:         Function Alias Analysis Results
+; CHECK-NEXT:         Memory SSA
 ; CHECK-NEXT:         Natural Loop Information
 ; CHECK-NEXT:         Canonicalize natural loops
 ; CHECK-NEXT:         LCSSA Verifier
 ; CHECK-NEXT:         Loop-Closed SSA Form Pass
-; CHECK-NEXT:         Basic Alias Analysis (stateless AA impl)
-; CHECK-NEXT:         Function Alias Analysis Results
 ; CHECK-NEXT:         Scalar Evolution Analysis
 ; CHECK-NEXT:         Loop Pass Manager
 ; CHECK-NEXT:           Rotate Loops
-; CHECK-NEXT:         Memory SSA
-; CHECK-NEXT:         Loop Pass Manager
 ; CHECK-NEXT:           Loop Invariant Code Motion
 ; CHECK-NEXT:           Unswitch loops
 ; CHECK-NEXT:         Simplify the CFG
 ; CHECK-NEXT:         Dominator Tree Construction
 ; CHECK-NEXT:         Basic Alias Analysis (stateless AA impl)
 ; CHECK-NEXT:         Function Alias Analysis Results
 ; CHECK-NEXT:         Natural Loop Information
 ; CHECK-NEXT:         Lazy Branch Probability Analysis

llvm/test/Other/opt-O3-pipeline.ll

 ; CHECK-NEXT:         Natural Loop Information
 ; CHECK-NEXT:         Lazy Branch Probability Analysis
 ; CHECK-NEXT:         Lazy Block Frequency Analysis
 ; CHECK-NEXT:         Optimization Remark Emitter
 ; CHECK-NEXT:         Tail Call Elimination
 ; CHECK-NEXT:         Simplify the CFG
 ; CHECK-NEXT:         Reassociate expressions
 ; CHECK-NEXT:         Dominator Tree Construction
+; CHECK-NEXT:         Basic Alias Analysis (stateless AA impl)
+; CHECK-NEXT:         Function Alias Analysis Results
+; CHECK-NEXT:         Memory SSA
 ; CHECK-NEXT:         Natural Loop Information
 ; CHECK-NEXT:         Canonicalize natural loops
 ; CHECK-NEXT:         LCSSA Verifier
 ; CHECK-NEXT:         Loop-Closed SSA Form Pass
-; CHECK-NEXT:         Basic Alias Analysis (stateless AA impl)
-; CHECK-NEXT:         Function Alias Analysis Results
 ; CHECK-NEXT:         Scalar Evolution Analysis
 ; CHECK-NEXT:         Loop Pass Manager
 ; CHECK-NEXT:           Rotate Loops
-; CHECK-NEXT:         Memory SSA
-; CHECK-NEXT:         Loop Pass Manager
 ; CHECK-NEXT:           Loop Invariant Code Motion
 ; CHECK-NEXT:           Unswitch loops
 ; CHECK-NEXT:         Simplify the CFG
 ; CHECK-NEXT:         Dominator Tree Construction
 ; CHECK-NEXT:         Basic Alias Analysis (stateless AA impl)
 ; CHECK-NEXT:         Function Alias Analysis Results
 ; CHECK-NEXT:         Natural Loop Information
 ; CHECK-NEXT:         Lazy Branch Probability Analysis

llvm/test/Other/opt-Os-pipeline.ll

 ; CHECK-NEXT:         Lazy Block Frequency Analysis
 ; CHECK-NEXT:         Optimization Remark Emitter
 ; CHECK-NEXT:         Combine redundant instructions
 ; CHECK-NEXT:         Optimization Remark Emitter
 ; CHECK-NEXT:         Tail Call Elimination
 ; CHECK-NEXT:         Simplify the CFG
 ; CHECK-NEXT:         Reassociate expressions
 ; CHECK-NEXT:         Dominator Tree Construction
+; CHECK-NEXT:         Basic Alias Analysis (stateless AA impl)
+; CHECK-NEXT:         Function Alias Analysis Results
+; CHECK-NEXT:         Memory SSA
 ; CHECK-NEXT:         Natural Loop Information
 ; CHECK-NEXT:         Canonicalize natural loops
 ; CHECK-NEXT:         LCSSA Verifier
 ; CHECK-NEXT:         Loop-Closed SSA Form Pass
-; CHECK-NEXT:         Basic Alias Analysis (stateless AA impl)
-; CHECK-NEXT:         Function Alias Analysis Results
 ; CHECK-NEXT:         Scalar Evolution Analysis
 ; CHECK-NEXT:         Loop Pass Manager
 ; CHECK-NEXT:           Rotate Loops
-; CHECK-NEXT:         Memory SSA
-; CHECK-NEXT:         Loop Pass Manager
 ; CHECK-NEXT:           Loop Invariant Code Motion
 ; CHECK-NEXT:           Unswitch loops
 ; CHECK-NEXT:         Simplify the CFG
 ; CHECK-NEXT:         Dominator Tree Construction
 ; CHECK-NEXT:         Basic Alias Analysis (stateless AA impl)
 ; CHECK-NEXT:         Function Alias Analysis Results
 ; CHECK-NEXT:         Natural Loop Information
 ; CHECK-NEXT:         Lazy Branch Probability Analysis

llvm/test/Other/pass-pipelines.ll

 ; CHECK-O2-NEXT: Function Integration/Inlining
 ; CHECK-O2-NEXT: OpenMP specific optimizations
 ; CHECK-O2-NEXT: Deduce function attributes
 ; Next up is the main function pass pipeline. It shouldn't be split up and
 ; should contain the main loop pass pipeline as well.
 ; CHECK-O2-NEXT: FunctionPass Manager
 ; CHECK-O2-NOT: Manager
 ; CHECK-O2: Loop Pass Manager
-; CHECK-O2: Loop Pass Manager
 ; CHECK-O2-NOT: Manager
 ; FIXME: We shouldn't be pulling out to simplify-cfg and instcombine and
 ; causing new loop pass managers.
 ; CHECK-O2: Simplify the CFG
 ; CHECK-O2-NOT: Manager
 ; CHECK-O2: Combine redundant instructions
 ; CHECK-O2-NOT: Manager
 ; CHECK-O2: Loop Pass Manager