1 //===- MemoryBuiltins.cpp - Identify calls to memory builtins -------------===//
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 #include "llvm/Analysis/MemoryBuiltins.h"
15 #include "llvm/ADT/APInt.h"
16 #include "llvm/ADT/None.h"
17 #include "llvm/ADT/Optional.h"
18 #include "llvm/ADT/STLExtras.h"
19 #include "llvm/ADT/Statistic.h"
20 #include "llvm/ADT/StringRef.h"
21 #include "llvm/Analysis/TargetFolder.h"
22 #include "llvm/Analysis/TargetLibraryInfo.h"
23 #include "llvm/Analysis/Utils/Local.h"
24 #include "llvm/Analysis/ValueTracking.h"
25 #include "llvm/IR/Argument.h"
26 #include "llvm/IR/Attributes.h"
27 #include "llvm/IR/Constants.h"
28 #include "llvm/IR/DataLayout.h"
29 #include "llvm/IR/DerivedTypes.h"
30 #include "llvm/IR/Function.h"
31 #include "llvm/IR/GlobalAlias.h"
32 #include "llvm/IR/GlobalVariable.h"
33 #include "llvm/IR/Instruction.h"
34 #include "llvm/IR/Instructions.h"
35 #include "llvm/IR/IntrinsicInst.h"
36 #include "llvm/IR/Operator.h"
37 #include "llvm/IR/Type.h"
38 #include "llvm/IR/Value.h"
39 #include "llvm/Support/Casting.h"
40 #include "llvm/Support/Debug.h"
41 #include "llvm/Support/MathExtras.h"
42 #include "llvm/Support/raw_ostream.h"
43 #include <cassert>
44 #include <cstdint>
45 #include <iterator>
46 #include <utility>
47
48 using namespace llvm;
49
50 #define DEBUG_TYPE "memory-builtins"
51
52 enum AllocType : uint8_t {
53 OpNewLike = 1<<0, // allocates; never returns null
54 MallocLike = 1<<1 | OpNewLike, // allocates; may return null
55 AlignedAllocLike = 1<<2, // allocates with alignment; may return null
56 CallocLike = 1<<3, // allocates + bzero
57 ReallocLike = 1<<4, // reallocates
58 StrDupLike = 1<<5,
59 MallocOrCallocLike = MallocLike | CallocLike | AlignedAllocLike,
60 AllocLike = MallocOrCallocLike | StrDupLike,
61 AnyAlloc = AllocLike | ReallocLike
62 };
63
64 struct AllocFnsTy {
65 AllocType AllocTy;
66 unsigned NumParams;
67 // First and Second size parameters (or -1 if unused)
68 int FstParam, SndParam;
69 };
70
71 // FIXME: certain users need more information. E.g., SimplifyLibCalls needs to
72 // know which functions are nounwind, noalias, nocapture parameters, etc.
73 static const std::pair<LibFunc, AllocFnsTy> AllocationFnData[] = {
74 {LibFunc_malloc, {MallocLike, 1, 0, -1}},
75 {LibFunc_vec_malloc, {MallocLike, 1, 0, -1}},
76 {LibFunc_valloc, {MallocLike, 1, 0, -1}},
77 {LibFunc_Znwj, {OpNewLike, 1, 0, -1}}, // new(unsigned int)
78 {LibFunc_ZnwjRKSt9nothrow_t, {MallocLike, 2, 0, -1}}, // new(unsigned int, nothrow)
79 {LibFunc_ZnwjSt11align_val_t, {OpNewLike, 2, 0, -1}}, // new(unsigned int, align_val_t)
80 {LibFunc_ZnwjSt11align_val_tRKSt9nothrow_t, // new(unsigned int, align_val_t, nothrow)
81 {MallocLike, 3, 0, -1}},
82 {LibFunc_Znwm, {OpNewLike, 1, 0, -1}}, // new(unsigned long)
83 {LibFunc_ZnwmRKSt9nothrow_t, {MallocLike, 2, 0, -1}}, // new(unsigned long, nothrow)
84 {LibFunc_ZnwmSt11align_val_t, {OpNewLike, 2, 0, -1}}, // new(unsigned long, align_val_t)
85 {LibFunc_ZnwmSt11align_val_tRKSt9nothrow_t, // new(unsigned long, align_val_t, nothrow)
86 {MallocLike, 3, 0, -1}},
87 {LibFunc_Znaj, {OpNewLike, 1, 0, -1}}, // new[](unsigned int)
88 {LibFunc_ZnajRKSt9nothrow_t, {MallocLike, 2, 0, -1}}, // new[](unsigned int, nothrow)
89 {LibFunc_ZnajSt11align_val_t, {OpNewLike, 2, 0, -1}}, // new[](unsigned int, align_val_t)
90 {LibFunc_ZnajSt11align_val_tRKSt9nothrow_t, // new[](unsigned int, align_val_t, nothrow)
91 {MallocLike, 3, 0, -1}},
92 {LibFunc_Znam, {OpNewLike, 1, 0, -1}}, // new[](unsigned long)
93 {LibFunc_ZnamRKSt9nothrow_t, {MallocLike, 2, 0, -1}}, // new[](unsigned long, nothrow)
94 {LibFunc_ZnamSt11align_val_t, {OpNewLike, 2, 0, -1}}, // new[](unsigned long, align_val_t)
95 {LibFunc_ZnamSt11align_val_tRKSt9nothrow_t, // new[](unsigned long, align_val_t, nothrow)
96 {MallocLike, 3, 0, -1}},
97 {LibFunc_msvc_new_int, {OpNewLike, 1, 0, -1}}, // new(unsigned int)
98 {LibFunc_msvc_new_int_nothrow, {MallocLike, 2, 0, -1}}, // new(unsigned int, nothrow)
99 {LibFunc_msvc_new_longlong, {OpNewLike, 1, 0, -1}}, // new(unsigned long long)
100 {LibFunc_msvc_new_longlong_nothrow, {MallocLike, 2, 0, -1}}, // new(unsigned long long, nothrow)
101 {LibFunc_msvc_new_array_int, {OpNewLike, 1, 0, -1}}, // new[](unsigned int)
102 {LibFunc_msvc_new_array_int_nothrow, {MallocLike, 2, 0, -1}}, // new[](unsigned int, nothrow)
103 {LibFunc_msvc_new_array_longlong, {OpNewLike, 1, 0, -1}}, // new[](unsigned long long)
104 {LibFunc_msvc_new_array_longlong_nothrow, {MallocLike, 2, 0, -1}}, // new[](unsigned long long, nothrow)
105 {LibFunc_aligned_alloc, {AlignedAllocLike, 2, 1, -1}},
106 {LibFunc_memalign, {AlignedAllocLike, 2, 1, -1}},
107 {LibFunc_calloc, {CallocLike, 2, 0, 1}},
108 {LibFunc_vec_calloc, {CallocLike, 2, 0, 1}},
109 {LibFunc_realloc, {ReallocLike, 2, 1, -1}},
110 {LibFunc_vec_realloc, {ReallocLike, 2, 1, -1}},
111 {LibFunc_reallocf, {ReallocLike, 2, 1, -1}},
112 {LibFunc_strdup, {StrDupLike, 1, -1, -1}},
113 {LibFunc_strndup, {StrDupLike, 2, 1, -1}},
114 {LibFunc___kmpc_alloc_shared, {MallocLike, 1, 0, -1}},
115
116 {LibFunc_rust_alloc, {MallocLike, 2, 0, -1}},
117 {LibFunc_rust_realloc, {ReallocLike, 4, 3, -1}},
118 // TODO: Handle "int posix_memalign(void **, size_t, size_t)"
119 };
120
getCalledFunction(const Value * V,bool LookThroughBitCast,bool & IsNoBuiltin)121 static const Function *getCalledFunction(const Value *V, bool LookThroughBitCast,
122 bool &IsNoBuiltin) {
123 // Don't care about intrinsics in this case.
124 if (isa<IntrinsicInst>(V))
125 return nullptr;
126
127 if (LookThroughBitCast)
128 V = V->stripPointerCasts();
129
130 const auto *CB = dyn_cast<CallBase>(V);
131 if (!CB)
132 return nullptr;
133
134 IsNoBuiltin = CB->isNoBuiltin();
135
136 if (const Function *Callee = CB->getCalledFunction())
137 return Callee;
138 return nullptr;
139 }
140
141 /// Returns the allocation data for the given value if it's either a call to a
142 /// known allocation function, or a call to a function with the allocsize
143 /// attribute.
144 static Optional<AllocFnsTy>
getAllocationDataForFunction(const Function * Callee,AllocType AllocTy,const TargetLibraryInfo * TLI)145 getAllocationDataForFunction(const Function *Callee, AllocType AllocTy,
146 const TargetLibraryInfo *TLI) {
147 // Make sure that the function is available.
148 LibFunc TLIFn;
149 if (!TLI || !TLI->getLibFunc(*Callee, TLIFn) || !TLI->has(TLIFn))
150 return None;
151
152 const auto *Iter = find_if(
153 AllocationFnData, [TLIFn](const std::pair<LibFunc, AllocFnsTy> &P) {
154 return P.first == TLIFn;
155 });
156
157 if (Iter == std::end(AllocationFnData))
158 return None;
159
160 const AllocFnsTy *FnData = &Iter->second;
161 if ((FnData->AllocTy & AllocTy) != FnData->AllocTy)
162 return None;
163
164 // Check function prototype.
165 int FstParam = FnData->FstParam;
166 int SndParam = FnData->SndParam;
167 FunctionType *FTy = Callee->getFunctionType();
168
169 if (FTy->getReturnType() == Type::getInt8PtrTy(FTy->getContext()) &&
170 FTy->getNumParams() == FnData->NumParams &&
171 (FstParam < 0 ||
172 (FTy->getParamType(FstParam)->isIntegerTy(32) ||
173 FTy->getParamType(FstParam)->isIntegerTy(64))) &&
174 (SndParam < 0 ||
175 FTy->getParamType(SndParam)->isIntegerTy(32) ||
176 FTy->getParamType(SndParam)->isIntegerTy(64)))
177 return *FnData;
178 return None;
179 }
180
getAllocationData(const Value * V,AllocType AllocTy,const TargetLibraryInfo * TLI,bool LookThroughBitCast=false)181 static Optional<AllocFnsTy> getAllocationData(const Value *V, AllocType AllocTy,
182 const TargetLibraryInfo *TLI,
183 bool LookThroughBitCast = false) {
184 bool IsNoBuiltinCall;
185 if (const Function *Callee =
186 getCalledFunction(V, LookThroughBitCast, IsNoBuiltinCall))
187 if (!IsNoBuiltinCall)
188 return getAllocationDataForFunction(Callee, AllocTy, TLI);
189 return None;
190 }
191
192 static Optional<AllocFnsTy>
getAllocationData(const Value * V,AllocType AllocTy,function_ref<const TargetLibraryInfo & (Function &)> GetTLI,bool LookThroughBitCast=false)193 getAllocationData(const Value *V, AllocType AllocTy,
194 function_ref<const TargetLibraryInfo &(Function &)> GetTLI,
195 bool LookThroughBitCast = false) {
196 bool IsNoBuiltinCall;
197 if (const Function *Callee =
198 getCalledFunction(V, LookThroughBitCast, IsNoBuiltinCall))
199 if (!IsNoBuiltinCall)
200 return getAllocationDataForFunction(
201 Callee, AllocTy, &GetTLI(const_cast<Function &>(*Callee)));
202 return None;
203 }
204
getAllocationSize(const Value * V,const TargetLibraryInfo * TLI)205 static Optional<AllocFnsTy> getAllocationSize(const Value *V,
206 const TargetLibraryInfo *TLI) {
207 bool IsNoBuiltinCall;
208 const Function *Callee =
209 getCalledFunction(V, /*LookThroughBitCast=*/false, IsNoBuiltinCall);
210 if (!Callee)
211 return None;
212
213 // Prefer to use existing information over allocsize. This will give us an
214 // accurate AllocTy.
215 if (!IsNoBuiltinCall)
216 if (Optional<AllocFnsTy> Data =
217 getAllocationDataForFunction(Callee, AnyAlloc, TLI))
218 return Data;
219
220 Attribute Attr = Callee->getFnAttribute(Attribute::AllocSize);
221 if (Attr == Attribute())
222 return None;
223
224 std::pair<unsigned, Optional<unsigned>> Args = Attr.getAllocSizeArgs();
225
226 AllocFnsTy Result;
227 // Because allocsize only tells us how many bytes are allocated, we're not
228 // really allowed to assume anything, so we use MallocLike.
229 Result.AllocTy = MallocLike;
230 Result.NumParams = Callee->getNumOperands();
231 Result.FstParam = Args.first;
232 Result.SndParam = Args.second.getValueOr(-1);
233 return Result;
234 }
235
hasNoAliasAttr(const Value * V,bool LookThroughBitCast)236 static bool hasNoAliasAttr(const Value *V, bool LookThroughBitCast) {
237 const auto *CB =
238 dyn_cast<CallBase>(LookThroughBitCast ? V->stripPointerCasts() : V);
239 return CB && CB->hasRetAttr(Attribute::NoAlias);
240 }
241
242 /// Tests if a value is a call or invoke to a library function that
243 /// allocates or reallocates memory (either malloc, calloc, realloc, or strdup
244 /// like).
isAllocationFn(const Value * V,const TargetLibraryInfo * TLI,bool LookThroughBitCast)245 bool llvm::isAllocationFn(const Value *V, const TargetLibraryInfo *TLI,
246 bool LookThroughBitCast) {
247 return getAllocationData(V, AnyAlloc, TLI, LookThroughBitCast).hasValue();
248 }
isAllocationFn(const Value * V,function_ref<const TargetLibraryInfo & (Function &)> GetTLI,bool LookThroughBitCast)249 bool llvm::isAllocationFn(
250 const Value *V, function_ref<const TargetLibraryInfo &(Function &)> GetTLI,
251 bool LookThroughBitCast) {
252 return getAllocationData(V, AnyAlloc, GetTLI, LookThroughBitCast).hasValue();
253 }
254
255 /// Tests if a value is a call or invoke to a function that returns a
256 /// NoAlias pointer (including malloc/calloc/realloc/strdup-like functions).
isNoAliasFn(const Value * V,const TargetLibraryInfo * TLI,bool LookThroughBitCast)257 bool llvm::isNoAliasFn(const Value *V, const TargetLibraryInfo *TLI,
258 bool LookThroughBitCast) {
259 // it's safe to consider realloc as noalias since accessing the original
260 // pointer is undefined behavior
261 return isAllocationFn(V, TLI, LookThroughBitCast) ||
262 hasNoAliasAttr(V, LookThroughBitCast);
263 }
264
265 /// Tests if a value is a call or invoke to a library function that
266 /// allocates uninitialized memory (such as malloc).
isMallocLikeFn(const Value * V,const TargetLibraryInfo * TLI,bool LookThroughBitCast)267 bool llvm::isMallocLikeFn(const Value *V, const TargetLibraryInfo *TLI,
268 bool LookThroughBitCast) {
269 return getAllocationData(V, MallocLike, TLI, LookThroughBitCast).hasValue();
270 }
isMallocLikeFn(const Value * V,function_ref<const TargetLibraryInfo & (Function &)> GetTLI,bool LookThroughBitCast)271 bool llvm::isMallocLikeFn(
272 const Value *V, function_ref<const TargetLibraryInfo &(Function &)> GetTLI,
273 bool LookThroughBitCast) {
274 return getAllocationData(V, MallocLike, GetTLI, LookThroughBitCast)
275 .hasValue();
276 }
277
278 /// Tests if a value is a call or invoke to a library function that
279 /// allocates uninitialized memory with alignment (such as aligned_alloc).
isAlignedAllocLikeFn(const Value * V,const TargetLibraryInfo * TLI,bool LookThroughBitCast)280 bool llvm::isAlignedAllocLikeFn(const Value *V, const TargetLibraryInfo *TLI,
281 bool LookThroughBitCast) {
282 return getAllocationData(V, AlignedAllocLike, TLI, LookThroughBitCast)
283 .hasValue();
284 }
isAlignedAllocLikeFn(const Value * V,function_ref<const TargetLibraryInfo & (Function &)> GetTLI,bool LookThroughBitCast)285 bool llvm::isAlignedAllocLikeFn(
286 const Value *V, function_ref<const TargetLibraryInfo &(Function &)> GetTLI,
287 bool LookThroughBitCast) {
288 return getAllocationData(V, AlignedAllocLike, GetTLI, LookThroughBitCast)
289 .hasValue();
290 }
291
292 /// Tests if a value is a call or invoke to a library function that
293 /// allocates zero-filled memory (such as calloc).
isCallocLikeFn(const Value * V,const TargetLibraryInfo * TLI,bool LookThroughBitCast)294 bool llvm::isCallocLikeFn(const Value *V, const TargetLibraryInfo *TLI,
295 bool LookThroughBitCast) {
296 return getAllocationData(V, CallocLike, TLI, LookThroughBitCast).hasValue();
297 }
298
299 /// Tests if a value is a call or invoke to a library function that
300 /// allocates memory similar to malloc or calloc.
isMallocOrCallocLikeFn(const Value * V,const TargetLibraryInfo * TLI,bool LookThroughBitCast)301 bool llvm::isMallocOrCallocLikeFn(const Value *V, const TargetLibraryInfo *TLI,
302 bool LookThroughBitCast) {
303 return getAllocationData(V, MallocOrCallocLike, TLI,
304 LookThroughBitCast).hasValue();
305 }
306
307 /// Tests if a value is a call or invoke to a library function that
308 /// allocates memory (either malloc, calloc, or strdup like).
isAllocLikeFn(const Value * V,const TargetLibraryInfo * TLI,bool LookThroughBitCast)309 bool llvm::isAllocLikeFn(const Value *V, const TargetLibraryInfo *TLI,
310 bool LookThroughBitCast) {
311 return getAllocationData(V, AllocLike, TLI, LookThroughBitCast).hasValue();
312 }
313
314 /// Tests if a value is a call or invoke to a library function that
315 /// reallocates memory (e.g., realloc).
isReallocLikeFn(const Value * V,const TargetLibraryInfo * TLI,bool LookThroughBitCast)316 bool llvm::isReallocLikeFn(const Value *V, const TargetLibraryInfo *TLI,
317 bool LookThroughBitCast) {
318 return getAllocationData(V, ReallocLike, TLI, LookThroughBitCast).hasValue();
319 }
320
321 /// Tests if a functions is a call or invoke to a library function that
322 /// reallocates memory (e.g., realloc).
isReallocLikeFn(const Function * F,const TargetLibraryInfo * TLI)323 bool llvm::isReallocLikeFn(const Function *F, const TargetLibraryInfo *TLI) {
324 return getAllocationDataForFunction(F, ReallocLike, TLI).hasValue();
325 }
326
327 /// Tests if a value is a call or invoke to a library function that
328 /// allocates memory and throws if an allocation failed (e.g., new).
isOpNewLikeFn(const Value * V,const TargetLibraryInfo * TLI,bool LookThroughBitCast)329 bool llvm::isOpNewLikeFn(const Value *V, const TargetLibraryInfo *TLI,
330 bool LookThroughBitCast) {
331 return getAllocationData(V, OpNewLike, TLI, LookThroughBitCast).hasValue();
332 }
333
334 /// Tests if a value is a call or invoke to a library function that
335 /// allocates memory (strdup, strndup).
isStrdupLikeFn(const Value * V,const TargetLibraryInfo * TLI,bool LookThroughBitCast)336 bool llvm::isStrdupLikeFn(const Value *V, const TargetLibraryInfo *TLI,
337 bool LookThroughBitCast) {
338 return getAllocationData(V, StrDupLike, TLI, LookThroughBitCast).hasValue();
339 }
340
341 /// extractMallocCall - Returns the corresponding CallInst if the instruction
342 /// is a malloc call. Since CallInst::CreateMalloc() only creates calls, we
343 /// ignore InvokeInst here.
extractMallocCall(const Value * I,function_ref<const TargetLibraryInfo & (Function &)> GetTLI)344 const CallInst *llvm::extractMallocCall(
345 const Value *I,
346 function_ref<const TargetLibraryInfo &(Function &)> GetTLI) {
347 return isMallocLikeFn(I, GetTLI) ? dyn_cast<CallInst>(I) : nullptr;
348 }
349
computeArraySize(const CallInst * CI,const DataLayout & DL,const TargetLibraryInfo * TLI,bool LookThroughSExt=false)350 static Value *computeArraySize(const CallInst *CI, const DataLayout &DL,
351 const TargetLibraryInfo *TLI,
352 bool LookThroughSExt = false) {
353 if (!CI)
354 return nullptr;
355
356 // The size of the malloc's result type must be known to determine array size.
357 Type *T = getMallocAllocatedType(CI, TLI);
358 if (!T || !T->isSized())
359 return nullptr;
360
361 unsigned ElementSize = DL.getTypeAllocSize(T);
362 if (StructType *ST = dyn_cast<StructType>(T))
363 ElementSize = DL.getStructLayout(ST)->getSizeInBytes();
364
365 // If malloc call's arg can be determined to be a multiple of ElementSize,
366 // return the multiple. Otherwise, return NULL.
367 Value *MallocArg = CI->getArgOperand(0);
368 Value *Multiple = nullptr;
369 if (ComputeMultiple(MallocArg, ElementSize, Multiple, LookThroughSExt))
370 return Multiple;
371
372 return nullptr;
373 }
374
375 /// getMallocType - Returns the PointerType resulting from the malloc call.
376 /// The PointerType depends on the number of bitcast uses of the malloc call:
377 /// 0: PointerType is the calls' return type.
378 /// 1: PointerType is the bitcast's result type.
379 /// >1: Unique PointerType cannot be determined, return NULL.
getMallocType(const CallInst * CI,const TargetLibraryInfo * TLI)380 PointerType *llvm::getMallocType(const CallInst *CI,
381 const TargetLibraryInfo *TLI) {
382 assert(isMallocLikeFn(CI, TLI) && "getMallocType and not malloc call");
383
384 PointerType *MallocType = nullptr;
385 unsigned NumOfBitCastUses = 0;
386
387 // Determine if CallInst has a bitcast use.
388 for (const User *U : CI->users())
389 if (const BitCastInst *BCI = dyn_cast<BitCastInst>(U)) {
390 MallocType = cast<PointerType>(BCI->getDestTy());
391 NumOfBitCastUses++;
392 }
393
394 // Malloc call has 1 bitcast use, so type is the bitcast's destination type.
395 if (NumOfBitCastUses == 1)
396 return MallocType;
397
398 // Malloc call was not bitcast, so type is the malloc function's return type.
399 if (NumOfBitCastUses == 0)
400 return cast<PointerType>(CI->getType());
401
402 // Type could not be determined.
403 return nullptr;
404 }
405
406 /// getMallocAllocatedType - Returns the Type allocated by malloc call.
407 /// The Type depends on the number of bitcast uses of the malloc call:
408 /// 0: PointerType is the malloc calls' return type.
409 /// 1: PointerType is the bitcast's result type.
410 /// >1: Unique PointerType cannot be determined, return NULL.
getMallocAllocatedType(const CallInst * CI,const TargetLibraryInfo * TLI)411 Type *llvm::getMallocAllocatedType(const CallInst *CI,
412 const TargetLibraryInfo *TLI) {
413 PointerType *PT = getMallocType(CI, TLI);
414 return PT ? PT->getElementType() : nullptr;
415 }
416
417 /// getMallocArraySize - Returns the array size of a malloc call. If the
418 /// argument passed to malloc is a multiple of the size of the malloced type,
419 /// then return that multiple. For non-array mallocs, the multiple is
420 /// constant 1. Otherwise, return NULL for mallocs whose array size cannot be
421 /// determined.
getMallocArraySize(CallInst * CI,const DataLayout & DL,const TargetLibraryInfo * TLI,bool LookThroughSExt)422 Value *llvm::getMallocArraySize(CallInst *CI, const DataLayout &DL,
423 const TargetLibraryInfo *TLI,
424 bool LookThroughSExt) {
425 assert(isMallocLikeFn(CI, TLI) && "getMallocArraySize and not malloc call");
426 return computeArraySize(CI, DL, TLI, LookThroughSExt);
427 }
428
429 /// extractCallocCall - Returns the corresponding CallInst if the instruction
430 /// is a calloc call.
extractCallocCall(const Value * I,const TargetLibraryInfo * TLI)431 const CallInst *llvm::extractCallocCall(const Value *I,
432 const TargetLibraryInfo *TLI) {
433 return isCallocLikeFn(I, TLI) ? cast<CallInst>(I) : nullptr;
434 }
435
436 /// isLibFreeFunction - Returns true if the function is a builtin free()
isLibFreeFunction(const Function * F,const LibFunc TLIFn)437 bool llvm::isLibFreeFunction(const Function *F, const LibFunc TLIFn) {
438 unsigned ExpectedNumParams;
439 if (TLIFn == LibFunc_free ||
440 TLIFn == LibFunc_ZdlPv || // operator delete(void*)
441 TLIFn == LibFunc_ZdaPv || // operator delete[](void*)
442 TLIFn == LibFunc_msvc_delete_ptr32 || // operator delete(void*)
443 TLIFn == LibFunc_msvc_delete_ptr64 || // operator delete(void*)
444 TLIFn == LibFunc_msvc_delete_array_ptr32 || // operator delete[](void*)
445 TLIFn == LibFunc_msvc_delete_array_ptr64) // operator delete[](void*)
446 ExpectedNumParams = 1;
447 else if (TLIFn == LibFunc_ZdlPvj || // delete(void*, uint)
448 TLIFn == LibFunc_ZdlPvm || // delete(void*, ulong)
449 TLIFn == LibFunc_ZdlPvRKSt9nothrow_t || // delete(void*, nothrow)
450 TLIFn == LibFunc_ZdlPvSt11align_val_t || // delete(void*, align_val_t)
451 TLIFn == LibFunc_ZdaPvj || // delete[](void*, uint)
452 TLIFn == LibFunc_ZdaPvm || // delete[](void*, ulong)
453 TLIFn == LibFunc_ZdaPvRKSt9nothrow_t || // delete[](void*, nothrow)
454 TLIFn == LibFunc_ZdaPvSt11align_val_t || // delete[](void*, align_val_t)
455 TLIFn == LibFunc_msvc_delete_ptr32_int || // delete(void*, uint)
456 TLIFn == LibFunc_msvc_delete_ptr64_longlong || // delete(void*, ulonglong)
457 TLIFn == LibFunc_msvc_delete_ptr32_nothrow || // delete(void*, nothrow)
458 TLIFn == LibFunc_msvc_delete_ptr64_nothrow || // delete(void*, nothrow)
459 TLIFn == LibFunc_msvc_delete_array_ptr32_int || // delete[](void*, uint)
460 TLIFn == LibFunc_msvc_delete_array_ptr64_longlong || // delete[](void*, ulonglong)
461 TLIFn == LibFunc_msvc_delete_array_ptr32_nothrow || // delete[](void*, nothrow)
462 TLIFn == LibFunc_msvc_delete_array_ptr64_nothrow || // delete[](void*, nothrow)
463 TLIFn == LibFunc___kmpc_free_shared) // OpenMP Offloading RTL free
464 ExpectedNumParams = 2;
465 else if (TLIFn == LibFunc_ZdaPvSt11align_val_tRKSt9nothrow_t || // delete(void*, align_val_t, nothrow)
466 TLIFn == LibFunc_ZdlPvSt11align_val_tRKSt9nothrow_t || // delete[](void*, align_val_t, nothrow)
467 TLIFn == LibFunc_ZdlPvjSt11align_val_t || // delete(void*, unsigned long, align_val_t)
468 TLIFn == LibFunc_ZdlPvmSt11align_val_t || // delete(void*, unsigned long, align_val_t)
469 TLIFn == LibFunc_ZdaPvjSt11align_val_t || // delete[](void*, unsigned int, align_val_t)
470 TLIFn == LibFunc_ZdaPvmSt11align_val_t || // delete[](void*, unsigned long, align_val_t)
471 TLIFn == LibFunc_rust_dealloc)
472 ExpectedNumParams = 3;
473 else
474 return false;
475
476 // Check free prototype.
477 // FIXME: workaround for PR5130, this will be obsolete when a nobuiltin
478 // attribute will exist.
479 FunctionType *FTy = F->getFunctionType();
480 if (!FTy->getReturnType()->isVoidTy())
481 return false;
482 if (FTy->getNumParams() != ExpectedNumParams)
483 return false;
484 if (FTy->getParamType(0) != Type::getInt8PtrTy(F->getContext()))
485 return false;
486
487 return true;
488 }
489
490 /// isFreeCall - Returns non-null if the value is a call to the builtin free()
isFreeCall(const Value * I,const TargetLibraryInfo * TLI)491 const CallInst *llvm::isFreeCall(const Value *I, const TargetLibraryInfo *TLI) {
492 bool IsNoBuiltinCall;
493 const Function *Callee =
494 getCalledFunction(I, /*LookThroughBitCast=*/false, IsNoBuiltinCall);
495 if (Callee == nullptr || IsNoBuiltinCall)
496 return nullptr;
497
498 LibFunc TLIFn;
499 if (!TLI || !TLI->getLibFunc(*Callee, TLIFn) || !TLI->has(TLIFn))
500 return nullptr;
501
502 return isLibFreeFunction(Callee, TLIFn) ? dyn_cast<CallInst>(I) : nullptr;
503 }
504
505
506 //===----------------------------------------------------------------------===//
507 // Utility functions to compute size of objects.
508 //
getSizeWithOverflow(const SizeOffsetType & Data)509 static APInt getSizeWithOverflow(const SizeOffsetType &Data) {
510 if (Data.second.isNegative() || Data.first.ult(Data.second))
511 return APInt(Data.first.getBitWidth(), 0);
512 return Data.first - Data.second;
513 }
514
515 /// Compute the size of the object pointed by Ptr. Returns true and the
516 /// object size in Size if successful, and false otherwise.
517 /// If RoundToAlign is true, then Size is rounded up to the alignment of
518 /// allocas, byval arguments, and global variables.
getObjectSize(const Value * Ptr,uint64_t & Size,const DataLayout & DL,const TargetLibraryInfo * TLI,ObjectSizeOpts Opts)519 bool llvm::getObjectSize(const Value *Ptr, uint64_t &Size, const DataLayout &DL,
520 const TargetLibraryInfo *TLI, ObjectSizeOpts Opts) {
521 ObjectSizeOffsetVisitor Visitor(DL, TLI, Ptr->getContext(), Opts);
522 SizeOffsetType Data = Visitor.compute(const_cast<Value*>(Ptr));
523 if (!Visitor.bothKnown(Data))
524 return false;
525
526 Size = getSizeWithOverflow(Data).getZExtValue();
527 return true;
528 }
529
lowerObjectSizeCall(IntrinsicInst * ObjectSize,const DataLayout & DL,const TargetLibraryInfo * TLI,bool MustSucceed)530 Value *llvm::lowerObjectSizeCall(IntrinsicInst *ObjectSize,
531 const DataLayout &DL,
532 const TargetLibraryInfo *TLI,
533 bool MustSucceed) {
534 assert(ObjectSize->getIntrinsicID() == Intrinsic::objectsize &&
535 "ObjectSize must be a call to llvm.objectsize!");
536
537 bool MaxVal = cast<ConstantInt>(ObjectSize->getArgOperand(1))->isZero();
538 ObjectSizeOpts EvalOptions;
539 // Unless we have to fold this to something, try to be as accurate as
540 // possible.
541 if (MustSucceed)
542 EvalOptions.EvalMode =
543 MaxVal ? ObjectSizeOpts::Mode::Max : ObjectSizeOpts::Mode::Min;
544 else
545 EvalOptions.EvalMode = ObjectSizeOpts::Mode::Exact;
546
547 EvalOptions.NullIsUnknownSize =
548 cast<ConstantInt>(ObjectSize->getArgOperand(2))->isOne();
549
550 auto *ResultType = cast<IntegerType>(ObjectSize->getType());
551 bool StaticOnly = cast<ConstantInt>(ObjectSize->getArgOperand(3))->isZero();
552 if (StaticOnly) {
553 // FIXME: Does it make sense to just return a failure value if the size won't
554 // fit in the output and `!MustSucceed`?
555 uint64_t Size;
556 if (getObjectSize(ObjectSize->getArgOperand(0), Size, DL, TLI, EvalOptions) &&
557 isUIntN(ResultType->getBitWidth(), Size))
558 return ConstantInt::get(ResultType, Size);
559 } else {
560 LLVMContext &Ctx = ObjectSize->getFunction()->getContext();
561 ObjectSizeOffsetEvaluator Eval(DL, TLI, Ctx, EvalOptions);
562 SizeOffsetEvalType SizeOffsetPair =
563 Eval.compute(ObjectSize->getArgOperand(0));
564
565 if (SizeOffsetPair != ObjectSizeOffsetEvaluator::unknown()) {
566 IRBuilder<TargetFolder> Builder(Ctx, TargetFolder(DL));
567 Builder.SetInsertPoint(ObjectSize);
568
569 // If we've outside the end of the object, then we can always access
570 // exactly 0 bytes.
571 Value *ResultSize =
572 Builder.CreateSub(SizeOffsetPair.first, SizeOffsetPair.second);
573 Value *UseZero =
574 Builder.CreateICmpULT(SizeOffsetPair.first, SizeOffsetPair.second);
575 ResultSize = Builder.CreateZExtOrTrunc(ResultSize, ResultType);
576 Value *Ret = Builder.CreateSelect(
577 UseZero, ConstantInt::get(ResultType, 0), ResultSize);
578
579 // The non-constant size expression cannot evaluate to -1.
580 if (!isa<Constant>(SizeOffsetPair.first) ||
581 !isa<Constant>(SizeOffsetPair.second))
582 Builder.CreateAssumption(
583 Builder.CreateICmpNE(Ret, ConstantInt::get(ResultType, -1)));
584
585 return Ret;
586 }
587 }
588
589 if (!MustSucceed)
590 return nullptr;
591
592 return ConstantInt::get(ResultType, MaxVal ? -1ULL : 0);
593 }
594
595 STATISTIC(ObjectVisitorArgument,
596 "Number of arguments with unsolved size and offset");
597 STATISTIC(ObjectVisitorLoad,
598 "Number of load instructions with unsolved size and offset");
599
align(APInt Size,uint64_t Alignment)600 APInt ObjectSizeOffsetVisitor::align(APInt Size, uint64_t Alignment) {
601 if (Options.RoundToAlign && Alignment)
602 return APInt(IntTyBits, alignTo(Size.getZExtValue(), Align(Alignment)));
603 return Size;
604 }
605
ObjectSizeOffsetVisitor(const DataLayout & DL,const TargetLibraryInfo * TLI,LLVMContext & Context,ObjectSizeOpts Options)606 ObjectSizeOffsetVisitor::ObjectSizeOffsetVisitor(const DataLayout &DL,
607 const TargetLibraryInfo *TLI,
608 LLVMContext &Context,
609 ObjectSizeOpts Options)
610 : DL(DL), TLI(TLI), Options(Options) {
611 // Pointer size must be rechecked for each object visited since it could have
612 // a different address space.
613 }
614
compute(Value * V)615 SizeOffsetType ObjectSizeOffsetVisitor::compute(Value *V) {
616 IntTyBits = DL.getIndexTypeSizeInBits(V->getType());
617 Zero = APInt::getNullValue(IntTyBits);
618
619 V = V->stripPointerCasts();
620 if (Instruction *I = dyn_cast<Instruction>(V)) {
621 // If we have already seen this instruction, bail out. Cycles can happen in
622 // unreachable code after constant propagation.
623 if (!SeenInsts.insert(I).second)
624 return unknown();
625
626 if (GEPOperator *GEP = dyn_cast<GEPOperator>(V))
627 return visitGEPOperator(*GEP);
628 return visit(*I);
629 }
630 if (Argument *A = dyn_cast<Argument>(V))
631 return visitArgument(*A);
632 if (ConstantPointerNull *P = dyn_cast<ConstantPointerNull>(V))
633 return visitConstantPointerNull(*P);
634 if (GlobalAlias *GA = dyn_cast<GlobalAlias>(V))
635 return visitGlobalAlias(*GA);
636 if (GlobalVariable *GV = dyn_cast<GlobalVariable>(V))
637 return visitGlobalVariable(*GV);
638 if (UndefValue *UV = dyn_cast<UndefValue>(V))
639 return visitUndefValue(*UV);
640 if (ConstantExpr *CE = dyn_cast<ConstantExpr>(V)) {
641 if (CE->getOpcode() == Instruction::IntToPtr)
642 return unknown(); // clueless
643 if (CE->getOpcode() == Instruction::GetElementPtr)
644 return visitGEPOperator(cast<GEPOperator>(*CE));
645 }
646
647 LLVM_DEBUG(dbgs() << "ObjectSizeOffsetVisitor::compute() unhandled value: "
648 << *V << '\n');
649 return unknown();
650 }
651
652 /// When we're compiling N-bit code, and the user uses parameters that are
653 /// greater than N bits (e.g. uint64_t on a 32-bit build), we can run into
654 /// trouble with APInt size issues. This function handles resizing + overflow
655 /// checks for us. Check and zext or trunc \p I depending on IntTyBits and
656 /// I's value.
CheckedZextOrTrunc(APInt & I)657 bool ObjectSizeOffsetVisitor::CheckedZextOrTrunc(APInt &I) {
658 // More bits than we can handle. Checking the bit width isn't necessary, but
659 // it's faster than checking active bits, and should give `false` in the
660 // vast majority of cases.
661 if (I.getBitWidth() > IntTyBits && I.getActiveBits() > IntTyBits)
662 return false;
663 if (I.getBitWidth() != IntTyBits)
664 I = I.zextOrTrunc(IntTyBits);
665 return true;
666 }
667
visitAllocaInst(AllocaInst & I)668 SizeOffsetType ObjectSizeOffsetVisitor::visitAllocaInst(AllocaInst &I) {
669 if (!I.getAllocatedType()->isSized())
670 return unknown();
671
672 if (isa<ScalableVectorType>(I.getAllocatedType()))
673 return unknown();
674
675 APInt Size(IntTyBits, DL.getTypeAllocSize(I.getAllocatedType()));
676 if (!I.isArrayAllocation())
677 return std::make_pair(align(Size, I.getAlignment()), Zero);
678
679 Value *ArraySize = I.getArraySize();
680 if (const ConstantInt *C = dyn_cast<ConstantInt>(ArraySize)) {
681 APInt NumElems = C->getValue();
682 if (!CheckedZextOrTrunc(NumElems))
683 return unknown();
684
685 bool Overflow;
686 Size = Size.umul_ov(NumElems, Overflow);
687 return Overflow ? unknown() : std::make_pair(align(Size, I.getAlignment()),
688 Zero);
689 }
690 return unknown();
691 }
692
visitArgument(Argument & A)693 SizeOffsetType ObjectSizeOffsetVisitor::visitArgument(Argument &A) {
694 Type *MemoryTy = A.getPointeeInMemoryValueType();
695 // No interprocedural analysis is done at the moment.
696 if (!MemoryTy|| !MemoryTy->isSized()) {
697 ++ObjectVisitorArgument;
698 return unknown();
699 }
700
701 APInt Size(IntTyBits, DL.getTypeAllocSize(MemoryTy));
702 return std::make_pair(align(Size, A.getParamAlignment()), Zero);
703 }
704
visitCallBase(CallBase & CB)705 SizeOffsetType ObjectSizeOffsetVisitor::visitCallBase(CallBase &CB) {
706 Optional<AllocFnsTy> FnData = getAllocationSize(&CB, TLI);
707 if (!FnData)
708 return unknown();
709
710 // Handle strdup-like functions separately.
711 if (FnData->AllocTy == StrDupLike) {
712 APInt Size(IntTyBits, GetStringLength(CB.getArgOperand(0)));
713 if (!Size)
714 return unknown();
715
716 // Strndup limits strlen.
717 if (FnData->FstParam > 0) {
718 ConstantInt *Arg =
719 dyn_cast<ConstantInt>(CB.getArgOperand(FnData->FstParam));
720 if (!Arg)
721 return unknown();
722
723 APInt MaxSize = Arg->getValue().zextOrSelf(IntTyBits);
724 if (Size.ugt(MaxSize))
725 Size = MaxSize + 1;
726 }
727 return std::make_pair(Size, Zero);
728 }
729
730 ConstantInt *Arg = dyn_cast<ConstantInt>(CB.getArgOperand(FnData->FstParam));
731 if (!Arg)
732 return unknown();
733
734 APInt Size = Arg->getValue();
735 if (!CheckedZextOrTrunc(Size))
736 return unknown();
737
738 // Size is determined by just 1 parameter.
739 if (FnData->SndParam < 0)
740 return std::make_pair(Size, Zero);
741
742 Arg = dyn_cast<ConstantInt>(CB.getArgOperand(FnData->SndParam));
743 if (!Arg)
744 return unknown();
745
746 APInt NumElems = Arg->getValue();
747 if (!CheckedZextOrTrunc(NumElems))
748 return unknown();
749
750 bool Overflow;
751 Size = Size.umul_ov(NumElems, Overflow);
752 return Overflow ? unknown() : std::make_pair(Size, Zero);
753
754 // TODO: handle more standard functions (+ wchar cousins):
755 // - strdup / strndup
756 // - strcpy / strncpy
757 // - strcat / strncat
758 // - memcpy / memmove
759 // - strcat / strncat
760 // - memset
761 }
762
763 SizeOffsetType
visitConstantPointerNull(ConstantPointerNull & CPN)764 ObjectSizeOffsetVisitor::visitConstantPointerNull(ConstantPointerNull& CPN) {
765 // If null is unknown, there's nothing we can do. Additionally, non-zero
766 // address spaces can make use of null, so we don't presume to know anything
767 // about that.
768 //
769 // TODO: How should this work with address space casts? We currently just drop
770 // them on the floor, but it's unclear what we should do when a NULL from
771 // addrspace(1) gets casted to addrspace(0) (or vice-versa).
772 if (Options.NullIsUnknownSize || CPN.getType()->getAddressSpace())
773 return unknown();
774 return std::make_pair(Zero, Zero);
775 }
776
777 SizeOffsetType
visitExtractElementInst(ExtractElementInst &)778 ObjectSizeOffsetVisitor::visitExtractElementInst(ExtractElementInst&) {
779 return unknown();
780 }
781
782 SizeOffsetType
visitExtractValueInst(ExtractValueInst &)783 ObjectSizeOffsetVisitor::visitExtractValueInst(ExtractValueInst&) {
784 // Easy cases were already folded by previous passes.
785 return unknown();
786 }
787
visitGEPOperator(GEPOperator & GEP)788 SizeOffsetType ObjectSizeOffsetVisitor::visitGEPOperator(GEPOperator &GEP) {
789 SizeOffsetType PtrData = compute(GEP.getPointerOperand());
790 APInt Offset(DL.getIndexTypeSizeInBits(GEP.getPointerOperand()->getType()), 0);
791 if (!bothKnown(PtrData) || !GEP.accumulateConstantOffset(DL, Offset))
792 return unknown();
793
794 return std::make_pair(PtrData.first, PtrData.second + Offset);
795 }
796
visitGlobalAlias(GlobalAlias & GA)797 SizeOffsetType ObjectSizeOffsetVisitor::visitGlobalAlias(GlobalAlias &GA) {
798 if (GA.isInterposable())
799 return unknown();
800 return compute(GA.getAliasee());
801 }
802
visitGlobalVariable(GlobalVariable & GV)803 SizeOffsetType ObjectSizeOffsetVisitor::visitGlobalVariable(GlobalVariable &GV){
804 if (!GV.hasDefinitiveInitializer())
805 return unknown();
806
807 APInt Size(IntTyBits, DL.getTypeAllocSize(GV.getValueType()));
808 return std::make_pair(align(Size, GV.getAlignment()), Zero);
809 }
810
visitIntToPtrInst(IntToPtrInst &)811 SizeOffsetType ObjectSizeOffsetVisitor::visitIntToPtrInst(IntToPtrInst&) {
812 // clueless
813 return unknown();
814 }
815
visitLoadInst(LoadInst &)816 SizeOffsetType ObjectSizeOffsetVisitor::visitLoadInst(LoadInst&) {
817 ++ObjectVisitorLoad;
818 return unknown();
819 }
820
visitPHINode(PHINode &)821 SizeOffsetType ObjectSizeOffsetVisitor::visitPHINode(PHINode&) {
822 // too complex to analyze statically.
823 return unknown();
824 }
825
visitSelectInst(SelectInst & I)826 SizeOffsetType ObjectSizeOffsetVisitor::visitSelectInst(SelectInst &I) {
827 SizeOffsetType TrueSide = compute(I.getTrueValue());
828 SizeOffsetType FalseSide = compute(I.getFalseValue());
829 if (bothKnown(TrueSide) && bothKnown(FalseSide)) {
830 if (TrueSide == FalseSide) {
831 return TrueSide;
832 }
833
834 APInt TrueResult = getSizeWithOverflow(TrueSide);
835 APInt FalseResult = getSizeWithOverflow(FalseSide);
836
837 if (TrueResult == FalseResult) {
838 return TrueSide;
839 }
840 if (Options.EvalMode == ObjectSizeOpts::Mode::Min) {
841 if (TrueResult.slt(FalseResult))
842 return TrueSide;
843 return FalseSide;
844 }
845 if (Options.EvalMode == ObjectSizeOpts::Mode::Max) {
846 if (TrueResult.sgt(FalseResult))
847 return TrueSide;
848 return FalseSide;
849 }
850 }
851 return unknown();
852 }
853
visitUndefValue(UndefValue &)854 SizeOffsetType ObjectSizeOffsetVisitor::visitUndefValue(UndefValue&) {
855 return std::make_pair(Zero, Zero);
856 }
857
visitInstruction(Instruction & I)858 SizeOffsetType ObjectSizeOffsetVisitor::visitInstruction(Instruction &I) {
859 LLVM_DEBUG(dbgs() << "ObjectSizeOffsetVisitor unknown instruction:" << I
860 << '\n');
861 return unknown();
862 }
863
ObjectSizeOffsetEvaluator(const DataLayout & DL,const TargetLibraryInfo * TLI,LLVMContext & Context,ObjectSizeOpts EvalOpts)864 ObjectSizeOffsetEvaluator::ObjectSizeOffsetEvaluator(
865 const DataLayout &DL, const TargetLibraryInfo *TLI, LLVMContext &Context,
866 ObjectSizeOpts EvalOpts)
867 : DL(DL), TLI(TLI), Context(Context),
868 Builder(Context, TargetFolder(DL),
869 IRBuilderCallbackInserter(
870 [&](Instruction *I) { InsertedInstructions.insert(I); })),
871 EvalOpts(EvalOpts) {
872 // IntTy and Zero must be set for each compute() since the address space may
873 // be different for later objects.
874 }
875
compute(Value * V)876 SizeOffsetEvalType ObjectSizeOffsetEvaluator::compute(Value *V) {
877 // XXX - Are vectors of pointers possible here?
878 IntTy = cast<IntegerType>(DL.getIndexType(V->getType()));
879 Zero = ConstantInt::get(IntTy, 0);
880
881 SizeOffsetEvalType Result = compute_(V);
882
883 if (!bothKnown(Result)) {
884 // Erase everything that was computed in this iteration from the cache, so
885 // that no dangling references are left behind. We could be a bit smarter if
886 // we kept a dependency graph. It's probably not worth the complexity.
887 for (const Value *SeenVal : SeenVals) {
888 CacheMapTy::iterator CacheIt = CacheMap.find(SeenVal);
889 // non-computable results can be safely cached
890 if (CacheIt != CacheMap.end() && anyKnown(CacheIt->second))
891 CacheMap.erase(CacheIt);
892 }
893
894 // Erase any instructions we inserted as part of the traversal.
895 for (Instruction *I : InsertedInstructions) {
896 I->replaceAllUsesWith(UndefValue::get(I->getType()));
897 I->eraseFromParent();
898 }
899 }
900
901 SeenVals.clear();
902 InsertedInstructions.clear();
903 return Result;
904 }
905
compute_(Value * V)906 SizeOffsetEvalType ObjectSizeOffsetEvaluator::compute_(Value *V) {
907 ObjectSizeOffsetVisitor Visitor(DL, TLI, Context, EvalOpts);
908 SizeOffsetType Const = Visitor.compute(V);
909 if (Visitor.bothKnown(Const))
910 return std::make_pair(ConstantInt::get(Context, Const.first),
911 ConstantInt::get(Context, Const.second));
912
913 V = V->stripPointerCasts();
914
915 // Check cache.
916 CacheMapTy::iterator CacheIt = CacheMap.find(V);
917 if (CacheIt != CacheMap.end())
918 return CacheIt->second;
919
920 // Always generate code immediately before the instruction being
921 // processed, so that the generated code dominates the same BBs.
922 BuilderTy::InsertPointGuard Guard(Builder);
923 if (Instruction *I = dyn_cast<Instruction>(V))
924 Builder.SetInsertPoint(I);
925
926 // Now compute the size and offset.
927 SizeOffsetEvalType Result;
928
929 // Record the pointers that were handled in this run, so that they can be
930 // cleaned later if something fails. We also use this set to break cycles that
931 // can occur in dead code.
932 if (!SeenVals.insert(V).second) {
933 Result = unknown();
934 } else if (GEPOperator *GEP = dyn_cast<GEPOperator>(V)) {
935 Result = visitGEPOperator(*GEP);
936 } else if (Instruction *I = dyn_cast<Instruction>(V)) {
937 Result = visit(*I);
938 } else if (isa<Argument>(V) ||
939 (isa<ConstantExpr>(V) &&
940 cast<ConstantExpr>(V)->getOpcode() == Instruction::IntToPtr) ||
941 isa<GlobalAlias>(V) ||
942 isa<GlobalVariable>(V)) {
943 // Ignore values where we cannot do more than ObjectSizeVisitor.
944 Result = unknown();
945 } else {
946 LLVM_DEBUG(
947 dbgs() << "ObjectSizeOffsetEvaluator::compute() unhandled value: " << *V
948 << '\n');
949 Result = unknown();
950 }
951
952 // Don't reuse CacheIt since it may be invalid at this point.
953 CacheMap[V] = Result;
954 return Result;
955 }
956
visitAllocaInst(AllocaInst & I)957 SizeOffsetEvalType ObjectSizeOffsetEvaluator::visitAllocaInst(AllocaInst &I) {
958 if (!I.getAllocatedType()->isSized())
959 return unknown();
960
961 // must be a VLA
962 assert(I.isArrayAllocation());
963
964 // If needed, adjust the alloca's operand size to match the pointer size.
965 // Subsequent math operations expect the types to match.
966 Value *ArraySize = Builder.CreateZExtOrTrunc(
967 I.getArraySize(), DL.getIntPtrType(I.getContext()));
968 assert(ArraySize->getType() == Zero->getType() &&
969 "Expected zero constant to have pointer type");
970
971 Value *Size = ConstantInt::get(ArraySize->getType(),
972 DL.getTypeAllocSize(I.getAllocatedType()));
973 Size = Builder.CreateMul(Size, ArraySize);
974 return std::make_pair(Size, Zero);
975 }
976
visitCallBase(CallBase & CB)977 SizeOffsetEvalType ObjectSizeOffsetEvaluator::visitCallBase(CallBase &CB) {
978 Optional<AllocFnsTy> FnData = getAllocationSize(&CB, TLI);
979 if (!FnData)
980 return unknown();
981
982 // Handle strdup-like functions separately.
983 if (FnData->AllocTy == StrDupLike) {
984 // TODO
985 return unknown();
986 }
987
988 Value *FirstArg = CB.getArgOperand(FnData->FstParam);
989 FirstArg = Builder.CreateZExtOrTrunc(FirstArg, IntTy);
990 if (FnData->SndParam < 0)
991 return std::make_pair(FirstArg, Zero);
992
993 Value *SecondArg = CB.getArgOperand(FnData->SndParam);
994 SecondArg = Builder.CreateZExtOrTrunc(SecondArg, IntTy);
995 Value *Size = Builder.CreateMul(FirstArg, SecondArg);
996 return std::make_pair(Size, Zero);
997
998 // TODO: handle more standard functions (+ wchar cousins):
999 // - strdup / strndup
1000 // - strcpy / strncpy
1001 // - strcat / strncat
1002 // - memcpy / memmove
1003 // - strcat / strncat
1004 // - memset
1005 }
1006
1007 SizeOffsetEvalType
visitExtractElementInst(ExtractElementInst &)1008 ObjectSizeOffsetEvaluator::visitExtractElementInst(ExtractElementInst&) {
1009 return unknown();
1010 }
1011
1012 SizeOffsetEvalType
visitExtractValueInst(ExtractValueInst &)1013 ObjectSizeOffsetEvaluator::visitExtractValueInst(ExtractValueInst&) {
1014 return unknown();
1015 }
1016
1017 SizeOffsetEvalType
visitGEPOperator(GEPOperator & GEP)1018 ObjectSizeOffsetEvaluator::visitGEPOperator(GEPOperator &GEP) {
1019 SizeOffsetEvalType PtrData = compute_(GEP.getPointerOperand());
1020 if (!bothKnown(PtrData))
1021 return unknown();
1022
1023 Value *Offset = EmitGEPOffset(&Builder, DL, &GEP, /*NoAssumptions=*/true);
1024 Offset = Builder.CreateAdd(PtrData.second, Offset);
1025 return std::make_pair(PtrData.first, Offset);
1026 }
1027
visitIntToPtrInst(IntToPtrInst &)1028 SizeOffsetEvalType ObjectSizeOffsetEvaluator::visitIntToPtrInst(IntToPtrInst&) {
1029 // clueless
1030 return unknown();
1031 }
1032
visitLoadInst(LoadInst &)1033 SizeOffsetEvalType ObjectSizeOffsetEvaluator::visitLoadInst(LoadInst&) {
1034 return unknown();
1035 }
1036
visitPHINode(PHINode & PHI)1037 SizeOffsetEvalType ObjectSizeOffsetEvaluator::visitPHINode(PHINode &PHI) {
1038 // Create 2 PHIs: one for size and another for offset.
1039 PHINode *SizePHI = Builder.CreatePHI(IntTy, PHI.getNumIncomingValues());
1040 PHINode *OffsetPHI = Builder.CreatePHI(IntTy, PHI.getNumIncomingValues());
1041
1042 // Insert right away in the cache to handle recursive PHIs.
1043 CacheMap[&PHI] = std::make_pair(SizePHI, OffsetPHI);
1044
1045 // Compute offset/size for each PHI incoming pointer.
1046 for (unsigned i = 0, e = PHI.getNumIncomingValues(); i != e; ++i) {
1047 Builder.SetInsertPoint(&*PHI.getIncomingBlock(i)->getFirstInsertionPt());
1048 SizeOffsetEvalType EdgeData = compute_(PHI.getIncomingValue(i));
1049
1050 if (!bothKnown(EdgeData)) {
1051 OffsetPHI->replaceAllUsesWith(UndefValue::get(IntTy));
1052 OffsetPHI->eraseFromParent();
1053 InsertedInstructions.erase(OffsetPHI);
1054 SizePHI->replaceAllUsesWith(UndefValue::get(IntTy));
1055 SizePHI->eraseFromParent();
1056 InsertedInstructions.erase(SizePHI);
1057 return unknown();
1058 }
1059 SizePHI->addIncoming(EdgeData.first, PHI.getIncomingBlock(i));
1060 OffsetPHI->addIncoming(EdgeData.second, PHI.getIncomingBlock(i));
1061 }
1062
1063 Value *Size = SizePHI, *Offset = OffsetPHI;
1064 if (Value *Tmp = SizePHI->hasConstantValue()) {
1065 Size = Tmp;
1066 SizePHI->replaceAllUsesWith(Size);
1067 SizePHI->eraseFromParent();
1068 InsertedInstructions.erase(SizePHI);
1069 }
1070 if (Value *Tmp = OffsetPHI->hasConstantValue()) {
1071 Offset = Tmp;
1072 OffsetPHI->replaceAllUsesWith(Offset);
1073 OffsetPHI->eraseFromParent();
1074 InsertedInstructions.erase(OffsetPHI);
1075 }
1076 return std::make_pair(Size, Offset);
1077 }
1078
visitSelectInst(SelectInst & I)1079 SizeOffsetEvalType ObjectSizeOffsetEvaluator::visitSelectInst(SelectInst &I) {
1080 SizeOffsetEvalType TrueSide = compute_(I.getTrueValue());
1081 SizeOffsetEvalType FalseSide = compute_(I.getFalseValue());
1082
1083 if (!bothKnown(TrueSide) || !bothKnown(FalseSide))
1084 return unknown();
1085 if (TrueSide == FalseSide)
1086 return TrueSide;
1087
1088 Value *Size = Builder.CreateSelect(I.getCondition(), TrueSide.first,
1089 FalseSide.first);
1090 Value *Offset = Builder.CreateSelect(I.getCondition(), TrueSide.second,
1091 FalseSide.second);
1092 return std::make_pair(Size, Offset);
1093 }
1094
visitInstruction(Instruction & I)1095 SizeOffsetEvalType ObjectSizeOffsetEvaluator::visitInstruction(Instruction &I) {
1096 LLVM_DEBUG(dbgs() << "ObjectSizeOffsetEvaluator unknown instruction:" << I
1097 << '\n');
1098 return unknown();
1099 }
1100