Fix PR1798 - an error in the evaluation of SCEVAddRecExpr at an

arbitrary iteration.

The patch:
1) changes SCEVSDivExpr into SCEVUDivExpr,
2) replaces PartialFact() function with BinomialCoefficient(); the 
computations (essentially, the division) in BinomialCoefficient() are 
performed with the apprioprate bitwidth necessary to avoid overflow; 
unsigned division is used instead of the signed one.

Computations in BinomialCoefficient() require support from the code 
generator for APInts. Currently, we use a hack rounding up the 
neccessary bitwidth to the nearest power of 2. The hack is easy to turn 
off in future.

One remaining issue: we assume the divisor of the binomial coefficient 
formula can be computed accurately using 16 bits. It means we can handle 
AddRecs of length up to 9. In future, we should use APInts to evaluate 
the divisor.

Thanks to Nicholas for cooperation!


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

3 files changed, 14 insertions, 14 deletions

diff --git a/include/llvm/Analysis/ScalarEvolution.h b/include/llvm/Analysis/ScalarEvolution.h
index b1cd287c7e..ecf28adfc8 100644
--- a/include/llvm/Analysis/ScalarEvolution.h
+++ b/include/llvm/Analysis/ScalarEvolution.h
@@ -225,7 +225,7 @@ namespace llvm {
       Ops.push_back(RHS);
       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 4470c9c173..530ce37880 100644
--- a/include/llvm/Analysis/ScalarEvolutionExpander.h
+++ b/include/llvm/Analysis/ScalarEvolutionExpander.h
@@ -126,10 +126,10 @@ namespace llvm {
 
     Value *visitMulExpr(SCEVMulExpr *S);
 
-    Value *visitSDivExpr(SCEVSDivExpr *S) {
+    Value *visitUDivExpr(SCEVUDivExpr *S) {
       Value *LHS = expand(S->getLHS());
       Value *RHS = expand(S->getRHS());
-      return InsertBinop(Instruction::SDiv, LHS, RHS, InsertPt);
+      return InsertBinop(Instruction::UDiv, LHS, RHS, InsertPt);
     }
 
     Value *visitAddRecExpr(SCEVAddRecExpr *S);
diff --git a/include/llvm/Analysis/ScalarEvolutionExpressions.h b/include/llvm/Analysis/ScalarEvolutionExpressions.h
index 6564d636b3..409ad9ecc4 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, scSMaxExpr, scUnknown, scCouldNotCompute
+    scUDivExpr, scAddRecExpr, scSMaxExpr, scUnknown, scCouldNotCompute
   };
 
   //===--------------------------------------------------------------------===//
@@ -322,16 +322,16 @@ namespace llvm {
 
 
   //===--------------------------------------------------------------------===//
-  /// SCEVSDivExpr - This class represents a binary signed division operation.
+  /// SCEVUDivExpr - This class represents a binary unsigned division operation.
   ///
-  class SCEVSDivExpr : public SCEV {
+  class SCEVUDivExpr : public SCEV {
     friend class ScalarEvolution;
 
     SCEVHandle LHS, RHS;
-    SCEVSDivExpr(const SCEVHandle &lhs, const SCEVHandle &rhs)
-      : SCEV(scSDivExpr), LHS(lhs), RHS(rhs) {}
+    SCEVUDivExpr(const SCEVHandle &lhs, const SCEVHandle &rhs)
+      : SCEV(scUDivExpr), LHS(lhs), RHS(rhs) {}
 
-    virtual ~SCEVSDivExpr();
+    virtual ~SCEVUDivExpr();
   public:
     const SCEVHandle &getLHS() const { return LHS; }
     const SCEVHandle &getRHS() const { return RHS; }
@@ -353,7 +353,7 @@ namespace llvm {
       if (L == LHS && R == RHS)
         return this;
       else
-        return SE.getSDivExpr(L, R);
+        return SE.getUDivExpr(L, R);
     }
 
 
@@ -363,9 +363,9 @@ namespace llvm {
     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 SCEVSDivExpr *S) { return true; }
+    static inline bool classof(const SCEVUDivExpr *S) { return true; }
     static inline bool classof(const SCEV *S) {
-      return S->getSCEVType() == scSDivExpr;
+      return S->getSCEVType() == scUDivExpr;
     }
   };
 
@@ -540,8 +540,8 @@ namespace llvm {
         return ((SC*)this)->visitAddExpr((SCEVAddExpr*)S);
       case scMulExpr:
         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 scSMaxExpr: