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 using SizeOffsetType = std::pair<APInt, APInt>;
191 
192 /// Evaluate the size and offset of an object pointed to by a Value*
193 /// statically. Fails if size or offset are not known at compile time.
194 class ObjectSizeOffsetVisitor
195   : public InstVisitor<ObjectSizeOffsetVisitor, SizeOffsetType> {
196   const DataLayout &DL;
197   const TargetLibraryInfo *TLI;
198   ObjectSizeOpts Options;
199   unsigned IntTyBits;
200   APInt Zero;
201   SmallPtrSet<Instruction *, 8> SeenInsts;
202 
203   APInt align(APInt Size, MaybeAlign Align);
204 
205   SizeOffsetType unknown() {
206     return std::make_pair(APInt(), APInt());
207   }
208 
209 public:
210   ObjectSizeOffsetVisitor(const DataLayout &DL, const TargetLibraryInfo *TLI,
211                           LLVMContext &Context, ObjectSizeOpts Options = {});
212 
213   SizeOffsetType compute(Value *V);
214 
215   static bool knownSize(const SizeOffsetType &SizeOffset) {
216     return SizeOffset.first.getBitWidth() > 1;
217   }
218 
219   static bool knownOffset(const SizeOffsetType &SizeOffset) {
220     return SizeOffset.second.getBitWidth() > 1;
221   }
222 
223   static bool bothKnown(const SizeOffsetType &SizeOffset) {
224     return knownSize(SizeOffset) && knownOffset(SizeOffset);
225   }
226 
227   // These are "private", except they can't actually be made private. Only
228   // compute() should be used by external users.
229   SizeOffsetType visitAllocaInst(AllocaInst &I);
230   SizeOffsetType visitArgument(Argument &A);
231   SizeOffsetType visitCallBase(CallBase &CB);
232   SizeOffsetType visitConstantPointerNull(ConstantPointerNull&);
233   SizeOffsetType visitExtractElementInst(ExtractElementInst &I);
234   SizeOffsetType visitExtractValueInst(ExtractValueInst &I);
235   SizeOffsetType visitGlobalAlias(GlobalAlias &GA);
236   SizeOffsetType visitGlobalVariable(GlobalVariable &GV);
237   SizeOffsetType visitIntToPtrInst(IntToPtrInst&);
238   SizeOffsetType visitLoadInst(LoadInst &I);
239   SizeOffsetType visitPHINode(PHINode&);
240   SizeOffsetType visitSelectInst(SelectInst &I);
241   SizeOffsetType visitUndefValue(UndefValue&);
242   SizeOffsetType visitInstruction(Instruction &I);
243 
244 private:
245   SizeOffsetType findLoadSizeOffset(
246       LoadInst &LoadFrom, BasicBlock &BB, BasicBlock::iterator From,
247       SmallDenseMap<BasicBlock *, SizeOffsetType, 8> &VisitedBlocks,
248       unsigned &ScannedInstCount);
249   SizeOffsetType combineSizeOffset(SizeOffsetType LHS, SizeOffsetType RHS);
250   SizeOffsetType computeImpl(Value *V);
251   bool CheckedZextOrTrunc(APInt &I);
252 };
253 
254 using SizeOffsetEvalType = std::pair<Value *, Value *>;
255 
256 /// Evaluate the size and offset of an object pointed to by a Value*.
257 /// May create code to compute the result at run-time.
258 class ObjectSizeOffsetEvaluator
259   : public InstVisitor<ObjectSizeOffsetEvaluator, SizeOffsetEvalType> {
260   using BuilderTy = IRBuilder<TargetFolder, IRBuilderCallbackInserter>;
261   using WeakEvalType = std::pair<WeakTrackingVH, WeakTrackingVH>;
262   using CacheMapTy = DenseMap<const Value *, WeakEvalType>;
263   using PtrSetTy = SmallPtrSet<const Value *, 8>;
264 
265   const DataLayout &DL;
266   const TargetLibraryInfo *TLI;
267   LLVMContext &Context;
268   BuilderTy Builder;
269   IntegerType *IntTy;
270   Value *Zero;
271   CacheMapTy CacheMap;
272   PtrSetTy SeenVals;
273   ObjectSizeOpts EvalOpts;
274   SmallPtrSet<Instruction *, 8> InsertedInstructions;
275 
276   SizeOffsetEvalType compute_(Value *V);
277 
278 public:
279   static SizeOffsetEvalType unknown() {
280     return std::make_pair(nullptr, nullptr);
281   }
282 
283   ObjectSizeOffsetEvaluator(const DataLayout &DL, const TargetLibraryInfo *TLI,
284                             LLVMContext &Context, ObjectSizeOpts EvalOpts = {});
285 
286   SizeOffsetEvalType compute(Value *V);
287 
288   bool knownSize(SizeOffsetEvalType SizeOffset) {
289     return SizeOffset.first;
290   }
291 
292   bool knownOffset(SizeOffsetEvalType SizeOffset) {
293     return SizeOffset.second;
294   }
295 
296   bool anyKnown(SizeOffsetEvalType SizeOffset) {
297     return knownSize(SizeOffset) || knownOffset(SizeOffset);
298   }
299 
300   bool bothKnown(SizeOffsetEvalType SizeOffset) {
301     return knownSize(SizeOffset) && knownOffset(SizeOffset);
302   }
303 
304   // The individual instruction visitors should be treated as private.
305   SizeOffsetEvalType visitAllocaInst(AllocaInst &I);
306   SizeOffsetEvalType visitCallBase(CallBase &CB);
307   SizeOffsetEvalType visitExtractElementInst(ExtractElementInst &I);
308   SizeOffsetEvalType visitExtractValueInst(ExtractValueInst &I);
309   SizeOffsetEvalType visitGEPOperator(GEPOperator &GEP);
310   SizeOffsetEvalType visitIntToPtrInst(IntToPtrInst&);
311   SizeOffsetEvalType visitLoadInst(LoadInst &I);
312   SizeOffsetEvalType visitPHINode(PHINode &PHI);
313   SizeOffsetEvalType visitSelectInst(SelectInst &I);
314   SizeOffsetEvalType visitInstruction(Instruction &I);
315 };
316 
317 } // end namespace llvm
318 
319 #endif // LLVM_ANALYSIS_MEMORYBUILTINS_H
320