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 11263509Sdim// or free memory. 12198892Srdivacky// 13198892Srdivacky//===----------------------------------------------------------------------===// 14198892Srdivacky 15198892Srdivacky#ifndef LLVM_ANALYSIS_MEMORYBUILTINS_H 16198892Srdivacky#define LLVM_ANALYSIS_MEMORYBUILTINS_H 17198892Srdivacky 18245431Sdim#include "llvm/ADT/DenseMap.h" 19245431Sdim#include "llvm/ADT/SmallPtrSet.h" 20252723Sdim#include "llvm/IR/IRBuilder.h" 21252723Sdim#include "llvm/IR/Operator.h" 22252723Sdim#include "llvm/InstVisitor.h" 23245431Sdim#include "llvm/Support/DataTypes.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 67263509Sdim/// \brief Tests if a value is a call or invoke to a library function that 68263509Sdim/// allocates memory and never returns null (such as operator new). 69263509Sdimbool isOperatorNewLikeFn(const Value *V, const TargetLibraryInfo *TLI, 70263509Sdim bool LookThroughBitCast = false); 71245431Sdim 72198892Srdivacky//===----------------------------------------------------------------------===// 73198892Srdivacky// malloc Call Utility Functions. 74198892Srdivacky// 75198892Srdivacky 76198892Srdivacky/// extractMallocCall - Returns the corresponding CallInst if the instruction 77198892Srdivacky/// is a malloc call. Since CallInst::CreateMalloc() only creates calls, we 78198892Srdivacky/// ignore InvokeInst here. 79245431Sdimconst CallInst *extractMallocCall(const Value *I, const TargetLibraryInfo *TLI); 80245431Sdimstatic inline CallInst *extractMallocCall(Value *I, 81245431Sdim const TargetLibraryInfo *TLI) { 82245431Sdim return const_cast<CallInst*>(extractMallocCall((const Value*)I, TLI)); 83245431Sdim} 84198892Srdivacky 85263509Sdim/// isArrayMalloc - Returns the corresponding CallInst if the instruction 86198892Srdivacky/// is a call to malloc whose array size can be determined and the array size 87198892Srdivacky/// is not constant 1. Otherwise, return NULL. 88263509Sdimconst CallInst *isArrayMalloc(const Value *I, const DataLayout *DL, 89245431Sdim const TargetLibraryInfo *TLI); 90198892Srdivacky 91198892Srdivacky/// getMallocType - Returns the PointerType resulting from the malloc call. 92198953Srdivacky/// The PointerType depends on the number of bitcast uses of the malloc call: 93198953Srdivacky/// 0: PointerType is the malloc calls' return type. 94198953Srdivacky/// 1: PointerType is the bitcast's result type. 95198953Srdivacky/// >1: Unique PointerType cannot be determined, return NULL. 96245431SdimPointerType *getMallocType(const CallInst *CI, const TargetLibraryInfo *TLI); 97198892Srdivacky 98198953Srdivacky/// getMallocAllocatedType - Returns the Type allocated by malloc call. 99198953Srdivacky/// The Type depends on the number of bitcast uses of the malloc call: 100198953Srdivacky/// 0: PointerType is the malloc calls' return type. 101198953Srdivacky/// 1: PointerType is the bitcast's result type. 102198953Srdivacky/// >1: Unique PointerType cannot be determined, return NULL. 103245431SdimType *getMallocAllocatedType(const CallInst *CI, const TargetLibraryInfo *TLI); 104198892Srdivacky 105263509Sdim/// getMallocArraySize - Returns the array size of a malloc call. If the 106198892Srdivacky/// argument passed to malloc is a multiple of the size of the malloced type, 107198892Srdivacky/// then return that multiple. For non-array mallocs, the multiple is 108198892Srdivacky/// constant 1. Otherwise, return NULL for mallocs whose array size cannot be 109198892Srdivacky/// determined. 110263509SdimValue *getMallocArraySize(CallInst *CI, const DataLayout *DL, 111245431Sdim const TargetLibraryInfo *TLI, 112199481Srdivacky bool LookThroughSExt = false); 113245431Sdim 114245431Sdim 115198892Srdivacky//===----------------------------------------------------------------------===// 116245431Sdim// calloc Call Utility Functions. 117245431Sdim// 118245431Sdim 119245431Sdim/// extractCallocCall - Returns the corresponding CallInst if the instruction 120245431Sdim/// is a calloc call. 121245431Sdimconst CallInst *extractCallocCall(const Value *I, const TargetLibraryInfo *TLI); 122245431Sdimstatic inline CallInst *extractCallocCall(Value *I, 123245431Sdim const TargetLibraryInfo *TLI) { 124245431Sdim return const_cast<CallInst*>(extractCallocCall((const Value*)I, TLI)); 125245431Sdim} 126245431Sdim 127245431Sdim 128245431Sdim//===----------------------------------------------------------------------===// 129198892Srdivacky// free Call Utility Functions. 130198892Srdivacky// 131198892Srdivacky 132210299Sed/// isFreeCall - Returns non-null if the value is a call to the builtin free() 133245431Sdimconst CallInst *isFreeCall(const Value *I, const TargetLibraryInfo *TLI); 134263509Sdim 135245431Sdimstatic inline CallInst *isFreeCall(Value *I, const TargetLibraryInfo *TLI) { 136245431Sdim return const_cast<CallInst*>(isFreeCall((const Value*)I, TLI)); 137218893Sdim} 138198892Srdivacky 139263509Sdim 140245431Sdim//===----------------------------------------------------------------------===// 141245431Sdim// Utility functions to compute size of objects. 142245431Sdim// 143245431Sdim 144245431Sdim/// \brief Compute the size of the object pointed by Ptr. Returns true and the 145252723Sdim/// object size in Size if successful, and false otherwise. In this context, by 146252723Sdim/// object we mean the region of memory starting at Ptr to the end of the 147252723Sdim/// underlying object pointed to by Ptr. 148245431Sdim/// If RoundToAlign is true, then Size is rounded up to the aligment of allocas, 149245431Sdim/// byval arguments, and global variables. 150263509Sdimbool getObjectSize(const Value *Ptr, uint64_t &Size, const DataLayout *DL, 151245431Sdim const TargetLibraryInfo *TLI, bool RoundToAlign = false); 152245431Sdim 153245431Sdim 154245431Sdim 155245431Sdimtypedef std::pair<APInt, APInt> SizeOffsetType; 156245431Sdim 157263509Sdim/// \brief Evaluate the size and offset of an object pointed to by a Value* 158245431Sdim/// statically. Fails if size or offset are not known at compile time. 159245431Sdimclass ObjectSizeOffsetVisitor 160245431Sdim : public InstVisitor<ObjectSizeOffsetVisitor, SizeOffsetType> { 161245431Sdim 162263509Sdim const DataLayout *DL; 163245431Sdim const TargetLibraryInfo *TLI; 164245431Sdim bool RoundToAlign; 165245431Sdim unsigned IntTyBits; 166245431Sdim APInt Zero; 167245431Sdim SmallPtrSet<Instruction *, 8> SeenInsts; 168245431Sdim 169245431Sdim APInt align(APInt Size, uint64_t Align); 170245431Sdim 171245431Sdim SizeOffsetType unknown() { 172245431Sdim return std::make_pair(APInt(), APInt()); 173245431Sdim } 174245431Sdim 175245431Sdimpublic: 176263509Sdim ObjectSizeOffsetVisitor(const DataLayout *DL, const TargetLibraryInfo *TLI, 177245431Sdim LLVMContext &Context, bool RoundToAlign = false); 178245431Sdim 179245431Sdim SizeOffsetType compute(Value *V); 180245431Sdim 181245431Sdim bool knownSize(SizeOffsetType &SizeOffset) { 182245431Sdim return SizeOffset.first.getBitWidth() > 1; 183245431Sdim } 184245431Sdim 185245431Sdim bool knownOffset(SizeOffsetType &SizeOffset) { 186245431Sdim return SizeOffset.second.getBitWidth() > 1; 187245431Sdim } 188245431Sdim 189245431Sdim bool bothKnown(SizeOffsetType &SizeOffset) { 190245431Sdim return knownSize(SizeOffset) && knownOffset(SizeOffset); 191245431Sdim } 192245431Sdim 193245431Sdim SizeOffsetType visitAllocaInst(AllocaInst &I); 194245431Sdim SizeOffsetType visitArgument(Argument &A); 195245431Sdim SizeOffsetType visitCallSite(CallSite CS); 196245431Sdim SizeOffsetType visitConstantPointerNull(ConstantPointerNull&); 197245431Sdim SizeOffsetType visitExtractElementInst(ExtractElementInst &I); 198245431Sdim SizeOffsetType visitExtractValueInst(ExtractValueInst &I); 199245431Sdim SizeOffsetType visitGEPOperator(GEPOperator &GEP); 200252723Sdim SizeOffsetType visitGlobalAlias(GlobalAlias &GA); 201245431Sdim SizeOffsetType visitGlobalVariable(GlobalVariable &GV); 202245431Sdim SizeOffsetType visitIntToPtrInst(IntToPtrInst&); 203245431Sdim SizeOffsetType visitLoadInst(LoadInst &I); 204245431Sdim SizeOffsetType visitPHINode(PHINode&); 205245431Sdim SizeOffsetType visitSelectInst(SelectInst &I); 206245431Sdim SizeOffsetType visitUndefValue(UndefValue&); 207245431Sdim SizeOffsetType visitInstruction(Instruction &I); 208245431Sdim}; 209245431Sdim 210245431Sdimtypedef std::pair<Value*, Value*> SizeOffsetEvalType; 211245431Sdim 212245431Sdim 213263509Sdim/// \brief Evaluate the size and offset of an object pointed to by a Value*. 214245431Sdim/// May create code to compute the result at run-time. 215245431Sdimclass ObjectSizeOffsetEvaluator 216245431Sdim : public InstVisitor<ObjectSizeOffsetEvaluator, SizeOffsetEvalType> { 217245431Sdim 218245431Sdim typedef IRBuilder<true, TargetFolder> BuilderTy; 219245431Sdim typedef std::pair<WeakVH, WeakVH> WeakEvalType; 220245431Sdim typedef DenseMap<const Value*, WeakEvalType> CacheMapTy; 221245431Sdim typedef SmallPtrSet<const Value*, 8> PtrSetTy; 222245431Sdim 223263509Sdim const DataLayout *DL; 224245431Sdim const TargetLibraryInfo *TLI; 225245431Sdim LLVMContext &Context; 226245431Sdim BuilderTy Builder; 227245431Sdim IntegerType *IntTy; 228245431Sdim Value *Zero; 229245431Sdim CacheMapTy CacheMap; 230245431Sdim PtrSetTy SeenVals; 231263509Sdim bool RoundToAlign; 232245431Sdim 233245431Sdim SizeOffsetEvalType unknown() { 234245431Sdim return std::make_pair((Value*)0, (Value*)0); 235245431Sdim } 236245431Sdim SizeOffsetEvalType compute_(Value *V); 237245431Sdim 238245431Sdimpublic: 239263509Sdim ObjectSizeOffsetEvaluator(const DataLayout *DL, const TargetLibraryInfo *TLI, 240263509Sdim LLVMContext &Context, bool RoundToAlign = false); 241245431Sdim SizeOffsetEvalType compute(Value *V); 242245431Sdim 243245431Sdim bool knownSize(SizeOffsetEvalType SizeOffset) { 244245431Sdim return SizeOffset.first; 245245431Sdim } 246245431Sdim 247245431Sdim bool knownOffset(SizeOffsetEvalType SizeOffset) { 248245431Sdim return SizeOffset.second; 249245431Sdim } 250245431Sdim 251245431Sdim bool anyKnown(SizeOffsetEvalType SizeOffset) { 252245431Sdim return knownSize(SizeOffset) || knownOffset(SizeOffset); 253245431Sdim } 254245431Sdim 255245431Sdim bool bothKnown(SizeOffsetEvalType SizeOffset) { 256245431Sdim return knownSize(SizeOffset) && knownOffset(SizeOffset); 257245431Sdim } 258245431Sdim 259245431Sdim SizeOffsetEvalType visitAllocaInst(AllocaInst &I); 260245431Sdim SizeOffsetEvalType visitCallSite(CallSite CS); 261245431Sdim SizeOffsetEvalType visitExtractElementInst(ExtractElementInst &I); 262245431Sdim SizeOffsetEvalType visitExtractValueInst(ExtractValueInst &I); 263245431Sdim SizeOffsetEvalType visitGEPOperator(GEPOperator &GEP); 264245431Sdim SizeOffsetEvalType visitIntToPtrInst(IntToPtrInst&); 265245431Sdim SizeOffsetEvalType visitLoadInst(LoadInst &I); 266245431Sdim SizeOffsetEvalType visitPHINode(PHINode &PHI); 267245431Sdim SizeOffsetEvalType visitSelectInst(SelectInst &I); 268245431Sdim SizeOffsetEvalType visitInstruction(Instruction &I); 269245431Sdim}; 270245431Sdim 271198892Srdivacky} // End llvm namespace 272198892Srdivacky 273198892Srdivacky#endif 274