MemoryBuiltins.h revision 245431
1198892Srdivacky//===- llvm/Analysis/MemoryBuiltins.h- Calls to memory builtins -*- C++ -*-===// 2198892Srdivacky// 3198892Srdivacky// The LLVM Compiler Infrastructure 4198892Srdivacky// 5198892Srdivacky// This file is distributed under the University of Illinois Open Source 6198892Srdivacky// License. See LICENSE.TXT for details. 7198892Srdivacky// 8198892Srdivacky//===----------------------------------------------------------------------===// 9198892Srdivacky// 10198892Srdivacky// This family of functions identifies calls to builtin functions that allocate 11198892Srdivacky// or free memory. 12198892Srdivacky// 13198892Srdivacky//===----------------------------------------------------------------------===// 14198892Srdivacky 15198892Srdivacky#ifndef LLVM_ANALYSIS_MEMORYBUILTINS_H 16198892Srdivacky#define LLVM_ANALYSIS_MEMORYBUILTINS_H 17198892Srdivacky 18245431Sdim#include "llvm/IRBuilder.h" 19245431Sdim#include "llvm/Operator.h" 20245431Sdim#include "llvm/ADT/DenseMap.h" 21245431Sdim#include "llvm/ADT/SmallPtrSet.h" 22245431Sdim#include "llvm/Support/DataTypes.h" 23245431Sdim#include "llvm/Support/InstVisitor.h" 24245431Sdim#include "llvm/Support/TargetFolder.h" 25245431Sdim#include "llvm/Support/ValueHandle.h" 26245431Sdim 27198892Srdivackynamespace llvm { 28198892Srdivackyclass CallInst; 29198892Srdivackyclass PointerType; 30245431Sdimclass DataLayout; 31245431Sdimclass TargetLibraryInfo; 32198892Srdivackyclass Type; 33198892Srdivackyclass Value; 34198892Srdivacky 35245431Sdim 36245431Sdim/// \brief Tests if a value is a call or invoke to a library function that 37245431Sdim/// allocates or reallocates memory (either malloc, calloc, realloc, or strdup 38245431Sdim/// like). 39245431Sdimbool isAllocationFn(const Value *V, const TargetLibraryInfo *TLI, 40245431Sdim bool LookThroughBitCast = false); 41245431Sdim 42245431Sdim/// \brief Tests if a value is a call or invoke to a function that returns a 43245431Sdim/// NoAlias pointer (including malloc/calloc/realloc/strdup-like functions). 44245431Sdimbool isNoAliasFn(const Value *V, const TargetLibraryInfo *TLI, 45245431Sdim bool LookThroughBitCast = false); 46245431Sdim 47245431Sdim/// \brief Tests if a value is a call or invoke to a library function that 48245431Sdim/// allocates uninitialized memory (such as malloc). 49245431Sdimbool isMallocLikeFn(const Value *V, const TargetLibraryInfo *TLI, 50245431Sdim bool LookThroughBitCast = false); 51245431Sdim 52245431Sdim/// \brief Tests if a value is a call or invoke to a library function that 53245431Sdim/// allocates zero-filled memory (such as calloc). 54245431Sdimbool isCallocLikeFn(const Value *V, const TargetLibraryInfo *TLI, 55245431Sdim bool LookThroughBitCast = false); 56245431Sdim 57245431Sdim/// \brief Tests if a value is a call or invoke to a library function that 58245431Sdim/// allocates memory (either malloc, calloc, or strdup like). 59245431Sdimbool isAllocLikeFn(const Value *V, const TargetLibraryInfo *TLI, 60245431Sdim bool LookThroughBitCast = false); 61245431Sdim 62245431Sdim/// \brief Tests if a value is a call or invoke to a library function that 63245431Sdim/// reallocates memory (such as realloc). 64245431Sdimbool isReallocLikeFn(const Value *V, const TargetLibraryInfo *TLI, 65245431Sdim bool LookThroughBitCast = false); 66245431Sdim 67245431Sdim 68198892Srdivacky//===----------------------------------------------------------------------===// 69198892Srdivacky// malloc Call Utility Functions. 70198892Srdivacky// 71198892Srdivacky 72198892Srdivacky/// extractMallocCall - Returns the corresponding CallInst if the instruction 73198892Srdivacky/// is a malloc call. Since CallInst::CreateMalloc() only creates calls, we 74198892Srdivacky/// ignore InvokeInst here. 75245431Sdimconst CallInst *extractMallocCall(const Value *I, const TargetLibraryInfo *TLI); 76245431Sdimstatic inline CallInst *extractMallocCall(Value *I, 77245431Sdim const TargetLibraryInfo *TLI) { 78245431Sdim return const_cast<CallInst*>(extractMallocCall((const Value*)I, TLI)); 79245431Sdim} 80198892Srdivacky 81198892Srdivacky/// isArrayMalloc - Returns the corresponding CallInst if the instruction 82198892Srdivacky/// is a call to malloc whose array size can be determined and the array size 83198892Srdivacky/// is not constant 1. Otherwise, return NULL. 84245431Sdimconst CallInst *isArrayMalloc(const Value *I, const DataLayout *TD, 85245431Sdim const TargetLibraryInfo *TLI); 86198892Srdivacky 87198892Srdivacky/// getMallocType - Returns the PointerType resulting from the malloc call. 88198953Srdivacky/// The PointerType depends on the number of bitcast uses of the malloc call: 89198953Srdivacky/// 0: PointerType is the malloc calls' return type. 90198953Srdivacky/// 1: PointerType is the bitcast's result type. 91198953Srdivacky/// >1: Unique PointerType cannot be determined, return NULL. 92245431SdimPointerType *getMallocType(const CallInst *CI, const TargetLibraryInfo *TLI); 93198892Srdivacky 94198953Srdivacky/// getMallocAllocatedType - Returns the Type allocated by malloc call. 95198953Srdivacky/// The Type depends on the number of bitcast uses of the malloc call: 96198953Srdivacky/// 0: PointerType is the malloc calls' return type. 97198953Srdivacky/// 1: PointerType is the bitcast's result type. 98198953Srdivacky/// >1: Unique PointerType cannot be determined, return NULL. 99245431SdimType *getMallocAllocatedType(const CallInst *CI, const TargetLibraryInfo *TLI); 100198892Srdivacky 101198892Srdivacky/// getMallocArraySize - Returns the array size of a malloc call. If the 102198892Srdivacky/// argument passed to malloc is a multiple of the size of the malloced type, 103198892Srdivacky/// then return that multiple. For non-array mallocs, the multiple is 104198892Srdivacky/// constant 1. Otherwise, return NULL for mallocs whose array size cannot be 105198892Srdivacky/// determined. 106245431SdimValue *getMallocArraySize(CallInst *CI, const DataLayout *TD, 107245431Sdim const TargetLibraryInfo *TLI, 108199481Srdivacky bool LookThroughSExt = false); 109245431Sdim 110245431Sdim 111198892Srdivacky//===----------------------------------------------------------------------===// 112245431Sdim// calloc Call Utility Functions. 113245431Sdim// 114245431Sdim 115245431Sdim/// extractCallocCall - Returns the corresponding CallInst if the instruction 116245431Sdim/// is a calloc call. 117245431Sdimconst CallInst *extractCallocCall(const Value *I, const TargetLibraryInfo *TLI); 118245431Sdimstatic inline CallInst *extractCallocCall(Value *I, 119245431Sdim const TargetLibraryInfo *TLI) { 120245431Sdim return const_cast<CallInst*>(extractCallocCall((const Value*)I, TLI)); 121245431Sdim} 122245431Sdim 123245431Sdim 124245431Sdim//===----------------------------------------------------------------------===// 125198892Srdivacky// free Call Utility Functions. 126198892Srdivacky// 127198892Srdivacky 128210299Sed/// isFreeCall - Returns non-null if the value is a call to the builtin free() 129245431Sdimconst CallInst *isFreeCall(const Value *I, const TargetLibraryInfo *TLI); 130218893Sdim 131245431Sdimstatic inline CallInst *isFreeCall(Value *I, const TargetLibraryInfo *TLI) { 132245431Sdim return const_cast<CallInst*>(isFreeCall((const Value*)I, TLI)); 133218893Sdim} 134198892Srdivacky 135245431Sdim 136245431Sdim//===----------------------------------------------------------------------===// 137245431Sdim// Utility functions to compute size of objects. 138245431Sdim// 139245431Sdim 140245431Sdim/// \brief Compute the size of the object pointed by Ptr. Returns true and the 141245431Sdim/// object size in Size if successful, and false otherwise. 142245431Sdim/// If RoundToAlign is true, then Size is rounded up to the aligment of allocas, 143245431Sdim/// byval arguments, and global variables. 144245431Sdimbool getObjectSize(const Value *Ptr, uint64_t &Size, const DataLayout *TD, 145245431Sdim const TargetLibraryInfo *TLI, bool RoundToAlign = false); 146245431Sdim 147245431Sdim 148245431Sdim 149245431Sdimtypedef std::pair<APInt, APInt> SizeOffsetType; 150245431Sdim 151245431Sdim/// \brief Evaluate the size and offset of an object ponted by a Value* 152245431Sdim/// statically. Fails if size or offset are not known at compile time. 153245431Sdimclass ObjectSizeOffsetVisitor 154245431Sdim : public InstVisitor<ObjectSizeOffsetVisitor, SizeOffsetType> { 155245431Sdim 156245431Sdim const DataLayout *TD; 157245431Sdim const TargetLibraryInfo *TLI; 158245431Sdim bool RoundToAlign; 159245431Sdim unsigned IntTyBits; 160245431Sdim APInt Zero; 161245431Sdim SmallPtrSet<Instruction *, 8> SeenInsts; 162245431Sdim 163245431Sdim APInt align(APInt Size, uint64_t Align); 164245431Sdim 165245431Sdim SizeOffsetType unknown() { 166245431Sdim return std::make_pair(APInt(), APInt()); 167245431Sdim } 168245431Sdim 169245431Sdimpublic: 170245431Sdim ObjectSizeOffsetVisitor(const DataLayout *TD, const TargetLibraryInfo *TLI, 171245431Sdim LLVMContext &Context, bool RoundToAlign = false); 172245431Sdim 173245431Sdim SizeOffsetType compute(Value *V); 174245431Sdim 175245431Sdim bool knownSize(SizeOffsetType &SizeOffset) { 176245431Sdim return SizeOffset.first.getBitWidth() > 1; 177245431Sdim } 178245431Sdim 179245431Sdim bool knownOffset(SizeOffsetType &SizeOffset) { 180245431Sdim return SizeOffset.second.getBitWidth() > 1; 181245431Sdim } 182245431Sdim 183245431Sdim bool bothKnown(SizeOffsetType &SizeOffset) { 184245431Sdim return knownSize(SizeOffset) && knownOffset(SizeOffset); 185245431Sdim } 186245431Sdim 187245431Sdim SizeOffsetType visitAllocaInst(AllocaInst &I); 188245431Sdim SizeOffsetType visitArgument(Argument &A); 189245431Sdim SizeOffsetType visitCallSite(CallSite CS); 190245431Sdim SizeOffsetType visitConstantPointerNull(ConstantPointerNull&); 191245431Sdim SizeOffsetType visitExtractElementInst(ExtractElementInst &I); 192245431Sdim SizeOffsetType visitExtractValueInst(ExtractValueInst &I); 193245431Sdim SizeOffsetType visitGEPOperator(GEPOperator &GEP); 194245431Sdim SizeOffsetType visitGlobalVariable(GlobalVariable &GV); 195245431Sdim SizeOffsetType visitIntToPtrInst(IntToPtrInst&); 196245431Sdim SizeOffsetType visitLoadInst(LoadInst &I); 197245431Sdim SizeOffsetType visitPHINode(PHINode&); 198245431Sdim SizeOffsetType visitSelectInst(SelectInst &I); 199245431Sdim SizeOffsetType visitUndefValue(UndefValue&); 200245431Sdim SizeOffsetType visitInstruction(Instruction &I); 201245431Sdim}; 202245431Sdim 203245431Sdimtypedef std::pair<Value*, Value*> SizeOffsetEvalType; 204245431Sdim 205245431Sdim 206245431Sdim/// \brief Evaluate the size and offset of an object ponted by a Value*. 207245431Sdim/// May create code to compute the result at run-time. 208245431Sdimclass ObjectSizeOffsetEvaluator 209245431Sdim : public InstVisitor<ObjectSizeOffsetEvaluator, SizeOffsetEvalType> { 210245431Sdim 211245431Sdim typedef IRBuilder<true, TargetFolder> BuilderTy; 212245431Sdim typedef std::pair<WeakVH, WeakVH> WeakEvalType; 213245431Sdim typedef DenseMap<const Value*, WeakEvalType> CacheMapTy; 214245431Sdim typedef SmallPtrSet<const Value*, 8> PtrSetTy; 215245431Sdim 216245431Sdim const DataLayout *TD; 217245431Sdim const TargetLibraryInfo *TLI; 218245431Sdim LLVMContext &Context; 219245431Sdim BuilderTy Builder; 220245431Sdim IntegerType *IntTy; 221245431Sdim Value *Zero; 222245431Sdim CacheMapTy CacheMap; 223245431Sdim PtrSetTy SeenVals; 224245431Sdim 225245431Sdim SizeOffsetEvalType unknown() { 226245431Sdim return std::make_pair((Value*)0, (Value*)0); 227245431Sdim } 228245431Sdim SizeOffsetEvalType compute_(Value *V); 229245431Sdim 230245431Sdimpublic: 231245431Sdim ObjectSizeOffsetEvaluator(const DataLayout *TD, const TargetLibraryInfo *TLI, 232245431Sdim LLVMContext &Context); 233245431Sdim SizeOffsetEvalType compute(Value *V); 234245431Sdim 235245431Sdim bool knownSize(SizeOffsetEvalType SizeOffset) { 236245431Sdim return SizeOffset.first; 237245431Sdim } 238245431Sdim 239245431Sdim bool knownOffset(SizeOffsetEvalType SizeOffset) { 240245431Sdim return SizeOffset.second; 241245431Sdim } 242245431Sdim 243245431Sdim bool anyKnown(SizeOffsetEvalType SizeOffset) { 244245431Sdim return knownSize(SizeOffset) || knownOffset(SizeOffset); 245245431Sdim } 246245431Sdim 247245431Sdim bool bothKnown(SizeOffsetEvalType SizeOffset) { 248245431Sdim return knownSize(SizeOffset) && knownOffset(SizeOffset); 249245431Sdim } 250245431Sdim 251245431Sdim SizeOffsetEvalType visitAllocaInst(AllocaInst &I); 252245431Sdim SizeOffsetEvalType visitCallSite(CallSite CS); 253245431Sdim SizeOffsetEvalType visitExtractElementInst(ExtractElementInst &I); 254245431Sdim SizeOffsetEvalType visitExtractValueInst(ExtractValueInst &I); 255245431Sdim SizeOffsetEvalType visitGEPOperator(GEPOperator &GEP); 256245431Sdim SizeOffsetEvalType visitIntToPtrInst(IntToPtrInst&); 257245431Sdim SizeOffsetEvalType visitLoadInst(LoadInst &I); 258245431Sdim SizeOffsetEvalType visitPHINode(PHINode &PHI); 259245431Sdim SizeOffsetEvalType visitSelectInst(SelectInst &I); 260245431Sdim SizeOffsetEvalType visitInstruction(Instruction &I); 261245431Sdim}; 262245431Sdim 263198892Srdivacky} // End llvm namespace 264198892Srdivacky 265198892Srdivacky#endif 266