//===----------------------------------------------------------------------===//
//
// This family of functions identifies calls to builtin functions that allocate
-// or free memory.
+// or free memory.
//
//===----------------------------------------------------------------------===//
-#define DEBUG_TYPE "memory-builtins"
#include "llvm/Analysis/MemoryBuiltins.h"
#include "llvm/ADT/STLExtras.h"
#include "llvm/ADT/Statistic.h"
+#include "llvm/Analysis/TargetLibraryInfo.h"
#include "llvm/Analysis/ValueTracking.h"
#include "llvm/IR/DataLayout.h"
#include "llvm/IR/GlobalVariable.h"
#include "llvm/Support/Debug.h"
#include "llvm/Support/MathExtras.h"
#include "llvm/Support/raw_ostream.h"
-#include "llvm/Target/TargetLibraryInfo.h"
#include "llvm/Transforms/Utils/Local.h"
using namespace llvm;
+#define DEBUG_TYPE "memory-builtins"
+
enum AllocType {
- MallocLike = 1<<0, // allocates
- CallocLike = 1<<1, // allocates + bzero
- ReallocLike = 1<<2, // reallocates
- StrDupLike = 1<<3,
+ OpNewLike = 1<<0, // allocates; never returns null
+ MallocLike = 1<<1 | OpNewLike, // allocates; may return null
+ CallocLike = 1<<2, // allocates + bzero
+ ReallocLike = 1<<3, // reallocates
+ StrDupLike = 1<<4,
AllocLike = MallocLike | CallocLike | StrDupLike,
- AnyAlloc = MallocLike | CallocLike | ReallocLike | StrDupLike
+ AnyAlloc = AllocLike | ReallocLike
};
struct AllocFnsTy {
static const AllocFnsTy AllocationFnData[] = {
{LibFunc::malloc, MallocLike, 1, 0, -1},
{LibFunc::valloc, MallocLike, 1, 0, -1},
- {LibFunc::Znwj, MallocLike, 1, 0, -1}, // new(unsigned int)
+ {LibFunc::Znwj, OpNewLike, 1, 0, -1}, // new(unsigned int)
{LibFunc::ZnwjRKSt9nothrow_t, MallocLike, 2, 0, -1}, // new(unsigned int, nothrow)
- {LibFunc::Znwm, MallocLike, 1, 0, -1}, // new(unsigned long)
+ {LibFunc::Znwm, OpNewLike, 1, 0, -1}, // new(unsigned long)
{LibFunc::ZnwmRKSt9nothrow_t, MallocLike, 2, 0, -1}, // new(unsigned long, nothrow)
- {LibFunc::Znaj, MallocLike, 1, 0, -1}, // new[](unsigned int)
+ {LibFunc::Znaj, OpNewLike, 1, 0, -1}, // new[](unsigned int)
{LibFunc::ZnajRKSt9nothrow_t, MallocLike, 2, 0, -1}, // new[](unsigned int, nothrow)
- {LibFunc::Znam, MallocLike, 1, 0, -1}, // new[](unsigned long)
+ {LibFunc::Znam, OpNewLike, 1, 0, -1}, // new[](unsigned long)
{LibFunc::ZnamRKSt9nothrow_t, MallocLike, 2, 0, -1}, // new[](unsigned long, nothrow)
- {LibFunc::posix_memalign, MallocLike, 3, 2, -1},
{LibFunc::calloc, CallocLike, 2, 0, 1},
{LibFunc::realloc, ReallocLike, 2, 1, -1},
{LibFunc::reallocf, ReallocLike, 2, 1, -1},
{LibFunc::strdup, StrDupLike, 1, -1, -1},
{LibFunc::strndup, StrDupLike, 2, 1, -1}
+ // TODO: Handle "int posix_memalign(void **, size_t, size_t)"
};
CallSite CS(const_cast<Value*>(V));
if (!CS.getInstruction())
- return 0;
+ return nullptr;
+
+ if (CS.isNoBuiltin())
+ return nullptr;
Function *Callee = CS.getCalledFunction();
if (!Callee || !Callee->isDeclaration())
- return 0;
+ return nullptr;
return Callee;
}
static const AllocFnsTy *getAllocationData(const Value *V, AllocType AllocTy,
const TargetLibraryInfo *TLI,
bool LookThroughBitCast = false) {
+ // Skip intrinsics
+ if (isa<IntrinsicInst>(V))
+ return nullptr;
+
Function *Callee = getCalledFunction(V, LookThroughBitCast);
if (!Callee)
- return 0;
+ return nullptr;
// Make sure that the function is available.
StringRef FnName = Callee->getName();
LibFunc::Func TLIFn;
if (!TLI || !TLI->getLibFunc(FnName, TLIFn) || !TLI->has(TLIFn))
- return 0;
+ return nullptr;
unsigned i = 0;
bool found = false;
}
}
if (!found)
- return 0;
+ return nullptr;
const AllocFnsTy *FnData = &AllocationFnData[i];
- if ((FnData->AllocTy & AllocTy) == 0)
- return 0;
+ if ((FnData->AllocTy & AllocTy) != FnData->AllocTy)
+ return nullptr;
// Check function prototype.
int FstParam = FnData->FstParam;
FTy->getParamType(SndParam)->isIntegerTy(32) ||
FTy->getParamType(SndParam)->isIntegerTy(64)))
return FnData;
- return 0;
+ return nullptr;
}
static bool hasNoAliasAttr(const Value *V, bool LookThroughBitCast) {
return getAllocationData(V, ReallocLike, TLI, LookThroughBitCast);
}
+/// \brief Tests if a value is a call or invoke to a library function that
+/// allocates memory and never returns null (such as operator new).
+bool llvm::isOperatorNewLikeFn(const Value *V, const TargetLibraryInfo *TLI,
+ bool LookThroughBitCast) {
+ return getAllocationData(V, OpNewLike, TLI, LookThroughBitCast);
+}
+
/// 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 TargetLibraryInfo *TLI) {
- return isMallocLikeFn(I, TLI) ? dyn_cast<CallInst>(I) : 0;
+ return isMallocLikeFn(I, TLI) ? dyn_cast<CallInst>(I) : nullptr;
}
-static Value *computeArraySize(const CallInst *CI, const DataLayout *TD,
+static Value *computeArraySize(const CallInst *CI, const DataLayout &DL,
const TargetLibraryInfo *TLI,
bool LookThroughSExt = false) {
if (!CI)
- return NULL;
+ return nullptr;
// The size of the malloc's result type must be known to determine array size.
Type *T = getMallocAllocatedType(CI, TLI);
- if (!T || !T->isSized() || !TD)
- return NULL;
+ if (!T || !T->isSized())
+ return nullptr;
- unsigned ElementSize = TD->getTypeAllocSize(T);
+ unsigned ElementSize = DL.getTypeAllocSize(T);
if (StructType *ST = dyn_cast<StructType>(T))
- ElementSize = TD->getStructLayout(ST)->getSizeInBytes();
+ ElementSize = DL.getStructLayout(ST)->getSizeInBytes();
// 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;
+ Value *Multiple = nullptr;
if (ComputeMultiple(MallocArg, ElementSize, Multiple,
LookThroughSExt))
return Multiple;
- 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.
-const CallInst *llvm::isArrayMalloc(const Value *I,
- const DataLayout *TD,
- const TargetLibraryInfo *TLI) {
- const CallInst *CI = extractMallocCall(I, TLI);
- Value *ArraySize = computeArraySize(CI, TD, TLI);
-
- 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;
+ return nullptr;
}
/// getMallocType - Returns the PointerType resulting from the malloc call.
PointerType *llvm::getMallocType(const CallInst *CI,
const TargetLibraryInfo *TLI) {
assert(isMallocLikeFn(CI, TLI) && "getMallocType and not malloc call");
-
- PointerType *MallocType = NULL;
+
+ PointerType *MallocType = nullptr;
unsigned NumOfBitCastUses = 0;
// Determine if CallInst has a bitcast use.
- for (Value::const_use_iterator UI = CI->use_begin(), E = CI->use_end();
- UI != E; )
+ for (Value::const_user_iterator UI = CI->user_begin(), E = CI->user_end();
+ UI != E;)
if (const BitCastInst *BCI = dyn_cast<BitCastInst>(*UI++)) {
MallocType = cast<PointerType>(BCI->getDestTy());
NumOfBitCastUses++;
return cast<PointerType>(CI->getType());
// Type could not be determined.
- return NULL;
+ return nullptr;
}
/// getMallocAllocatedType - Returns the Type allocated by malloc call.
Type *llvm::getMallocAllocatedType(const CallInst *CI,
const TargetLibraryInfo *TLI) {
PointerType *PT = getMallocType(CI, TLI);
- return PT ? PT->getElementType() : NULL;
+ return PT ? PT->getElementType() : nullptr;
}
-/// getMallocArraySize - Returns the array size of a malloc call. If the
+/// 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 DataLayout *TD,
+Value *llvm::getMallocArraySize(CallInst *CI, const DataLayout &DL,
const TargetLibraryInfo *TLI,
bool LookThroughSExt) {
assert(isMallocLikeFn(CI, TLI) && "getMallocArraySize and not malloc call");
- return computeArraySize(CI, TD, TLI, LookThroughSExt);
+ return computeArraySize(CI, DL, TLI, LookThroughSExt);
}
/// is a calloc call.
const CallInst *llvm::extractCallocCall(const Value *I,
const TargetLibraryInfo *TLI) {
- return isCallocLikeFn(I, TLI) ? cast<CallInst>(I) : 0;
+ return isCallocLikeFn(I, TLI) ? cast<CallInst>(I) : nullptr;
}
/// isFreeCall - Returns non-null if the value is a call to the builtin free()
const CallInst *llvm::isFreeCall(const Value *I, const TargetLibraryInfo *TLI) {
const CallInst *CI = dyn_cast<CallInst>(I);
- if (!CI)
- return 0;
+ if (!CI || isa<IntrinsicInst>(CI))
+ return nullptr;
Function *Callee = CI->getCalledFunction();
- if (Callee == 0 || !Callee->isDeclaration())
- return 0;
+ if (Callee == nullptr)
+ return nullptr;
StringRef FnName = Callee->getName();
LibFunc::Func TLIFn;
if (!TLI || !TLI->getLibFunc(FnName, TLIFn) || !TLI->has(TLIFn))
- return 0;
-
- if (TLIFn != LibFunc::free &&
- TLIFn != LibFunc::ZdlPv && // operator delete(void*)
- TLIFn != LibFunc::ZdaPv) // operator delete[](void*)
- return 0;
+ return nullptr;
+
+ unsigned ExpectedNumParams;
+ if (TLIFn == LibFunc::free ||
+ TLIFn == LibFunc::ZdlPv || // operator delete(void*)
+ TLIFn == LibFunc::ZdaPv) // operator delete[](void*)
+ ExpectedNumParams = 1;
+ else if (TLIFn == LibFunc::ZdlPvj || // delete(void*, uint)
+ TLIFn == LibFunc::ZdlPvm || // delete(void*, ulong)
+ TLIFn == LibFunc::ZdlPvRKSt9nothrow_t || // delete(void*, nothrow)
+ TLIFn == LibFunc::ZdaPvj || // delete[](void*, uint)
+ TLIFn == LibFunc::ZdaPvm || // delete[](void*, ulong)
+ TLIFn == LibFunc::ZdaPvRKSt9nothrow_t) // delete[](void*, nothrow)
+ ExpectedNumParams = 2;
+ else
+ return nullptr;
// Check free prototype.
- // FIXME: workaround for PR5130, this will be obsolete when a nobuiltin
+ // FIXME: workaround for PR5130, this will be obsolete when a nobuiltin
// attribute will exist.
FunctionType *FTy = Callee->getFunctionType();
if (!FTy->getReturnType()->isVoidTy())
- return 0;
- if (FTy->getNumParams() != 1)
- return 0;
+ return nullptr;
+ if (FTy->getNumParams() != ExpectedNumParams)
+ return nullptr;
if (FTy->getParamType(0) != Type::getInt8PtrTy(Callee->getContext()))
- return 0;
+ return nullptr;
return CI;
}
/// object size in Size if successful, and false otherwise.
/// If RoundToAlign is true, then Size is rounded up to the aligment of allocas,
/// byval arguments, and global variables.
-bool llvm::getObjectSize(const Value *Ptr, uint64_t &Size, const DataLayout *TD,
+bool llvm::getObjectSize(const Value *Ptr, uint64_t &Size, const DataLayout &DL,
const TargetLibraryInfo *TLI, bool RoundToAlign) {
- if (!TD)
- return false;
-
- ObjectSizeOffsetVisitor Visitor(TD, TLI, Ptr->getContext(), RoundToAlign);
+ ObjectSizeOffsetVisitor Visitor(DL, TLI, Ptr->getContext(), RoundToAlign);
SizeOffsetType Data = Visitor.compute(const_cast<Value*>(Ptr));
if (!Visitor.bothKnown(Data))
return false;
return Size;
}
-ObjectSizeOffsetVisitor::ObjectSizeOffsetVisitor(const DataLayout *TD,
+ObjectSizeOffsetVisitor::ObjectSizeOffsetVisitor(const DataLayout &DL,
const TargetLibraryInfo *TLI,
LLVMContext &Context,
bool RoundToAlign)
-: TD(TD), TLI(TLI), RoundToAlign(RoundToAlign) {
- IntegerType *IntTy = TD->getIntPtrType(Context);
- IntTyBits = IntTy->getBitWidth();
- Zero = APInt::getNullValue(IntTyBits);
+ : DL(DL), TLI(TLI), RoundToAlign(RoundToAlign) {
+ // Pointer size must be rechecked for each object visited since it could have
+ // a different address space.
}
SizeOffsetType ObjectSizeOffsetVisitor::compute(Value *V) {
- V = V->stripPointerCasts();
+ IntTyBits = DL.getPointerTypeSizeInBits(V->getType());
+ Zero = APInt::getNullValue(IntTyBits);
- if (isa<Instruction>(V) || isa<GEPOperator>(V)) {
- // If we have already seen this instruction, bail out.
- if (!SeenInsts.insert(V))
+ V = V->stripPointerCasts();
+ if (Instruction *I = dyn_cast<Instruction>(V)) {
+ // If we have already seen this instruction, bail out. Cycles can happen in
+ // unreachable code after constant propagation.
+ if (!SeenInsts.insert(I).second)
return unknown();
- SizeOffsetType Ret;
if (GEPOperator *GEP = dyn_cast<GEPOperator>(V))
- Ret = visitGEPOperator(*GEP);
- else
- Ret = visit(cast<Instruction>(*V));
- SeenInsts.erase(V);
- return Ret;
+ return visitGEPOperator(*GEP);
+ return visit(*I);
}
-
if (Argument *A = dyn_cast<Argument>(V))
return visitArgument(*A);
if (ConstantPointerNull *P = dyn_cast<ConstantPointerNull>(V))
if (ConstantExpr *CE = dyn_cast<ConstantExpr>(V)) {
if (CE->getOpcode() == Instruction::IntToPtr)
return unknown(); // clueless
+ if (CE->getOpcode() == Instruction::GetElementPtr)
+ return visitGEPOperator(cast<GEPOperator>(*CE));
}
DEBUG(dbgs() << "ObjectSizeOffsetVisitor::compute() unhandled value: " << *V
if (!I.getAllocatedType()->isSized())
return unknown();
- APInt Size(IntTyBits, TD->getTypeAllocSize(I.getAllocatedType()));
+ APInt Size(IntTyBits, DL.getTypeAllocSize(I.getAllocatedType()));
if (!I.isArrayAllocation())
return std::make_pair(align(Size, I.getAlignment()), Zero);
SizeOffsetType ObjectSizeOffsetVisitor::visitArgument(Argument &A) {
// no interprocedural analysis is done at the moment
- if (!A.hasByValAttr()) {
+ if (!A.hasByValOrInAllocaAttr()) {
++ObjectVisitorArgument;
return unknown();
}
PointerType *PT = cast<PointerType>(A.getType());
- APInt Size(IntTyBits, TD->getTypeAllocSize(PT->getElementType()));
+ APInt Size(IntTyBits, DL.getTypeAllocSize(PT->getElementType()));
return std::make_pair(align(Size, A.getParamAlignment()), Zero);
}
SizeOffsetType ObjectSizeOffsetVisitor::visitGEPOperator(GEPOperator &GEP) {
SizeOffsetType PtrData = compute(GEP.getPointerOperand());
APInt Offset(IntTyBits, 0);
- if (!bothKnown(PtrData) || !GEP.accumulateConstantOffset(*TD, Offset))
+ if (!bothKnown(PtrData) || !GEP.accumulateConstantOffset(DL, Offset))
return unknown();
return std::make_pair(PtrData.first, PtrData.second + Offset);
if (!GV.hasDefinitiveInitializer())
return unknown();
- APInt Size(IntTyBits, TD->getTypeAllocSize(GV.getType()->getElementType()));
+ APInt Size(IntTyBits, DL.getTypeAllocSize(GV.getType()->getElementType()));
return std::make_pair(align(Size, GV.getAlignment()), Zero);
}
return unknown();
}
-SizeOffsetType ObjectSizeOffsetVisitor::visitPHINode(PHINode &PHI) {
- if (PHI.getNumIncomingValues() == 0)
- return unknown();
-
- SizeOffsetType Ret = compute(PHI.getIncomingValue(0));
- if (!bothKnown(Ret))
- return unknown();
-
- // verify that all PHI incoming pointers have the same size and offset
- for (unsigned i = 1, e = PHI.getNumIncomingValues(); i != e; ++i) {
- SizeOffsetType EdgeData = compute(PHI.getIncomingValue(i));
- if (!bothKnown(EdgeData) || EdgeData != Ret)
- return unknown();
- }
- return Ret;
+SizeOffsetType ObjectSizeOffsetVisitor::visitPHINode(PHINode&) {
+ // too complex to analyze statically.
+ return unknown();
}
SizeOffsetType ObjectSizeOffsetVisitor::visitSelectInst(SelectInst &I) {
return unknown();
}
-
-ObjectSizeOffsetEvaluator::ObjectSizeOffsetEvaluator(const DataLayout *TD,
- const TargetLibraryInfo *TLI,
- LLVMContext &Context)
-: TD(TD), TLI(TLI), Context(Context), Builder(Context, TargetFolder(TD)) {
- IntTy = TD->getIntPtrType(Context);
- Zero = ConstantInt::get(IntTy, 0);
+ObjectSizeOffsetEvaluator::ObjectSizeOffsetEvaluator(
+ const DataLayout &DL, const TargetLibraryInfo *TLI, LLVMContext &Context,
+ bool RoundToAlign)
+ : DL(DL), TLI(TLI), Context(Context), Builder(Context, TargetFolder(DL)),
+ RoundToAlign(RoundToAlign) {
+ // IntTy and Zero must be set for each compute() since the address space may
+ // be different for later objects.
}
SizeOffsetEvalType ObjectSizeOffsetEvaluator::compute(Value *V) {
+ // XXX - Are vectors of pointers possible here?
+ IntTy = cast<IntegerType>(DL.getIntPtrType(V->getType()));
+ Zero = ConstantInt::get(IntTy, 0);
+
SizeOffsetEvalType Result = compute_(V);
if (!bothKnown(Result)) {
}
SizeOffsetEvalType ObjectSizeOffsetEvaluator::compute_(Value *V) {
- ObjectSizeOffsetVisitor Visitor(TD, TLI, Context);
+ ObjectSizeOffsetVisitor Visitor(DL, TLI, Context, RoundToAlign);
SizeOffsetType Const = Visitor.compute(V);
if (Visitor.bothKnown(Const))
return std::make_pair(ConstantInt::get(Context, Const.first),
if (Instruction *I = dyn_cast<Instruction>(V))
Builder.SetInsertPoint(I);
- // record the pointers that were handled in this run, so that they can be
- // cleaned later if something fails
- SeenVals.insert(V);
-
// now compute the size and offset
SizeOffsetEvalType Result;
- if (GEPOperator *GEP = dyn_cast<GEPOperator>(V)) {
+
+ // Record the pointers that were handled in this run, so that they can be
+ // cleaned later if something fails. We also use this set to break cycles that
+ // can occur in dead code.
+ if (!SeenVals.insert(V).second) {
+ Result = unknown();
+ } else if (GEPOperator *GEP = dyn_cast<GEPOperator>(V)) {
Result = visitGEPOperator(*GEP);
} else if (Instruction *I = dyn_cast<Instruction>(V)) {
Result = visit(*I);
assert(I.isArrayAllocation());
Value *ArraySize = I.getArraySize();
Value *Size = ConstantInt::get(ArraySize->getType(),
- TD->getTypeAllocSize(I.getAllocatedType()));
+ DL.getTypeAllocSize(I.getAllocatedType()));
Size = Builder.CreateMul(Size, ArraySize);
return std::make_pair(Size, Zero);
}
if (!bothKnown(PtrData))
return unknown();
- Value *Offset = EmitGEPOffset(&Builder, *TD, &GEP, /*NoAssumptions=*/true);
+ Value *Offset = EmitGEPOffset(&Builder, DL, &GEP, /*NoAssumptions=*/true);
Offset = Builder.CreateAdd(PtrData.second, Offset);
return std::make_pair(PtrData.first, Offset);
}
projects / oota-llvm.git / blobdiff