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 | |
29 | namespace llvm { |
30 | |
31 | class AllocaInst; |
32 | class AAResults; |
33 | class Argument; |
34 | class ConstantPointerNull; |
35 | class DataLayout; |
36 | class ; |
37 | class ; |
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 SelectInst; |
49 | class Type; |
50 | class UndefValue; |
51 | class 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). |
56 | bool isAllocationFn(const Value *V, const TargetLibraryInfo *TLI); |
57 | bool 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. |
62 | bool 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. |
66 | bool 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). |
70 | bool 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). |
74 | bool isReallocLikeFn(const Function *F); |
75 | |
76 | /// If this is a call to a realloc function, return the reallocated operand. |
77 | Value *getReallocatedOperand(const CallBase *CB); |
78 | |
79 | //===----------------------------------------------------------------------===// |
80 | // free Call Utility Functions. |
81 | // |
82 | |
83 | /// isLibFreeFunction - Returns true if the function is a builtin free() |
84 | bool isLibFreeFunction(const Function *F, const LibFunc TLIFn); |
85 | |
86 | /// If this if a call to a free function, return the freed operand. |
87 | Value *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. |
102 | bool 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. |
108 | Value *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. |
115 | std::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. |
124 | Constant *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. |
131 | std::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. |
139 | struct 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. |
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 | Value *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. |
193 | template <typename T, class C> struct SizeOffsetType { |
194 | public: |
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. |
216 | struct 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. |
225 | class 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 | |
239 | public: |
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 (ExtractElementInst &I); |
252 | SizeOffsetAPInt (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 | |
262 | private: |
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. |
275 | struct SizeOffsetWeakTrackingVH; |
276 | struct 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. |
286 | struct 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. |
299 | class 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 | |
319 | public: |
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 (ExtractElementInst &I); |
331 | SizeOffsetValue (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 | |