X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FAnalysis%2FMemoryBuiltins.cpp;h=9695ae1dec225cf55e5ebf34c406978717fe2838;hb=8aa22019ca5ef29a15058be905d782e7225aa206;hp=cf2ad62b617e24f13add98d07aae9ba23c0a92be;hpb=f006b183e2d2bebcf6968d1dd7350397c95b0325;p=oota-llvm.git diff --git a/lib/Analysis/MemoryBuiltins.cpp b/lib/Analysis/MemoryBuiltins.cpp index cf2ad62b617..9695ae1dec2 100644 --- a/lib/Analysis/MemoryBuiltins.cpp +++ b/lib/Analysis/MemoryBuiltins.cpp @@ -16,16 +16,17 @@ #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; //===----------------------------------------------------------------------===// // malloc Call Utility Functions. // -/// isMalloc - Returns true if the the value is either a malloc call or a +/// isMalloc - Returns true if the value is either a malloc call or a /// bitcast of the result of a malloc call. -bool llvm::isMalloc(const Value* I) { +bool llvm::isMalloc(const Value *I) { return extractMallocCall(I) || extractMallocCallFromBitCast(I); } @@ -33,41 +34,40 @@ static bool isMallocCall(const CallInst *CI) { if (!CI) return false; - const Module* M = CI->getParent()->getParent()->getParent(); - Function *MallocFunc = M->getFunction("malloc"); - - if (CI->getOperand(0) != MallocFunc) + Function *Callee = CI->getCalledFunction(); + if (Callee == 0 || !Callee->isDeclaration()) + return false; + if (Callee->getName() != "malloc" && + Callee->getName() != "_Znwj" && // operator new(unsigned int) + Callee->getName() != "_Znwm" && // operator new(unsigned long) + Callee->getName() != "_Znaj" && // operator new[](unsigned int) + Callee->getName() != "_Znam") // operator new[](unsigned long) return false; // Check malloc prototype. // FIXME: workaround for PR5130, this will be obsolete when a nobuiltin // attribute will exist. - const FunctionType *FTy = MallocFunc->getFunctionType(); - if (FTy->getNumParams() != 1) - return false; - if (IntegerType *ITy = dyn_cast(FTy->param_begin()->get())) { - if (ITy->getBitWidth() != 32 && ITy->getBitWidth() != 64) - return false; - return true; - } - - return false; + FunctionType *FTy = Callee->getFunctionType(); + return FTy->getReturnType() == Type::getInt8PtrTy(FTy->getContext()) && + FTy->getNumParams() == 1 && + (FTy->getParamType(0)->isIntegerTy(32) || + FTy->getParamType(0)->isIntegerTy(64)); } /// extractMallocCall - Returns the corresponding CallInst if the instruction /// is a malloc call. Since CallInst::CreateMalloc() only creates calls, we /// ignore InvokeInst here. -const CallInst* llvm::extractMallocCall(const Value* I) { +const CallInst *llvm::extractMallocCall(const Value *I) { const CallInst *CI = dyn_cast(I); return (isMallocCall(CI)) ? CI : NULL; } -CallInst* llvm::extractMallocCall(Value* I) { +CallInst *llvm::extractMallocCall(Value *I) { CallInst *CI = dyn_cast(I); return (isMallocCall(CI)) ? CI : NULL; } -static bool isBitCastOfMallocCall(const BitCastInst* BCI) { +static bool isBitCastOfMallocCall(const BitCastInst *BCI) { if (!BCI) return false; @@ -76,220 +76,178 @@ static bool isBitCastOfMallocCall(const BitCastInst* BCI) { /// extractMallocCallFromBitCast - Returns the corresponding CallInst if the /// instruction is a bitcast of the result of a malloc call. -CallInst* llvm::extractMallocCallFromBitCast(Value* I) { +CallInst *llvm::extractMallocCallFromBitCast(Value *I) { BitCastInst *BCI = dyn_cast(I); return (isBitCastOfMallocCall(BCI)) ? cast(BCI->getOperand(0)) : NULL; } -const CallInst* llvm::extractMallocCallFromBitCast(const Value* I) { +const CallInst *llvm::extractMallocCallFromBitCast(const Value *I) { const BitCastInst *BCI = dyn_cast(I); return (isBitCastOfMallocCall(BCI)) ? cast(BCI->getOperand(0)) : NULL; } -static bool isArrayMallocHelper(const CallInst *CI, LLVMContext &Context, - const TargetData* TD) { +static Value *computeArraySize(const CallInst *CI, const TargetData *TD, + bool LookThroughSExt = false) { if (!CI) - return false; - - const Type* T = getMallocAllocatedType(CI); - - // We can only indentify an array malloc if we know the type of the malloc - // call. - if (!T) return false; - - Value* MallocArg = CI->getOperand(1); - Constant *ElementSize = ConstantExpr::getSizeOf(T); - ElementSize = ConstantExpr::getTruncOrBitCast(ElementSize, - MallocArg->getType()); - Constant *FoldedElementSize = ConstantFoldConstantExpression( - cast(ElementSize), - Context, TD); - - - if (isa(MallocArg)) - return (MallocArg != ElementSize); + return NULL; - BinaryOperator *BI = dyn_cast(MallocArg); - if (!BI) - return false; + // The size of the malloc's result type must be known to determine array size. + Type *T = getMallocAllocatedType(CI); + if (!T || !T->isSized() || !TD) + return NULL; - if (BI->getOpcode() == Instruction::Mul) - // ArraySize * ElementSize - if (BI->getOperand(1) == ElementSize || - (FoldedElementSize && BI->getOperand(1) == FoldedElementSize)) - return true; + unsigned ElementSize = TD->getTypeAllocSize(T); + if (StructType *ST = dyn_cast(T)) + ElementSize = TD->getStructLayout(ST)->getSizeInBytes(); - // TODO: Detect case where MallocArg mul has been transformed to shl. + // If malloc call's arg can be determined to be a multiple of ElementSize, + // return the multiple. Otherwise, return NULL. + Value *MallocArg = CI->getArgOperand(0); + Value *Multiple = NULL; + if (ComputeMultiple(MallocArg, ElementSize, Multiple, + LookThroughSExt)) + return Multiple; - return false; + return NULL; } /// isArrayMalloc - Returns the corresponding CallInst if the instruction -/// matches the malloc call IR generated by CallInst::CreateMalloc(). This -/// means that it is a malloc call with one bitcast use AND the malloc call's -/// size argument is: -/// 1. a constant not equal to the size of the malloced type -/// or -/// 2. the result of a multiplication by the size of the malloced type -/// Otherwise it returns NULL. -/// The unique bitcast is needed to determine the type/size of the array -/// allocation. -CallInst* llvm::isArrayMalloc(Value* I, LLVMContext &Context, - const TargetData* TD) { - CallInst *CI = extractMallocCall(I); - return (isArrayMallocHelper(CI, Context, TD)) ? CI : NULL; -} - -const CallInst* llvm::isArrayMalloc(const Value* I, LLVMContext &Context, - const TargetData* TD) { +/// is a call to malloc whose array size can be determined and the array size +/// is not constant 1. Otherwise, return NULL. +const CallInst *llvm::isArrayMalloc(const Value *I, const TargetData *TD) { const CallInst *CI = extractMallocCall(I); - return (isArrayMallocHelper(CI, Context, TD)) ? CI : NULL; + Value *ArraySize = computeArraySize(CI, TD); + + if (ArraySize && + ArraySize != ConstantInt::get(CI->getArgOperand(0)->getType(), 1)) + return CI; + + // CI is a non-array malloc or we can't figure out that it is an array malloc. + return NULL; } /// getMallocType - Returns the PointerType resulting from the malloc call. -/// This PointerType is the result type of the call's only bitcast use. -/// If there is no unique bitcast use, then return NULL. -const PointerType* llvm::getMallocType(const CallInst* CI) { - assert(isMalloc(CI) && "GetMallocType and not malloc call"); - - const BitCastInst* BCI = NULL; +/// The PointerType depends on the number of bitcast uses of the malloc call: +/// 0: PointerType is the calls' return type. +/// 1: PointerType is the bitcast's result type. +/// >1: Unique PointerType cannot be determined, return NULL. +PointerType *llvm::getMallocType(const CallInst *CI) { + assert(isMalloc(CI) && "getMallocType and not malloc call"); + PointerType *MallocType = NULL; + unsigned NumOfBitCastUses = 0; + // Determine if CallInst has a bitcast use. - for (Value::use_const_iterator UI = CI->use_begin(), E = CI->use_end(); + for (Value::const_use_iterator UI = CI->use_begin(), E = CI->use_end(); UI != E; ) - if ((BCI = dyn_cast(cast(*UI++)))) - break; + if (const BitCastInst *BCI = dyn_cast(*UI++)) { + MallocType = cast(BCI->getDestTy()); + NumOfBitCastUses++; + } - // Malloc call has 1 bitcast use and no other uses, so type is the bitcast's - // destination type. - if (BCI && CI->hasOneUse()) - return cast(BCI->getDestTy()); + // Malloc call has 1 bitcast use, so type is the bitcast's destination type. + if (NumOfBitCastUses == 1) + return MallocType; // Malloc call was not bitcast, so type is the malloc function's return type. - if (!BCI) + if (NumOfBitCastUses == 0) return cast(CI->getType()); // Type could not be determined. return NULL; } -/// getMallocAllocatedType - Returns the Type allocated by malloc call. This -/// Type is the result type of the call's only bitcast use. If there is no -/// unique bitcast use, then return NULL. -const Type* llvm::getMallocAllocatedType(const CallInst* CI) { - const PointerType* PT = getMallocType(CI); +/// getMallocAllocatedType - Returns the Type allocated by malloc call. +/// The Type depends on the number of bitcast uses of the malloc call: +/// 0: PointerType is the malloc calls' return type. +/// 1: PointerType is the bitcast's result type. +/// >1: Unique PointerType cannot be determined, return NULL. +Type *llvm::getMallocAllocatedType(const CallInst *CI) { + PointerType *PT = getMallocType(CI); return PT ? PT->getElementType() : NULL; } -/// isSafeToGetMallocArraySize - Returns true if the array size of a malloc can -/// be determined. It can be determined in these 3 cases of malloc codegen: -/// 1. non-array malloc: The malloc's size argument is a constant and equals the /// size of the type being malloced. -/// 2. array malloc: This is a malloc call with one bitcast use AND the malloc -/// call's size argument is a constant multiple of the size of the malloced -/// type. -/// 3. array malloc: This is a malloc call with one bitcast use AND the malloc -/// call's size argument is the result of a multiplication by the size of the -/// malloced type. -/// Otherwise returns false. -static bool isSafeToGetMallocArraySize(const CallInst *CI, - LLVMContext &Context, - const TargetData* TD) { - if (!CI) - return false; - - // Type must be known to determine array size. - const Type* T = getMallocAllocatedType(CI); - if (!T) return false; +/// getMallocArraySize - Returns the array size of a malloc call. If the +/// argument passed to malloc is a multiple of the size of the malloced type, +/// 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, + bool LookThroughSExt) { + assert(isMalloc(CI) && "getMallocArraySize and not malloc call"); + return computeArraySize(CI, TD, LookThroughSExt); +} - Value* MallocArg = CI->getOperand(1); - Constant *ElementSize = ConstantExpr::getSizeOf(T); - ElementSize = ConstantExpr::getTruncOrBitCast(ElementSize, - MallocArg->getType()); - // First, check if it is a non-array malloc. - if (isa(MallocArg) && (MallocArg == ElementSize)) - return true; +//===----------------------------------------------------------------------===// +// calloc Call Utility Functions. +// - // Second, check if it can be determined that this is an array malloc. - return isArrayMallocHelper(CI, Context, TD); +static bool isCallocCall(const CallInst *CI) { + if (!CI) + return false; + + Function *Callee = CI->getCalledFunction(); + if (Callee == 0 || !Callee->isDeclaration()) + return false; + if (Callee->getName() != "calloc") + return false; + + // Check malloc prototype. + // FIXME: workaround for PR5130, this will be obsolete when a nobuiltin + // attribute exists. + FunctionType *FTy = Callee->getFunctionType(); + return FTy->getReturnType() == Type::getInt8PtrTy(FTy->getContext()) && + FTy->getNumParams() == 2 && + ((FTy->getParamType(0)->isIntegerTy(32) && + FTy->getParamType(1)->isIntegerTy(32)) || + (FTy->getParamType(0)->isIntegerTy(64) && + FTy->getParamType(1)->isIntegerTy(64))); +} + +/// extractCallocCall - Returns the corresponding CallInst if the instruction +/// is a calloc call. +const CallInst *llvm::extractCallocCall(const Value *I) { + const CallInst *CI = dyn_cast(I); + return isCallocCall(CI) ? CI : 0; } -/// isConstantOne - Return true only if val is constant int 1. -static bool isConstantOne(Value *val) { - return isa(val) && cast(val)->isOne(); +CallInst *llvm::extractCallocCall(Value *I) { + CallInst *CI = dyn_cast(I); + return isCallocCall(CI) ? CI : 0; } -/// getMallocArraySize - Returns the array size of a malloc call. For array -/// mallocs, the size is computated in 1 of 3 ways: -/// 1. If the element type is of size 1, then array size is the argument to -/// malloc. -/// 2. Else if the malloc's argument is a constant, the array size is that -/// argument divided by the element type's size. -/// 3. Else the malloc argument must be a multiplication and the array size is -/// the first operand of the multiplication. -/// For non-array mallocs, the computed size is constant 1. -/// This function returns NULL for all mallocs whose array size cannot be -/// determined. -Value* llvm::getMallocArraySize(CallInst* CI, LLVMContext &Context, - const TargetData* TD) { - if (!isSafeToGetMallocArraySize(CI, Context, TD)) - return NULL; - - // Match CreateMalloc's use of constant 1 array-size for non-array mallocs. - if (!isArrayMalloc(CI, Context, TD)) - return ConstantInt::get(CI->getOperand(1)->getType(), 1); - - Value* MallocArg = CI->getOperand(1); - assert(getMallocAllocatedType(CI) && "getMallocArraySize and no type"); - Constant *ElementSize = ConstantExpr::getSizeOf(getMallocAllocatedType(CI)); - ElementSize = ConstantExpr::getTruncOrBitCast(ElementSize, - MallocArg->getType()); - - Constant* CO = dyn_cast(MallocArg); - BinaryOperator* BO = dyn_cast(MallocArg); - assert((isConstantOne(ElementSize) || CO || BO) && - "getMallocArraySize and malformed malloc IR"); - - if (isConstantOne(ElementSize)) - return MallocArg; - - if (CO) - return CO->getOperand(0); - - // TODO: Detect case where MallocArg mul has been transformed to shl. - - assert(BO && "getMallocArraySize not constant but not multiplication either"); - return BO->getOperand(0); -} //===----------------------------------------------------------------------===// // free Call Utility Functions. // -/// isFreeCall - Returns true if the the value is a call to the builtin free() -bool llvm::isFreeCall(const Value* I) { +/// isFreeCall - Returns non-null if the value is a call to the builtin free() +const CallInst *llvm::isFreeCall(const Value *I) { const CallInst *CI = dyn_cast(I); if (!CI) - return false; - - const Module* M = CI->getParent()->getParent()->getParent(); - Function *FreeFunc = M->getFunction("free"); + return 0; + Function *Callee = CI->getCalledFunction(); + if (Callee == 0 || !Callee->isDeclaration()) + return 0; - if (CI->getOperand(0) != FreeFunc) - return false; + if (Callee->getName() != "free" && + Callee->getName() != "_ZdlPv" && // operator delete(void*) + Callee->getName() != "_ZdaPv") // operator delete[](void*) + return 0; // Check free prototype. // FIXME: workaround for PR5130, this will be obsolete when a nobuiltin // attribute will exist. - const FunctionType *FTy = FreeFunc->getFunctionType(); - if (FTy->getReturnType() != Type::getVoidTy(M->getContext())) - return false; + FunctionType *FTy = Callee->getFunctionType(); + if (!FTy->getReturnType()->isVoidTy()) + return 0; if (FTy->getNumParams() != 1) - return false; - if (FTy->param_begin()->get() != Type::getInt8PtrTy(M->getContext())) - return false; + return 0; + if (FTy->getParamType(0) != Type::getInt8PtrTy(Callee->getContext())) + return 0; - return true; + return CI; }