Fix Transforms/IndVarsSimplify/2006-03-31-NegativeStride.ll and

PR726 by performing consistent signed division, not consistent unsigned
division when evaluating scev's.  Do not touch udivs.

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

diff --git a/include/llvm/Analysis/ScalarEvolutionExpander.h b/include/llvm/Analysis/ScalarEvolutionExpander.h
index e155e3b6273ec4c041f4483076c66d78d6dc31bb..36731120696b84a60ccdac21ad860dfee3b95f88 100644 (file)
--- a/include/llvm/Analysis/ScalarEvolutionExpander.h
+++ b/include/llvm/Analysis/ScalarEvolutionExpander.h
@@ -136,7 +136,7 @@ namespace llvm {
 
     Value *visitMulExpr(SCEVMulExpr *S);
 
-    Value *visitUDivExpr(SCEVUDivExpr *S) {
+    Value *visitSDivExpr(SCEVSDivExpr *S) {
       const Type *Ty = S->getType();
       Value *LHS = expandInTy(S->getLHS(), Ty);
       Value *RHS = expandInTy(S->getRHS(), Ty);

diff --git a/include/llvm/Analysis/ScalarEvolutionExpressions.h b/include/llvm/Analysis/ScalarEvolutionExpressions.h
index 43244c028aa98f6b01eb321bc26298915c482b82..2a546c34824f9273ff4a8ed87856a9d052d9e274 100644 (file)
--- a/include/llvm/Analysis/ScalarEvolutionExpressions.h
+++ b/include/llvm/Analysis/ScalarEvolutionExpressions.h
@@ -23,7 +23,7 @@ namespace llvm {
   enum SCEVTypes {
     // These should be ordered in terms of increasing complexity to make the
     // folders simpler.
-    scConstant, scTruncate, scZeroExtend, scAddExpr, scMulExpr, scUDivExpr,
+    scConstant, scTruncate, scZeroExtend, scAddExpr, scMulExpr, scSDivExpr,
     scAddRecExpr, scUnknown, scCouldNotCompute
   };
 
@@ -293,16 +293,16 @@ namespace llvm {
 
 
   //===--------------------------------------------------------------------===//
-  /// SCEVUDivExpr - This class represents a binary unsigned division operation.
+  /// SCEVSDivExpr - This class represents a binary unsigned division operation.
   ///
-  class SCEVUDivExpr : public SCEV {
+  class SCEVSDivExpr : public SCEV {
     SCEVHandle LHS, RHS;
-    SCEVUDivExpr(const SCEVHandle &lhs, const SCEVHandle &rhs)
-      : SCEV(scUDivExpr), LHS(lhs), RHS(rhs) {}
+    SCEVSDivExpr(const SCEVHandle &lhs, const SCEVHandle &rhs)
+      : SCEV(scSDivExpr), LHS(lhs), RHS(rhs) {}
 
-    virtual ~SCEVUDivExpr();
+    virtual ~SCEVSDivExpr();
   public:
-    /// get method - This just gets and returns a new SCEVUDiv object.
+    /// get method - This just gets and returns a new SCEVSDiv object.
     ///
     static SCEVHandle get(const SCEVHandle &LHS, const SCEVHandle &RHS);
 
@@ -334,9 +334,9 @@ namespace llvm {
     void print(std::ostream &OS) const;
 
     /// 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 SCEVSDivExpr *S) { return true; }
     static inline bool classof(const SCEV *S) {
-      return S->getSCEVType() == scUDivExpr;
+      return S->getSCEVType() == scSDivExpr;
     }
   };
 
@@ -496,8 +496,8 @@ namespace llvm {
         return ((SC*)this)->visitAddExpr((SCEVAddExpr*)S);
       case scMulExpr:
         return ((SC*)this)->visitMulExpr((SCEVMulExpr*)S);
-      case scUDivExpr:
-        return ((SC*)this)->visitUDivExpr((SCEVUDivExpr*)S);
+      case scSDivExpr:
+        return ((SC*)this)->visitSDivExpr((SCEVSDivExpr*)S);
       case scAddRecExpr:
         return ((SC*)this)->visitAddRecExpr((SCEVAddRecExpr*)S);
       case scUnknown:

diff --git a/lib/Analysis/ScalarEvolution.cpp b/lib/Analysis/ScalarEvolution.cpp
index b28d89c961e2a7ebd0536f20448f447efe36d7e8..f8b4ab9be133d4bf457c79644fe5b2f92f54b201 100644 (file)
--- a/lib/Analysis/ScalarEvolution.cpp
+++ b/lib/Analysis/ScalarEvolution.cpp
@@ -294,22 +294,22 @@ replaceSymbolicValuesWithConcrete(const SCEVHandle &Sym,
 }
 
 
-// SCEVUDivs - Only allow the creation of one SCEVUDivExpr for any particular
+// SCEVSDivs - Only allow the creation of one SCEVSDivExpr for any particular
 // input.  Don't use a SCEVHandle here, or else the object will never be
 // deleted!
-static std::map<std::pair<SCEV*, SCEV*>, SCEVUDivExpr*> SCEVUDivs;
+static std::map<std::pair<SCEV*, SCEV*>, SCEVSDivExpr*> SCEVSDivs;
 
-SCEVUDivExpr::~SCEVUDivExpr() {
-  SCEVUDivs.erase(std::make_pair(LHS, RHS));
+SCEVSDivExpr::~SCEVSDivExpr() {
+  SCEVSDivs.erase(std::make_pair(LHS, RHS));
 }
 
-void SCEVUDivExpr::print(std::ostream &OS) const {
-  OS << "(" << *LHS << " /u " << *RHS << ")";
+void SCEVSDivExpr::print(std::ostream &OS) const {
+  OS << "(" << *LHS << " /s " << *RHS << ")";
 }
 
-const Type *SCEVUDivExpr::getType() const {
+const Type *SCEVSDivExpr::getType() const {
   const Type *Ty = LHS->getType();
-  if (Ty->isSigned()) Ty = Ty->getUnsignedVersion();
+  if (Ty->isUnsigned()) Ty = Ty->getSignedVersion();
   return Ty;
 }
 
@@ -540,7 +540,7 @@ SCEVHandle SCEVAddRecExpr::evaluateAtIteration(SCEVHandle It) const {
   for (unsigned i = 1, e = getNumOperands(); i != e; ++i) {
     SCEVHandle BC = PartialFact(It, i);
     Divisor *= i;
-    SCEVHandle Val = SCEVUDivExpr::get(SCEVMulExpr::get(BC, getOperand(i)),
+    SCEVHandle Val = SCEVSDivExpr::get(SCEVMulExpr::get(BC, getOperand(i)),
                                        SCEVUnknown::getIntegerSCEV(Divisor,Ty));
     Result = SCEVAddExpr::get(Result, Val);
   }
@@ -982,20 +982,20 @@ SCEVHandle SCEVMulExpr::get(std::vector<SCEVHandle> &Ops) {
   return Result;
 }
 
-SCEVHandle SCEVUDivExpr::get(const SCEVHandle &LHS, const SCEVHandle &RHS) {
+SCEVHandle SCEVSDivExpr::get(const SCEVHandle &LHS, const SCEVHandle &RHS) {
   if (SCEVConstant *RHSC = dyn_cast<SCEVConstant>(RHS)) {
     if (RHSC->getValue()->equalsInt(1))
-      return LHS;                            // X /u 1 --> x
+      return LHS;                            // X /s 1 --> x
     if (RHSC->getValue()->isAllOnesValue())
-      return SCEV::getNegativeSCEV(LHS);           // X /u -1  -->  -x
+      return SCEV::getNegativeSCEV(LHS);           // X /s -1  -->  -x
 
     if (SCEVConstant *LHSC = dyn_cast<SCEVConstant>(LHS)) {
       Constant *LHSCV = LHSC->getValue();
       Constant *RHSCV = RHSC->getValue();
-      if (LHSCV->getType()->isSigned())
+      if (LHSCV->getType()->isUnsigned())
         LHSCV = ConstantExpr::getCast(LHSCV,
-                                      LHSCV->getType()->getUnsignedVersion());
-      if (RHSCV->getType()->isSigned())
+                                      LHSCV->getType()->getSignedVersion());
+      if (RHSCV->getType()->isUnsigned())
         RHSCV = ConstantExpr::getCast(RHSCV, LHSCV->getType());
       return SCEVUnknown::get(ConstantExpr::getDiv(LHSCV, RHSCV));
     }
@@ -1003,8 +1003,8 @@ SCEVHandle SCEVUDivExpr::get(const SCEVHandle &LHS, const SCEVHandle &RHS) {
 
   // 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);
+  SCEVSDivExpr *&Result = SCEVSDivs[std::make_pair(LHS, RHS)];
+  if (Result == 0) Result = new SCEVSDivExpr(LHS, RHS);
   return Result;
 }
 
@@ -1356,8 +1356,8 @@ SCEVHandle ScalarEvolutionsImpl::createSCEV(Value *V) {
       return SCEVMulExpr::get(getSCEV(I->getOperand(0)),
                               getSCEV(I->getOperand(1)));
     case Instruction::Div:
-      if (V->getType()->isInteger() && V->getType()->isUnsigned())
-        return SCEVUDivExpr::get(getSCEV(I->getOperand(0)),
+      if (V->getType()->isInteger() && V->getType()->isSigned())
+        return SCEVSDivExpr::get(getSCEV(I->getOperand(0)),
                                  getSCEV(I->getOperand(1)));
       break;
 
@@ -1376,10 +1376,10 @@ SCEVHandle ScalarEvolutionsImpl::createSCEV(Value *V) {
 
     case Instruction::Shr:
       if (ConstantUInt *SA = dyn_cast<ConstantUInt>(I->getOperand(1)))
-        if (V->getType()->isUnsigned()) {
+        if (V->getType()->isSigned()) {
           Constant *X = ConstantInt::get(V->getType(), 1);
           X = ConstantExpr::getShl(X, SA);
-          return SCEVUDivExpr::get(getSCEV(I->getOperand(0)), getSCEV(X));
+          return SCEVSDivExpr::get(getSCEV(I->getOperand(0)), getSCEV(X));
         }
       break;
 
@@ -1982,14 +1982,14 @@ SCEVHandle ScalarEvolutionsImpl::getSCEVAtScope(SCEV *V, const Loop *L) {
     return Comm;
   }
 
-  if (SCEVUDivExpr *UDiv = dyn_cast<SCEVUDivExpr>(V)) {
-    SCEVHandle LHS = getSCEVAtScope(UDiv->getLHS(), L);
+  if (SCEVSDivExpr *Div = dyn_cast<SCEVSDivExpr>(V)) {
+    SCEVHandle LHS = getSCEVAtScope(Div->getLHS(), L);
     if (LHS == UnknownValue) return LHS;
-    SCEVHandle RHS = getSCEVAtScope(UDiv->getRHS(), L);
+    SCEVHandle RHS = getSCEVAtScope(Div->getRHS(), L);
     if (RHS == UnknownValue) return RHS;
-    if (LHS == UDiv->getLHS() && RHS == UDiv->getRHS())
-      return UDiv;   // must be loop invariant
-    return SCEVUDivExpr::get(LHS, RHS);
+    if (LHS == Div->getLHS() && RHS == Div->getRHS())
+      return Div;   // must be loop invariant
+    return SCEVSDivExpr::get(LHS, RHS);
   }
 
   // If this is a loop recurrence for a loop that does not contain L, then we