LLVM 20.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"
21#include "llvm/IR/IRBuilder.h"
22#include "llvm/IR/InstVisitor.h"
23#include "llvm/IR/ValueHandle.h"
24#include <cstdint>
25#include <optional>
26#include <utility>
27
28namespace llvm {
29
30class AllocaInst;
31class AAResults;
32class Argument;
33class ConstantPointerNull;
34class DataLayout;
35class ExtractElementInst;
36class ExtractValueInst;
37class GEPOperator;
38class GlobalAlias;
39class GlobalVariable;
40class Instruction;
41class IntegerType;
42class IntrinsicInst;
43class IntToPtrInst;
44class LLVMContext;
45class LoadInst;
46class PHINode;
47class SelectInst;
48class Type;
49class UndefValue;
50class Value;
51
52/// Tests if a value is a call or invoke to a library function that
53/// allocates or reallocates memory (either malloc, calloc, realloc, or strdup
54/// like).
55bool isAllocationFn(const Value *V, const TargetLibraryInfo *TLI);
56bool isAllocationFn(const Value *V,
57 function_ref<const TargetLibraryInfo &(Function &)> GetTLI);
58
59/// Tests if a value is a call or invoke to a library function that
60/// allocates memory via new.
61bool isNewLikeFn(const Value *V, const TargetLibraryInfo *TLI);
62
63/// Tests if a value is a call or invoke to a library function that
64/// allocates memory similar to malloc or calloc.
65bool isMallocOrCallocLikeFn(const Value *V, const TargetLibraryInfo *TLI);
66
67/// Tests if a value is a call or invoke to a library function that
68/// allocates memory (either malloc, calloc, or strdup like).
69bool isAllocLikeFn(const Value *V, const TargetLibraryInfo *TLI);
70
71/// Tests if a function is a call or invoke to a library function that
72/// reallocates memory (e.g., realloc).
73bool isReallocLikeFn(const Function *F);
74
75/// If this is a call to a realloc function, return the reallocated operand.
76Value *getReallocatedOperand(const CallBase *CB);
77
78//===----------------------------------------------------------------------===//
79// free Call Utility Functions.
80//
81
82/// isLibFreeFunction - Returns true if the function is a builtin free()
83bool isLibFreeFunction(const Function *F, const LibFunc TLIFn);
84
85/// If this if a call to a free function, return the freed operand.
86Value *getFreedOperand(const CallBase *CB, const TargetLibraryInfo *TLI);
87
88//===----------------------------------------------------------------------===//
89// Properties of allocation functions
90//
91
92/// Return true if this is a call to an allocation function that does not have
93/// side effects that we are required to preserve beyond the effect of
94/// allocating a new object.
95/// Ex: If our allocation routine has a counter for the number of objects
96/// allocated, and the program prints it on exit, can the value change due
97/// to optimization? Answer is highly language dependent.
98/// Note: *Removable* really does mean removable; it does not mean observable.
99/// A language (e.g. C++) can allow removing allocations without allowing
100/// insertion or speculative execution of allocation routines.
101bool isRemovableAlloc(const CallBase *V, const TargetLibraryInfo *TLI);
102
103/// Gets the alignment argument for an aligned_alloc-like function, using either
104/// built-in knowledge based on fuction names/signatures or allocalign
105/// attributes. Note: the Value returned may not indicate a valid alignment, per
106/// the definition of the allocalign attribute.
107Value *getAllocAlignment(const CallBase *V, const TargetLibraryInfo *TLI);
108
109/// Return the size of the requested allocation. With a trivial mapper, this is
110/// similar to calling getObjectSize(..., Exact), but without looking through
111/// calls that return their argument. A mapper function can be used to replace
112/// one Value* (operand to the allocation) with another. This is useful when
113/// doing abstract interpretation.
114std::optional<APInt> getAllocSize(
115 const CallBase *CB, const TargetLibraryInfo *TLI,
116 function_ref<const Value *(const Value *)> Mapper = [](const Value *V) {
117 return V;
118 });
119
120/// If this is a call to an allocation function that initializes memory to a
121/// fixed value, return said value in the requested type. Otherwise, return
122/// nullptr.
124 const TargetLibraryInfo *TLI,
125 Type *Ty);
126
127/// If a function is part of an allocation family (e.g.
128/// malloc/realloc/calloc/free), return the identifier for its family
129/// of functions.
130std::optional<StringRef> getAllocationFamily(const Value *I,
131 const TargetLibraryInfo *TLI);
132
133//===----------------------------------------------------------------------===//
134// Utility functions to compute size of objects.
135//
136
137/// Various options to control the behavior of getObjectSize.
139 /// Controls how we handle conditional statements with unknown conditions.
140 enum class Mode : uint8_t {
141 /// All branches must be known and have the same size, starting from the
142 /// offset, to be merged.
144 /// All branches must be known and have the same underlying size and offset
145 /// to be merged.
147 /// Evaluate all branches of an unknown condition. If all evaluations
148 /// succeed, pick the minimum size.
149 Min,
150 /// Same as Min, except we pick the maximum size of all of the branches.
151 Max,
152 };
153
154 /// How we want to evaluate this object's size.
156 /// Whether to round the result up to the alignment of allocas, byval
157 /// arguments, and global variables.
158 bool RoundToAlign = false;
159 /// If this is true, null pointers in address space 0 will be treated as
160 /// though they can't be evaluated. Otherwise, null is always considered to
161 /// point to a 0 byte region of memory.
162 bool NullIsUnknownSize = false;
163 /// If set, used for more accurate evaluation
164 AAResults *AA = nullptr;
165};
166
167/// Compute the size of the object pointed by Ptr. Returns true and the
168/// object size in Size if successful, and false otherwise. In this context, by
169/// object we mean the region of memory starting at Ptr to the end of the
170/// underlying object pointed to by Ptr.
171///
172/// WARNING: The object size returned is the allocation size. This does not
173/// imply dereferenceability at site of use since the object may be freeed in
174/// between.
175bool getObjectSize(const Value *Ptr, uint64_t &Size, const DataLayout &DL,
176 const TargetLibraryInfo *TLI, ObjectSizeOpts Opts = {});
177
178/// Try to turn a call to \@llvm.objectsize into an integer value of the given
179/// Type. Returns null on failure. If MustSucceed is true, this function will
180/// not return null, and may return conservative values governed by the second
181/// argument of the call to objectsize.
182Value *lowerObjectSizeCall(IntrinsicInst *ObjectSize, const DataLayout &DL,
183 const TargetLibraryInfo *TLI, bool MustSucceed);
185 IntrinsicInst *ObjectSize, const DataLayout &DL,
186 const TargetLibraryInfo *TLI, AAResults *AA, bool MustSucceed,
187 SmallVectorImpl<Instruction *> *InsertedInstructions = nullptr);
188
189/// SizeOffsetType - A base template class for the object size visitors. Used
190/// here as a self-documenting way to handle the values rather than using a
191/// \p std::pair.
192template <typename T, class C> struct SizeOffsetType {
193public:
196
197 SizeOffsetType() = default;
199 : Size(std::move(Size)), Offset(std::move(Offset)) {}
200
201 bool knownSize() const { return C::known(Size); }
202 bool knownOffset() const { return C::known(Offset); }
203 bool anyKnown() const { return knownSize() || knownOffset(); }
204 bool bothKnown() const { return knownSize() && knownOffset(); }
205
207 return Size == RHS.Size && Offset == RHS.Offset;
208 }
210 return !(*this == RHS);
211 }
212};
213
214/// SizeOffsetAPInt - Used by \p ObjectSizeOffsetVisitor, which works with
215/// \p APInts.
216struct SizeOffsetAPInt : public SizeOffsetType<APInt, SizeOffsetAPInt> {
217 SizeOffsetAPInt() = default;
220
221 static bool known(const APInt &V) { return V.getBitWidth() > 1; }
222};
223
224/// Evaluate the size and offset of an object pointed to by a Value*
225/// statically. Fails if size or offset are not known at compile time.
227 : public InstVisitor<ObjectSizeOffsetVisitor, SizeOffsetAPInt> {
228 const DataLayout &DL;
229 const TargetLibraryInfo *TLI;
230 ObjectSizeOpts Options;
231 unsigned IntTyBits;
232 APInt Zero;
234 unsigned InstructionsVisited;
235
237
238 static SizeOffsetAPInt unknown() { return SizeOffsetAPInt(); }
239
240public:
242 LLVMContext &Context, ObjectSizeOpts Options = {});
243
245
246 // These are "private", except they can't actually be made private. Only
247 // compute() should be used by external users.
262
263private:
264 SizeOffsetAPInt findLoadSizeOffset(
267 unsigned &ScannedInstCount);
269 SizeOffsetAPInt computeImpl(Value *V);
270 SizeOffsetAPInt computeValue(Value *V);
271 bool CheckedZextOrTrunc(APInt &I);
272};
273
274/// SizeOffsetValue - Used by \p ObjectSizeOffsetEvaluator, which works with
275/// \p Values.
277struct SizeOffsetValue : public SizeOffsetType<Value *, SizeOffsetValue> {
278 SizeOffsetValue() : SizeOffsetType(nullptr, nullptr) {}
281
282 static bool known(Value *V) { return V != nullptr; }
283};
284
285/// SizeOffsetWeakTrackingVH - Used by \p ObjectSizeOffsetEvaluator in a
286/// \p DenseMap.
288 : public SizeOffsetType<WeakTrackingVH, SizeOffsetWeakTrackingVH> {
293 : SizeOffsetType(SOV.Size, SOV.Offset) {}
294
295 static bool known(WeakTrackingVH V) { return V.pointsToAliveValue(); }
296};
297
298/// Evaluate the size and offset of an object pointed to by a Value*.
299/// May create code to compute the result at run-time.
301 : public InstVisitor<ObjectSizeOffsetEvaluator, SizeOffsetValue> {
306
307 const DataLayout &DL;
308 const TargetLibraryInfo *TLI;
309 LLVMContext &Context;
310 BuilderTy Builder;
311 IntegerType *IntTy;
312 Value *Zero;
313 CacheMapTy CacheMap;
314 PtrSetTy SeenVals;
315 ObjectSizeOpts EvalOpts;
316 SmallPtrSet<Instruction *, 8> InsertedInstructions;
317
318 SizeOffsetValue compute_(Value *V);
319
320public:
322 LLVMContext &Context, ObjectSizeOpts EvalOpts = {});
323
325
327
328 // The individual instruction visitors should be treated as private.
339};
340
341} // end namespace llvm
342
343#endif // LLVM_ANALYSIS_MEMORYBUILTINS_H
Rewrite undef for PHI
This file implements a class to represent arbitrary precision integral constant values and operations...
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL
BlockVerifier::State From
static GCRegistry::Add< ErlangGC > A("erlang", "erlang-compatible garbage collector")
RelocType Type
Definition: COFFYAML.cpp:391
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
This file defines the SmallPtrSet class.
Value * RHS
Value * LHS
Class for arbitrary precision integers.
Definition: APInt.h:77
an instruction to allocate memory on the stack
Definition: Instructions.h:61
This class represents an incoming formal argument to a Function.
Definition: Argument.h:31
LLVM Basic Block Representation.
Definition: BasicBlock.h:61
InstListType::iterator iterator
Instruction iterators...
Definition: BasicBlock.h:177
Base class for all callable instructions (InvokeInst and CallInst) Holds everything related to callin...
Definition: InstrTypes.h:1236
A constant pointer value that points to null.
Definition: Constants.h:549
A parsed version of the target data layout string in and methods for querying it.
Definition: DataLayout.h:63
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:174
Evaluate the size and offset of an object pointed to by a Value*.
SizeOffsetValue visitExtractValueInst(ExtractValueInst &I)
SizeOffsetValue visitExtractElementInst(ExtractElementInst &I)
SizeOffsetValue compute(Value *V)
SizeOffsetValue visitInstruction(Instruction &I)
SizeOffsetValue visitLoadInst(LoadInst &I)
SizeOffsetValue visitGEPOperator(GEPOperator &GEP)
SizeOffsetValue visitIntToPtrInst(IntToPtrInst &)
SizeOffsetValue visitPHINode(PHINode &PHI)
SizeOffsetValue visitCallBase(CallBase &CB)
SizeOffsetValue visitSelectInst(SelectInst &I)
SizeOffsetValue visitAllocaInst(AllocaInst &I)
static SizeOffsetValue unknown()
Evaluate the size and offset of an object pointed to by a Value* statically.
SizeOffsetAPInt visitLoadInst(LoadInst &I)
SizeOffsetAPInt visitConstantPointerNull(ConstantPointerNull &)
SizeOffsetAPInt visitCallBase(CallBase &CB)
SizeOffsetAPInt visitInstruction(Instruction &I)
SizeOffsetAPInt visitGlobalAlias(GlobalAlias &GA)
SizeOffsetAPInt visitIntToPtrInst(IntToPtrInst &)
SizeOffsetAPInt visitExtractElementInst(ExtractElementInst &I)
SizeOffsetAPInt compute(Value *V)
SizeOffsetAPInt visitExtractValueInst(ExtractValueInst &I)
SizeOffsetAPInt visitUndefValue(UndefValue &)
SizeOffsetAPInt visitPHINode(PHINode &)
SizeOffsetAPInt visitArgument(Argument &A)
SizeOffsetAPInt visitGlobalVariable(GlobalVariable &GV)
SizeOffsetAPInt visitSelectInst(SelectInst &I)
SizeOffsetAPInt visitAllocaInst(AllocaInst &I)
This class represents the LLVM 'select' instruction.
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:1398
LLVM Value Representation.
Definition: Value.h:74
Value handle that is nullable, but tries to track the Value.
Definition: ValueHandle.h:204
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,...
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...
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.
OutputIt move(R &&Range, OutputIt Out)
Provide wrappers to std::move which take ranges instead of having to pass begin/end explicitly.
Definition: STLExtras.h:1856
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.
Implement std::hash so that hash_code can be used in STL containers.
Definition: BitVector.h:858
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.
SizeOffsetAPInt - Used by ObjectSizeOffsetVisitor, which works with APInts.
static bool known(const APInt &V)
SizeOffsetAPInt(APInt Size, APInt Offset)
SizeOffsetType - A base template class for the object size visitors.
bool operator!=(const SizeOffsetType< T, C > &RHS) const
bool operator==(const SizeOffsetType< T, C > &RHS) const
SizeOffsetType()=default
SizeOffsetType(T Size, T Offset)
bool knownOffset() const
bool knownSize() const
bool bothKnown() const
SizeOffsetValue(Value *Size, Value *Offset)
static bool known(Value *V)
SizeOffsetWeakTrackingVH - Used by ObjectSizeOffsetEvaluator in a DenseMap.
SizeOffsetWeakTrackingVH(const SizeOffsetValue &SOV)
static bool known(WeakTrackingVH V)
SizeOffsetWeakTrackingVH(Value *Size, Value *Offset)