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 <utility>
27 
28 namespace llvm {
29 
30 class AllocaInst;
31 class AAResults;
32 class Argument;
33 class ConstantPointerNull;
34 class DataLayout;
35 class ExtractElementInst;
36 class ExtractValueInst;
37 class GEPOperator;
38 class GlobalAlias;
39 class GlobalVariable;
40 class Instruction;
41 class IntegerType;
42 class IntrinsicInst;
43 class IntToPtrInst;
44 class LLVMContext;
45 class LoadInst;
46 class PHINode;
47 class SelectInst;
48 class Type;
49 class UndefValue;
50 class Value;
51 
52 /// Tests if a value is a call or invoke to a library function that
53 /// allocates or reallocates memory (either malloc, calloc, realloc, or strdup
54 /// like).
55 bool isAllocationFn(const Value *V, const TargetLibraryInfo *TLI);
56 bool isAllocationFn(const Value *V,
57                     function_ref<const TargetLibraryInfo &(Function &)> GetTLI);
58 
59 /// Tests if a value is a call or invoke to a library function that
60 /// allocates memory similar to malloc or calloc.
61 bool isMallocOrCallocLikeFn(const Value *V, const TargetLibraryInfo *TLI);
62 
63 /// Tests if a value is a call or invoke to a library function that
64 /// allocates memory (either malloc, calloc, or strdup like).
65 bool isAllocLikeFn(const Value *V, const TargetLibraryInfo *TLI);
66 
67 /// Tests if a function is a call or invoke to a library function that
68 /// reallocates memory (e.g., realloc).
69 bool isReallocLikeFn(const Function *F, const TargetLibraryInfo *TLI);
70 
71 /// If this is a call to a realloc function, return the reallocated operand.
72 Value *getReallocatedOperand(const CallBase *CB, const TargetLibraryInfo *TLI);
73 
74 //===----------------------------------------------------------------------===//
75 //  free Call Utility Functions.
76 //
77 
78 /// isLibFreeFunction - Returns true if the function is a builtin free()
79 bool isLibFreeFunction(const Function *F, const LibFunc TLIFn);
80 
81 /// If this if a call to a free function, return the freed operand.
82 Value *getFreedOperand(const CallBase *CB, const TargetLibraryInfo *TLI);
83 
84 //===----------------------------------------------------------------------===//
85 //  Properties of allocation functions
86 //
87 
88 /// Return true if this is a call to an allocation function that does not have
89 /// side effects that we are required to preserve beyond the effect of
90 /// allocating a new object.
91 /// Ex: If our allocation routine has a counter for the number of objects
92 /// allocated, and the program prints it on exit, can the value change due
93 /// to optimization? Answer is highly language dependent.
94 /// Note: *Removable* really does mean removable; it does not mean observable.
95 /// A language (e.g. C++) can allow removing allocations without allowing
96 /// insertion or speculative execution of allocation routines.
97 bool isRemovableAlloc(const CallBase *V, const TargetLibraryInfo *TLI);
98 
99 /// Gets the alignment argument for an aligned_alloc-like function, using either
100 /// built-in knowledge based on fuction names/signatures or allocalign
101 /// attributes. Note: the Value returned may not indicate a valid alignment, per
102 /// the definition of the allocalign attribute.
103 Value *getAllocAlignment(const CallBase *V, const TargetLibraryInfo *TLI);
104 
105 /// Return the size of the requested allocation. With a trivial mapper, this is
106 /// similar to calling getObjectSize(..., Exact), but without looking through
107 /// calls that return their argument. A mapper function can be used to replace
108 /// one Value* (operand to the allocation) with another. This is useful when
109 /// doing abstract interpretation.
110 Optional<APInt> getAllocSize(
111     const CallBase *CB, const TargetLibraryInfo *TLI,
112     function_ref<const Value *(const Value *)> Mapper = [](const Value *V) {
113       return V;
114     });
115 
116 /// If this is a call to an allocation function that initializes memory to a
117 /// fixed value, return said value in the requested type.  Otherwise, return
118 /// nullptr.
119 Constant *getInitialValueOfAllocation(const Value *V,
120                                       const TargetLibraryInfo *TLI,
121                                       Type *Ty);
122 
123 /// If a function is part of an allocation family (e.g.
124 /// malloc/realloc/calloc/free), return the identifier for its family
125 /// of functions.
126 Optional<StringRef> getAllocationFamily(const Value *I,
127                                         const TargetLibraryInfo *TLI);
128 
129 //===----------------------------------------------------------------------===//
130 //  Utility functions to compute size of objects.
131 //
132 
133 /// Various options to control the behavior of getObjectSize.
134 struct ObjectSizeOpts {
135   /// Controls how we handle conditional statements with unknown conditions.
136   enum class Mode : uint8_t {
137     /// Fail to evaluate an unknown condition.
138     Exact,
139     /// Evaluate all branches of an unknown condition. If all evaluations
140     /// succeed, pick the minimum size.
141     Min,
142     /// Same as Min, except we pick the maximum size of all of the branches.
143     Max
144   };
145 
146   /// How we want to evaluate this object's size.
147   Mode EvalMode = Mode::Exact;
148   /// Whether to round the result up to the alignment of allocas, byval
149   /// arguments, and global variables.
150   bool RoundToAlign = false;
151   /// If this is true, null pointers in address space 0 will be treated as
152   /// though they can't be evaluated. Otherwise, null is always considered to
153   /// point to a 0 byte region of memory.
154   bool NullIsUnknownSize = false;
155   /// If set, used for more accurate evaluation
156   AAResults *AA = nullptr;
157 };
158 
159 /// Compute the size of the object pointed by Ptr. Returns true and the
160 /// object size in Size if successful, and false otherwise. In this context, by
161 /// object we mean the region of memory starting at Ptr to the end of the
162 /// underlying object pointed to by Ptr.
163 ///
164 /// WARNING: The object size returned is the allocation size.  This does not
165 /// imply dereferenceability at site of use since the object may be freeed in
166 /// between.
167 bool getObjectSize(const Value *Ptr, uint64_t &Size, const DataLayout &DL,
168                    const TargetLibraryInfo *TLI, ObjectSizeOpts Opts = {});
169 
170 /// Try to turn a call to \@llvm.objectsize into an integer value of the given
171 /// Type. Returns null on failure. If MustSucceed is true, this function will
172 /// not return null, and may return conservative values governed by the second
173 /// argument of the call to objectsize.
174 Value *lowerObjectSizeCall(IntrinsicInst *ObjectSize, const DataLayout &DL,
175                            const TargetLibraryInfo *TLI, bool MustSucceed);
176 Value *lowerObjectSizeCall(IntrinsicInst *ObjectSize, const DataLayout &DL,
177                            const TargetLibraryInfo *TLI, AAResults *AA,
178                            bool MustSucceed);
179 
180 using SizeOffsetType = std::pair<APInt, APInt>;
181 
182 /// Evaluate the size and offset of an object pointed to by a Value*
183 /// statically. Fails if size or offset are not known at compile time.
184 class ObjectSizeOffsetVisitor
185   : public InstVisitor<ObjectSizeOffsetVisitor, SizeOffsetType> {
186   const DataLayout &DL;
187   const TargetLibraryInfo *TLI;
188   ObjectSizeOpts Options;
189   unsigned IntTyBits;
190   APInt Zero;
191   SmallPtrSet<Instruction *, 8> SeenInsts;
192 
193   APInt align(APInt Size, MaybeAlign Align);
194 
195   SizeOffsetType unknown() {
196     return std::make_pair(APInt(), APInt());
197   }
198 
199 public:
200   ObjectSizeOffsetVisitor(const DataLayout &DL, const TargetLibraryInfo *TLI,
201                           LLVMContext &Context, ObjectSizeOpts Options = {});
202 
203   SizeOffsetType compute(Value *V);
204 
205   static bool knownSize(const SizeOffsetType &SizeOffset) {
206     return SizeOffset.first.getBitWidth() > 1;
207   }
208 
209   static bool knownOffset(const SizeOffsetType &SizeOffset) {
210     return SizeOffset.second.getBitWidth() > 1;
211   }
212 
213   static bool bothKnown(const SizeOffsetType &SizeOffset) {
214     return knownSize(SizeOffset) && knownOffset(SizeOffset);
215   }
216 
217   // These are "private", except they can't actually be made private. Only
218   // compute() should be used by external users.
219   SizeOffsetType visitAllocaInst(AllocaInst &I);
220   SizeOffsetType visitArgument(Argument &A);
221   SizeOffsetType visitCallBase(CallBase &CB);
222   SizeOffsetType visitConstantPointerNull(ConstantPointerNull&);
223   SizeOffsetType visitExtractElementInst(ExtractElementInst &I);
224   SizeOffsetType visitExtractValueInst(ExtractValueInst &I);
225   SizeOffsetType visitGlobalAlias(GlobalAlias &GA);
226   SizeOffsetType visitGlobalVariable(GlobalVariable &GV);
227   SizeOffsetType visitIntToPtrInst(IntToPtrInst&);
228   SizeOffsetType visitLoadInst(LoadInst &I);
229   SizeOffsetType visitPHINode(PHINode&);
230   SizeOffsetType visitSelectInst(SelectInst &I);
231   SizeOffsetType visitUndefValue(UndefValue&);
232   SizeOffsetType visitInstruction(Instruction &I);
233 
234 private:
235   SizeOffsetType findLoadSizeOffset(
236       LoadInst &LoadFrom, BasicBlock &BB, BasicBlock::iterator From,
237       SmallDenseMap<BasicBlock *, SizeOffsetType, 8> &VisitedBlocks,
238       unsigned &ScannedInstCount);
239   SizeOffsetType combineSizeOffset(SizeOffsetType LHS, SizeOffsetType RHS);
240   SizeOffsetType computeImpl(Value *V);
241   bool CheckedZextOrTrunc(APInt &I);
242 };
243 
244 using SizeOffsetEvalType = std::pair<Value *, Value *>;
245 
246 /// Evaluate the size and offset of an object pointed to by a Value*.
247 /// May create code to compute the result at run-time.
248 class ObjectSizeOffsetEvaluator
249   : public InstVisitor<ObjectSizeOffsetEvaluator, SizeOffsetEvalType> {
250   using BuilderTy = IRBuilder<TargetFolder, IRBuilderCallbackInserter>;
251   using WeakEvalType = std::pair<WeakTrackingVH, WeakTrackingVH>;
252   using CacheMapTy = DenseMap<const Value *, WeakEvalType>;
253   using PtrSetTy = SmallPtrSet<const Value *, 8>;
254 
255   const DataLayout &DL;
256   const TargetLibraryInfo *TLI;
257   LLVMContext &Context;
258   BuilderTy Builder;
259   IntegerType *IntTy;
260   Value *Zero;
261   CacheMapTy CacheMap;
262   PtrSetTy SeenVals;
263   ObjectSizeOpts EvalOpts;
264   SmallPtrSet<Instruction *, 8> InsertedInstructions;
265 
266   SizeOffsetEvalType compute_(Value *V);
267 
268 public:
269   static SizeOffsetEvalType unknown() {
270     return std::make_pair(nullptr, nullptr);
271   }
272 
273   ObjectSizeOffsetEvaluator(const DataLayout &DL, const TargetLibraryInfo *TLI,
274                             LLVMContext &Context, ObjectSizeOpts EvalOpts = {});
275 
276   SizeOffsetEvalType compute(Value *V);
277 
278   bool knownSize(SizeOffsetEvalType SizeOffset) {
279     return SizeOffset.first;
280   }
281 
282   bool knownOffset(SizeOffsetEvalType SizeOffset) {
283     return SizeOffset.second;
284   }
285 
286   bool anyKnown(SizeOffsetEvalType SizeOffset) {
287     return knownSize(SizeOffset) || knownOffset(SizeOffset);
288   }
289 
290   bool bothKnown(SizeOffsetEvalType SizeOffset) {
291     return knownSize(SizeOffset) && knownOffset(SizeOffset);
292   }
293 
294   // The individual instruction visitors should be treated as private.
295   SizeOffsetEvalType visitAllocaInst(AllocaInst &I);
296   SizeOffsetEvalType visitCallBase(CallBase &CB);
297   SizeOffsetEvalType visitExtractElementInst(ExtractElementInst &I);
298   SizeOffsetEvalType visitExtractValueInst(ExtractValueInst &I);
299   SizeOffsetEvalType visitGEPOperator(GEPOperator &GEP);
300   SizeOffsetEvalType visitIntToPtrInst(IntToPtrInst&);
301   SizeOffsetEvalType visitLoadInst(LoadInst &I);
302   SizeOffsetEvalType visitPHINode(PHINode &PHI);
303   SizeOffsetEvalType visitSelectInst(SelectInst &I);
304   SizeOffsetEvalType visitInstruction(Instruction &I);
305 };
306 
307 } // end namespace llvm
308 
309 #endif // LLVM_ANALYSIS_MEMORYBUILTINS_H
310