Fix handling of overflow in loop calculation by adding new UDiv SCEV. This SCEV

is disabled in the sense that it will refuse to create one from a UDiv
instruction, until the code is better tested.


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

5 files changed, 134 insertions, 5 deletions

diff --git a/include/llvm/Analysis/ScalarEvolution.h b/include/llvm/Analysis/ScalarEvolution.h
index a52f273b2c..a51a63f1bc 100644
--- a/include/llvm/Analysis/ScalarEvolution.h
+++ b/include/llvm/Analysis/ScalarEvolution.h
@@ -226,6 +226,7 @@ namespace llvm {
       return getMulExpr(Ops);
     }
     SCEVHandle getSDivExpr(const SCEVHandle &LHS, const SCEVHandle &RHS);
+    SCEVHandle getUDivExpr(const SCEVHandle &LHS, const SCEVHandle &RHS);
     SCEVHandle getAddRecExpr(const SCEVHandle &Start, const SCEVHandle &Step,
                              const Loop *L);
     SCEVHandle getAddRecExpr(std::vector<SCEVHandle> &Operands,
diff --git a/include/llvm/Analysis/ScalarEvolutionExpander.h b/include/llvm/Analysis/ScalarEvolutionExpander.h
index 8582067e10..3cd5ea5269 100644
--- a/include/llvm/Analysis/ScalarEvolutionExpander.h
+++ b/include/llvm/Analysis/ScalarEvolutionExpander.h
@@ -132,6 +132,12 @@ namespace llvm {
       return InsertBinop(Instruction::SDiv, LHS, RHS, InsertPt);
     }
 
+    Value *visitUDivExpr(SCEVUDivExpr *S) {
+      Value *LHS = expand(S->getLHS());
+      Value *RHS = expand(S->getRHS());
+      return InsertBinop(Instruction::UDiv, LHS, RHS, InsertPt);
+    }
+
     Value *visitAddRecExpr(SCEVAddRecExpr *S);
 
     Value *visitUnknown(SCEVUnknown *S) {
diff --git a/include/llvm/Analysis/ScalarEvolutionExpressions.h b/include/llvm/Analysis/ScalarEvolutionExpressions.h
index 7fbeff7de0..7034b6eea6 100644
--- a/include/llvm/Analysis/ScalarEvolutionExpressions.h
+++ b/include/llvm/Analysis/ScalarEvolutionExpressions.h
@@ -25,7 +25,7 @@ namespace llvm {
     // These should be ordered in terms of increasing complexity to make the
     // folders simpler.
     scConstant, scTruncate, scZeroExtend, scSignExtend, scAddExpr, scMulExpr,
-    scSDivExpr, scAddRecExpr, scUnknown, scCouldNotCompute
+    scSDivExpr, scUDivExpr, scAddRecExpr, scUnknown, scCouldNotCompute
   };
 
   //===--------------------------------------------------------------------===//
@@ -370,6 +370,55 @@ namespace llvm {
 
 
   //===--------------------------------------------------------------------===//
+  /// SCEVUDivExpr - This class represents a binary unsigned division operation.
+  ///
+  class SCEVUDivExpr : public SCEV {
+    friend class ScalarEvolution;
+
+    SCEVHandle LHS, RHS;
+    SCEVUDivExpr(const SCEVHandle &lhs, const SCEVHandle &rhs)
+      : SCEV(scUDivExpr), LHS(lhs), RHS(rhs) {}
+
+    virtual ~SCEVUDivExpr();
+  public:
+    const SCEVHandle &getLHS() const { return LHS; }
+    const SCEVHandle &getRHS() const { return RHS; }
+
+    virtual bool isLoopInvariant(const Loop *L) const {
+      return LHS->isLoopInvariant(L) && RHS->isLoopInvariant(L);
+    }
+
+    virtual bool hasComputableLoopEvolution(const Loop *L) const {
+      return LHS->hasComputableLoopEvolution(L) &&
+             RHS->hasComputableLoopEvolution(L);
+    }
+
+    SCEVHandle replaceSymbolicValuesWithConcrete(const SCEVHandle &Sym,
+                                                 const SCEVHandle &Conc,
+                                                 ScalarEvolution &SE) const {
+      SCEVHandle L = LHS->replaceSymbolicValuesWithConcrete(Sym, Conc, SE);
+      SCEVHandle R = RHS->replaceSymbolicValuesWithConcrete(Sym, Conc, SE);
+      if (L == LHS && R == RHS)
+        return this;
+      else
+        return SE.getUDivExpr(L, R);
+    }
+
+
+    virtual const Type *getType() const;
+
+    void print(std::ostream &OS) const;
+    void print(std::ostream *OS) const { if (OS) print(*OS); }
+
+    /// Methods for support type inquiry through isa, cast, and dyn_cast:
+    static inline bool classof(const SCEVUDivExpr *S) { return true; }
+    static inline bool classof(const SCEV *S) {
+      return S->getSCEVType() == scUDivExpr;
+    }
+  };
+
+
+  //===--------------------------------------------------------------------===//
   /// SCEVAddRecExpr - This node represents a polynomial recurrence on the trip
   /// count of the specified loop.
   ///
@@ -519,6 +568,8 @@ namespace llvm {
         return ((SC*)this)->visitMulExpr((SCEVMulExpr*)S);
       case scSDivExpr:
         return ((SC*)this)->visitSDivExpr((SCEVSDivExpr*)S);
+      case scUDivExpr:
+        return ((SC*)this)->visitUDivExpr((SCEVUDivExpr*)S);
       case scAddRecExpr:
         return ((SC*)this)->visitAddRecExpr((SCEVAddRecExpr*)S);
       case scUnknown:
diff --git a/lib/Analysis/ScalarEvolution.cpp b/lib/Analysis/ScalarEvolution.cpp
index 6c91dca330..70321facde 100644
--- a/lib/Analysis/ScalarEvolution.cpp
+++ b/lib/Analysis/ScalarEvolution.cpp
@@ -344,6 +344,24 @@ const Type *SCEVSDivExpr::getType() const {
   return LHS->getType();
 }
 
+// SCEVUDivs - Only allow the creation of one SCEVUDivExpr for any particular
+// input.  Don't use a SCEVHandle here, or else the object will never be
+// deleted!
+static ManagedStatic<std::map<std::pair<SCEV*, SCEV*>, 
+                     SCEVUDivExpr*> > SCEVUDivs;
+
+SCEVUDivExpr::~SCEVUDivExpr() {
+  SCEVUDivs->erase(std::make_pair(LHS, RHS));
+}
+
+void SCEVUDivExpr::print(std::ostream &OS) const {
+  OS << "(" << *LHS << " /u " << *RHS << ")";
+}
+
+const Type *SCEVUDivExpr::getType() const {
+  return LHS->getType();
+}
+
 // SCEVAddRecExprs - Only allow the creation of one SCEVAddRecExpr for any
 // particular input.  Don't use a SCEVHandle here, or else the object will never
 // be deleted!
@@ -573,7 +591,7 @@ SCEVHandle SCEVAddRecExpr::evaluateAtIteration(SCEVHandle It,
   for (unsigned i = 1, e = getNumOperands(); i != e; ++i) {
     SCEVHandle BC = PartialFact(It, i, SE);
     Divisor *= i;
-    SCEVHandle Val = SE.getSDivExpr(SE.getMulExpr(BC, getOperand(i)),
+    SCEVHandle Val = SE.getUDivExpr(SE.getMulExpr(BC, getOperand(i)),
                                     SE.getIntegerSCEV(Divisor,Ty));
     Result = SE.getAddExpr(Result, Val);
   }
@@ -1037,7 +1055,8 @@ SCEVHandle ScalarEvolution::getMulExpr(std::vector<SCEVHandle> &Ops) {
   return Result;
 }
 
-SCEVHandle ScalarEvolution::getSDivExpr(const SCEVHandle &LHS, const SCEVHandle &RHS) {
+SCEVHandle ScalarEvolution::getSDivExpr(const SCEVHandle &LHS,
+                                        const SCEVHandle &RHS) {
   if (SCEVConstant *RHSC = dyn_cast<SCEVConstant>(RHS)) {
     if (RHSC->getValue()->equalsInt(1))
       return LHS;                            // X sdiv 1 --> x
@@ -1058,6 +1077,26 @@ SCEVHandle ScalarEvolution::getSDivExpr(const SCEVHandle &LHS, const SCEVHandle
   return Result;
 }
 
+SCEVHandle ScalarEvolution::getUDivExpr(const SCEVHandle &LHS,
+                                        const SCEVHandle &RHS) {
+  if (SCEVConstant *RHSC = dyn_cast<SCEVConstant>(RHS)) {
+    if (RHSC->getValue()->equalsInt(1))
+      return LHS;                            // X udiv 1 --> x
+
+    if (SCEVConstant *LHSC = dyn_cast<SCEVConstant>(LHS)) {
+      Constant *LHSCV = LHSC->getValue();
+      Constant *RHSCV = RHSC->getValue();
+      return getUnknown(ConstantExpr::getUDiv(LHSCV, RHSCV));
+    }
+  }
+
+  // FIXME: implement folding of (X*4)/4 when we know X*4 doesn't overflow.
+
+  SCEVUDivExpr *&Result = (*SCEVUDivs)[std::make_pair(LHS, RHS)];
+  if (Result == 0) Result = new SCEVUDivExpr(LHS, RHS);
+  return Result;
+}
+
 
 /// SCEVAddRecExpr::get - Get a add recurrence expression for the
 /// specified loop.  Simplify the expression as much as possible.
@@ -1484,8 +1523,6 @@ SCEVHandle ScalarEvolutionsImpl::createSCEV(Value *V) {
     case Instruction::SDiv:
       return SE.getSDivExpr(getSCEV(I->getOperand(0)),
                             getSCEV(I->getOperand(1)));
-      break;
-
     case Instruction::Sub:
       return SE.getMinusSCEV(getSCEV(I->getOperand(0)),
                              getSCEV(I->getOperand(1)));
@@ -2145,6 +2182,16 @@ SCEVHandle ScalarEvolutionsImpl::getSCEVAtScope(SCEV *V, const Loop *L) {
     return SE.getSDivExpr(LHS, RHS);
   }
 
+  if (SCEVUDivExpr *Div = dyn_cast<SCEVUDivExpr>(V)) {
+    SCEVHandle LHS = getSCEVAtScope(Div->getLHS(), L);
+    if (LHS == UnknownValue) return LHS;
+    SCEVHandle RHS = getSCEVAtScope(Div->getRHS(), L);
+    if (RHS == UnknownValue) return RHS;
+    if (LHS == Div->getLHS() && RHS == Div->getRHS())
+      return Div;   // must be loop invariant
+    return SE.getUDivExpr(LHS, RHS);
+  }
+
   // If this is a loop recurrence for a loop that does not contain L, then we
   // are dealing with the final value computed by the loop.
   if (SCEVAddRecExpr *AddRec = dyn_cast<SCEVAddRecExpr>(V)) {
diff --git a/test/Analysis/ScalarEvolution/2007-11-14-SignedAddRec.ll b/test/Analysis/ScalarEvolution/2007-11-14-SignedAddRec.ll
new file mode 100644
index 0000000000..66ca7551c2
--- /dev/null
+++ b/test/Analysis/ScalarEvolution/2007-11-14-SignedAddRec.ll
@@ -0,0 +1,24 @@
+; RUN: llvm-as < %s | opt -indvars | llvm-dis | grep printd | grep 1206807378
+; PR1798
+
+declare void @printd(i32)
+
+define i32 @test() {
+entry:
+	br label %bb6
+
+bb:		; preds = %bb6
+	%tmp3 = add i32 %x.0, %i.0		; <i32> [#uses=1]
+	%tmp5 = add i32 %i.0, 1		; <i32> [#uses=1]
+	br label %bb6
+
+bb6:		; preds = %bb, %entry
+	%i.0 = phi i32 [ 0, %entry ], [ %tmp5, %bb ]		; <i32> [#uses=3]
+	%x.0 = phi i32 [ 0, %entry ], [ %tmp3, %bb ]		; <i32> [#uses=3]
+	%tmp8 = icmp slt i32 %i.0, 123456789		; <i1> [#uses=1]
+	br i1 %tmp8, label %bb, label %bb10
+
+bb10:		; preds = %bb6
+	call void @printd(i32 %x.0)
+	ret i32 0
+}