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