[NPM] Port -loop-versioning-licm to NPM

[aeubanks]

Thanks! Can you add a second RUN line with -passes=loop-versioning-licm to an existing test?

[aeubanks]

llvm/include/llvm/Transforms/Scalar/LoopVersioningLICM.h

18–19

These shouldn't be necessary

llvm/lib/Transforms/Scalar/LoopVersioningLICM.cpp

147

is the LoopAccessLegacyAnalysis necessary? Can LoopVersioningLICM only need the LoopAccessInfo passed in from callers? Looks like both the legacy and NPM pass can create the proper LoopAccessInfo.

[TaWeiTu]

Address comments.

[TaWeiTu]

In D89371#2330309, @aeubanks wrote:

Thanks! Can you add a second RUN line with -passes=loop-versioning-licm to an existing test?

Thanks for the review! I will update the tests later.

[aeubanks]

llvm/lib/Transforms/Scalar/LoopVersioningLICM.cpp

147

I meant can we can treat LoopAccessInfo just like the other analyses like DominatorTree?
Creating it inside LoopVersioningLICMPass::run/LoopVersioningLICMLegacyPass::runOnLoop rather than passing a function_ref. So GetLAI is unnecessary.

[TaWeiTu]

llvm/lib/Transforms/Scalar/LoopVersioningLICM.cpp

147

The reason I used GetLAI in the first place is that we might hit an early return with instructions that are not safe for versioning and we don't need to analyze the whole loop in this case.
What's your opinion on this? Thanks!

[aeubanks]

llvm/lib/Transforms/Scalar/LoopVersioningLICM.cpp

147

Ah that makes sense, sgtm. A comment would be good.

[TaWeiTu]

Add comments regarding GetLAI. Port tests to NPM.

[TaWeiTu]

llvm/test/Transforms/LoopVersioningLICM/loopversioningLICM1.ll

2 ↗

(On Diff #298391)

I was not able to fix the remaining part of this test and loopversioningLICM2.ll yet, but it seemed to be more related to LICM itself.

[aeubanks]

To test the NPM, don't add -enable-new-pm, but use the proper NPM flag -passes. So e.g. -passes=default<O1>,loop-versioning-licm,licm in place of -enable-new-pm -O1 -loop-versioning-licm -licm.
The failing tests seem fairly brittle and likely fail because the O1 pipeline is slightly different. Especially the names. Maybe the test should instead contain the output IR of running the existing test under -O1, then as the test itself run that IR through the proper passes.

[TaWeiTu]

In D89371#2332614, @aeubanks wrote:

To test the NPM, don't add -enable-new-pm, but use the proper NPM flag -passes. So e.g. -passes=default<O1>,loop-versioning-licm,licm in place of -enable-new-pm -O1 -loop-versioning-licm -licm.

OK. Will update the tests.

The failing tests seem fairly brittle and likely fail because the O1 pipeline is slightly different. Especially the names. Maybe the test should instead contain the output IR of running the existing test under -O1, then as the test itself run that IR through the proper passes.

From what I've seen the tests have already been passed through the O1 pipeline.
Since by specifying -O1 -loop-versioning-licm -licm the O1 pipeline runs after the two passes, even though NPM and LPM produce (almost) the same IR, the difference between the O1 pipelines that run afterward results in the failures.
So, one quick fix would be to run the IR through the two passes in NPM and then pipe it into the LPM O1 pipeline, but I find it quite inelegant.
What's your opinion? Thanks!

[aeubanks]

./build/rel/bin/opt -S -o - -enable-new-pm=0 -O1 -loop-versioning-licm -licm -debug-pass=Structure llvm/test/Transforms/LoopVersioningLICM/loopversioningLICM1.ll --print-before-all shows that -O1 runs first, then the LICM passes. In opt.cpp it checks the order they are passed on the command line and adds them in that order (including -O#).
So I think running it through the tests through legacy -O1 and using that as the actual test would work.

[TaWeiTu]

In D89371#2332731, @aeubanks wrote:

./build/rel/bin/opt -S -o - -enable-new-pm=0 -O1 -loop-versioning-licm -licm -debug-pass=Structure llvm/test/Transforms/LoopVersioningLICM/loopversioningLICM1.ll --print-before-all shows that -O1 runs first, then the LICM passes. In opt.cpp it checks the order they are passed on the command line and adds them in that order (including -O#).
So I think running it through the tests through legacy -O1 and using that as the actual test would work.

Ah, my bad, thanks for clarifying! However,

./bin/opt -S -O1 loopversioningLICM1.ll -o O1.ll
./bin/opt -S -loop-versioning-licm -licm O1.ll

does not seem to be working for me for some unknown reasons. I'll dive into it more deeply tomorrow.
Thanks for your time.

[TaWeiTu]

Fix tests.

[TaWeiTu]

llvm/test/Transforms/LoopVersioningLICM/loopversioningLICM1.ll

2 ↗

(On Diff #298572)

Running the two passes separately here to ensure the simplified and LCSSA loop structured of the versioned loops so that LICM works properly.
Is there a better way to do so?

[aeubanks]

llvm/test/Transforms/LoopVersioningLICM/loopversioningLICM1.ll

2 ↗

(On Diff #298572)

I think that's the proper way. I'm not super familiar with loop passes, I believe they must preserve LCSSA form, but do loop passes need to make sure that loop-simplify is a no-op if run after?

[TaWeiTu]

llvm/test/Transforms/LoopVersioningLICM/loopversioningLICM1.ll

2 ↗

(On Diff #298572)

This pass does preserve LCSSA judging from the assertion in LICM. The problem is that the LICM demands the loop to have a dedicated exit.
I'm not sure whether the simplified-form should be preserved. The loop terminology page says that LCSSA should be preserved, but I couldn't find similar discussion about loop-simplify.
However, since the versioning part of loop-versioning-licm is done via loop-versioning, I suspect that the latter preserves simplified form.
Should I add dummy exit blocks after the versioned loops to make it simplified?

[aeubanks]

I'm not sure, maybe asbirlea has better comments.
Otherwise lgtm

[TaWeiTu]

OK! Thanks for your review. I've submitted a patch D89569 which adds dedicated exits to the versioned loops.

[TaWeiTu]

Ping.

[aeubanks]

lgtm, but https://reviews.llvm.org/D89569 should be submitted first

[TaWeiTu]

In D89371#2347633, @aeubanks wrote:

lgtm, but https://reviews.llvm.org/D89569 should be submitted first

Of course. Thanks!

[TaWeiTu]

Rebase

llvm/include/llvm/InitializePasses.h

 void initializeLoopRotateLegacyPassPass(PassRegistry&);
 void initializeLoopSimplifyCFGLegacyPassPass(PassRegistry&);
 void initializeLoopSimplifyPass(PassRegistry&);
 void initializeLoopStrengthReducePass(PassRegistry&);
 void initializeLoopUnrollAndJamPass(PassRegistry&);
 void initializeLoopUnrollPass(PassRegistry&);
 void initializeLoopUnswitchPass(PassRegistry&);
 void initializeLoopVectorizePass(PassRegistry&);
-void initializeLoopVersioningLICMPass(PassRegistry&);
+void initializeLoopVersioningLICMLegacyPassPass(PassRegistry &);
 void initializeLoopVersioningLegacyPassPass(PassRegistry &);
 void initializeLowerAtomicLegacyPassPass(PassRegistry&);
 void initializeLowerConstantIntrinsicsPass(PassRegistry&);
 void initializeLowerEmuTLSPass(PassRegistry&);
 void initializeLowerExpectIntrinsicPass(PassRegistry&);
 void initializeLowerGuardIntrinsicLegacyPassPass(PassRegistry&);
 void initializeLowerWidenableConditionLegacyPassPass(PassRegistry&);
 void initializeLowerIntrinsicsPass(PassRegistry&);

llvm/include/llvm/Transforms/Scalar/LoopVersioningLICM.h

+//===- LoopVersioningLICM.h - LICM Loop Versioning ------------------------===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_TRANSFORMS_SCALAR_LOOPVERSIONINGLICM_H
+#define LLVM_TRANSFORMS_SCALAR_LOOPVERSIONINGLICM_H
+
+#include "llvm/IR/PassManager.h"
+#include "llvm/Transforms/Scalar/LoopPassManager.h"
+
+namespace llvm {
+
+class LoopVersioningLICMPass : public PassInfoMixin<LoopVersioningLICMPass> {
+public:
+  PreservedAnalyses run(Loop &L, LoopAnalysisManager &AM,
+                        LoopStandardAnalysisResults &LAR, LPMUpdater &U);
+};
+
+} // namespace llvm
+
+#endif // LLVM_TRANSFORMS_SCALAR_LOOPVERSIONINGLICM_H

llvm/lib/Passes/PassBuilder.cpp

 #include "llvm/Transforms/Scalar/LoopPredication.h"
 #include "llvm/Transforms/Scalar/LoopReroll.h"
 #include "llvm/Transforms/Scalar/LoopRotation.h"
 #include "llvm/Transforms/Scalar/LoopSimplifyCFG.h"
 #include "llvm/Transforms/Scalar/LoopSink.h"
 #include "llvm/Transforms/Scalar/LoopStrengthReduce.h"
 #include "llvm/Transforms/Scalar/LoopUnrollAndJamPass.h"
 #include "llvm/Transforms/Scalar/LoopUnrollPass.h"
+#include "llvm/Transforms/Scalar/LoopVersioningLICM.h"
 #include "llvm/Transforms/Scalar/LowerAtomic.h"
 #include "llvm/Transforms/Scalar/LowerConstantIntrinsics.h"
 #include "llvm/Transforms/Scalar/LowerExpectIntrinsic.h"
 #include "llvm/Transforms/Scalar/LowerGuardIntrinsic.h"
 #include "llvm/Transforms/Scalar/LowerMatrixIntrinsics.h"
 #include "llvm/Transforms/Scalar/LowerWidenableCondition.h"
 #include "llvm/Transforms/Scalar/MakeGuardsExplicit.h"
 #include "llvm/Transforms/Scalar/MemCpyOptimizer.h"

llvm/lib/Passes/PassRegistry.def

 LOOP_PASS("print<ddg>", DDGAnalysisPrinterPass(dbgs()))
 LOOP_PASS("print<iv-users>", IVUsersPrinterPass(dbgs()))
 LOOP_PASS("print<loopnest>", LoopNestPrinterPass(dbgs()))
 LOOP_PASS("print<loop-cache-cost>", LoopCachePrinterPass(dbgs()))
 LOOP_PASS("loop-predication", LoopPredicationPass())
 LOOP_PASS("guard-widening", GuardWideningPass())
 LOOP_PASS("simple-loop-unswitch", SimpleLoopUnswitchPass())
 LOOP_PASS("loop-reroll", LoopRerollPass())
+LOOP_PASS("loop-versioning-licm", LoopVersioningLICMPass())
 #undef LOOP_PASS
 
 #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/LoopVersioningLICM.cpp

 //              +----------+--------------+-----------+
 //                                 |
 //                           +-----+----+
 //                           |Join Block|
 //                           +----------+
 //
 //===----------------------------------------------------------------------===//
 
+#include "llvm/Transforms/Scalar/LoopVersioningLICM.h"
 #include "llvm/ADT/SmallVector.h"
 #include "llvm/ADT/StringRef.h"
 #include "llvm/Analysis/AliasAnalysis.h"
 #include "llvm/Analysis/AliasSetTracker.h"
 #include "llvm/Analysis/GlobalsModRef.h"
 #include "llvm/Analysis/LoopAccessAnalysis.h"
 #include "llvm/Analysis/LoopInfo.h"
 #include "llvm/Analysis/LoopPass.h"

 static cl::opt<unsigned> LVLoopDepthThreshold(
     "licm-versioning-max-depth-threshold",
     cl::desc(
         "LoopVersioningLICM's threshold for maximum allowed loop nest/depth"),
     cl::init(2), cl::Hidden);
 
 namespace {
 
-struct LoopVersioningLICM : public LoopPass {
+struct LoopVersioningLICMLegacyPass : public LoopPass {
   static char ID;
 
-  LoopVersioningLICM()
-      : LoopPass(ID), LoopDepthThreshold(LVLoopDepthThreshold),
-        InvariantThreshold(LVInvarThreshold) {
-    initializeLoopVersioningLICMPass(*PassRegistry::getPassRegistry());
+  LoopVersioningLICMLegacyPass() : LoopPass(ID) {
+    initializeLoopVersioningLICMLegacyPassPass(
+        *PassRegistry::getPassRegistry());
   }
 
   bool runOnLoop(Loop *L, LPPassManager &LPM) override;
 
+  StringRef getPassName() const override { return "Loop Versioning for LICM"; }
+
   void getAnalysisUsage(AnalysisUsage &AU) const override {
     AU.setPreservesCFG();
     AU.addRequired<AAResultsWrapperPass>();
     AU.addRequired<DominatorTreeWrapperPass>();
     AU.addRequiredID(LCSSAID);
     AU.addRequired<LoopAccessLegacyAnalysis>();
     AU.addRequired<LoopInfoWrapperPass>();
     AU.addRequiredID(LoopSimplifyID);
     AU.addRequired<ScalarEvolutionWrapperPass>();
     AU.addPreserved<AAResultsWrapperPass>();
     AU.addPreserved<GlobalsAAWrapperPass>();
     AU.addRequired<OptimizationRemarkEmitterWrapperPass>();
   }
+};
 
-  StringRef getPassName() const override { return "Loop Versioning for LICM"; }
+struct LoopVersioningLICM {
+  LoopVersioningLICM(AliasAnalysis *AA, ScalarEvolution *SE,
+                     OptimizationRemarkEmitter *ORE,
+                     function_ref<const LoopAccessInfo &(Loop *)> GetLAI)
+      : AA(AA), SE(SE), GetLAI(GetLAI),
+        LoopDepthThreshold(LVLoopDepthThreshold),
+        InvariantThreshold(LVInvarThreshold), ORE(ORE) {}
+
+  bool runOnLoop(Loop *L, LoopInfo *LI, DominatorTree *DT);
 
   void reset() {
     AA = nullptr;
     SE = nullptr;
-    LAA = nullptr;
     CurLoop = nullptr;
     LoadAndStoreCounter = 0;
     InvariantCounter = 0;
     IsReadOnlyLoop = true;
     ORE = nullptr;
     CurAST.reset();
   }
 
   class AutoResetter {
   public:
     AutoResetter(LoopVersioningLICM &LVLICM) : LVLICM(LVLICM) {}
     ~AutoResetter() { LVLICM.reset(); }
 
   private:
     LoopVersioningLICM &LVLICM;
   };
 
 private:
   // Current AliasAnalysis information
   AliasAnalysis *AA = nullptr;
 
   // Current ScalarEvolution
   ScalarEvolution *SE = nullptr;
 
-  // Current LoopAccessAnalysis
-  LoopAccessLegacyAnalysis *LAA = nullptr;
-
   // Current Loop's LoopAccessInfo
   const LoopAccessInfo *LAI = nullptr;
 
+  // Function for retrieving LoopAccessInfo
+  function_ref<const LoopAccessInfo &(Loop *)> GetLAI;
+
   // The current loop we are working on.
   Loop *CurLoop = nullptr;
 
   // AliasSet information for the current loop.
   std::unique_ptr<AliasSetTracker> CurAST;
 
   // Maximum loop nest threshold
   unsigned LoopDepthThreshold;
for (auto &Inst : *Block) {
         ORE->emit([&]() {
           return OptimizationRemarkMissed(DEBUG_TYPE, "IllegalLoopInst", &Inst)
                  << " Unsafe Loop Instruction";
         });
         return false;
       }
     }
   // Get LoopAccessInfo from current loop.
-  LAI = &LAA->getInfo(CurLoop);
+  LAI = &GetLAI(CurLoop);
   // Check LoopAccessInfo for need of runtime check.
   if (LAI->getRuntimePointerChecking()->getChecks().empty()) {
     LLVM_DEBUG(dbgs() << "    LAA: Runtime check not found !!\n");
     return false;
   }
   // Number of runtime-checks should be less then RuntimeMemoryCheckThreshold
   if (LAI->getNumRuntimePointerChecks() >
       VectorizerParams::RuntimeMemoryCheckThreshold) {
for (auto &Inst : *Block) {
       Inst.setMetadata(
           LLVMContext::MD_alias_scope,
           MDNode::concatenate(Inst.getMetadata(LLVMContext::MD_alias_scope),
                               MDNode::get(Inst.getContext(), Scopes)));
     }
   }
 }
 
-bool LoopVersioningLICM::runOnLoop(Loop *L, LPPassManager &LPM) {
+bool LoopVersioningLICMLegacyPass::runOnLoop(Loop *L, LPPassManager &LPM) {
+  if (skipLoop(L))
+    return false;
+
+  AliasAnalysis *AA = &getAnalysis<AAResultsWrapperPass>().getAAResults();
+  ScalarEvolution *SE = &getAnalysis<ScalarEvolutionWrapperPass>().getSE();
+  OptimizationRemarkEmitter *ORE =
+      &getAnalysis<OptimizationRemarkEmitterWrapperPass>().getORE();
+  LoopInfo *LI = &getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
+  DominatorTree *DT = &getAnalysis<DominatorTreeWrapperPass>().getDomTree();
+
+  auto GetLAI = [&](Loop *L) -> const LoopAccessInfo & {
+    return getAnalysis<LoopAccessLegacyAnalysis>().getInfo(L);
+  };
+
+  return LoopVersioningLICM(AA, SE, ORE, GetLAI).runOnLoop(L, LI, DT);
+}
+
+bool LoopVersioningLICM::runOnLoop(Loop *L, LoopInfo *LI, DominatorTree *DT) {
   // This will automatically release all resources hold by the current
   // LoopVersioningLICM object.
   AutoResetter Resetter(*this);
 
-  if (skipLoop(L))
-    return false;
-
   // Do not do the transformation if disabled by metadata.
   if (hasLICMVersioningTransformation(L) & TM_Disable)
     return false;
 
-  // Get Analysis information.
-  AA = &getAnalysis<AAResultsWrapperPass>().getAAResults();
-  SE = &getAnalysis<ScalarEvolutionWrapperPass>().getSE();
-  LAA = &getAnalysis<LoopAccessLegacyAnalysis>();
-  ORE = &getAnalysis<OptimizationRemarkEmitterWrapperPass>().getORE();
-  LAI = nullptr;
   // Set Current Loop
   CurLoop = L;
   CurAST.reset(new AliasSetTracker(*AA));
 
   // Loop over the body of this loop, construct AST.
-  LoopInfo *LI = &getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
   for (auto *Block : L->getBlocks()) {
     if (LI->getLoopFor(Block) == L) // Ignore blocks in subloop.
       CurAST->add(*Block);          // Incorporate the specified basic block
   }
 
   bool Changed = false;
 
   // Check feasiblity of LoopVersioningLICM.
   // If versioning found to be feasible and beneficial then proceed
   // else simply return, by cleaning up memory.
   if (isLegalForVersioning()) {
     // Do loop versioning.
     // Create memcheck for memory accessed inside loop.
     // Clone original loop, and set blocks properly.
-    DominatorTree *DT = &getAnalysis<DominatorTreeWrapperPass>().getDomTree();
     LoopVersioning LVer(*LAI, CurLoop, LI, DT, SE, true);
     LVer.versionLoop();
     // Set Loop Versioning metaData for original loop.
     addStringMetadataToLoop(LVer.getNonVersionedLoop(), LICMVersioningMetaData);
     // Set Loop Versioning metaData for version loop.
     addStringMetadataToLoop(LVer.getVersionedLoop(), LICMVersioningMetaData);
     // Set "llvm.mem.parallel_loop_access" metaData to versioned loop.
     // FIXME: "llvm.mem.parallel_loop_access" annotates memory access
     // instructions, not loops.
     addStringMetadataToLoop(LVer.getVersionedLoop(),
                             "llvm.mem.parallel_loop_access");
     // Update version loop with aggressive aliasing assumption.
     setNoAliasToLoop(LVer.getVersionedLoop());
     Changed = true;
   }
   return Changed;
 }
 
-char LoopVersioningLICM::ID = 0;
+char LoopVersioningLICMLegacyPass::ID = 0;
 
-INITIALIZE_PASS_BEGIN(LoopVersioningLICM, "loop-versioning-licm",
+INITIALIZE_PASS_BEGIN(LoopVersioningLICMLegacyPass, "loop-versioning-licm",
                       "Loop Versioning For LICM", false, false)
 INITIALIZE_PASS_DEPENDENCY(AAResultsWrapperPass)
 INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
 INITIALIZE_PASS_DEPENDENCY(GlobalsAAWrapperPass)
 INITIALIZE_PASS_DEPENDENCY(LCSSAWrapperPass)
 INITIALIZE_PASS_DEPENDENCY(LoopAccessLegacyAnalysis)
 INITIALIZE_PASS_DEPENDENCY(LoopInfoWrapperPass)
 INITIALIZE_PASS_DEPENDENCY(LoopSimplify)
 INITIALIZE_PASS_DEPENDENCY(ScalarEvolutionWrapperPass)
 INITIALIZE_PASS_DEPENDENCY(OptimizationRemarkEmitterWrapperPass)
-INITIALIZE_PASS_END(LoopVersioningLICM, "loop-versioning-licm",
+INITIALIZE_PASS_END(LoopVersioningLICMLegacyPass, "loop-versioning-licm",
                     "Loop Versioning For LICM", false, false)
 
-Pass *llvm::createLoopVersioningLICMPass() { return new LoopVersioningLICM(); }
+Pass *llvm::createLoopVersioningLICMPass() {
+  return new LoopVersioningLICMLegacyPass();
+}
+
+namespace llvm {
+
+PreservedAnalyses LoopVersioningLICMPass::run(Loop &L, LoopAnalysisManager &AM,
+                                              LoopStandardAnalysisResults &LAR,
+                                              LPMUpdater &U) {
+  AliasAnalysis *AA = &LAR.AA;
+  ScalarEvolution *SE = &LAR.SE;
+  DominatorTree *DT = &LAR.DT;
+  LoopInfo *LI = &LAR.LI;
+  const Function *F = L.getHeader()->getParent();
+  OptimizationRemarkEmitter ORE(F);
+
+  auto GetLAI = [&](Loop *L) -> const LoopAccessInfo & {
+    return AM.getResult<LoopAccessAnalysis>(*L, LAR);
+  };
+
+  if (!LoopVersioningLICM(AA, SE, &ORE, GetLAI).runOnLoop(&L, LI, DT))
+    return PreservedAnalyses::all();
+  return getLoopPassPreservedAnalyses();
+}
+} // namespace llvm

llvm/lib/Transforms/Scalar/Scalar.cpp

void llvm::initializeScalarOpts(PassRegistry &Registry) {
   initializeLoopPredicationLegacyPassPass(Registry);
   initializeLoopRotateLegacyPassPass(Registry);
   initializeLoopStrengthReducePass(Registry);
   initializeLoopRerollLegacyPassPass(Registry);
   initializeLoopUnrollPass(Registry);
   initializeLoopUnrollAndJamPass(Registry);
   initializeLoopUnswitchPass(Registry);
   initializeWarnMissedTransformationsLegacyPass(Registry);
-  initializeLoopVersioningLICMPass(Registry);
+  initializeLoopVersioningLICMLegacyPassPass(Registry);
   initializeLoopIdiomRecognizeLegacyPassPass(Registry);
   initializeLowerAtomicLegacyPassPass(Registry);
   initializeLowerConstantIntrinsicsPass(Registry);
   initializeLowerExpectIntrinsicPass(Registry);
   initializeLowerGuardIntrinsicLegacyPassPass(Registry);
   initializeLowerMatrixIntrinsicsLegacyPassPass(Registry);
   initializeLowerMatrixIntrinsicsMinimalLegacyPassPass(Registry);
   initializeLowerWidenableConditionLegacyPassPass(Registry);