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 29namespace llvm { 30 31class AllocaInst; 32class Argument; 33class CallInst; 34class ConstantInt; 35class ConstantPointerNull; 36class DataLayout; 37class ExtractElementInst; 38class ExtractValueInst; 39class GEPOperator; 40class GlobalAlias; 41class GlobalVariable; 42class Instruction; 43class IntegerType; 44class IntrinsicInst; 45class IntToPtrInst; 46class LLVMContext; 47class LoadInst; 48class PHINode; 49class PointerType; 50class SelectInst; 51class TargetLibraryInfo; 52class Type; 53class UndefValue; 54class 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). 59bool isAllocationFn(const Value *V, const TargetLibraryInfo *TLI, 60 bool LookThroughBitCast = false); 61bool 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). 67bool 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). 72bool isMallocLikeFn(const Value *V, const TargetLibraryInfo *TLI, 73 bool LookThroughBitCast = false); 74bool 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). 80bool 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. 85bool 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). 90bool 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). 95bool 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). 100bool 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). 104bool 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). 109bool 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. 119const CallInst * 120extractMallocCall(const Value *I, 121 function_ref<const TargetLibraryInfo &(Function &)> GetTLI); 122inline CallInst * 123extractMallocCall(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. 133PointerType *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. 140Type *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. 147Value *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. 157const CallInst *extractCallocCall(const Value *I, const TargetLibraryInfo *TLI); 158inline 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() 168bool isLibFreeFunction(const Function *F, const LibFunc TLIFn); 169 170/// isFreeCall - Returns non-null if the value is a call to the builtin free() 171const CallInst *isFreeCall(const Value *I, const TargetLibraryInfo *TLI); 172 173inline 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. 182struct 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. 209bool 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. 216Value *lowerObjectSizeCall(IntrinsicInst *ObjectSize, const DataLayout &DL, 217 const TargetLibraryInfo *TLI, bool MustSucceed); 218 219 220 221using 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. 225class 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 240public: 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 276private: 277 bool CheckedZextOrTrunc(APInt &I); 278}; 279 280using 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. 284class 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 304public: 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