[PM][DA] Port of the DependenceAnalysis to the new PM

[philip.pfaffe]

Summary

Ported DA to the new PM by splitting the former DependenceAnalysis Pass into a DependenceInfo result type and DependenceAnalysisWrapperPass type and adding a new PM-style DependenceAnalysis analysis pass returning the DependenceInfo.

[Resubmitting this because I forgot to add llvm-commits as a subscriber]

[philip.pfaffe]

Fixed bogner's nits and clang-formatted the patch.

Regarding the DependenceInfo and DependenceInfo::Constraint pointer members: I, too, think they should be references, but the patch is quite big, so I'll submit it seperately.

[philip.pfaffe]

Turned the check whether the Wrapper Pass has been run correctly into an assert.

Side Note: Other Analysis Wrapper Passes even completely omit this check (e.g. scev), so it might be worth consideration to either omit the check entirely or to update other Wrapper Passes to perform the check as well.

[philip.pfaffe]

Dropped info object checks to be consistent with other analysis wrapper passes and added a releaseMemory implementation.

[chandlerc]

Thanks Philip, landed it r269370 for you!

llvm/trunk/include/llvm/Analysis/DependenceAnalysis.h

public:
 
     /// dump - For debugging purposes, dumps a dependence to OS.
     ///
     void dump(raw_ostream &OS) const;
 
   private:
     Instruction *Src, *Dst;
     const Dependence *NextPredecessor, *NextSuccessor;
-    friend class DependenceAnalysis;
+    friend class DependenceInfo;
   };
 
   /// FullDependence - This class represents a dependence between two memory
   /// references in a function. It contains detailed information about the
   /// dependence (direction vectors, etc.) and is used when the compiler is
   /// able to accurately analyze the interaction of the references; that is,
   /// it is not a confused dependence (see Dependence). In most cases
   /// (for output, flow, and anti dependences), the dependence implies an
public:
     /// variable associated with the loop at this level.
     bool isScalar(unsigned Level) const override;
 
   private:
     unsigned short Levels;
     bool LoopIndependent;
     bool Consistent; // Init to true, then refine.
     std::unique_ptr<DVEntry[]> DV;
-    friend class DependenceAnalysis;
+    friend class DependenceInfo;
   };
 
-  /// DependenceAnalysis - This class is the main dependence-analysis driver.
+  /// DependenceInfo - This class is the main dependence-analysis driver.
   ///
-  class DependenceAnalysis : public FunctionPass {
-    void operator=(const DependenceAnalysis &) = delete;
-    DependenceAnalysis(const DependenceAnalysis &) = delete;
-
+  class DependenceInfo {
   public:
+    DependenceInfo(Function *F, AliasAnalysis *AA, ScalarEvolution *SE,
+                   LoopInfo *LI)
+        : AA(AA), SE(SE), LI(LI), F(F) {}
+
     /// depends - Tests for a dependence between the Src and Dst instructions.
     /// Returns NULL if no dependence; otherwise, returns a Dependence (or a
     /// FullDependence) with as much information as can be gleaned.
     /// The flag PossiblyLoopIndependent should be set by the caller
     /// if it appears that control flow can reach from Src to Dst
     /// without traversing a loop back edge.
     std::unique_ptr<Dependence> depends(Instruction *Src,
                                         Instruction *Dst,
public:
     ///    for (i = 6; i < 10; i++)
     ///        A[i] = ...
     ///        ... = A[11 - i]
     ///
     /// breaks the dependence and allows us to vectorize/parallelize
     /// both loops.
     const SCEV *getSplitIteration(const Dependence &Dep, unsigned Level);
 
+    Function *getFunction() const { return F; }
+
   private:
     AliasAnalysis *AA;
     ScalarEvolution *SE;
     LoopInfo *LI;
     Function *F;
 
     /// Subscript - This private struct represents a pair of subscripts from
     /// a pair of potentially multi-dimensional array references. We use a
private:
 
     /// updateDirection - Update direction vector entry
     /// based on the current constraint.
     void updateDirection(Dependence::DVEntry &Level,
                          const Constraint &CurConstraint) const;
 
     bool tryDelinearize(Instruction *Src, Instruction *Dst,
                         SmallVectorImpl<Subscript> &Pair);
+  }; // class DependenceInfo
 
+  /// \brief AnalysisPass to compute dependence information in a function
+  class DependenceAnalysis : public AnalysisInfoMixin<DependenceAnalysis> {
+  public:
+    typedef DependenceInfo Result;
+    Result run(Function &F, FunctionAnalysisManager &FAM);
+
+  private:
+    static char PassID;
+    friend struct AnalysisInfoMixin<DependenceAnalysis>;
+  }; // class DependenceAnalysis
+
+  /// \brief Legacy pass manager pass to access dependence information
+  class DependenceAnalysisWrapperPass : public FunctionPass {
   public:
     static char ID; // Class identification, replacement for typeinfo
-    DependenceAnalysis() : FunctionPass(ID) {
-      initializeDependenceAnalysisPass(*PassRegistry::getPassRegistry());
+    DependenceAnalysisWrapperPass() : FunctionPass(ID) {
+      initializeDependenceAnalysisWrapperPassPass(
+          *PassRegistry::getPassRegistry());
     }
 
     bool runOnFunction(Function &F) override;
     void releaseMemory() override;
     void getAnalysisUsage(AnalysisUsage &) const override;
     void print(raw_ostream &, const Module * = nullptr) const override;
-  }; // class DependenceAnalysis
+    DependenceInfo &getDI() const;
+
+  private:
+    std::unique_ptr<DependenceInfo> info;
+  }; // class DependenceAnalysisWrapperPass
 
   /// createDependenceAnalysisPass - This creates an instance of the
-  /// DependenceAnalysis pass.
-  FunctionPass *createDependenceAnalysisPass();
+  /// DependenceAnalysis wrapper pass.
+  FunctionPass *createDependenceAnalysisWrapperPass();
 
 } // namespace llvm
 
 #endif

llvm/trunk/include/llvm/Analysis/Passes.h

namespace llvm {
   //===--------------------------------------------------------------------===//
   //
   /// createLazyValueInfoPass - This creates an instance of the LazyValueInfo
   /// pass.
   FunctionPass *createLazyValueInfoPass();
 
   //===--------------------------------------------------------------------===//
   //
-  // createDependenceAnalysisPass - This creates an instance of the
-  // DependenceAnalysis pass.
+  // createDependenceAnalysisWrapperPass - This creates an instance of the
+  // DependenceAnalysisWrapper pass.
   //
-  FunctionPass *createDependenceAnalysisPass();
+  FunctionPass *createDependenceAnalysisWrapperPass();
 
   //===--------------------------------------------------------------------===//
   //
   // createCostModelAnalysisPass - This creates an instance of the
   // CostModelAnalysis pass.
   //
   FunctionPass *createCostModelAnalysisPass();
 

llvm/trunk/include/llvm/InitializePasses.h

 void initializeDAHPass(PassRegistry&);
 void initializeDCELegacyPassPass(PassRegistry&);
 void initializeDSEPass(PassRegistry&);
 void initializeDeadInstEliminationPass(PassRegistry&);
 void initializeDeadMachineInstructionElimPass(PassRegistry&);
 void initializeDelinearizationPass(PassRegistry &);
 void initializeDependenceAnalysisPass(PassRegistry&);
 void initializeDetectDeadLanesPass(PassRegistry&);
+void initializeDependenceAnalysisWrapperPassPass(PassRegistry&);
 void initializeDivergenceAnalysisPass(PassRegistry&);
 void initializeDomOnlyPrinterPass(PassRegistry&);
 void initializeDomOnlyViewerPass(PassRegistry&);
 void initializeDomPrinterPass(PassRegistry&);
 void initializeDomViewerPass(PassRegistry&);
 void initializeDominanceFrontierWrapperPassPass(PassRegistry&);
 void initializeDominatorTreeWrapperPassPass(PassRegistry&);
 void initializeEarlyIfConverterPass(PassRegistry&);

llvm/trunk/include/llvm/LinkAllPasses.h

ForcePassLinking() {
       (void) llvm::createStructurizeCFGPass();
       (void) llvm::createConstantMergePass();
       (void) llvm::createConstantPropagationPass();
       (void) llvm::createCostModelAnalysisPass();
       (void) llvm::createDeadArgEliminationPass();
       (void) llvm::createDeadCodeEliminationPass();
       (void) llvm::createDeadInstEliminationPass();
       (void) llvm::createDeadStoreEliminationPass();
-      (void) llvm::createDependenceAnalysisPass();
+      (void) llvm::createDependenceAnalysisWrapperPass();
       (void) llvm::createDivergenceAnalysisPass();
       (void) llvm::createDomOnlyPrinterPass();
       (void) llvm::createDomPrinterPass();
       (void) llvm::createDomOnlyViewerPass();
       (void) llvm::createDomViewerPass();
       (void) llvm::createGCOVProfilerPass();
       (void) llvm::createPGOInstrumentationGenLegacyPass();
       (void) llvm::createPGOInstrumentationUseLegacyPass();

llvm/trunk/lib/Analysis/Analysis.cpp

void llvm::initializeAnalysis(PassRegistry &Registry) {
   initializeCallGraphPrinterLegacyPassPass(Registry);
   initializeCallGraphViewerPass(Registry);
   initializeCostModelAnalysisPass(Registry);
   initializeCFGViewerPass(Registry);
   initializeCFGPrinterPass(Registry);
   initializeCFGOnlyViewerPass(Registry);
   initializeCFGOnlyPrinterPass(Registry);
   initializeCFLAAWrapperPassPass(Registry);
-  initializeDependenceAnalysisPass(Registry);
+  initializeDependenceAnalysisWrapperPassPass(Registry);
   initializeDelinearizationPass(Registry);
   initializeDemandedBitsWrapperPassPass(Registry);
   initializeDivergenceAnalysisPass(Registry);
   initializeDominanceFrontierWrapperPassPass(Registry);
   initializeDomViewerPass(Registry);
   initializeDomPrinterPass(Registry);
   initializeDomOnlyViewerPass(Registry);
   initializePostDomViewerPass(Registry);

llvm/trunk/lib/Analysis/DependenceAnalysis.cpp

 
 static cl::opt<bool>
 Delinearize("da-delinearize", cl::init(false), cl::Hidden, cl::ZeroOrMore,
             cl::desc("Try to delinearize array references."));
 
 //===----------------------------------------------------------------------===//
 // basics
 
-INITIALIZE_PASS_BEGIN(DependenceAnalysis, "da",
+DependenceAnalysis::Result
+DependenceAnalysis::run(Function &F, FunctionAnalysisManager &FAM) {
+  auto &AA = FAM.getResult<AAManager>(F);
+  auto &SE = FAM.getResult<ScalarEvolutionAnalysis>(F);
+  auto &LI = FAM.getResult<LoopAnalysis>(F);
+  return DependenceInfo(&F, &AA, &SE, &LI);
+}
+
+char DependenceAnalysis::PassID;
+
+INITIALIZE_PASS_BEGIN(DependenceAnalysisWrapperPass, "da",
                       "Dependence Analysis", true, true)
 INITIALIZE_PASS_DEPENDENCY(LoopInfoWrapperPass)
 INITIALIZE_PASS_DEPENDENCY(ScalarEvolutionWrapperPass)
 INITIALIZE_PASS_DEPENDENCY(AAResultsWrapperPass)
-INITIALIZE_PASS_END(DependenceAnalysis, "da",
-                    "Dependence Analysis", true, true)
-
-char DependenceAnalysis::ID = 0;
+INITIALIZE_PASS_END(DependenceAnalysisWrapperPass, "da", "Dependence Analysis",
+                    true, true)
 
+char DependenceAnalysisWrapperPass::ID = 0;
 
-FunctionPass *llvm::createDependenceAnalysisPass() {
-  return new DependenceAnalysis();
+FunctionPass *llvm::createDependenceAnalysisWrapperPass() {
+  return new DependenceAnalysisWrapperPass();
 }
 
-
-bool DependenceAnalysis::runOnFunction(Function &F) {
-  this->F = &F;
-  AA = &getAnalysis<AAResultsWrapperPass>().getAAResults();
-  SE = &getAnalysis<ScalarEvolutionWrapperPass>().getSE();
-  LI = &getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
+bool DependenceAnalysisWrapperPass::runOnFunction(Function &F) {
+  auto &AA = getAnalysis<AAResultsWrapperPass>().getAAResults();
+  auto &SE = getAnalysis<ScalarEvolutionWrapperPass>().getSE();
+  auto &LI = getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
+  info.reset(new DependenceInfo(&F, &AA, &SE, &LI));
   return false;
 }
 
+DependenceInfo &DependenceAnalysisWrapperPass::getDI() const { return *info; }
 
-void DependenceAnalysis::releaseMemory() {
-}
-
+void DependenceAnalysisWrapperPass::releaseMemory() { info.reset(); }
 
-void DependenceAnalysis::getAnalysisUsage(AnalysisUsage &AU) const {
+void DependenceAnalysisWrapperPass::getAnalysisUsage(AnalysisUsage &AU) const {
   AU.setPreservesAll();
   AU.addRequiredTransitive<AAResultsWrapperPass>();
   AU.addRequiredTransitive<ScalarEvolutionWrapperPass>();
   AU.addRequiredTransitive<LoopInfoWrapperPass>();
 }
 
 
 // Used to test the dependence analyzer.
 // Looks through the function, noting loads and stores.
 // Calls depends() on every possible pair and prints out the result.
 // Ignores all other instructions.
-static
-void dumpExampleDependence(raw_ostream &OS, Function *F,
-                           DependenceAnalysis *DA) {
-  for (inst_iterator SrcI = inst_begin(F), SrcE = inst_end(F);
-       SrcI != SrcE; ++SrcI) {
+static void dumpExampleDependence(raw_ostream &OS, DependenceInfo *DA) {
+  auto *F = DA->getFunction();
+  for (inst_iterator SrcI = inst_begin(F), SrcE = inst_end(F); SrcI != SrcE;
+       ++SrcI) {
     if (isa<StoreInst>(*SrcI) || isa<LoadInst>(*SrcI)) {
       for (inst_iterator DstI = SrcI, DstE = inst_end(F);
            DstI != DstE; ++DstI) {
         if (isa<StoreInst>(*DstI) || isa<LoadInst>(*DstI)) {
           OS << "da analyze - ";
           if (auto D = DA->depends(&*SrcI, &*DstI, true)) {
             D->dump(OS);
             for (unsigned Level = 1; Level <= D->getLevels(); Level++) {
               if (D->isSplitable(Level)) {
                 OS << "da analyze - split level = " << Level;
                 OS << ", iteration = " << *DA->getSplitIteration(*D, Level);
                 OS << "!\n";
               }
             }
           }
           else
             OS << "none!\n";
         }
       }
     }
   }
 }
 
-
-void DependenceAnalysis::print(raw_ostream &OS, const Module*) const {
-  dumpExampleDependence(OS, F, const_cast<DependenceAnalysis *>(this));
+void DependenceAnalysisWrapperPass::print(raw_ostream &OS,
+                                          const Module *) const {
+  dumpExampleDependence(OS, info.get());
 }
 
 //===----------------------------------------------------------------------===//
 // Dependence methods
 
 // Returns true if this is an input dependence.
 bool Dependence::isInput() const {
   return Src->mayReadFromMemory() && Dst->mayReadFromMemory();

 // Returns true if splitting this loop will break the dependence.
 bool FullDependence::isSplitable(unsigned Level) const {
   assert(0 < Level && Level <= Levels && "Level out of range");
   return DV[Level - 1].Splitable;
 }
 
 
 //===----------------------------------------------------------------------===//
-// DependenceAnalysis::Constraint methods
+// DependenceInfo::Constraint methods
 
 // If constraint is a point <X, Y>, returns X.
 // Otherwise assert.
-const SCEV *DependenceAnalysis::Constraint::getX() const {
+const SCEV *DependenceInfo::Constraint::getX() const {
   assert(Kind == Point && "Kind should be Point");
   return A;
 }
 
 
 // If constraint is a point <X, Y>, returns Y.
 // Otherwise assert.
-const SCEV *DependenceAnalysis::Constraint::getY() const {
+const SCEV *DependenceInfo::Constraint::getY() const {
   assert(Kind == Point && "Kind should be Point");
   return B;
 }
 
 
 // If constraint is a line AX + BY = C, returns A.
 // Otherwise assert.
-const SCEV *DependenceAnalysis::Constraint::getA() const {
+const SCEV *DependenceInfo::Constraint::getA() const {
   assert((Kind == Line || Kind == Distance) &&
          "Kind should be Line (or Distance)");
   return A;
 }
 
 
 // If constraint is a line AX + BY = C, returns B.
 // Otherwise assert.
-const SCEV *DependenceAnalysis::Constraint::getB() const {
+const SCEV *DependenceInfo::Constraint::getB() const {
   assert((Kind == Line || Kind == Distance) &&
          "Kind should be Line (or Distance)");
   return B;
 }
 
 
 // If constraint is a line AX + BY = C, returns C.
 // Otherwise assert.
-const SCEV *DependenceAnalysis::Constraint::getC() const {
+const SCEV *DependenceInfo::Constraint::getC() const {
   assert((Kind == Line || Kind == Distance) &&
          "Kind should be Line (or Distance)");
   return C;
 }
 
 
 // If constraint is a distance, returns D.
 // Otherwise assert.
-const SCEV *DependenceAnalysis::Constraint::getD() const {
+const SCEV *DependenceInfo::Constraint::getD() const {
   assert(Kind == Distance && "Kind should be Distance");
   return SE->getNegativeSCEV(C);
 }
 
 
 // Returns the loop associated with this constraint.
-const Loop *DependenceAnalysis::Constraint::getAssociatedLoop() const {
+const Loop *DependenceInfo::Constraint::getAssociatedLoop() const {
   assert((Kind == Distance || Kind == Line || Kind == Point) &&
          "Kind should be Distance, Line, or Point");
   return AssociatedLoop;
 }
 
-
-void DependenceAnalysis::Constraint::setPoint(const SCEV *X,
-                                              const SCEV *Y,
-                                              const Loop *CurLoop) {
+void DependenceInfo::Constraint::setPoint(const SCEV *X, const SCEV *Y,
   Kind = Point;
   A = X;
   B = Y;
   AssociatedLoop = CurLoop;
 }
 
-
-void DependenceAnalysis::Constraint::setLine(const SCEV *AA,
-                                             const SCEV *BB,
-                                             const SCEV *CC,
-                                             const Loop *CurLoop) {
+void DependenceInfo::Constraint::setLine(const SCEV *AA, const SCEV *BB,
+                                         const SCEV *CC, const Loop *CurLoop) {
   Kind = Line;
   A = AA;
   B = BB;
   C = CC;
   AssociatedLoop = CurLoop;
 }
 
-
-void DependenceAnalysis::Constraint::setDistance(const SCEV *D,
-                                                 const Loop *CurLoop) {
+void DependenceInfo::Constraint::setDistance(const SCEV *D,
   Kind = Distance;
   A = SE->getOne(D->getType());
   B = SE->getNegativeSCEV(A);
   C = SE->getNegativeSCEV(D);
   AssociatedLoop = CurLoop;
 }
 
+void DependenceInfo::Constraint::setEmpty() { Kind = Empty; }
 
-void DependenceAnalysis::Constraint::setEmpty() {
-  Kind = Empty;
-}
-
-
-void DependenceAnalysis::Constraint::setAny(ScalarEvolution *NewSE) {
+void DependenceInfo::Constraint::setAny(ScalarEvolution *NewSE) {
   SE = NewSE;
   Kind = Any;
 }
 
 
 // For debugging purposes. Dumps the constraint out to OS.
-void DependenceAnalysis::Constraint::dump(raw_ostream &OS) const {
+void DependenceInfo::Constraint::dump(raw_ostream &OS) const {
   if (isEmpty())
     OS << " Empty\n";
   else if (isAny())
     OS << " Any\n";
   else if (isPoint())
     OS << " Point is <" << *getX() << ", " << *getY() << ">\n";
   else if (isDistance())
     OS << " Distance is " << *getD() <<
       " (" << *getA() << "*X + " << *getB() << "*Y = " << *getC() << ")\n";
   else if (isLine())
     OS << " Line is " << *getA() << "*X + " <<
       *getB() << "*Y = " << *getC() << "\n";
   else
     llvm_unreachable("unknown constraint type in Constraint::dump");
 }
 
 
 // Updates X with the intersection
 // of the Constraints X and Y. Returns true if X has changed.
 // Corresponds to Figure 4 from the paper
 //
 //            Practical Dependence Testing
 //            Goff, Kennedy, Tseng
 //            PLDI 1991
-bool DependenceAnalysis::intersectConstraints(Constraint *X,
-                                              const Constraint *Y) {
+bool DependenceInfo::intersectConstraints(Constraint *X, const Constraint *Y) {
   ++DeltaApplications;
   DEBUG(dbgs() << "\tintersect constraints\n");
   DEBUG(dbgs() << "\t    X ="; X->dump(dbgs()));
   DEBUG(dbgs() << "\t    Y ="; Y->dump(dbgs()));
   assert(!Y->isPoint() && "Y must not be a Point");
   if (X->isAny()) {
     if (Y->isAny())
       return false;
bool DependenceInfo::intersectConstraints(Constraint *X, const Constraint *Y) {
   }
 
   llvm_unreachable("shouldn't reach the end of Constraint intersection");
   return false;
 }
 
 
 //===----------------------------------------------------------------------===//
-// DependenceAnalysis methods
+// DependenceInfo methods
 
 // For debugging purposes. Dumps a dependence to OS.
 void Dependence::dump(raw_ostream &OS) const {
   bool Splitable = false;
   if (isConfused())
     OS << "confused";
   else {
     if (isConsistent())

 // A map from loop names to loop numbers would look like
 //     a - 1
 //     b - 2 = CommonLevels
 //     c - 3
 //     d - 4 = SrcLevels
 //     e - 5
 //     f - 6
 //     g - 7 = MaxLevels
-void DependenceAnalysis::establishNestingLevels(const Instruction *Src,
-                                                const Instruction *Dst) {
+void DependenceInfo::establishNestingLevels(const Instruction *Src,
   const BasicBlock *SrcBlock = Src->getParent();
   const BasicBlock *DstBlock = Dst->getParent();
   unsigned SrcLevel = LI->getLoopDepth(SrcBlock);
   unsigned DstLevel = LI->getLoopDepth(DstBlock);
   const Loop *SrcLoop = LI->getLoopFor(SrcBlock);
   const Loop *DstLoop = LI->getLoopFor(DstBlock);
   SrcLevels = SrcLevel;
   MaxLevels = SrcLevel + DstLevel;
void DependenceInfo::establishNestingLevels(const Instruction *Src,
   }
   CommonLevels = SrcLevel;
   MaxLevels -= CommonLevels;
 }
 
 
 // Given one of the loops containing the source, return
 // its level index in our numbering scheme.
-unsigned DependenceAnalysis::mapSrcLoop(const Loop *SrcLoop) const {
+unsigned DependenceInfo::mapSrcLoop(const Loop *SrcLoop) const {
   return SrcLoop->getLoopDepth();
 }
 
 
 // Given one of the loops containing the destination,
 // return its level index in our numbering scheme.
-unsigned DependenceAnalysis::mapDstLoop(const Loop *DstLoop) const {
+unsigned DependenceInfo::mapDstLoop(const Loop *DstLoop) const {
   unsigned D = DstLoop->getLoopDepth();
   if (D > CommonLevels)
     return D - CommonLevels + SrcLevels;
   else
     return D;
 }
 
 
 // Returns true if Expression is loop invariant in LoopNest.
-bool DependenceAnalysis::isLoopInvariant(const SCEV *Expression,
-                                         const Loop *LoopNest) const {
+bool DependenceInfo::isLoopInvariant(const SCEV *Expression,
   if (!LoopNest)
     return true;
   return SE->isLoopInvariant(Expression, LoopNest) &&
     isLoopInvariant(Expression, LoopNest->getParentLoop());
 }
 
 
 
 // Finds the set of loops from the LoopNest that
 // have a level <= CommonLevels and are referred to by the SCEV Expression.
-void DependenceAnalysis::collectCommonLoops(const SCEV *Expression,
-                                            const Loop *LoopNest,
-                                            SmallBitVector &Loops) const {
+void DependenceInfo::collectCommonLoops(const SCEV *Expression,
   while (LoopNest) {
     unsigned Level = LoopNest->getLoopDepth();
     if (Level <= CommonLevels && !SE->isLoopInvariant(Expression, LoopNest))
       Loops.set(Level);
     LoopNest = LoopNest->getParentLoop();
   }
 }
 
-void DependenceAnalysis::unifySubscriptType(ArrayRef<Subscript *> Pairs) {
+void DependenceInfo::unifySubscriptType(ArrayRef<Subscript *> Pairs) {
 
   unsigned widestWidthSeen = 0;
   Type *widestType;
 
   // Go through each pair and find the widest bit to which we need
   // to extend all of them.
   for (unsigned i = 0; i < Pairs.size(); i++) {
     const SCEV *Src = Pairs[i]->Src;
for (unsigned i = 0; i < Pairs.size(); i++) {
     }
   }
 }
 
 // removeMatchingExtensions - Examines a subscript pair.
 // If the source and destination are identically sign (or zero)
 // extended, it strips off the extension in an effect to simplify
 // the actual analysis.
-void DependenceAnalysis::removeMatchingExtensions(Subscript *Pair) {
+void DependenceInfo::removeMatchingExtensions(Subscript *Pair) {
   const SCEV *Src = Pair->Src;
   const SCEV *Dst = Pair->Dst;
   if ((isa<SCEVZeroExtendExpr>(Src) && isa<SCEVZeroExtendExpr>(Dst)) ||
       (isa<SCEVSignExtendExpr>(Src) && isa<SCEVSignExtendExpr>(Dst))) {
     const SCEVCastExpr *SrcCast = cast<SCEVCastExpr>(Src);
     const SCEVCastExpr *DstCast = cast<SCEVCastExpr>(Dst);
     const SCEV *SrcCastOp = SrcCast->getOperand();
     const SCEV *DstCastOp = DstCast->getOperand();
     if (SrcCastOp->getType() == DstCastOp->getType()) {
       Pair->Src = SrcCastOp;
       Pair->Dst = DstCastOp;
     }
   }
 }
 
 
 // Examine the scev and return true iff it's linear.
 // Collect any loops mentioned in the set of "Loops".
-bool DependenceAnalysis::checkSrcSubscript(const SCEV *Src,
-                                           const Loop *LoopNest,
-                                           SmallBitVector &Loops) {
+bool DependenceInfo::checkSrcSubscript(const SCEV *Src, const Loop *LoopNest,
   const SCEVAddRecExpr *AddRec = dyn_cast<SCEVAddRecExpr>(Src);
   if (!AddRec)
     return isLoopInvariant(Src, LoopNest);
   const SCEV *Start = AddRec->getStart();
   const SCEV *Step = AddRec->getStepRecurrence(*SE);
   const SCEV *UB = SE->getBackedgeTakenCount(AddRec->getLoop());
   if (!isa<SCEVCouldNotCompute>(UB)) {
     if (SE->getTypeSizeInBits(Start->getType()) <
         SE->getTypeSizeInBits(UB->getType())) {
       if (!AddRec->getNoWrapFlags())
         return false;
     }
   }
   if (!isLoopInvariant(Step, LoopNest))
     return false;
   Loops.set(mapSrcLoop(AddRec->getLoop()));
   return checkSrcSubscript(Start, LoopNest, Loops);
 }
 
 
 
 // Examine the scev and return true iff it's linear.
 // Collect any loops mentioned in the set of "Loops".
-bool DependenceAnalysis::checkDstSubscript(const SCEV *Dst,
-                                           const Loop *LoopNest,
-                                           SmallBitVector &Loops) {
+bool DependenceInfo::checkDstSubscript(const SCEV *Dst, const Loop *LoopNest,
   const SCEVAddRecExpr *AddRec = dyn_cast<SCEVAddRecExpr>(Dst);
   if (!AddRec)
     return isLoopInvariant(Dst, LoopNest);
   const SCEV *Start = AddRec->getStart();
   const SCEV *Step = AddRec->getStepRecurrence(*SE);
   const SCEV *UB = SE->getBackedgeTakenCount(AddRec->getLoop());
   if (!isa<SCEVCouldNotCompute>(UB)) {
     if (SE->getTypeSizeInBits(Start->getType()) <
         SE->getTypeSizeInBits(UB->getType())) {
       if (!AddRec->getNoWrapFlags())
         return false;
     }
   }
   if (!isLoopInvariant(Step, LoopNest))
     return false;
   Loops.set(mapDstLoop(AddRec->getLoop()));
   return checkDstSubscript(Start, LoopNest, Loops);
 }
 
 
 // Examines the subscript pair (the Src and Dst SCEVs)
 // and classifies it as either ZIV, SIV, RDIV, MIV, or Nonlinear.
 // Collects the associated loops in a set.
-DependenceAnalysis::Subscript::ClassificationKind
-DependenceAnalysis::classifyPair(const SCEV *Src, const Loop *SrcLoopNest,
-                                 const SCEV *Dst, const Loop *DstLoopNest,
-                                 SmallBitVector &Loops) {
+DependenceInfo::Subscript::ClassificationKind
+DependenceInfo::classifyPair(const SCEV *Src, const Loop *SrcLoopNest,
   SmallBitVector SrcLoops(MaxLevels + 1);
   SmallBitVector DstLoops(MaxLevels + 1);
   if (!checkSrcSubscript(Src, SrcLoopNest, SrcLoops))
     return Subscript::NonLinear;
   if (!checkDstSubscript(Dst, DstLoopNest, DstLoops))
     return Subscript::NonLinear;
   Loops = SrcLoops;
   Loops |= DstLoops;

 // If both X and Y have been identically sign or zero extended,
 // it strips off the (confusing) extensions before invoking
 // SCEV::isKnownPredicate. Perhaps, someday, the ScalarEvolution package
 // will be similarly updated.
 //
 // If SCEV::isKnownPredicate can't prove the predicate,
 // we try simple subtraction, which seems to help in some cases
 // involving symbolics.
-bool DependenceAnalysis::isKnownPredicate(ICmpInst::Predicate Pred,
-                                          const SCEV *X,
-                                          const SCEV *Y) const {
+bool DependenceInfo::isKnownPredicate(ICmpInst::Predicate Pred, const SCEV *X,
   if (Pred == CmpInst::ICMP_EQ ||
       Pred == CmpInst::ICMP_NE) {
     if ((isa<SCEVSignExtendExpr>(X) &&
          isa<SCEVSignExtendExpr>(Y)) ||
         (isa<SCEVZeroExtendExpr>(X) &&
          isa<SCEVZeroExtendExpr>(Y))) {
       const SCEVCastExpr *CX = cast<SCEVCastExpr>(X);
       const SCEVCastExpr *CY = cast<SCEVCastExpr>(Y);

 
 // All subscripts are all the same type.
 // Loop bound may be smaller (e.g., a char).
 // Should zero extend loop bound, since it's always >= 0.
 // This routine collects upper bound and extends or truncates if needed.
 // Truncating is safe when subscripts are known not to wrap. Cases without
 // nowrap flags should have been rejected earlier.
 // Return null if no bound available.
-const SCEV *DependenceAnalysis::collectUpperBound(const Loop *L,
-                                                  Type *T) const {
+const SCEV *DependenceInfo::collectUpperBound(const Loop *L, Type *T) const {
   if (SE->hasLoopInvariantBackedgeTakenCount(L)) {
     const SCEV *UB = SE->getBackedgeTakenCount(L);
     return SE->getTruncateOrZeroExtend(UB, T);
   }
   return nullptr;
 }
 
 
 // Calls collectUpperBound(), then attempts to cast it to SCEVConstant.
 // If the cast fails, returns NULL.
-const SCEVConstant *DependenceAnalysis::collectConstantUpperBound(const Loop *L,
-                                                                  Type *T
-                                                                  ) const {
+const SCEVConstant *DependenceInfo::collectConstantUpperBound(const Loop *L,
+                                                              Type *T) const {
   if (const SCEV *UB = collectUpperBound(L, T))
     return dyn_cast<SCEVConstant>(UB);
   return nullptr;
 }
 
 
 // testZIV -
 // When we have a pair of subscripts of the form [c1] and [c2],
 // where c1 and c2 are both loop invariant, we attack it using
 // the ZIV test. Basically, we test by comparing the two values,
 // but there are actually three possible results:
 // 1) the values are equal, so there's a dependence
 // 2) the values are different, so there's no dependence
 // 3) the values might be equal, so we have to assume a dependence.
 //
 // Return true if dependence disproved.
-bool DependenceAnalysis::testZIV(const SCEV *Src,
-                                 const SCEV *Dst,
-                                 FullDependence &Result) const {
+bool DependenceInfo::testZIV(const SCEV *Src, const SCEV *Dst,
   DEBUG(dbgs() << "    src = " << *Src << "\n");
   DEBUG(dbgs() << "    dst = " << *Dst << "\n");
   ++ZIVapplications;
   if (isKnownPredicate(CmpInst::ICMP_EQ, Src, Dst)) {
     DEBUG(dbgs() << "    provably dependent\n");
     return false; // provably dependent
   }
   if (isKnownPredicate(CmpInst::ICMP_NE, Src, Dst)) {

 // loop's upper bound. If a dependence exists, the dependence direction is
 // defined as
 //
 //                { < if d > 0
 //    direction = { = if d = 0
 //                { > if d < 0
 //
 // Return true if dependence disproved.
-bool DependenceAnalysis::strongSIVtest(const SCEV *Coeff,
-                                       const SCEV *SrcConst,
-                                       const SCEV *DstConst,
-                                       const Loop *CurLoop,
-                                       unsigned Level,
-                                       FullDependence &Result,
-                                       Constraint &NewConstraint) const {
+bool DependenceInfo::strongSIVtest(const SCEV *Coeff, const SCEV *SrcConst,
+                                   const SCEV *DstConst, const Loop *CurLoop,
+                                   unsigned Level, FullDependence &Result,
   DEBUG(dbgs() << "\tStrong SIV test\n");
   DEBUG(dbgs() << "\t    Coeff = " << *Coeff);
   DEBUG(dbgs() << ", " << *Coeff->getType() << "\n");
   DEBUG(dbgs() << "\t    SrcConst = " << *SrcConst);
   DEBUG(dbgs() << ", " << *SrcConst->getType() << "\n");
   DEBUG(dbgs() << "\t    DstConst = " << *DstConst);
   DEBUG(dbgs() << ", " << *DstConst->getType() << "\n");
   ++StrongSIVapplications;

 // If the non-integer part = 1/2, there's a dependence (<> directions).
 // Otherwise, there's no dependence.
 //
 // Can prove independence. Failing that,
 // can sometimes refine the directions.
 // Can determine iteration for splitting.
 //
 // Return true if dependence disproved.
-bool DependenceAnalysis::weakCrossingSIVtest(const SCEV *Coeff,
-                                             const SCEV *SrcConst,
-                                             const SCEV *DstConst,
-                                             const Loop *CurLoop,
-                                             unsigned Level,
-                                             FullDependence &Result,
-                                             Constraint &NewConstraint,
-                                             const SCEV *&SplitIter) const {
+bool DependenceInfo::weakCrossingSIVtest(
+    const SCEV *Coeff, const SCEV *SrcConst, const SCEV *DstConst,
+    const Loop *CurLoop, unsigned Level, FullDependence &Result,
+    Constraint &NewConstraint, const SCEV *&SplitIter) const {
   DEBUG(dbgs() << "\tWeak-Crossing SIV test\n");
   DEBUG(dbgs() << "\t    Coeff = " << *Coeff << "\n");
   DEBUG(dbgs() << "\t    SrcConst = " << *SrcConst << "\n");
   DEBUG(dbgs() << "\t    DstConst = " << *DstConst << "\n");
   ++WeakCrossingSIVapplications;
   assert(0 < Level && Level <= CommonLevels && "Level out of range");
   Level--;
   Result.Consistent = false;
bool DependenceInfo::weakCrossingSIVtest(
   if (SE->isKnownNegative(ConstCoeff)) {
     ConstCoeff = dyn_cast<SCEVConstant>(SE->getNegativeSCEV(ConstCoeff));
     assert(ConstCoeff &&
            "dynamic cast of negative of ConstCoeff should yield constant");
     Delta = SE->getNegativeSCEV(Delta);
   }
   assert(SE->isKnownPositive(ConstCoeff) && "ConstCoeff should be positive");
 
-  // compute SplitIter for use by DependenceAnalysis::getSplitIteration()
+  // compute SplitIter for use by DependenceInfo::getSplitIteration()
   SplitIter = SE->getUDivExpr(
       SE->getSMaxExpr(SE->getZero(Delta->getType()), Delta),
       SE->getMulExpr(SE->getConstant(Delta->getType(), 2), ConstCoeff));
   DEBUG(dbgs() << "\t    Split iter = " << *SplitIter << "\n");
 
   const SCEVConstant *ConstDelta = dyn_cast<SCEVConstant>(Delta);
   if (!ConstDelta)
     return false;

 //        Michael Wolfe
 //        MIT Press, 1989
 //
 // It's slower than the specialized tests (strong SIV, weak-zero SIV, etc),
 // so use them if possible. They're also a bit better with symbolics and,
 // in the case of the strong SIV test, can compute Distances.
 //
 // Return true if dependence disproved.
-bool DependenceAnalysis::exactSIVtest(const SCEV *SrcCoeff,
-                                      const SCEV *DstCoeff,
-                                      const SCEV *SrcConst,
-                                      const SCEV *DstConst,
-                                      const Loop *CurLoop,
-                                      unsigned Level,
-                                      FullDependence &Result,
-                                      Constraint &NewConstraint) const {
+bool DependenceInfo::exactSIVtest(const SCEV *SrcCoeff, const SCEV *DstCoeff,
+                                  const SCEV *SrcConst, const SCEV *DstConst,
+                                  const Loop *CurLoop, unsigned Level,
   DEBUG(dbgs() << "\tExact SIV test\n");
   DEBUG(dbgs() << "\t    SrcCoeff = " << *SrcCoeff << " = AM\n");
   DEBUG(dbgs() << "\t    DstCoeff = " << *DstCoeff << " = BM\n");
   DEBUG(dbgs() << "\t    SrcConst = " << *SrcConst << "\n");
   DEBUG(dbgs() << "\t    DstConst = " << *DstConst << "\n");
   ++ExactSIVapplications;
   assert(0 < Level && Level <= CommonLevels && "Level out of range");
   Level--;

 //
 // Can prove independence. Failing that, we can sometimes refine
 // the directions. Can sometimes show that first or last
 // iteration carries all the dependences (so worth peeling).
 //
 // (see also weakZeroDstSIVtest)
 //
 // Return true if dependence disproved.
-bool DependenceAnalysis::weakZeroSrcSIVtest(const SCEV *DstCoeff,
-                                            const SCEV *SrcConst,
-                                            const SCEV *DstConst,
-                                            const Loop *CurLoop,
-                                            unsigned Level,
-                                            FullDependence &Result,
-                                            Constraint &NewConstraint) const {
+bool DependenceInfo::weakZeroSrcSIVtest(const SCEV *DstCoeff,
+                                        const Loop *CurLoop, unsigned Level,
   // For the WeakSIV test, it's possible the loop isn't common to
   // the Src and Dst loops. If it isn't, then there's no need to
   // record a direction.
   DEBUG(dbgs() << "\tWeak-Zero (src) SIV test\n");
   DEBUG(dbgs() << "\t    DstCoeff = " << *DstCoeff << "\n");
   DEBUG(dbgs() << "\t    SrcConst = " << *SrcConst << "\n");
   DEBUG(dbgs() << "\t    DstConst = " << *DstConst << "\n");
   ++WeakZeroSIVapplications;

 //
 // Can prove independence. Failing that, we can sometimes refine
 // the directions. Can sometimes show that first or last
 // iteration carries all the dependences (so worth peeling).
 //
 // (see also weakZeroSrcSIVtest)
 //
 // Return true if dependence disproved.
-bool DependenceAnalysis::weakZeroDstSIVtest(const SCEV *SrcCoeff,
-                                            const SCEV *SrcConst,
-                                            const SCEV *DstConst,
-                                            const Loop *CurLoop,
-                                            unsigned Level,
-                                            FullDependence &Result,
-                                            Constraint &NewConstraint) const {
+bool DependenceInfo::weakZeroDstSIVtest(const SCEV *SrcCoeff,
+                                        const Loop *CurLoop, unsigned Level,
   // For the WeakSIV test, it's possible the loop isn't common to the
   // Src and Dst loops. If it isn't, then there's no need to record a direction.
   DEBUG(dbgs() << "\tWeak-Zero (dst) SIV test\n");
   DEBUG(dbgs() << "\t    SrcCoeff = " << *SrcCoeff << "\n");
   DEBUG(dbgs() << "\t    SrcConst = " << *SrcConst << "\n");
   DEBUG(dbgs() << "\t    DstConst = " << *DstConst << "\n");
   ++WeakZeroSIVapplications;
   assert(0 < Level && Level <= SrcLevels && "Level out of range");

 
 // exactRDIVtest - Tests the RDIV subscript pair for dependence.
 // Things of the form [c1 + a*i] and [c2 + b*j],
 // where i and j are induction variable, c1 and c2 are loop invariant,
 // and a and b are constants.
 // Returns true if any possible dependence is disproved.
 // Marks the result as inconsistent.
 // Works in some cases that symbolicRDIVtest doesn't, and vice versa.
-bool DependenceAnalysis::exactRDIVtest(const SCEV *SrcCoeff,
-                                       const SCEV *DstCoeff,
-                                       const SCEV *SrcConst,
-                                       const SCEV *DstConst,
-                                       const Loop *SrcLoop,
-                                       const Loop *DstLoop,
-                                       FullDependence &Result) const {
+bool DependenceInfo::exactRDIVtest(const SCEV *SrcCoeff, const SCEV *DstCoeff,
+                                   const SCEV *SrcConst, const SCEV *DstConst,
+                                   const Loop *SrcLoop, const Loop *DstLoop,
   DEBUG(dbgs() << "\tExact RDIV test\n");
   DEBUG(dbgs() << "\t    SrcCoeff = " << *SrcCoeff << " = AM\n");
   DEBUG(dbgs() << "\t    DstCoeff = " << *DstCoeff << " = BM\n");
   DEBUG(dbgs() << "\t    SrcConst = " << *SrcConst << "\n");
   DEBUG(dbgs() << "\t    DstConst = " << *DstConst << "\n");
   ++ExactRDIVapplications;
   Result.Consistent = false;
   const SCEV *Delta = SE->getMinusSCEV(DstConst, SrcConst);

 //        a1*N1 - a2*N2 <= c2 - c1 <= a1*0 - a2*0
 //        a1*N1 - a2*N2 <= c2 - c1 <= 0
 //
 // 4) If a1 <= 0 and a2 <= 0, then
 //        a1*N1 - a2*0  <= c2 - c1 <= a1*0 - a2*N2
 //        a1*N1         <= c2 - c1 <=       -a2*N2
 //
 // return true if dependence disproved
-bool DependenceAnalysis::symbolicRDIVtest(const SCEV *A1,
-                                          const SCEV *A2,
-                                          const SCEV *C1,
-                                          const SCEV *C2,
-                                          const Loop *Loop1,
-                                          const Loop *Loop2) const {
+bool DependenceInfo::symbolicRDIVtest(const SCEV *A1, const SCEV *A2,
+                                      const SCEV *C1, const SCEV *C2,
   ++SymbolicRDIVapplications;
   DEBUG(dbgs() << "\ttry symbolic RDIV test\n");
   DEBUG(dbgs() << "\t    A1 = " << *A1);
   DEBUG(dbgs() << ", type = " << *A1->getType() << "\n");
   DEBUG(dbgs() << "\t    A2 = " << *A2 << "\n");
   DEBUG(dbgs() << "\t    C1 = " << *C1 << "\n");
   DEBUG(dbgs() << "\t    C2 = " << *C2 << "\n");
   const SCEV *N1 = collectUpperBound(Loop1, A1->getType());

 // testSIV -
 // When we have a pair of subscripts of the form [c1 + a1*i] and [c2 - a2*i]
 // where i is an induction variable, c1 and c2 are loop invariant, and a1 and
 // a2 are constant, we attack it with an SIV test. While they can all be
 // solved with the Exact SIV test, it's worthwhile to use simpler tests when
 // they apply; they're cheaper and sometimes more precise.
 //
 // Return true if dependence disproved.
-bool DependenceAnalysis::testSIV(const SCEV *Src,
-                                 const SCEV *Dst,
-                                 unsigned &Level,
-                                 FullDependence &Result,
-                                 Constraint &NewConstraint,
-                                 const SCEV *&SplitIter) const {
+bool DependenceInfo::testSIV(const SCEV *Src, const SCEV *Dst, unsigned &Level,
+                             FullDependence &Result, Constraint &NewConstraint,
   DEBUG(dbgs() << "    src = " << *Src << "\n");
   DEBUG(dbgs() << "    dst = " << *Dst << "\n");
   const SCEVAddRecExpr *SrcAddRec = dyn_cast<SCEVAddRecExpr>(Src);
   const SCEVAddRecExpr *DstAddRec = dyn_cast<SCEVAddRecExpr>(Dst);
   if (SrcAddRec && DstAddRec) {
     const SCEV *SrcConst = SrcAddRec->getStart();
     const SCEV *DstConst = DstAddRec->getStart();
     const SCEV *SrcCoeff = SrcAddRec->getStepRecurrence(*SE);

 // It doesn't make sense to talk about distance or direction in this case,
 // so there's no point in making special versions of the Strong SIV test or
 // the Weak-crossing SIV test.
 //
 // With minor algebra, this test can also be used for things like
 // [c1 + a1*i + a2*j][c2].
 //
 // Return true if dependence disproved.
-bool DependenceAnalysis::testRDIV(const SCEV *Src,
-                                  const SCEV *Dst,
-                                  FullDependence &Result) const {
+bool DependenceInfo::testRDIV(const SCEV *Src, const SCEV *Dst,
   // we have 3 possible situations here:
   //   1) [a*i + b] and [c*j + d]
   //   2) [a*i + c*j + b] and [d]
   //   3) [b] and [a*i + c*j + d]
   // We need to find what we've got and get organized
 
   const SCEV *SrcConst, *DstConst;
   const SCEV *SrcCoeff, *DstCoeff;
symbolicRDIVtest(SrcCoeff, DstCoeff,
                      SrcConst, DstConst,
                      SrcLoop, DstLoop);
 }
 
 
 // Tests the single-subscript MIV pair (Src and Dst) for dependence.
 // Return true if dependence disproved.
 // Can sometimes refine direction vectors.
-bool DependenceAnalysis::testMIV(const SCEV *Src,
-                                 const SCEV *Dst,
-                                 const SmallBitVector &Loops,
-                                 FullDependence &Result) const {
+bool DependenceInfo::testMIV(const SCEV *Src, const SCEV *Dst,
   DEBUG(dbgs() << "    src = " << *Src << "\n");
   DEBUG(dbgs() << "    dst = " << *Dst << "\n");
   Result.Consistent = false;
   return gcdMIVtest(Src, Dst, Result) ||
     banerjeeMIVtest(Src, Dst, Loops, Result);
 }
 
 

 // [10*i + 5*N*j + 15*M + 6], where i and j are induction variables,
 // but M and N are just loop-invariant variables.
 // This should help us handle linearized subscripts;
 // also makes this test a useful backup to the various SIV tests.
 //
 // It occurs to me that the presence of loop-invariant variables
 // changes the nature of the test from "greatest common divisor"
 // to "a common divisor".
-bool DependenceAnalysis::gcdMIVtest(const SCEV *Src,
-                                    const SCEV *Dst,
-                                    FullDependence &Result) const {
+bool DependenceInfo::gcdMIVtest(const SCEV *Src, const SCEV *Dst,
   DEBUG(dbgs() << "starting gcd\n");
   ++GCDapplications;
   unsigned BitWidth = SE->getTypeSizeInBits(Src->getType());
   APInt RunningGCD = APInt::getNullValue(BitWidth);
 
   // Examine Src coefficients.
   // Compute running GCD and record source constant.
   // Because we're looking for the constant at the end of the chain,

 // Similar simplifications are possible for the other equations.
 //
 // When we can't determine the number of iterations for a loop,
 // we use NULL as an indicator for the worst case, infinity.
 // When computing the upper bound, NULL denotes +inf;
 // for the lower bound, NULL denotes -inf.
 //
 // Return true if dependence disproved.
-bool DependenceAnalysis::banerjeeMIVtest(const SCEV *Src,
-                                         const SCEV *Dst,
-                                         const SmallBitVector &Loops,
-                                         FullDependence &Result) const {
+bool DependenceInfo::banerjeeMIVtest(const SCEV *Src, const SCEV *Dst,
   DEBUG(dbgs() << "starting Banerjee\n");
   ++BanerjeeApplications;
   DEBUG(dbgs() << "    Src = " << *Src << '\n');
   const SCEV *A0;
   CoefficientInfo *A = collectCoeffInfo(Src, true, A0);
   DEBUG(dbgs() << "    Dst = " << *Dst << '\n');
   const SCEV *B0;
   CoefficientInfo *B = collectCoeffInfo(Dst, false, B0);

 }
 
 
 // Hierarchically expands the direction vector
 // search space, combining the directions of discovered dependences
 // in the DirSet field of Bound. Returns the number of distinct
 // dependences discovered. If the dependence is disproved,
 // it will return 0.
-unsigned DependenceAnalysis::exploreDirections(unsigned Level,
-                                               CoefficientInfo *A,
-                                               CoefficientInfo *B,
-                                               BoundInfo *Bound,
-                                               const SmallBitVector &Loops,
-                                               unsigned &DepthExpanded,
-                                               const SCEV *Delta) const {
+unsigned DependenceInfo::exploreDirections(unsigned Level, CoefficientInfo *A,
+                                           CoefficientInfo *B, BoundInfo *Bound,
   if (Level > CommonLevels) {
     // record result
     DEBUG(dbgs() << "\t[");
     for (unsigned K = 1; K <= CommonLevels; ++K) {
       if (Loops[K]) {
         Bound[K].DirSet |= Bound[K].Direction;
 #ifndef NDEBUG
         switch (Bound[K].Direction) {
#endif
     return NewDeps;
   }
   else
     return exploreDirections(Level + 1, A, B, Bound, Loops, DepthExpanded, Delta);
 }
 
 
 // Returns true iff the current bounds are plausible.
-bool DependenceAnalysis::testBounds(unsigned char DirKind,
-                                    unsigned Level,
-                                    BoundInfo *Bound,
-                                    const SCEV *Delta) const {
+bool DependenceInfo::testBounds(unsigned char DirKind, unsigned Level,
+                                BoundInfo *Bound, const SCEV *Delta) const {
   Bound[Level].Direction = DirKind;
   if (const SCEV *LowerBound = getLowerBound(Bound))
     if (isKnownPredicate(CmpInst::ICMP_SGT, LowerBound, Delta))
       return false;
   if (const SCEV *UpperBound = getUpperBound(Bound))
     if (isKnownPredicate(CmpInst::ICMP_SGT, Delta, UpperBound))
       return false;
   return true;

 // Since we normalize loops, we can simplify these equations to
 //
 //    LB^*_k = (A^-_k - B^+_k)U_k
 //    UB^*_k = (A^+_k - B^-_k)U_k
 //
 // We must be careful to handle the case where the upper bound is unknown.
 // Note that the lower bound is always <= 0
 // and the upper bound is always >= 0.
-void DependenceAnalysis::findBoundsALL(CoefficientInfo *A,
-                                       CoefficientInfo *B,
-                                       BoundInfo *Bound,
-                                       unsigned K) const {
+void DependenceInfo::findBoundsALL(CoefficientInfo *A, CoefficientInfo *B,
+                                   BoundInfo *Bound, unsigned K) const {
   Bound[K].Lower[Dependence::DVEntry::ALL] = nullptr; // Default value = -infinity.
   Bound[K].Upper[Dependence::DVEntry::ALL] = nullptr; // Default value = +infinity.
   if (Bound[K].Iterations) {
     Bound[K].Lower[Dependence::DVEntry::ALL] =
       SE->getMulExpr(SE->getMinusSCEV(A[K].NegPart, B[K].PosPart),
                      Bound[K].Iterations);
     Bound[K].Upper[Dependence::DVEntry::ALL] =
       SE->getMulExpr(SE->getMinusSCEV(A[K].PosPart, B[K].NegPart),

 // Since we normalize loops, we can simplify these equations to
 //
 //    LB^=_k = (A_k - B_k)^- U_k
 //    UB^=_k = (A_k - B_k)^+ U_k
 //
 // We must be careful to handle the case where the upper bound is unknown.
 // Note that the lower bound is always <= 0
 // and the upper bound is always >= 0.
-void DependenceAnalysis::findBoundsEQ(CoefficientInfo *A,
-                                      CoefficientInfo *B,
-                                      BoundInfo *Bound,
-                                      unsigned K) const {
+void DependenceInfo::findBoundsEQ(CoefficientInfo *A, CoefficientInfo *B,
+                                  BoundInfo *Bound, unsigned K) const {
   Bound[K].Lower[Dependence::DVEntry::EQ] = nullptr; // Default value = -infinity.
   Bound[K].Upper[Dependence::DVEntry::EQ] = nullptr; // Default value = +infinity.
   if (Bound[K].Iterations) {
     const SCEV *Delta = SE->getMinusSCEV(A[K].Coeff, B[K].Coeff);
     const SCEV *NegativePart = getNegativePart(Delta);
     Bound[K].Lower[Dependence::DVEntry::EQ] =
       SE->getMulExpr(NegativePart, Bound[K].Iterations);
     const SCEV *PositivePart = getPositivePart(Delta);

 //    UB^<_k = (A^+_k - B_k)^+ (U_k - L_k - N_k) + (A_k - B_k)L_k - B_k N_k
 //
 // Since we normalize loops, we can simplify these equations to
 //
 //    LB^<_k = (A^-_k - B_k)^- (U_k - 1) - B_k
 //    UB^<_k = (A^+_k - B_k)^+ (U_k - 1) - B_k
 //
 // We must be careful to handle the case where the upper bound is unknown.
-void DependenceAnalysis::findBoundsLT(CoefficientInfo *A,
-                                      CoefficientInfo *B,
-                                      BoundInfo *Bound,
-                                      unsigned K) const {
+void DependenceInfo::findBoundsLT(CoefficientInfo *A, CoefficientInfo *B,
+                                  BoundInfo *Bound, unsigned K) const {
   Bound[K].Lower[Dependence::DVEntry::LT] = nullptr; // Default value = -infinity.
   Bound[K].Upper[Dependence::DVEntry::LT] = nullptr; // Default value = +infinity.
   if (Bound[K].Iterations) {
     const SCEV *Iter_1 = SE->getMinusSCEV(
         Bound[K].Iterations, SE->getOne(Bound[K].Iterations->getType()));
     const SCEV *NegPart =
       getNegativePart(SE->getMinusSCEV(A[K].NegPart, B[K].Coeff));
     Bound[K].Lower[Dependence::DVEntry::LT] =

 //    UB^>_k = (A_k - B^-_k)^+ (U_k - L_k - N_k) + (A_k - B_k)L_k + A_k N_k
 //
 // Since we normalize loops, we can simplify these equations to
 //
 //    LB^>_k = (A_k - B^+_k)^- (U_k - 1) + A_k
 //    UB^>_k = (A_k - B^-_k)^+ (U_k - 1) + A_k
 //
 // We must be careful to handle the case where the upper bound is unknown.
-void DependenceAnalysis::findBoundsGT(CoefficientInfo *A,
-                                      CoefficientInfo *B,
-                                      BoundInfo *Bound,
-                                      unsigned K) const {
+void DependenceInfo::findBoundsGT(CoefficientInfo *A, CoefficientInfo *B,
+                                  BoundInfo *Bound, unsigned K) const {
   Bound[K].Lower[Dependence::DVEntry::GT] = nullptr; // Default value = -infinity.
   Bound[K].Upper[Dependence::DVEntry::GT] = nullptr; // Default value = +infinity.
   if (Bound[K].Iterations) {
     const SCEV *Iter_1 = SE->getMinusSCEV(
         Bound[K].Iterations, SE->getOne(Bound[K].Iterations->getType()));
     const SCEV *NegPart =
       getNegativePart(SE->getMinusSCEV(A[K].Coeff, B[K].PosPart));
     Bound[K].Lower[Dependence::DVEntry::GT] =
else {
     const SCEV *PosPart = getPositivePart(SE->getMinusSCEV(A[K].Coeff, B[K].NegPart));
     if (PosPart->isZero())
       Bound[K].Upper[Dependence::DVEntry::GT] = A[K].Coeff;
   }
 }
 
 
 // X^+ = max(X, 0)
-const SCEV *DependenceAnalysis::getPositivePart(const SCEV *X) const {
+const SCEV *DependenceInfo::getPositivePart(const SCEV *X) const {
   return SE->getSMaxExpr(X, SE->getZero(X->getType()));
 }
 
 
 // X^- = min(X, 0)
-const SCEV *DependenceAnalysis::getNegativePart(const SCEV *X) const {
+const SCEV *DependenceInfo::getNegativePart(const SCEV *X) const {
   return SE->getSMinExpr(X, SE->getZero(X->getType()));
 }
 
 
 // Walks through the subscript,
 // collecting each coefficient, the associated loop bounds,
 // and recording its positive and negative parts for later use.
-DependenceAnalysis::CoefficientInfo *
-DependenceAnalysis::collectCoeffInfo(const SCEV *Subscript,
-                                     bool SrcFlag,
-                                     const SCEV *&Constant) const {
+DependenceInfo::CoefficientInfo *
+DependenceInfo::collectCoeffInfo(const SCEV *Subscript, bool SrcFlag,
   const SCEV *Zero = SE->getZero(Subscript->getType());
   CoefficientInfo *CI = new CoefficientInfo[MaxLevels + 1];
   for (unsigned K = 1; K <= MaxLevels; ++K) {
     CI[K].Coeff = Zero;
     CI[K].PosPart = Zero;
     CI[K].NegPart = Zero;
     CI[K].Iterations = nullptr;
   }
#endif
   return CI;
 }
 
 
 // Looks through all the bounds info and
 // computes the lower bound given the current direction settings
 // at each level. If the lower bound for any level is -inf,
 // the result is -inf.
-const SCEV *DependenceAnalysis::getLowerBound(BoundInfo *Bound) const {
+const SCEV *DependenceInfo::getLowerBound(BoundInfo *Bound) const {
   const SCEV *Sum = Bound[1].Lower[Bound[1].Direction];
   for (unsigned K = 2; Sum && K <= MaxLevels; ++K) {
     if (Bound[K].Lower[Bound[K].Direction])
       Sum = SE->getAddExpr(Sum, Bound[K].Lower[Bound[K].Direction]);
     else
       Sum = nullptr;
   }
   return Sum;
 }
 
 
 // Looks through all the bounds info and
 // computes the upper bound given the current direction settings
 // at each level. If the upper bound at any level is +inf,
 // the result is +inf.
-const SCEV *DependenceAnalysis::getUpperBound(BoundInfo *Bound) const {
+const SCEV *DependenceInfo::getUpperBound(BoundInfo *Bound) const {
   const SCEV *Sum = Bound[1].Upper[Bound[1].Direction];
   for (unsigned K = 2; Sum && K <= MaxLevels; ++K) {
     if (Bound[K].Upper[Bound[K].Direction])
       Sum = SE->getAddExpr(Sum, Bound[K].Upper[Bound[K].Direction]);
     else
       Sum = nullptr;
   }
   return Sum;
 }
 
 
 //===----------------------------------------------------------------------===//
 // Constraint manipulation for Delta test.
 
 // Given a linear SCEV,
 // return the coefficient (the step)
 // corresponding to the specified loop.
 // If there isn't one, return 0.
 // For example, given a*i + b*j + c*k, finding the coefficient
 // corresponding to the j loop would yield b.
-const SCEV *DependenceAnalysis::findCoefficient(const SCEV *Expr,
-                                                const Loop *TargetLoop)  const {
+const SCEV *DependenceInfo::findCoefficient(const SCEV *Expr,
+                                            const Loop *TargetLoop) const {
   const SCEVAddRecExpr *AddRec = dyn_cast<SCEVAddRecExpr>(Expr);
   if (!AddRec)
     return SE->getZero(Expr->getType());
   if (AddRec->getLoop() == TargetLoop)
     return AddRec->getStepRecurrence(*SE);
   return findCoefficient(AddRec->getStart(), TargetLoop);
 }
 
 
 // Given a linear SCEV,
 // return the SCEV given by zeroing out the coefficient
 // corresponding to the specified loop.
 // For example, given a*i + b*j + c*k, zeroing the coefficient
 // corresponding to the j loop would yield a*i + c*k.
-const SCEV *DependenceAnalysis::zeroCoefficient(const SCEV *Expr,
-                                                const Loop *TargetLoop)  const {
+const SCEV *DependenceInfo::zeroCoefficient(const SCEV *Expr,
+                                            const Loop *TargetLoop) const {
   const SCEVAddRecExpr *AddRec = dyn_cast<SCEVAddRecExpr>(Expr);
   if (!AddRec)
     return Expr; // ignore
   if (AddRec->getLoop() == TargetLoop)
     return AddRec->getStart();
   return SE->getAddRecExpr(zeroCoefficient(AddRec->getStart(), TargetLoop),
                            AddRec->getStepRecurrence(*SE),
                            AddRec->getLoop(),
                            AddRec->getNoWrapFlags());
 }
 
 
 // Given a linear SCEV Expr,
 // return the SCEV given by adding some Value to the
 // coefficient corresponding to the specified TargetLoop.
 // For example, given a*i + b*j + c*k, adding 1 to the coefficient
 // corresponding to the j loop would yield a*i + (b+1)*j + c*k.
-const SCEV *DependenceAnalysis::addToCoefficient(const SCEV *Expr,
-                                                 const Loop *TargetLoop,
-                                                 const SCEV *Value)  const {
+const SCEV *DependenceInfo::addToCoefficient(const SCEV *Expr,
+                                             const SCEV *Value) const {
   const SCEVAddRecExpr *AddRec = dyn_cast<SCEVAddRecExpr>(Expr);
   if (!AddRec) // create a new addRec
     return SE->getAddRecExpr(Expr,
                              Value,
                              TargetLoop,
                              SCEV::FlagAnyWrap); // Worst case, with no info.
   if (AddRec->getLoop() == TargetLoop) {
     const SCEV *Sum = SE->getAddExpr(AddRec->getStepRecurrence(*SE), Value);

 // Return true if some simplification occurs.
 // If the simplification isn't exact (that is, if it is conservative
 // in terms of dependence), set consistent to false.
 // Corresponds to Figure 5 from the paper
 //
 //            Practical Dependence Testing
 //            Goff, Kennedy, Tseng
 //            PLDI 1991
-bool DependenceAnalysis::propagate(const SCEV *&Src,
-                                   const SCEV *&Dst,
-                                   SmallBitVector &Loops,
-                                   SmallVectorImpl<Constraint> &Constraints,
-                                   bool &Consistent) {
+bool DependenceInfo::propagate(const SCEV *&Src, const SCEV *&Dst,
   bool Result = false;
   for (int LI = Loops.find_first(); LI >= 0; LI = Loops.find_next(LI)) {
     DEBUG(dbgs() << "\t    Constraint[" << LI << "] is");
     DEBUG(Constraints[LI].dump(dbgs()));
     if (Constraints[LI].isDistance())
       Result |= propagateDistance(Src, Dst, Constraints[LI], Consistent);
     else if (Constraints[LI].isLine())
       Result |= propagateLine(Src, Dst, Constraints[LI], Consistent);
     else if (Constraints[LI].isPoint())
       Result |= propagatePoint(Src, Dst, Constraints[LI]);
   }
   return Result;
 }
 
 
 // Attempt to propagate a distance
 // constraint into a subscript pair (Src and Dst).
 // Return true if some simplification occurs.
 // If the simplification isn't exact (that is, if it is conservative
 // in terms of dependence), set consistent to false.
-bool DependenceAnalysis::propagateDistance(const SCEV *&Src,
-                                           const SCEV *&Dst,
-                                           Constraint &CurConstraint,
-                                           bool &Consistent) {
+bool DependenceInfo::propagateDistance(const SCEV *&Src, const SCEV *&Dst,
   const Loop *CurLoop = CurConstraint.getAssociatedLoop();
   DEBUG(dbgs() << "\t\tSrc is " << *Src << "\n");
   const SCEV *A_K = findCoefficient(Src, CurLoop);
   if (A_K->isZero())
     return false;
   const SCEV *DA_K = SE->getMulExpr(A_K, CurConstraint.getD());
   Src = SE->getMinusSCEV(Src, DA_K);
   Src = zeroCoefficient(Src, CurLoop);
   DEBUG(dbgs() << "\t\tnew Src is " << *Src << "\n");
   DEBUG(dbgs() << "\t\tDst is " << *Dst << "\n");
   Dst = addToCoefficient(Dst, CurLoop, SE->getNegativeSCEV(A_K));
   DEBUG(dbgs() << "\t\tnew Dst is " << *Dst << "\n");
   if (!findCoefficient(Dst, CurLoop)->isZero())
     Consistent = false;
   return true;
 }
 
 
 // Attempt to propagate a line
 // constraint into a subscript pair (Src and Dst).
 // Return true if some simplification occurs.
 // If the simplification isn't exact (that is, if it is conservative
 // in terms of dependence), set consistent to false.
-bool DependenceAnalysis::propagateLine(const SCEV *&Src,
-                                       const SCEV *&Dst,
-                                       Constraint &CurConstraint,
-                                       bool &Consistent) {
+bool DependenceInfo::propagateLine(const SCEV *&Src, const SCEV *&Dst,
   const Loop *CurLoop = CurConstraint.getAssociatedLoop();
   const SCEV *A = CurConstraint.getA();
   const SCEV *B = CurConstraint.getB();
   const SCEV *C = CurConstraint.getC();
   DEBUG(dbgs() << "\t\tA = " << *A << ", B = " << *B << ", C = " << *C << "\n");
   DEBUG(dbgs() << "\t\tSrc = " << *Src << "\n");
   DEBUG(dbgs() << "\t\tDst = " << *Dst << "\n");
   if (A->isZero()) {
bool DependenceInfo::propagateLine(const SCEV *&Src, const SCEV *&Dst,
   DEBUG(dbgs() << "\t\tnew Dst = " << *Dst << "\n");
   return true;
 }
 
 
 // Attempt to propagate a point
 // constraint into a subscript pair (Src and Dst).
 // Return true if some simplification occurs.
-bool DependenceAnalysis::propagatePoint(const SCEV *&Src,
-                                        const SCEV *&Dst,
-                                        Constraint &CurConstraint) {
+bool DependenceInfo::propagatePoint(const SCEV *&Src, const SCEV *&Dst,
   const Loop *CurLoop = CurConstraint.getAssociatedLoop();
   const SCEV *A_K = findCoefficient(Src, CurLoop);
   const SCEV *AP_K = findCoefficient(Dst, CurLoop);
   const SCEV *XA_K = SE->getMulExpr(A_K, CurConstraint.getX());
   const SCEV *YAP_K = SE->getMulExpr(AP_K, CurConstraint.getY());
   DEBUG(dbgs() << "\t\tSrc is " << *Src << "\n");
   Src = SE->getAddExpr(Src, SE->getMinusSCEV(XA_K, YAP_K));
   Src = zeroCoefficient(Src, CurLoop);
   DEBUG(dbgs() << "\t\tnew Src is " << *Src << "\n");
   DEBUG(dbgs() << "\t\tDst is " << *Dst << "\n");
   Dst = zeroCoefficient(Dst, CurLoop);
   DEBUG(dbgs() << "\t\tnew Dst is " << *Dst << "\n");
   return true;
 }
 
 
 // Update direction vector entry based on the current constraint.
-void DependenceAnalysis::updateDirection(Dependence::DVEntry &Level,
-                                         const Constraint &CurConstraint
-                                         ) const {
+void DependenceInfo::updateDirection(Dependence::DVEntry &Level,
+                                     const Constraint &CurConstraint) const {
   DEBUG(dbgs() << "\tUpdate direction, constraint =");
   DEBUG(CurConstraint.dump(dbgs()));
   if (CurConstraint.isAny())
     ; // use defaults
   else if (CurConstraint.isDistance()) {
     // this one is consistent, the others aren't
     Level.Scalar = false;
     Level.Distance = CurConstraint.getD();
void DependenceInfo::updateDirection(Dependence::DVEntry &Level,
   else
     llvm_unreachable("constraint has unexpected kind");
 }
 
 /// Check if we can delinearize the subscripts. If the SCEVs representing the
 /// source and destination array references are recurrences on a nested loop,
 /// this function flattens the nested recurrences into separate recurrences
 /// for each loop level.
-bool DependenceAnalysis::tryDelinearize(Instruction *Src,
-                                        Instruction *Dst,
-                                        SmallVectorImpl<Subscript> &Pair)
-{
+bool DependenceInfo::tryDelinearize(Instruction *Src, Instruction *Dst,
+                                    SmallVectorImpl<Subscript> &Pair) {
   Value *SrcPtr = getPointerOperand(Src);
   Value *DstPtr = getPointerOperand(Dst);
 
   Loop *SrcLoop = LI->getLoopFor(Src->getParent());
   Loop *DstLoop = LI->getLoopFor(Dst->getParent());
 
   // Below code mimics the code in Delinearization.cpp
   const SCEV *SrcAccessFn =

 //
 //            Practical Dependence Testing
 //            Goff, Kennedy, Tseng
 //            PLDI 1991
 //
 // Care is required to keep the routine below, getSplitIteration(),
 // up to date with respect to this routine.
 std::unique_ptr<Dependence>
-DependenceAnalysis::depends(Instruction *Src, Instruction *Dst,
-                            bool PossiblyLoopIndependent) {
+DependenceInfo::depends(Instruction *Src, Instruction *Dst,
   if (Src == Dst)
     PossiblyLoopIndependent = false;
 
   if ((!Src->mayReadFromMemory() && !Src->mayWriteToMemory()) ||
       (!Dst->mayReadFromMemory() && !Dst->mayWriteToMemory()))
     // if both instructions don't reference memory, there's no dependence
     return nullptr;
 

 //        A[i] = ...
 //        ... = A[11 - i]
 //    for (i = 6; i < 10; i++)
 //        A[i] = ...
 //        ... = A[11 - i]
 //
 // breaks the dependence and allows us to vectorize/parallelize
 // both loops.
-const  SCEV *DependenceAnalysis::getSplitIteration(const Dependence &Dep,
-                                                   unsigned SplitLevel) {
+const SCEV *DependenceInfo::getSplitIteration(const Dependence &Dep,
   assert(Dep.isSplitable(SplitLevel) &&
          "Dep should be splitable at SplitLevel");
   Instruction *Src = Dep.getSrc();
   Instruction *Dst = Dep.getDst();
   assert(Src->mayReadFromMemory() || Src->mayWriteToMemory());
   assert(Dst->mayReadFromMemory() || Dst->mayWriteToMemory());
   assert(isLoadOrStore(Src));
   assert(isLoadOrStore(Dst));

llvm/trunk/lib/Passes/PassBuilder.cpp

 #include "llvm/Analysis/BasicAliasAnalysis.h"
 #include "llvm/Analysis/BlockFrequencyInfo.h"
 #include "llvm/Analysis/BlockFrequencyInfoImpl.h"
 #include "llvm/Analysis/BranchProbabilityInfo.h"
 #include "llvm/Analysis/CFLAliasAnalysis.h"
 #include "llvm/Analysis/CGSCCPassManager.h"
 #include "llvm/Analysis/CallGraph.h"
 #include "llvm/Analysis/DemandedBits.h"
+#include "llvm/Analysis/DependenceAnalysis.h"
 #include "llvm/Analysis/DominanceFrontier.h"
 #include "llvm/Analysis/GlobalsModRef.h"
 #include "llvm/Analysis/LazyCallGraph.h"
 #include "llvm/Analysis/LoopInfo.h"
 #include "llvm/Analysis/MemoryDependenceAnalysis.h"
 #include "llvm/Analysis/PostDominators.h"
 #include "llvm/Analysis/RegionInfo.h"
 #include "llvm/Analysis/ScalarEvolution.h"

llvm/trunk/lib/Passes/PassRegistry.def

 FUNCTION_ANALYSIS("assumptions", AssumptionAnalysis())
 FUNCTION_ANALYSIS("block-freq", BlockFrequencyAnalysis())
 FUNCTION_ANALYSIS("branch-prob", BranchProbabilityAnalysis())
 FUNCTION_ANALYSIS("domtree", DominatorTreeAnalysis())
 FUNCTION_ANALYSIS("postdomtree", PostDominatorTreeAnalysis())
 FUNCTION_ANALYSIS("demanded-bits", DemandedBitsAnalysis())
 FUNCTION_ANALYSIS("domfrontier", DominanceFrontierAnalysis())
 FUNCTION_ANALYSIS("loops", LoopAnalysis())
+FUNCTION_ANALYSIS("da", DependenceAnalysis())
 FUNCTION_ANALYSIS("memdep", MemoryDependenceAnalysis())
 FUNCTION_ANALYSIS("regions", RegionInfoAnalysis())
 FUNCTION_ANALYSIS("no-op-function", NoOpFunctionAnalysis())
 FUNCTION_ANALYSIS("scalar-evolution", ScalarEvolutionAnalysis())
 FUNCTION_ANALYSIS("targetlibinfo", TargetLibraryAnalysis())
 FUNCTION_ANALYSIS("targetir",
                   TM ? TM->getTargetIRAnalysis() : TargetIRAnalysis())
 FUNCTION_ANALYSIS("verify", VerifierAnalysis())

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

for (auto I = DepMatrix.begin(), E = DepMatrix.end(); I != E; ++I) {
     for (auto II = Vec.begin(), EE = Vec.end(); II != EE; ++II)
       DEBUG(dbgs() << *II << " ");
     DEBUG(dbgs() << "\n");
   }
 }
 #endif
 
 static bool populateDependencyMatrix(CharMatrix &DepMatrix, unsigned Level,
-                                     Loop *L, DependenceAnalysis *DA) {
+                                     Loop *L, DependenceInfo *DI) {
   typedef SmallVector<Value *, 16> ValueVector;
   ValueVector MemInstr;
 
   if (Level > MaxLoopNestDepth) {
     DEBUG(dbgs() << "Cannot handle loops of depth greater than "
                  << MaxLoopNestDepth << "\n");
     return false;
   }
for (I = MemInstr.begin(), IE = MemInstr.end(); I != IE; ++I) {
     for (J = I, JE = MemInstr.end(); J != JE; ++J) {
       std::vector<char> Dep;
       Instruction *Src = dyn_cast<Instruction>(*I);
       Instruction *Des = dyn_cast<Instruction>(*J);
       if (Src == Des)
         continue;
       if (isa<LoadInst>(Src) && isa<LoadInst>(Des))
         continue;
-      if (auto D = DA->depends(Src, Des, true)) {
+      if (auto D = DI->depends(Src, Des, true)) {
         DEBUG(dbgs() << "Found Dependency between Src=" << Src << " Des=" << Des
                      << "\n");
         if (D->isFlow()) {
           // TODO: Handle Flow dependence.Check if it is sufficient to populate
           // the Dependence Matrix with the direction reversed.
           DEBUG(dbgs() << "Flow dependence not handled");
           return false;
         }
private:
   bool InnerLoopHasReduction;
 };
 
 // Main LoopInterchange Pass.
 struct LoopInterchange : public FunctionPass {
   static char ID;
   ScalarEvolution *SE;
   LoopInfo *LI;
-  DependenceAnalysis *DA;
+  DependenceInfo *DI;
   DominatorTree *DT;
   bool PreserveLCSSA;
   LoopInterchange()
-      : FunctionPass(ID), SE(nullptr), LI(nullptr), DA(nullptr), DT(nullptr) {
+      : FunctionPass(ID), SE(nullptr), LI(nullptr), DI(nullptr), DT(nullptr) {
     initializeLoopInterchangePass(*PassRegistry::getPassRegistry());
   }
 
   void getAnalysisUsage(AnalysisUsage &AU) const override {
     AU.addRequired<ScalarEvolutionWrapperPass>();
     AU.addRequired<AAResultsWrapperPass>();
     AU.addRequired<DominatorTreeWrapperPass>();
     AU.addRequired<LoopInfoWrapperPass>();
-    AU.addRequired<DependenceAnalysis>();
+    AU.addRequired<DependenceAnalysisWrapperPass>();
     AU.addRequiredID(LoopSimplifyID);
     AU.addRequiredID(LCSSAID);
   }
 
   bool runOnFunction(Function &F) override {
     if (skipFunction(F))
       return false;
 
     SE = &getAnalysis<ScalarEvolutionWrapperPass>().getSE();
     LI = &getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
-    DA = &getAnalysis<DependenceAnalysis>();
+    DI = &getAnalysis<DependenceAnalysisWrapperPass>().getDI();
     auto *DTWP = getAnalysisIfAvailable<DominatorTreeWrapperPass>();
     DT = DTWP ? &DTWP->getDomTree() : nullptr;
     PreserveLCSSA = mustPreserveAnalysisID(LCSSAID);
 
     // Build up a worklist of loop pairs to analyze.
     SmallVector<LoopVector, 8> Worklist;
 
     for (Loop *L : *LI)
if (!isComputableLoopNest(LoopList)) {
       return false;
     }
     Loop *OuterMostLoop = *(LoopList.begin());
 
     DEBUG(dbgs() << "Processing LoopList of size = " << LoopList.size()
                  << "\n");
 
     if (!populateDependencyMatrix(DependencyMatrix, LoopList.size(),
-                                  OuterMostLoop, DA)) {
+                                  OuterMostLoop, DI)) {
       DEBUG(dbgs() << "Populating Dependency matrix failed\n");
       return false;
     }
 #ifdef DUMP_DEP_MATRICIES
     DEBUG(dbgs() << "Dependence before inter change \n");
     printDepMatrix(DependencyMatrix);
 #endif
 
if (Changed)
     adjustLoopPreheaders();
   return Changed;
 }
 
 char LoopInterchange::ID = 0;
 INITIALIZE_PASS_BEGIN(LoopInterchange, "loop-interchange",
                       "Interchanges loops for cache reuse", false, false)
 INITIALIZE_PASS_DEPENDENCY(AAResultsWrapperPass)
-INITIALIZE_PASS_DEPENDENCY(DependenceAnalysis)
+INITIALIZE_PASS_DEPENDENCY(DependenceAnalysisWrapperPass)
 INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
 INITIALIZE_PASS_DEPENDENCY(ScalarEvolutionWrapperPass)
 INITIALIZE_PASS_DEPENDENCY(LoopSimplify)
 INITIALIZE_PASS_DEPENDENCY(LCSSA)
 INITIALIZE_PASS_DEPENDENCY(LoopInfoWrapperPass)
 
 INITIALIZE_PASS_END(LoopInterchange, "loop-interchange",
                     "Interchanges loops for cache reuse", false, false)
 
 Pass *llvm::createLoopInterchangePass() { return new LoopInterchange(); }

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

if (skipLoop(L))
       return false;
 
     DominatorTree &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree();
     LoopInfo &LI = getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
     return simplifyLoopCFG(*L, DT, LI);
   }
 
   void getAnalysisUsage(AnalysisUsage &AU) const override {
-    AU.addPreserved<DependenceAnalysis>();
+    AU.addPreserved<DependenceAnalysisWrapperPass>();
     getLoopAnalysisUsage(AU);
   }
 };
 }
 
 char LoopSimplifyCFGLegacyPass::ID = 0;
 INITIALIZE_PASS_BEGIN(LoopSimplifyCFGLegacyPass, "loop-simplifycfg",
                       "Simplify loop CFG", false, false)
 INITIALIZE_PASS_DEPENDENCY(LoopPass)
 INITIALIZE_PASS_END(LoopSimplifyCFGLegacyPass, "loop-simplifycfg",
                     "Simplify loop CFG", false, false)
 
 Pass *llvm::createLoopSimplifyCFGPass() {
   return new LoopSimplifyCFGLegacyPass();
 }

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

void getAnalysisUsage(AnalysisUsage &AU) const override {
       AU.addRequired<LoopInfoWrapperPass>();
       AU.addPreserved<LoopInfoWrapperPass>();
 
       AU.addPreserved<BasicAAWrapperPass>();
       AU.addPreserved<AAResultsWrapperPass>();
       AU.addPreserved<GlobalsAAWrapperPass>();
       AU.addPreserved<ScalarEvolutionWrapperPass>();
       AU.addPreserved<SCEVAAWrapperPass>();
-      AU.addPreserved<DependenceAnalysis>();
+      AU.addPreserved<DependenceAnalysisWrapperPass>();
       AU.addPreservedID(BreakCriticalEdgesID);  // No critical edges added.
     }
 
     /// verifyAnalysis() - Verify LoopSimplifyForm's guarantees.
     void verifyAnalysis() const override;
   };
 }