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