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 11263508Sdim// or free memory. 12198892Srdivacky// 13198892Srdivacky//===----------------------------------------------------------------------===// 14198892Srdivacky 15198892Srdivacky#ifndef LLVM_ANALYSIS_MEMORYBUILTINS_H 16198892Srdivacky#define LLVM_ANALYSIS_MEMORYBUILTINS_H 17198892Srdivacky 18239462Sdim#include "llvm/ADT/DenseMap.h" 19239462Sdim#include "llvm/ADT/SmallPtrSet.h" 20249423Sdim#include "llvm/IR/IRBuilder.h" 21249423Sdim#include "llvm/IR/Operator.h" 22249423Sdim#include "llvm/InstVisitor.h" 23239462Sdim#include "llvm/Support/DataTypes.h" 24239462Sdim#include "llvm/Support/TargetFolder.h" 25239462Sdim#include "llvm/Support/ValueHandle.h" 26239462Sdim 27198892Srdivackynamespace llvm { 28198892Srdivackyclass CallInst; 29198892Srdivackyclass PointerType; 30243830Sdimclass DataLayout; 31243830Sdimclass TargetLibraryInfo; 32198892Srdivackyclass Type; 33198892Srdivackyclass Value; 34198892Srdivacky 35239462Sdim 36239462Sdim/// \brief Tests if a value is a call or invoke to a library function that 37239462Sdim/// allocates or reallocates memory (either malloc, calloc, realloc, or strdup 38239462Sdim/// like). 39243830Sdimbool isAllocationFn(const Value *V, const TargetLibraryInfo *TLI, 40243830Sdim bool LookThroughBitCast = false); 41239462Sdim 42239462Sdim/// \brief Tests if a value is a call or invoke to a function that returns a 43239462Sdim/// NoAlias pointer (including malloc/calloc/realloc/strdup-like functions). 44243830Sdimbool isNoAliasFn(const Value *V, const TargetLibraryInfo *TLI, 45243830Sdim bool LookThroughBitCast = false); 46239462Sdim 47239462Sdim/// \brief Tests if a value is a call or invoke to a library function that 48239462Sdim/// allocates uninitialized memory (such as malloc). 49243830Sdimbool isMallocLikeFn(const Value *V, const TargetLibraryInfo *TLI, 50243830Sdim bool LookThroughBitCast = false); 51239462Sdim 52239462Sdim/// \brief Tests if a value is a call or invoke to a library function that 53239462Sdim/// allocates zero-filled memory (such as calloc). 54243830Sdimbool isCallocLikeFn(const Value *V, const TargetLibraryInfo *TLI, 55243830Sdim bool LookThroughBitCast = false); 56239462Sdim 57239462Sdim/// \brief Tests if a value is a call or invoke to a library function that 58239462Sdim/// allocates memory (either malloc, calloc, or strdup like). 59243830Sdimbool isAllocLikeFn(const Value *V, const TargetLibraryInfo *TLI, 60243830Sdim bool LookThroughBitCast = false); 61239462Sdim 62239462Sdim/// \brief Tests if a value is a call or invoke to a library function that 63239462Sdim/// reallocates memory (such as realloc). 64243830Sdimbool isReallocLikeFn(const Value *V, const TargetLibraryInfo *TLI, 65243830Sdim bool LookThroughBitCast = false); 66239462Sdim 67263508Sdim/// \brief Tests if a value is a call or invoke to a library function that 68263508Sdim/// allocates memory and never returns null (such as operator new). 69263508Sdimbool isOperatorNewLikeFn(const Value *V, const TargetLibraryInfo *TLI, 70263508Sdim bool LookThroughBitCast = false); 71239462Sdim 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. 79243830Sdimconst CallInst *extractMallocCall(const Value *I, const TargetLibraryInfo *TLI); 80243830Sdimstatic inline CallInst *extractMallocCall(Value *I, 81243830Sdim const TargetLibraryInfo *TLI) { 82243830Sdim return const_cast<CallInst*>(extractMallocCall((const Value*)I, TLI)); 83239462Sdim} 84198892Srdivacky 85263508Sdim/// 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. 88263508Sdimconst CallInst *isArrayMalloc(const Value *I, const DataLayout *DL, 89243830Sdim 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. 96243830SdimPointerType *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. 103243830SdimType *getMallocAllocatedType(const CallInst *CI, const TargetLibraryInfo *TLI); 104198892Srdivacky 105263508Sdim/// 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. 110263508SdimValue *getMallocArraySize(CallInst *CI, const DataLayout *DL, 111243830Sdim const TargetLibraryInfo *TLI, 112199481Srdivacky bool LookThroughSExt = false); 113239462Sdim 114239462Sdim 115198892Srdivacky//===----------------------------------------------------------------------===// 116239462Sdim// calloc Call Utility Functions. 117239462Sdim// 118239462Sdim 119239462Sdim/// extractCallocCall - Returns the corresponding CallInst if the instruction 120239462Sdim/// is a calloc call. 121243830Sdimconst CallInst *extractCallocCall(const Value *I, const TargetLibraryInfo *TLI); 122243830Sdimstatic inline CallInst *extractCallocCall(Value *I, 123243830Sdim const TargetLibraryInfo *TLI) { 124243830Sdim return const_cast<CallInst*>(extractCallocCall((const Value*)I, TLI)); 125239462Sdim} 126239462Sdim 127239462Sdim 128239462Sdim//===----------------------------------------------------------------------===// 129198892Srdivacky// free Call Utility Functions. 130198892Srdivacky// 131198892Srdivacky 132210299Sed/// isFreeCall - Returns non-null if the value is a call to the builtin free() 133243830Sdimconst CallInst *isFreeCall(const Value *I, const TargetLibraryInfo *TLI); 134263508Sdim 135243830Sdimstatic inline CallInst *isFreeCall(Value *I, const TargetLibraryInfo *TLI) { 136243830Sdim return const_cast<CallInst*>(isFreeCall((const Value*)I, TLI)); 137218893Sdim} 138198892Srdivacky 139263508Sdim 140239462Sdim//===----------------------------------------------------------------------===// 141239462Sdim// Utility functions to compute size of objects. 142239462Sdim// 143239462Sdim 144239462Sdim/// \brief Compute the size of the object pointed by Ptr. Returns true and the 145249423Sdim/// object size in Size if successful, and false otherwise. In this context, by 146249423Sdim/// object we mean the region of memory starting at Ptr to the end of the 147249423Sdim/// underlying object pointed to by Ptr. 148239462Sdim/// If RoundToAlign is true, then Size is rounded up to the aligment of allocas, 149239462Sdim/// byval arguments, and global variables. 150263508Sdimbool getObjectSize(const Value *Ptr, uint64_t &Size, const DataLayout *DL, 151243830Sdim const TargetLibraryInfo *TLI, bool RoundToAlign = false); 152239462Sdim 153239462Sdim 154239462Sdim 155239462Sdimtypedef std::pair<APInt, APInt> SizeOffsetType; 156239462Sdim 157263508Sdim/// \brief Evaluate the size and offset of an object pointed to by a Value* 158239462Sdim/// statically. Fails if size or offset are not known at compile time. 159239462Sdimclass ObjectSizeOffsetVisitor 160239462Sdim : public InstVisitor<ObjectSizeOffsetVisitor, SizeOffsetType> { 161239462Sdim 162263508Sdim const DataLayout *DL; 163243830Sdim const TargetLibraryInfo *TLI; 164239462Sdim bool RoundToAlign; 165239462Sdim unsigned IntTyBits; 166239462Sdim APInt Zero; 167251662Sdim SmallPtrSet<Instruction *, 8> SeenInsts; 168239462Sdim 169239462Sdim APInt align(APInt Size, uint64_t Align); 170239462Sdim 171239462Sdim SizeOffsetType unknown() { 172239462Sdim return std::make_pair(APInt(), APInt()); 173239462Sdim } 174239462Sdim 175239462Sdimpublic: 176263508Sdim ObjectSizeOffsetVisitor(const DataLayout *DL, const TargetLibraryInfo *TLI, 177243830Sdim LLVMContext &Context, bool RoundToAlign = false); 178239462Sdim 179239462Sdim SizeOffsetType compute(Value *V); 180239462Sdim 181239462Sdim bool knownSize(SizeOffsetType &SizeOffset) { 182239462Sdim return SizeOffset.first.getBitWidth() > 1; 183239462Sdim } 184239462Sdim 185239462Sdim bool knownOffset(SizeOffsetType &SizeOffset) { 186239462Sdim return SizeOffset.second.getBitWidth() > 1; 187239462Sdim } 188239462Sdim 189239462Sdim bool bothKnown(SizeOffsetType &SizeOffset) { 190239462Sdim return knownSize(SizeOffset) && knownOffset(SizeOffset); 191239462Sdim } 192239462Sdim 193239462Sdim SizeOffsetType visitAllocaInst(AllocaInst &I); 194239462Sdim SizeOffsetType visitArgument(Argument &A); 195239462Sdim SizeOffsetType visitCallSite(CallSite CS); 196239462Sdim SizeOffsetType visitConstantPointerNull(ConstantPointerNull&); 197239462Sdim SizeOffsetType visitExtractElementInst(ExtractElementInst &I); 198239462Sdim SizeOffsetType visitExtractValueInst(ExtractValueInst &I); 199239462Sdim SizeOffsetType visitGEPOperator(GEPOperator &GEP); 200249423Sdim SizeOffsetType visitGlobalAlias(GlobalAlias &GA); 201239462Sdim SizeOffsetType visitGlobalVariable(GlobalVariable &GV); 202239462Sdim SizeOffsetType visitIntToPtrInst(IntToPtrInst&); 203239462Sdim SizeOffsetType visitLoadInst(LoadInst &I); 204239462Sdim SizeOffsetType visitPHINode(PHINode&); 205239462Sdim SizeOffsetType visitSelectInst(SelectInst &I); 206239462Sdim SizeOffsetType visitUndefValue(UndefValue&); 207239462Sdim SizeOffsetType visitInstruction(Instruction &I); 208239462Sdim}; 209239462Sdim 210239462Sdimtypedef std::pair<Value*, Value*> SizeOffsetEvalType; 211239462Sdim 212239462Sdim 213263508Sdim/// \brief Evaluate the size and offset of an object pointed to by a Value*. 214239462Sdim/// May create code to compute the result at run-time. 215239462Sdimclass ObjectSizeOffsetEvaluator 216239462Sdim : public InstVisitor<ObjectSizeOffsetEvaluator, SizeOffsetEvalType> { 217239462Sdim 218239462Sdim typedef IRBuilder<true, TargetFolder> BuilderTy; 219239462Sdim typedef std::pair<WeakVH, WeakVH> WeakEvalType; 220239462Sdim typedef DenseMap<const Value*, WeakEvalType> CacheMapTy; 221239462Sdim typedef SmallPtrSet<const Value*, 8> PtrSetTy; 222239462Sdim 223263508Sdim const DataLayout *DL; 224243830Sdim const TargetLibraryInfo *TLI; 225239462Sdim LLVMContext &Context; 226239462Sdim BuilderTy Builder; 227239462Sdim IntegerType *IntTy; 228239462Sdim Value *Zero; 229239462Sdim CacheMapTy CacheMap; 230239462Sdim PtrSetTy SeenVals; 231263508Sdim bool RoundToAlign; 232239462Sdim 233239462Sdim SizeOffsetEvalType unknown() { 234239462Sdim return std::make_pair((Value*)0, (Value*)0); 235239462Sdim } 236239462Sdim SizeOffsetEvalType compute_(Value *V); 237239462Sdim 238239462Sdimpublic: 239263508Sdim ObjectSizeOffsetEvaluator(const DataLayout *DL, const TargetLibraryInfo *TLI, 240263508Sdim LLVMContext &Context, bool RoundToAlign = false); 241239462Sdim SizeOffsetEvalType compute(Value *V); 242239462Sdim 243239462Sdim bool knownSize(SizeOffsetEvalType SizeOffset) { 244239462Sdim return SizeOffset.first; 245239462Sdim } 246239462Sdim 247239462Sdim bool knownOffset(SizeOffsetEvalType SizeOffset) { 248239462Sdim return SizeOffset.second; 249239462Sdim } 250239462Sdim 251239462Sdim bool anyKnown(SizeOffsetEvalType SizeOffset) { 252239462Sdim return knownSize(SizeOffset) || knownOffset(SizeOffset); 253239462Sdim } 254239462Sdim 255239462Sdim bool bothKnown(SizeOffsetEvalType SizeOffset) { 256239462Sdim return knownSize(SizeOffset) && knownOffset(SizeOffset); 257239462Sdim } 258239462Sdim 259239462Sdim SizeOffsetEvalType visitAllocaInst(AllocaInst &I); 260239462Sdim SizeOffsetEvalType visitCallSite(CallSite CS); 261239462Sdim SizeOffsetEvalType visitExtractElementInst(ExtractElementInst &I); 262239462Sdim SizeOffsetEvalType visitExtractValueInst(ExtractValueInst &I); 263239462Sdim SizeOffsetEvalType visitGEPOperator(GEPOperator &GEP); 264239462Sdim SizeOffsetEvalType visitIntToPtrInst(IntToPtrInst&); 265239462Sdim SizeOffsetEvalType visitLoadInst(LoadInst &I); 266239462Sdim SizeOffsetEvalType visitPHINode(PHINode &PHI); 267239462Sdim SizeOffsetEvalType visitSelectInst(SelectInst &I); 268239462Sdim SizeOffsetEvalType visitInstruction(Instruction &I); 269239462Sdim}; 270239462Sdim 271198892Srdivacky} // End llvm namespace 272198892Srdivacky 273198892Srdivacky#endif 274