LLVM  12.0.0git
MemoryBuiltins.h
Go to the documentation of this file.
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"
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 Argument;
32 class CallInst;
33 class ConstantInt;
34 class ConstantPointerNull;
35 class DataLayout;
36 class ExtractElementInst;
37 class ExtractValueInst;
38 class GEPOperator;
39 class GlobalAlias;
40 class GlobalVariable;
41 class Instruction;
42 class IntegerType;
43 class IntrinsicInst;
44 class IntToPtrInst;
45 class LLVMContext;
46 class LoadInst;
47 class PHINode;
48 class PointerType;
49 class SelectInst;
50 class Type;
51 class UndefValue;
52 class Value;
53 
54 /// Tests if a value is a call or invoke to a library function that
55 /// allocates or reallocates memory (either malloc, calloc, realloc, or strdup
56 /// like).
57 bool isAllocationFn(const Value *V, const TargetLibraryInfo *TLI,
58  bool LookThroughBitCast = false);
59 bool isAllocationFn(const Value *V,
60  function_ref<const TargetLibraryInfo &(Function &)> GetTLI,
61  bool LookThroughBitCast = false);
62 
63 /// Tests if a value is a call or invoke to a function that returns a
64 /// NoAlias pointer (including malloc/calloc/realloc/strdup-like functions).
65 bool isNoAliasFn(const Value *V, const TargetLibraryInfo *TLI,
66  bool LookThroughBitCast = false);
67 
68 /// Tests if a value is a call or invoke to a library function that
69 /// allocates uninitialized memory (such as malloc).
70 bool isMallocLikeFn(const Value *V, const TargetLibraryInfo *TLI,
71  bool LookThroughBitCast = false);
72 bool isMallocLikeFn(const Value *V,
73  function_ref<const TargetLibraryInfo &(Function &)> GetTLI,
74  bool LookThroughBitCast = false);
75 
76 /// Tests if a value is a call or invoke to a library function that
77 /// allocates uninitialized memory with alignment (such as aligned_alloc).
78 bool isAlignedAllocLikeFn(const Value *V, const TargetLibraryInfo *TLI,
79  bool LookThroughBitCast = false);
81  const Value *V, function_ref<const TargetLibraryInfo &(Function &)> GetTLI,
82  bool LookThroughBitCast = false);
83 
84 /// Tests if a value is a call or invoke to a library function that
85 /// allocates zero-filled memory (such as calloc).
86 bool isCallocLikeFn(const Value *V, const TargetLibraryInfo *TLI,
87  bool LookThroughBitCast = false);
88 
89 /// Tests if a value is a call or invoke to a library function that
90 /// allocates memory similar to malloc or calloc.
91 bool isMallocOrCallocLikeFn(const Value *V, const TargetLibraryInfo *TLI,
92  bool LookThroughBitCast = false);
93 
94 /// Tests if a value is a call or invoke to a library function that
95 /// allocates memory (either malloc, calloc, or strdup like).
96 bool isAllocLikeFn(const Value *V, const TargetLibraryInfo *TLI,
97  bool LookThroughBitCast = false);
98 
99 /// Tests if a value is a call or invoke to a library function that
100 /// reallocates memory (e.g., realloc).
101 bool isReallocLikeFn(const Value *V, const TargetLibraryInfo *TLI,
102  bool LookThroughBitCast = false);
103 
104 /// Tests if a function is a call or invoke to a library function that
105 /// reallocates memory (e.g., realloc).
106 bool isReallocLikeFn(const Function *F, const TargetLibraryInfo *TLI);
107 
108 /// Tests if a value is a call or invoke to a library function that
109 /// allocates memory and throws if an allocation failed (e.g., new).
110 bool isOpNewLikeFn(const Value *V, const TargetLibraryInfo *TLI,
111  bool LookThroughBitCast = false);
112 
113 /// Tests if a value is a call or invoke to a library function that
114 /// allocates memory (strdup, strndup).
115 bool isStrdupLikeFn(const Value *V, const TargetLibraryInfo *TLI,
116  bool LookThroughBitCast = false);
117 
118 //===----------------------------------------------------------------------===//
119 // malloc Call Utility Functions.
120 //
121 
122 /// extractMallocCall - Returns the corresponding CallInst if the instruction
123 /// is a malloc call. Since CallInst::CreateMalloc() only creates calls, we
124 /// ignore InvokeInst here.
125 const CallInst *
126 extractMallocCall(const Value *I,
127  function_ref<const TargetLibraryInfo &(Function &)> GetTLI);
128 inline CallInst *
130  function_ref<const TargetLibraryInfo &(Function &)> GetTLI) {
131  return const_cast<CallInst *>(extractMallocCall((const Value *)I, GetTLI));
132 }
133 
134 /// getMallocType - Returns the PointerType resulting from the malloc call.
135 /// The PointerType depends on the number of bitcast uses of the malloc call:
136 /// 0: PointerType is the malloc calls' return type.
137 /// 1: PointerType is the bitcast's result type.
138 /// >1: Unique PointerType cannot be determined, return NULL.
139 PointerType *getMallocType(const CallInst *CI, const TargetLibraryInfo *TLI);
140 
141 /// getMallocAllocatedType - Returns the Type allocated by malloc call.
142 /// The Type depends on the number of bitcast uses of the malloc call:
143 /// 0: PointerType is the malloc calls' return type.
144 /// 1: PointerType is the bitcast's result type.
145 /// >1: Unique PointerType cannot be determined, return NULL.
146 Type *getMallocAllocatedType(const CallInst *CI, const TargetLibraryInfo *TLI);
147 
148 /// getMallocArraySize - Returns the array size of a malloc call. If the
149 /// argument passed to malloc is a multiple of the size of the malloced type,
150 /// then return that multiple. For non-array mallocs, the multiple is
151 /// constant 1. Otherwise, return NULL for mallocs whose array size cannot be
152 /// determined.
154  const TargetLibraryInfo *TLI,
155  bool LookThroughSExt = false);
156 
157 //===----------------------------------------------------------------------===//
158 // calloc Call Utility Functions.
159 //
160 
161 /// extractCallocCall - Returns the corresponding CallInst if the instruction
162 /// is a calloc call.
163 const CallInst *extractCallocCall(const Value *I, const TargetLibraryInfo *TLI);
165  return const_cast<CallInst*>(extractCallocCall((const Value*)I, TLI));
166 }
167 
168 
169 //===----------------------------------------------------------------------===//
170 // free Call Utility Functions.
171 //
172 
173 /// isLibFreeFunction - Returns true if the function is a builtin free()
174 bool isLibFreeFunction(const Function *F, const LibFunc TLIFn);
175 
176 /// isFreeCall - Returns non-null if the value is a call to the builtin free()
177 const CallInst *isFreeCall(const Value *I, const TargetLibraryInfo *TLI);
178 
179 inline CallInst *isFreeCall(Value *I, const TargetLibraryInfo *TLI) {
180  return const_cast<CallInst*>(isFreeCall((const Value*)I, TLI));
181 }
182 
183 //===----------------------------------------------------------------------===//
184 // Utility functions to compute size of objects.
185 //
186 
187 /// Various options to control the behavior of getObjectSize.
189  /// Controls how we handle conditional statements with unknown conditions.
190  enum class Mode : uint8_t {
191  /// Fail to evaluate an unknown condition.
192  Exact,
193  /// Evaluate all branches of an unknown condition. If all evaluations
194  /// succeed, pick the minimum size.
195  Min,
196  /// Same as Min, except we pick the maximum size of all of the branches.
197  Max
198  };
199 
200  /// How we want to evaluate this object's size.
202  /// Whether to round the result up to the alignment of allocas, byval
203  /// arguments, and global variables.
204  bool RoundToAlign = false;
205  /// If this is true, null pointers in address space 0 will be treated as
206  /// though they can't be evaluated. Otherwise, null is always considered to
207  /// point to a 0 byte region of memory.
208  bool NullIsUnknownSize = false;
209 };
210 
211 /// Compute the size of the object pointed by Ptr. Returns true and the
212 /// object size in Size if successful, and false otherwise. In this context, by
213 /// object we mean the region of memory starting at Ptr to the end of the
214 /// underlying object pointed to by Ptr.
215 bool getObjectSize(const Value *Ptr, uint64_t &Size, const DataLayout &DL,
216  const TargetLibraryInfo *TLI, ObjectSizeOpts Opts = {});
217 
218 /// Try to turn a call to \@llvm.objectsize into an integer value of the given
219 /// Type. Returns null on failure. If MustSucceed is true, this function will
220 /// not return null, and may return conservative values governed by the second
221 /// argument of the call to objectsize.
222 Value *lowerObjectSizeCall(IntrinsicInst *ObjectSize, const DataLayout &DL,
223  const TargetLibraryInfo *TLI, bool MustSucceed);
224 
225 
226 
227 using SizeOffsetType = std::pair<APInt, APInt>;
228 
229 /// Evaluate the size and offset of an object pointed to by a Value*
230 /// statically. Fails if size or offset are not known at compile time.
232  : public InstVisitor<ObjectSizeOffsetVisitor, SizeOffsetType> {
233  const DataLayout &DL;
234  const TargetLibraryInfo *TLI;
235  ObjectSizeOpts Options;
236  unsigned IntTyBits;
237  APInt Zero;
239 
240  APInt align(APInt Size, uint64_t Align);
241 
242  SizeOffsetType unknown() {
243  return std::make_pair(APInt(), APInt());
244  }
245 
246 public:
248  LLVMContext &Context, ObjectSizeOpts Options = {});
249 
250  SizeOffsetType compute(Value *V);
251 
252  static bool knownSize(const SizeOffsetType &SizeOffset) {
253  return SizeOffset.first.getBitWidth() > 1;
254  }
255 
256  static bool knownOffset(const SizeOffsetType &SizeOffset) {
257  return SizeOffset.second.getBitWidth() > 1;
258  }
259 
260  static bool bothKnown(const SizeOffsetType &SizeOffset) {
261  return knownSize(SizeOffset) && knownOffset(SizeOffset);
262  }
263 
264  // These are "private", except they can't actually be made private. Only
265  // compute() should be used by external users.
266  SizeOffsetType visitAllocaInst(AllocaInst &I);
267  SizeOffsetType visitArgument(Argument &A);
268  SizeOffsetType visitCallBase(CallBase &CB);
269  SizeOffsetType visitConstantPointerNull(ConstantPointerNull&);
270  SizeOffsetType visitExtractElementInst(ExtractElementInst &I);
271  SizeOffsetType visitExtractValueInst(ExtractValueInst &I);
272  SizeOffsetType visitGEPOperator(GEPOperator &GEP);
273  SizeOffsetType visitGlobalAlias(GlobalAlias &GA);
274  SizeOffsetType visitGlobalVariable(GlobalVariable &GV);
275  SizeOffsetType visitIntToPtrInst(IntToPtrInst&);
276  SizeOffsetType visitLoadInst(LoadInst &I);
277  SizeOffsetType visitPHINode(PHINode&);
278  SizeOffsetType visitSelectInst(SelectInst &I);
279  SizeOffsetType visitUndefValue(UndefValue&);
280  SizeOffsetType visitInstruction(Instruction &I);
281 
282 private:
283  bool CheckedZextOrTrunc(APInt &I);
284 };
285 
286 using SizeOffsetEvalType = std::pair<Value *, Value *>;
287 
288 /// Evaluate the size and offset of an object pointed to by a Value*.
289 /// May create code to compute the result at run-time.
291  : public InstVisitor<ObjectSizeOffsetEvaluator, SizeOffsetEvalType> {
293  using WeakEvalType = std::pair<WeakTrackingVH, WeakTrackingVH>;
296 
297  const DataLayout &DL;
298  const TargetLibraryInfo *TLI;
301  IntegerType *IntTy;
302  Value *Zero;
303  CacheMapTy CacheMap;
304  PtrSetTy SeenVals;
305  ObjectSizeOpts EvalOpts;
306  SmallPtrSet<Instruction *, 8> InsertedInstructions;
307 
308  SizeOffsetEvalType compute_(Value *V);
309 
310 public:
312  return std::make_pair(nullptr, nullptr);
313  }
314 
316  LLVMContext &Context, ObjectSizeOpts EvalOpts = {});
317 
318  SizeOffsetEvalType compute(Value *V);
319 
320  bool knownSize(SizeOffsetEvalType SizeOffset) {
321  return SizeOffset.first;
322  }
323 
324  bool knownOffset(SizeOffsetEvalType SizeOffset) {
325  return SizeOffset.second;
326  }
327 
328  bool anyKnown(SizeOffsetEvalType SizeOffset) {
329  return knownSize(SizeOffset) || knownOffset(SizeOffset);
330  }
331 
332  bool bothKnown(SizeOffsetEvalType SizeOffset) {
333  return knownSize(SizeOffset) && knownOffset(SizeOffset);
334  }
335 
336  // The individual instruction visitors should be treated as private.
337  SizeOffsetEvalType visitAllocaInst(AllocaInst &I);
338  SizeOffsetEvalType visitCallBase(CallBase &CB);
339  SizeOffsetEvalType visitExtractElementInst(ExtractElementInst &I);
340  SizeOffsetEvalType visitExtractValueInst(ExtractValueInst &I);
341  SizeOffsetEvalType visitGEPOperator(GEPOperator &GEP);
342  SizeOffsetEvalType visitIntToPtrInst(IntToPtrInst&);
343  SizeOffsetEvalType visitLoadInst(LoadInst &I);
344  SizeOffsetEvalType visitPHINode(PHINode &PHI);
345  SizeOffsetEvalType visitSelectInst(SelectInst &I);
346  SizeOffsetEvalType visitInstruction(Instruction &I);
347 };
348 
349 } // end namespace llvm
350 
351 #endif // LLVM_ANALYSIS_MEMORYBUILTINS_H
bool getObjectSize(const Value *Ptr, uint64_t &Size, const DataLayout &DL, const TargetLibraryInfo *TLI, ObjectSizeOpts Opts={})
Compute the size of the object pointed by Ptr.
bool isAllocationFn(const Value *V, const TargetLibraryInfo *TLI, bool LookThroughBitCast=false)
Tests if a value is a call or invoke to a library function that allocates or reallocates memory (eith...
A parsed version of the target data layout string in and methods for querying it. ...
Definition: DataLayout.h:111
bool isAlignedAllocLikeFn(const Value *V, const TargetLibraryInfo *TLI, bool LookThroughBitCast=false)
Tests if a value is a call or invoke to a library function that allocates uninitialized memory with a...
This instruction extracts a struct member or array element value from an aggregate value...
This class represents an incoming formal argument to a Function.
Definition: Argument.h:29
LLVMContext & Context
Base class for instruction visitors.
Definition: InstVisitor.h:79
This class represents lattice values for constants.
Definition: AllocatorList.h:23
static SizeOffsetEvalType unknown()
const CallInst * extractCallocCall(const Value *I, const TargetLibraryInfo *TLI)
extractCallocCall - Returns the corresponding CallInst if the instruction is a calloc call...
std::pair< Value *, Value * > SizeOffsetEvalType
static bool knownSize(const SizeOffsetType &SizeOffset)
bool NullIsUnknownSize
If this is true, null pointers in address space 0 will be treated as though they can&#39;t be evaluated...
This class represents a function call, abstracting a target machine&#39;s calling convention.
An efficient, type-erasing, non-owning reference to a callable.
Definition: STLExtras.h:176
bool RoundToAlign
Whether to round the result up to the alignment of allocas, byval arguments, and global variables...
Base class for all callable instructions (InvokeInst and CallInst) Holds everything related to callin...
Definition: InstrTypes.h:1100
F(f)
bool isLibFreeFunction(const Function *F, const LibFunc TLIFn)
isLibFreeFunction - Returns true if the function is a builtin free()
An instruction for reading from memory.
Definition: Instructions.h:173
bool isReallocLikeFn(const Value *V, const TargetLibraryInfo *TLI, bool LookThroughBitCast=false)
Tests if a value is a call or invoke to a library function that reallocates memory (e...
Hexagon Common GEP
const CallInst * isFreeCall(const Value *I, const TargetLibraryInfo *TLI)
isFreeCall - Returns non-null if the value is a call to the builtin free()
This class represents the LLVM &#39;select&#39; instruction.
const CallInst * extractMallocCall(const Value *I, function_ref< const TargetLibraryInfo &(Function &)> GetTLI)
extractMallocCall - Returns the corresponding CallInst if the instruction is a malloc call...
&#39;undef&#39; values are things that do not have specified contents.
Definition: Constants.h:1309
bool knownSize(SizeOffsetEvalType SizeOffset)
This file implements a class to represent arbitrary precision integral constant values and operations...
Value * lowerObjectSizeCall(IntrinsicInst *ObjectSize, const DataLayout &DL, const TargetLibraryInfo *TLI, bool MustSucceed)
Try to turn a call to @llvm.objectsize into an integer value of the given Type.
bool isNoAliasFn(const Value *V, const TargetLibraryInfo *TLI, bool LookThroughBitCast=false)
Tests if a value is a call or invoke to a function that returns a NoAlias pointer (including malloc/c...
Same as Min, except we pick the maximum size of all of the branches.
Evaluate all branches of an unknown condition.
Evaluate the size and offset of an object pointed to by a Value*.
bool isOpNewLikeFn(const Value *V, const TargetLibraryInfo *TLI, bool LookThroughBitCast=false)
Tests if a value is a call or invoke to a library function that allocates memory and throws if an all...
Class to represent pointers.
Definition: DerivedTypes.h:662
Value * getMallocArraySize(CallInst *CI, const DataLayout &DL, const TargetLibraryInfo *TLI, bool LookThroughSExt=false)
getMallocArraySize - Returns the array size of a malloc call.
The instances of the Type class are immutable: once they are created, they are never changed...
Definition: Type.h:46
This is an important class for using LLVM in a threaded context.
Definition: LLVMContext.h:68
Class to represent integer types.
Definition: DerivedTypes.h:40
This class represents a cast from an integer to a pointer.
assume Assume Builder
std::pair< APInt, APInt > SizeOffsetType
PointerType * getMallocType(const CallInst *CI, const TargetLibraryInfo *TLI)
getMallocType - Returns the PointerType resulting from the malloc call.
This struct is a compact representation of a valid (non-zero power of two) alignment.
Definition: Alignment.h:39
Mode EvalMode
How we want to evaluate this object&#39;s size.
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements...
Definition: SmallPtrSet.h:439
Evaluate the size and offset of an object pointed to by a Value* statically.
static bool knownOffset(const SizeOffsetType &SizeOffset)
Provides information about what library functions are available for the current target.
A constant pointer value that points to null.
Definition: Constants.h:548
Class for arbitrary precision integers.
Definition: APInt.h:69
Type * getMallocAllocatedType(const CallInst *CI, const TargetLibraryInfo *TLI)
getMallocAllocatedType - Returns the Type allocated by malloc call.
bool isMallocLikeFn(const Value *V, const TargetLibraryInfo *TLI, bool LookThroughBitCast=false)
Tests if a value is a call or invoke to a library function that allocates uninitialized memory (such ...
Fail to evaluate an unknown condition.
bool isMallocOrCallocLikeFn(const Value *V, const TargetLibraryInfo *TLI, bool LookThroughBitCast=false)
Tests if a value is a call or invoke to a library function that allocates memory similar to malloc or...
bool isCallocLikeFn(const Value *V, const TargetLibraryInfo *TLI, bool LookThroughBitCast=false)
Tests if a value is a call or invoke to a library function that allocates zero-filled memory (such as...
#define I(x, y, z)
Definition: MD5.cpp:59
bool isAllocLikeFn(const Value *V, const TargetLibraryInfo *TLI, bool LookThroughBitCast=false)
Tests if a value is a call or invoke to a library function that allocates memory (either malloc...
This instruction extracts a single (scalar) element from a VectorType value.
uint32_t Size
Definition: Profile.cpp:46
bool knownOffset(SizeOffsetEvalType SizeOffset)
bool anyKnown(SizeOffsetEvalType SizeOffset)
static bool bothKnown(const SizeOffsetType &SizeOffset)
LLVM Value Representation.
Definition: Value.h:74
Mode
Controls how we handle conditional statements with unknown conditions.
Various options to control the behavior of getObjectSize.
bool isStrdupLikeFn(const Value *V, const TargetLibraryInfo *TLI, bool LookThroughBitCast=false)
Tests if a value is a call or invoke to a library function that allocates memory (strdup, strndup).
bool bothKnown(SizeOffsetEvalType SizeOffset)
A wrapper class for inspecting calls to intrinsic functions.
Definition: IntrinsicInst.h:44
an instruction to allocate memory on the stack
Definition: Instructions.h:60
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL