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 
62 /// Tests if a value is a call or invoke to a function that returns a
63 /// NoAlias pointer (including malloc/calloc/realloc/strdup-like functions).
64 bool isNoAliasFn(const Value *V, const TargetLibraryInfo *TLI,
65  bool LookThroughBitCast = false);
66 
67 /// Tests if a value is a call or invoke to a library function that
68 /// allocates uninitialized memory (such as malloc).
69 bool isMallocLikeFn(const Value *V, const TargetLibraryInfo *TLI,
70  bool LookThroughBitCast = false);
71 
72 /// Tests if a value is a call or invoke to a library function that
73 /// allocates zero-filled memory (such as calloc).
74 bool isCallocLikeFn(const Value *V, const TargetLibraryInfo *TLI,
75  bool LookThroughBitCast = false);
76 
77 /// Tests if a value is a call or invoke to a library function that
78 /// allocates memory similar to malloc or calloc.
79 bool isMallocOrCallocLikeFn(const Value *V, const TargetLibraryInfo *TLI,
80  bool LookThroughBitCast = false);
81 
82 /// Tests if a value is a call or invoke to a library function that
83 /// allocates memory (either malloc, calloc, or strdup like).
84 bool isAllocLikeFn(const Value *V, const TargetLibraryInfo *TLI,
85  bool LookThroughBitCast = false);
86 
87 /// Tests if a value is a call or invoke to a library function that
88 /// reallocates memory (e.g., realloc).
89 bool isReallocLikeFn(const Value *V, const TargetLibraryInfo *TLI,
90  bool LookThroughBitCast = false);
91 
92 /// Tests if a function is a call or invoke to a library function that
93 /// reallocates memory (e.g., realloc).
94 bool isReallocLikeFn(const Function *F, const TargetLibraryInfo *TLI);
95 
96 //===----------------------------------------------------------------------===//
97 // malloc Call Utility Functions.
98 //
99 
100 /// extractMallocCall - Returns the corresponding CallInst if the instruction
101 /// is a malloc call. Since CallInst::CreateMalloc() only creates calls, we
102 /// ignore InvokeInst here.
103 const CallInst *extractMallocCall(const Value *I, const TargetLibraryInfo *TLI);
105  return const_cast<CallInst*>(extractMallocCall((const Value*)I, TLI));
106 }
107 
108 /// getMallocType - Returns the PointerType resulting from the malloc call.
109 /// The PointerType depends on the number of bitcast uses of the malloc call:
110 /// 0: PointerType is the malloc calls' return type.
111 /// 1: PointerType is the bitcast's result type.
112 /// >1: Unique PointerType cannot be determined, return NULL.
113 PointerType *getMallocType(const CallInst *CI, const TargetLibraryInfo *TLI);
114 
115 /// getMallocAllocatedType - Returns the Type allocated by malloc call.
116 /// The Type depends on the number of bitcast uses of the malloc call:
117 /// 0: PointerType is the malloc calls' return type.
118 /// 1: PointerType is the bitcast's result type.
119 /// >1: Unique PointerType cannot be determined, return NULL.
120 Type *getMallocAllocatedType(const CallInst *CI, const TargetLibraryInfo *TLI);
121 
122 /// getMallocArraySize - Returns the array size of a malloc call. If the
123 /// argument passed to malloc is a multiple of the size of the malloced type,
124 /// then return that multiple. For non-array mallocs, the multiple is
125 /// constant 1. Otherwise, return NULL for mallocs whose array size cannot be
126 /// determined.
128  const TargetLibraryInfo *TLI,
129  bool LookThroughSExt = false);
130 
131 //===----------------------------------------------------------------------===//
132 // calloc Call Utility Functions.
133 //
134 
135 /// extractCallocCall - Returns the corresponding CallInst if the instruction
136 /// is a calloc call.
137 const CallInst *extractCallocCall(const Value *I, const TargetLibraryInfo *TLI);
139  return const_cast<CallInst*>(extractCallocCall((const Value*)I, TLI));
140 }
141 
142 
143 //===----------------------------------------------------------------------===//
144 // free Call Utility Functions.
145 //
146 
147 /// isLibFreeFunction - Returns true if the function is a builtin free()
148 bool isLibFreeFunction(const Function *F, const LibFunc TLIFn);
149 
150 /// isFreeCall - Returns non-null if the value is a call to the builtin free()
151 const CallInst *isFreeCall(const Value *I, const TargetLibraryInfo *TLI);
152 
153 inline CallInst *isFreeCall(Value *I, const TargetLibraryInfo *TLI) {
154  return const_cast<CallInst*>(isFreeCall((const Value*)I, TLI));
155 }
156 
157 //===----------------------------------------------------------------------===//
158 // Utility functions to compute size of objects.
159 //
160 
161 /// Various options to control the behavior of getObjectSize.
163  /// Controls how we handle conditional statements with unknown conditions.
164  enum class Mode : uint8_t {
165  /// Fail to evaluate an unknown condition.
166  Exact,
167  /// Evaluate all branches of an unknown condition. If all evaluations
168  /// succeed, pick the minimum size.
169  Min,
170  /// Same as Min, except we pick the maximum size of all of the branches.
171  Max
172  };
173 
174  /// How we want to evaluate this object's size.
176  /// Whether to round the result up to the alignment of allocas, byval
177  /// arguments, and global variables.
178  bool RoundToAlign = false;
179  /// If this is true, null pointers in address space 0 will be treated as
180  /// though they can't be evaluated. Otherwise, null is always considered to
181  /// point to a 0 byte region of memory.
182  bool NullIsUnknownSize = false;
183 };
184 
185 /// Compute the size of the object pointed by Ptr. Returns true and the
186 /// object size in Size if successful, and false otherwise. In this context, by
187 /// object we mean the region of memory starting at Ptr to the end of the
188 /// underlying object pointed to by Ptr.
189 bool getObjectSize(const Value *Ptr, uint64_t &Size, const DataLayout &DL,
190  const TargetLibraryInfo *TLI, ObjectSizeOpts Opts = {});
191 
192 /// Try to turn a call to \@llvm.objectsize into an integer value of the given
193 /// Type. Returns null on failure. If MustSucceed is true, this function will
194 /// not return null, and may return conservative values governed by the second
195 /// argument of the call to objectsize.
196 Value *lowerObjectSizeCall(IntrinsicInst *ObjectSize, const DataLayout &DL,
197  const TargetLibraryInfo *TLI, bool MustSucceed);
198 
199 
200 
201 using SizeOffsetType = std::pair<APInt, APInt>;
202 
203 /// Evaluate the size and offset of an object pointed to by a Value*
204 /// statically. Fails if size or offset are not known at compile time.
206  : public InstVisitor<ObjectSizeOffsetVisitor, SizeOffsetType> {
207  const DataLayout &DL;
208  const TargetLibraryInfo *TLI;
209  ObjectSizeOpts Options;
210  unsigned IntTyBits;
211  APInt Zero;
213 
214  APInt align(APInt Size, uint64_t Align);
215 
216  SizeOffsetType unknown() {
217  return std::make_pair(APInt(), APInt());
218  }
219 
220 public:
222  LLVMContext &Context, ObjectSizeOpts Options = {});
223 
224  SizeOffsetType compute(Value *V);
225 
226  static bool knownSize(const SizeOffsetType &SizeOffset) {
227  return SizeOffset.first.getBitWidth() > 1;
228  }
229 
230  static bool knownOffset(const SizeOffsetType &SizeOffset) {
231  return SizeOffset.second.getBitWidth() > 1;
232  }
233 
234  static bool bothKnown(const SizeOffsetType &SizeOffset) {
235  return knownSize(SizeOffset) && knownOffset(SizeOffset);
236  }
237 
238  // These are "private", except they can't actually be made private. Only
239  // compute() should be used by external users.
240  SizeOffsetType visitAllocaInst(AllocaInst &I);
241  SizeOffsetType visitArgument(Argument &A);
242  SizeOffsetType visitCallSite(CallSite CS);
243  SizeOffsetType visitConstantPointerNull(ConstantPointerNull&);
244  SizeOffsetType visitExtractElementInst(ExtractElementInst &I);
245  SizeOffsetType visitExtractValueInst(ExtractValueInst &I);
246  SizeOffsetType visitGEPOperator(GEPOperator &GEP);
247  SizeOffsetType visitGlobalAlias(GlobalAlias &GA);
248  SizeOffsetType visitGlobalVariable(GlobalVariable &GV);
249  SizeOffsetType visitIntToPtrInst(IntToPtrInst&);
250  SizeOffsetType visitLoadInst(LoadInst &I);
251  SizeOffsetType visitPHINode(PHINode&);
252  SizeOffsetType visitSelectInst(SelectInst &I);
253  SizeOffsetType visitUndefValue(UndefValue&);
254  SizeOffsetType visitInstruction(Instruction &I);
255 
256 private:
257  bool CheckedZextOrTrunc(APInt &I);
258 };
259 
260 using SizeOffsetEvalType = std::pair<Value *, Value *>;
261 
262 /// Evaluate the size and offset of an object pointed to by a Value*.
263 /// May create code to compute the result at run-time.
265  : public InstVisitor<ObjectSizeOffsetEvaluator, SizeOffsetEvalType> {
267  using WeakEvalType = std::pair<WeakTrackingVH, WeakTrackingVH>;
270 
271  const DataLayout &DL;
272  const TargetLibraryInfo *TLI;
274  BuilderTy Builder;
275  IntegerType *IntTy;
276  Value *Zero;
277  CacheMapTy CacheMap;
278  PtrSetTy SeenVals;
279  ObjectSizeOpts EvalOpts;
280  SmallPtrSet<Instruction *, 8> InsertedInstructions;
281 
282  SizeOffsetEvalType compute_(Value *V);
283 
284 public:
286  return std::make_pair(nullptr, nullptr);
287  }
288 
290  LLVMContext &Context, ObjectSizeOpts EvalOpts = {});
291 
292  SizeOffsetEvalType compute(Value *V);
293 
294  bool knownSize(SizeOffsetEvalType SizeOffset) {
295  return SizeOffset.first;
296  }
297 
298  bool knownOffset(SizeOffsetEvalType SizeOffset) {
299  return SizeOffset.second;
300  }
301 
302  bool anyKnown(SizeOffsetEvalType SizeOffset) {
303  return knownSize(SizeOffset) || knownOffset(SizeOffset);
304  }
305 
306  bool bothKnown(SizeOffsetEvalType SizeOffset) {
307  return knownSize(SizeOffset) && knownOffset(SizeOffset);
308  }
309 
310  // The individual instruction visitors should be treated as private.
311  SizeOffsetEvalType visitAllocaInst(AllocaInst &I);
312  SizeOffsetEvalType visitCallSite(CallSite CS);
313  SizeOffsetEvalType visitExtractElementInst(ExtractElementInst &I);
314  SizeOffsetEvalType visitExtractValueInst(ExtractValueInst &I);
315  SizeOffsetEvalType visitGEPOperator(GEPOperator &GEP);
316  SizeOffsetEvalType visitIntToPtrInst(IntToPtrInst&);
317  SizeOffsetEvalType visitLoadInst(LoadInst &I);
318  SizeOffsetEvalType visitPHINode(PHINode &PHI);
319  SizeOffsetEvalType visitSelectInst(SelectInst &I);
320  SizeOffsetEvalType visitInstruction(Instruction &I);
321 };
322 
323 } // end namespace llvm
324 
325 #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:110
constexpr char Align[]
Key for Kernel::Arg::Metadata::mAlign.
Type
MessagePack types as defined in the standard, with the exception of Integer being divided into a sign...
Definition: MsgPackReader.h:48
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.
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:167
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.
&#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*.
Class to represent pointers.
Definition: DerivedTypes.h:544
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:45
This is an important class for using LLVM in a threaded context.
Definition: LLVMContext.h:64
const CallInst * extractMallocCall(const Value *I, const TargetLibraryInfo *TLI)
extractMallocCall - Returns the corresponding CallInst if the instruction is a malloc call...
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.
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:72
Mode
Controls how we handle conditional statements with unknown conditions.
Various options to control the behavior of getObjectSize.
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