LLVM  8.0.0svn
MemoryBuiltins.h
Go to the documentation of this file.
1 //==- llvm/Analysis/MemoryBuiltins.h - Calls to memory builtins --*- C++ -*-==//
2 //
3 // The LLVM Compiler Infrastructure
4 //
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
7 //
8 //===----------------------------------------------------------------------===//
9 //
10 // This family of functions identifies calls to builtin functions that allocate
11 // or free memory.
12 //
13 //===----------------------------------------------------------------------===//
14 
15 #ifndef LLVM_ANALYSIS_MEMORYBUILTINS_H
16 #define LLVM_ANALYSIS_MEMORYBUILTINS_H
17 
18 #include "llvm/ADT/APInt.h"
19 #include "llvm/ADT/DenseMap.h"
20 #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 //===----------------------------------------------------------------------===//
88 // malloc Call Utility Functions.
89 //
90 
91 /// extractMallocCall - Returns the corresponding CallInst if the instruction
92 /// is a malloc call. Since CallInst::CreateMalloc() only creates calls, we
93 /// ignore InvokeInst here.
94 const CallInst *extractMallocCall(const Value *I, const TargetLibraryInfo *TLI);
96  return const_cast<CallInst*>(extractMallocCall((const Value*)I, TLI));
97 }
98 
99 /// getMallocType - Returns the PointerType resulting from the malloc call.
100 /// The PointerType depends on the number of bitcast uses of the malloc call:
101 /// 0: PointerType is the malloc calls' return type.
102 /// 1: PointerType is the bitcast's result type.
103 /// >1: Unique PointerType cannot be determined, return NULL.
104 PointerType *getMallocType(const CallInst *CI, const TargetLibraryInfo *TLI);
105 
106 /// getMallocAllocatedType - Returns the Type allocated by malloc call.
107 /// The Type depends on the number of bitcast uses of the malloc call:
108 /// 0: PointerType is the malloc calls' return type.
109 /// 1: PointerType is the bitcast's result type.
110 /// >1: Unique PointerType cannot be determined, return NULL.
111 Type *getMallocAllocatedType(const CallInst *CI, const TargetLibraryInfo *TLI);
112 
113 /// getMallocArraySize - Returns the array size of a malloc call. If the
114 /// argument passed to malloc is a multiple of the size of the malloced type,
115 /// then return that multiple. For non-array mallocs, the multiple is
116 /// constant 1. Otherwise, return NULL for mallocs whose array size cannot be
117 /// determined.
119  const TargetLibraryInfo *TLI,
120  bool LookThroughSExt = false);
121 
122 //===----------------------------------------------------------------------===//
123 // calloc Call Utility Functions.
124 //
125 
126 /// extractCallocCall - Returns the corresponding CallInst if the instruction
127 /// is a calloc call.
128 const CallInst *extractCallocCall(const Value *I, const TargetLibraryInfo *TLI);
130  return const_cast<CallInst*>(extractCallocCall((const Value*)I, TLI));
131 }
132 
133 
134 //===----------------------------------------------------------------------===//
135 // free Call Utility Functions.
136 //
137 
138 /// isFreeCall - Returns non-null if the value is a call to the builtin free()
139 const CallInst *isFreeCall(const Value *I, const TargetLibraryInfo *TLI);
140 
141 inline CallInst *isFreeCall(Value *I, const TargetLibraryInfo *TLI) {
142  return const_cast<CallInst*>(isFreeCall((const Value*)I, TLI));
143 }
144 
145 //===----------------------------------------------------------------------===//
146 // Utility functions to compute size of objects.
147 //
148 
149 /// Various options to control the behavior of getObjectSize.
151  /// Controls how we handle conditional statements with unknown conditions.
152  enum class Mode : uint8_t {
153  /// Fail to evaluate an unknown condition.
154  Exact,
155  /// Evaluate all branches of an unknown condition. If all evaluations
156  /// succeed, pick the minimum size.
157  Min,
158  /// Same as Min, except we pick the maximum size of all of the branches.
159  Max
160  };
161 
162  /// How we want to evaluate this object's size.
164  /// Whether to round the result up to the alignment of allocas, byval
165  /// arguments, and global variables.
166  bool RoundToAlign = false;
167  /// If this is true, null pointers in address space 0 will be treated as
168  /// though they can't be evaluated. Otherwise, null is always considered to
169  /// point to a 0 byte region of memory.
170  bool NullIsUnknownSize = false;
171 };
172 
173 /// Compute the size of the object pointed by Ptr. Returns true and the
174 /// object size in Size if successful, and false otherwise. In this context, by
175 /// object we mean the region of memory starting at Ptr to the end of the
176 /// underlying object pointed to by Ptr.
177 bool getObjectSize(const Value *Ptr, uint64_t &Size, const DataLayout &DL,
178  const TargetLibraryInfo *TLI, ObjectSizeOpts Opts = {});
179 
180 /// Try to turn a call to \@llvm.objectsize into an integer value of the given
181 /// Type. Returns null on failure.
182 /// If MustSucceed is true, this function will not return null, and may return
183 /// conservative values governed by the second argument of the call to
184 /// objectsize.
186  const DataLayout &DL,
187  const TargetLibraryInfo *TLI,
188  bool MustSucceed);
189 
190 using SizeOffsetType = std::pair<APInt, APInt>;
191 
192 /// Evaluate the size and offset of an object pointed to by a Value*
193 /// statically. Fails if size or offset are not known at compile time.
195  : public InstVisitor<ObjectSizeOffsetVisitor, SizeOffsetType> {
196  const DataLayout &DL;
197  const TargetLibraryInfo *TLI;
198  ObjectSizeOpts Options;
199  unsigned IntTyBits;
200  APInt Zero;
202 
203  APInt align(APInt Size, uint64_t Align);
204 
205  SizeOffsetType unknown() {
206  return std::make_pair(APInt(), APInt());
207  }
208 
209 public:
211  LLVMContext &Context, ObjectSizeOpts Options = {});
212 
213  SizeOffsetType compute(Value *V);
214 
215  static bool knownSize(const SizeOffsetType &SizeOffset) {
216  return SizeOffset.first.getBitWidth() > 1;
217  }
218 
219  static bool knownOffset(const SizeOffsetType &SizeOffset) {
220  return SizeOffset.second.getBitWidth() > 1;
221  }
222 
223  static bool bothKnown(const SizeOffsetType &SizeOffset) {
224  return knownSize(SizeOffset) && knownOffset(SizeOffset);
225  }
226 
227  // These are "private", except they can't actually be made private. Only
228  // compute() should be used by external users.
229  SizeOffsetType visitAllocaInst(AllocaInst &I);
230  SizeOffsetType visitArgument(Argument &A);
231  SizeOffsetType visitCallSite(CallSite CS);
232  SizeOffsetType visitConstantPointerNull(ConstantPointerNull&);
233  SizeOffsetType visitExtractElementInst(ExtractElementInst &I);
234  SizeOffsetType visitExtractValueInst(ExtractValueInst &I);
235  SizeOffsetType visitGEPOperator(GEPOperator &GEP);
236  SizeOffsetType visitGlobalAlias(GlobalAlias &GA);
237  SizeOffsetType visitGlobalVariable(GlobalVariable &GV);
238  SizeOffsetType visitIntToPtrInst(IntToPtrInst&);
239  SizeOffsetType visitLoadInst(LoadInst &I);
240  SizeOffsetType visitPHINode(PHINode&);
241  SizeOffsetType visitSelectInst(SelectInst &I);
242  SizeOffsetType visitUndefValue(UndefValue&);
243  SizeOffsetType visitInstruction(Instruction &I);
244 
245 private:
246  bool CheckedZextOrTrunc(APInt &I);
247 };
248 
249 using SizeOffsetEvalType = std::pair<Value *, Value *>;
250 
251 /// Evaluate the size and offset of an object pointed to by a Value*.
252 /// May create code to compute the result at run-time.
254  : public InstVisitor<ObjectSizeOffsetEvaluator, SizeOffsetEvalType> {
256  using WeakEvalType = std::pair<WeakTrackingVH, WeakTrackingVH>;
259 
260  const DataLayout &DL;
261  const TargetLibraryInfo *TLI;
263  BuilderTy Builder;
264  IntegerType *IntTy;
265  Value *Zero;
266  CacheMapTy CacheMap;
267  PtrSetTy SeenVals;
268  bool RoundToAlign;
269 
270  SizeOffsetEvalType unknown() {
271  return std::make_pair(nullptr, nullptr);
272  }
273 
274  SizeOffsetEvalType compute_(Value *V);
275 
276 public:
278  LLVMContext &Context, bool RoundToAlign = false);
279 
280  SizeOffsetEvalType compute(Value *V);
281 
282  bool knownSize(SizeOffsetEvalType SizeOffset) {
283  return SizeOffset.first;
284  }
285 
286  bool knownOffset(SizeOffsetEvalType SizeOffset) {
287  return SizeOffset.second;
288  }
289 
290  bool anyKnown(SizeOffsetEvalType SizeOffset) {
291  return knownSize(SizeOffset) || knownOffset(SizeOffset);
292  }
293 
294  bool bothKnown(SizeOffsetEvalType SizeOffset) {
295  return knownSize(SizeOffset) && knownOffset(SizeOffset);
296  }
297 
298  // The individual instruction visitors should be treated as private.
299  SizeOffsetEvalType visitAllocaInst(AllocaInst &I);
300  SizeOffsetEvalType visitCallSite(CallSite CS);
301  SizeOffsetEvalType visitExtractElementInst(ExtractElementInst &I);
302  SizeOffsetEvalType visitExtractValueInst(ExtractValueInst &I);
303  SizeOffsetEvalType visitGEPOperator(GEPOperator &GEP);
304  SizeOffsetEvalType visitIntToPtrInst(IntToPtrInst&);
305  SizeOffsetEvalType visitLoadInst(LoadInst &I);
306  SizeOffsetEvalType visitPHINode(PHINode &PHI);
307  SizeOffsetEvalType visitSelectInst(SelectInst &I);
308  SizeOffsetEvalType visitInstruction(Instruction &I);
309 };
310 
311 } // end namespace llvm
312 
313 #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
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:49
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:30
LLVMContext & Context
Base class for instruction visitors.
Definition: InstVisitor.h:81
This class represents lattice values for constants.
Definition: AllocatorList.h:24
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...
An instruction for reading from memory.
Definition: Instructions.h:168
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:1286
bool knownSize(SizeOffsetEvalType SizeOffset)
This file implements a class to represent arbitrary precision integral constant values and operations...
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:467
Value * getMallocArraySize(CallInst *CI, const DataLayout &DL, const TargetLibraryInfo *TLI, bool LookThroughSExt=false)
getMallocArraySize - Returns the array size of a malloc call.
ConstantInt * 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.
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:69
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:418
This is the shared class of boolean and integer constants.
Definition: Constants.h:84
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:539
Class for arbitrary precision integers.
Definition: APInt.h:70
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:47
bool knownOffset(SizeOffsetEvalType SizeOffset)
bool anyKnown(SizeOffsetEvalType SizeOffset)
static bool bothKnown(const SizeOffsetType &SizeOffset)
LLVM Value Representation.
Definition: Value.h:73
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:44
an instruction to allocate memory on the stack
Definition: Instructions.h:60