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/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 bool isAllocationFn(const Value *V,
62 function_ref<const TargetLibraryInfo &(Function &)> GetTLI,
63 bool LookThroughBitCast = false);
64
65 /// Tests if a value is a call or invoke to a function that returns a
66 /// NoAlias pointer (including malloc/calloc/realloc/strdup-like functions).
67 bool isNoAliasFn(const Value *V, const TargetLibraryInfo *TLI,
68 bool LookThroughBitCast = false);
69
70 /// Tests if a value is a call or invoke to a library function that
71 /// allocates uninitialized memory (such as malloc).
72 bool isMallocLikeFn(const Value *V, const TargetLibraryInfo *TLI,
73 bool LookThroughBitCast = false);
74 bool isMallocLikeFn(const Value *V,
75 function_ref<const TargetLibraryInfo &(Function &)> GetTLI,
76 bool LookThroughBitCast = false);
77
78 /// Tests if a value is a call or invoke to a library function that
79 /// allocates zero-filled memory (such as calloc).
80 bool isCallocLikeFn(const Value *V, const TargetLibraryInfo *TLI,
81 bool LookThroughBitCast = false);
82
83 /// Tests if a value is a call or invoke to a library function that
84 /// allocates memory similar to malloc or calloc.
85 bool isMallocOrCallocLikeFn(const Value *V, const TargetLibraryInfo *TLI,
86 bool LookThroughBitCast = false);
87
88 /// Tests if a value is a call or invoke to a library function that
89 /// allocates memory (either malloc, calloc, or strdup like).
90 bool isAllocLikeFn(const Value *V, const TargetLibraryInfo *TLI,
91 bool LookThroughBitCast = false);
92
93 /// Tests if a value is a call or invoke to a library function that
94 /// reallocates memory (e.g., realloc).
95 bool isReallocLikeFn(const Value *V, const TargetLibraryInfo *TLI,
96 bool LookThroughBitCast = false);
97
98 /// Tests if a function is a call or invoke to a library function that
99 /// reallocates memory (e.g., realloc).
100 bool isReallocLikeFn(const Function *F, const TargetLibraryInfo *TLI);
101
102 /// Tests if a value is a call or invoke to a library function that
103 /// allocates memory and throws if an allocation failed (e.g., new).
104 bool isOpNewLikeFn(const Value *V, const TargetLibraryInfo *TLI,
105 bool LookThroughBitCast = false);
106
107 /// Tests if a value is a call or invoke to a library function that
108 /// allocates memory (strdup, strndup).
109 bool isStrdupLikeFn(const Value *V, const TargetLibraryInfo *TLI,
110 bool LookThroughBitCast = false);
111
112 //===----------------------------------------------------------------------===//
113 // malloc Call Utility Functions.
114 //
115
116 /// extractMallocCall - Returns the corresponding CallInst if the instruction
117 /// is a malloc call. Since CallInst::CreateMalloc() only creates calls, we
118 /// ignore InvokeInst here.
119 const CallInst *
120 extractMallocCall(const Value *I,
121 function_ref<const TargetLibraryInfo &(Function &)> GetTLI);
122 inline CallInst *
extractMallocCall(Value * I,function_ref<const TargetLibraryInfo & (Function &)> GetTLI)123 extractMallocCall(Value *I,
124 function_ref<const TargetLibraryInfo &(Function &)> GetTLI) {
125 return const_cast<CallInst *>(extractMallocCall((const Value *)I, GetTLI));
126 }
127
128 /// getMallocType - Returns the PointerType resulting from the malloc call.
129 /// The PointerType depends on the number of bitcast uses of the malloc call:
130 /// 0: PointerType is the malloc calls' return type.
131 /// 1: PointerType is the bitcast's result type.
132 /// >1: Unique PointerType cannot be determined, return NULL.
133 PointerType *getMallocType(const CallInst *CI, const TargetLibraryInfo *TLI);
134
135 /// getMallocAllocatedType - Returns the Type allocated by malloc call.
136 /// The Type depends on the number of bitcast uses of the malloc call:
137 /// 0: PointerType is the malloc calls' return type.
138 /// 1: PointerType is the bitcast's result type.
139 /// >1: Unique PointerType cannot be determined, return NULL.
140 Type *getMallocAllocatedType(const CallInst *CI, const TargetLibraryInfo *TLI);
141
142 /// getMallocArraySize - Returns the array size of a malloc call. If the
143 /// argument passed to malloc is a multiple of the size of the malloced type,
144 /// then return that multiple. For non-array mallocs, the multiple is
145 /// constant 1. Otherwise, return NULL for mallocs whose array size cannot be
146 /// determined.
147 Value *getMallocArraySize(CallInst *CI, const DataLayout &DL,
148 const TargetLibraryInfo *TLI,
149 bool LookThroughSExt = false);
150
151 //===----------------------------------------------------------------------===//
152 // calloc Call Utility Functions.
153 //
154
155 /// extractCallocCall - Returns the corresponding CallInst if the instruction
156 /// is a calloc call.
157 const CallInst *extractCallocCall(const Value *I, const TargetLibraryInfo *TLI);
extractCallocCall(Value * I,const TargetLibraryInfo * TLI)158 inline CallInst *extractCallocCall(Value *I, const TargetLibraryInfo *TLI) {
159 return const_cast<CallInst*>(extractCallocCall((const Value*)I, TLI));
160 }
161
162
163 //===----------------------------------------------------------------------===//
164 // free Call Utility Functions.
165 //
166
167 /// isLibFreeFunction - Returns true if the function is a builtin free()
168 bool isLibFreeFunction(const Function *F, const LibFunc TLIFn);
169
170 /// isFreeCall - Returns non-null if the value is a call to the builtin free()
171 const CallInst *isFreeCall(const Value *I, const TargetLibraryInfo *TLI);
172
isFreeCall(Value * I,const TargetLibraryInfo * TLI)173 inline CallInst *isFreeCall(Value *I, const TargetLibraryInfo *TLI) {
174 return const_cast<CallInst*>(isFreeCall((const Value*)I, TLI));
175 }
176
177 //===----------------------------------------------------------------------===//
178 // Utility functions to compute size of objects.
179 //
180
181 /// Various options to control the behavior of getObjectSize.
182 struct ObjectSizeOpts {
183 /// Controls how we handle conditional statements with unknown conditions.
184 enum class Mode : uint8_t {
185 /// Fail to evaluate an unknown condition.
186 Exact,
187 /// Evaluate all branches of an unknown condition. If all evaluations
188 /// succeed, pick the minimum size.
189 Min,
190 /// Same as Min, except we pick the maximum size of all of the branches.
191 Max
192 };
193
194 /// How we want to evaluate this object's size.
195 Mode EvalMode = Mode::Exact;
196 /// Whether to round the result up to the alignment of allocas, byval
197 /// arguments, and global variables.
198 bool RoundToAlign = false;
199 /// If this is true, null pointers in address space 0 will be treated as
200 /// though they can't be evaluated. Otherwise, null is always considered to
201 /// point to a 0 byte region of memory.
202 bool NullIsUnknownSize = false;
203 };
204
205 /// Compute the size of the object pointed by Ptr. Returns true and the
206 /// object size in Size if successful, and false otherwise. In this context, by
207 /// object we mean the region of memory starting at Ptr to the end of the
208 /// underlying object pointed to by Ptr.
209 bool getObjectSize(const Value *Ptr, uint64_t &Size, const DataLayout &DL,
210 const TargetLibraryInfo *TLI, ObjectSizeOpts Opts = {});
211
212 /// Try to turn a call to \@llvm.objectsize into an integer value of the given
213 /// Type. Returns null on failure. If MustSucceed is true, this function will
214 /// not return null, and may return conservative values governed by the second
215 /// argument of the call to objectsize.
216 Value *lowerObjectSizeCall(IntrinsicInst *ObjectSize, const DataLayout &DL,
217 const TargetLibraryInfo *TLI, bool MustSucceed);
218
219
220
221 using SizeOffsetType = std::pair<APInt, APInt>;
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, SizeOffsetType> {
227 const DataLayout &DL;
228 const TargetLibraryInfo *TLI;
229 ObjectSizeOpts Options;
230 unsigned IntTyBits;
231 APInt Zero;
232 SmallPtrSet<Instruction *, 8> SeenInsts;
233
234 APInt align(APInt Size, uint64_t Align);
235
unknown()236 SizeOffsetType unknown() {
237 return std::make_pair(APInt(), APInt());
238 }
239
240 public:
241 ObjectSizeOffsetVisitor(const DataLayout &DL, const TargetLibraryInfo *TLI,
242 LLVMContext &Context, ObjectSizeOpts Options = {});
243
244 SizeOffsetType compute(Value *V);
245
knownSize(const SizeOffsetType & SizeOffset)246 static bool knownSize(const SizeOffsetType &SizeOffset) {
247 return SizeOffset.first.getBitWidth() > 1;
248 }
249
knownOffset(const SizeOffsetType & SizeOffset)250 static bool knownOffset(const SizeOffsetType &SizeOffset) {
251 return SizeOffset.second.getBitWidth() > 1;
252 }
253
bothKnown(const SizeOffsetType & SizeOffset)254 static bool bothKnown(const SizeOffsetType &SizeOffset) {
255 return knownSize(SizeOffset) && knownOffset(SizeOffset);
256 }
257
258 // These are "private", except they can't actually be made private. Only
259 // compute() should be used by external users.
260 SizeOffsetType visitAllocaInst(AllocaInst &I);
261 SizeOffsetType visitArgument(Argument &A);
262 SizeOffsetType visitCallSite(CallSite CS);
263 SizeOffsetType visitConstantPointerNull(ConstantPointerNull&);
264 SizeOffsetType visitExtractElementInst(ExtractElementInst &I);
265 SizeOffsetType visitExtractValueInst(ExtractValueInst &I);
266 SizeOffsetType visitGEPOperator(GEPOperator &GEP);
267 SizeOffsetType visitGlobalAlias(GlobalAlias &GA);
268 SizeOffsetType visitGlobalVariable(GlobalVariable &GV);
269 SizeOffsetType visitIntToPtrInst(IntToPtrInst&);
270 SizeOffsetType visitLoadInst(LoadInst &I);
271 SizeOffsetType visitPHINode(PHINode&);
272 SizeOffsetType visitSelectInst(SelectInst &I);
273 SizeOffsetType visitUndefValue(UndefValue&);
274 SizeOffsetType visitInstruction(Instruction &I);
275
276 private:
277 bool CheckedZextOrTrunc(APInt &I);
278 };
279
280 using SizeOffsetEvalType = std::pair<Value *, Value *>;
281
282 /// Evaluate the size and offset of an object pointed to by a Value*.
283 /// May create code to compute the result at run-time.
284 class ObjectSizeOffsetEvaluator
285 : public InstVisitor<ObjectSizeOffsetEvaluator, SizeOffsetEvalType> {
286 using BuilderTy = IRBuilder<TargetFolder, IRBuilderCallbackInserter>;
287 using WeakEvalType = std::pair<WeakTrackingVH, WeakTrackingVH>;
288 using CacheMapTy = DenseMap<const Value *, WeakEvalType>;
289 using PtrSetTy = SmallPtrSet<const Value *, 8>;
290
291 const DataLayout &DL;
292 const TargetLibraryInfo *TLI;
293 LLVMContext &Context;
294 BuilderTy Builder;
295 IntegerType *IntTy;
296 Value *Zero;
297 CacheMapTy CacheMap;
298 PtrSetTy SeenVals;
299 ObjectSizeOpts EvalOpts;
300 SmallPtrSet<Instruction *, 8> InsertedInstructions;
301
302 SizeOffsetEvalType compute_(Value *V);
303
304 public:
unknown()305 static SizeOffsetEvalType unknown() {
306 return std::make_pair(nullptr, nullptr);
307 }
308
309 ObjectSizeOffsetEvaluator(const DataLayout &DL, const TargetLibraryInfo *TLI,
310 LLVMContext &Context, ObjectSizeOpts EvalOpts = {});
311
312 SizeOffsetEvalType compute(Value *V);
313
knownSize(SizeOffsetEvalType SizeOffset)314 bool knownSize(SizeOffsetEvalType SizeOffset) {
315 return SizeOffset.first;
316 }
317
knownOffset(SizeOffsetEvalType SizeOffset)318 bool knownOffset(SizeOffsetEvalType SizeOffset) {
319 return SizeOffset.second;
320 }
321
anyKnown(SizeOffsetEvalType SizeOffset)322 bool anyKnown(SizeOffsetEvalType SizeOffset) {
323 return knownSize(SizeOffset) || knownOffset(SizeOffset);
324 }
325
bothKnown(SizeOffsetEvalType SizeOffset)326 bool bothKnown(SizeOffsetEvalType SizeOffset) {
327 return knownSize(SizeOffset) && knownOffset(SizeOffset);
328 }
329
330 // The individual instruction visitors should be treated as private.
331 SizeOffsetEvalType visitAllocaInst(AllocaInst &I);
332 SizeOffsetEvalType visitCallSite(CallSite CS);
333 SizeOffsetEvalType visitExtractElementInst(ExtractElementInst &I);
334 SizeOffsetEvalType visitExtractValueInst(ExtractValueInst &I);
335 SizeOffsetEvalType visitGEPOperator(GEPOperator &GEP);
336 SizeOffsetEvalType visitIntToPtrInst(IntToPtrInst&);
337 SizeOffsetEvalType visitLoadInst(LoadInst &I);
338 SizeOffsetEvalType visitPHINode(PHINode &PHI);
339 SizeOffsetEvalType visitSelectInst(SelectInst &I);
340 SizeOffsetEvalType visitInstruction(Instruction &I);
341 };
342
343 } // end namespace llvm
344
345 #endif // LLVM_ANALYSIS_MEMORYBUILTINS_H
346