1 //==- llvm/Analysis/MemoryBuiltins.h - Calls to memory builtins --*- C++ -*-==// 2 // 3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4 // See https://llvm.org/LICENSE.txt for license information. 5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 6 // 7 //===----------------------------------------------------------------------===// 8 // 9 // This family of functions identifies calls to builtin functions that allocate 10 // or free memory. 11 // 12 //===----------------------------------------------------------------------===// 13 14 #ifndef LLVM_ANALYSIS_MEMORYBUILTINS_H 15 #define LLVM_ANALYSIS_MEMORYBUILTINS_H 16 17 #include "llvm/ADT/APInt.h" 18 #include "llvm/ADT/DenseMap.h" 19 #include "llvm/ADT/SmallPtrSet.h" 20 #include "llvm/Analysis/TargetFolder.h" 21 #include "llvm/Analysis/TargetLibraryInfo.h" 22 #include "llvm/IR/CallSite.h" 23 #include "llvm/IR/IRBuilder.h" 24 #include "llvm/IR/InstVisitor.h" 25 #include "llvm/IR/ValueHandle.h" 26 #include <cstdint> 27 #include <utility> 28 29 namespace llvm { 30 31 class AllocaInst; 32 class Argument; 33 class CallInst; 34 class ConstantInt; 35 class ConstantPointerNull; 36 class DataLayout; 37 class ExtractElementInst; 38 class ExtractValueInst; 39 class GEPOperator; 40 class GlobalAlias; 41 class GlobalVariable; 42 class Instruction; 43 class IntegerType; 44 class IntrinsicInst; 45 class IntToPtrInst; 46 class LLVMContext; 47 class LoadInst; 48 class PHINode; 49 class PointerType; 50 class SelectInst; 51 class TargetLibraryInfo; 52 class Type; 53 class UndefValue; 54 class Value; 55 56 /// Tests if a value is a call or invoke to a library function that 57 /// allocates or reallocates memory (either malloc, calloc, realloc, or strdup 58 /// like). 59 bool isAllocationFn(const Value *V, const TargetLibraryInfo *TLI, 60 bool LookThroughBitCast = false); 61 bool isAllocationFn(const Value *V, 62 function_ref<const TargetLibraryInfo &(Function &)> GetTLI, 63 bool LookThroughBitCast = false); 64 65 /// Tests if a value is a call or invoke to a function that returns a 66 /// NoAlias pointer (including malloc/calloc/realloc/strdup-like functions). 67 bool isNoAliasFn(const Value *V, const TargetLibraryInfo *TLI, 68 bool LookThroughBitCast = false); 69 70 /// Tests if a value is a call or invoke to a library function that 71 /// allocates uninitialized memory (such as malloc). 72 bool isMallocLikeFn(const Value *V, const TargetLibraryInfo *TLI, 73 bool LookThroughBitCast = false); 74 bool isMallocLikeFn(const Value *V, 75 function_ref<const TargetLibraryInfo &(Function &)> GetTLI, 76 bool LookThroughBitCast = false); 77 78 /// Tests if a value is a call or invoke to a library function that 79 /// allocates zero-filled memory (such as calloc). 80 bool isCallocLikeFn(const Value *V, const TargetLibraryInfo *TLI, 81 bool LookThroughBitCast = false); 82 83 /// Tests if a value is a call or invoke to a library function that 84 /// allocates memory similar to malloc or calloc. 85 bool isMallocOrCallocLikeFn(const Value *V, const TargetLibraryInfo *TLI, 86 bool LookThroughBitCast = false); 87 88 /// Tests if a value is a call or invoke to a library function that 89 /// allocates memory (either malloc, calloc, or strdup like). 90 bool isAllocLikeFn(const Value *V, const TargetLibraryInfo *TLI, 91 bool LookThroughBitCast = false); 92 93 /// Tests if a value is a call or invoke to a library function that 94 /// reallocates memory (e.g., realloc). 95 bool isReallocLikeFn(const Value *V, const TargetLibraryInfo *TLI, 96 bool LookThroughBitCast = false); 97 98 /// Tests if a function is a call or invoke to a library function that 99 /// reallocates memory (e.g., realloc). 100 bool isReallocLikeFn(const Function *F, const TargetLibraryInfo *TLI); 101 102 /// Tests if a value is a call or invoke to a library function that 103 /// allocates memory and throws if an allocation failed (e.g., new). 104 bool isOpNewLikeFn(const Value *V, const TargetLibraryInfo *TLI, 105 bool LookThroughBitCast = false); 106 107 /// Tests if a value is a call or invoke to a library function that 108 /// allocates memory (strdup, strndup). 109 bool isStrdupLikeFn(const Value *V, const TargetLibraryInfo *TLI, 110 bool LookThroughBitCast = false); 111 112 //===----------------------------------------------------------------------===// 113 // malloc Call Utility Functions. 114 // 115 116 /// extractMallocCall - Returns the corresponding CallInst if the instruction 117 /// is a malloc call. Since CallInst::CreateMalloc() only creates calls, we 118 /// ignore InvokeInst here. 119 const CallInst * 120 extractMallocCall(const Value *I, 121 function_ref<const TargetLibraryInfo &(Function &)> GetTLI); 122 inline CallInst * 123 extractMallocCall(Value *I, 124 function_ref<const TargetLibraryInfo &(Function &)> GetTLI) { 125 return const_cast<CallInst *>(extractMallocCall((const Value *)I, GetTLI)); 126 } 127 128 /// getMallocType - Returns the PointerType resulting from the malloc call. 129 /// The PointerType depends on the number of bitcast uses of the malloc call: 130 /// 0: PointerType is the malloc calls' return type. 131 /// 1: PointerType is the bitcast's result type. 132 /// >1: Unique PointerType cannot be determined, return NULL. 133 PointerType *getMallocType(const CallInst *CI, const TargetLibraryInfo *TLI); 134 135 /// getMallocAllocatedType - Returns the Type allocated by malloc call. 136 /// The Type depends on the number of bitcast uses of the malloc call: 137 /// 0: PointerType is the malloc calls' return type. 138 /// 1: PointerType is the bitcast's result type. 139 /// >1: Unique PointerType cannot be determined, return NULL. 140 Type *getMallocAllocatedType(const CallInst *CI, const TargetLibraryInfo *TLI); 141 142 /// getMallocArraySize - Returns the array size of a malloc call. If the 143 /// argument passed to malloc is a multiple of the size of the malloced type, 144 /// then return that multiple. For non-array mallocs, the multiple is 145 /// constant 1. Otherwise, return NULL for mallocs whose array size cannot be 146 /// determined. 147 Value *getMallocArraySize(CallInst *CI, const DataLayout &DL, 148 const TargetLibraryInfo *TLI, 149 bool LookThroughSExt = false); 150 151 //===----------------------------------------------------------------------===// 152 // calloc Call Utility Functions. 153 // 154 155 /// extractCallocCall - Returns the corresponding CallInst if the instruction 156 /// is a calloc call. 157 const CallInst *extractCallocCall(const Value *I, const TargetLibraryInfo *TLI); 158 inline CallInst *extractCallocCall(Value *I, const TargetLibraryInfo *TLI) { 159 return const_cast<CallInst*>(extractCallocCall((const Value*)I, TLI)); 160 } 161 162 163 //===----------------------------------------------------------------------===// 164 // free Call Utility Functions. 165 // 166 167 /// isLibFreeFunction - Returns true if the function is a builtin free() 168 bool isLibFreeFunction(const Function *F, const LibFunc TLIFn); 169 170 /// isFreeCall - Returns non-null if the value is a call to the builtin free() 171 const CallInst *isFreeCall(const Value *I, const TargetLibraryInfo *TLI); 172 173 inline CallInst *isFreeCall(Value *I, const TargetLibraryInfo *TLI) { 174 return const_cast<CallInst*>(isFreeCall((const Value*)I, TLI)); 175 } 176 177 //===----------------------------------------------------------------------===// 178 // Utility functions to compute size of objects. 179 // 180 181 /// Various options to control the behavior of getObjectSize. 182 struct ObjectSizeOpts { 183 /// Controls how we handle conditional statements with unknown conditions. 184 enum class Mode : uint8_t { 185 /// Fail to evaluate an unknown condition. 186 Exact, 187 /// Evaluate all branches of an unknown condition. If all evaluations 188 /// succeed, pick the minimum size. 189 Min, 190 /// Same as Min, except we pick the maximum size of all of the branches. 191 Max 192 }; 193 194 /// How we want to evaluate this object's size. 195 Mode EvalMode = Mode::Exact; 196 /// Whether to round the result up to the alignment of allocas, byval 197 /// arguments, and global variables. 198 bool RoundToAlign = false; 199 /// If this is true, null pointers in address space 0 will be treated as 200 /// though they can't be evaluated. Otherwise, null is always considered to 201 /// point to a 0 byte region of memory. 202 bool NullIsUnknownSize = false; 203 }; 204 205 /// Compute the size of the object pointed by Ptr. Returns true and the 206 /// object size in Size if successful, and false otherwise. In this context, by 207 /// object we mean the region of memory starting at Ptr to the end of the 208 /// underlying object pointed to by Ptr. 209 bool getObjectSize(const Value *Ptr, uint64_t &Size, const DataLayout &DL, 210 const TargetLibraryInfo *TLI, ObjectSizeOpts Opts = {}); 211 212 /// Try to turn a call to \@llvm.objectsize into an integer value of the given 213 /// Type. Returns null on failure. If MustSucceed is true, this function will 214 /// not return null, and may return conservative values governed by the second 215 /// argument of the call to objectsize. 216 Value *lowerObjectSizeCall(IntrinsicInst *ObjectSize, const DataLayout &DL, 217 const TargetLibraryInfo *TLI, bool MustSucceed); 218 219 220 221 using SizeOffsetType = std::pair<APInt, APInt>; 222 223 /// Evaluate the size and offset of an object pointed to by a Value* 224 /// statically. Fails if size or offset are not known at compile time. 225 class ObjectSizeOffsetVisitor 226 : public InstVisitor<ObjectSizeOffsetVisitor, SizeOffsetType> { 227 const DataLayout &DL; 228 const TargetLibraryInfo *TLI; 229 ObjectSizeOpts Options; 230 unsigned IntTyBits; 231 APInt Zero; 232 SmallPtrSet<Instruction *, 8> SeenInsts; 233 234 APInt align(APInt Size, uint64_t Align); 235 236 SizeOffsetType unknown() { 237 return std::make_pair(APInt(), APInt()); 238 } 239 240 public: 241 ObjectSizeOffsetVisitor(const DataLayout &DL, const TargetLibraryInfo *TLI, 242 LLVMContext &Context, ObjectSizeOpts Options = {}); 243 244 SizeOffsetType compute(Value *V); 245 246 static bool knownSize(const SizeOffsetType &SizeOffset) { 247 return SizeOffset.first.getBitWidth() > 1; 248 } 249 250 static bool knownOffset(const SizeOffsetType &SizeOffset) { 251 return SizeOffset.second.getBitWidth() > 1; 252 } 253 254 static bool bothKnown(const SizeOffsetType &SizeOffset) { 255 return knownSize(SizeOffset) && knownOffset(SizeOffset); 256 } 257 258 // These are "private", except they can't actually be made private. Only 259 // compute() should be used by external users. 260 SizeOffsetType visitAllocaInst(AllocaInst &I); 261 SizeOffsetType visitArgument(Argument &A); 262 SizeOffsetType visitCallSite(CallSite CS); 263 SizeOffsetType visitConstantPointerNull(ConstantPointerNull&); 264 SizeOffsetType visitExtractElementInst(ExtractElementInst &I); 265 SizeOffsetType visitExtractValueInst(ExtractValueInst &I); 266 SizeOffsetType visitGEPOperator(GEPOperator &GEP); 267 SizeOffsetType visitGlobalAlias(GlobalAlias &GA); 268 SizeOffsetType visitGlobalVariable(GlobalVariable &GV); 269 SizeOffsetType visitIntToPtrInst(IntToPtrInst&); 270 SizeOffsetType visitLoadInst(LoadInst &I); 271 SizeOffsetType visitPHINode(PHINode&); 272 SizeOffsetType visitSelectInst(SelectInst &I); 273 SizeOffsetType visitUndefValue(UndefValue&); 274 SizeOffsetType visitInstruction(Instruction &I); 275 276 private: 277 bool CheckedZextOrTrunc(APInt &I); 278 }; 279 280 using SizeOffsetEvalType = std::pair<Value *, Value *>; 281 282 /// Evaluate the size and offset of an object pointed to by a Value*. 283 /// May create code to compute the result at run-time. 284 class ObjectSizeOffsetEvaluator 285 : public InstVisitor<ObjectSizeOffsetEvaluator, SizeOffsetEvalType> { 286 using BuilderTy = IRBuilder<TargetFolder, IRBuilderCallbackInserter>; 287 using WeakEvalType = std::pair<WeakTrackingVH, WeakTrackingVH>; 288 using CacheMapTy = DenseMap<const Value *, WeakEvalType>; 289 using PtrSetTy = SmallPtrSet<const Value *, 8>; 290 291 const DataLayout &DL; 292 const TargetLibraryInfo *TLI; 293 LLVMContext &Context; 294 BuilderTy Builder; 295 IntegerType *IntTy; 296 Value *Zero; 297 CacheMapTy CacheMap; 298 PtrSetTy SeenVals; 299 ObjectSizeOpts EvalOpts; 300 SmallPtrSet<Instruction *, 8> InsertedInstructions; 301 302 SizeOffsetEvalType compute_(Value *V); 303 304 public: 305 static SizeOffsetEvalType unknown() { 306 return std::make_pair(nullptr, nullptr); 307 } 308 309 ObjectSizeOffsetEvaluator(const DataLayout &DL, const TargetLibraryInfo *TLI, 310 LLVMContext &Context, ObjectSizeOpts EvalOpts = {}); 311 312 SizeOffsetEvalType compute(Value *V); 313 314 bool knownSize(SizeOffsetEvalType SizeOffset) { 315 return SizeOffset.first; 316 } 317 318 bool knownOffset(SizeOffsetEvalType SizeOffset) { 319 return SizeOffset.second; 320 } 321 322 bool anyKnown(SizeOffsetEvalType SizeOffset) { 323 return knownSize(SizeOffset) || knownOffset(SizeOffset); 324 } 325 326 bool bothKnown(SizeOffsetEvalType SizeOffset) { 327 return knownSize(SizeOffset) && knownOffset(SizeOffset); 328 } 329 330 // The individual instruction visitors should be treated as private. 331 SizeOffsetEvalType visitAllocaInst(AllocaInst &I); 332 SizeOffsetEvalType visitCallSite(CallSite CS); 333 SizeOffsetEvalType visitExtractElementInst(ExtractElementInst &I); 334 SizeOffsetEvalType visitExtractValueInst(ExtractValueInst &I); 335 SizeOffsetEvalType visitGEPOperator(GEPOperator &GEP); 336 SizeOffsetEvalType visitIntToPtrInst(IntToPtrInst&); 337 SizeOffsetEvalType visitLoadInst(LoadInst &I); 338 SizeOffsetEvalType visitPHINode(PHINode &PHI); 339 SizeOffsetEvalType visitSelectInst(SelectInst &I); 340 SizeOffsetEvalType visitInstruction(Instruction &I); 341 }; 342 343 } // end namespace llvm 344 345 #endif // LLVM_ANALYSIS_MEMORYBUILTINS_H 346