[SCEV] Replace SCEVComparePredicate with a wrapped SCEV expression

[reames]

Summary

This builds on D119558, and shows how having a compare node in SCEV itself lets us start to simplify the predication mechanism used in SCEVPredicate. This initial patch only handles the SCEVComparePredicate node, but once this lands, I plan to tackle the other leaf node type (SCEVWrapPredicate) and then the union wrapper.

Once this line of work is done, we will be able to form more general predicates, and will have eliminated all the duplicate logic in SCEVPredicate. The later will make it easier to keep the code correct, and the former will enable a couple of use cases which have come up in discussion over the last couple months.

[reames]

Closing review I'm not currently working on, and am unlikely to get back to in near future. Will reopen if priorities change.

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_Compare, P_Wrap };
+  enum SCEVPredicateKind { P_Union, P_Expr, P_Wrap };
 
 protected:
   SCEVPredicateKind Kind;
   ~SCEVPredicate() = default;
   SCEVPredicate(const SCEVPredicate &) = default;
   SCEVPredicate &operator=(const SCEVPredicate &) = default;
 
 public:
   SCEVPredicate(const FoldingSetNodeIDRef ID, SCEVPredicateKind Kind);
 
   SCEVPredicateKind getKind() const { return Kind; }
 
   /// Returns the estimated complexity of this predicate.  This is roughly
   /// measured in the number of run-time checks required.
   virtual unsigned getComplexity() const { return 1; }
 
   /// Returns true if the predicate is always true. This means that no
   /// assumptions were made and nothing needs to be checked at run-time.
   virtual bool isAlwaysTrue() const = 0;
 
   /// Returns true if this predicate implies \p N.
-  virtual bool implies(const SCEVPredicate *N) const = 0;
+  virtual bool implies(ScalarEvolution &SE, const SCEVPredicate *N) const = 0;
 
   /// Prints a textual representation of this predicate with an indentation of
   /// \p Depth.
   virtual void print(raw_ostream &OS, unsigned Depth = 0) const = 0;
 };
 
 inline raw_ostream &operator<<(raw_ostream &OS, const SCEVPredicate &P) {
   P.print(OS);
struct FoldingSetTrait<SCEVPredicate> : DefaultFoldingSetTrait<SCEVPredicate> {
   }
 
   static unsigned ComputeHash(const SCEVPredicate &X,
                               FoldingSetNodeID &TempID) {
     return X.FastID.ComputeHash();
   }
 };
 
-/// This class represents an assumption that the expression LHS Pred RHS
-/// evaluates to true, and this can be checked at run-time.
-class SCEVComparePredicate final : public SCEVPredicate {
-  /// We assume that LHS Pred RHS is true.
-  const ICmpInst::Predicate Pred;
-  const SCEV *LHS;
-  const SCEV *RHS;
+/// This class represents an assumption that the expression Expr evaluates
+/// to true, and this can be checked at run-time.
+class SCEVExprPredicate final : public SCEVPredicate {
+  const SCEV *Expr;
 
 public:
-  SCEVComparePredicate(const FoldingSetNodeIDRef ID,
-                       const ICmpInst::Predicate Pred,
-                       const SCEV *LHS, const SCEV *RHS);
+  SCEVExprPredicate(const FoldingSetNodeIDRef ID, const SCEV *Expr);
 
   /// Implementation of the SCEVPredicate interface
-  bool implies(const SCEVPredicate *N) const override;
+  bool implies(ScalarEvolution &SE, const SCEVPredicate *N) const override;
   void print(raw_ostream &OS, unsigned Depth = 0) const override;
   bool isAlwaysTrue() const override;
 
-  ICmpInst::Predicate getPredicate() const { return Pred; }
-
-  /// Returns the left hand side of the predicate.
-  const SCEV *getLHS() const { return LHS; }
-
-  /// Returns the right hand side of the predicate.
-  const SCEV *getRHS() const { return RHS; }
+  const SCEV *getExpr() const { return Expr; }
 
   /// Methods for support type inquiry through isa, cast, and dyn_cast:
   static bool classof(const SCEVPredicate *P) {
-    return P->getKind() == P_Compare;
+    return P->getKind() == P_Expr;
   }
 };
 
 /// 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).
 ///
explicit SCEVWrapPredicate(const FoldingSetNodeIDRef ID,
                              const SCEVAddRecExpr *AR,
                              IncrementWrapFlags Flags);
 
   /// Returns the set assumed no overflow flags.
   IncrementWrapFlags getFlags() const { return Flags; }
 
   /// Implementation of the SCEVPredicate interface
   const SCEVAddRecExpr *getExpr() const;
-  bool implies(const SCEVPredicate *N) const override;
+  bool implies(ScalarEvolution &SE, const SCEVPredicate *N) const override;
   void print(raw_ostream &OS, unsigned Depth = 0) const override;
   bool isAlwaysTrue() const override;
 
   /// Methods for support type inquiry through isa, cast, and dyn_cast:
   static bool classof(const SCEVPredicate *P) {
     return P->getKind() == P_Wrap;
   }
 };
public:
   SCEVUnionPredicate(ArrayRef<const SCEVPredicate *> Preds);
 
   const SmallVectorImpl<const SCEVPredicate *> &getPredicates() const {
     return Preds;
   }
 
   /// Implementation of the SCEVPredicate interface
   bool isAlwaysTrue() const override;
-  bool implies(const SCEVPredicate *N) const override;
+  bool implies(ScalarEvolution &SE, const SCEVPredicate *N) const override;
   void print(raw_ostream &OS, unsigned Depth) const override;
 
   /// We estimate the complexity of a union predicate as the size number of
   /// predicates in the union.
   unsigned getComplexity() const override { return Preds.size(); }
 
   /// Methods for support type inquiry through isa, cast, and dyn_cast:
   static bool classof(const SCEVPredicate *P) {
bool isKnownPredicateAt(ICmpInst::Predicate Pred, const SCEV *LHS,
                           const SCEV *RHS, const Instruction *CtxI);
 
   /// Check whether the condition described by Pred, LHS, and RHS is true or
   /// false in the given \p Context. If we know it, return the evaluation of
   /// this condition. If neither is proved, return None.
   Optional<bool> evaluatePredicateAt(ICmpInst::Predicate Pred, const SCEV *LHS,
                                      const SCEV *RHS, const Instruction *CtxI);
 
+  /// Return true of A implies B.
+  bool isImpliedCond(const SCEV *B, const SCEV *A);
+
   /// Test if the condition described by Pred, LHS, RHS is known to be true on
   /// every iteration of the loop of the recurrency LHS.
   bool isKnownOnEveryIteration(ICmpInst::Predicate Pred,
                                const SCEVAddRecExpr *LHS, const SCEV *RHS);
 
   /// A predicate is said to be monotonically increasing if may go from being
   /// false to being true as the loop iterates, but never the other way
   /// around.  A predicate is said to be monotonically decreasing if may go

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

#endif
   }
 
   /// Generates a code sequence that evaluates this predicate.  The inserted
   /// 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 SCEVComparePredicate.
-  Value *expandComparePredicate(const SCEVComparePredicate *Pred,
-                                Instruction *Loc);
+  /// we are expanding code for a SCEVExprPredicate.
+  Value *expandExprPredicate(const SCEVExprPredicate *Pred,
 
   /// 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/ScalarEvolution.cpp

 /// Return a SCEV corresponding to ~V = -1-V
 const SCEV *ScalarEvolution::getNotSCEV(const SCEV *V) {
   assert(!V->getType()->isPointerTy() && "Can't negate pointer");
 
   if (const SCEVConstant *VC = dyn_cast<SCEVConstant>(V))
     return getConstant(
                 cast<ConstantInt>(ConstantExpr::getNot(VC->getValue())));
 
+  if (const SCEVCompareExpr *C = dyn_cast<SCEVCompareExpr>(V))
+    return getCompareExpr(ICmpInst::getInversePredicate(C->getPredicate()),
+                          C->getLHS(), C->getRHS());
+
   // Fold ~(u|s)(min|max)(~x, ~y) to (u|s)(max|min)(x, y)
   if (const SCEVMinMaxExpr *MME = dyn_cast<SCEVMinMaxExpr>(V)) {
     auto MatchMinMaxNegation = [&](const SCEVMinMaxExpr *MME) {
       SmallVector<const SCEV *, 2> MatchedOperands;
       for (const SCEV *Operand : MME->operands()) {
         const SCEV *Matched = MatchNotExpr(Operand);
         if (!Matched)
           return (const SCEV *)nullptr;

 // even when the following Equal predicate exists:
 // "%step == (sext ix (trunc iy to ix) to iy)".
 bool PredicatedScalarEvolution::areAddRecsEqualWithPreds(
     const SCEVAddRecExpr *AR1, const SCEVAddRecExpr *AR2) const {
   if (AR1 == AR2)
     return true;
 
   auto areExprsEqual = [&](const SCEV *Expr1, const SCEV *Expr2) -> bool {
-    if (Expr1 != Expr2 && !Preds->implies(SE.getEqualPredicate(Expr1, Expr2)) &&
-        !Preds->implies(SE.getEqualPredicate(Expr2, Expr1)))
+    if (Expr1 != Expr2 &&
+        !Preds->implies(SE, SE.getEqualPredicate(Expr1, Expr2)) &&
+        !Preds->implies(SE, SE.getEqualPredicate(Expr2, Expr1)))
       return false;
     return true;
   };
 
   if (!areExprsEqual(AR1->getStart(), AR2->getStart()) ||
       !areExprsEqual(AR1->getStepRecurrence(SE), AR2->getStepRecurrence(SE)))
     return false;
   return true;
if (isBasicBlockEntryGuardedByCond(CtxI->getParent(), Pred, LHS, RHS))
     return true;
   else if (isBasicBlockEntryGuardedByCond(CtxI->getParent(),
                                           ICmpInst::getInversePredicate(Pred),
                                           LHS, RHS))
     return false;
   return None;
 }
 
+bool ScalarEvolution::isImpliedCond(const SCEV *B, const SCEV *A) {
+  const auto *CmpA = dyn_cast<SCEVCompareExpr>(A);
+  const auto *CmpB = dyn_cast<SCEVCompareExpr>(B);
+  return CmpA && CmpB &&
+    isImpliedCond(CmpB->getPredicate(), CmpB->getLHS(), CmpB->getRHS(),
+                  CmpA->getPredicate(), CmpA->getLHS(), CmpA->getRHS());
+}
+
+
 bool ScalarEvolution::isKnownOnEveryIteration(ICmpInst::Predicate Pred,
                                               const SCEVAddRecExpr *LHS,
                                               const SCEV *RHS) {
   const Loop *L = LHS->getLoop();
   return isLoopEntryGuardedByCond(L, Pred, LHS->getStart(), RHS) &&
          isLoopBackedgeGuardedByCond(L, Pred, LHS->getPostIncExpr(*this), RHS);
 }
 

 }
 
 const SCEVPredicate *
 ScalarEvolution::getComparePredicate(const ICmpInst::Predicate Pred,
                                      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_Compare);
-  ID.AddInteger(Pred);
-  ID.AddPointer(LHS);
-  ID.AddPointer(RHS);
+
+  auto *Expr = getCompareExpr(Pred, LHS, RHS);
+
+  ID.AddInteger(SCEVPredicate::P_Expr);
+  ID.AddPointer(Expr);
   void *IP = nullptr;
   if (const auto *S = UniquePreds.FindNodeOrInsertPos(ID, IP))
     return S;
-  SCEVComparePredicate *Eq = new (SCEVAllocator)
-    SCEVComparePredicate(ID.Intern(SCEVAllocator), Pred, LHS, RHS);
-  UniquePreds.InsertNode(Eq, IP);
-  return Eq;
+  auto *P = new (SCEVAllocator)
+    SCEVExprPredicate(ID.Intern(SCEVAllocator), Expr);
+  UniquePreds.InsertNode(P, IP);
+  return P;
 }
 
 const SCEVPredicate *ScalarEvolution::getWrapPredicate(
     const SCEVAddRecExpr *AR,
     SCEVWrapPredicate::IncrementWrapFlags AddedFlags) {
   FoldingSetNodeID ID;
   // Unique this node based on the arguments
   ID.AddInteger(SCEVPredicate::P_Wrap);
static const SCEV *rewrite(const SCEV *S, const Loop *L, ScalarEvolution &SE,
                              SmallPtrSetImpl<const SCEVPredicate *> *NewPreds,
                              const SCEVPredicate *Pred) {
     SCEVPredicateRewriter Rewriter(L, SE, NewPreds, Pred);
     return Rewriter.visit(S);
   }
 
   const SCEV *visitUnknown(const SCEVUnknown *Expr) {
     if (Pred) {
+      auto MatchEqCompare = [&](const SCEVPredicate *Pred) -> const SCEV* {
+        if (const auto *IPred = dyn_cast<SCEVExprPredicate>(Pred))
+          if (const auto *Cmp = dyn_cast<SCEVCompareExpr>(IPred->getExpr()))
+            if (Cmp->getLHS() == Expr &&
+                Cmp->getPredicate() == ICmpInst::ICMP_EQ)
+              return Cmp->getRHS();
+        return nullptr;
+      };
+
       if (auto *U = dyn_cast<SCEVUnionPredicate>(Pred)) {
         for (auto *Pred : U->getPredicates())
-          if (const auto *IPred = dyn_cast<SCEVComparePredicate>(Pred))
-            if (IPred->getLHS() == Expr &&
-                IPred->getPredicate() == ICmpInst::ICMP_EQ)
-              return IPred->getRHS();
-      } else if (const auto *IPred = dyn_cast<SCEVComparePredicate>(Pred)) {
-        if (IPred->getLHS() == Expr &&
-            IPred->getPredicate() == ICmpInst::ICMP_EQ)
-          return IPred->getRHS();
+          if (auto *Res = MatchEqCompare(Pred))
+            return Res;
+      } else if (auto *Res = MatchEqCompare(Pred)) {
+        return Res;
       }
     }
     return convertToAddRecWithPreds(Expr);
   }
 
   const SCEV *visitZeroExtendExpr(const SCEVZeroExtendExpr *Expr) {
     const SCEV *Operand = visit(Expr->getOperand());
     const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(Operand);
private:
   explicit SCEVPredicateRewriter(const Loop *L, ScalarEvolution &SE,
                         SmallPtrSetImpl<const SCEVPredicate *> *NewPreds,
                         const SCEVPredicate *Pred)
       : SCEVRewriteVisitor(SE), NewPreds(NewPreds), Pred(Pred), L(L) {}
 
   bool addOverflowAssumption(const SCEVPredicate *P) {
     if (!NewPreds) {
       // Check if we've already made this assumption.
-      return Pred && Pred->implies(P);
+      return Pred && Pred->implies(SE, P);
     }
     NewPreds->insert(P);
     return true;
   }
 
   bool addOverflowAssumption(const SCEVAddRecExpr *AR,
                              SCEVWrapPredicate::IncrementWrapFlags AddedFlags) {
     auto *A = SE.getWrapPredicate(AR, AddedFlags);
const SCEVAddRecExpr *ScalarEvolution::convertSCEVToAddRecWithPredicates(
   return AddRec;
 }
 
 /// SCEV predicates
 SCEVPredicate::SCEVPredicate(const FoldingSetNodeIDRef ID,
                              SCEVPredicateKind Kind)
     : FastID(ID), Kind(Kind) {}
 
-SCEVComparePredicate::SCEVComparePredicate(const FoldingSetNodeIDRef ID,
-                                   const ICmpInst::Predicate Pred,
-                                   const SCEV *LHS, const SCEV *RHS)
-  : SCEVPredicate(ID, P_Compare), Pred(Pred), 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");
+SCEVExprPredicate::SCEVExprPredicate(const FoldingSetNodeIDRef ID,
+                                     const SCEV *Expr)
+  : SCEVPredicate(ID, P_Expr), Expr(Expr) {
+  assert(Expr->getType()->isIntegerTy(1) && "must be a boolean");
 }
 
-bool SCEVComparePredicate::implies(const SCEVPredicate *N) const {
-  const auto *Op = dyn_cast<SCEVComparePredicate>(N);
-
+bool SCEVExprPredicate::implies(ScalarEvolution &SE,
+                                const SCEVPredicate *N) const {
+  const auto *Op = dyn_cast<SCEVExprPredicate>(N);
   if (!Op)
     return false;
 
-  if (Pred != ICmpInst::ICMP_EQ)
-    return false;
-
-  return Op->LHS == LHS && Op->RHS == RHS;
+  return SE.isImpliedCond(Op->Expr, this->Expr);
 }
 
-bool SCEVComparePredicate::isAlwaysTrue() const { return false; }
-
-void SCEVComparePredicate::print(raw_ostream &OS, unsigned Depth) const {
-  if (Pred == ICmpInst::ICMP_EQ)
-    OS.indent(Depth) << "Equal predicate: " << *LHS << " == " << *RHS << "\n";
-  else
-    OS.indent(Depth) << "Compare predicate: " << *LHS
-                     << " " << CmpInst::getPredicateName(Pred) << ") "
-                     << *RHS << "\n";
+bool SCEVExprPredicate::isAlwaysTrue() const { return Expr->isOne(); }
 
+void SCEVExprPredicate::print(raw_ostream &OS, unsigned Depth) const {
+  OS.indent(Depth) << "Expr predicate: " << *Expr << "\n";
 }
 
 SCEVWrapPredicate::SCEVWrapPredicate(const FoldingSetNodeIDRef ID,
                                      const SCEVAddRecExpr *AR,
                                      IncrementWrapFlags Flags)
     : SCEVPredicate(ID, P_Wrap), AR(AR), Flags(Flags) {}
 
 const SCEVAddRecExpr *SCEVWrapPredicate::getExpr() const { return AR; }
 
-bool SCEVWrapPredicate::implies(const SCEVPredicate *N) const {
+bool SCEVWrapPredicate::implies(ScalarEvolution &SE,
+                                const SCEVPredicate *N) const {
   const auto *Op = dyn_cast<SCEVWrapPredicate>(N);
 
   return Op && Op->AR == AR && setFlags(Flags, Op->Flags) == Flags;
 }
 
 bool SCEVWrapPredicate::isAlwaysTrue() const {
   SCEV::NoWrapFlags ScevFlags = AR->getNoWrapFlags();
   IncrementWrapFlags IFlags = Flags;
for (auto *P : Preds)
     add(P);
 }
 
 bool SCEVUnionPredicate::isAlwaysTrue() const {
   return all_of(Preds,
                 [](const SCEVPredicate *I) { return I->isAlwaysTrue(); });
 }
 
-bool SCEVUnionPredicate::implies(const SCEVPredicate *N) const {
+bool SCEVUnionPredicate::implies(ScalarEvolution &SE,
+                                 const SCEVPredicate *N) const {
   if (const auto *Set = dyn_cast<SCEVUnionPredicate>(N))
     return all_of(Set->Preds,
-                  [this](const SCEVPredicate *I) { return this->implies(I); });
+                  [&](const SCEVPredicate *I) { return this->implies(SE, I); });
 
   return any_of(Preds,
-                [N](const SCEVPredicate *I) { return I->implies(N); });
+                [&](const SCEVPredicate *I) { return I->implies(SE, N); });
 }
 
 void SCEVUnionPredicate::print(raw_ostream &OS, unsigned Depth) const {
   for (auto Pred : Preds)
     Pred->print(OS, Depth);
 }
 
 void SCEVUnionPredicate::add(const SCEVPredicate *N) {
if (!BackedgeCount) {
     BackedgeCount = SE.getPredicatedBackedgeTakenCount(&L, Preds);
     for (auto *P : Preds)
       addPredicate(*P);
   }
   return BackedgeCount;
 }
 
 void PredicatedScalarEvolution::addPredicate(const SCEVPredicate &Pred) {
-  if (Preds->implies(&Pred))
+  if (Preds->implies(SE, &Pred))
     return;
 
   auto &OldPreds = Preds->getPredicates();
   SmallVector<const SCEVPredicate*, 4> NewPreds(OldPreds.begin(), OldPreds.end());
   NewPreds.push_back(&Pred);
   Preds = std::make_unique<SCEVUnionPredicate>(NewPreds);
   updateGeneration();
 }

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_Compare:
-    return expandComparePredicate(cast<SCEVComparePredicate>(Pred), IP);
+  case SCEVPredicate::P_Expr:
+    return expandExprPredicate(cast<SCEVExprPredicate>(Pred), IP);
   case SCEVPredicate::P_Wrap: {
     auto *AddRecPred = cast<SCEVWrapPredicate>(Pred);
     return expandWrapPredicate(AddRecPred, IP);
   }
   }
   llvm_unreachable("Unknown SCEV predicate type");
 }
 
-Value *SCEVExpander::expandComparePredicate(const SCEVComparePredicate *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 InvPred = ICmpInst::getInversePredicate(Pred->getPredicate());
-  auto *I = Builder.CreateICmp(InvPred, Expr0, Expr1, "ident.check");
-  return I;
+Value *SCEVExpander::expandExprPredicate(const SCEVExprPredicate *Pred,
+  // WARNING: We're implicitly negating the expression here.  This only works
+  // because we're currently only using SCEVExprPredicate for leaf predicates.
+  // When we remove SCEVUnionExpr, we need to adjust the leaf handling.
+  auto *S = SE.getNotSCEV(Pred->getExpr());
+  return expandCodeForImpl(S, S->getType(), IP, false);
 }
 
 Value *SCEVExpander::generateOverflowCheck(const SCEVAddRecExpr *AR,
                                            Instruction *Loc, bool Signed) {
   assert(AR->isAffine() && "Cannot generate RT check for "
                            "non-affine expression");
 
   // FIXME: It is highly suspicious that we're ignoring the predicates here.

llvm/test/Analysis/LoopAccessAnalysis/symbolic-stride.ll

 ; CHECK-NEXT:          %load = load i32, i32* %gep.A, align 4 ->
 ; CHECK-NEXT:          store i32 %add, i32* %gep.A.next, align 4
 ; CHECK-EMPTY:
 ; CHECK-NEXT:    Run-time memory checks:
 ; CHECK-NEXT:    Grouped accesses:
 ; CHECK-EMPTY:
 ; CHECK-NEXT:    Non vectorizable stores to invariant address were not found in loop.
 ; CHECK-NEXT:    SCEV assumptions:
-; CHECK-NEXT:    Equal predicate: %stride == 1
+; CHECK-NEXT:    Expr predicate: (%stride eq 1)
+
 ; CHECK-EMPTY:
 ; CHECK-NEXT:    Expressions re-written:
 ; CHECK-NEXT:    [PSE]  %gep.A = getelementptr inbounds i32, i32* %A, i64 %mul:
 ; CHECK-NEXT:      {%A,+,(4 * %stride)}<%loop>
 ; CHECK-NEXT:      --> {%A,+,4}<%loop>
 ;
 entry:
   br label %loop

 ; CHECK-NEXT:          %load = load { i32, i8 }, { i32, i8 }* %gep.A, align 4 ->
 ; CHECK-NEXT:          store { i32, i8 } %ins, { i32, i8 }* %gep.A.next, align 4
 ; CHECK-EMPTY:
 ; CHECK-NEXT:    Run-time memory checks:
 ; CHECK-NEXT:    Grouped accesses:
 ; CHECK-EMPTY:
 ; CHECK-NEXT:    Non vectorizable stores to invariant address were not found in loop.
 ; CHECK-NEXT:    SCEV assumptions:
-; CHECK-NEXT:    Equal predicate: %stride == 1
+; CHECK-NEXT:    Expr predicate: (%stride eq 1)
 ; CHECK-EMPTY:
 ; CHECK-NEXT:    Expressions re-written:
 ; CHECK-NEXT:    [PSE]  %gep.A = getelementptr inbounds { i32, i8 }, { i32, i8 }* %A, i64 %mul:
 ; CHECK-NEXT:      {%A,+,(8 * %stride)}<%loop>
 ; CHECK-NEXT:      --> {%A,+,8}<%loop>
 ;
 entry:
   br label %loop

 ; CHECK-NEXT:          %load = load i32, i32* %gep.A, align 4 ->
 ; CHECK-NEXT:          store i32 %add, i32* %gep.A.next, align 4
 ; CHECK-EMPTY:
 ; CHECK-NEXT:    Run-time memory checks:
 ; CHECK-NEXT:    Grouped accesses:
 ; CHECK-EMPTY:
 ; CHECK-NEXT:    Non vectorizable stores to invariant address were not found in loop.
 ; CHECK-NEXT:    SCEV assumptions:
-; CHECK-NEXT:    Equal predicate: %stride.2 == 1
-; CHECK-NEXT:    Equal predicate: %stride.1 == 1
+; CHECK-NEXT:    Expr predicate: (%stride.2 eq 1)
+; CHECK-NEXT:    Expr predicate: (%stride.1 eq 1)
 ; CHECK-EMPTY:
 ; CHECK-NEXT:    Expressions re-written:
 ; CHECK-NEXT:    [PSE]  %gep.A = getelementptr inbounds i32, i32* %A, i64 %mul:
 ; CHECK-NEXT:      {%A,+,(4 * %stride.1)}<%loop>
 ; CHECK-NEXT:      --> {%A,+,4}<%loop>
 ; CHECK-NEXT:    [PSE]  %gep.A.next = getelementptr inbounds i32, i32* %A, i64 %mul.2:
 ; CHECK-NEXT:      {((4 * %stride.2) + %A),+,(4 * %stride.2)}<%loop>
 ; CHECK-NEXT:      --> {(4 + %A),+,4}<%loop>

llvm/test/Transforms/LoopDistribute/symbolic-stride.ll

 
 define void @f(i32* noalias %a,
 ;
 ;
 ; DEFAULT-LABEL: @f(
 ; DEFAULT-NEXT:  entry:
 ; DEFAULT-NEXT:    br label [[FOR_BODY_LVER_CHECK:%.*]]
 ; DEFAULT:       for.body.lver.check:
-; DEFAULT-NEXT:    [[IDENT_CHECK:%.*]] = icmp ne i64 [[STRIDE:%.*]], 1
-; DEFAULT-NEXT:    br i1 [[IDENT_CHECK]], label [[FOR_BODY_PH_LVER_ORIG:%.*]], label [[FOR_BODY_PH_LDIST1:%.*]]
+; DEFAULT-NEXT:    [[TMP0:%.*]] = icmp ne i64 [[STRIDE:%.*]], 1
+; DEFAULT-NEXT:    br i1 [[TMP0]], label [[FOR_BODY_PH_LVER_ORIG:%.*]], label [[FOR_BODY_PH_LDIST1:%.*]]
 ; DEFAULT:       for.body.ph.lver.orig:
 ; DEFAULT-NEXT:    br label [[FOR_BODY_LVER_ORIG:%.*]]
 ; DEFAULT:       for.body.lver.orig:
 ; DEFAULT-NEXT:    [[IND_LVER_ORIG:%.*]] = phi i64 [ 0, [[FOR_BODY_PH_LVER_ORIG]] ], [ [[ADD_LVER_ORIG:%.*]], [[FOR_BODY_LVER_ORIG]] ]
 ; DEFAULT-NEXT:    [[ARRAYIDXA_LVER_ORIG:%.*]] = getelementptr inbounds i32, i32* [[A:%.*]], i64 [[IND_LVER_ORIG]]
 ; DEFAULT-NEXT:    [[LOADA_LVER_ORIG:%.*]] = load i32, i32* [[ARRAYIDXA_LVER_ORIG]], align 4
 ; DEFAULT-NEXT:    [[ARRAYIDXB_LVER_ORIG:%.*]] = getelementptr inbounds i32, i32* [[B:%.*]], i64 [[IND_LVER_ORIG]]
 ; DEFAULT-NEXT:    [[LOADB_LVER_ORIG:%.*]] = load i32, i32* [[ARRAYIDXB_LVER_ORIG]], align 4

llvm/test/Transforms/LoopLoadElim/symbolic-stride.ll

 
 target datalayout = "e-m:o-i64:64-f80:128-n8:16:32:64-S128"
 
 define void @f(i32* noalias nocapture %A, i32* noalias nocapture readonly %B, i64 %N,
 ;
 ;
 ;
 ;
-;
 ; DEFAULT-LABEL: @f(
 ; DEFAULT-NEXT:  for.body.lver.check:
-; DEFAULT-NEXT:    [[IDENT_CHECK:%.*]] = icmp ne i64 [[STRIDE:%.*]], 1
-; DEFAULT-NEXT:    br i1 [[IDENT_CHECK]], label [[FOR_BODY_PH_LVER_ORIG:%.*]], label [[FOR_BODY_PH:%.*]]
+; DEFAULT-NEXT:    [[TMP0:%.*]] = icmp ne i64 [[STRIDE:%.*]], 1
+; DEFAULT-NEXT:    br i1 [[TMP0]], label [[FOR_BODY_PH_LVER_ORIG:%.*]], label [[FOR_BODY_PH:%.*]]
 ; DEFAULT:       for.body.ph.lver.orig:
 ; DEFAULT-NEXT:    br label [[FOR_BODY_LVER_ORIG:%.*]]
 ; DEFAULT:       for.body.lver.orig:
 ; DEFAULT-NEXT:    [[INDVARS_IV_LVER_ORIG:%.*]] = phi i64 [ 0, [[FOR_BODY_PH_LVER_ORIG]] ], [ [[INDVARS_IV_NEXT_LVER_ORIG:%.*]], [[FOR_BODY_LVER_ORIG]] ]
 ; DEFAULT-NEXT:    [[MUL_LVER_ORIG:%.*]] = mul i64 [[INDVARS_IV_LVER_ORIG]], [[STRIDE]]
 ; DEFAULT-NEXT:    [[ARRAYIDX_LVER_ORIG:%.*]] = getelementptr inbounds i32, i32* [[A:%.*]], i64 [[MUL_LVER_ORIG]]
 ; DEFAULT-NEXT:    [[LOAD_LVER_ORIG:%.*]] = load i32, i32* [[ARRAYIDX_LVER_ORIG]], align 4
 ; DEFAULT-NEXT:    [[ARRAYIDX2_LVER_ORIG:%.*]] = getelementptr inbounds i32, i32* [[B:%.*]], i64 [[INDVARS_IV_LVER_ORIG]]

 ; NO-VERSION-NEXT:    store i32 [[ADD]], i32* [[ARRAYIDX_NEXT]], align 4
 ; NO-VERSION-NEXT:    [[EXITCOND:%.*]] = icmp eq i64 [[INDVARS_IV_NEXT]], [[N:%.*]]
 ; NO-VERSION-NEXT:    br i1 [[EXITCOND]], label [[FOR_END:%.*]], label [[FOR_BODY]]
 ; NO-VERSION:       for.end:
 ; NO-VERSION-NEXT:    ret void
 ;
 ; THRESHOLD-LABEL: @f(
 ; THRESHOLD-NEXT:  for.body.lver.check:
-; THRESHOLD-NEXT:    [[IDENT_CHECK:%.*]] = icmp ne i64 [[STRIDE:%.*]], 1
-; THRESHOLD-NEXT:    br i1 [[IDENT_CHECK]], label [[FOR_BODY_PH_LVER_ORIG:%.*]], label [[FOR_BODY_PH:%.*]]
+; THRESHOLD-NEXT:    [[TMP0:%.*]] = icmp ne i64 [[STRIDE:%.*]], 1
+; THRESHOLD-NEXT:    br i1 [[TMP0]], label [[FOR_BODY_PH_LVER_ORIG:%.*]], label [[FOR_BODY_PH:%.*]]
 ; THRESHOLD:       for.body.ph.lver.orig:
 ; THRESHOLD-NEXT:    br label [[FOR_BODY_LVER_ORIG:%.*]]
 ; THRESHOLD:       for.body.lver.orig:
 ; THRESHOLD-NEXT:    [[INDVARS_IV_LVER_ORIG:%.*]] = phi i64 [ 0, [[FOR_BODY_PH_LVER_ORIG]] ], [ [[INDVARS_IV_NEXT_LVER_ORIG:%.*]], [[FOR_BODY_LVER_ORIG]] ]
 ; THRESHOLD-NEXT:    [[MUL_LVER_ORIG:%.*]] = mul i64 [[INDVARS_IV_LVER_ORIG]], [[STRIDE]]
 ; THRESHOLD-NEXT:    [[ARRAYIDX_LVER_ORIG:%.*]] = getelementptr inbounds i32, i32* [[A:%.*]], i64 [[MUL_LVER_ORIG]]
 ; THRESHOLD-NEXT:    [[LOAD_LVER_ORIG:%.*]] = load i32, i32* [[ARRAYIDX_LVER_ORIG]], align 4
 ; THRESHOLD-NEXT:    [[ARRAYIDX2_LVER_ORIG:%.*]] = getelementptr inbounds i32, i32* [[B:%.*]], i64 [[INDVARS_IV_LVER_ORIG]]

 define void @f_struct({ i32, i8 } * noalias nocapture %A, { i32, i8 }* noalias nocapture readonly %B, i64 %N,
 ;
 ;
 ;
 ;
 ;
 ; DEFAULT-LABEL: @f_struct(
 ; DEFAULT-NEXT:  for.body.lver.check:
-; DEFAULT-NEXT:    [[IDENT_CHECK:%.*]] = icmp ne i64 [[STRIDE:%.*]], 1
-; DEFAULT-NEXT:    br i1 [[IDENT_CHECK]], label [[FOR_BODY_PH_LVER_ORIG:%.*]], label [[FOR_BODY_PH:%.*]]
+; DEFAULT-NEXT:    [[TMP0:%.*]] = icmp ne i64 [[STRIDE:%.*]], 1
+; DEFAULT-NEXT:    br i1 [[TMP0]], label [[FOR_BODY_PH_LVER_ORIG:%.*]], label [[FOR_BODY_PH:%.*]]
 ; DEFAULT:       for.body.ph.lver.orig:
 ; DEFAULT-NEXT:    br label [[FOR_BODY_LVER_ORIG:%.*]]
 ; DEFAULT:       for.body.lver.orig:
 ; DEFAULT-NEXT:    [[INDVARS_IV_LVER_ORIG:%.*]] = phi i64 [ 0, [[FOR_BODY_PH_LVER_ORIG]] ], [ [[INDVARS_IV_NEXT_LVER_ORIG:%.*]], [[FOR_BODY_LVER_ORIG]] ]
 ; DEFAULT-NEXT:    [[MUL_LVER_ORIG:%.*]] = mul i64 [[INDVARS_IV_LVER_ORIG]], [[STRIDE]]
 ; DEFAULT-NEXT:    [[ARRAYIDX_LVER_ORIG:%.*]] = getelementptr inbounds { i32, i8 }, { i32, i8 }* [[A:%.*]], i64 [[MUL_LVER_ORIG]]
 ; DEFAULT-NEXT:    [[LOAD_LVER_ORIG:%.*]] = load { i32, i8 }, { i32, i8 }* [[ARRAYIDX_LVER_ORIG]], align 4
 ; DEFAULT-NEXT:    [[ARRAYIDX2_LVER_ORIG:%.*]] = getelementptr inbounds { i32, i8 }, { i32, i8 }* [[B:%.*]], i64 [[INDVARS_IV_LVER_ORIG]]

 ; NO-VERSION-NEXT:    store { i32, i8 } [[INS]], { i32, i8 }* [[ARRAYIDX_NEXT]], align 4
 ; NO-VERSION-NEXT:    [[EXITCOND:%.*]] = icmp eq i64 [[INDVARS_IV_NEXT]], [[N:%.*]]
 ; NO-VERSION-NEXT:    br i1 [[EXITCOND]], label [[FOR_END:%.*]], label [[FOR_BODY]]
 ; NO-VERSION:       for.end:
 ; NO-VERSION-NEXT:    ret void
 ;
 ; THRESHOLD-LABEL: @f_struct(
 ; THRESHOLD-NEXT:  for.body.lver.check:
-; THRESHOLD-NEXT:    [[IDENT_CHECK:%.*]] = icmp ne i64 [[STRIDE:%.*]], 1
-; THRESHOLD-NEXT:    br i1 [[IDENT_CHECK]], label [[FOR_BODY_PH_LVER_ORIG:%.*]], label [[FOR_BODY_PH:%.*]]
+; THRESHOLD-NEXT:    [[TMP0:%.*]] = icmp ne i64 [[STRIDE:%.*]], 1
+; THRESHOLD-NEXT:    br i1 [[TMP0]], label [[FOR_BODY_PH_LVER_ORIG:%.*]], label [[FOR_BODY_PH:%.*]]
 ; THRESHOLD:       for.body.ph.lver.orig:
 ; THRESHOLD-NEXT:    br label [[FOR_BODY_LVER_ORIG:%.*]]
 ; THRESHOLD:       for.body.lver.orig:
 ; THRESHOLD-NEXT:    [[INDVARS_IV_LVER_ORIG:%.*]] = phi i64 [ 0, [[FOR_BODY_PH_LVER_ORIG]] ], [ [[INDVARS_IV_NEXT_LVER_ORIG:%.*]], [[FOR_BODY_LVER_ORIG]] ]
 ; THRESHOLD-NEXT:    [[MUL_LVER_ORIG:%.*]] = mul i64 [[INDVARS_IV_LVER_ORIG]], [[STRIDE]]
 ; THRESHOLD-NEXT:    [[ARRAYIDX_LVER_ORIG:%.*]] = getelementptr inbounds { i32, i8 }, { i32, i8 }* [[A:%.*]], i64 [[MUL_LVER_ORIG]]
 ; THRESHOLD-NEXT:    [[LOAD_LVER_ORIG:%.*]] = load { i32, i8 }, { i32, i8 }* [[ARRAYIDX_LVER_ORIG]], align 4
 ; THRESHOLD-NEXT:    [[ARRAYIDX2_LVER_ORIG:%.*]] = getelementptr inbounds { i32, i8 }, { i32, i8 }* [[B:%.*]], i64 [[INDVARS_IV_LVER_ORIG]]

 ;
 ;
 ;
 ;
 ;
 ;
 ; DEFAULT-LABEL: @two_strides(
 ; DEFAULT-NEXT:  for.body.lver.check:
-; DEFAULT-NEXT:    [[IDENT_CHECK:%.*]] = icmp ne i64 [[STRIDE_2:%.*]], 1
-; DEFAULT-NEXT:    [[IDENT_CHECK1:%.*]] = icmp ne i64 [[STRIDE_1:%.*]], 1
-; DEFAULT-NEXT:    [[TMP0:%.*]] = or i1 [[IDENT_CHECK]], [[IDENT_CHECK1]]
-; DEFAULT-NEXT:    br i1 [[TMP0]], label [[FOR_BODY_PH_LVER_ORIG:%.*]], label [[FOR_BODY_PH:%.*]]
+; DEFAULT-NEXT:    [[TMP0:%.*]] = icmp ne i64 [[STRIDE_2:%.*]], 1
+; DEFAULT-NEXT:    [[TMP1:%.*]] = icmp ne i64 [[STRIDE_1:%.*]], 1
+; DEFAULT-NEXT:    [[TMP2:%.*]] = or i1 [[TMP0]], [[TMP1]]
+; DEFAULT-NEXT:    br i1 [[TMP2]], label [[FOR_BODY_PH_LVER_ORIG:%.*]], label [[FOR_BODY_PH:%.*]]
 ; DEFAULT:       for.body.ph.lver.orig:
 ; DEFAULT-NEXT:    br label [[FOR_BODY_LVER_ORIG:%.*]]
 ; DEFAULT:       for.body.lver.orig:
 ; DEFAULT-NEXT:    [[INDVARS_IV_LVER_ORIG:%.*]] = phi i64 [ 0, [[FOR_BODY_PH_LVER_ORIG]] ], [ [[INDVARS_IV_NEXT_LVER_ORIG:%.*]], [[FOR_BODY_LVER_ORIG]] ]
 ; DEFAULT-NEXT:    [[MUL_LVER_ORIG:%.*]] = mul i64 [[INDVARS_IV_LVER_ORIG]], [[STRIDE_1]]
 ; DEFAULT-NEXT:    [[ARRAYIDX_LVER_ORIG:%.*]] = getelementptr inbounds i32, i32* [[A:%.*]], i64 [[MUL_LVER_ORIG]]
 ; DEFAULT-NEXT:    [[LOAD_LVER_ORIG:%.*]] = load i32, i32* [[ARRAYIDX_LVER_ORIG]], align 4
 ; DEFAULT-NEXT:    [[ARRAYIDX2_LVER_ORIG:%.*]] = getelementptr inbounds i32, i32* [[B:%.*]], i64 [[INDVARS_IV_LVER_ORIG]]

 ; DEFAULT-NEXT:    [[ARRAYIDX2:%.*]] = getelementptr inbounds i32, i32* [[B]], i64 [[INDVARS_IV]]
 ; DEFAULT-NEXT:    [[LOAD_1:%.*]] = load i32, i32* [[ARRAYIDX2]], align 4
 ; DEFAULT-NEXT:    [[ADD]] = add i32 [[LOAD_1]], [[STORE_FORWARDED]]
 ; DEFAULT-NEXT:    [[INDVARS_IV_NEXT]] = add nuw nsw i64 [[INDVARS_IV]], 1
 ; DEFAULT-NEXT:    [[MUL_2:%.*]] = mul i64 [[INDVARS_IV_NEXT]], [[STRIDE_2]]
 ; DEFAULT-NEXT:    [[ARRAYIDX_NEXT:%.*]] = getelementptr inbounds i32, i32* [[A]], i64 [[MUL_2]]
 ; DEFAULT-NEXT:    store i32 [[ADD]], i32* [[ARRAYIDX_NEXT]], align 4
 ; DEFAULT-NEXT:    [[EXITCOND:%.*]] = icmp eq i64 [[INDVARS_IV_NEXT]], [[N]]
-; DEFAULT-NEXT:    br i1 [[EXITCOND]], label [[FOR_END_LOOPEXIT2:%.*]], label [[FOR_BODY]]
+; DEFAULT-NEXT:    br i1 [[EXITCOND]], label [[FOR_END_LOOPEXIT1:%.*]], label [[FOR_BODY]]
 ; DEFAULT:       for.end.loopexit:
 ; DEFAULT-NEXT:    br label [[FOR_END:%.*]]
-; DEFAULT:       for.end.loopexit2:
+; DEFAULT:       for.end.loopexit1:
 ; DEFAULT-NEXT:    br label [[FOR_END]]
 ; DEFAULT:       for.end:
 ; DEFAULT-NEXT:    ret void
 ;
 ; NO-VERSION-LABEL: @two_strides(
 ; NO-VERSION-NEXT:  entry:
 ; NO-VERSION-NEXT:    br label [[FOR_BODY:%.*]]
 ; NO-VERSION:       for.body: