From 6f8abf929ac173872cc50aff767bc25f2a07a523 Mon Sep 17 00:00:00 2001 From: Nick Lewycky Date: Fri, 13 Jun 2008 04:38:55 +0000 Subject: [PATCH] Crash less. The i64 restriction in BinomialCoefficient caused some problems with code that was expecting different bit widths for different values. Make getTruncateOrZeroExtend a method on ScalarEvolution, and use it. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@52248 91177308-0d34-0410-b5e6-96231b3b80d8 --- include/llvm/Analysis/ScalarEvolution.h | 5 ++ lib/Analysis/ScalarEvolution.cpp | 54 ++++++++++--------- .../2008-06-12-BinomialInt64.ll | 43 +++++++++++++++ 3 files changed, 78 insertions(+), 24 deletions(-) create mode 100644 test/Analysis/ScalarEvolution/2008-06-12-BinomialInt64.ll diff --git a/include/llvm/Analysis/ScalarEvolution.h b/include/llvm/Analysis/ScalarEvolution.h index a8e45e0fa64..8474b724638 100644 --- a/include/llvm/Analysis/ScalarEvolution.h +++ b/include/llvm/Analysis/ScalarEvolution.h @@ -253,6 +253,11 @@ namespace llvm { SCEVHandle getMinusSCEV(const SCEVHandle &LHS, const SCEVHandle &RHS); + /// getTruncateOrZeroExtend - Return a SCEV corresponding to a conversion + /// of the input value to the specified type. If the type must be + /// extended, it is zero extended. + SCEVHandle getTruncateOrZeroExtend(const SCEVHandle &V, const Type *Ty); + /// getIntegerSCEV - Given an integer or FP type, create a constant for the /// specified signed integer value and return a SCEV for the constant. SCEVHandle getIntegerSCEV(int Val, const Type *Ty); diff --git a/lib/Analysis/ScalarEvolution.cpp b/lib/Analysis/ScalarEvolution.cpp index e01cf51794e..ae3d10033f1 100644 --- a/lib/Analysis/ScalarEvolution.cpp +++ b/lib/Analysis/ScalarEvolution.cpp @@ -499,21 +499,6 @@ SCEVHandle ScalarEvolution::getIntegerSCEV(int Val, const Type *Ty) { return getUnknown(C); } -/// getTruncateOrZeroExtend - Return a SCEV corresponding to a conversion of the -/// input value to the specified type. If the type must be extended, it is zero -/// extended. -static SCEVHandle getTruncateOrZeroExtend(const SCEVHandle &V, const Type *Ty, - ScalarEvolution &SE) { - const Type *SrcTy = V->getType(); - assert(SrcTy->isInteger() && Ty->isInteger() && - "Cannot truncate or zero extend with non-integer arguments!"); - if (SrcTy->getPrimitiveSizeInBits() == Ty->getPrimitiveSizeInBits()) - return V; // No conversion - if (SrcTy->getPrimitiveSizeInBits() > Ty->getPrimitiveSizeInBits()) - return SE.getTruncateExpr(V, Ty); - return SE.getZeroExtendExpr(V, Ty); -} - /// getNegativeSCEV - Return a SCEV corresponding to -V = -1*V /// SCEVHandle ScalarEvolution::getNegativeSCEV(const SCEVHandle &V) { @@ -585,7 +570,7 @@ static SCEVHandle BinomialCoefficient(SCEVHandle It, unsigned K, #endif const IntegerType *DividendTy = IntegerType::get(DividendBits); - const SCEVHandle ExIt = SE.getZeroExtendExpr(It, DividendTy); + const SCEVHandle ExIt = SE.getTruncateOrZeroExtend(It, DividendTy); // The final number of bits we need to perform the division is the maximum of // dividend and divisor bitwidths. @@ -607,7 +592,12 @@ static SCEVHandle BinomialCoefficient(SCEVHandle It, unsigned K, Dividend *= N-(K-1); if (DividendTy != DivisionTy) Dividend = Dividend.zext(DivisionTy->getBitWidth()); - return SE.getConstant(Dividend.udiv(Divisor).trunc(It->getBitWidth())); + + APInt Result = Dividend.udiv(Divisor); + if (Result.getBitWidth() != It->getBitWidth()) + Result = Result.trunc(It->getBitWidth()); + + return SE.getConstant(Result); } SCEVHandle Dividend = ExIt; @@ -615,11 +605,12 @@ static SCEVHandle BinomialCoefficient(SCEVHandle It, unsigned K, Dividend = SE.getMulExpr(Dividend, SE.getMinusSCEV(ExIt, SE.getIntegerSCEV(i, DividendTy))); - if (DividendTy != DivisionTy) - Dividend = SE.getZeroExtendExpr(Dividend, DivisionTy); - return - SE.getTruncateExpr(SE.getUDivExpr(Dividend, SE.getConstant(Divisor)), - It->getType()); + + return SE.getTruncateOrZeroExtend( + SE.getUDivExpr( + SE.getTruncateOrZeroExtend(Dividend, DivisionTy), + SE.getConstant(Divisor) + ), It->getType()); } /// evaluateAtIteration - Return the value of this chain of recurrences at @@ -703,6 +694,21 @@ SCEVHandle ScalarEvolution::getSignExtendExpr(const SCEVHandle &Op, const Type * return Result; } +/// getTruncateOrZeroExtend - Return a SCEV corresponding to a conversion +/// of the input value to the specified type. If the type must be +/// extended, it is zero extended. +SCEVHandle ScalarEvolution::getTruncateOrZeroExtend(const SCEVHandle &V, + const Type *Ty) { + const Type *SrcTy = V->getType(); + assert(SrcTy->isInteger() && Ty->isInteger() && + "Cannot truncate or zero extend with non-integer arguments!"); + if (SrcTy->getPrimitiveSizeInBits() == Ty->getPrimitiveSizeInBits()) + return V; // No conversion + if (SrcTy->getPrimitiveSizeInBits() > Ty->getPrimitiveSizeInBits()) + return getTruncateExpr(V, Ty); + return getZeroExtendExpr(V, Ty); +} + // get - Get a canonical add expression, or something simpler if possible. SCEVHandle ScalarEvolution::getAddExpr(std::vector &Ops) { assert(!Ops.empty() && "Cannot get empty add!"); @@ -2432,8 +2438,8 @@ SCEVHandle ScalarEvolutionsImpl::getSCEVAtScope(SCEV *V, const Loop *L) { // loop iterates. Compute this now. SCEVHandle IterationCount = getIterationCount(AddRec->getLoop()); if (IterationCount == UnknownValue) return UnknownValue; - IterationCount = getTruncateOrZeroExtend(IterationCount, - AddRec->getType(), SE); + IterationCount = SE.getTruncateOrZeroExtend(IterationCount, + AddRec->getType()); // If the value is affine, simplify the expression evaluation to just // Start + Step*IterationCount. diff --git a/test/Analysis/ScalarEvolution/2008-06-12-BinomialInt64.ll b/test/Analysis/ScalarEvolution/2008-06-12-BinomialInt64.ll new file mode 100644 index 00000000000..cbe5c97905c --- /dev/null +++ b/test/Analysis/ScalarEvolution/2008-06-12-BinomialInt64.ll @@ -0,0 +1,43 @@ +; RUN: llvm-as < %s | opt -analyze -scalar-evolution 2>/dev/null +; PR2433 + +define i32 @main1(i32 %argc, i8** %argv) nounwind { +entry: + br i1 false, label %bb10, label %bb23 + +bb10: ; preds = %bb10, %entry + %accum.03 = phi i64 [ %tmp14, %bb10 ], [ 0, %entry ] ; [#uses=1] + %i.02 = phi i32 [ %tmp16, %bb10 ], [ 0, %entry ] ; [#uses=1] + %d.1.01 = phi i64 [ %tmp5.i, %bb10 ], [ 0, %entry ] ; [#uses=1] + %tmp5.i = add i64 %d.1.01, 1 ; [#uses=2] + %tmp14 = add i64 %accum.03, %tmp5.i ; [#uses=2] + %tmp16 = add i32 %i.02, 1 ; [#uses=2] + %tmp20 = icmp slt i32 %tmp16, 0 ; [#uses=1] + br i1 %tmp20, label %bb10, label %bb23 + +bb23: ; preds = %bb10, %entry + %accum.0.lcssa = phi i64 [ 0, %entry ], [ %tmp14, %bb10 ] ; [#uses=0] + ret i32 0 +} + +define i32 @main2(i32 %argc, i8** %argv) { +entry: + %tmp8 = tail call i32 @atoi( i8* null ) nounwind readonly ; [#uses=1] + br i1 false, label %bb9, label %bb21 + +bb9: ; preds = %bb9, %entry + %accum.03 = phi i64 [ %tmp12, %bb9 ], [ 0, %entry ] ; [#uses=1] + %i.02 = phi i32 [ %tmp14, %bb9 ], [ 0, %entry ] ; [#uses=1] + %d.1.01 = phi i64 [ %tmp4.i, %bb9 ], [ 0, %entry ] ; [#uses=1] + %tmp4.i = add i64 %d.1.01, 1 ; [#uses=2] + %tmp12 = add i64 %accum.03, %tmp4.i ; [#uses=2] + %tmp14 = add i32 %i.02, 1 ; [#uses=2] + %tmp18 = icmp slt i32 %tmp14, %tmp8 ; [#uses=1] + br i1 %tmp18, label %bb9, label %bb21 + +bb21: ; preds = %bb9, %entry + %accum.0.lcssa = phi i64 [ 0, %entry ], [ %tmp12, %bb9 ] ; [#uses=0] + ret i32 0 +} + +declare i32 @atoi(i8*) nounwind readonly -- 2.34.1