LLVM 17.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"
22#include "llvm/IR/IRBuilder.h"
23#include "llvm/IR/InstVisitor.h"
24#include "llvm/IR/ValueHandle.h"
25#include <cstdint>
26#include <optional>
27#include <utility>
28
29namespace llvm {
30
31class AllocaInst;
32class AAResults;
33class Argument;
34class ConstantPointerNull;
35class DataLayout;
36class ExtractElementInst;
37class ExtractValueInst;
38class GEPOperator;
39class GlobalAlias;
40class GlobalVariable;
41class Instruction;
42class IntegerType;
43class IntrinsicInst;
44class IntToPtrInst;
45class LLVMContext;
46class LoadInst;
47class PHINode;
48class SelectInst;
49class Type;
50class UndefValue;
51class Value;
52
53/// Tests if a value is a call or invoke to a library function that
54/// allocates or reallocates memory (either malloc, calloc, realloc, or strdup
55/// like).
56bool isAllocationFn(const Value *V, const TargetLibraryInfo *TLI);
57bool isAllocationFn(const Value *V,
58 function_ref<const TargetLibraryInfo &(Function &)> GetTLI);
59
60/// Tests if a value is a call or invoke to a library function that
61/// allocates memory via new.
62bool isNewLikeFn(const Value *V, const TargetLibraryInfo *TLI);
63
64/// Tests if a value is a call or invoke to a library function that
65/// allocates memory similar to malloc or calloc.
66bool isMallocOrCallocLikeFn(const Value *V, const TargetLibraryInfo *TLI);
67
68/// Tests if a value is a call or invoke to a library function that
69/// allocates memory (either malloc, calloc, or strdup like).
70bool isAllocLikeFn(const Value *V, const TargetLibraryInfo *TLI);
71
72/// Tests if a function is a call or invoke to a library function that
73/// reallocates memory (e.g., realloc).
74bool isReallocLikeFn(const Function *F);
75
76/// If this is a call to a realloc function, return the reallocated operand.
77Value *getReallocatedOperand(const CallBase *CB);
78
79//===----------------------------------------------------------------------===//
80// free Call Utility Functions.
81//
82
83/// isLibFreeFunction - Returns true if the function is a builtin free()
84bool isLibFreeFunction(const Function *F, const LibFunc TLIFn);
85
86/// If this if a call to a free function, return the freed operand.
87Value *getFreedOperand(const CallBase *CB, const TargetLibraryInfo *TLI);
88
89//===----------------------------------------------------------------------===//
90// Properties of allocation functions
91//
92
93/// Return true if this is a call to an allocation function that does not have
94/// side effects that we are required to preserve beyond the effect of
95/// allocating a new object.
96/// Ex: If our allocation routine has a counter for the number of objects
97/// allocated, and the program prints it on exit, can the value change due
98/// to optimization? Answer is highly language dependent.
99/// Note: *Removable* really does mean removable; it does not mean observable.
100/// A language (e.g. C++) can allow removing allocations without allowing
101/// insertion or speculative execution of allocation routines.
102bool isRemovableAlloc(const CallBase *V, const TargetLibraryInfo *TLI);
103
104/// Gets the alignment argument for an aligned_alloc-like function, using either
105/// built-in knowledge based on fuction names/signatures or allocalign
106/// attributes. Note: the Value returned may not indicate a valid alignment, per
107/// the definition of the allocalign attribute.
108Value *getAllocAlignment(const CallBase *V, const TargetLibraryInfo *TLI);
109
110/// Return the size of the requested allocation. With a trivial mapper, this is
111/// similar to calling getObjectSize(..., Exact), but without looking through
112/// calls that return their argument. A mapper function can be used to replace
113/// one Value* (operand to the allocation) with another. This is useful when
114/// doing abstract interpretation.
115std::optional<APInt> getAllocSize(
116 const CallBase *CB, const TargetLibraryInfo *TLI,
117 function_ref<const Value *(const Value *)> Mapper = [](const Value *V) {
118 return V;
119 });
120
121/// If this is a call to an allocation function that initializes memory to a
122/// fixed value, return said value in the requested type. Otherwise, return
123/// nullptr.
125 const TargetLibraryInfo *TLI,
126 Type *Ty);
127
128/// If a function is part of an allocation family (e.g.
129/// malloc/realloc/calloc/free), return the identifier for its family
130/// of functions.
131std::optional<StringRef> getAllocationFamily(const Value *I,
132 const TargetLibraryInfo *TLI);
133
134//===----------------------------------------------------------------------===//
135// Utility functions to compute size of objects.
136//
137
138/// Various options to control the behavior of getObjectSize.
140 /// Controls how we handle conditional statements with unknown conditions.
141 enum class Mode : uint8_t {
142 /// All branches must be known and have the same size, starting from the
143 /// offset, to be merged.
145 /// All branches must be known and have the same underlying size and offset
146 /// to be merged.
148 /// Evaluate all branches of an unknown condition. If all evaluations
149 /// succeed, pick the minimum size.
150 Min,
151 /// Same as Min, except we pick the maximum size of all of the branches.
152 Max,
153 };
154
155 /// How we want to evaluate this object's size.
157 /// Whether to round the result up to the alignment of allocas, byval
158 /// arguments, and global variables.
159 bool RoundToAlign = false;
160 /// If this is true, null pointers in address space 0 will be treated as
161 /// though they can't be evaluated. Otherwise, null is always considered to
162 /// point to a 0 byte region of memory.
163 bool NullIsUnknownSize = false;
164 /// If set, used for more accurate evaluation
165 AAResults *AA = nullptr;
166};
167
168/// Compute the size of the object pointed by Ptr. Returns true and the
169/// object size in Size if successful, and false otherwise. In this context, by
170/// object we mean the region of memory starting at Ptr to the end of the
171/// underlying object pointed to by Ptr.
172///
173/// WARNING: The object size returned is the allocation size. This does not
174/// imply dereferenceability at site of use since the object may be freeed in
175/// between.
176bool 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.
183Value *lowerObjectSizeCall(IntrinsicInst *ObjectSize, const DataLayout &DL,
184 const TargetLibraryInfo *TLI, bool MustSucceed);
185Value *lowerObjectSizeCall(IntrinsicInst *ObjectSize, const DataLayout &DL,
186 const TargetLibraryInfo *TLI, AAResults *AA,
187 bool MustSucceed);
188
189using SizeOffsetType = std::pair<APInt, APInt>;
190
191/// Evaluate the size and offset of an object pointed to by a Value*
192/// statically. Fails if size or offset are not known at compile time.
194 : public InstVisitor<ObjectSizeOffsetVisitor, SizeOffsetType> {
195 const DataLayout &DL;
196 const TargetLibraryInfo *TLI;
197 ObjectSizeOpts Options;
198 unsigned IntTyBits;
199 APInt Zero;
201
203
204 SizeOffsetType unknown() {
205 return std::make_pair(APInt(), APInt());
206 }
207
208public:
211
213
214 static bool knownSize(const SizeOffsetType &SizeOffset) {
215 return SizeOffset.first.getBitWidth() > 1;
216 }
217
218 static bool knownOffset(const SizeOffsetType &SizeOffset) {
219 return SizeOffset.second.getBitWidth() > 1;
220 }
221
222 static bool bothKnown(const SizeOffsetType &SizeOffset) {
223 return knownSize(SizeOffset) && knownOffset(SizeOffset);
224 }
225
226 // These are "private", except they can't actually be made private. Only
227 // compute() should be used by external users.
242
243private:
244 SizeOffsetType findLoadSizeOffset(
247 unsigned &ScannedInstCount);
249 SizeOffsetType computeImpl(Value *V);
250 bool CheckedZextOrTrunc(APInt &I);
251};
252
253using SizeOffsetEvalType = std::pair<Value *, Value *>;
254
255/// Evaluate the size and offset of an object pointed to by a Value*.
256/// May create code to compute the result at run-time.
258 : public InstVisitor<ObjectSizeOffsetEvaluator, SizeOffsetEvalType> {
260 using WeakEvalType = std::pair<WeakTrackingVH, WeakTrackingVH>;
263
264 const DataLayout &DL;
265 const TargetLibraryInfo *TLI;
266 LLVMContext &Context;
267 BuilderTy Builder;
268 IntegerType *IntTy;
269 Value *Zero;
270 CacheMapTy CacheMap;
271 PtrSetTy SeenVals;
272 ObjectSizeOpts EvalOpts;
273 SmallPtrSet<Instruction *, 8> InsertedInstructions;
274
275 SizeOffsetEvalType compute_(Value *V);
276
277public:
279 return std::make_pair(nullptr, nullptr);
280 }
281
283 LLVMContext &Context, ObjectSizeOpts EvalOpts = {});
284
285 SizeOffsetEvalType compute(Value *V);
286
287 bool knownSize(SizeOffsetEvalType SizeOffset) {
288 return SizeOffset.first;
289 }
290
292 return SizeOffset.second;
293 }
294
295 bool anyKnown(SizeOffsetEvalType SizeOffset) {
296 return knownSize(SizeOffset) || knownOffset(SizeOffset);
297 }
298
299 bool bothKnown(SizeOffsetEvalType SizeOffset) {
300 return knownSize(SizeOffset) && knownOffset(SizeOffset);
301 }
302
303 // The individual instruction visitors should be treated as private.
314};
315
316} // end namespace llvm
317
318#endif // LLVM_ANALYSIS_MEMORYBUILTINS_H
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL
Rewrite undef for PHI
This file implements a class to represent arbitrary precision integral constant values and operations...
BlockVerifier::State From
static GCRegistry::Add< ErlangGC > A("erlang", "erlang-compatible garbage collector")
RelocType Type
Definition: COFFYAML.cpp:390
This file defines the DenseMap class.
uint64_t Size
Hexagon Common GEP
#define F(x, y, z)
Definition: MD5.cpp:55
#define I(x, y, z)
Definition: MD5.cpp:58
LLVMContext & Context
const char LLVMTargetMachineRef LLVMPassBuilderOptionsRef Options
This file defines the SmallPtrSet class.
Value * RHS
Value * LHS
Class for arbitrary precision integers.
Definition: APInt.h:75
an instruction to allocate memory on the stack
Definition: Instructions.h:58
This class represents an incoming formal argument to a Function.
Definition: Argument.h:28
LLVM Basic Block Representation.
Definition: BasicBlock.h:56
InstListType::iterator iterator
Instruction iterators...
Definition: BasicBlock.h:87
Base class for all callable instructions (InvokeInst and CallInst) Holds everything related to callin...
Definition: InstrTypes.h:1186
A constant pointer value that points to null.
Definition: Constants.h:538
A parsed version of the target data layout string in and methods for querying it.
Definition: DataLayout.h:110
This instruction extracts a single (scalar) element from a VectorType value.
This instruction extracts a struct member or array element value from an aggregate value.
Base class for instruction visitors.
Definition: InstVisitor.h:78
This class represents a cast from an integer to a pointer.
Class to represent integer types.
Definition: DerivedTypes.h:40
This is an important class for using LLVM in a threaded context.
Definition: LLVMContext.h:67
An instruction for reading from memory.
Definition: Instructions.h:177
Evaluate the size and offset of an object pointed to by a Value*.
SizeOffsetEvalType visitExtractValueInst(ExtractValueInst &I)
SizeOffsetEvalType visitExtractElementInst(ExtractElementInst &I)
bool knownOffset(SizeOffsetEvalType SizeOffset)
SizeOffsetEvalType visitPHINode(PHINode &PHI)
SizeOffsetEvalType visitSelectInst(SelectInst &I)
static SizeOffsetEvalType unknown()
SizeOffsetEvalType compute(Value *V)
bool anyKnown(SizeOffsetEvalType SizeOffset)
bool knownSize(SizeOffsetEvalType SizeOffset)
SizeOffsetEvalType visitCallBase(CallBase &CB)
SizeOffsetEvalType visitInstruction(Instruction &I)
SizeOffsetEvalType visitAllocaInst(AllocaInst &I)
bool bothKnown(SizeOffsetEvalType SizeOffset)
SizeOffsetEvalType visitIntToPtrInst(IntToPtrInst &)
SizeOffsetEvalType visitLoadInst(LoadInst &I)
SizeOffsetEvalType visitGEPOperator(GEPOperator &GEP)
Evaluate the size and offset of an object pointed to by a Value* statically.
SizeOffsetType visitAllocaInst(AllocaInst &I)
SizeOffsetType visitArgument(Argument &A)
SizeOffsetType visitGlobalVariable(GlobalVariable &GV)
SizeOffsetType visitSelectInst(SelectInst &I)
SizeOffsetType visitCallBase(CallBase &CB)
SizeOffsetType visitExtractValueInst(ExtractValueInst &I)
SizeOffsetType visitConstantPointerNull(ConstantPointerNull &)
SizeOffsetType visitExtractElementInst(ExtractElementInst &I)
static bool bothKnown(const SizeOffsetType &SizeOffset)
SizeOffsetType visitUndefValue(UndefValue &)
SizeOffsetType visitGlobalAlias(GlobalAlias &GA)
SizeOffsetType visitIntToPtrInst(IntToPtrInst &)
static bool knownSize(const SizeOffsetType &SizeOffset)
SizeOffsetType visitLoadInst(LoadInst &I)
static bool knownOffset(const SizeOffsetType &SizeOffset)
SizeOffsetType visitInstruction(Instruction &I)
SizeOffsetType compute(Value *V)
SizeOffsetType visitPHINode(PHINode &)
This class represents the LLVM 'select' instruction.
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
Definition: SmallPtrSet.h:450
Provides information about what library functions are available for the current target.
'undef' values are things that do not have specified contents.
Definition: Constants.h:1375
LLVM Value Representation.
Definition: Value.h:74
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
Constant * getInitialValueOfAllocation(const Value *V, const TargetLibraryInfo *TLI, Type *Ty)
If this is a call to an allocation function that initializes memory to a fixed value,...
std::pair< APInt, APInt > SizeOffsetType
bool isRemovableAlloc(const CallBase *V, const TargetLibraryInfo *TLI)
Return true if this is a call to an allocation function that does not have side effects that we are r...
std::optional< StringRef > getAllocationFamily(const Value *I, const TargetLibraryInfo *TLI)
If a function is part of an allocation family (e.g.
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.
Value * getAllocAlignment(const CallBase *V, const TargetLibraryInfo *TLI)
Gets the alignment argument for an aligned_alloc-like function, using either built-in knowledge based...
std::pair< Value *, Value * > SizeOffsetEvalType
bool isLibFreeFunction(const Function *F, const LibFunc TLIFn)
isLibFreeFunction - Returns true if the function is a builtin free()
Value * getReallocatedOperand(const CallBase *CB)
If this is a call to a realloc function, return the reallocated operand.
bool isAllocLikeFn(const Value *V, const TargetLibraryInfo *TLI)
Tests if a value is a call or invoke to a library function that allocates memory (either malloc,...
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 isMallocOrCallocLikeFn(const Value *V, const TargetLibraryInfo *TLI)
Tests if a value is a call or invoke to a library function that allocates memory similar to malloc or...
bool isReallocLikeFn(const Function *F)
Tests if a function is a call or invoke to a library function that reallocates memory (e....
Value * getFreedOperand(const CallBase *CB, const TargetLibraryInfo *TLI)
If this if a call to a free function, return the freed operand.
bool isAllocationFn(const Value *V, const TargetLibraryInfo *TLI)
Tests if a value is a call or invoke to a library function that allocates or reallocates memory (eith...
std::optional< APInt > getAllocSize(const CallBase *CB, const TargetLibraryInfo *TLI, function_ref< const Value *(const Value *)> Mapper=[](const Value *V) { return V;})
Return the size of the requested allocation.
bool isNewLikeFn(const Value *V, const TargetLibraryInfo *TLI)
Tests if a value is a call or invoke to a library function that allocates memory via new.
This struct is a compact representation of a valid (non-zero power of two) alignment.
Definition: Alignment.h:39
This struct is a compact representation of a valid (power of two) or undefined (0) alignment.
Definition: Alignment.h:117
Various options to control the behavior of getObjectSize.
bool NullIsUnknownSize
If this is true, null pointers in address space 0 will be treated as though they can't be evaluated.
Mode EvalMode
How we want to evaluate this object's size.
AAResults * AA
If set, used for more accurate evaluation.
bool RoundToAlign
Whether to round the result up to the alignment of allocas, byval arguments, and global variables.
Mode
Controls how we handle conditional statements with unknown conditions.
@ ExactUnderlyingSizeAndOffset
All branches must be known and have the same underlying size and offset to be merged.
@ Max
Same as Min, except we pick the maximum size of all of the branches.
@ Min
Evaluate all branches of an unknown condition.
@ ExactSizeFromOffset
All branches must be known and have the same size, starting from the offset, to be merged.