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/IRBuilder.h" 23 #include "llvm/IR/InstVisitor.h" 24 #include "llvm/IR/ValueHandle.h" 25 #include <cstdint> 26 #include <utility> 27 28 namespace llvm { 29 30 class AllocaInst; 31 class AAResults; 32 class Argument; 33 class ConstantPointerNull; 34 class DataLayout; 35 class ExtractElementInst; 36 class ExtractValueInst; 37 class GEPOperator; 38 class GlobalAlias; 39 class GlobalVariable; 40 class Instruction; 41 class IntegerType; 42 class IntrinsicInst; 43 class IntToPtrInst; 44 class LLVMContext; 45 class LoadInst; 46 class PHINode; 47 class SelectInst; 48 class Type; 49 class UndefValue; 50 class Value; 51 52 /// Tests if a value is a call or invoke to a library function that 53 /// allocates or reallocates memory (either malloc, calloc, realloc, or strdup 54 /// like). 55 bool isAllocationFn(const Value *V, const TargetLibraryInfo *TLI); 56 bool isAllocationFn(const Value *V, 57 function_ref<const TargetLibraryInfo &(Function &)> GetTLI); 58 59 /// Tests if a value is a call or invoke to a library function that 60 /// allocates memory similar to malloc or calloc. 61 bool isMallocOrCallocLikeFn(const Value *V, const TargetLibraryInfo *TLI); 62 63 /// Tests if a value is a call or invoke to a library function that 64 /// allocates memory (either malloc, calloc, or strdup like). 65 bool isAllocLikeFn(const Value *V, const TargetLibraryInfo *TLI); 66 67 /// Tests if a function is a call or invoke to a library function that 68 /// reallocates memory (e.g., realloc). 69 bool isReallocLikeFn(const Function *F, const TargetLibraryInfo *TLI); 70 71 /// If this is a call to a realloc function, return the reallocated operand. 72 Value *getReallocatedOperand(const CallBase *CB, const TargetLibraryInfo *TLI); 73 74 //===----------------------------------------------------------------------===// 75 // free Call Utility Functions. 76 // 77 78 /// isLibFreeFunction - Returns true if the function is a builtin free() 79 bool isLibFreeFunction(const Function *F, const LibFunc TLIFn); 80 81 /// If this if a call to a free function, return the freed operand. 82 Value *getFreedOperand(const CallBase *CB, const TargetLibraryInfo *TLI); 83 84 //===----------------------------------------------------------------------===// 85 // Properties of allocation functions 86 // 87 88 /// Return true if this is a call to an allocation function that does not have 89 /// side effects that we are required to preserve beyond the effect of 90 /// allocating a new object. 91 /// Ex: If our allocation routine has a counter for the number of objects 92 /// allocated, and the program prints it on exit, can the value change due 93 /// to optimization? Answer is highly language dependent. 94 /// Note: *Removable* really does mean removable; it does not mean observable. 95 /// A language (e.g. C++) can allow removing allocations without allowing 96 /// insertion or speculative execution of allocation routines. 97 bool isRemovableAlloc(const CallBase *V, const TargetLibraryInfo *TLI); 98 99 /// Gets the alignment argument for an aligned_alloc-like function, using either 100 /// built-in knowledge based on fuction names/signatures or allocalign 101 /// attributes. Note: the Value returned may not indicate a valid alignment, per 102 /// the definition of the allocalign attribute. 103 Value *getAllocAlignment(const CallBase *V, const TargetLibraryInfo *TLI); 104 105 /// Return the size of the requested allocation. With a trivial mapper, this is 106 /// similar to calling getObjectSize(..., Exact), but without looking through 107 /// calls that return their argument. A mapper function can be used to replace 108 /// one Value* (operand to the allocation) with another. This is useful when 109 /// doing abstract interpretation. 110 Optional<APInt> getAllocSize( 111 const CallBase *CB, const TargetLibraryInfo *TLI, 112 function_ref<const Value *(const Value *)> Mapper = [](const Value *V) { 113 return V; 114 }); 115 116 /// If this is a call to an allocation function that initializes memory to a 117 /// fixed value, return said value in the requested type. Otherwise, return 118 /// nullptr. 119 Constant *getInitialValueOfAllocation(const Value *V, 120 const TargetLibraryInfo *TLI, 121 Type *Ty); 122 123 /// If a function is part of an allocation family (e.g. 124 /// malloc/realloc/calloc/free), return the identifier for its family 125 /// of functions. 126 Optional<StringRef> getAllocationFamily(const Value *I, 127 const TargetLibraryInfo *TLI); 128 129 //===----------------------------------------------------------------------===// 130 // Utility functions to compute size of objects. 131 // 132 133 /// Various options to control the behavior of getObjectSize. 134 struct ObjectSizeOpts { 135 /// Controls how we handle conditional statements with unknown conditions. 136 enum class Mode : uint8_t { 137 /// Fail to evaluate an unknown condition. 138 Exact, 139 /// Evaluate all branches of an unknown condition. If all evaluations 140 /// succeed, pick the minimum size. 141 Min, 142 /// Same as Min, except we pick the maximum size of all of the branches. 143 Max 144 }; 145 146 /// How we want to evaluate this object's size. 147 Mode EvalMode = Mode::Exact; 148 /// Whether to round the result up to the alignment of allocas, byval 149 /// arguments, and global variables. 150 bool RoundToAlign = false; 151 /// If this is true, null pointers in address space 0 will be treated as 152 /// though they can't be evaluated. Otherwise, null is always considered to 153 /// point to a 0 byte region of memory. 154 bool NullIsUnknownSize = false; 155 /// If set, used for more accurate evaluation 156 AAResults *AA = nullptr; 157 }; 158 159 /// Compute the size of the object pointed by Ptr. Returns true and the 160 /// object size in Size if successful, and false otherwise. In this context, by 161 /// object we mean the region of memory starting at Ptr to the end of the 162 /// underlying object pointed to by Ptr. 163 /// 164 /// WARNING: The object size returned is the allocation size. This does not 165 /// imply dereferenceability at site of use since the object may be freeed in 166 /// between. 167 bool getObjectSize(const Value *Ptr, uint64_t &Size, const DataLayout &DL, 168 const TargetLibraryInfo *TLI, ObjectSizeOpts Opts = {}); 169 170 /// Try to turn a call to \@llvm.objectsize into an integer value of the given 171 /// Type. Returns null on failure. If MustSucceed is true, this function will 172 /// not return null, and may return conservative values governed by the second 173 /// argument of the call to objectsize. 174 Value *lowerObjectSizeCall(IntrinsicInst *ObjectSize, const DataLayout &DL, 175 const TargetLibraryInfo *TLI, bool MustSucceed); 176 Value *lowerObjectSizeCall(IntrinsicInst *ObjectSize, const DataLayout &DL, 177 const TargetLibraryInfo *TLI, AAResults *AA, 178 bool MustSucceed); 179 180 using SizeOffsetType = std::pair<APInt, APInt>; 181 182 /// Evaluate the size and offset of an object pointed to by a Value* 183 /// statically. Fails if size or offset are not known at compile time. 184 class ObjectSizeOffsetVisitor 185 : public InstVisitor<ObjectSizeOffsetVisitor, SizeOffsetType> { 186 const DataLayout &DL; 187 const TargetLibraryInfo *TLI; 188 ObjectSizeOpts Options; 189 unsigned IntTyBits; 190 APInt Zero; 191 SmallPtrSet<Instruction *, 8> SeenInsts; 192 193 APInt align(APInt Size, MaybeAlign Align); 194 195 SizeOffsetType unknown() { 196 return std::make_pair(APInt(), APInt()); 197 } 198 199 public: 200 ObjectSizeOffsetVisitor(const DataLayout &DL, const TargetLibraryInfo *TLI, 201 LLVMContext &Context, ObjectSizeOpts Options = {}); 202 203 SizeOffsetType compute(Value *V); 204 205 static bool knownSize(const SizeOffsetType &SizeOffset) { 206 return SizeOffset.first.getBitWidth() > 1; 207 } 208 209 static bool knownOffset(const SizeOffsetType &SizeOffset) { 210 return SizeOffset.second.getBitWidth() > 1; 211 } 212 213 static bool bothKnown(const SizeOffsetType &SizeOffset) { 214 return knownSize(SizeOffset) && knownOffset(SizeOffset); 215 } 216 217 // These are "private", except they can't actually be made private. Only 218 // compute() should be used by external users. 219 SizeOffsetType visitAllocaInst(AllocaInst &I); 220 SizeOffsetType visitArgument(Argument &A); 221 SizeOffsetType visitCallBase(CallBase &CB); 222 SizeOffsetType visitConstantPointerNull(ConstantPointerNull&); 223 SizeOffsetType visitExtractElementInst(ExtractElementInst &I); 224 SizeOffsetType visitExtractValueInst(ExtractValueInst &I); 225 SizeOffsetType visitGlobalAlias(GlobalAlias &GA); 226 SizeOffsetType visitGlobalVariable(GlobalVariable &GV); 227 SizeOffsetType visitIntToPtrInst(IntToPtrInst&); 228 SizeOffsetType visitLoadInst(LoadInst &I); 229 SizeOffsetType visitPHINode(PHINode&); 230 SizeOffsetType visitSelectInst(SelectInst &I); 231 SizeOffsetType visitUndefValue(UndefValue&); 232 SizeOffsetType visitInstruction(Instruction &I); 233 234 private: 235 SizeOffsetType findLoadSizeOffset( 236 LoadInst &LoadFrom, BasicBlock &BB, BasicBlock::iterator From, 237 SmallDenseMap<BasicBlock *, SizeOffsetType, 8> &VisitedBlocks, 238 unsigned &ScannedInstCount); 239 SizeOffsetType combineSizeOffset(SizeOffsetType LHS, SizeOffsetType RHS); 240 SizeOffsetType computeImpl(Value *V); 241 bool CheckedZextOrTrunc(APInt &I); 242 }; 243 244 using SizeOffsetEvalType = std::pair<Value *, Value *>; 245 246 /// Evaluate the size and offset of an object pointed to by a Value*. 247 /// May create code to compute the result at run-time. 248 class ObjectSizeOffsetEvaluator 249 : public InstVisitor<ObjectSizeOffsetEvaluator, SizeOffsetEvalType> { 250 using BuilderTy = IRBuilder<TargetFolder, IRBuilderCallbackInserter>; 251 using WeakEvalType = std::pair<WeakTrackingVH, WeakTrackingVH>; 252 using CacheMapTy = DenseMap<const Value *, WeakEvalType>; 253 using PtrSetTy = SmallPtrSet<const Value *, 8>; 254 255 const DataLayout &DL; 256 const TargetLibraryInfo *TLI; 257 LLVMContext &Context; 258 BuilderTy Builder; 259 IntegerType *IntTy; 260 Value *Zero; 261 CacheMapTy CacheMap; 262 PtrSetTy SeenVals; 263 ObjectSizeOpts EvalOpts; 264 SmallPtrSet<Instruction *, 8> InsertedInstructions; 265 266 SizeOffsetEvalType compute_(Value *V); 267 268 public: 269 static SizeOffsetEvalType unknown() { 270 return std::make_pair(nullptr, nullptr); 271 } 272 273 ObjectSizeOffsetEvaluator(const DataLayout &DL, const TargetLibraryInfo *TLI, 274 LLVMContext &Context, ObjectSizeOpts EvalOpts = {}); 275 276 SizeOffsetEvalType compute(Value *V); 277 278 bool knownSize(SizeOffsetEvalType SizeOffset) { 279 return SizeOffset.first; 280 } 281 282 bool knownOffset(SizeOffsetEvalType SizeOffset) { 283 return SizeOffset.second; 284 } 285 286 bool anyKnown(SizeOffsetEvalType SizeOffset) { 287 return knownSize(SizeOffset) || knownOffset(SizeOffset); 288 } 289 290 bool bothKnown(SizeOffsetEvalType SizeOffset) { 291 return knownSize(SizeOffset) && knownOffset(SizeOffset); 292 } 293 294 // The individual instruction visitors should be treated as private. 295 SizeOffsetEvalType visitAllocaInst(AllocaInst &I); 296 SizeOffsetEvalType visitCallBase(CallBase &CB); 297 SizeOffsetEvalType visitExtractElementInst(ExtractElementInst &I); 298 SizeOffsetEvalType visitExtractValueInst(ExtractValueInst &I); 299 SizeOffsetEvalType visitGEPOperator(GEPOperator &GEP); 300 SizeOffsetEvalType visitIntToPtrInst(IntToPtrInst&); 301 SizeOffsetEvalType visitLoadInst(LoadInst &I); 302 SizeOffsetEvalType visitPHINode(PHINode &PHI); 303 SizeOffsetEvalType visitSelectInst(SelectInst &I); 304 SizeOffsetEvalType visitInstruction(Instruction &I); 305 }; 306 307 } // end namespace llvm 308 309 #endif // LLVM_ANALYSIS_MEMORYBUILTINS_H 310