LLVM  10.0.0svn
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/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 *
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.
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);
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.
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.
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.
226  : public InstVisitor<ObjectSizeOffsetVisitor, SizeOffsetType> {
227  const DataLayout &DL;
228  const TargetLibraryInfo *TLI;
229  ObjectSizeOpts Options;
230  unsigned IntTyBits;
231  APInt Zero;
233 
234  APInt align(APInt Size, uint64_t Align);
235 
236  SizeOffsetType unknown() {
237  return std::make_pair(APInt(), APInt());
238  }
239 
240 public:
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.
285  : public InstVisitor<ObjectSizeOffsetEvaluator, SizeOffsetEvalType> {
287  using WeakEvalType = std::pair<WeakTrackingVH, WeakTrackingVH>;
290 
291  const DataLayout &DL;
292  const TargetLibraryInfo *TLI;
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:
306  return std::make_pair(nullptr, nullptr);
307  }
308 
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
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
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:80
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:104
bool RoundToAlign
Whether to round the result up to the alignment of allocas, byval arguments, and global variables...
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:169
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:1285
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:579
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:64
Class to represent integer types.
Definition: DerivedTypes.h:40
This class represents a cast from an integer to a pointer.
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:40
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:417
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:538
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:58
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:43
an instruction to allocate memory on the stack
Definition: Instructions.h:59