[LoopFlatten] Run it earlier, just before IndVarSimplify

[SjoerdMeijer]

Summary

This is a prep step for widening induction variables of a nested loop in LoopFlatten if this is posssible, to avoid having to perform certain overflow checks. Since IndVarSimplify may already widen induction variables, we want to run LoopFlatten just before IndVarSimplify. This is a minor reshuffle as both passes were already close after each other.

This is separated out from D88880, which is about making LoopFlatten triggeron 64-bit targets too and is the motivation of this work.

PS. No pipeline pass manager test were changed, because LoopFlatten isn't enabled by default yet.

[dmgreen]

Quick question on loop flattening preserving analyses. As far as I understand loop passes are required to preserve a number of analyses across all loops. Although I'm not sure if that is new or old pass managers. It's because function level analyses can't easily be rerun inside loop passes.

Would that be true for loop flattening? If we did enable this, would the pass pipeline still look OK?

[SjoerdMeijer]

In D90402#2367865, @dmgreen wrote:

Quick question on loop flattening preserving analyses. As far as I understand loop passes are required to preserve a number of analyses across all loops. Although I'm not sure if that is new or old pass managers. It's because function level analyses can't easily be rerun inside loop passes.

Would that be true for loop flattening? If we did enable this, would the pass pipeline still look OK?

From a look at the relevant parts in LoopFlatten, I think it's the NPM that deals with the preserved analysis business:

https://github.com/llvm/llvm-project/blob/b51b424c679f57dd65d83652f3e62ac2cf6de738/llvm/lib/Transforms/Scalar/LoopFlatten.cpp#L550

And what I really hope is that a Loop pass is allowed to modify a loop, and that the pass managers is providing the framework to rerun loop analysis if loop flatten returns getLoopPassPreservedAnalyses() and a next pass depends on loop info.

But fair enough, that's a bit of speculation as I never had to look into this. Since the NPM seems to deal with this, I am further guessing it might be the LPM. However, since this is a minor reshuffle, any problem that we had before, is one we will currently have....and since I haven't seen problems, I am guessing (again) it is alright, but could look into this....

[SjoerdMeijer]

I have found this so far:

A LoopPass subclass which is intended to run as part of the main loop pass pipeline needs to preserve all of the same function analyses that the other loop passes in its pipeline require.

which mentions function analysis, so looks okay to me.

[dmgreen]

OK yeah, they look like they are already in different loop managers on the old pass manager side.

llvm/lib/Passes/PassBuilder.cpp

540

I think this one would be better put into a new LoopPassManager, LPM3, if flattening is enabled. I think that's how it's meant to work.

[SjoerdMeijer]

llvm/lib/Passes/PassBuilder.cpp

540

Cheers Dave. Like we discussed, I will convert LoopFlatten first to a Function pass as a loop pass that's deleting loops might be a bit tricky; looks like that is just the easiest to deal with this. Then, I will return to this change.

[SjoerdMeijer]

Rebased on top of D90940, which converts this into a function pass.

[dmgreen]

LGTM

llvm/lib/Passes/PassBuilder.cpp

PassBuilder::buildO1FunctionSimplificationPipeline(OptimizationLevel Level,
   // implications on the outer loop.
   LPM1.addPass(LoopInstSimplifyPass());
   LPM1.addPass(LoopSimplifyCFGPass());
 
   LPM1.addPass(LoopRotatePass(/* Disable header duplication */ true));
   // TODO: Investigate promotion cap for O1.
   LPM1.addPass(LICMPass(PTO.LicmMssaOptCap, PTO.LicmMssaNoAccForPromotionCap));
   LPM1.addPass(SimpleLoopUnswitchPass());
+
+  if (EnableLoopFlatten)
+    FPM.addPass(LoopFlattenPass());
   LPM2.addPass(IndVarSimplifyPass());
   LPM2.addPass(LoopIdiomRecognizePass());
 
   for (auto &C : LateLoopOptimizationsEPCallbacks)
     C(LPM2, Level);
 
   LPM2.addPass(LoopDeletionPass());
-  if (EnableLoopFlatten)
-    FPM.addPass(LoopFlattenPass());
   // Do not enable unrolling in PreLinkThinLTO phase during sample PGO
   // because it changes IR to makes profile annotation in back compile
   // inaccurate. The normal unroller doesn't pay attention to forced full unroll
   // attributes so we need to make sure and allow the full unroll pass to pay
   // attention to it.
   if (Phase != ThinLTOPhase::PreLink || !PGOOpt ||
       PGOOpt->Action != PGOOptions::SampleUse)
     LPM2.addPass(LoopFullUnrollPass(Level.getSpeedupLevel(),

llvm/lib/Transforms/IPO/PassManagerBuilder.cpp

void PassManagerBuilder::addFunctionSimplificationPasses(
   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
   // need for this.
   MPM.add(createCFGSimplificationPass());
   MPM.add(createInstructionCombiningPass());
   // We resume loop passes creating a second loop pipeline here.
+  if (EnableLoopFlatten) {
+    MPM.add(createLoopFlattenPass()); // Flatten loops
+    MPM.add(createLoopSimplifyCFGPass());
+  }
   MPM.add(createIndVarSimplifyPass());        // Canonicalize indvars
   MPM.add(createLoopIdiomPass());             // Recognize idioms like memset.
   addExtensionsToPM(EP_LateLoopOptimizations, MPM);
   MPM.add(createLoopDeletionPass());          // Delete dead loops
 
   if (EnableLoopInterchange)
     MPM.add(createLoopInterchangePass()); // Interchange loops
-  if (EnableLoopFlatten) {
-    MPM.add(createLoopFlattenPass()); // Flatten loops
-    MPM.add(createLoopSimplifyCFGPass());
-  }
 
   // Unroll small loops
   MPM.add(createSimpleLoopUnrollPass(OptLevel, DisableUnrollLoops,
                                      ForgetAllSCEVInLoopUnroll));
   addExtensionsToPM(EP_LoopOptimizerEnd, MPM);
   // This ends the loop pass pipelines.
 
   // Break up allocas that may now be splittable after loop unrolling.
PM.add(NewGVN ? createNewGVNPass()
                 : createGVNPass(DisableGVNLoadPRE)); // Remove redundancies.
   PM.add(createMemCpyOptPass());            // Remove dead memcpys.
 
   // Nuke dead stores.
   PM.add(createDeadStoreEliminationPass());
   PM.add(createMergedLoadStoreMotionPass()); // Merge ld/st in diamonds.
 
   // More loops are countable; try to optimize them.
+  if (EnableLoopFlatten)
+    PM.add(createLoopFlattenPass());
   PM.add(createIndVarSimplifyPass());
   PM.add(createLoopDeletionPass());
   if (EnableLoopInterchange)
     PM.add(createLoopInterchangePass());
-  if (EnableLoopFlatten)
-    PM.add(createLoopFlattenPass());
 
   // Unroll small loops
   PM.add(createSimpleLoopUnrollPass(OptLevel, DisableUnrollLoops,
                                     ForgetAllSCEVInLoopUnroll));
   PM.add(createLoopDistributePass());
   PM.add(createLoopVectorizePass(true, !LoopVectorize));
   // The vectorizer may have significantly shortened a loop body; unroll again.
   PM.add(createLoopUnrollPass(OptLevel, DisableUnrollLoops,