1 //==- llvm/Analysis/MemoryBuiltins.h - Calls to memory builtins --*- C++ -*-==//
2 //
3 //                     The LLVM Compiler Infrastructure
4 //
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
7 //
8 //===----------------------------------------------------------------------===//
9 //
10 // This family of functions identifies calls to builtin functions that allocate
11 // or free memory.
12 //
13 //===----------------------------------------------------------------------===//
14 
15 #ifndef LLVM_ANALYSIS_MEMORYBUILTINS_H
16 #define LLVM_ANALYSIS_MEMORYBUILTINS_H
17 
18 #include "llvm/ADT/APInt.h"
19 #include "llvm/ADT/DenseMap.h"
20 #include "llvm/ADT/SmallPtrSet.h"
21 #include "llvm/Analysis/TargetFolder.h"
22 #include "llvm/IR/CallSite.h"
23 #include "llvm/IR/IRBuilder.h"
24 #include "llvm/IR/InstVisitor.h"
25 #include "llvm/IR/ValueHandle.h"
26 #include <cstdint>
27 #include <utility>
28 
29 namespace llvm {
30 
31 class AllocaInst;
32 class Argument;
33 class CallInst;
34 class ConstantInt;
35 class ConstantPointerNull;
36 class DataLayout;
37 class ExtractElementInst;
38 class ExtractValueInst;
39 class GEPOperator;
40 class GlobalAlias;
41 class GlobalVariable;
42 class Instruction;
43 class IntegerType;
44 class IntrinsicInst;
45 class IntToPtrInst;
46 class LLVMContext;
47 class LoadInst;
48 class PHINode;
49 class PointerType;
50 class SelectInst;
51 class TargetLibraryInfo;
52 class Type;
53 class UndefValue;
54 class Value;
55 
56 /// Tests if a value is a call or invoke to a library function that
57 /// allocates or reallocates memory (either malloc, calloc, realloc, or strdup
58 /// like).
59 bool isAllocationFn(const Value *V, const TargetLibraryInfo *TLI,
60                     bool LookThroughBitCast = false);
61 
62 /// Tests if a value is a call or invoke to a function that returns a
63 /// NoAlias pointer (including malloc/calloc/realloc/strdup-like functions).
64 bool isNoAliasFn(const Value *V, const TargetLibraryInfo *TLI,
65                  bool LookThroughBitCast = false);
66 
67 /// Tests if a value is a call or invoke to a library function that
68 /// allocates uninitialized memory (such as malloc).
69 bool isMallocLikeFn(const Value *V, const TargetLibraryInfo *TLI,
70                     bool LookThroughBitCast = false);
71 
72 /// Tests if a value is a call or invoke to a library function that
73 /// allocates zero-filled memory (such as calloc).
74 bool isCallocLikeFn(const Value *V, const TargetLibraryInfo *TLI,
75                     bool LookThroughBitCast = false);
76 
77 /// Tests if a value is a call or invoke to a library function that
78 /// allocates memory similar to malloc or calloc.
79 bool isMallocOrCallocLikeFn(const Value *V, const TargetLibraryInfo *TLI,
80                             bool LookThroughBitCast = false);
81 
82 /// Tests if a value is a call or invoke to a library function that
83 /// allocates memory (either malloc, calloc, or strdup like).
84 bool isAllocLikeFn(const Value *V, const TargetLibraryInfo *TLI,
85                    bool LookThroughBitCast = false);
86 
87 //===----------------------------------------------------------------------===//
88 //  malloc Call Utility Functions.
89 //
90 
91 /// extractMallocCall - Returns the corresponding CallInst if the instruction
92 /// is a malloc call.  Since CallInst::CreateMalloc() only creates calls, we
93 /// ignore InvokeInst here.
94 const CallInst *extractMallocCall(const Value *I, const TargetLibraryInfo *TLI);
extractMallocCall(Value * I,const TargetLibraryInfo * TLI)95 inline CallInst *extractMallocCall(Value *I, const TargetLibraryInfo *TLI) {
96   return const_cast<CallInst*>(extractMallocCall((const Value*)I, TLI));
97 }
98 
99 /// getMallocType - Returns the PointerType resulting from the malloc call.
100 /// The PointerType depends on the number of bitcast uses of the malloc call:
101 ///   0: PointerType is the malloc calls' return type.
102 ///   1: PointerType is the bitcast's result type.
103 ///  >1: Unique PointerType cannot be determined, return NULL.
104 PointerType *getMallocType(const CallInst *CI, const TargetLibraryInfo *TLI);
105 
106 /// getMallocAllocatedType - Returns the Type allocated by malloc call.
107 /// The Type depends on the number of bitcast uses of the malloc call:
108 ///   0: PointerType is the malloc calls' return type.
109 ///   1: PointerType is the bitcast's result type.
110 ///  >1: Unique PointerType cannot be determined, return NULL.
111 Type *getMallocAllocatedType(const CallInst *CI, const TargetLibraryInfo *TLI);
112 
113 /// getMallocArraySize - Returns the array size of a malloc call.  If the
114 /// argument passed to malloc is a multiple of the size of the malloced type,
115 /// then return that multiple.  For non-array mallocs, the multiple is
116 /// constant 1.  Otherwise, return NULL for mallocs whose array size cannot be
117 /// determined.
118 Value *getMallocArraySize(CallInst *CI, const DataLayout &DL,
119                           const TargetLibraryInfo *TLI,
120                           bool LookThroughSExt = false);
121 
122 //===----------------------------------------------------------------------===//
123 //  calloc Call Utility Functions.
124 //
125 
126 /// extractCallocCall - Returns the corresponding CallInst if the instruction
127 /// is a calloc call.
128 const CallInst *extractCallocCall(const Value *I, const TargetLibraryInfo *TLI);
extractCallocCall(Value * I,const TargetLibraryInfo * TLI)129 inline CallInst *extractCallocCall(Value *I, const TargetLibraryInfo *TLI) {
130   return const_cast<CallInst*>(extractCallocCall((const Value*)I, TLI));
131 }
132 
133 
134 //===----------------------------------------------------------------------===//
135 //  free Call Utility Functions.
136 //
137 
138 /// isFreeCall - Returns non-null if the value is a call to the builtin free()
139 const CallInst *isFreeCall(const Value *I, const TargetLibraryInfo *TLI);
140 
isFreeCall(Value * I,const TargetLibraryInfo * TLI)141 inline CallInst *isFreeCall(Value *I, const TargetLibraryInfo *TLI) {
142   return const_cast<CallInst*>(isFreeCall((const Value*)I, TLI));
143 }
144 
145 //===----------------------------------------------------------------------===//
146 //  Utility functions to compute size of objects.
147 //
148 
149 /// Various options to control the behavior of getObjectSize.
150 struct ObjectSizeOpts {
151   /// Controls how we handle conditional statements with unknown conditions.
152   enum class Mode : uint8_t {
153     /// Fail to evaluate an unknown condition.
154     Exact,
155     /// Evaluate all branches of an unknown condition. If all evaluations
156     /// succeed, pick the minimum size.
157     Min,
158     /// Same as Min, except we pick the maximum size of all of the branches.
159     Max
160   };
161 
162   /// How we want to evaluate this object's size.
163   Mode EvalMode = Mode::Exact;
164   /// Whether to round the result up to the alignment of allocas, byval
165   /// arguments, and global variables.
166   bool RoundToAlign = false;
167   /// If this is true, null pointers in address space 0 will be treated as
168   /// though they can't be evaluated. Otherwise, null is always considered to
169   /// point to a 0 byte region of memory.
170   bool NullIsUnknownSize = false;
171 };
172 
173 /// Compute the size of the object pointed by Ptr. Returns true and the
174 /// object size in Size if successful, and false otherwise. In this context, by
175 /// object we mean the region of memory starting at Ptr to the end of the
176 /// underlying object pointed to by Ptr.
177 bool getObjectSize(const Value *Ptr, uint64_t &Size, const DataLayout &DL,
178                    const TargetLibraryInfo *TLI, ObjectSizeOpts Opts = {});
179 
180 /// Try to turn a call to \@llvm.objectsize into an integer value of the given
181 /// Type. Returns null on failure.
182 /// If MustSucceed is true, this function will not return null, and may return
183 /// conservative values governed by the second argument of the call to
184 /// objectsize.
185 ConstantInt *lowerObjectSizeCall(IntrinsicInst *ObjectSize,
186                                  const DataLayout &DL,
187                                  const TargetLibraryInfo *TLI,
188                                  bool MustSucceed);
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, uint64_t Align);
204 
unknown()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 
knownSize(const SizeOffsetType & SizeOffset)215   static bool knownSize(const SizeOffsetType &SizeOffset) {
216     return SizeOffset.first.getBitWidth() > 1;
217   }
218 
knownOffset(const SizeOffsetType & SizeOffset)219   static bool knownOffset(const SizeOffsetType &SizeOffset) {
220     return SizeOffset.second.getBitWidth() > 1;
221   }
222 
bothKnown(const SizeOffsetType & SizeOffset)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 visitCallSite(CallSite CS);
232   SizeOffsetType visitConstantPointerNull(ConstantPointerNull&);
233   SizeOffsetType visitExtractElementInst(ExtractElementInst &I);
234   SizeOffsetType visitExtractValueInst(ExtractValueInst &I);
235   SizeOffsetType visitGEPOperator(GEPOperator &GEP);
236   SizeOffsetType visitGlobalAlias(GlobalAlias &GA);
237   SizeOffsetType visitGlobalVariable(GlobalVariable &GV);
238   SizeOffsetType visitIntToPtrInst(IntToPtrInst&);
239   SizeOffsetType visitLoadInst(LoadInst &I);
240   SizeOffsetType visitPHINode(PHINode&);
241   SizeOffsetType visitSelectInst(SelectInst &I);
242   SizeOffsetType visitUndefValue(UndefValue&);
243   SizeOffsetType visitInstruction(Instruction &I);
244 
245 private:
246   bool CheckedZextOrTrunc(APInt &I);
247 };
248 
249 using SizeOffsetEvalType = std::pair<Value *, Value *>;
250 
251 /// Evaluate the size and offset of an object pointed to by a Value*.
252 /// May create code to compute the result at run-time.
253 class ObjectSizeOffsetEvaluator
254   : public InstVisitor<ObjectSizeOffsetEvaluator, SizeOffsetEvalType> {
255   using BuilderTy = IRBuilder<TargetFolder>;
256   using WeakEvalType = std::pair<WeakTrackingVH, WeakTrackingVH>;
257   using CacheMapTy = DenseMap<const Value *, WeakEvalType>;
258   using PtrSetTy = SmallPtrSet<const Value *, 8>;
259 
260   const DataLayout &DL;
261   const TargetLibraryInfo *TLI;
262   LLVMContext &Context;
263   BuilderTy Builder;
264   IntegerType *IntTy;
265   Value *Zero;
266   CacheMapTy CacheMap;
267   PtrSetTy SeenVals;
268   bool RoundToAlign;
269 
unknown()270   SizeOffsetEvalType unknown() {
271     return std::make_pair(nullptr, nullptr);
272   }
273 
274   SizeOffsetEvalType compute_(Value *V);
275 
276 public:
277   ObjectSizeOffsetEvaluator(const DataLayout &DL, const TargetLibraryInfo *TLI,
278                             LLVMContext &Context, bool RoundToAlign = false);
279 
280   SizeOffsetEvalType compute(Value *V);
281 
knownSize(SizeOffsetEvalType SizeOffset)282   bool knownSize(SizeOffsetEvalType SizeOffset) {
283     return SizeOffset.first;
284   }
285 
knownOffset(SizeOffsetEvalType SizeOffset)286   bool knownOffset(SizeOffsetEvalType SizeOffset) {
287     return SizeOffset.second;
288   }
289 
anyKnown(SizeOffsetEvalType SizeOffset)290   bool anyKnown(SizeOffsetEvalType SizeOffset) {
291     return knownSize(SizeOffset) || knownOffset(SizeOffset);
292   }
293 
bothKnown(SizeOffsetEvalType SizeOffset)294   bool bothKnown(SizeOffsetEvalType SizeOffset) {
295     return knownSize(SizeOffset) && knownOffset(SizeOffset);
296   }
297 
298   // The individual instruction visitors should be treated as private.
299   SizeOffsetEvalType visitAllocaInst(AllocaInst &I);
300   SizeOffsetEvalType visitCallSite(CallSite CS);
301   SizeOffsetEvalType visitExtractElementInst(ExtractElementInst &I);
302   SizeOffsetEvalType visitExtractValueInst(ExtractValueInst &I);
303   SizeOffsetEvalType visitGEPOperator(GEPOperator &GEP);
304   SizeOffsetEvalType visitIntToPtrInst(IntToPtrInst&);
305   SizeOffsetEvalType visitLoadInst(LoadInst &I);
306   SizeOffsetEvalType visitPHINode(PHINode &PHI);
307   SizeOffsetEvalType visitSelectInst(SelectInst &I);
308   SizeOffsetEvalType visitInstruction(Instruction &I);
309 };
310 
311 } // end namespace llvm
312 
313 #endif // LLVM_ANALYSIS_MEMORYBUILTINS_H
314