[LoopNest][LoopFlatten] Change LoopFlattenPass to LoopNest pass

[eopXD]

Summary

This patch changes LoopFlattenPass from FunctionPass to LoopNestPass.

Utilize LoopNest and let function 'Flatten' generate information from it.

[eopXD]

Apply clang-format.

[eopXD]

Utilize LoopNest in Flatten, this shall eliminate repeating calls to FlattenLoopPair

[eopXD]

Apply clang-tidy.

[eopXD]

Reset update on files.

[Whitney]

llvm/lib/Transforms/Scalar/LoopFlatten.cpp

70

Please avoid unnecessary changes.

723

We can keep the LPM manager as FunctionPass, as after this change, a loop nest can be transform repeatedly the number of loops time.

[eopXD]

address comments.

[Whitney]

llvm/lib/Passes/PassRegistry.def

424

Please undo this no newline change.

llvm/lib/Transforms/Scalar/LoopFlatten.cpp

91

Please avoid unnecessary changes.
Same goes to other changes.

[eopXD]

revert the changes caused by clang-format.

[eopXD]

more recoveries from clang-format.

[eopXD]

Added new lines at end of file,
also removed the redundant header I added.

[dmgreen]

D99149 ended up needing to use the LPMUpdater as the loops may be removed. Does the same thing need to be done here? As loop flattening does inherently remove loops.

[eopXD]

D99149 ended up needing to use the LPMUpdater as the loops may be removed. Does the same thing need to be done here? As loop flattening does inherently remove loops.

Loop flattening aims to remove the inner loop of a nested loop,
but under LoopNestMode there is an assertion in LPMUpdater::markLoopAsDeleted that checks if the deleting loop the outer-most loop.
I think the assertion should not hold, the function shall allow markLoopAsDeleted for sub-loop in LoopNestMode,
and check that whether the mark-deleted-loop is a sub-loop, then call revisitCurrentLoop if so.

Thank you for spotting out the problem.

[eopXD]

added LPMUpdater for loop removal,
updated LPMUpdater::markLoopAsDeleted, allow sub-loop to be deleted in LoopNestMode.

[Whitney]

llvm/include/llvm/Transforms/Scalar/LoopPassManager.h

262 ↗

(On Diff #347340)

Can you please explain why should revisitCurrentLoop?

llvm/lib/Transforms/Scalar/LoopFlatten.cpp

726

There can be more than one loop nest in a function. You may need a loop like for (auto *InnerLoop : LI->getLoopsInPreorder()) { here.

[eopXD]

@Whitney : Can you please explain why should revisitCurrentLoop?

I think I have misused revisitCurrentLoop here, the loop don't need to be revisited again,
because Flatten will be called for go through the possible inner/outer loop pairs.

@dmgreen
In LoopNestMode, sub-loops are not in the work list of LPMUpdater, so inner-loops can't be marked by deleted.
I think wrong for removing the assertion, since LAM.clear(L, Name); won't find the sub-loop, and markLoopAsDelete shall not be called for the inner-loop.
May you correct me if I am wrong.

[eopXD]

1. revert change for LPMUpdater::markLoopAsDeleted, remove the call also.
2. iterate through Loops and record top-level loops for legacy LoopFlattenPass, a seperate for-loop is called because LoopFlatten may affect the range.

[eopXD]

remove redundant LPMUpdater parameter.

[dmgreen]

OK. So because we only delete the inner loop, not the current one, the loop nest pass remains valid? That sounds Ok then.

I think the changes from UnrollAndJam were found with a sanitizer build, so it might be worth testing it with one of those (or letting the buildbots do it post-commit, and keeping an eye one them to make sure they remain OK).

llvm/lib/Transforms/Scalar/LoopFlatten.cpp

676

We can remove the LPMUpdater again if it's not needed/used?

732

I think this can just be for (Loop *L : *LI), then it will only include the outermost loops.

[eopXD]

address comments.

[eopXD]

We can remove the LPMUpdater again if it's not needed/used?

I think for a LoopNestPass (or a LoopPass), the LPMUpdater is necessary parameter.
As LoopNestPass is added by createFunctionToLoopPassAdaptor< LoopPassManager >(),
it needs to takes LPMUpdater & even though it is not used.

[Whitney]

llvm/lib/Transforms/Scalar/LoopFlatten.cpp

718

Why do we need these 3 new dependencies?

[eopXD]

@Whitney : do we need these 3 new dependencies?

I've deleted the parts for loop simplification and form LCSSA inside function Flatten,
and thought this would lead to the legacy pass depending on the passes I added.

I've just commented out the 3 passes and the tests still passed when I added -enable-new-pm=0 (using the legacy pass).
I think this means the 3 dependencies are unnecessary then, I will remove my addition.

[eopXD]

remove redundant pass dependencies added.

[eopXD]

remove redundant header added.

[Whitney]

LGTM.

[eopXD]

Reverting my commit to investigate for build failure.

[eopXD]

Resolve merge conflict correctly. (previously caused build fail)

[eopXD]

Rebase code to main.

[eopXD]

Remove declaration of LoopUnrollAndJam as a FunctionPass.

Previously I resolved the merge conflict incorrecly.
LoopUnrollAndJam is now a LoopPass.

llvm/include/llvm/Transforms/Scalar/LoopFlatten.h

 #include "llvm/Transforms/Scalar/LoopPassManager.h"
 
 namespace llvm {
 
 class LoopFlattenPass : public PassInfoMixin<LoopFlattenPass> {
 public:
   LoopFlattenPass() = default;
 
-  PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM);
+  PreservedAnalyses run(LoopNest &LN, LoopAnalysisManager &LAM,
+                        LoopStandardAnalysisResults &AR, LPMUpdater &U);
 };
 
 } // end namespace llvm
 
 #endif // LLVM_TRANSFORMS_SCALAR_LOOPFLATTEN_H

llvm/lib/Passes/PassBuilder.cpp

PassBuilder::buildO1FunctionSimplificationPipeline(OptimizationLevel Level,
   FPM.addPass(
       RequireAnalysisPass<OptimizationRemarkEmitterAnalysis, Function>());
   FPM.addPass(createFunctionToLoopPassAdaptor(std::move(LPM1),
                                               EnableMSSALoopDependency,
                                               /*UseBlockFrequencyInfo=*/true));
   FPM.addPass(SimplifyCFGPass());
   FPM.addPass(InstCombinePass());
   if (EnableLoopFlatten)
-    FPM.addPass(LoopFlattenPass());
+    FPM.addPass(createFunctionToLoopPassAdaptor(LoopFlattenPass()));
   // The loop passes in LPM2 (LoopFullUnrollPass) do not preserve MemorySSA.
   // *All* loop passes must preserve it, in order to be able to use it.
   FPM.addPass(createFunctionToLoopPassAdaptor(std::move(LPM2),
                                               /*UseMemorySSA=*/false,
                                               /*UseBlockFrequencyInfo=*/false));
 
   // Delete small array after loop unroll.
   FPM.addPass(SROA());
PassBuilder::buildFunctionSimplificationPipeline(OptimizationLevel Level,
   FPM.addPass(
       RequireAnalysisPass<OptimizationRemarkEmitterAnalysis, Function>());
   FPM.addPass(createFunctionToLoopPassAdaptor(std::move(LPM1),
                                               EnableMSSALoopDependency,
                                               /*UseBlockFrequencyInfo=*/true));
   FPM.addPass(SimplifyCFGPass());
   FPM.addPass(InstCombinePass());
   if (EnableLoopFlatten)
-    FPM.addPass(LoopFlattenPass());
+    FPM.addPass(createFunctionToLoopPassAdaptor(LoopFlattenPass()));
   // The loop passes in LPM2 (LoopIdiomRecognizePass, IndVarSimplifyPass,
   // LoopDeletionPass and LoopFullUnrollPass) do not preserve MemorySSA.
   // *All* loop passes must preserve it, in order to be able to use it.
   FPM.addPass(createFunctionToLoopPassAdaptor(std::move(LPM2),
                                               /*UseMemorySSA=*/false,
                                               /*UseBlockFrequencyInfo=*/false));
 
   // Delete small array after loop unroll.
PassBuilder::buildLTODefaultPipeline(OptimizationLevel Level,
   MainFPM.addPass(MemCpyOptPass());
 
   // Nuke dead stores.
   MainFPM.addPass(DSEPass());
   MainFPM.addPass(MergedLoadStoreMotionPass());
 
   // More loops are countable; try to optimize them.
   if (EnableLoopFlatten && Level.getSpeedupLevel() > 1)
-    MainFPM.addPass(LoopFlattenPass());
+    MainFPM.addPass(createFunctionToLoopPassAdaptor(LoopFlattenPass()));
 
   if (EnableConstraintElimination)
     MainFPM.addPass(ConstraintEliminationPass());
 
   LoopPassManager LPM;
   LPM.addPass(IndVarSimplifyPass());
   LPM.addPass(LoopDeletionPass());
   // FIXME: Add loop interchange.

llvm/lib/Passes/PassRegistry.def

 FUNCTION_PASS("lower-constant-intrinsics", LowerConstantIntrinsicsPass())
 FUNCTION_PASS("lower-matrix-intrinsics", LowerMatrixIntrinsicsPass())
 FUNCTION_PASS("lower-matrix-intrinsics-minimal", LowerMatrixIntrinsicsPass(true))
 FUNCTION_PASS("lower-widenable-condition", LowerWidenableConditionPass())
 FUNCTION_PASS("guard-widening", GuardWideningPass())
 FUNCTION_PASS("load-store-vectorizer", LoadStoreVectorizerPass())
 FUNCTION_PASS("loop-simplify", LoopSimplifyPass())
 FUNCTION_PASS("loop-sink", LoopSinkPass())
-FUNCTION_PASS("loop-flatten", LoopFlattenPass())
 FUNCTION_PASS("lowerinvoke", LowerInvokePass())
 FUNCTION_PASS("lowerswitch", LowerSwitchPass())
 FUNCTION_PASS("mem2reg", PromotePass())
 FUNCTION_PASS("memcpyopt", MemCpyOptPass())
 FUNCTION_PASS("mergeicmps", MergeICmpsPass())
 FUNCTION_PASS("mergereturn", UnifyFunctionExitNodesPass())
 FUNCTION_PASS("nary-reassociate", NaryReassociatePass())
 FUNCTION_PASS("newgvn", NewGVNPass())

 
 #ifndef LOOP_PASS
 #define LOOP_PASS(NAME, CREATE_PASS)
 #endif
 LOOP_PASS("canon-freeze", CanonicalizeFreezeInLoopsPass())
 LOOP_PASS("dot-ddg", DDGDotPrinterPass())
 LOOP_PASS("invalidate<all>", InvalidateAllAnalysesPass())
 LOOP_PASS("licm", LICMPass())
+LOOP_PASS("loop-flatten", LoopFlattenPass())
 LOOP_PASS("loop-idiom", LoopIdiomRecognizePass())
 LOOP_PASS("loop-instsimplify", LoopInstSimplifyPass())
 LOOP_PASS("loop-interchange", LoopInterchangePass())
 LOOP_PASS("loop-rotate", LoopRotatePass())
 LOOP_PASS("no-op-loop", NoOpLoopPass())
 LOOP_PASS("print", PrintLoopPass(dbgs()))
 LOOP_PASS("loop-deletion", LoopDeletionPass())
 LOOP_PASS("loop-simplifycfg", LoopSimplifyCFGPass())

 #ifndef LOOP_PASS_WITH_PARAMS
 #define LOOP_PASS_WITH_PARAMS(NAME, CREATE_PASS, PARSER)
 #endif
 LOOP_PASS_WITH_PARAMS("unswitch",
                            [](bool NonTrivial) {
                              return SimpleLoopUnswitchPass(NonTrivial);
                            },
                            parseLoopUnswitchOptions)
 #undef LOOP_PASS_WITH_PARAMS

llvm/lib/Transforms/Scalar/LoopFlatten.cpp

 static cl::opt<bool>
     AssumeNoOverflow("loop-flatten-assume-no-overflow", cl::Hidden,
                      cl::init(false),
                      cl::desc("Assume that the product of the two iteration "
                               "limits will never overflow"));
 
 static cl::opt<bool>
     WidenIV("loop-flatten-widen-iv", cl::Hidden,
             cl::init(true),
             cl::desc("Widen the loop induction variables, if possible, so "
                      "overflow checks won't reject flattening"));
 
 struct FlattenInfo {
   Loop *OuterLoop = nullptr;
   Loop *InnerLoop = nullptr;
   PHINode *InnerInductionPHI = nullptr;
   PHINode *OuterInductionPHI = nullptr;
   Value *InnerLimit = nullptr;
   Value *OuterLimit = nullptr;
   BinaryOperator *InnerIncrement = nullptr;
   BinaryOperator *OuterIncrement = nullptr;
   BranchInst *InnerBranch = nullptr;
   BranchInst *OuterBranch = nullptr;
   SmallPtrSet<Value *, 4> LinearIVUses;
   SmallPtrSet<PHINode *, 4> InnerPHIsToTransform;
 
   // Whether this holds the flatten info before or after widening.
   bool Widened = false;
 
   FlattenInfo(Loop *OL, Loop *IL) : OuterLoop(OL), InnerLoop(IL) {};
 };
 
 // Finds the induction variable, increment and limit for a simple loop that we
 // can flatten.
 static bool findLoopComponents(
     Loop *L, SmallPtrSetImpl<Instruction *> &IterationInstructions,
     PHINode *&InductionPHI, Value *&Limit, BinaryOperator *&Increment,
     BranchInst *&BackBranch, ScalarEvolution *SE) {
if (OR == OverflowResult::AlwaysOverflowsHigh ||
     LLVM_DEBUG(dbgs() << "Multiply might overflow, not flattening\n");
     return false;
   }
 
   LLVM_DEBUG(dbgs() << "Multiply cannot overflow, modifying loop in-place\n");
   return DoFlattenLoopPair(FI, DT, LI, SE, AC, TTI);
 }
 
-bool Flatten(DominatorTree *DT, LoopInfo *LI, ScalarEvolution *SE,
+bool Flatten(LoopNest &LN, DominatorTree *DT, LoopInfo *LI, ScalarEvolution *SE,
              AssumptionCache *AC, TargetTransformInfo *TTI) {
   bool Changed = false;
-  for (auto *InnerLoop : LI->getLoopsInPreorder()) {
+  for (Loop *InnerLoop : LN.getLoops()) {
     auto *OuterLoop = InnerLoop->getParentLoop();
     if (!OuterLoop)
       continue;
     FlattenInfo FI(OuterLoop, InnerLoop);
     Changed |= FlattenLoopPair(FI, DT, LI, SE, AC, TTI);
   }
   return Changed;
 }
 
-PreservedAnalyses LoopFlattenPass::run(Function &F,
-                                       FunctionAnalysisManager &AM) {
-  auto *DT = &AM.getResult<DominatorTreeAnalysis>(F);
-  auto *LI = &AM.getResult<LoopAnalysis>(F);
-  auto *SE = &AM.getResult<ScalarEvolutionAnalysis>(F);
-  auto *AC = &AM.getResult<AssumptionAnalysis>(F);
-  auto *TTI = &AM.getResult<TargetIRAnalysis>(F);
+PreservedAnalyses LoopFlattenPass::run(LoopNest &LN, LoopAnalysisManager &LAM,
+                                       LoopStandardAnalysisResults &AR,
+                                       LPMUpdater &U) {
 
   bool Changed = false;
 
   // The loop flattening pass requires loops to be
   // in simplified form, and also needs LCSSA. Running
   // this pass will simplify all loops that contain inner loops,
   // regardless of whether anything ends up being flattened.
-  for (const auto &L : *LI) {
-    if (L->isInnermost())
-      continue;
-    Changed |=
-        simplifyLoop(L, DT, LI, SE, AC, nullptr, false /* PreserveLCSSA */);
-    Changed |= formLCSSARecursively(*L, *DT, LI, SE);
-  }
-
-  Changed |= Flatten(DT, LI, SE, AC, TTI);
+  Changed |= Flatten(LN, &AR.DT, &AR.LI, &AR.SE, &AR.AC, &AR.TTI);
 
   if (!Changed)
     return PreservedAnalyses::all();
 
   return PreservedAnalyses::none();
 }
 
 namespace {

 };
 } // namespace
 
 char LoopFlattenLegacyPass::ID = 0;
 INITIALIZE_PASS_BEGIN(LoopFlattenLegacyPass, "loop-flatten", "Flattens loops",
                       false, false)
 INITIALIZE_PASS_DEPENDENCY(TargetTransformInfoWrapperPass)
 INITIALIZE_PASS_DEPENDENCY(AssumptionCacheTracker)
 INITIALIZE_PASS_END(LoopFlattenLegacyPass, "loop-flatten", "Flattens loops",
                     false, false)
 
 FunctionPass *llvm::createLoopFlattenPass() { return new LoopFlattenLegacyPass(); }
 
 bool LoopFlattenLegacyPass::runOnFunction(Function &F) {
   ScalarEvolution *SE = &getAnalysis<ScalarEvolutionWrapperPass>().getSE();
   LoopInfo *LI = &getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
   auto *DTWP = getAnalysisIfAvailable<DominatorTreeWrapperPass>();
   DominatorTree *DT = DTWP ? &DTWP->getDomTree() : nullptr;
   auto &TTIP = getAnalysis<TargetTransformInfoWrapperPass>();
   auto *TTI = &TTIP.getTTI(F);
   auto *AC = &getAnalysis<AssumptionCacheTracker>().getAssumptionCache(F);
-  return Flatten(DT, LI, SE, AC, TTI);
+  bool Changed = false;
+  for (Loop *L : *LI) {
+    auto LN = LoopNest::getLoopNest(*L, *SE);
+    Changed |= Flatten(*LN, DT, LI, SE, AC, TTI);
+  }
+  return Changed;
 }