X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FAnalysis%2FMemoryBuiltins.cpp;h=9695ae1dec225cf55e5ebf34c406978717fe2838;hb=8aa22019ca5ef29a15058be905d782e7225aa206;hp=0982345cfa9fb23b216971d12c3e47cc217dcfc2;hpb=90f48e7c91a8faa875ba889ca66b137ffd46e34a;p=oota-llvm.git diff --git a/lib/Analysis/MemoryBuiltins.cpp b/lib/Analysis/MemoryBuiltins.cpp index 0982345cfa9..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,127 +76,52 @@ 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; } -/// 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, LLVMContext &Context, - const TargetData* TD) { +static Value *computeArraySize(const CallInst *CI, const TargetData *TD, + bool LookThroughSExt = false) { if (!CI) return NULL; - // Type must be known to determine array size. - const Type* T = getMallocAllocatedType(CI); - if (!T) + // 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; - Value* MallocArg = CI->getOperand(1); - ConstantExpr* CO = dyn_cast(MallocArg); - BinaryOperator* BO = dyn_cast(MallocArg); + unsigned ElementSize = TD->getTypeAllocSize(T); + if (StructType *ST = dyn_cast(T)) + ElementSize = TD->getStructLayout(ST)->getSizeInBytes(); - Constant* ElementSize = ConstantExpr::getSizeOf(T); - ElementSize = ConstantExpr::getTruncOrBitCast(ElementSize, - MallocArg->getType()); - Constant *FoldedElementSize = - ConstantFoldConstantExpression(cast(ElementSize), Context, TD); - - // First, check if CI is a non-array malloc. - if (CO && ((CO == ElementSize) || - (FoldedElementSize && (CO == FoldedElementSize)))) - // Match CreateMalloc's use of constant 1 array-size for non-array mallocs. - return ConstantInt::get(MallocArg->getType(), 1); - - // Second, check if CI is an array malloc whose array size can be determined. - if (isConstantOne(ElementSize) || - (FoldedElementSize && isConstantOne(FoldedElementSize))) - return MallocArg; - - 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) || - (FoldedElementSize && (Op1 == FoldedElementSize))) - // ArraySize * ElementSize - return Op0; - if ((Op0 == ElementSize) || - (FoldedElementSize && (Op0 == FoldedElementSize))) - // ElementSize * ArraySize - return Op1; - } - if (Opcode == Instruction::Shl) { - ConstantInt* Op1Int = dyn_cast(Op1); - if (!Op1Int) return NULL; - Value* Op1Pow = ConstantInt::get(Op1->getType(), - pow(2, Op1Int->getZExtValue())); - if (Op0 == ElementSize || (FoldedElementSize && Op0 == FoldedElementSize)) - // ArraySize << log2(ElementSize) - return Op1Pow; - if (Op1Pow == ElementSize || - (FoldedElementSize && Op1Pow == FoldedElementSize)) - // ElementSize << log2(ArraySize) - return Op0; - } - } + // 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; - // 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, LLVMContext &Context, - const TargetData* TD) { - CallInst *CI = extractMallocCall(I); - Value* ArraySize = isArrayMallocHelper(CI, Context, 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, LLVMContext &Context, - const TargetData* TD) { +const CallInst *llvm::isArrayMalloc(const Value *I, const TargetData *TD) { const CallInst *CI = extractMallocCall(I); - Value* ArraySize = isArrayMallocHelper(CI, Context, TD); + Value *ArraySize = computeArraySize(CI, TD); if (ArraySize && - ArraySize != ConstantInt::get(CI->getOperand(1)->getType(), 1)) + 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. @@ -204,37 +129,43 @@ const CallInst* llvm::isArrayMalloc(const Value* I, LLVMContext &Context, } /// 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; } @@ -243,37 +174,80 @@ 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, LLVMContext &Context, - const TargetData* TD) { - return isArrayMallocHelper(CI, Context, TD); +Value *llvm::getMallocArraySize(CallInst *CI, const TargetData *TD, + bool LookThroughSExt) { + assert(isMalloc(CI) && "getMallocArraySize and not malloc call"); + return computeArraySize(CI, TD, LookThroughSExt); } + //===----------------------------------------------------------------------===// -// free Call Utility Functions. +// calloc Call Utility Functions. // -/// isFreeCall - Returns true if the the value is a call to the builtin free() -bool llvm::isFreeCall(const Value* I) { - const CallInst *CI = dyn_cast(I); +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))); +} - const Module* M = CI->getParent()->getParent()->getParent(); - Function *FreeFunc = M->getFunction("free"); +/// 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; +} + +CallInst *llvm::extractCallocCall(Value *I) { + CallInst *CI = dyn_cast(I); + return isCallocCall(CI) ? CI : 0; +} - if (CI->getOperand(0) != FreeFunc) - return false; + +//===----------------------------------------------------------------------===// +// free Call Utility Functions. +// + +/// 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 0; + Function *Callee = CI->getCalledFunction(); + if (Callee == 0 || !Callee->isDeclaration()) + return 0; + + 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; }