From 2ceb40f3da2290d37e9a4faa35bd5199e5dc90d5 Mon Sep 17 00:00:00 2001 From: Nick Lewycky Date: Mon, 21 Jul 2008 02:51:31 +0000 Subject: [PATCH] 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 --- lib/Analysis/ScalarEvolution.cpp | 30 ++++++++---------------------- 1 file changed, 8 insertions(+), 22 deletions(-) diff --git a/lib/Analysis/ScalarEvolution.cpp b/lib/Analysis/ScalarEvolution.cpp index 737d9b3823e..dc1129469d8 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 -- 2.34.1