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"
20#include "llvm/Analysis/TargetFolder.h"
21#include "llvm/Analysis/TargetLibraryInfo.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.
124Constant *getInitialValueOfAllocation(const Value *V,
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.
139struct ObjectSizeOpts {
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.
144 ExactSizeFromOffset,
145 /// All branches must be known and have the same underlying size and offset
146 /// to be merged.
147 ExactUnderlyingSizeAndOffset,
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.
156 Mode EvalMode = Mode::ExactSizeFromOffset;
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(
186 IntrinsicInst *ObjectSize, const DataLayout &DL,
187 const TargetLibraryInfo *TLI, AAResults *AA, bool MustSucceed,
188 SmallVectorImpl<Instruction *> *InsertedInstructions = nullptr);
189
190/// SizeOffsetType - A base template class for the object size visitors. Used
191/// here as a self-documenting way to handle the values rather than using a
192/// \p std::pair.
193template <typename T, class C> struct SizeOffsetType {
194public:
195 T Size;
196 T Offset;
197
198 SizeOffsetType() = default;
199 SizeOffsetType(T Size, T Offset) : Size(Size), Offset(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
206 bool operator==(const SizeOffsetType<T, C> &RHS) const {
207 return Size == RHS.Size && Offset == RHS.Offset;
208 }
209 bool operator!=(const SizeOffsetType<T, C> &RHS) const {
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;
218 SizeOffsetAPInt(APInt Size, APInt Offset) : SizeOffsetType(Size, Offset) {}
219
220 static bool known(APInt V) { return V.getBitWidth() > 1; }
221};
222
223/// Evaluate the size and offset of an object pointed to by a Value*
224/// statically. Fails if size or offset are not known at compile time.
225class ObjectSizeOffsetVisitor
226 : public InstVisitor<ObjectSizeOffsetVisitor, SizeOffsetAPInt> {
227 const DataLayout &DL;
228 const TargetLibraryInfo *TLI;
229 ObjectSizeOpts Options;
230 unsigned IntTyBits;
231 APInt Zero;
232 SmallDenseMap<Instruction *, SizeOffsetAPInt, 8> SeenInsts;
233 unsigned InstructionsVisited;
234
235 APInt align(APInt Size, MaybeAlign Align);
236
237 static SizeOffsetAPInt unknown() { return SizeOffsetAPInt(); }
238
239public:
240 ObjectSizeOffsetVisitor(const DataLayout &DL, const TargetLibraryInfo *TLI,
241 LLVMContext &Context, ObjectSizeOpts Options = {});
242
243 SizeOffsetAPInt compute(Value *V);
244
245 // These are "private", except they can't actually be made private. Only
246 // compute() should be used by external users.
247 SizeOffsetAPInt visitAllocaInst(AllocaInst &I);
248 SizeOffsetAPInt visitArgument(Argument &A);
249 SizeOffsetAPInt visitCallBase(CallBase &CB);
250 SizeOffsetAPInt visitConstantPointerNull(ConstantPointerNull &);
251 SizeOffsetAPInt visitExtractElementInst(ExtractElementInst &I);
252 SizeOffsetAPInt visitExtractValueInst(ExtractValueInst &I);
253 SizeOffsetAPInt visitGlobalAlias(GlobalAlias &GA);
254 SizeOffsetAPInt visitGlobalVariable(GlobalVariable &GV);
255 SizeOffsetAPInt visitIntToPtrInst(IntToPtrInst &);
256 SizeOffsetAPInt visitLoadInst(LoadInst &I);
257 SizeOffsetAPInt visitPHINode(PHINode &);
258 SizeOffsetAPInt visitSelectInst(SelectInst &I);
259 SizeOffsetAPInt visitUndefValue(UndefValue &);
260 SizeOffsetAPInt visitInstruction(Instruction &I);
261
262private:
263 SizeOffsetAPInt findLoadSizeOffset(
264 LoadInst &LoadFrom, BasicBlock &BB, BasicBlock::iterator From,
265 SmallDenseMap<BasicBlock *, SizeOffsetAPInt, 8> &VisitedBlocks,
266 unsigned &ScannedInstCount);
267 SizeOffsetAPInt combineSizeOffset(SizeOffsetAPInt LHS, SizeOffsetAPInt RHS);
268 SizeOffsetAPInt computeImpl(Value *V);
269 SizeOffsetAPInt computeValue(Value *V);
270 bool CheckedZextOrTrunc(APInt &I);
271};
272
273/// SizeOffsetValue - Used by \p ObjectSizeOffsetEvaluator, which works with
274/// \p Values.
275struct SizeOffsetWeakTrackingVH;
276struct SizeOffsetValue : public SizeOffsetType<Value *, SizeOffsetValue> {
277 SizeOffsetValue() : SizeOffsetType(nullptr, nullptr) {}
278 SizeOffsetValue(Value *Size, Value *Offset) : SizeOffsetType(Size, Offset) {}
279 SizeOffsetValue(const SizeOffsetWeakTrackingVH &SOT);
280
281 static bool known(Value *V) { return V != nullptr; }
282};
283
284/// SizeOffsetWeakTrackingVH - Used by \p ObjectSizeOffsetEvaluator in a
285/// \p DenseMap.
286struct SizeOffsetWeakTrackingVH
287 : public SizeOffsetType<WeakTrackingVH, SizeOffsetWeakTrackingVH> {
288 SizeOffsetWeakTrackingVH() : SizeOffsetType(nullptr, nullptr) {}
289 SizeOffsetWeakTrackingVH(Value *Size, Value *Offset)
290 : SizeOffsetType(Size, Offset) {}
291 SizeOffsetWeakTrackingVH(const SizeOffsetValue &SOV)
292 : SizeOffsetType(SOV.Size, SOV.Offset) {}
293
294 static bool known(WeakTrackingVH V) { return V.pointsToAliveValue(); }
295};
296
297/// Evaluate the size and offset of an object pointed to by a Value*.
298/// May create code to compute the result at run-time.
299class ObjectSizeOffsetEvaluator
300 : public InstVisitor<ObjectSizeOffsetEvaluator, SizeOffsetValue> {
301 using BuilderTy = IRBuilder<TargetFolder, IRBuilderCallbackInserter>;
302 using WeakEvalType = SizeOffsetWeakTrackingVH;
303 using CacheMapTy = DenseMap<const Value *, WeakEvalType>;
304 using PtrSetTy = SmallPtrSet<const Value *, 8>;
305
306 const DataLayout &DL;
307 const TargetLibraryInfo *TLI;
308 LLVMContext &Context;
309 BuilderTy Builder;
310 IntegerType *IntTy;
311 Value *Zero;
312 CacheMapTy CacheMap;
313 PtrSetTy SeenVals;
314 ObjectSizeOpts EvalOpts;
315 SmallPtrSet<Instruction *, 8> InsertedInstructions;
316
317 SizeOffsetValue compute_(Value *V);
318
319public:
320 ObjectSizeOffsetEvaluator(const DataLayout &DL, const TargetLibraryInfo *TLI,
321 LLVMContext &Context, ObjectSizeOpts EvalOpts = {});
322
323 static SizeOffsetValue unknown() { return SizeOffsetValue(); }
324
325 SizeOffsetValue compute(Value *V);
326
327 // The individual instruction visitors should be treated as private.
328 SizeOffsetValue visitAllocaInst(AllocaInst &I);
329 SizeOffsetValue visitCallBase(CallBase &CB);
330 SizeOffsetValue visitExtractElementInst(ExtractElementInst &I);
331 SizeOffsetValue visitExtractValueInst(ExtractValueInst &I);
332 SizeOffsetValue visitGEPOperator(GEPOperator &GEP);
333 SizeOffsetValue visitIntToPtrInst(IntToPtrInst &);
334 SizeOffsetValue visitLoadInst(LoadInst &I);
335 SizeOffsetValue visitPHINode(PHINode &PHI);
336 SizeOffsetValue visitSelectInst(SelectInst &I);
337 SizeOffsetValue visitInstruction(Instruction &I);
338};
339
340} // end namespace llvm
341
342#endif // LLVM_ANALYSIS_MEMORYBUILTINS_H
343

source code of llvm/include/llvm/Analysis/MemoryBuiltins.h