Remove the Expr member from IVUsers. Instead of remembering the expression,

just ask ScalarEvolution for it on demand. This helps IVUsers be more robust
in the case of expressions changing underneath it. This fixes PR6862.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@101819 91177308-0d34-0410-b5e6-96231b3b80d8

diff --git a/include/llvm/Analysis/IVUsers.h b/include/llvm/Analysis/IVUsers.h
index a887c830c954ce4f5057b56dc71cf110bdf72432..578e6aba8338521203b1ec760193012680c32c98 100644 (file)
--- a/include/llvm/Analysis/IVUsers.h
+++ b/include/llvm/Analysis/IVUsers.h
@@ -36,9 +36,8 @@ class IVUsers;
 class IVStrideUse : public CallbackVH, public ilist_node<IVStrideUse> {
   friend class IVUsers;
 public:
-  IVStrideUse(IVUsers *P, const SCEV *E,
-              Instruction* U, Value *O)
-    : CallbackVH(U), Parent(P), Expr(E), OperandValToReplace(O) {
+  IVStrideUse(IVUsers *P, Instruction* U, Value *O)
+    : CallbackVH(U), Parent(P), OperandValToReplace(O) {
   }
 
   /// getUser - Return the user instruction for this use.
@@ -51,20 +50,6 @@ public:
     setValPtr(NewUser);
   }
 
-  /// getParent - Return a pointer to the IVUsers that owns
-  /// this IVStrideUse.
-  IVUsers *getParent() const { return Parent; }
-
-  /// getExpr - Return the expression for the use.
-  const SCEV *getExpr() const { return Expr; }
-
-  /// setExpr - Assign a new expression to this use.
-  void setExpr(const SCEV *Val) {
-    Expr = Val;
-  }
-
-  const SCEV *getStride(const Loop *L) const;
-
   /// getOperandValToReplace - Return the Value of the operand in the user
   /// instruction that this IVStrideUse is representing.
   Value *getOperandValToReplace() const {
@@ -91,9 +76,6 @@ private:
   /// Parent - a pointer to the IVUsers that owns this IVStrideUse.
   IVUsers *Parent;
 
-  /// Expr - The expression for this use.
-  const SCEV *Expr;
-
   /// OperandValToReplace - The Value of the operand in the user instruction
   /// that this IVStrideUse is representing.
   WeakVH OperandValToReplace;
@@ -161,12 +143,16 @@ public:
   /// return true.  Otherwise, return false.
   bool AddUsersIfInteresting(Instruction *I);
 
-  IVStrideUse &AddUser(const SCEV *Expr,
-                       Instruction *User, Value *Operand);
+  IVStrideUse &AddUser(Instruction *User, Value *Operand);
 
   /// getReplacementExpr - Return a SCEV expression which computes the
   /// value of the OperandValToReplace of the given IVStrideUse.
-  const SCEV *getReplacementExpr(const IVStrideUse &U) const;
+  const SCEV *getReplacementExpr(const IVStrideUse &IU) const;
+
+  /// getExpr - Return the expression for the use.
+  const SCEV *getExpr(const IVStrideUse &IU) const;
+
+  const SCEV *getStride(const IVStrideUse &IU, const Loop *L) const;
 
   typedef ilist<IVStrideUse>::iterator iterator;
   typedef ilist<IVStrideUse>::const_iterator const_iterator;

diff --git a/lib/Analysis/IVUsers.cpp b/lib/Analysis/IVUsers.cpp
index fbd3e7071275ec61948a494b324ad1ee5a2b6c05..2c997dae5859ce35fab3fb6144709e93e822a9cf 100644 (file)
--- a/lib/Analysis/IVUsers.cpp
+++ b/lib/Analysis/IVUsers.cpp
@@ -122,23 +122,21 @@ bool IVUsers::AddUsersIfInteresting(Instruction *I) {
 
     if (AddUserToIVUsers) {
       // Okay, we found a user that we cannot reduce.
-      IVUses.push_back(new IVStrideUse(this, ISE, User, I));
+      IVUses.push_back(new IVStrideUse(this, User, I));
       IVStrideUse &NewUse = IVUses.back();
       // Transform the expression into a normalized form.
-      NewUse.Expr =
-        TransformForPostIncUse(NormalizeAutodetect, NewUse.Expr,
-                               User, I,
-                               NewUse.PostIncLoops,
-                               *SE, *DT);
-      DEBUG(dbgs() << "   NORMALIZED TO: " << *NewUse.Expr << '\n');
+      ISE = TransformForPostIncUse(NormalizeAutodetect,
+                                   ISE, User, I,
+                                   NewUse.PostIncLoops,
+                                   *SE, *DT);
+      DEBUG(dbgs() << "   NORMALIZED TO: " << *ISE << '\n');
     }
   }
   return true;
 }
 
-IVStrideUse &IVUsers::AddUser(const SCEV *Expr,
-                              Instruction *User, Value *Operand) {
-  IVUses.push_back(new IVStrideUse(this, Expr, User, Operand));
+IVStrideUse &IVUsers::AddUser(Instruction *User, Value *Operand) {
+  IVUses.push_back(new IVStrideUse(this, User, Operand));
   return IVUses.back();
 }
 
@@ -169,15 +167,6 @@ bool IVUsers::runOnLoop(Loop *l, LPPassManager &LPM) {
   return false;
 }
 
-/// getReplacementExpr - Return a SCEV expression which computes the
-/// value of the OperandValToReplace of the given IVStrideUse.
-const SCEV *IVUsers::getReplacementExpr(const IVStrideUse &U) const {
-  PostIncLoopSet &Loops = const_cast<PostIncLoopSet &>(U.PostIncLoops);
-  return TransformForPostIncUse(Denormalize, U.getExpr(),
-                                U.getUser(), U.getOperandValToReplace(),
-                                Loops, *SE, *DT);
-}
-
 void IVUsers::print(raw_ostream &OS, const Module *M) const {
   OS << "IV Users for loop ";
   WriteAsOperand(OS, L->getHeader(), false);
@@ -194,8 +183,7 @@ void IVUsers::print(raw_ostream &OS, const Module *M) const {
        E = IVUses.end(); UI != E; ++UI) {
     OS << "  ";
     WriteAsOperand(OS, UI->getOperandValToReplace(), false);
-    OS << " = "
-       << *getReplacementExpr(*UI);
+    OS << " = " << *getReplacementExpr(*UI);
     for (PostIncLoopSet::const_iterator
          I = UI->PostIncLoops.begin(),
          E = UI->PostIncLoops.end(); I != E; ++I) {
@@ -218,6 +206,21 @@ void IVUsers::releaseMemory() {
   IVUses.clear();
 }
 
+/// getReplacementExpr - Return a SCEV expression which computes the
+/// value of the OperandValToReplace.
+const SCEV *IVUsers::getReplacementExpr(const IVStrideUse &IU) const {
+  return SE->getSCEV(IU.getOperandValToReplace());
+}
+
+/// getExpr - Return the expression for the use.
+const SCEV *IVUsers::getExpr(const IVStrideUse &IU) const {
+  return
+    TransformForPostIncUse(Normalize, getReplacementExpr(IU),
+                           IU.getUser(), IU.getOperandValToReplace(),
+                           const_cast<PostIncLoopSet &>(IU.getPostIncLoops()),
+                           *SE, *DT);
+}
+
 static const SCEVAddRecExpr *findAddRecForLoop(const SCEV *S, const Loop *L) {
   if (const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(S)) {
     if (AR->getLoop() == L)
@@ -236,18 +239,13 @@ static const SCEVAddRecExpr *findAddRecForLoop(const SCEV *S, const Loop *L) {
   return 0;
 }
 
-const SCEV *IVStrideUse::getStride(const Loop *L) const {
-  if (const SCEVAddRecExpr *AR = findAddRecForLoop(getExpr(), L))
-    return AR->getStepRecurrence(*Parent->SE);
+const SCEV *IVUsers::getStride(const IVStrideUse &IU, const Loop *L) const {
+  if (const SCEVAddRecExpr *AR = findAddRecForLoop(getExpr(IU), L))
+    return AR->getStepRecurrence(*SE);
   return 0;
 }
 
 void IVStrideUse::transformToPostInc(const Loop *L) {
-  PostIncLoopSet Loops;
-  Loops.insert(L);
-  Expr = TransformForPostIncUse(Normalize, Expr,
-                                getUser(), getOperandValToReplace(),
-                                Loops, *Parent->SE, *Parent->DT);
   PostIncLoops.insert(L);
 }
 

diff --git a/lib/Transforms/Scalar/LoopStrengthReduce.cpp b/lib/Transforms/Scalar/LoopStrengthReduce.cpp
index 19f78f424ce9a830ad4cf497f95502d88d56137c..a09bca89976cc3142d3540f807012e8f3428059c 100644 (file)
--- a/lib/Transforms/Scalar/LoopStrengthReduce.cpp
+++ b/lib/Transforms/Scalar/LoopStrengthReduce.cpp
@@ -1575,8 +1575,8 @@ LSRInstance::OptimizeLoopTermCond() {
             !DT.properlyDominates(UI->getUser()->getParent(), ExitingBlock)) {
           // Conservatively assume there may be reuse if the quotient of their
           // strides could be a legal scale.
-          const SCEV *A = CondUse->getStride(L);
-          const SCEV *B = UI->getStride(L);
+          const SCEV *A = IU.getStride(*CondUse, L);
+          const SCEV *B = IU.getStride(*UI, L);
           if (!A || !B) continue;
           if (SE.getTypeSizeInBits(A->getType()) !=
               SE.getTypeSizeInBits(B->getType())) {
@@ -1629,8 +1629,7 @@ LSRInstance::OptimizeLoopTermCond() {
         ExitingBlock->getInstList().insert(TermBr, Cond);
 
         // Clone the IVUse, as the old use still exists!
-        CondUse = &IU.AddUser(CondUse->getExpr(),
-                              Cond, CondUse->getOperandValToReplace());
+        CondUse = &IU.AddUser(Cond, CondUse->getOperandValToReplace());
         TermBr->replaceUsesOfWith(OldCond, Cond);
       }
     }
@@ -1748,7 +1747,7 @@ void LSRInstance::CollectInterestingTypesAndFactors() {
   // Collect interesting types and strides.
   SmallVector<const SCEV *, 4> Worklist;
   for (IVUsers::const_iterator UI = IU.begin(), E = IU.end(); UI != E; ++UI) {
-    const SCEV *Expr = UI->getExpr();
+    const SCEV *Expr = IU.getExpr(*UI);
 
     // Collect interesting types.
     Types.insert(SE.getEffectiveSCEVType(Expr->getType()));
@@ -1819,7 +1818,7 @@ void LSRInstance::CollectFixupsAndInitialFormulae() {
       AccessTy = getAccessType(LF.UserInst);
     }
 
-    const SCEV *S = UI->getExpr();
+    const SCEV *S = IU.getExpr(*UI);
 
     // Equality (== and !=) ICmps are special. We can rewrite (i == N) as
     // (N - i == 0), and this allows (N - i) to be the expression that we work

diff --git a/test/Transforms/IndVarSimplify/eliminate-comparison.ll b/test/Transforms/IndVarSimplify/eliminate-comparison.ll
index 93466496828bcb8bf72eefb53440a0c8ab7c1946..953bbdff5c62de3db4a3503c7504f6238aed35a4 100644 (file)
--- a/test/Transforms/IndVarSimplify/eliminate-comparison.ll
+++ b/test/Transforms/IndVarSimplify/eliminate-comparison.ll
@@ -82,3 +82,27 @@ bb20.loopexit:
   %tmp.0.ph = phi i32 [ 0, %bb18 ], [ 1, %bb15 ], [ 0, %bb13 ]
   ret i32 %tmp.0.ph
 }
+
+; Indvars should eliminate the icmp here.
+
+; CHECK: @func_10
+; CHECK-NOT: icmp
+; CHECK: ret void
+
+define void @func_10() nounwind {
+entry:
+  br label %loop
+
+loop:
+  %i = phi i32 [ %i.next, %loop ], [ 0, %entry ]
+  %t0 = icmp slt i32 %i, 0
+  %t1 = zext i1 %t0 to i32
+  %t2 = add i32 %t1, %i
+  %u3 = zext i32 %t2 to i64
+  store i64 %u3, i64* null
+  %i.next = add i32 %i, 1
+  br i1 undef, label %loop, label %return
+
+return:
+  ret void
+}