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/IR/IRBuilder.h"
22#include "llvm/IR/InstVisitor.h"
23#include "llvm/IR/ValueHandle.h"
24#include "llvm/Support/Compiler.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).
56LLVM_ABI bool isAllocationFn(const Value *V, const TargetLibraryInfo *TLI);
57LLVM_ABI bool
58isAllocationFn(const Value *V,
59 function_ref<const TargetLibraryInfo &(Function &)> GetTLI);
60
61/// Tests if a value is a call or invoke to a library function that
62/// allocates memory via new.
63LLVM_ABI bool isNewLikeFn(const Value *V, const TargetLibraryInfo *TLI);
64
65/// Tests if a value is a call or invoke to a library function that
66/// allocates memory similar to malloc or calloc.
67LLVM_ABI bool isMallocOrCallocLikeFn(const Value *V,
68 const TargetLibraryInfo *TLI);
69
70/// Tests if a value is a call or invoke to a library function that
71/// allocates memory (either malloc, calloc, or strdup like).
72LLVM_ABI bool isAllocLikeFn(const Value *V, const TargetLibraryInfo *TLI);
73
74/// Tests if a function is a call or invoke to a library function that
75/// reallocates memory (e.g., realloc).
76LLVM_ABI bool isReallocLikeFn(const Function *F);
77
78/// If this is a call to a realloc function, return the reallocated operand.
79LLVM_ABI Value *getReallocatedOperand(const CallBase *CB);
80
81//===----------------------------------------------------------------------===//
82// free Call Utility Functions.
83//
84
85/// isLibFreeFunction - Returns true if the function is a builtin free()
86LLVM_ABI bool isLibFreeFunction(const Function *F, const LibFunc TLIFn);
87
88/// If this if a call to a free function, return the freed operand.
89LLVM_ABI Value *getFreedOperand(const CallBase *CB,
90 const TargetLibraryInfo *TLI);
91
92//===----------------------------------------------------------------------===//
93// Properties of allocation functions
94//
95
96/// Return true if this is a call to an allocation function that does not have
97/// side effects that we are required to preserve beyond the effect of
98/// allocating a new object.
99/// Ex: If our allocation routine has a counter for the number of objects
100/// allocated, and the program prints it on exit, can the value change due
101/// to optimization? Answer is highly language dependent.
102/// Note: *Removable* really does mean removable; it does not mean observable.
103/// A language (e.g. C++) can allow removing allocations without allowing
104/// insertion or speculative execution of allocation routines.
105LLVM_ABI bool isRemovableAlloc(const CallBase *V, const TargetLibraryInfo *TLI);
106
107/// Gets the alignment argument for an aligned_alloc-like function, using either
108/// built-in knowledge based on fuction names/signatures or allocalign
109/// attributes. Note: the Value returned may not indicate a valid alignment, per
110/// the definition of the allocalign attribute.
111LLVM_ABI Value *getAllocAlignment(const CallBase *V,
112 const TargetLibraryInfo *TLI);
113
114/// Return the size of the requested allocation. With a trivial mapper, this is
115/// similar to calling getObjectSize(..., Exact), but without looking through
116/// calls that return their argument. A mapper function can be used to replace
117/// one Value* (operand to the allocation) with another. This is useful when
118/// doing abstract interpretation.
119LLVM_ABI std::optional<APInt> getAllocSize(
120 const CallBase *CB, const TargetLibraryInfo *TLI,
121 function_ref<const Value *(const Value *)> Mapper = [](const Value *V) {
122 return V;
123 });
124
125/// If this is a call to an allocation function that initializes memory to a
126/// fixed value, return said value in the requested type. Otherwise, return
127/// nullptr.
128LLVM_ABI Constant *getInitialValueOfAllocation(const Value *V,
129 const TargetLibraryInfo *TLI,
130 Type *Ty);
131
132/// If a function is part of an allocation family (e.g.
133/// malloc/realloc/calloc/free), return the identifier for its family
134/// of functions.
135LLVM_ABI std::optional<StringRef>
136getAllocationFamily(const Value *I, const TargetLibraryInfo *TLI);
137
138//===----------------------------------------------------------------------===//
139// Utility functions to compute size of objects.
140//
141
142/// Various options to control the behavior of getObjectSize.
143struct ObjectSizeOpts {
144 /// Controls how we handle conditional statements with unknown conditions.
145 enum class Mode : uint8_t {
146 /// All branches must be known and have the same size, starting from the
147 /// offset, to be merged.
148 ExactSizeFromOffset,
149 /// All branches must be known and have the same underlying size and offset
150 /// to be merged.
151 ExactUnderlyingSizeAndOffset,
152 /// Evaluate all branches of an unknown condition. If all evaluations
153 /// succeed, pick the minimum size.
154 Min,
155 /// Same as Min, except we pick the maximum size of all of the branches.
156 Max,
157 };
158
159 /// How we want to evaluate this object's size.
160 Mode EvalMode = Mode::ExactSizeFromOffset;
161 /// Whether to round the result up to the alignment of allocas, byval
162 /// arguments, and global variables.
163 bool RoundToAlign = false;
164 /// If this is true, null pointers in address space 0 will be treated as
165 /// though they can't be evaluated. Otherwise, null is always considered to
166 /// point to a 0 byte region of memory.
167 bool NullIsUnknownSize = false;
168 /// If set, used for more accurate evaluation
169 AAResults *AA = nullptr;
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///
177/// WARNING: The object size returned is the allocation size. This does not
178/// imply dereferenceability at site of use since the object may be freeed in
179/// between.
180LLVM_ABI bool getObjectSize(const Value *Ptr, uint64_t &Size,
181 const DataLayout &DL, const TargetLibraryInfo *TLI,
182 ObjectSizeOpts Opts = {});
183
184/// Like getObjectSize(), but only returns the size of base objects (like
185/// allocas, global variables and allocator calls) and std::nullopt otherwise.
186/// Requires ExactSizeFromOffset mode.
187LLVM_ABI std::optional<TypeSize> getBaseObjectSize(const Value *Ptr,
188 const DataLayout &DL,
189 const TargetLibraryInfo *TLI,
190 ObjectSizeOpts Opts = {});
191
192/// Try to turn a call to \@llvm.objectsize into an integer value of the given
193/// Type. Returns null on failure. If MustSucceed is true, this function will
194/// not return null, and may return conservative values governed by the second
195/// argument of the call to objectsize.
196LLVM_ABI Value *lowerObjectSizeCall(IntrinsicInst *ObjectSize,
197 const DataLayout &DL,
198 const TargetLibraryInfo *TLI,
199 bool MustSucceed);
200LLVM_ABI Value *lowerObjectSizeCall(
201 IntrinsicInst *ObjectSize, const DataLayout &DL,
202 const TargetLibraryInfo *TLI, AAResults *AA, bool MustSucceed,
203 SmallVectorImpl<Instruction *> *InsertedInstructions = nullptr);
204
205/// SizeOffsetType - A base template class for the object size visitors. Used
206/// here as a self-documenting way to handle the values rather than using a
207/// \p std::pair.
208template <typename T, class C> struct SizeOffsetType {
209public:
210 T Size;
211 T Offset;
212
213 SizeOffsetType() = default;
214 SizeOffsetType(T Size, T Offset)
215 : Size(std::move(Size)), Offset(std::move(Offset)) {}
216
217 bool knownSize() const { return C::known(Size); }
218 bool knownOffset() const { return C::known(Offset); }
219 bool anyKnown() const { return knownSize() || knownOffset(); }
220 bool bothKnown() const { return knownSize() && knownOffset(); }
221
222 bool operator==(const SizeOffsetType<T, C> &RHS) const {
223 return Size == RHS.Size && Offset == RHS.Offset;
224 }
225 bool operator!=(const SizeOffsetType<T, C> &RHS) const {
226 return !(*this == RHS);
227 }
228};
229
230/// SizeOffsetAPInt - Used by \p ObjectSizeOffsetVisitor, which works with
231/// \p APInts.
232struct SizeOffsetAPInt : public SizeOffsetType<APInt, SizeOffsetAPInt> {
233 SizeOffsetAPInt() = default;
234 SizeOffsetAPInt(APInt Size, APInt Offset)
235 : SizeOffsetType(std::move(Size), std::move(Offset)) {}
236
237 static bool known(const APInt &V) { return V.getBitWidth() > 1; }
238};
239
240/// OffsetSpan - Used internally by \p ObjectSizeOffsetVisitor. Represents a
241/// point in memory as a pair of allocated bytes before and after it.
242///
243/// \c Before and \c After fields are signed values. It makes it possible to
244/// represent out-of-bound access, e.g. as a result of a GEP, at the expense of
245/// not being able to represent very large allocation.
246struct OffsetSpan {
247 APInt Before; /// Number of allocated bytes before this point.
248 APInt After; /// Number of allocated bytes after this point.
249
250 OffsetSpan() = default;
251 OffsetSpan(APInt Before, APInt After) : Before(Before), After(After) {}
252
253 bool knownBefore() const { return known(V: Before); }
254 bool knownAfter() const { return known(V: After); }
255 bool anyKnown() const { return knownBefore() || knownAfter(); }
256 bool bothKnown() const { return knownBefore() && knownAfter(); }
257
258 bool operator==(const OffsetSpan &RHS) const {
259 return Before == RHS.Before && After == RHS.After;
260 }
261 bool operator!=(const OffsetSpan &RHS) const { return !(*this == RHS); }
262
263 static bool known(const APInt &V) { return V.getBitWidth() > 1; }
264};
265
266/// Evaluate the size and offset of an object pointed to by a Value*
267/// statically. Fails if size or offset are not known at compile time.
268class ObjectSizeOffsetVisitor
269 : public InstVisitor<ObjectSizeOffsetVisitor, OffsetSpan> {
270 const DataLayout &DL;
271 const TargetLibraryInfo *TLI;
272 ObjectSizeOpts Options;
273 unsigned IntTyBits;
274 APInt Zero;
275 SmallDenseMap<Instruction *, OffsetSpan, 8> SeenInsts;
276 unsigned InstructionsVisited;
277
278 APInt align(APInt Size, MaybeAlign Align);
279
280 static OffsetSpan unknown() { return OffsetSpan(); }
281
282public:
283 LLVM_ABI ObjectSizeOffsetVisitor(const DataLayout &DL,
284 const TargetLibraryInfo *TLI,
285 LLVMContext &Context,
286 ObjectSizeOpts Options = {});
287
288 LLVM_ABI SizeOffsetAPInt compute(Value *V);
289
290 // These are "private", except they can't actually be made private. Only
291 // compute() should be used by external users.
292 LLVM_ABI OffsetSpan visitAllocaInst(AllocaInst &I);
293 LLVM_ABI OffsetSpan visitArgument(Argument &A);
294 LLVM_ABI OffsetSpan visitCallBase(CallBase &CB);
295 LLVM_ABI OffsetSpan visitConstantPointerNull(ConstantPointerNull &);
296 LLVM_ABI OffsetSpan visitExtractElementInst(ExtractElementInst &I);
297 LLVM_ABI OffsetSpan visitExtractValueInst(ExtractValueInst &I);
298 LLVM_ABI OffsetSpan visitGlobalAlias(GlobalAlias &GA);
299 LLVM_ABI OffsetSpan visitGlobalVariable(GlobalVariable &GV);
300 LLVM_ABI OffsetSpan visitIntToPtrInst(IntToPtrInst &);
301 LLVM_ABI OffsetSpan visitLoadInst(LoadInst &I);
302 LLVM_ABI OffsetSpan visitPHINode(PHINode &);
303 LLVM_ABI OffsetSpan visitSelectInst(SelectInst &I);
304 LLVM_ABI OffsetSpan visitUndefValue(UndefValue &);
305 LLVM_ABI OffsetSpan visitInstruction(Instruction &I);
306
307private:
308 OffsetSpan
309 findLoadOffsetRange(LoadInst &LoadFrom, BasicBlock &BB,
310 BasicBlock::iterator From,
311 SmallDenseMap<BasicBlock *, OffsetSpan, 8> &VisitedBlocks,
312 unsigned &ScannedInstCount);
313 OffsetSpan combineOffsetRange(OffsetSpan LHS, OffsetSpan RHS);
314 OffsetSpan computeImpl(Value *V);
315 OffsetSpan computeValue(Value *V);
316 bool CheckedZextOrTrunc(APInt &I);
317};
318
319/// SizeOffsetValue - Used by \p ObjectSizeOffsetEvaluator, which works with
320/// \p Values.
321struct SizeOffsetWeakTrackingVH;
322struct SizeOffsetValue : public SizeOffsetType<Value *, SizeOffsetValue> {
323 SizeOffsetValue() : SizeOffsetType(nullptr, nullptr) {}
324 SizeOffsetValue(Value *Size, Value *Offset) : SizeOffsetType(Size, Offset) {}
325 LLVM_ABI SizeOffsetValue(const SizeOffsetWeakTrackingVH &SOT);
326
327 static bool known(Value *V) { return V != nullptr; }
328};
329
330/// SizeOffsetWeakTrackingVH - Used by \p ObjectSizeOffsetEvaluator in a
331/// \p DenseMap.
332struct SizeOffsetWeakTrackingVH
333 : public SizeOffsetType<WeakTrackingVH, SizeOffsetWeakTrackingVH> {
334 SizeOffsetWeakTrackingVH() : SizeOffsetType(nullptr, nullptr) {}
335 SizeOffsetWeakTrackingVH(Value *Size, Value *Offset)
336 : SizeOffsetType(Size, Offset) {}
337 SizeOffsetWeakTrackingVH(const SizeOffsetValue &SOV)
338 : SizeOffsetType(SOV.Size, SOV.Offset) {}
339
340 static bool known(WeakTrackingVH V) { return V.pointsToAliveValue(); }
341};
342
343/// Evaluate the size and offset of an object pointed to by a Value*.
344/// May create code to compute the result at run-time.
345class ObjectSizeOffsetEvaluator
346 : public InstVisitor<ObjectSizeOffsetEvaluator, SizeOffsetValue> {
347 using BuilderTy = IRBuilder<TargetFolder, IRBuilderCallbackInserter>;
348 using WeakEvalType = SizeOffsetWeakTrackingVH;
349 using CacheMapTy = DenseMap<const Value *, WeakEvalType>;
350 using PtrSetTy = SmallPtrSet<const Value *, 8>;
351
352 const DataLayout &DL;
353 const TargetLibraryInfo *TLI;
354 LLVMContext &Context;
355 BuilderTy Builder;
356 IntegerType *IntTy;
357 Value *Zero;
358 CacheMapTy CacheMap;
359 PtrSetTy SeenVals;
360 ObjectSizeOpts EvalOpts;
361 SmallPtrSet<Instruction *, 8> InsertedInstructions;
362
363 SizeOffsetValue compute_(Value *V);
364
365public:
366 LLVM_ABI ObjectSizeOffsetEvaluator(const DataLayout &DL,
367 const TargetLibraryInfo *TLI,
368 LLVMContext &Context,
369 ObjectSizeOpts EvalOpts = {});
370
371 static SizeOffsetValue unknown() { return SizeOffsetValue(); }
372
373 LLVM_ABI SizeOffsetValue compute(Value *V);
374
375 // The individual instruction visitors should be treated as private.
376 LLVM_ABI SizeOffsetValue visitAllocaInst(AllocaInst &I);
377 LLVM_ABI SizeOffsetValue visitCallBase(CallBase &CB);
378 LLVM_ABI SizeOffsetValue visitExtractElementInst(ExtractElementInst &I);
379 LLVM_ABI SizeOffsetValue visitExtractValueInst(ExtractValueInst &I);
380 LLVM_ABI SizeOffsetValue visitGEPOperator(GEPOperator &GEP);
381 LLVM_ABI SizeOffsetValue visitIntToPtrInst(IntToPtrInst &);
382 LLVM_ABI SizeOffsetValue visitLoadInst(LoadInst &I);
383 LLVM_ABI SizeOffsetValue visitPHINode(PHINode &PHI);
384 LLVM_ABI SizeOffsetValue visitSelectInst(SelectInst &I);
385 LLVM_ABI SizeOffsetValue visitInstruction(Instruction &I);
386};
387
388} // end namespace llvm
389
390#endif // LLVM_ANALYSIS_MEMORYBUILTINS_H
391