From 8e345a1c418608c49abb7c51a090bbb36f1273bc Mon Sep 17 00:00:00 2001 From: Victor Hernandez Date: Tue, 10 Nov 2009 08:32:25 +0000 Subject: [PATCH] Update computeArraySize() to use ComputeMultiple() to determine the array size associated with a malloc; also extend PerformHeapAllocSRoA() to check if the optimized malloc's arg had its highest bit set, so that it is safe for ComputeMultiple() to look through sext instructions while determining the optimized malloc's array size git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@86676 91177308-0d34-0410-b5e6-96231b3b80d8 --- include/llvm/Analysis/MemoryBuiltins.h | 7 +- lib/Analysis/MemoryBuiltins.cpp | 109 +++++-------------------- lib/Transforms/IPO/GlobalOpt.cpp | 14 ++-- test/Analysis/PointerTracking/sizes.ll | 10 +-- 4 files changed, 30 insertions(+), 110 deletions(-) diff --git a/include/llvm/Analysis/MemoryBuiltins.h b/include/llvm/Analysis/MemoryBuiltins.h index 6944564b8fa..f6fa0c8d1e7 100644 --- a/include/llvm/Analysis/MemoryBuiltins.h +++ b/include/llvm/Analysis/MemoryBuiltins.h @@ -44,9 +44,7 @@ CallInst *extractMallocCallFromBitCast(Value *I); /// isArrayMalloc - Returns the corresponding CallInst if the instruction /// is a call to malloc whose array size can be determined and the array size /// is not constant 1. Otherwise, return NULL. -CallInst *isArrayMalloc(Value *I, const TargetData *TD); -const CallInst *isArrayMalloc(const Value *I, - const TargetData *TD); +const CallInst *isArrayMalloc(const Value *I, const TargetData *TD); /// getMallocType - Returns the PointerType resulting from the malloc call. /// The PointerType depends on the number of bitcast uses of the malloc call: @@ -67,7 +65,8 @@ const Type *getMallocAllocatedType(const CallInst *CI); /// then return that multiple. For non-array mallocs, the multiple is /// constant 1. Otherwise, return NULL for mallocs whose array size cannot be /// determined. -Value *getMallocArraySize(CallInst *CI, const TargetData *TD); +Value *getMallocArraySize(CallInst *CI, const TargetData *TD, + bool LookThroughSExt = false); //===----------------------------------------------------------------------===// // free Call Utility Functions. diff --git a/lib/Analysis/MemoryBuiltins.cpp b/lib/Analysis/MemoryBuiltins.cpp index 6e2094027e5..9f036f4e2ae 100644 --- a/lib/Analysis/MemoryBuiltins.cpp +++ b/lib/Analysis/MemoryBuiltins.cpp @@ -16,7 +16,7 @@ #include "llvm/Constants.h" #include "llvm/Instructions.h" #include "llvm/Module.h" -#include "llvm/Analysis/ConstantFolding.h" +#include "llvm/Analysis/ValueTracking.h" #include "llvm/Target/TargetData.h" using namespace llvm; @@ -87,12 +87,8 @@ const CallInst *llvm::extractMallocCallFromBitCast(const Value *I) { : NULL; } -/// isConstantOne - Return true only if val is constant int 1. -static bool isConstantOne(Value *val) { - return isa(val) && cast(val)->isOne(); -} - -static Value *isArrayMallocHelper(const CallInst *CI, const TargetData *TD) { +static Value *computeArraySize(const CallInst *CI, const TargetData *TD, + bool LookThroughSExt = false) { if (!CI) return NULL; @@ -101,97 +97,28 @@ static Value *isArrayMallocHelper(const CallInst *CI, const TargetData *TD) { if (!T || !T->isSized() || !TD) return NULL; - Value *MallocArg = CI->getOperand(1); - const Type *ArgType = MallocArg->getType(); - ConstantExpr *CO = dyn_cast(MallocArg); - BinaryOperator *BO = dyn_cast(MallocArg); - - unsigned ElementSizeInt = TD->getTypeAllocSize(T); + unsigned ElementSize = TD->getTypeAllocSize(T); if (const StructType *ST = dyn_cast(T)) - ElementSizeInt = TD->getStructLayout(ST)->getSizeInBytes(); - Constant *ElementSize = ConstantInt::get(ArgType, ElementSizeInt); - - // First, check if CI is a non-array malloc. - if (CO && CO == ElementSize) - // Match CreateMalloc's use of constant 1 array-size for non-array mallocs. - return ConstantInt::get(ArgType, 1); - - // Second, check if CI is an array malloc whose array size can be determined. - if (isConstantOne(ElementSize)) - return MallocArg; - - if (ConstantInt *CInt = dyn_cast(MallocArg)) - if (CInt->getZExtValue() % ElementSizeInt == 0) - return ConstantInt::get(ArgType, CInt->getZExtValue() / ElementSizeInt); + ElementSize = TD->getStructLayout(ST)->getSizeInBytes(); - if (!CO && !BO) - return NULL; - - Value *Op0 = NULL; - Value *Op1 = NULL; - unsigned Opcode = 0; - if (CO && ((CO->getOpcode() == Instruction::Mul) || - (CO->getOpcode() == Instruction::Shl))) { - Op0 = CO->getOperand(0); - Op1 = CO->getOperand(1); - Opcode = CO->getOpcode(); - } - if (BO && ((BO->getOpcode() == Instruction::Mul) || - (BO->getOpcode() == Instruction::Shl))) { - Op0 = BO->getOperand(0); - Op1 = BO->getOperand(1); - Opcode = BO->getOpcode(); - } - - // Determine array size if malloc's argument is the product of a mul or shl. - if (Op0) { - if (Opcode == Instruction::Mul) { - if (Op1 == ElementSize) - // ArraySize * ElementSize - return Op0; - if (Op0 == ElementSize) - // ElementSize * ArraySize - return Op1; - } - if (Opcode == Instruction::Shl) { - ConstantInt *Op1CI = dyn_cast(Op1); - if (!Op1CI) return NULL; - - APInt Op1Int = Op1CI->getValue(); - uint64_t BitToSet = Op1Int.getLimitedValue(Op1Int.getBitWidth() - 1); - Value *Op1Pow = ConstantInt::get(Op1CI->getContext(), - APInt(Op1Int.getBitWidth(), 0).set(BitToSet)); - if (Op0 == ElementSize) - // ArraySize << log2(ElementSize) - return Op1Pow; - if (Op1Pow == ElementSize) - // ElementSize << log2(ArraySize) - return Op0; - } - } + // If malloc calls' arg can be determined to be a multiple of ElementSize, + // return the multiple. Otherwise, return NULL. + Value *MallocArg = CI->getOperand(1); + Value *Multiple = NULL; + APInt Val(TD->getTypeSizeInBits(MallocArg->getType()->getScalarType()), 0); + if (ComputeMultiple(MallocArg, ElementSize, Multiple, + Val, LookThroughSExt, TD)) + return Multiple; - // We could not determine the malloc array size from MallocArg. return NULL; } /// isArrayMalloc - Returns the corresponding CallInst if the instruction /// is a call to malloc whose array size can be determined and the array size /// is not constant 1. Otherwise, return NULL. -CallInst *llvm::isArrayMalloc(Value *I, const TargetData *TD) { - CallInst *CI = extractMallocCall(I); - Value *ArraySize = isArrayMallocHelper(CI, TD); - - if (ArraySize && - ArraySize != ConstantInt::get(CI->getOperand(1)->getType(), 1)) - return CI; - - // CI is a non-array malloc or we can't figure out that it is an array malloc. - return NULL; -} - const CallInst *llvm::isArrayMalloc(const Value *I, const TargetData *TD) { const CallInst *CI = extractMallocCall(I); - Value *ArraySize = isArrayMallocHelper(CI, TD); + Value *ArraySize = computeArraySize(CI, TD); if (ArraySize && ArraySize != ConstantInt::get(CI->getOperand(1)->getType(), 1)) @@ -207,7 +134,7 @@ const CallInst *llvm::isArrayMalloc(const Value *I, const TargetData *TD) { /// 1: PointerType is the bitcast's result type. /// >1: Unique PointerType cannot be determined, return NULL. const PointerType *llvm::getMallocType(const CallInst *CI) { - assert(isMalloc(CI) && "GetMallocType and not malloc call"); + assert(isMalloc(CI) && "getMallocType and not malloc call"); const PointerType *MallocType = NULL; unsigned NumOfBitCastUses = 0; @@ -247,8 +174,10 @@ const Type *llvm::getMallocAllocatedType(const CallInst *CI) { /// then return that multiple. For non-array mallocs, the multiple is /// constant 1. Otherwise, return NULL for mallocs whose array size cannot be /// determined. -Value *llvm::getMallocArraySize(CallInst *CI, const TargetData *TD) { - return isArrayMallocHelper(CI, TD); +Value *llvm::getMallocArraySize(CallInst *CI, const TargetData *TD, + bool LookThroughSExt) { + assert(isMalloc(CI) && "getMallocArraySize and not malloc call"); + return computeArraySize(CI, TD, LookThroughSExt); } //===----------------------------------------------------------------------===// diff --git a/lib/Transforms/IPO/GlobalOpt.cpp b/lib/Transforms/IPO/GlobalOpt.cpp index 4013272cd27..442f2fb6552 100644 --- a/lib/Transforms/IPO/GlobalOpt.cpp +++ b/lib/Transforms/IPO/GlobalOpt.cpp @@ -1321,15 +1321,15 @@ static GlobalVariable *PerformHeapAllocSRoA(GlobalVariable *GV, CallInst *CI, // if (F1) { free(F1); F1 = 0; } // if (F2) { free(F2); F2 = 0; } // } - Value *RunningOr = 0; + // The malloc can also fail if its argument is too large. + Constant *ConstantZero = ConstantInt::get(CI->getOperand(1)->getType(), 0); + Value *RunningOr = new ICmpInst(CI, ICmpInst::ICMP_SLT, CI->getOperand(1), + ConstantZero, "isneg"); for (unsigned i = 0, e = FieldMallocs.size(); i != e; ++i) { Value *Cond = new ICmpInst(CI, ICmpInst::ICMP_EQ, FieldMallocs[i], Constant::getNullValue(FieldMallocs[i]->getType()), "isnull"); - if (!RunningOr) - RunningOr = Cond; // First seteq - else - RunningOr = BinaryOperator::CreateOr(RunningOr, Cond, "tmp", CI); + RunningOr = BinaryOperator::CreateOr(RunningOr, Cond, "tmp", CI); } // Split the basic block at the old malloc. @@ -1490,7 +1490,7 @@ static bool TryToOptimizeStoreOfMallocToGlobal(GlobalVariable *GV, // This eliminates dynamic allocation, avoids an indirection accessing the // data, and exposes the resultant global to further GlobalOpt. // We cannot optimize the malloc if we cannot determine malloc array size. - if (Value *NElems = getMallocArraySize(CI, TD)) { + if (Value *NElems = getMallocArraySize(CI, TD, true)) { if (ConstantInt *NElements = dyn_cast(NElems)) // Restrict this transformation to only working on small allocations // (2048 bytes currently), as we don't want to introduce a 16M global or @@ -1535,7 +1535,7 @@ static bool TryToOptimizeStoreOfMallocToGlobal(GlobalVariable *GV, extractMallocCallFromBitCast(Malloc) : cast(Malloc); } - GVI = PerformHeapAllocSRoA(GV, CI, getMallocArraySize(CI, TD), TD); + GVI = PerformHeapAllocSRoA(GV, CI, getMallocArraySize(CI, TD, true),TD); return true; } } diff --git a/test/Analysis/PointerTracking/sizes.ll b/test/Analysis/PointerTracking/sizes.ll index 267c3b83e29..c8ca648e877 100644 --- a/test/Analysis/PointerTracking/sizes.ll +++ b/test/Analysis/PointerTracking/sizes.ll @@ -31,7 +31,6 @@ entry: } declare i32 @bar(i8*) -declare i32 @bar2(i64*) define i32 @foo1(i32 %n) nounwind { entry: @@ -66,11 +65,6 @@ entry: %call = tail call i8* @malloc(i64 %n) ; [#uses=1] ; CHECK: %call = ; CHECK: ==> %n elements, %n bytes allocated - %mallocsize = mul i64 %n, 8 ; [#uses=1] - %malloccall = tail call i8* @malloc(i64 %mallocsize) ; [#uses=1] - %call3 = bitcast i8* %malloccall to i64* ; [#uses=1] -; CHECK: %malloccall = -; CHECK: ==> (8 * %n) elements, (8 * %n) bytes allocated %call2 = tail call i8* @calloc(i64 2, i64 4) nounwind ; [#uses=1] ; CHECK: %call2 = ; CHECK: ==> 8 elements, 8 bytes allocated @@ -78,12 +72,10 @@ entry: ; CHECK: %call4 = ; CHECK: ==> 16 elements, 16 bytes allocated %call6 = tail call i32 @bar(i8* %call) nounwind ; [#uses=1] - %call7 = tail call i32 @bar2(i64* %call3) nounwind ; [#uses=1] %call8 = tail call i32 @bar(i8* %call2) nounwind ; [#uses=1] %call10 = tail call i32 @bar(i8* %call4) nounwind ; [#uses=1] %add = add i32 %call8, %call6 ; [#uses=1] - %add10 = add i32 %add, %call7 ; [#uses=1] - %add11 = add i32 %add10, %call10 ; [#uses=1] + %add11 = add i32 %add, %call10 ; [#uses=1] ret i32 %add11 } -- 2.34.1