1 //===- llvm/Analysis/MemoryBuiltins.h- Calls to memory builtins -*- C++ -*-===// 2 // 3 // The LLVM Compiler Infrastructure 4 // 5 // This file is distributed under the University of Illinois Open Source 6 // License. See LICENSE.TXT for details. 7 // 8 //===----------------------------------------------------------------------===// 9 // 10 // This family of functions identifies calls to builtin functions that allocate 11 // or free memory. 12 // 13 //===----------------------------------------------------------------------===// 14 15 #ifndef LLVM_ANALYSIS_MEMORYBUILTINS_H 16 #define LLVM_ANALYSIS_MEMORYBUILTINS_H 17 18 #include "llvm/ADT/DenseMap.h" 19 #include "llvm/ADT/SmallPtrSet.h" 20 #include "llvm/Analysis/TargetFolder.h" 21 #include "llvm/IR/IRBuilder.h" 22 #include "llvm/IR/InstVisitor.h" 23 #include "llvm/IR/Operator.h" 24 #include "llvm/IR/ValueHandle.h" 25 #include "llvm/Support/DataTypes.h" 26 27 namespace llvm { 28 class CallInst; 29 class PointerType; 30 class DataLayout; 31 class TargetLibraryInfo; 32 class Type; 33 class Value; 34 35 36 /// \brief Tests if a value is a call or invoke to a library function that 37 /// allocates or reallocates memory (either malloc, calloc, realloc, or strdup 38 /// like). 39 bool isAllocationFn(const Value *V, const TargetLibraryInfo *TLI, 40 bool LookThroughBitCast = false); 41 42 /// \brief Tests if a value is a call or invoke to a function that returns a 43 /// NoAlias pointer (including malloc/calloc/realloc/strdup-like functions). 44 bool isNoAliasFn(const Value *V, const TargetLibraryInfo *TLI, 45 bool LookThroughBitCast = false); 46 47 /// \brief Tests if a value is a call or invoke to a library function that 48 /// allocates uninitialized memory (such as malloc). 49 bool isMallocLikeFn(const Value *V, const TargetLibraryInfo *TLI, 50 bool LookThroughBitCast = false); 51 52 /// \brief Tests if a value is a call or invoke to a library function that 53 /// allocates zero-filled memory (such as calloc). 54 bool isCallocLikeFn(const Value *V, const TargetLibraryInfo *TLI, 55 bool LookThroughBitCast = false); 56 57 /// \brief Tests if a value is a call or invoke to a library function that 58 /// allocates memory (either malloc, calloc, or strdup like). 59 bool isAllocLikeFn(const Value *V, const TargetLibraryInfo *TLI, 60 bool LookThroughBitCast = false); 61 62 /// \brief Tests if a value is a call or invoke to a library function that 63 /// reallocates memory (such as realloc). 64 bool isReallocLikeFn(const Value *V, const TargetLibraryInfo *TLI, 65 bool LookThroughBitCast = false); 66 67 /// \brief Tests if a value is a call or invoke to a library function that 68 /// allocates memory and never returns null (such as operator new). 69 bool isOperatorNewLikeFn(const Value *V, const TargetLibraryInfo *TLI, 70 bool LookThroughBitCast = false); 71 72 //===----------------------------------------------------------------------===// 73 // malloc Call Utility Functions. 74 // 75 76 /// extractMallocCall - Returns the corresponding CallInst if the instruction 77 /// is a malloc call. Since CallInst::CreateMalloc() only creates calls, we 78 /// ignore InvokeInst here. 79 const CallInst *extractMallocCall(const Value *I, const TargetLibraryInfo *TLI); 80 static inline CallInst *extractMallocCall(Value *I, 81 const TargetLibraryInfo *TLI) { 82 return const_cast<CallInst*>(extractMallocCall((const Value*)I, TLI)); 83 } 84 85 /// getMallocType - Returns the PointerType resulting from the malloc call. 86 /// The PointerType depends on the number of bitcast uses of the malloc call: 87 /// 0: PointerType is the malloc calls' return type. 88 /// 1: PointerType is the bitcast's result type. 89 /// >1: Unique PointerType cannot be determined, return NULL. 90 PointerType *getMallocType(const CallInst *CI, const TargetLibraryInfo *TLI); 91 92 /// getMallocAllocatedType - Returns the Type allocated by malloc call. 93 /// The Type depends on the number of bitcast uses of the malloc call: 94 /// 0: PointerType is the malloc calls' return type. 95 /// 1: PointerType is the bitcast's result type. 96 /// >1: Unique PointerType cannot be determined, return NULL. 97 Type *getMallocAllocatedType(const CallInst *CI, const TargetLibraryInfo *TLI); 98 99 /// getMallocArraySize - Returns the array size of a malloc call. If the 100 /// argument passed to malloc is a multiple of the size of the malloced type, 101 /// then return that multiple. For non-array mallocs, the multiple is 102 /// constant 1. Otherwise, return NULL for mallocs whose array size cannot be 103 /// determined. 104 Value *getMallocArraySize(CallInst *CI, const DataLayout &DL, 105 const TargetLibraryInfo *TLI, 106 bool LookThroughSExt = false); 107 108 //===----------------------------------------------------------------------===// 109 // calloc Call Utility Functions. 110 // 111 112 /// extractCallocCall - Returns the corresponding CallInst if the instruction 113 /// is a calloc call. 114 const CallInst *extractCallocCall(const Value *I, const TargetLibraryInfo *TLI); 115 static inline CallInst *extractCallocCall(Value *I, 116 const TargetLibraryInfo *TLI) { 117 return const_cast<CallInst*>(extractCallocCall((const Value*)I, TLI)); 118 } 119 120 121 //===----------------------------------------------------------------------===// 122 // free Call Utility Functions. 123 // 124 125 /// isFreeCall - Returns non-null if the value is a call to the builtin free() 126 const CallInst *isFreeCall(const Value *I, const TargetLibraryInfo *TLI); 127 128 static inline CallInst *isFreeCall(Value *I, const TargetLibraryInfo *TLI) { 129 return const_cast<CallInst*>(isFreeCall((const Value*)I, TLI)); 130 } 131 132 133 //===----------------------------------------------------------------------===// 134 // Utility functions to compute size of objects. 135 // 136 137 /// \brief Compute the size of the object pointed by Ptr. Returns true and the 138 /// object size in Size if successful, and false otherwise. In this context, by 139 /// object we mean the region of memory starting at Ptr to the end of the 140 /// underlying object pointed to by Ptr. 141 /// If RoundToAlign is true, then Size is rounded up to the aligment of allocas, 142 /// byval arguments, and global variables. 143 bool getObjectSize(const Value *Ptr, uint64_t &Size, const DataLayout &DL, 144 const TargetLibraryInfo *TLI, bool RoundToAlign = false); 145 146 typedef std::pair<APInt, APInt> SizeOffsetType; 147 148 /// \brief Evaluate the size and offset of an object pointed to by a Value* 149 /// statically. Fails if size or offset are not known at compile time. 150 class ObjectSizeOffsetVisitor 151 : public InstVisitor<ObjectSizeOffsetVisitor, SizeOffsetType> { 152 153 const DataLayout &DL; 154 const TargetLibraryInfo *TLI; 155 bool RoundToAlign; 156 unsigned IntTyBits; 157 APInt Zero; 158 SmallPtrSet<Instruction *, 8> SeenInsts; 159 160 APInt align(APInt Size, uint64_t Align); 161 162 SizeOffsetType unknown() { 163 return std::make_pair(APInt(), APInt()); 164 } 165 166 public: 167 ObjectSizeOffsetVisitor(const DataLayout &DL, const TargetLibraryInfo *TLI, 168 LLVMContext &Context, bool RoundToAlign = false); 169 170 SizeOffsetType compute(Value *V); 171 172 bool knownSize(SizeOffsetType &SizeOffset) { 173 return SizeOffset.first.getBitWidth() > 1; 174 } 175 176 bool knownOffset(SizeOffsetType &SizeOffset) { 177 return SizeOffset.second.getBitWidth() > 1; 178 } 179 180 bool bothKnown(SizeOffsetType &SizeOffset) { 181 return knownSize(SizeOffset) && knownOffset(SizeOffset); 182 } 183 184 // These are "private", except they can't actually be made private. Only 185 // compute() should be used by external users. 186 SizeOffsetType visitAllocaInst(AllocaInst &I); 187 SizeOffsetType visitArgument(Argument &A); 188 SizeOffsetType visitCallSite(CallSite CS); 189 SizeOffsetType visitConstantPointerNull(ConstantPointerNull&); 190 SizeOffsetType visitExtractElementInst(ExtractElementInst &I); 191 SizeOffsetType visitExtractValueInst(ExtractValueInst &I); 192 SizeOffsetType visitGEPOperator(GEPOperator &GEP); 193 SizeOffsetType visitGlobalAlias(GlobalAlias &GA); 194 SizeOffsetType visitGlobalVariable(GlobalVariable &GV); 195 SizeOffsetType visitIntToPtrInst(IntToPtrInst&); 196 SizeOffsetType visitLoadInst(LoadInst &I); 197 SizeOffsetType visitPHINode(PHINode&); 198 SizeOffsetType visitSelectInst(SelectInst &I); 199 SizeOffsetType visitUndefValue(UndefValue&); 200 SizeOffsetType visitInstruction(Instruction &I); 201 }; 202 203 typedef std::pair<Value*, Value*> SizeOffsetEvalType; 204 205 206 /// \brief Evaluate the size and offset of an object pointed to by a Value*. 207 /// May create code to compute the result at run-time. 208 class ObjectSizeOffsetEvaluator 209 : public InstVisitor<ObjectSizeOffsetEvaluator, SizeOffsetEvalType> { 210 211 typedef IRBuilder<true, TargetFolder> BuilderTy; 212 typedef std::pair<WeakVH, WeakVH> WeakEvalType; 213 typedef DenseMap<const Value*, WeakEvalType> CacheMapTy; 214 typedef SmallPtrSet<const Value*, 8> PtrSetTy; 215 216 const DataLayout &DL; 217 const TargetLibraryInfo *TLI; 218 LLVMContext &Context; 219 BuilderTy Builder; 220 IntegerType *IntTy; 221 Value *Zero; 222 CacheMapTy CacheMap; 223 PtrSetTy SeenVals; 224 bool RoundToAlign; 225 226 SizeOffsetEvalType unknown() { 227 return std::make_pair(nullptr, nullptr); 228 } 229 SizeOffsetEvalType compute_(Value *V); 230 231 public: 232 ObjectSizeOffsetEvaluator(const DataLayout &DL, const TargetLibraryInfo *TLI, 233 LLVMContext &Context, bool RoundToAlign = false); 234 SizeOffsetEvalType compute(Value *V); 235 236 bool knownSize(SizeOffsetEvalType SizeOffset) { 237 return SizeOffset.first; 238 } 239 240 bool knownOffset(SizeOffsetEvalType SizeOffset) { 241 return SizeOffset.second; 242 } 243 244 bool anyKnown(SizeOffsetEvalType SizeOffset) { 245 return knownSize(SizeOffset) || knownOffset(SizeOffset); 246 } 247 248 bool bothKnown(SizeOffsetEvalType SizeOffset) { 249 return knownSize(SizeOffset) && knownOffset(SizeOffset); 250 } 251 252 // The individual instruction visitors should be treated as private. 253 SizeOffsetEvalType visitAllocaInst(AllocaInst &I); 254 SizeOffsetEvalType visitCallSite(CallSite CS); 255 SizeOffsetEvalType visitExtractElementInst(ExtractElementInst &I); 256 SizeOffsetEvalType visitExtractValueInst(ExtractValueInst &I); 257 SizeOffsetEvalType visitGEPOperator(GEPOperator &GEP); 258 SizeOffsetEvalType visitIntToPtrInst(IntToPtrInst&); 259 SizeOffsetEvalType visitLoadInst(LoadInst &I); 260 SizeOffsetEvalType visitPHINode(PHINode &PHI); 261 SizeOffsetEvalType visitSelectInst(SelectInst &I); 262 SizeOffsetEvalType visitInstruction(Instruction &I); 263 }; 264 265 } // End llvm namespace 266 267 #endif 268