[NFCI][LoopUnrollAndJam] Changing LoopUnrollAndJamPass to a function pass.

[Whitney]

Summary

This patch changes LoopUnrollAndJamPass to a function pass, and keeps the loops traversal order same as defined in FunctionToLoopPassAdaptor LoopPassManager.h.

The next patch will change the loop traversal to outer to inner order, so more loops can be transform.

Discussion in llvm-dev mailing list: https://groups.google.com/forum/#!topic/llvm-dev/LF4rUjkVI2g

[dmgreen]

Thanks.

This is only the new pass manager, right? It's probably best to keep the old pass manager working in the same way too, to keep them in sync. That will be the one that we use downstream at the mo.

[Whitney]

Changing LoopUnrollAndJamPass to a function pass for old pass manager as well.

[dmgreen]

llvm/lib/Transforms/Scalar/LoopUnrollAndJamPass.cpp

440

What if the function has no loops?

[Whitney]

Addressed review comment.

[dmgreen]

If UnJ needs loops in LoopSimplify form then it should request (or enforce) that loops are in that form. I think it can be done with AU.addRequiredID(LoopSimplifyID); (and maybe a DEPENDENCY on LoopSimplify?) That should hopefully mean that the tests don't need these adjustments.

Do we have any tests for the new pass manager? I feel we would have added some, but I don't see any here.

llvm/lib/Transforms/Scalar/LoopUnrollAndJamPass.cpp

441

I feel like we may need LCSSA on the outermost loops before calling UnJ on the inner one, from the loop of the check on line 576 of LoopUnrollAndJam.cpp. I'm not sure though, I didn't see it crash anywhere, but we likely don't have a good testcase for this.

[Whitney]

In D72230#1808620, @dmgreen wrote:

If UnJ needs loops in LoopSimplify form then it should request (or enforce) that loops are in that form. I think it can be done with AU.addRequiredID(LoopSimplifyID); (and maybe a DEPENDENCY on LoopSimplify?) That should hopefully mean that the tests don't need these adjustments.

I am not familiar with addRequiredID, do you know if there is an equivalent in the new pass manager?

Do we have any tests for the new pass manager? I feel we would have added some, but I don't see any here.

I don't see any LIT tests using the new pass manager in llvm/test/Transforms/LoopUnrollAndJam, is it in some other folder I missed?

[Whitney]

llvm/lib/Transforms/Scalar/LoopUnrollAndJamPass.cpp

441

I am thinking that we can treat LCSSA the same as loop simplify, if the loop is not in LCSSA form, then give up. And we can run LoopSimplify pass and LCSSA pass before unroll and jam pass. What do you think?

[dmgreen]

In D72230#1808657, @Whitney wrote:

In D72230#1808620, @dmgreen wrote:

If UnJ needs loops in LoopSimplify form then it should request (or enforce) that loops are in that form. I think it can be done with AU.addRequiredID(LoopSimplifyID); (and maybe a DEPENDENCY on LoopSimplify?) That should hopefully mean that the tests don't need these adjustments.

I am not familiar with addRequiredID, do you know if there is an equivalent in the new pass manager?

Do we have any tests for the new pass manager? I feel we would have added some, but I don't see any here.

I don't see any LIT tests using the new pass manager in llvm/test/Transforms/LoopUnrollAndJam, is it in some other folder I missed?

Not sure I'm afraid. I'm not much of an expert on the new pass manager (whenever I've tried it here, it's made performance worse and codesize bigger! So haven't used it much)

Please add the tests if it's simple enough. If it looks like it might be trouble, feel free to leave that to another patch.

llvm/lib/Transforms/Scalar/LoopUnrollAndJamPass.cpp

441

Sounds good. I think (but may be mistaken) that LCSSA can't "fail" to be created in the same way as LoopSimplify can. It looks like we can request them and mark them as preserved in the same way, though.

[Whitney]

In D72230#1808620, @dmgreen wrote:

If UnJ needs loops in LoopSimplify form then it should request (or enforce) that loops are in that form. I think it can be done with AU.addRequiredID(LoopSimplifyID); (and maybe a DEPENDENCY on LoopSimplify?) That should hopefully mean that the tests don't need these adjustments.

In https://groups.google.com/forum/m/?fbclid=IwAR3jQc7xQaWv2ovAvFTNuZXFKvCBo5lRx-vt_kyomdmcBgYpcRy5YcaDa0s#!topic/llvm-dev/0K8gEZ22VOE,
You cannot reliably use the addRequired() method to force a transform pass to run before another pass
The addRequired method is designed to tell the PassManager which *analysis* passes to run before your pass.

The discussion in the link above sounds like using addRequiredID on a transformation pass is not a good idea. Beside that, I don't know a way to require transformations to run before a pass in the new pass manager.
I suggested to give up on loops that are not simplified or loop nests that are not in LCSSA. And change the LITs to be all in simplified and LCSSA form. In additional, add the two transformation passes before LoopUnrollAndJamPass in the pipeline. What do you think?

[dmgreen]

In D72230#1809519, @Whitney wrote:

The discussion in the link above sounds like using addRequiredID on a transformation pass is not a good idea. Beside that, I don't know a way to require transformations to run before a pass in the new pass manager.
I suggested to give up on loops that are not simplified or loop nests that are not in LCSSA. And change the LITs to be all in simplified and LCSSA form. In additional, add the two transformation passes before LoopUnrollAndJamPass in the pipeline. What do you think?

I would agree that depending on other transform passes is a little odd, but it seems to work elsewhere. How do other passes work? LoopLoadElimination seems to be a FunctionPass that requires loops be in LoopSimplifyForm. I see it using INITIALIZE_PASS_DEPENDENCY(LoopSimplify) and AU.addRequiredID(LoopSimplifyID);

The LoopUnrollPass in the new pass manager seems to be a function pass now, and has this (same for the vectorizer):

// The unroller requires loops to be in simplified form, and also needs LCSSA.
// Since simplification may add new inner loops, it has to run before the
// legality and profitability checks. This means running the loop unroller
// will simplify all loops, regardless of whether anything end up being
// unrolled.
for (auto &L : LI) {
  Changed |=
      simplifyLoop(L, &DT, &LI, &SE, &AC, nullptr, false /* PreserveLCSSA */);
  Changed |= formLCSSARecursively(*L, DT, &LI, &SE);
}

Can we steal that? I would prefer it if this was mostly automatic, not having to update the tests or be careful to run passes in the right order every time.

From poking around, you may also need -aa-pipeline=type-based-aa,basic-aa to some of the tests if you run them under the new pass manager. And the order of addRequiredID seems to matter to get it to work.

[Whitney]

1. Makes loops in simplified and LCSSA form in the beginning of LoopUnrollAndJamPass.
2. Add LITs for new pass manager.

[dmgreen]

LGTM. Thanks.

llvm/include/llvm/Transforms/Scalar/LoopUnrollAndJamPass.h

 #define LLVM_TRANSFORMS_SCALAR_LOOPUNROLLANDJAMPASS_H
 
 #include "llvm/Analysis/LoopAnalysisManager.h"
 #include "llvm/Analysis/LoopInfo.h"
 #include "llvm/IR/PassManager.h"
 
 namespace llvm {
 
-class Loop;
-struct LoopStandardAnalysisResults;
-class LPMUpdater;
+class Function;
 
 /// A simple loop rotation transformation.
 class LoopUnrollAndJamPass : public PassInfoMixin<LoopUnrollAndJamPass> {
   const int OptLevel;
 
 public:
   explicit LoopUnrollAndJamPass(int OptLevel = 2) : OptLevel(OptLevel) {}
-  PreservedAnalyses run(Loop &L, LoopAnalysisManager &AM,
-                        LoopStandardAnalysisResults &AR, LPMUpdater &U);
+  PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM);
 };
 
 } // end namespace llvm
 
 #endif // LLVM_TRANSFORMS_SCALAR_LOOPUNROLLANDJAMPASS_H

llvm/lib/Passes/PassBuilder.cpp

ModulePassManager PassBuilder::buildModuleOptimizationPipeline(
   // Unroll small loops to hide loop backedge latency and saturate any parallel
   // execution resources of an out-of-order processor. We also then need to
   // clean up redundancies and loop invariant code.
   // FIXME: It would be really good to use a loop-integrated instruction
   // combiner for cleanup here so that the unrolling and LICM can be pipelined
   // across the loop nests.
   // We do UnrollAndJam in a separate LPM to ensure it happens before unroll
   if (EnableUnrollAndJam && PTO.LoopUnrolling) {
-    OptimizePM.addPass(
-        createFunctionToLoopPassAdaptor(LoopUnrollAndJamPass(Level)));
+    OptimizePM.addPass(LoopUnrollAndJamPass(Level));
   }
   OptimizePM.addPass(LoopUnrollPass(
       LoopUnrollOptions(Level, /*OnlyWhenForced=*/!PTO.LoopUnrolling,
                         PTO.ForgetAllSCEVInLoopUnroll)));
   OptimizePM.addPass(WarnMissedTransformationsPass());
   OptimizePM.addPass(InstCombinePass());
   OptimizePM.addPass(RequireAnalysisPass<OptimizationRemarkEmitterAnalysis, Function>());
   OptimizePM.addPass(createFunctionToLoopPassAdaptor(

llvm/lib/Passes/PassRegistry.def

 FUNCTION_PASS("sccp", SCCPPass())
 FUNCTION_PASS("sink", SinkingPass())
 FUNCTION_PASS("slp-vectorizer", SLPVectorizerPass())
 FUNCTION_PASS("speculative-execution", SpeculativeExecutionPass())
 FUNCTION_PASS("spec-phis", SpeculateAroundPHIsPass())
 FUNCTION_PASS("sroa", SROA())
 FUNCTION_PASS("tailcallelim", TailCallElimPass())
 FUNCTION_PASS("unreachableblockelim", UnreachableBlockElimPass())
+FUNCTION_PASS("unroll-and-jam", LoopUnrollAndJamPass())
 FUNCTION_PASS("verify", VerifierPass())
 FUNCTION_PASS("verify<domtree>", DominatorTreeVerifierPass())
 FUNCTION_PASS("verify<loops>", LoopVerifierPass())
 FUNCTION_PASS("verify<memoryssa>", MemorySSAVerifierPass())
 FUNCTION_PASS("verify<regions>", RegionInfoVerifierPass())
 FUNCTION_PASS("verify<safepoint-ir>", SafepointIRVerifierPass())
 FUNCTION_PASS("verify<scalar-evolution>", ScalarEvolutionVerifierPass())
 FUNCTION_PASS("view-cfg", CFGViewerPass())

 LOOP_PASS("rotate", LoopRotatePass())
 LOOP_PASS("no-op-loop", NoOpLoopPass())
 LOOP_PASS("print", PrintLoopPass(dbgs()))
 LOOP_PASS("loop-deletion", LoopDeletionPass())
 LOOP_PASS("simplify-cfg", LoopSimplifyCFGPass())
 LOOP_PASS("strength-reduce", LoopStrengthReducePass())
 LOOP_PASS("indvars", IndVarSimplifyPass())
 LOOP_PASS("irce", IRCEPass())
-LOOP_PASS("unroll-and-jam", LoopUnrollAndJamPass())
 LOOP_PASS("unroll-full", LoopFullUnrollPass())
 LOOP_PASS("print-access-info", LoopAccessInfoPrinterPass(dbgs()))
 LOOP_PASS("print<ddg>", DDGAnalysisPrinterPass(dbgs()))
 LOOP_PASS("print<ivusers>", IVUsersPrinterPass(dbgs()))
 LOOP_PASS("print<loop-cache-cost>", LoopCachePrinterPass(dbgs()))
 LOOP_PASS("loop-predication", LoopPredicationPass())
 LOOP_PASS("guard-widening", GuardWideningPass())
 #undef LOOP_PASS

llvm/lib/Transforms/Scalar/LoopUnrollAndJamPass.cpp

tryToUnrollAndJamLoop(Loop *L, DominatorTree &DT, LoopInfo *LI,
   // If loop has an unroll count pragma or unrolled by explicitly set count
   // mark loop as unrolled to prevent unrolling beyond that requested.
   if (UnrollResult != LoopUnrollResult::FullyUnrolled && IsCountSetExplicitly)
     L->setLoopAlreadyUnrolled();
 
   return UnrollResult;
 }
 
+static bool tryToUnrollAndJamLoop(Function &F, DominatorTree &DT, LoopInfo &LI,
+                                  ScalarEvolution &SE,
+                                  const TargetTransformInfo &TTI,
+                                  AssumptionCache &AC, DependenceInfo &DI,
+                                  OptimizationRemarkEmitter &ORE,
+                                  int OptLevel) {
+  bool DidSomething = false;
+
+  // The loop unroll and jam pass requires loops to be in simplified form, and also needs LCSSA.
+  // Since simplification may add new inner loops, it has to run before the
+  // legality and profitability checks. This means running the loop unroll and jam pass
+  // will simplify all loops, regardless of whether anything end up being
+  // unroll and jammed.
+  for (auto &L : LI) {
+    DidSomething |=
+        simplifyLoop(L, &DT, &LI, &SE, &AC, nullptr, false /* PreserveLCSSA */);
+    DidSomething |= formLCSSARecursively(*L, DT, &LI, &SE);
+  }
+
+  SmallPriorityWorklist<Loop *, 4> Worklist;
+  internal::appendLoopsToWorklist(reverse(LI), Worklist);
+  while (!Worklist.empty()) {
+    Loop *L = Worklist.pop_back_val();
+    formLCSSA(*L, DT, &LI, &SE);
+    LoopUnrollResult Result =
+        tryToUnrollAndJamLoop(L, DT, &LI, SE, TTI, AC, DI, ORE, OptLevel);
+    if (Result != LoopUnrollResult::Unmodified)
+      DidSomething = true;
+  }
+
+  return DidSomething;
+}
+
 namespace {
 
-class LoopUnrollAndJam : public LoopPass {
+class LoopUnrollAndJam : public FunctionPass {
 public:
   static char ID; // Pass ID, replacement for typeid
   unsigned OptLevel;
 
-  LoopUnrollAndJam(int OptLevel = 2) : LoopPass(ID), OptLevel(OptLevel) {
+  LoopUnrollAndJam(int OptLevel = 2) : FunctionPass(ID), OptLevel(OptLevel) {
     initializeLoopUnrollAndJamPass(*PassRegistry::getPassRegistry());
   }
 
-  bool runOnLoop(Loop *L, LPPassManager &LPM) override {
-    if (skipLoop(L))
+  bool runOnFunction(Function &F) override {
+    if (skipFunction(F))
       return false;
 
-    Function &F = *L->getHeader()->getParent();
-
     auto &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree();
-    LoopInfo *LI = &getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
+    LoopInfo &LI = getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
     ScalarEvolution &SE = getAnalysis<ScalarEvolutionWrapperPass>().getSE();
     const TargetTransformInfo &TTI =
         getAnalysis<TargetTransformInfoWrapperPass>().getTTI(F);
     auto &AC = getAnalysis<AssumptionCacheTracker>().getAssumptionCache(F);
     auto &DI = getAnalysis<DependenceAnalysisWrapperPass>().getDI();
-    // For the old PM, we can't use OptimizationRemarkEmitter as an analysis
-    // pass.  Function analyses need to be preserved across loop transformations
-    // but ORE cannot be preserved (see comment before the pass definition).
-    OptimizationRemarkEmitter ORE(&F);
-
-    LoopUnrollResult Result =
-        tryToUnrollAndJamLoop(L, DT, LI, SE, TTI, AC, DI, ORE, OptLevel);
-
-    if (Result == LoopUnrollResult::FullyUnrolled)
-      LPM.markLoopAsDeleted(*L);
+    auto &ORE = getAnalysis<OptimizationRemarkEmitterWrapperPass>().getORE();
 
-    return Result != LoopUnrollResult::Unmodified;
+    return tryToUnrollAndJamLoop(F, DT, LI, SE, TTI, AC, DI, ORE, OptLevel);
   }
 
   /// This transformation requires natural loop information & requires that
   /// loop preheaders be inserted into the CFG...
   void getAnalysisUsage(AnalysisUsage &AU) const override {
-    AU.addRequired<AssumptionCacheTracker>();
+    AU.addRequired<DominatorTreeWrapperPass>();
+    AU.addRequired<LoopInfoWrapperPass>();
+    AU.addRequired<ScalarEvolutionWrapperPass>();
     AU.addRequired<TargetTransformInfoWrapperPass>();
+    AU.addRequired<AssumptionCacheTracker>();
     AU.addRequired<DependenceAnalysisWrapperPass>();
-    getLoopAnalysisUsage(AU);
+    AU.addRequired<OptimizationRemarkEmitterWrapperPass>();
   }
 };
 
 } // end anonymous namespace
 
 char LoopUnrollAndJam::ID = 0;
 
 INITIALIZE_PASS_BEGIN(LoopUnrollAndJam, "loop-unroll-and-jam",
                       "Unroll and Jam loops", false, false)
-INITIALIZE_PASS_DEPENDENCY(AssumptionCacheTracker)
-INITIALIZE_PASS_DEPENDENCY(LoopPass)
+INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
+INITIALIZE_PASS_DEPENDENCY(LoopInfoWrapperPass)
+INITIALIZE_PASS_DEPENDENCY(ScalarEvolutionWrapperPass)
 INITIALIZE_PASS_DEPENDENCY(TargetTransformInfoWrapperPass)
+INITIALIZE_PASS_DEPENDENCY(AssumptionCacheTracker)
 INITIALIZE_PASS_DEPENDENCY(DependenceAnalysisWrapperPass)
+INITIALIZE_PASS_DEPENDENCY(OptimizationRemarkEmitterWrapperPass)
 INITIALIZE_PASS_END(LoopUnrollAndJam, "loop-unroll-and-jam",
                     "Unroll and Jam loops", false, false)
 
 Pass *llvm::createLoopUnrollAndJamPass(int OptLevel) {
   return new LoopUnrollAndJam(OptLevel);
 }
 
-PreservedAnalyses LoopUnrollAndJamPass::run(Loop &L, LoopAnalysisManager &AM,
-                                            LoopStandardAnalysisResults &AR,
-                                            LPMUpdater &) {
-  const auto &FAM =
-      AM.getResult<FunctionAnalysisManagerLoopProxy>(L, AR).getManager();
-  Function *F = L.getHeader()->getParent();
-
-  auto *ORE = FAM.getCachedResult<OptimizationRemarkEmitterAnalysis>(*F);
-  // FIXME: This should probably be optional rather than required.
-  if (!ORE)
-    report_fatal_error(
-        "LoopUnrollAndJamPass: OptimizationRemarkEmitterAnalysis not cached at "
-        "a higher level");
-
-  DependenceInfo DI(F, &AR.AA, &AR.SE, &AR.LI);
-
-  LoopUnrollResult Result = tryToUnrollAndJamLoop(
-      &L, AR.DT, &AR.LI, AR.SE, AR.TTI, AR.AC, DI, *ORE, OptLevel);
+PreservedAnalyses LoopUnrollAndJamPass::run(Function &F,
+                                            FunctionAnalysisManager &AM) {
+  ScalarEvolution &SE = AM.getResult<ScalarEvolutionAnalysis>(F);
+  LoopInfo &LI = AM.getResult<LoopAnalysis>(F);
+  TargetTransformInfo &TTI = AM.getResult<TargetIRAnalysis>(F);
+  AssumptionCache &AC = AM.getResult<AssumptionAnalysis>(F);
+  DominatorTree &DT = AM.getResult<DominatorTreeAnalysis>(F);
+  DependenceInfo &DI = AM.getResult<DependenceAnalysis>(F);
+  OptimizationRemarkEmitter &ORE =
+      AM.getResult<OptimizationRemarkEmitterAnalysis>(F);
 
-  if (Result == LoopUnrollResult::Unmodified)
+  if (!tryToUnrollAndJamLoop(F, DT, LI, SE, TTI, AC, DI, ORE, OptLevel))
     return PreservedAnalyses::all();
 
   return getLoopPassPreservedAnalyses();
 }

llvm/test/Transforms/LoopUnrollAndJam/dependencies.ll

 ; RUN: opt -basicaa -loop-unroll-and-jam -allow-unroll-and-jam -unroll-and-jam-count=4 < %s -S | FileCheck %s
+; RUN: opt -aa-pipeline=basic-aa -passes='unroll-and-jam' -allow-unroll-and-jam -unroll-and-jam-count=4 < %s -S | FileCheck %s
 
 target datalayout = "e-m:e-p:32:32-i64:64-v128:64:128-a:0:32-n32-S64"
 
 ; CHECK-LABEL: fore_aft_less
 ; CHECK: %j = phi
 ; CHECK: %j.1 = phi
 ; CHECK: %j.2 = phi
 ; CHECK: %j.3 = phi

llvm/test/Transforms/LoopUnrollAndJam/disable.ll

 ; RUN: opt -loop-unroll-and-jam -allow-unroll-and-jam -unroll-and-jam-count=4 -pass-remarks=loop-unroll-and-jam < %s -S 2>&1 | FileCheck %s
+; RUN: opt -passes='unroll-and-jam' -allow-unroll-and-jam -unroll-and-jam-count=4 -pass-remarks=loop-unroll-and-jam < %s -S 2>&1 | FileCheck %s
 
 target datalayout = "e-m:e-p:32:32-i64:64-v128:64:128-a:0:32-n32-S64"
 
 ;; Common check for all tests. None should be unroll and jammed
 ; CHECK-NOT: remark: {{.*}} unroll and jammed
 
 
 ; CHECK-LABEL: disabled1

llvm/test/Transforms/LoopUnrollAndJam/pragma-explicit.ll

 ; RUN: opt -loop-unroll-and-jam -allow-unroll-and-jam -unroll-runtime -unroll-partial-threshold=60 < %s -S | FileCheck %s
+; RUN: opt -aa-pipeline=type-based-aa,basic-aa -passes='unroll-and-jam' -allow-unroll-and-jam -unroll-runtime -unroll-partial-threshold=60 < %s -S | FileCheck %s
 
 target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
 target triple = "x86_64-unknown-linux-gnu"
 
 ; CHECK-LABEL: function
 ; The explicit metadata here should force this to be unroll and jammed 4 times (hence the %.pre60.3)
 ; CHECK: %.pre = phi i8 [ %.pre60.3, %for.cond1.for.cond.cleanup3_crit_edge.us ], [ %.pre.pre, %for.cond1.preheader.us.preheader.new ]
 ; CHECK: %indvars.iv.3 = phi i64 [ 0, %for.cond1.preheader.us ], [ %indvars.iv.next.3, %for.body4.us ]

llvm/test/Transforms/LoopUnrollAndJam/unroll-and-jam.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt -basicaa -tbaa -loop-unroll-and-jam -allow-unroll-and-jam -unroll-and-jam-count=4 -unroll-remainder < %s -S | FileCheck %s
+; RUN: opt -aa-pipeline=type-based-aa,basic-aa -passes='unroll-and-jam' -allow-unroll-and-jam -unroll-and-jam-count=4 -unroll-remainder < %s -S | FileCheck %s
 
 target datalayout = "e-m:e-p:32:32-i64:64-v128:64:128-a:0:32-n32-S64"
 
 ; CHECK-LABEL: test1
 ; Tests for(i) { sum = 0; for(j) sum += B[j]; A[i] = sum; }
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[CMP:%.*]] = icmp ne i32 [[J:%.*]], 0
 ; CHECK-NEXT:    [[CMPJ:%.*]] = icmp ne i32 [[I:%.*]], 0