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