1327952Sdim//==- llvm/Analysis/MemoryBuiltins.h - Calls to memory builtins --*- C++ -*-==// 2198892Srdivacky// 3353358Sdim// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4353358Sdim// See https://llvm.org/LICENSE.txt for license information. 5353358Sdim// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 6198892Srdivacky// 7198892Srdivacky//===----------------------------------------------------------------------===// 8198892Srdivacky// 9198892Srdivacky// This family of functions identifies calls to builtin functions that allocate 10261991Sdim// or free memory. 11198892Srdivacky// 12198892Srdivacky//===----------------------------------------------------------------------===// 13198892Srdivacky 14198892Srdivacky#ifndef LLVM_ANALYSIS_MEMORYBUILTINS_H 15198892Srdivacky#define LLVM_ANALYSIS_MEMORYBUILTINS_H 16198892Srdivacky 17327952Sdim#include "llvm/ADT/APInt.h" 18239462Sdim#include "llvm/ADT/DenseMap.h" 19239462Sdim#include "llvm/ADT/SmallPtrSet.h" 20276479Sdim#include "llvm/Analysis/TargetFolder.h" 21353358Sdim#include "llvm/Analysis/TargetLibraryInfo.h" 22327952Sdim#include "llvm/IR/CallSite.h" 23249423Sdim#include "llvm/IR/IRBuilder.h" 24276479Sdim#include "llvm/IR/InstVisitor.h" 25276479Sdim#include "llvm/IR/ValueHandle.h" 26327952Sdim#include <cstdint> 27327952Sdim#include <utility> 28239462Sdim 29198892Srdivackynamespace llvm { 30327952Sdim 31327952Sdimclass AllocaInst; 32327952Sdimclass Argument; 33198892Srdivackyclass CallInst; 34327952Sdimclass ConstantInt; 35327952Sdimclass ConstantPointerNull; 36327952Sdimclass DataLayout; 37327952Sdimclass ExtractElementInst; 38327952Sdimclass ExtractValueInst; 39327952Sdimclass GEPOperator; 40327952Sdimclass GlobalAlias; 41327952Sdimclass GlobalVariable; 42327952Sdimclass Instruction; 43327952Sdimclass IntegerType; 44327952Sdimclass IntrinsicInst; 45327952Sdimclass IntToPtrInst; 46327952Sdimclass LLVMContext; 47327952Sdimclass LoadInst; 48327952Sdimclass PHINode; 49198892Srdivackyclass PointerType; 50327952Sdimclass SelectInst; 51243830Sdimclass TargetLibraryInfo; 52198892Srdivackyclass Type; 53327952Sdimclass UndefValue; 54198892Srdivackyclass Value; 55198892Srdivacky 56341825Sdim/// Tests if a value is a call or invoke to a library function that 57239462Sdim/// allocates or reallocates memory (either malloc, calloc, realloc, or strdup 58239462Sdim/// like). 59243830Sdimbool isAllocationFn(const Value *V, const TargetLibraryInfo *TLI, 60243830Sdim bool LookThroughBitCast = false); 61360784Sdimbool isAllocationFn(const Value *V, 62360784Sdim function_ref<const TargetLibraryInfo &(Function &)> GetTLI, 63360784Sdim bool LookThroughBitCast = false); 64239462Sdim 65341825Sdim/// Tests if a value is a call or invoke to a function that returns a 66239462Sdim/// NoAlias pointer (including malloc/calloc/realloc/strdup-like functions). 67243830Sdimbool isNoAliasFn(const Value *V, const TargetLibraryInfo *TLI, 68243830Sdim bool LookThroughBitCast = false); 69239462Sdim 70341825Sdim/// Tests if a value is a call or invoke to a library function that 71239462Sdim/// allocates uninitialized memory (such as malloc). 72243830Sdimbool isMallocLikeFn(const Value *V, const TargetLibraryInfo *TLI, 73243830Sdim bool LookThroughBitCast = false); 74360784Sdimbool isMallocLikeFn(const Value *V, 75360784Sdim function_ref<const TargetLibraryInfo &(Function &)> GetTLI, 76360784Sdim bool LookThroughBitCast = false); 77239462Sdim 78341825Sdim/// Tests if a value is a call or invoke to a library function that 79239462Sdim/// allocates zero-filled memory (such as calloc). 80243830Sdimbool isCallocLikeFn(const Value *V, const TargetLibraryInfo *TLI, 81243830Sdim bool LookThroughBitCast = false); 82239462Sdim 83341825Sdim/// Tests if a value is a call or invoke to a library function that 84321369Sdim/// allocates memory similar to malloc or calloc. 85321369Sdimbool isMallocOrCallocLikeFn(const Value *V, const TargetLibraryInfo *TLI, 86321369Sdim bool LookThroughBitCast = false); 87321369Sdim 88341825Sdim/// Tests if a value is a call or invoke to a library function that 89239462Sdim/// allocates memory (either malloc, calloc, or strdup like). 90243830Sdimbool isAllocLikeFn(const Value *V, const TargetLibraryInfo *TLI, 91243830Sdim bool LookThroughBitCast = false); 92239462Sdim 93353358Sdim/// Tests if a value is a call or invoke to a library function that 94353358Sdim/// reallocates memory (e.g., realloc). 95353358Sdimbool isReallocLikeFn(const Value *V, const TargetLibraryInfo *TLI, 96353358Sdim bool LookThroughBitCast = false); 97353358Sdim 98353358Sdim/// Tests if a function is a call or invoke to a library function that 99353358Sdim/// reallocates memory (e.g., realloc). 100353358Sdimbool isReallocLikeFn(const Function *F, const TargetLibraryInfo *TLI); 101353358Sdim 102360784Sdim/// Tests if a value is a call or invoke to a library function that 103360784Sdim/// allocates memory and throws if an allocation failed (e.g., new). 104360784Sdimbool isOpNewLikeFn(const Value *V, const TargetLibraryInfo *TLI, 105360784Sdim bool LookThroughBitCast = false); 106360784Sdim 107360784Sdim/// Tests if a value is a call or invoke to a library function that 108360784Sdim/// allocates memory (strdup, strndup). 109360784Sdimbool isStrdupLikeFn(const Value *V, const TargetLibraryInfo *TLI, 110360784Sdim bool LookThroughBitCast = false); 111360784Sdim 112198892Srdivacky//===----------------------------------------------------------------------===// 113198892Srdivacky// malloc Call Utility Functions. 114198892Srdivacky// 115198892Srdivacky 116198892Srdivacky/// extractMallocCall - Returns the corresponding CallInst if the instruction 117198892Srdivacky/// is a malloc call. Since CallInst::CreateMalloc() only creates calls, we 118198892Srdivacky/// ignore InvokeInst here. 119360784Sdimconst CallInst * 120360784SdimextractMallocCall(const Value *I, 121360784Sdim function_ref<const TargetLibraryInfo &(Function &)> GetTLI); 122360784Sdiminline CallInst * 123360784SdimextractMallocCall(Value *I, 124360784Sdim function_ref<const TargetLibraryInfo &(Function &)> GetTLI) { 125360784Sdim return const_cast<CallInst *>(extractMallocCall((const Value *)I, GetTLI)); 126239462Sdim} 127198892Srdivacky 128198892Srdivacky/// getMallocType - Returns the PointerType resulting from the malloc call. 129198953Srdivacky/// The PointerType depends on the number of bitcast uses of the malloc call: 130198953Srdivacky/// 0: PointerType is the malloc calls' return type. 131198953Srdivacky/// 1: PointerType is the bitcast's result type. 132198953Srdivacky/// >1: Unique PointerType cannot be determined, return NULL. 133243830SdimPointerType *getMallocType(const CallInst *CI, const TargetLibraryInfo *TLI); 134198892Srdivacky 135198953Srdivacky/// getMallocAllocatedType - Returns the Type allocated by malloc call. 136198953Srdivacky/// The Type depends on the number of bitcast uses of the malloc call: 137198953Srdivacky/// 0: PointerType is the malloc calls' return type. 138198953Srdivacky/// 1: PointerType is the bitcast's result type. 139198953Srdivacky/// >1: Unique PointerType cannot be determined, return NULL. 140243830SdimType *getMallocAllocatedType(const CallInst *CI, const TargetLibraryInfo *TLI); 141198892Srdivacky 142261991Sdim/// getMallocArraySize - Returns the array size of a malloc call. If the 143198892Srdivacky/// argument passed to malloc is a multiple of the size of the malloced type, 144198892Srdivacky/// then return that multiple. For non-array mallocs, the multiple is 145198892Srdivacky/// constant 1. Otherwise, return NULL for mallocs whose array size cannot be 146198892Srdivacky/// determined. 147288943SdimValue *getMallocArraySize(CallInst *CI, const DataLayout &DL, 148243830Sdim const TargetLibraryInfo *TLI, 149199481Srdivacky bool LookThroughSExt = false); 150239462Sdim 151198892Srdivacky//===----------------------------------------------------------------------===// 152239462Sdim// calloc Call Utility Functions. 153239462Sdim// 154239462Sdim 155239462Sdim/// extractCallocCall - Returns the corresponding CallInst if the instruction 156239462Sdim/// is a calloc call. 157243830Sdimconst CallInst *extractCallocCall(const Value *I, const TargetLibraryInfo *TLI); 158327952Sdiminline CallInst *extractCallocCall(Value *I, const TargetLibraryInfo *TLI) { 159243830Sdim return const_cast<CallInst*>(extractCallocCall((const Value*)I, TLI)); 160239462Sdim} 161239462Sdim 162239462Sdim 163239462Sdim//===----------------------------------------------------------------------===// 164198892Srdivacky// free Call Utility Functions. 165198892Srdivacky// 166198892Srdivacky 167353358Sdim/// isLibFreeFunction - Returns true if the function is a builtin free() 168353358Sdimbool isLibFreeFunction(const Function *F, const LibFunc TLIFn); 169353358Sdim 170210299Sed/// isFreeCall - Returns non-null if the value is a call to the builtin free() 171243830Sdimconst CallInst *isFreeCall(const Value *I, const TargetLibraryInfo *TLI); 172261991Sdim 173327952Sdiminline CallInst *isFreeCall(Value *I, const TargetLibraryInfo *TLI) { 174243830Sdim return const_cast<CallInst*>(isFreeCall((const Value*)I, TLI)); 175218893Sdim} 176198892Srdivacky 177239462Sdim//===----------------------------------------------------------------------===// 178239462Sdim// Utility functions to compute size of objects. 179239462Sdim// 180239462Sdim 181321369Sdim/// Various options to control the behavior of getObjectSize. 182321369Sdimstruct ObjectSizeOpts { 183321369Sdim /// Controls how we handle conditional statements with unknown conditions. 184321369Sdim enum class Mode : uint8_t { 185321369Sdim /// Fail to evaluate an unknown condition. 186321369Sdim Exact, 187321369Sdim /// Evaluate all branches of an unknown condition. If all evaluations 188321369Sdim /// succeed, pick the minimum size. 189321369Sdim Min, 190321369Sdim /// Same as Min, except we pick the maximum size of all of the branches. 191321369Sdim Max 192321369Sdim }; 193321369Sdim 194321369Sdim /// How we want to evaluate this object's size. 195321369Sdim Mode EvalMode = Mode::Exact; 196321369Sdim /// Whether to round the result up to the alignment of allocas, byval 197321369Sdim /// arguments, and global variables. 198321369Sdim bool RoundToAlign = false; 199321369Sdim /// If this is true, null pointers in address space 0 will be treated as 200321369Sdim /// though they can't be evaluated. Otherwise, null is always considered to 201321369Sdim /// point to a 0 byte region of memory. 202321369Sdim bool NullIsUnknownSize = false; 203321369Sdim}; 204321369Sdim 205341825Sdim/// Compute the size of the object pointed by Ptr. Returns true and the 206249423Sdim/// object size in Size if successful, and false otherwise. In this context, by 207249423Sdim/// object we mean the region of memory starting at Ptr to the end of the 208249423Sdim/// underlying object pointed to by Ptr. 209288943Sdimbool getObjectSize(const Value *Ptr, uint64_t &Size, const DataLayout &DL, 210321369Sdim const TargetLibraryInfo *TLI, ObjectSizeOpts Opts = {}); 211239462Sdim 212341825Sdim/// Try to turn a call to \@llvm.objectsize into an integer value of the given 213353358Sdim/// Type. Returns null on failure. If MustSucceed is true, this function will 214353358Sdim/// not return null, and may return conservative values governed by the second 215353358Sdim/// argument of the call to objectsize. 216353358SdimValue *lowerObjectSizeCall(IntrinsicInst *ObjectSize, const DataLayout &DL, 217353358Sdim const TargetLibraryInfo *TLI, bool MustSucceed); 218314564Sdim 219353358Sdim 220353358Sdim 221327952Sdimusing SizeOffsetType = std::pair<APInt, APInt>; 222239462Sdim 223341825Sdim/// Evaluate the size and offset of an object pointed to by a Value* 224239462Sdim/// statically. Fails if size or offset are not known at compile time. 225239462Sdimclass ObjectSizeOffsetVisitor 226239462Sdim : public InstVisitor<ObjectSizeOffsetVisitor, SizeOffsetType> { 227288943Sdim const DataLayout &DL; 228243830Sdim const TargetLibraryInfo *TLI; 229321369Sdim ObjectSizeOpts Options; 230239462Sdim unsigned IntTyBits; 231239462Sdim APInt Zero; 232251662Sdim SmallPtrSet<Instruction *, 8> SeenInsts; 233239462Sdim 234239462Sdim APInt align(APInt Size, uint64_t Align); 235239462Sdim 236239462Sdim SizeOffsetType unknown() { 237239462Sdim return std::make_pair(APInt(), APInt()); 238239462Sdim } 239239462Sdim 240239462Sdimpublic: 241288943Sdim ObjectSizeOffsetVisitor(const DataLayout &DL, const TargetLibraryInfo *TLI, 242321369Sdim LLVMContext &Context, ObjectSizeOpts Options = {}); 243239462Sdim 244239462Sdim SizeOffsetType compute(Value *V); 245239462Sdim 246309124Sdim static bool knownSize(const SizeOffsetType &SizeOffset) { 247239462Sdim return SizeOffset.first.getBitWidth() > 1; 248239462Sdim } 249239462Sdim 250309124Sdim static bool knownOffset(const SizeOffsetType &SizeOffset) { 251239462Sdim return SizeOffset.second.getBitWidth() > 1; 252239462Sdim } 253239462Sdim 254309124Sdim static bool bothKnown(const SizeOffsetType &SizeOffset) { 255239462Sdim return knownSize(SizeOffset) && knownOffset(SizeOffset); 256239462Sdim } 257239462Sdim 258276479Sdim // These are "private", except they can't actually be made private. Only 259276479Sdim // compute() should be used by external users. 260239462Sdim SizeOffsetType visitAllocaInst(AllocaInst &I); 261239462Sdim SizeOffsetType visitArgument(Argument &A); 262239462Sdim SizeOffsetType visitCallSite(CallSite CS); 263239462Sdim SizeOffsetType visitConstantPointerNull(ConstantPointerNull&); 264239462Sdim SizeOffsetType visitExtractElementInst(ExtractElementInst &I); 265239462Sdim SizeOffsetType visitExtractValueInst(ExtractValueInst &I); 266239462Sdim SizeOffsetType visitGEPOperator(GEPOperator &GEP); 267249423Sdim SizeOffsetType visitGlobalAlias(GlobalAlias &GA); 268239462Sdim SizeOffsetType visitGlobalVariable(GlobalVariable &GV); 269239462Sdim SizeOffsetType visitIntToPtrInst(IntToPtrInst&); 270239462Sdim SizeOffsetType visitLoadInst(LoadInst &I); 271239462Sdim SizeOffsetType visitPHINode(PHINode&); 272239462Sdim SizeOffsetType visitSelectInst(SelectInst &I); 273239462Sdim SizeOffsetType visitUndefValue(UndefValue&); 274239462Sdim SizeOffsetType visitInstruction(Instruction &I); 275321369Sdim 276321369Sdimprivate: 277321369Sdim bool CheckedZextOrTrunc(APInt &I); 278239462Sdim}; 279239462Sdim 280327952Sdimusing SizeOffsetEvalType = std::pair<Value *, Value *>; 281239462Sdim 282341825Sdim/// Evaluate the size and offset of an object pointed to by a Value*. 283239462Sdim/// May create code to compute the result at run-time. 284239462Sdimclass ObjectSizeOffsetEvaluator 285239462Sdim : public InstVisitor<ObjectSizeOffsetEvaluator, SizeOffsetEvalType> { 286353358Sdim using BuilderTy = IRBuilder<TargetFolder, IRBuilderCallbackInserter>; 287327952Sdim using WeakEvalType = std::pair<WeakTrackingVH, WeakTrackingVH>; 288327952Sdim using CacheMapTy = DenseMap<const Value *, WeakEvalType>; 289327952Sdim using PtrSetTy = SmallPtrSet<const Value *, 8>; 290239462Sdim 291288943Sdim const DataLayout &DL; 292243830Sdim const TargetLibraryInfo *TLI; 293239462Sdim LLVMContext &Context; 294239462Sdim BuilderTy Builder; 295239462Sdim IntegerType *IntTy; 296239462Sdim Value *Zero; 297239462Sdim CacheMapTy CacheMap; 298239462Sdim PtrSetTy SeenVals; 299353358Sdim ObjectSizeOpts EvalOpts; 300353358Sdim SmallPtrSet<Instruction *, 8> InsertedInstructions; 301239462Sdim 302353358Sdim SizeOffsetEvalType compute_(Value *V); 303353358Sdim 304353358Sdimpublic: 305353358Sdim static SizeOffsetEvalType unknown() { 306276479Sdim return std::make_pair(nullptr, nullptr); 307239462Sdim } 308327952Sdim 309288943Sdim ObjectSizeOffsetEvaluator(const DataLayout &DL, const TargetLibraryInfo *TLI, 310353358Sdim LLVMContext &Context, ObjectSizeOpts EvalOpts = {}); 311327952Sdim 312239462Sdim SizeOffsetEvalType compute(Value *V); 313239462Sdim 314239462Sdim bool knownSize(SizeOffsetEvalType SizeOffset) { 315239462Sdim return SizeOffset.first; 316239462Sdim } 317239462Sdim 318239462Sdim bool knownOffset(SizeOffsetEvalType SizeOffset) { 319239462Sdim return SizeOffset.second; 320239462Sdim } 321239462Sdim 322239462Sdim bool anyKnown(SizeOffsetEvalType SizeOffset) { 323239462Sdim return knownSize(SizeOffset) || knownOffset(SizeOffset); 324239462Sdim } 325239462Sdim 326239462Sdim bool bothKnown(SizeOffsetEvalType SizeOffset) { 327239462Sdim return knownSize(SizeOffset) && knownOffset(SizeOffset); 328239462Sdim } 329239462Sdim 330276479Sdim // The individual instruction visitors should be treated as private. 331239462Sdim SizeOffsetEvalType visitAllocaInst(AllocaInst &I); 332239462Sdim SizeOffsetEvalType visitCallSite(CallSite CS); 333239462Sdim SizeOffsetEvalType visitExtractElementInst(ExtractElementInst &I); 334239462Sdim SizeOffsetEvalType visitExtractValueInst(ExtractValueInst &I); 335239462Sdim SizeOffsetEvalType visitGEPOperator(GEPOperator &GEP); 336239462Sdim SizeOffsetEvalType visitIntToPtrInst(IntToPtrInst&); 337239462Sdim SizeOffsetEvalType visitLoadInst(LoadInst &I); 338239462Sdim SizeOffsetEvalType visitPHINode(PHINode &PHI); 339239462Sdim SizeOffsetEvalType visitSelectInst(SelectInst &I); 340239462Sdim SizeOffsetEvalType visitInstruction(Instruction &I); 341239462Sdim}; 342239462Sdim 343327952Sdim} // end namespace llvm 344198892Srdivacky 345327952Sdim#endif // LLVM_ANALYSIS_MEMORYBUILTINS_H 346