Switch on the use of arbitrary precision integers in scalar evolution. This will

bail after 256-bits to avoid producing code that the backends can't handle.
Previously, we capped it at 64-bits, preferring to miscompile in those cases.

This change also reverts much of r52248 because the invariants the code was
expecting are now being met.


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

1 files changed, 8 insertions, 22 deletions

diff --git a/lib/Analysis/ScalarEvolution.cpp b/lib/Analysis/ScalarEvolution.cpp
index 737d9b3823..dc1129469d 100644
--- a/lib/Analysis/ScalarEvolution.cpp
+++ b/lib/Analysis/ScalarEvolution.cpp
@@ -538,20 +538,12 @@ static SCEVHandle BinomialCoefficient(SCEVHandle It, unsigned K,
 
   assert(K < 9 && "We cannot handle such long AddRecs yet.");
   
-  // FIXME: A temporary hack to remove in future.  Arbitrary precision integers
-  // aren't supported by the code generator yet.  For the dividend, the bitwidth
-  // we use is the smallest power of 2 greater or equal to K*W and less or equal
-  // to 64.  Note that setting the upper bound for bitwidth may still lead to
-  // miscompilation in some cases.
-  unsigned DividendBits = 1U << Log2_32_Ceil(K * It->getBitWidth());
-  if (DividendBits > 64)
-    DividendBits = 64;
-#if 0 // Waiting for the APInt support in the code generator...
   unsigned DividendBits = K * It->getBitWidth();
-#endif
+  if (DividendBits > 256)
+    return new SCEVCouldNotCompute();
 
   const IntegerType *DividendTy = IntegerType::get(DividendBits);
-  const SCEVHandle ExIt = SE.getTruncateOrZeroExtend(It, DividendTy);
+  const SCEVHandle ExIt = SE.getZeroExtendExpr(It, DividendTy);
 
   // The final number of bits we need to perform the division is the maximum of
   // dividend and divisor bitwidths.
@@ -573,12 +565,7 @@ static SCEVHandle BinomialCoefficient(SCEVHandle It, unsigned K,
       Dividend *= N-(K-1);
     if (DividendTy != DivisionTy)
       Dividend = Dividend.zext(DivisionTy->getBitWidth());
-
-    APInt Result = Dividend.udiv(Divisor);
-    if (Result.getBitWidth() != It->getBitWidth())
-      Result = Result.trunc(It->getBitWidth());
-
-    return SE.getConstant(Result);
+    return SE.getConstant(Dividend.udiv(Divisor).trunc(It->getBitWidth()));
   }
   
   SCEVHandle Dividend = ExIt;
@@ -587,11 +574,10 @@ static SCEVHandle BinomialCoefficient(SCEVHandle It, unsigned K,
       SE.getMulExpr(Dividend,
                     SE.getMinusSCEV(ExIt, SE.getIntegerSCEV(i, DividendTy)));
 
-  return SE.getTruncateOrZeroExtend(
-             SE.getUDivExpr(
-                 SE.getTruncateOrZeroExtend(Dividend, DivisionTy),
-                 SE.getConstant(Divisor)
-             ), It->getType());
+  if (DividendTy != DivisionTy)
+    Dividend = SE.getZeroExtendExpr(Dividend, DivisionTy);
+  return SE.getTruncateExpr(SE.getUDivExpr(Dividend, SE.getConstant(Divisor)),
+                            It->getType());
 }
 
 /// evaluateAtIteration - Return the value of this chain of recurrences at