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 ExtractElementInst;
37 class ExtractValueInst;
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 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 
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 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