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 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 67239462Sdim 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. 75243830Sdimconst CallInst *extractMallocCall(const Value *I, const TargetLibraryInfo *TLI); 76243830Sdimstatic inline CallInst *extractMallocCall(Value *I, 77243830Sdim const TargetLibraryInfo *TLI) { 78243830Sdim return const_cast<CallInst*>(extractMallocCall((const Value*)I, TLI)); 79239462Sdim} 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. 84243830Sdimconst CallInst *isArrayMalloc(const Value *I, const DataLayout *TD, 85243830Sdim 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. 92243830SdimPointerType *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. 99243830SdimType *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. 106243830SdimValue *getMallocArraySize(CallInst *CI, const DataLayout *TD, 107243830Sdim const TargetLibraryInfo *TLI, 108199481Srdivacky bool LookThroughSExt = false); 109239462Sdim 110239462Sdim 111198892Srdivacky//===----------------------------------------------------------------------===// 112239462Sdim// calloc Call Utility Functions. 113239462Sdim// 114239462Sdim 115239462Sdim/// extractCallocCall - Returns the corresponding CallInst if the instruction 116239462Sdim/// is a calloc call. 117243830Sdimconst CallInst *extractCallocCall(const Value *I, const TargetLibraryInfo *TLI); 118243830Sdimstatic inline CallInst *extractCallocCall(Value *I, 119243830Sdim const TargetLibraryInfo *TLI) { 120243830Sdim return const_cast<CallInst*>(extractCallocCall((const Value*)I, TLI)); 121239462Sdim} 122239462Sdim 123239462Sdim 124239462Sdim//===----------------------------------------------------------------------===// 125198892Srdivacky// free Call Utility Functions. 126198892Srdivacky// 127198892Srdivacky 128210299Sed/// isFreeCall - Returns non-null if the value is a call to the builtin free() 129243830Sdimconst CallInst *isFreeCall(const Value *I, const TargetLibraryInfo *TLI); 130218893Sdim 131243830Sdimstatic inline CallInst *isFreeCall(Value *I, const TargetLibraryInfo *TLI) { 132243830Sdim return const_cast<CallInst*>(isFreeCall((const Value*)I, TLI)); 133218893Sdim} 134198892Srdivacky 135239462Sdim 136239462Sdim//===----------------------------------------------------------------------===// 137239462Sdim// Utility functions to compute size of objects. 138239462Sdim// 139239462Sdim 140239462Sdim/// \brief Compute the size of the object pointed by Ptr. Returns true and the 141249423Sdim/// object size in Size if successful, and false otherwise. In this context, by 142249423Sdim/// object we mean the region of memory starting at Ptr to the end of the 143249423Sdim/// underlying object pointed to by Ptr. 144239462Sdim/// If RoundToAlign is true, then Size is rounded up to the aligment of allocas, 145239462Sdim/// byval arguments, and global variables. 146243830Sdimbool getObjectSize(const Value *Ptr, uint64_t &Size, const DataLayout *TD, 147243830Sdim const TargetLibraryInfo *TLI, bool RoundToAlign = false); 148239462Sdim 149239462Sdim 150239462Sdim 151239462Sdimtypedef std::pair<APInt, APInt> SizeOffsetType; 152239462Sdim 153239462Sdim/// \brief Evaluate the size and offset of an object ponted by a Value* 154239462Sdim/// statically. Fails if size or offset are not known at compile time. 155239462Sdimclass ObjectSizeOffsetVisitor 156239462Sdim : public InstVisitor<ObjectSizeOffsetVisitor, SizeOffsetType> { 157239462Sdim 158243830Sdim const DataLayout *TD; 159243830Sdim const TargetLibraryInfo *TLI; 160239462Sdim bool RoundToAlign; 161239462Sdim unsigned IntTyBits; 162239462Sdim APInt Zero; 163251662Sdim SmallPtrSet<Instruction *, 8> SeenInsts; 164239462Sdim 165239462Sdim APInt align(APInt Size, uint64_t Align); 166239462Sdim 167239462Sdim SizeOffsetType unknown() { 168239462Sdim return std::make_pair(APInt(), APInt()); 169239462Sdim } 170239462Sdim 171239462Sdimpublic: 172243830Sdim ObjectSizeOffsetVisitor(const DataLayout *TD, const TargetLibraryInfo *TLI, 173243830Sdim LLVMContext &Context, bool RoundToAlign = false); 174239462Sdim 175239462Sdim SizeOffsetType compute(Value *V); 176239462Sdim 177239462Sdim bool knownSize(SizeOffsetType &SizeOffset) { 178239462Sdim return SizeOffset.first.getBitWidth() > 1; 179239462Sdim } 180239462Sdim 181239462Sdim bool knownOffset(SizeOffsetType &SizeOffset) { 182239462Sdim return SizeOffset.second.getBitWidth() > 1; 183239462Sdim } 184239462Sdim 185239462Sdim bool bothKnown(SizeOffsetType &SizeOffset) { 186239462Sdim return knownSize(SizeOffset) && knownOffset(SizeOffset); 187239462Sdim } 188239462Sdim 189239462Sdim SizeOffsetType visitAllocaInst(AllocaInst &I); 190239462Sdim SizeOffsetType visitArgument(Argument &A); 191239462Sdim SizeOffsetType visitCallSite(CallSite CS); 192239462Sdim SizeOffsetType visitConstantPointerNull(ConstantPointerNull&); 193239462Sdim SizeOffsetType visitExtractElementInst(ExtractElementInst &I); 194239462Sdim SizeOffsetType visitExtractValueInst(ExtractValueInst &I); 195239462Sdim SizeOffsetType visitGEPOperator(GEPOperator &GEP); 196249423Sdim SizeOffsetType visitGlobalAlias(GlobalAlias &GA); 197239462Sdim SizeOffsetType visitGlobalVariable(GlobalVariable &GV); 198239462Sdim SizeOffsetType visitIntToPtrInst(IntToPtrInst&); 199239462Sdim SizeOffsetType visitLoadInst(LoadInst &I); 200239462Sdim SizeOffsetType visitPHINode(PHINode&); 201239462Sdim SizeOffsetType visitSelectInst(SelectInst &I); 202239462Sdim SizeOffsetType visitUndefValue(UndefValue&); 203239462Sdim SizeOffsetType visitInstruction(Instruction &I); 204239462Sdim}; 205239462Sdim 206239462Sdimtypedef std::pair<Value*, Value*> SizeOffsetEvalType; 207239462Sdim 208239462Sdim 209239462Sdim/// \brief Evaluate the size and offset of an object ponted by a Value*. 210239462Sdim/// May create code to compute the result at run-time. 211239462Sdimclass ObjectSizeOffsetEvaluator 212239462Sdim : public InstVisitor<ObjectSizeOffsetEvaluator, SizeOffsetEvalType> { 213239462Sdim 214239462Sdim typedef IRBuilder<true, TargetFolder> BuilderTy; 215239462Sdim typedef std::pair<WeakVH, WeakVH> WeakEvalType; 216239462Sdim typedef DenseMap<const Value*, WeakEvalType> CacheMapTy; 217239462Sdim typedef SmallPtrSet<const Value*, 8> PtrSetTy; 218239462Sdim 219243830Sdim const DataLayout *TD; 220243830Sdim const TargetLibraryInfo *TLI; 221239462Sdim LLVMContext &Context; 222239462Sdim BuilderTy Builder; 223239462Sdim IntegerType *IntTy; 224239462Sdim Value *Zero; 225239462Sdim CacheMapTy CacheMap; 226239462Sdim PtrSetTy SeenVals; 227239462Sdim 228239462Sdim SizeOffsetEvalType unknown() { 229239462Sdim return std::make_pair((Value*)0, (Value*)0); 230239462Sdim } 231239462Sdim SizeOffsetEvalType compute_(Value *V); 232239462Sdim 233239462Sdimpublic: 234243830Sdim ObjectSizeOffsetEvaluator(const DataLayout *TD, const TargetLibraryInfo *TLI, 235243830Sdim LLVMContext &Context); 236239462Sdim SizeOffsetEvalType compute(Value *V); 237239462Sdim 238239462Sdim bool knownSize(SizeOffsetEvalType SizeOffset) { 239239462Sdim return SizeOffset.first; 240239462Sdim } 241239462Sdim 242239462Sdim bool knownOffset(SizeOffsetEvalType SizeOffset) { 243239462Sdim return SizeOffset.second; 244239462Sdim } 245239462Sdim 246239462Sdim bool anyKnown(SizeOffsetEvalType SizeOffset) { 247239462Sdim return knownSize(SizeOffset) || knownOffset(SizeOffset); 248239462Sdim } 249239462Sdim 250239462Sdim bool bothKnown(SizeOffsetEvalType SizeOffset) { 251239462Sdim return knownSize(SizeOffset) && knownOffset(SizeOffset); 252239462Sdim } 253239462Sdim 254239462Sdim SizeOffsetEvalType visitAllocaInst(AllocaInst &I); 255239462Sdim SizeOffsetEvalType visitCallSite(CallSite CS); 256239462Sdim SizeOffsetEvalType visitExtractElementInst(ExtractElementInst &I); 257239462Sdim SizeOffsetEvalType visitExtractValueInst(ExtractValueInst &I); 258239462Sdim SizeOffsetEvalType visitGEPOperator(GEPOperator &GEP); 259239462Sdim SizeOffsetEvalType visitIntToPtrInst(IntToPtrInst&); 260239462Sdim SizeOffsetEvalType visitLoadInst(LoadInst &I); 261239462Sdim SizeOffsetEvalType visitPHINode(PHINode &PHI); 262239462Sdim SizeOffsetEvalType visitSelectInst(SelectInst &I); 263239462Sdim SizeOffsetEvalType visitInstruction(Instruction &I); 264239462Sdim}; 265239462Sdim 266198892Srdivacky} // End llvm namespace 267198892Srdivacky 268198892Srdivacky#endif 269