[new PM] port LoopAccessAnalysis to new pass manager (part-1)

[davidxl]

Summary

part-1 is a NFC refactoring patch to enable porting. Changes include

1. renamed LoopAccessAnalysis.h to be LoopAccessInfo.h
2. split out LoopAccessAnalysis class into new file LoopAccessAnalysis.h
3. introduced LoopAccessFuncInfo class to represent function level analysis result of LoopAccess infos
4. machinery to support lazy computation of LoopAccessInfo

[davidxl]

ping ..

[chandlerc]

The number of different changes here make it really hard to review.

Can you instead actually send out the individual changes?

I also don't see any benefit to renaming the file. I think the "Info" suffix, as common as it is in LLVM, is probably a mistake. I'm not sure its worth going and fixing everything to use a different suffix, but I like the current file name better than the one you propose here. (Just my opinion, if others have a different view from working more closely with the loop access stuff or vectorization stuff, totally fine with that...)

[llvm-commits]

The renaming also makes the diff hard to read which I don't like either. I
will revert the renaming part.

thanks,

David

• msg-31405-77.txt162 BDownload

[davidxl]

Addressed review comments: do not rename existing header file and minimizes diffs.

PTAL

[chandlerc]

In D20560#450653, @davidxl wrote:

Addressed review comments: do not rename existing header file and minimizes diffs.

PTAL

I'm not sure what is expected to be changing here? There are four things in your patch description, and my suggestion was to split them apart. It looks like this isn't split apart, just adjusted?

I'm also not sure why you're adding the file to LoopAccessInfoAnalysis.h?

Maybe it would help to provide an updated over-all summary? I feel like I may just not understand what is going on here.

[davidxl]

New summary of the change:

1. split the legacy LoopAccess Analysis pass out of the header file LoopAccessAnalysis.h
2. introduced a new class LoopAccessFuncInfo that represents the function level analysis results that is cacheble.
3. move the interfaces that access the loop level LoopAccessInfo from legacy pass class to the new LoopAccessFuncInfo class
4. change clients to use the new interfaces

Does it make sense?

[chandlerc]

Thanks, this definitely helps.

In D20560#450661, @davidxl wrote:

New summary of the change:

1. split the legacy LoopAccess Analysis pass out of the header file LoopAccessAnalysis.h

Any particular reason to split these apart? It would seem simpler to just do the refactoring in place in the header file...

2. introduced a new class LoopAccessFuncInfo that represents the function level analysis results that is cacheble.

Makes sense. I'd probably call it LoopAccessInfo to fit with the common pattern, but I'm happy if there are reasons to name this differently.

3. move the interfaces that access the loop level LoopAccessInfo from legacy pass class to the new LoopAccessFuncInfo class
4. change clients to use the new interfaces

Does it make sense?

Yep. See one question on the code I have initially below...

include/llvm/Analysis/LoopAccessInfoAnalysis.h

36–45 ↗

(On Diff #59835)

Why this pattern?

Specifically, why deviate from the pattern that other analyses that have been ported use where you just construct the result class with pointers to the various other analysis results they reference?

Introducing a complete abstract interface seems like a much heavier weight abstraction; unless there is a specific problem solved, I'd rather the lighter weight abstraction.

[davidxl]

Addressed Chandler's feedback.

[anemet]

lib/Transforms/Scalar/LoopDistribute.cpp

611 ↗

(On Diff #59941)

getInfo().getInfo(...), really?

What is the difference between LAFI and LAA conceptually?

Without knowing much about the new PM, I see that you split out the cache from LAA (which was pretty much all it contained).

Should this perhaps be:

LAA->getCache().getInfo(..)

or getLoopInfo(..)

?

[davide]

include/llvm/Analysis/LoopAccessAnalysis.h

684 ↗

(On Diff #59941)

I'm not entirely sure what's the preferred LLVM style here, but I seldom (if ever) have seen variables ending with _ used like this.
I might miss something (and certainly I didn't compile), but, won't
this.AAR = AAR et similia work?

701 ↗

(On Diff #59941)

Move this outside of the function, and make it doxygen, i.e.
\brief Invalidate the cache when this pass is freed

706 ↗

(On Diff #59941)

This comment is too generic to be somehow useful. I think it should be expanded a bit, while you're here.

709 ↗

(On Diff #59941)

Why AAR and not AA as it was before? Also more consistent with how other variables are named.

lib/Analysis/LoopAccessAnalysis.cpp

1966 ↗

(On Diff #59941)

As you're passing getAnalysis everywhere, can't you also inline
TLIP ? &TLIP->getTLI() : nullptr instead of assigning TLI and passing the variable?

lib/Transforms/Scalar/LoopLoadElimination.cpp

555 ↗

(On Diff #59941)

I agree with Adam here, the getInfo().getInfo() is just very weird

[davidxl]

Addressed Adam and Davide's review comments.

[anemet]

I am fine with this with comments below addressed. Thanks!

include/llvm/Analysis/LoopAccessAnalysis.h

677 ↗

(On Diff #59997)

This needs a class comment. Also what do you think about naming this Result as well, i.e. LoopAccessAnalysisResult?

679–680 ↗

(On Diff #59997)

You don't need to call the default ctor for LAIM like this. Also you may want to use in-class data member initializers for the nullptrs and then remove the ctor altogether.

[davidxl]

Addressed Adam's feedback.

[anemet]

LGTM with the change below.

include/llvm/Analysis/LoopAccessAnalysis.h

747 ↗

(On Diff #60059)

s/LAFI/LAAR

[davide]

LGTM once you address Adam's last comment. Thanks for your patience.

[chandlerc]

At a meta level, if I've started reviewing a patch, please wait until I have a chance to see your updates before submitting it. I'm sorry I didn't get to it in the early morning, but its still well under 24h turn around and I don't know that its reasonable to expect lower latency.

That's not to say that I don't appreciate all of Adam and Davide's comments -- they're help reviewing is much appreciated -- but as it happens I don't actually think this is the right approach.

See below for more details.

llvm/trunk/include/llvm/Analysis/LoopAccessAnalysis.h

704–706

This doesn't seem like the right design. It leads to the getInfo().getInfo() awkward pattern that IMO is only marginally less awkward spelled as getResult().getInfo().

Instead, I think this pretty clearly wants to be a Loop analysis in the new pass manager. I think that the caching and map should be the new pass manager's caching and map, rather than rolling our own in a function analysis manager.

As a consequence, I don't think you need this result type at all. I think the LoopAccessInfo is already the correct result type. I think you'll need the DenseMap and logic around it in the legacy pass manager's function analysis, and you'll want a different query path to use the LoopAnalysisManager directly in the new pass manager.

Does that make sense?

[anemet]

llvm/trunk/include/llvm/Analysis/LoopAccessAnalysis.h

704–706

Just for the record, this had to be a function pass because the loop vectorizer is a function pass with the legacy PM.

It would be great to turn this into a loop pass with the new PM.

llvm/trunk/include/llvm/Analysis/LoopAccessAnalysis.h

 /// to \p PtrToStride and therefore add further predicates to \p PSE.
 /// The \p Assume parameter indicates if we are allowed to make additional
 /// run-time assumptions.
 int getPtrStride(PredicatedScalarEvolution &PSE, Value *Ptr, const Loop *Lp,
                  const ValueToValueMap &StridesMap = ValueToValueMap(),
                  bool Assume = false);
 
 /// \brief Returns true if the memory operations \p A and \p B are consecutive.
-/// This is a simple API that does not depend on the analysis pass. 
+/// This is a simple API that does not depend on the analysis pass.
 bool isConsecutiveAccess(Value *A, Value *B, const DataLayout &DL,
                          ScalarEvolution &SE, bool CheckType = true);
 
+/// \brief This class holds the result of LoopAccessAnalysis pass.
+class LoopAccessAnalysisResult {
+public:
+  void setDepAnalyses(AliasAnalysis *AA, DominatorTree *DT, LoopInfo *LI,
+                      ScalarEvolution *SCEV, TargetLibraryInfo *TLI) {
+    this->AA = AA;
+    this->DT = DT;
+    this->LI = LI;
+    this->SCEV = SCEV;
+    this->TLI = TLI;
+  }
+  /// \brief Query the result of the loop access information for the loop \p L.
+  ///
+  /// If the client speculates (and then issues run-time checks) for the values
+  /// of symbolic strides, \p Strides provides the mapping (see
+  /// replaceSymbolicStrideSCEV).  If there is no cached result available run
+  /// the analysis.
+  const LoopAccessInfo &getInfo(Loop *L, const ValueToValueMap &Strides);
+
+  void print(raw_ostream &OS, const Module *M = nullptr) const;
+
+  /// \brief Invalidate the cache when the pass is freed.
+  void releaseMemory() {
+    LoopAccessInfoMap.clear();
+  }
+
+private:
+  /// \brief LoopAccessInfo is created on demand. This map caches
+  /// the computed results.
+  DenseMap<Loop *, std::unique_ptr<LoopAccessInfo>> LoopAccessInfoMap;
+
+  AliasAnalysis *AA = nullptr;
+  DominatorTree *DT = nullptr;
+  LoopInfo *LI = nullptr;
+  ScalarEvolution *SCEV = nullptr;
+  TargetLibraryInfo *TLI = nullptr;
+};
+
 /// \brief This analysis provides dependence information for the memory accesses
 /// of a loop.
 ///
 /// It runs the analysis for a loop on demand.  This can be initiated by
 /// querying the loop access info via LAA::getInfo.  getInfo return a
 /// LoopAccessInfo object.  See this class for the specifics of what information
 /// is provided.
 class LoopAccessAnalysis : public FunctionPass {
 public:
   static char ID;
 
-  LoopAccessAnalysis() : FunctionPass(ID) {
+  LoopAccessAnalysis() : FunctionPass(ID), LAAR() {
     initializeLoopAccessAnalysisPass(*PassRegistry::getPassRegistry());
   }
 
   bool runOnFunction(Function &F) override;
 
   void getAnalysisUsage(AnalysisUsage &AU) const override;
 
-  /// \brief Query the result of the loop access information for the loop \p L.
-  ///
-  /// If the client speculates (and then issues run-time checks) for the values
-  /// of symbolic strides, \p Strides provides the mapping (see
-  /// replaceSymbolicStrideSCEV).  If there is no cached result available run
-  /// the analysis.
-  const LoopAccessInfo &getInfo(Loop *L, const ValueToValueMap &Strides);
+  LoopAccessAnalysisResult &getResult() { return LAAR; }
 
   void releaseMemory() override {
     // Invalidate the cache when the pass is freed.
-    LoopAccessInfoMap.clear();
+    LAAR.releaseMemory();
   }
 
   /// \brief Print the result of the analysis when invoked with -analyze.
-  void print(raw_ostream &OS, const Module *M = nullptr) const override;
+  void print(raw_ostream &OS, const Module *M = nullptr) const override {
+    LAAR.print(OS, M);
+  }
 
 private:
-  /// \brief The cache.
-  DenseMap<Loop *, std::unique_ptr<LoopAccessInfo>> LoopAccessInfoMap;
-
-  // The used analysis passes.
-  ScalarEvolution *SE;
-  const TargetLibraryInfo *TLI;
-  AliasAnalysis *AA;
-  DominatorTree *DT;
-  LoopInfo *LI;
+  LoopAccessAnalysisResult LAAR;
 };
 
 inline Instruction *MemoryDepChecker::Dependence::getSource(
     const LoopAccessInfo &LAI) const {
   return LAI.getDepChecker().getMemoryInstructions()[Source];
 }
 
 inline Instruction *MemoryDepChecker::Dependence::getDestination(
     const LoopAccessInfo &LAI) const {
   return LAI.getDepChecker().getMemoryInstructions()[Destination];
 }
 
 } // End llvm namespace
 
 #endif

llvm/trunk/lib/Analysis/LoopAccessAnalysis.cpp

void LoopAccessInfo::print(raw_ostream &OS, unsigned Depth) const {
 
   OS << "\n";
 
   OS.indent(Depth) << "Expressions re-written:\n";
   PSE.print(OS, Depth);
 }
 
 const LoopAccessInfo &
-LoopAccessAnalysis::getInfo(Loop *L, const ValueToValueMap &Strides) {
+LoopAccessAnalysisResult::getInfo(Loop *L, const ValueToValueMap &Strides) {
   auto &LAI = LoopAccessInfoMap[L];
 
 #ifndef NDEBUG
   assert((!LAI || LAI->NumSymbolicStrides == Strides.size()) &&
          "Symbolic strides changed for loop");
 #endif
 
   if (!LAI) {
     const DataLayout &DL = L->getHeader()->getModule()->getDataLayout();
-    LAI =
-        llvm::make_unique<LoopAccessInfo>(L, SE, DL, TLI, AA, DT, LI, Strides);
+    LAI = llvm::make_unique<LoopAccessInfo>(L, SCEV, DL, TLI, AA, DT, LI,
+                                            Strides);
 #ifndef NDEBUG
     LAI->NumSymbolicStrides = Strides.size();
 #endif
   }
   return *LAI.get();
 }
 
-void LoopAccessAnalysis::print(raw_ostream &OS, const Module *M) const {
-  LoopAccessAnalysis &LAA = *const_cast<LoopAccessAnalysis *>(this);
-
+void LoopAccessAnalysisResult::print(raw_ostream &OS, const Module *M) const {
   ValueToValueMap NoSymbolicStrides;
 
   for (Loop *TopLevelLoop : *LI)
     for (Loop *L : depth_first(TopLevelLoop)) {
       OS.indent(2) << L->getHeader()->getName() << ":\n";
-      auto &LAI = LAA.getInfo(L, NoSymbolicStrides);
+      auto &LAI = const_cast<LoopAccessAnalysisResult *>(this)->getInfo(
+          L, NoSymbolicStrides);
       LAI.print(OS, 4);
     }
 }
 
 bool LoopAccessAnalysis::runOnFunction(Function &F) {
-  SE = &getAnalysis<ScalarEvolutionWrapperPass>().getSE();
   auto *TLIP = getAnalysisIfAvailable<TargetLibraryInfoWrapperPass>();
-  TLI = TLIP ? &TLIP->getTLI() : nullptr;
-  AA = &getAnalysis<AAResultsWrapperPass>().getAAResults();
-  DT = &getAnalysis<DominatorTreeWrapperPass>().getDomTree();
-  LI = &getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
+  LAAR.setDepAnalyses(&getAnalysis<AAResultsWrapperPass>().getAAResults(),
+                      &getAnalysis<DominatorTreeWrapperPass>().getDomTree(),
+                      &getAnalysis<LoopInfoWrapperPass>().getLoopInfo(),
+                      &getAnalysis<ScalarEvolutionWrapperPass>().getSE(),
+                      TLIP ? &TLIP->getTLI() : nullptr);
 
   return false;
 }
 
 void LoopAccessAnalysis::getAnalysisUsage(AnalysisUsage &AU) const {
     AU.addRequired<ScalarEvolutionWrapperPass>();
     AU.addRequired<AAResultsWrapperPass>();
     AU.addRequired<DominatorTreeWrapperPass>();

llvm/trunk/lib/Transforms/Scalar/LoopDistribute.cpp

bool processLoop(LoopAccessAnalysis *LAA) {
 
     BasicBlock *PH = L->getLoopPreheader();
     if (!PH)
       return fail("no preheader");
     if (!L->getExitBlock())
       return fail("multiple exit blocks");
 
     // LAA will check that we only have a single exiting block.
-    LAI = &LAA->getInfo(L, ValueToValueMap());
+    LAI = &LAA->getResult().getInfo(L, ValueToValueMap());
 
     // Currently, we only distribute to isolate the part of the loop with
     // dependence cycles to enable partial vectorization.
     if (LAI->canVectorizeMemory())
       return fail("memory operations are safe for vectorization");
 
     auto *Dependences = LAI->getDepChecker().getDependences();
     if (!Dependences || Dependences->empty())

llvm/trunk/lib/Transforms/Scalar/LoopLoadElimination.cpp

for (Loop *TopLevelLoop : *LI)
       for (Loop *L : depth_first(TopLevelLoop))
         // We only handle inner-most loops.
         if (L->empty())
           Worklist.push_back(L);
 
     // Now walk the identified inner loops.
     bool Changed = false;
     for (Loop *L : Worklist) {
-      const LoopAccessInfo &LAI = LAA->getInfo(L, ValueToValueMap());
+      const LoopAccessInfo &LAI = LAA->getResult().getInfo(L, ValueToValueMap());
       // The actual work is performed by LoadEliminationForLoop.
       LoadEliminationForLoop LEL(L, LI, LAI, DT);
       Changed |= LEL.processLoop();
     }
 
     // Process each loop nest in the function.
     return Changed;
   }

llvm/trunk/lib/Transforms/Scalar/LoopVersioningLICM.cpp

bool LoopVersioningLICM::legalLoopInstructions() {
   // instruction safety.
   for (auto *Block : CurLoop->getBlocks())
     for (auto &Inst : *Block) {
       // If instruction is unsafe just return false.
       if (!instructionSafeForVersioning(&Inst))
         return false;
     }
   // Get LoopAccessInfo from current loop.
-  LAI = &LAA->getInfo(CurLoop, Strides);
+  LAI = &LAA->getResult().getInfo(CurLoop, Strides);
   // Check LoopAccessInfo for need of runtime check.
   if (LAI->getRuntimePointerChecking()->getChecks().empty()) {
     DEBUG(dbgs() << "    LAA: Runtime check not found !!\n");
     return false;
   }
   // Number of runtime-checks should be less then RuntimeMemoryCheckThreshold
   if (LAI->getNumRuntimePointerChecks() >
       VectorizerParams::RuntimeMemoryCheckThreshold) {

llvm/trunk/lib/Transforms/Utils/LoopVersioning.cpp

for (Loop *TopLevelLoop : *LI)
       for (Loop *L : depth_first(TopLevelLoop))
         // We only handle inner-most loops.
         if (L->empty())
           Worklist.push_back(L);
 
     // Now walk the identified inner loops.
     bool Changed = false;
     for (Loop *L : Worklist) {
-      const LoopAccessInfo &LAI = LAA->getInfo(L, ValueToValueMap());
+      const LoopAccessInfo &LAI = LAA->getResult().getInfo(L, ValueToValueMap());
       if (LAI.getNumRuntimePointerChecks() ||
           !LAI.PSE.getUnionPredicate().isAlwaysTrue()) {
         LoopVersioning LVer(LAI, L, LI, DT, SE);
         LVer.versionLoop();
         LVer.annotateLoopWithNoAlias();
         Changed = true;
       }
     }

llvm/trunk/lib/Transforms/Vectorize/LoopVectorize.cpp

while (!Worklist.empty()) {
     Uniforms.insert(I);
 
     // Insert all operands.
     Worklist.insert(Worklist.end(), I->op_begin(), I->op_end());
   }
 }
 
 bool LoopVectorizationLegality::canVectorizeMemory() {
-  LAI = &LAA->getInfo(TheLoop, Strides);
+  LAI = &LAA->getResult().getInfo(TheLoop, Strides);
   auto &OptionalReport = LAI->getReport();
   if (OptionalReport)
     emitAnalysis(VectorizationReport(*OptionalReport));
   if (!LAI->canVectorizeMemory())
     return false;
 
   if (LAI->hasStoreToLoopInvariantAddress()) {
     emitAnalysis(