LLVM 17.0.0git
MemoryBuiltins.cpp
Go to the documentation of this file.
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
15#include "llvm/ADT/APInt.h"
16#include "llvm/ADT/STLExtras.h"
17#include "llvm/ADT/Statistic.h"
23#include "llvm/IR/Argument.h"
24#include "llvm/IR/Attributes.h"
25#include "llvm/IR/Constants.h"
26#include "llvm/IR/DataLayout.h"
28#include "llvm/IR/Function.h"
29#include "llvm/IR/GlobalAlias.h"
31#include "llvm/IR/Instruction.h"
34#include "llvm/IR/Operator.h"
35#include "llvm/IR/Type.h"
36#include "llvm/IR/Value.h"
38#include "llvm/Support/Debug.h"
41#include <cassert>
42#include <cstdint>
43#include <iterator>
44#include <numeric>
45#include <optional>
46#include <type_traits>
47#include <utility>
48
49using namespace llvm;
50
51#define DEBUG_TYPE "memory-builtins"
52
53enum AllocType : uint8_t {
54 OpNewLike = 1<<0, // allocates; never returns null
55 MallocLike = 1<<1, // allocates; may return null
56 StrDupLike = 1<<2,
60};
61
62enum class MallocFamily {
63 Malloc,
64 CPPNew, // new(unsigned int)
65 CPPNewAligned, // new(unsigned int, align_val_t)
66 CPPNewArray, // new[](unsigned int)
67 CPPNewArrayAligned, // new[](unsigned long, align_val_t)
68 MSVCNew, // new(unsigned int)
69 MSVCArrayNew, // new[](unsigned int)
72};
73
75 switch (Family) {
77 return "malloc";
79 return "_Znwm";
81 return "_ZnwmSt11align_val_t";
83 return "_Znam";
85 return "_ZnamSt11align_val_t";
87 return "??2@YAPAXI@Z";
89 return "??_U@YAPAXI@Z";
91 return "vec_malloc";
93 return "__kmpc_alloc_shared";
94 }
95 llvm_unreachable("missing an alloc family");
96}
97
98struct AllocFnsTy {
100 unsigned NumParams;
101 // First and Second size parameters (or -1 if unused)
103 // Alignment parameter for aligned_alloc and aligned new
105 // Name of default allocator function to group malloc/free calls by family
107};
108
109// clang-format off
110// FIXME: certain users need more information. E.g., SimplifyLibCalls needs to
111// know which functions are nounwind, noalias, nocapture parameters, etc.
112static const std::pair<LibFunc, AllocFnsTy> AllocationFnData[] = {
113 {LibFunc_Znwj, {OpNewLike, 1, 0, -1, -1, MallocFamily::CPPNew}}, // new(unsigned int)
114 {LibFunc_ZnwjRKSt9nothrow_t, {MallocLike, 2, 0, -1, -1, MallocFamily::CPPNew}}, // new(unsigned int, nothrow)
115 {LibFunc_ZnwjSt11align_val_t, {OpNewLike, 2, 0, -1, 1, MallocFamily::CPPNewAligned}}, // new(unsigned int, align_val_t)
116 {LibFunc_ZnwjSt11align_val_tRKSt9nothrow_t, {MallocLike, 3, 0, -1, 1, MallocFamily::CPPNewAligned}}, // new(unsigned int, align_val_t, nothrow)
117 {LibFunc_Znwm, {OpNewLike, 1, 0, -1, -1, MallocFamily::CPPNew}}, // new(unsigned long)
118 {LibFunc_Znwm12__hot_cold_t, {OpNewLike, 2, 0, -1, -1, MallocFamily::CPPNew}}, // new(unsigned long, __hot_cold_t)
119 {LibFunc_ZnwmRKSt9nothrow_t, {MallocLike, 2, 0, -1, -1, MallocFamily::CPPNew}}, // new(unsigned long, nothrow)
120 {LibFunc_ZnwmRKSt9nothrow_t12__hot_cold_t, {MallocLike, 3, 0, -1, -1, MallocFamily::CPPNew}}, // new(unsigned long, nothrow, __hot_cold_t)
121 {LibFunc_ZnwmSt11align_val_t, {OpNewLike, 2, 0, -1, 1, MallocFamily::CPPNewAligned}}, // new(unsigned long, align_val_t)
122 {LibFunc_ZnwmSt11align_val_t12__hot_cold_t, {OpNewLike, 3, 0, -1, 1, MallocFamily::CPPNewAligned}}, // new(unsigned long, align_val_t, __hot_cold_t)
123 {LibFunc_ZnwmSt11align_val_tRKSt9nothrow_t, {MallocLike, 3, 0, -1, 1, MallocFamily::CPPNewAligned}}, // new(unsigned long, align_val_t, nothrow)
124 {LibFunc_ZnwmSt11align_val_tRKSt9nothrow_t12__hot_cold_t, {MallocLike, 4, 0, -1, 1, MallocFamily::CPPNewAligned}}, // new(unsigned long, align_val_t, nothrow, __hot_cold_t)
125 {LibFunc_Znaj, {OpNewLike, 1, 0, -1, -1, MallocFamily::CPPNewArray}}, // new[](unsigned int)
126 {LibFunc_ZnajRKSt9nothrow_t, {MallocLike, 2, 0, -1, -1, MallocFamily::CPPNewArray}}, // new[](unsigned int, nothrow)
127 {LibFunc_ZnajSt11align_val_t, {OpNewLike, 2, 0, -1, 1, MallocFamily::CPPNewArrayAligned}}, // new[](unsigned int, align_val_t)
128 {LibFunc_ZnajSt11align_val_tRKSt9nothrow_t, {MallocLike, 3, 0, -1, 1, MallocFamily::CPPNewArrayAligned}}, // new[](unsigned int, align_val_t, nothrow)
129 {LibFunc_Znam, {OpNewLike, 1, 0, -1, -1, MallocFamily::CPPNewArray}}, // new[](unsigned long)
130 {LibFunc_Znam12__hot_cold_t, {OpNewLike, 2, 0, -1, -1, MallocFamily::CPPNew}}, // new[](unsigned long, __hot_cold_t)
131 {LibFunc_ZnamRKSt9nothrow_t, {MallocLike, 2, 0, -1, -1, MallocFamily::CPPNewArray}}, // new[](unsigned long, nothrow)
132 {LibFunc_ZnamRKSt9nothrow_t12__hot_cold_t, {MallocLike, 3, 0, -1, -1, MallocFamily::CPPNew}}, // new[](unsigned long, nothrow, __hot_cold_t)
133 {LibFunc_ZnamSt11align_val_t, {OpNewLike, 2, 0, -1, 1, MallocFamily::CPPNewArrayAligned}}, // new[](unsigned long, align_val_t)
134 {LibFunc_ZnamSt11align_val_t12__hot_cold_t, {OpNewLike, 3, 0, -1, 1, MallocFamily::CPPNewAligned}}, // new[](unsigned long, align_val_t, __hot_cold_t)
135 {LibFunc_ZnamSt11align_val_tRKSt9nothrow_t, {MallocLike, 3, 0, -1, 1, MallocFamily::CPPNewArrayAligned}}, // new[](unsigned long, align_val_t, nothrow)
136 {LibFunc_ZnamSt11align_val_tRKSt9nothrow_t12__hot_cold_t, {MallocLike, 4, 0, -1, 1, MallocFamily::CPPNewAligned}}, // new[](unsigned long, align_val_t, nothrow, __hot_cold_t)
137 {LibFunc_msvc_new_int, {OpNewLike, 1, 0, -1, -1, MallocFamily::MSVCNew}}, // new(unsigned int)
138 {LibFunc_msvc_new_int_nothrow, {MallocLike, 2, 0, -1, -1, MallocFamily::MSVCNew}}, // new(unsigned int, nothrow)
139 {LibFunc_msvc_new_longlong, {OpNewLike, 1, 0, -1, -1, MallocFamily::MSVCNew}}, // new(unsigned long long)
140 {LibFunc_msvc_new_longlong_nothrow, {MallocLike, 2, 0, -1, -1, MallocFamily::MSVCNew}}, // new(unsigned long long, nothrow)
141 {LibFunc_msvc_new_array_int, {OpNewLike, 1, 0, -1, -1, MallocFamily::MSVCArrayNew}}, // new[](unsigned int)
142 {LibFunc_msvc_new_array_int_nothrow, {MallocLike, 2, 0, -1, -1, MallocFamily::MSVCArrayNew}}, // new[](unsigned int, nothrow)
143 {LibFunc_msvc_new_array_longlong, {OpNewLike, 1, 0, -1, -1, MallocFamily::MSVCArrayNew}}, // new[](unsigned long long)
144 {LibFunc_msvc_new_array_longlong_nothrow, {MallocLike, 2, 0, -1, -1, MallocFamily::MSVCArrayNew}}, // new[](unsigned long long, nothrow)
145 {LibFunc_strdup, {StrDupLike, 1, -1, -1, -1, MallocFamily::Malloc}},
146 {LibFunc_dunder_strdup, {StrDupLike, 1, -1, -1, -1, MallocFamily::Malloc}},
147 {LibFunc_strndup, {StrDupLike, 2, 1, -1, -1, MallocFamily::Malloc}},
148 {LibFunc_dunder_strndup, {StrDupLike, 2, 1, -1, -1, MallocFamily::Malloc}},
149 {LibFunc___kmpc_alloc_shared, {MallocLike, 1, 0, -1, -1, MallocFamily::KmpcAllocShared}},
150};
151// clang-format on
152
153static const Function *getCalledFunction(const Value *V,
154 bool &IsNoBuiltin) {
155 // Don't care about intrinsics in this case.
156 if (isa<IntrinsicInst>(V))
157 return nullptr;
158
159 const auto *CB = dyn_cast<CallBase>(V);
160 if (!CB)
161 return nullptr;
162
163 IsNoBuiltin = CB->isNoBuiltin();
164
165 if (const Function *Callee = CB->getCalledFunction())
166 return Callee;
167 return nullptr;
168}
169
170/// Returns the allocation data for the given value if it's a call to a known
171/// allocation function.
172static std::optional<AllocFnsTy>
174 const TargetLibraryInfo *TLI) {
175 // Don't perform a slow TLI lookup, if this function doesn't return a pointer
176 // and thus can't be an allocation function.
177 if (!Callee->getReturnType()->isPointerTy())
178 return std::nullopt;
179
180 // Make sure that the function is available.
181 LibFunc TLIFn;
182 if (!TLI || !TLI->getLibFunc(*Callee, TLIFn) || !TLI->has(TLIFn))
183 return std::nullopt;
184
185 const auto *Iter = find_if(
186 AllocationFnData, [TLIFn](const std::pair<LibFunc, AllocFnsTy> &P) {
187 return P.first == TLIFn;
188 });
189
190 if (Iter == std::end(AllocationFnData))
191 return std::nullopt;
192
193 const AllocFnsTy *FnData = &Iter->second;
194 if ((FnData->AllocTy & AllocTy) != FnData->AllocTy)
195 return std::nullopt;
196
197 // Check function prototype.
198 int FstParam = FnData->FstParam;
199 int SndParam = FnData->SndParam;
201
202 if (FTy->getReturnType()->isPointerTy() &&
203 FTy->getNumParams() == FnData->NumParams &&
204 (FstParam < 0 ||
205 (FTy->getParamType(FstParam)->isIntegerTy(32) ||
206 FTy->getParamType(FstParam)->isIntegerTy(64))) &&
207 (SndParam < 0 ||
208 FTy->getParamType(SndParam)->isIntegerTy(32) ||
209 FTy->getParamType(SndParam)->isIntegerTy(64)))
210 return *FnData;
211 return std::nullopt;
212}
213
214static std::optional<AllocFnsTy>
216 const TargetLibraryInfo *TLI) {
217 bool IsNoBuiltinCall;
218 if (const Function *Callee = getCalledFunction(V, IsNoBuiltinCall))
219 if (!IsNoBuiltinCall)
220 return getAllocationDataForFunction(Callee, AllocTy, TLI);
221 return std::nullopt;
222}
223
224static std::optional<AllocFnsTy>
226 function_ref<const TargetLibraryInfo &(Function &)> GetTLI) {
227 bool IsNoBuiltinCall;
228 if (const Function *Callee = getCalledFunction(V, IsNoBuiltinCall))
229 if (!IsNoBuiltinCall)
231 Callee, AllocTy, &GetTLI(const_cast<Function &>(*Callee)));
232 return std::nullopt;
233}
234
235static std::optional<AllocFnsTy>
237 bool IsNoBuiltinCall;
238 const Function *Callee =
239 getCalledFunction(V, IsNoBuiltinCall);
240 if (!Callee)
241 return std::nullopt;
242
243 // Prefer to use existing information over allocsize. This will give us an
244 // accurate AllocTy.
245 if (!IsNoBuiltinCall)
246 if (std::optional<AllocFnsTy> Data =
248 return Data;
249
250 Attribute Attr = Callee->getFnAttribute(Attribute::AllocSize);
251 if (Attr == Attribute())
252 return std::nullopt;
253
254 std::pair<unsigned, std::optional<unsigned>> Args = Attr.getAllocSizeArgs();
255
256 AllocFnsTy Result;
257 // Because allocsize only tells us how many bytes are allocated, we're not
258 // really allowed to assume anything, so we use MallocLike.
259 Result.AllocTy = MallocLike;
260 Result.NumParams = Callee->getNumOperands();
261 Result.FstParam = Args.first;
262 Result.SndParam = Args.second.value_or(-1);
263 // Allocsize has no way to specify an alignment argument
264 Result.AlignParam = -1;
265 return Result;
266}
267
269 if (const auto *CB = dyn_cast<CallBase>(V)) {
270 Attribute Attr = CB->getFnAttr(Attribute::AllocKind);
271 if (Attr.isValid())
272 return AllocFnKind(Attr.getValueAsInt());
273 }
274 return AllocFnKind::Unknown;
275}
276
278 Attribute Attr = F->getFnAttribute(Attribute::AllocKind);
279 if (Attr.isValid())
280 return AllocFnKind(Attr.getValueAsInt());
281 return AllocFnKind::Unknown;
282}
283
284static bool checkFnAllocKind(const Value *V, AllocFnKind Wanted) {
285 return (getAllocFnKind(V) & Wanted) != AllocFnKind::Unknown;
286}
287
288static bool checkFnAllocKind(const Function *F, AllocFnKind Wanted) {
289 return (getAllocFnKind(F) & Wanted) != AllocFnKind::Unknown;
290}
291
292/// Tests if a value is a call or invoke to a library function that
293/// allocates or reallocates memory (either malloc, calloc, realloc, or strdup
294/// like).
295bool llvm::isAllocationFn(const Value *V, const TargetLibraryInfo *TLI) {
296 return getAllocationData(V, AnyAlloc, TLI).has_value() ||
297 checkFnAllocKind(V, AllocFnKind::Alloc | AllocFnKind::Realloc);
298}
300 const Value *V,
301 function_ref<const TargetLibraryInfo &(Function &)> GetTLI) {
302 return getAllocationData(V, AnyAlloc, GetTLI).has_value() ||
303 checkFnAllocKind(V, AllocFnKind::Alloc | AllocFnKind::Realloc);
304}
305
306/// Tests if a value is a call or invoke to a library function that
307/// allocates memory via new.
308bool llvm::isNewLikeFn(const Value *V, const TargetLibraryInfo *TLI) {
309 return getAllocationData(V, OpNewLike, TLI).has_value();
310}
311
312/// Tests if a value is a call or invoke to a library function that
313/// allocates memory similar to malloc or calloc.
315 // TODO: Function behavior does not match name.
316 return getAllocationData(V, MallocOrOpNewLike, TLI).has_value();
317}
318
319/// Tests if a value is a call or invoke to a library function that
320/// allocates memory (either malloc, calloc, or strdup like).
321bool llvm::isAllocLikeFn(const Value *V, const TargetLibraryInfo *TLI) {
322 return getAllocationData(V, AllocLike, TLI).has_value() ||
323 checkFnAllocKind(V, AllocFnKind::Alloc);
324}
325
326/// Tests if a functions is a call or invoke to a library function that
327/// reallocates memory (e.g., realloc).
329 return checkFnAllocKind(F, AllocFnKind::Realloc);
330}
331
333 if (checkFnAllocKind(CB, AllocFnKind::Realloc))
334 return CB->getArgOperandWithAttribute(Attribute::AllocatedPointer);
335 return nullptr;
336}
337
339 // Note: Removability is highly dependent on the source language. For
340 // example, recent C++ requires direct calls to the global allocation
341 // [basic.stc.dynamic.allocation] to be observable unless part of a new
342 // expression [expr.new paragraph 13].
343
344 // Historically we've treated the C family allocation routines and operator
345 // new as removable
346 return isAllocLikeFn(CB, TLI);
347}
348
350 const TargetLibraryInfo *TLI) {
351 const std::optional<AllocFnsTy> FnData = getAllocationData(V, AnyAlloc, TLI);
352 if (FnData && FnData->AlignParam >= 0) {
353 return V->getOperand(FnData->AlignParam);
354 }
355 return V->getArgOperandWithAttribute(Attribute::AllocAlign);
356}
357
358/// When we're compiling N-bit code, and the user uses parameters that are
359/// greater than N bits (e.g. uint64_t on a 32-bit build), we can run into
360/// trouble with APInt size issues. This function handles resizing + overflow
361/// checks for us. Check and zext or trunc \p I depending on IntTyBits and
362/// I's value.
363static bool CheckedZextOrTrunc(APInt &I, unsigned IntTyBits) {
364 // More bits than we can handle. Checking the bit width isn't necessary, but
365 // it's faster than checking active bits, and should give `false` in the
366 // vast majority of cases.
367 if (I.getBitWidth() > IntTyBits && I.getActiveBits() > IntTyBits)
368 return false;
369 if (I.getBitWidth() != IntTyBits)
370 I = I.zextOrTrunc(IntTyBits);
371 return true;
372}
373
374std::optional<APInt>
376 function_ref<const Value *(const Value *)> Mapper) {
377 // Note: This handles both explicitly listed allocation functions and
378 // allocsize. The code structure could stand to be cleaned up a bit.
379 std::optional<AllocFnsTy> FnData = getAllocationSize(CB, TLI);
380 if (!FnData)
381 return std::nullopt;
382
383 // Get the index type for this address space, results and intermediate
384 // computations are performed at that width.
385 auto &DL = CB->getModule()->getDataLayout();
386 const unsigned IntTyBits = DL.getIndexTypeSizeInBits(CB->getType());
387
388 // Handle strdup-like functions separately.
389 if (FnData->AllocTy == StrDupLike) {
390 APInt Size(IntTyBits, GetStringLength(Mapper(CB->getArgOperand(0))));
391 if (!Size)
392 return std::nullopt;
393
394 // Strndup limits strlen.
395 if (FnData->FstParam > 0) {
396 const ConstantInt *Arg =
397 dyn_cast<ConstantInt>(Mapper(CB->getArgOperand(FnData->FstParam)));
398 if (!Arg)
399 return std::nullopt;
400
401 APInt MaxSize = Arg->getValue().zext(IntTyBits);
402 if (Size.ugt(MaxSize))
403 Size = MaxSize + 1;
404 }
405 return Size;
406 }
407
408 const ConstantInt *Arg =
409 dyn_cast<ConstantInt>(Mapper(CB->getArgOperand(FnData->FstParam)));
410 if (!Arg)
411 return std::nullopt;
412
413 APInt Size = Arg->getValue();
414 if (!CheckedZextOrTrunc(Size, IntTyBits))
415 return std::nullopt;
416
417 // Size is determined by just 1 parameter.
418 if (FnData->SndParam < 0)
419 return Size;
420
421 Arg = dyn_cast<ConstantInt>(Mapper(CB->getArgOperand(FnData->SndParam)));
422 if (!Arg)
423 return std::nullopt;
424
425 APInt NumElems = Arg->getValue();
426 if (!CheckedZextOrTrunc(NumElems, IntTyBits))
427 return std::nullopt;
428
429 bool Overflow;
430 Size = Size.umul_ov(NumElems, Overflow);
431 if (Overflow)
432 return std::nullopt;
433 return Size;
434}
435
437 const TargetLibraryInfo *TLI,
438 Type *Ty) {
439 auto *Alloc = dyn_cast<CallBase>(V);
440 if (!Alloc)
441 return nullptr;
442
443 // malloc are uninitialized (undef)
444 if (getAllocationData(Alloc, MallocOrOpNewLike, TLI).has_value())
445 return UndefValue::get(Ty);
446
447 AllocFnKind AK = getAllocFnKind(Alloc);
448 if ((AK & AllocFnKind::Uninitialized) != AllocFnKind::Unknown)
449 return UndefValue::get(Ty);
450 if ((AK & AllocFnKind::Zeroed) != AllocFnKind::Unknown)
451 return Constant::getNullValue(Ty);
452
453 return nullptr;
454}
455
456struct FreeFnsTy {
457 unsigned NumParams;
458 // Name of default allocator function to group malloc/free calls by family
460};
461
462// clang-format off
463static const std::pair<LibFunc, FreeFnsTy> FreeFnData[] = {
464 {LibFunc_ZdlPv, {1, MallocFamily::CPPNew}}, // operator delete(void*)
465 {LibFunc_ZdaPv, {1, MallocFamily::CPPNewArray}}, // operator delete[](void*)
466 {LibFunc_msvc_delete_ptr32, {1, MallocFamily::MSVCNew}}, // operator delete(void*)
467 {LibFunc_msvc_delete_ptr64, {1, MallocFamily::MSVCNew}}, // operator delete(void*)
468 {LibFunc_msvc_delete_array_ptr32, {1, MallocFamily::MSVCArrayNew}}, // operator delete[](void*)
469 {LibFunc_msvc_delete_array_ptr64, {1, MallocFamily::MSVCArrayNew}}, // operator delete[](void*)
470 {LibFunc_ZdlPvj, {2, MallocFamily::CPPNew}}, // delete(void*, uint)
471 {LibFunc_ZdlPvm, {2, MallocFamily::CPPNew}}, // delete(void*, ulong)
472 {LibFunc_ZdlPvRKSt9nothrow_t, {2, MallocFamily::CPPNew}}, // delete(void*, nothrow)
473 {LibFunc_ZdlPvSt11align_val_t, {2, MallocFamily::CPPNewAligned}}, // delete(void*, align_val_t)
474 {LibFunc_ZdaPvj, {2, MallocFamily::CPPNewArray}}, // delete[](void*, uint)
475 {LibFunc_ZdaPvm, {2, MallocFamily::CPPNewArray}}, // delete[](void*, ulong)
476 {LibFunc_ZdaPvRKSt9nothrow_t, {2, MallocFamily::CPPNewArray}}, // delete[](void*, nothrow)
477 {LibFunc_ZdaPvSt11align_val_t, {2, MallocFamily::CPPNewArrayAligned}}, // delete[](void*, align_val_t)
478 {LibFunc_msvc_delete_ptr32_int, {2, MallocFamily::MSVCNew}}, // delete(void*, uint)
479 {LibFunc_msvc_delete_ptr64_longlong, {2, MallocFamily::MSVCNew}}, // delete(void*, ulonglong)
480 {LibFunc_msvc_delete_ptr32_nothrow, {2, MallocFamily::MSVCNew}}, // delete(void*, nothrow)
481 {LibFunc_msvc_delete_ptr64_nothrow, {2, MallocFamily::MSVCNew}}, // delete(void*, nothrow)
482 {LibFunc_msvc_delete_array_ptr32_int, {2, MallocFamily::MSVCArrayNew}}, // delete[](void*, uint)
483 {LibFunc_msvc_delete_array_ptr64_longlong, {2, MallocFamily::MSVCArrayNew}}, // delete[](void*, ulonglong)
484 {LibFunc_msvc_delete_array_ptr32_nothrow, {2, MallocFamily::MSVCArrayNew}}, // delete[](void*, nothrow)
485 {LibFunc_msvc_delete_array_ptr64_nothrow, {2, MallocFamily::MSVCArrayNew}}, // delete[](void*, nothrow)
486 {LibFunc___kmpc_free_shared, {2, MallocFamily::KmpcAllocShared}}, // OpenMP Offloading RTL free
487 {LibFunc_ZdlPvSt11align_val_tRKSt9nothrow_t, {3, MallocFamily::CPPNewAligned}}, // delete(void*, align_val_t, nothrow)
488 {LibFunc_ZdaPvSt11align_val_tRKSt9nothrow_t, {3, MallocFamily::CPPNewArrayAligned}}, // delete[](void*, align_val_t, nothrow)
489 {LibFunc_ZdlPvjSt11align_val_t, {3, MallocFamily::CPPNewAligned}}, // delete(void*, unsigned int, align_val_t)
490 {LibFunc_ZdlPvmSt11align_val_t, {3, MallocFamily::CPPNewAligned}}, // delete(void*, unsigned long, align_val_t)
491 {LibFunc_ZdaPvjSt11align_val_t, {3, MallocFamily::CPPNewArrayAligned}}, // delete[](void*, unsigned int, align_val_t)
492 {LibFunc_ZdaPvmSt11align_val_t, {3, MallocFamily::CPPNewArrayAligned}}, // delete[](void*, unsigned long, align_val_t)
493};
494// clang-format on
495
496std::optional<FreeFnsTy> getFreeFunctionDataForFunction(const Function *Callee,
497 const LibFunc TLIFn) {
498 const auto *Iter =
499 find_if(FreeFnData, [TLIFn](const std::pair<LibFunc, FreeFnsTy> &P) {
500 return P.first == TLIFn;
501 });
502 if (Iter == std::end(FreeFnData))
503 return std::nullopt;
504 return Iter->second;
505}
506
507std::optional<StringRef>
509 bool IsNoBuiltin;
510 const Function *Callee = getCalledFunction(I, IsNoBuiltin);
511 if (Callee == nullptr || IsNoBuiltin)
512 return std::nullopt;
513 LibFunc TLIFn;
514
515 if (TLI && TLI->getLibFunc(*Callee, TLIFn) && TLI->has(TLIFn)) {
516 // Callee is some known library function.
517 const auto AllocData = getAllocationDataForFunction(Callee, AnyAlloc, TLI);
518 if (AllocData)
519 return mangledNameForMallocFamily(AllocData->Family);
520 const auto FreeData = getFreeFunctionDataForFunction(Callee, TLIFn);
521 if (FreeData)
522 return mangledNameForMallocFamily(FreeData->Family);
523 }
524 // Callee isn't a known library function, still check attributes.
525 if (checkFnAllocKind(I, AllocFnKind::Free | AllocFnKind::Alloc |
526 AllocFnKind::Realloc)) {
527 Attribute Attr = cast<CallBase>(I)->getFnAttr("alloc-family");
528 if (Attr.isValid())
529 return Attr.getValueAsString();
530 }
531 return std::nullopt;
532}
533
534/// isLibFreeFunction - Returns true if the function is a builtin free()
535bool llvm::isLibFreeFunction(const Function *F, const LibFunc TLIFn) {
536 std::optional<FreeFnsTy> FnData = getFreeFunctionDataForFunction(F, TLIFn);
537 if (!FnData)
538 return checkFnAllocKind(F, AllocFnKind::Free);
539
540 // Check free prototype.
541 // FIXME: workaround for PR5130, this will be obsolete when a nobuiltin
542 // attribute will exist.
543 FunctionType *FTy = F->getFunctionType();
544 if (!FTy->getReturnType()->isVoidTy())
545 return false;
546 if (FTy->getNumParams() != FnData->NumParams)
547 return false;
548 if (!FTy->getParamType(0)->isPointerTy())
549 return false;
550
551 return true;
552}
553
555 bool IsNoBuiltinCall;
556 const Function *Callee = getCalledFunction(CB, IsNoBuiltinCall);
557 if (Callee == nullptr || IsNoBuiltinCall)
558 return nullptr;
559
560 LibFunc TLIFn;
561 if (TLI && TLI->getLibFunc(*Callee, TLIFn) && TLI->has(TLIFn) &&
562 isLibFreeFunction(Callee, TLIFn)) {
563 // All currently supported free functions free the first argument.
564 return CB->getArgOperand(0);
565 }
566
567 if (checkFnAllocKind(CB, AllocFnKind::Free))
568 return CB->getArgOperandWithAttribute(Attribute::AllocatedPointer);
569
570 return nullptr;
571}
572
573//===----------------------------------------------------------------------===//
574// Utility functions to compute size of objects.
575//
577 if (Data.second.isNegative() || Data.first.ult(Data.second))
578 return APInt(Data.first.getBitWidth(), 0);
579 return Data.first - Data.second;
580}
581
582/// Compute the size of the object pointed by Ptr. Returns true and the
583/// object size in Size if successful, and false otherwise.
584/// If RoundToAlign is true, then Size is rounded up to the alignment of
585/// allocas, byval arguments, and global variables.
587 const TargetLibraryInfo *TLI, ObjectSizeOpts Opts) {
588 ObjectSizeOffsetVisitor Visitor(DL, TLI, Ptr->getContext(), Opts);
589 SizeOffsetType Data = Visitor.compute(const_cast<Value*>(Ptr));
590 if (!Visitor.bothKnown(Data))
591 return false;
592
594 return true;
595}
596
598 const DataLayout &DL,
599 const TargetLibraryInfo *TLI,
600 bool MustSucceed) {
601 return lowerObjectSizeCall(ObjectSize, DL, TLI, /*AAResults=*/nullptr,
602 MustSucceed);
603}
604
606 const DataLayout &DL,
607 const TargetLibraryInfo *TLI, AAResults *AA,
608 bool MustSucceed) {
609 assert(ObjectSize->getIntrinsicID() == Intrinsic::objectsize &&
610 "ObjectSize must be a call to llvm.objectsize!");
611
612 bool MaxVal = cast<ConstantInt>(ObjectSize->getArgOperand(1))->isZero();
613 ObjectSizeOpts EvalOptions;
614 EvalOptions.AA = AA;
615
616 // Unless we have to fold this to something, try to be as accurate as
617 // possible.
618 if (MustSucceed)
619 EvalOptions.EvalMode =
620 MaxVal ? ObjectSizeOpts::Mode::Max : ObjectSizeOpts::Mode::Min;
621 else
622 EvalOptions.EvalMode = ObjectSizeOpts::Mode::ExactSizeFromOffset;
623
624 EvalOptions.NullIsUnknownSize =
625 cast<ConstantInt>(ObjectSize->getArgOperand(2))->isOne();
626
627 auto *ResultType = cast<IntegerType>(ObjectSize->getType());
628 bool StaticOnly = cast<ConstantInt>(ObjectSize->getArgOperand(3))->isZero();
629 if (StaticOnly) {
630 // FIXME: Does it make sense to just return a failure value if the size won't
631 // fit in the output and `!MustSucceed`?
633 if (getObjectSize(ObjectSize->getArgOperand(0), Size, DL, TLI, EvalOptions) &&
634 isUIntN(ResultType->getBitWidth(), Size))
635 return ConstantInt::get(ResultType, Size);
636 } else {
637 LLVMContext &Ctx = ObjectSize->getFunction()->getContext();
638 ObjectSizeOffsetEvaluator Eval(DL, TLI, Ctx, EvalOptions);
639 SizeOffsetEvalType SizeOffsetPair =
640 Eval.compute(ObjectSize->getArgOperand(0));
641
642 if (SizeOffsetPair != ObjectSizeOffsetEvaluator::unknown()) {
644 Builder.SetInsertPoint(ObjectSize);
645
646 // If we've outside the end of the object, then we can always access
647 // exactly 0 bytes.
648 Value *ResultSize =
649 Builder.CreateSub(SizeOffsetPair.first, SizeOffsetPair.second);
650 Value *UseZero =
651 Builder.CreateICmpULT(SizeOffsetPair.first, SizeOffsetPair.second);
652 ResultSize = Builder.CreateZExtOrTrunc(ResultSize, ResultType);
653 Value *Ret = Builder.CreateSelect(
654 UseZero, ConstantInt::get(ResultType, 0), ResultSize);
655
656 // The non-constant size expression cannot evaluate to -1.
657 if (!isa<Constant>(SizeOffsetPair.first) ||
658 !isa<Constant>(SizeOffsetPair.second))
659 Builder.CreateAssumption(
660 Builder.CreateICmpNE(Ret, ConstantInt::get(ResultType, -1)));
661
662 return Ret;
663 }
664 }
665
666 if (!MustSucceed)
667 return nullptr;
668
669 return ConstantInt::get(ResultType, MaxVal ? -1ULL : 0);
670}
671
672STATISTIC(ObjectVisitorArgument,
673 "Number of arguments with unsolved size and offset");
674STATISTIC(ObjectVisitorLoad,
675 "Number of load instructions with unsolved size and offset");
676
677APInt ObjectSizeOffsetVisitor::align(APInt Size, MaybeAlign Alignment) {
678 if (Options.RoundToAlign && Alignment)
679 return APInt(IntTyBits, alignTo(Size.getZExtValue(), *Alignment));
680 return Size;
681}
682
684 const TargetLibraryInfo *TLI,
685 LLVMContext &Context,
687 : DL(DL), TLI(TLI), Options(Options) {
688 // Pointer size must be rechecked for each object visited since it could have
689 // a different address space.
690}
691
693 unsigned InitialIntTyBits = DL.getIndexTypeSizeInBits(V->getType());
694
695 // Stripping pointer casts can strip address space casts which can change the
696 // index type size. The invariant is that we use the value type to determine
697 // the index type size and if we stripped address space casts we have to
698 // readjust the APInt as we pass it upwards in order for the APInt to match
699 // the type the caller passed in.
700 APInt Offset(InitialIntTyBits, 0);
701 V = V->stripAndAccumulateConstantOffsets(
702 DL, Offset, /* AllowNonInbounds */ true, /* AllowInvariantGroup */ true);
703
704 // Later we use the index type size and zero but it will match the type of the
705 // value that is passed to computeImpl.
706 IntTyBits = DL.getIndexTypeSizeInBits(V->getType());
707 Zero = APInt::getZero(IntTyBits);
708
709 bool IndexTypeSizeChanged = InitialIntTyBits != IntTyBits;
710 if (!IndexTypeSizeChanged && Offset.isZero())
711 return computeImpl(V);
712
713 // We stripped an address space cast that changed the index type size or we
714 // accumulated some constant offset (or both). Readjust the bit width to match
715 // the argument index type size and apply the offset, as required.
716 SizeOffsetType SOT = computeImpl(V);
717 if (IndexTypeSizeChanged) {
718 if (knownSize(SOT) && !::CheckedZextOrTrunc(SOT.first, InitialIntTyBits))
719 SOT.first = APInt();
720 if (knownOffset(SOT) && !::CheckedZextOrTrunc(SOT.second, InitialIntTyBits))
721 SOT.second = APInt();
722 }
723 // If the computed offset is "unknown" we cannot add the stripped offset.
724 return {SOT.first,
725 SOT.second.getBitWidth() > 1 ? SOT.second + Offset : SOT.second};
726}
727
728SizeOffsetType ObjectSizeOffsetVisitor::computeImpl(Value *V) {
729 if (Instruction *I = dyn_cast<Instruction>(V)) {
730 // If we have already seen this instruction, bail out. Cycles can happen in
731 // unreachable code after constant propagation.
732 if (!SeenInsts.insert(I).second)
733 return unknown();
734
735 return visit(*I);
736 }
737 if (Argument *A = dyn_cast<Argument>(V))
738 return visitArgument(*A);
739 if (ConstantPointerNull *P = dyn_cast<ConstantPointerNull>(V))
741 if (GlobalAlias *GA = dyn_cast<GlobalAlias>(V))
742 return visitGlobalAlias(*GA);
743 if (GlobalVariable *GV = dyn_cast<GlobalVariable>(V))
744 return visitGlobalVariable(*GV);
745 if (UndefValue *UV = dyn_cast<UndefValue>(V))
746 return visitUndefValue(*UV);
747
748 LLVM_DEBUG(dbgs() << "ObjectSizeOffsetVisitor::compute() unhandled value: "
749 << *V << '\n');
750 return unknown();
751}
752
753bool ObjectSizeOffsetVisitor::CheckedZextOrTrunc(APInt &I) {
754 return ::CheckedZextOrTrunc(I, IntTyBits);
755}
756
758 TypeSize ElemSize = DL.getTypeAllocSize(I.getAllocatedType());
759 if (ElemSize.isScalable() && Options.EvalMode != ObjectSizeOpts::Mode::Min)
760 return unknown();
761 APInt Size(IntTyBits, ElemSize.getKnownMinValue());
762 if (!I.isArrayAllocation())
763 return std::make_pair(align(Size, I.getAlign()), Zero);
764
765 Value *ArraySize = I.getArraySize();
766 if (const ConstantInt *C = dyn_cast<ConstantInt>(ArraySize)) {
767 APInt NumElems = C->getValue();
768 if (!CheckedZextOrTrunc(NumElems))
769 return unknown();
770
771 bool Overflow;
772 Size = Size.umul_ov(NumElems, Overflow);
773 return Overflow ? unknown()
774 : std::make_pair(align(Size, I.getAlign()), Zero);
775 }
776 return unknown();
777}
778
780 Type *MemoryTy = A.getPointeeInMemoryValueType();
781 // No interprocedural analysis is done at the moment.
782 if (!MemoryTy|| !MemoryTy->isSized()) {
783 ++ObjectVisitorArgument;
784 return unknown();
785 }
786
787 APInt Size(IntTyBits, DL.getTypeAllocSize(MemoryTy));
788 return std::make_pair(align(Size, A.getParamAlign()), Zero);
789}
790
792 if (std::optional<APInt> Size = getAllocSize(&CB, TLI))
793 return std::make_pair(*Size, Zero);
794 return unknown();
795}
796
799 // If null is unknown, there's nothing we can do. Additionally, non-zero
800 // address spaces can make use of null, so we don't presume to know anything
801 // about that.
802 //
803 // TODO: How should this work with address space casts? We currently just drop
804 // them on the floor, but it's unclear what we should do when a NULL from
805 // addrspace(1) gets casted to addrspace(0) (or vice-versa).
806 if (Options.NullIsUnknownSize || CPN.getType()->getAddressSpace())
807 return unknown();
808 return std::make_pair(Zero, Zero);
809}
810
813 return unknown();
814}
815
818 // Easy cases were already folded by previous passes.
819 return unknown();
820}
821
823 if (GA.isInterposable())
824 return unknown();
825 return compute(GA.getAliasee());
826}
827
829 if (!GV.hasDefinitiveInitializer())
830 return unknown();
831
832 APInt Size(IntTyBits, DL.getTypeAllocSize(GV.getValueType()));
833 return std::make_pair(align(Size, GV.getAlign()), Zero);
834}
835
837 // clueless
838 return unknown();
839}
840
841SizeOffsetType ObjectSizeOffsetVisitor::findLoadSizeOffset(
844 unsigned &ScannedInstCount) {
845 constexpr unsigned MaxInstsToScan = 128;
846
847 auto Where = VisitedBlocks.find(&BB);
848 if (Where != VisitedBlocks.end())
849 return Where->second;
850
851 auto Unknown = [this, &BB, &VisitedBlocks]() {
852 return VisitedBlocks[&BB] = unknown();
853 };
854 auto Known = [&BB, &VisitedBlocks](SizeOffsetType SO) {
855 return VisitedBlocks[&BB] = SO;
856 };
857
858 do {
859 Instruction &I = *From;
860
861 if (I.isDebugOrPseudoInst())
862 continue;
863
864 if (++ScannedInstCount > MaxInstsToScan)
865 return Unknown();
866
867 if (!I.mayWriteToMemory())
868 continue;
869
870 if (auto *SI = dyn_cast<StoreInst>(&I)) {
871 AliasResult AR =
872 Options.AA->alias(SI->getPointerOperand(), Load.getPointerOperand());
873 switch ((AliasResult::Kind)AR) {
875 continue;
877 if (SI->getValueOperand()->getType()->isPointerTy())
878 return Known(compute(SI->getValueOperand()));
879 else
880 return Unknown(); // No handling of non-pointer values by `compute`.
881 default:
882 return Unknown();
883 }
884 }
885
886 if (auto *CB = dyn_cast<CallBase>(&I)) {
888 // Bail out on indirect call.
889 if (!Callee)
890 return Unknown();
891
892 LibFunc TLIFn;
893 if (!TLI || !TLI->getLibFunc(*CB->getCalledFunction(), TLIFn) ||
894 !TLI->has(TLIFn))
895 return Unknown();
896
897 // TODO: There's probably more interesting case to support here.
898 if (TLIFn != LibFunc_posix_memalign)
899 return Unknown();
900
901 AliasResult AR =
902 Options.AA->alias(CB->getOperand(0), Load.getPointerOperand());
903 switch ((AliasResult::Kind)AR) {
905 continue;
907 break;
908 default:
909 return Unknown();
910 }
911
912 // Is the error status of posix_memalign correctly checked? If not it
913 // would be incorrect to assume it succeeds and load doesn't see the
914 // previous value.
915 std::optional<bool> Checked = isImpliedByDomCondition(
916 ICmpInst::ICMP_EQ, CB, ConstantInt::get(CB->getType(), 0), &Load, DL);
917 if (!Checked || !*Checked)
918 return Unknown();
919
920 Value *Size = CB->getOperand(2);
921 auto *C = dyn_cast<ConstantInt>(Size);
922 if (!C)
923 return Unknown();
924
925 return Known({C->getValue(), APInt(C->getValue().getBitWidth(), 0)});
926 }
927
928 return Unknown();
929 } while (From-- != BB.begin());
930
931 SmallVector<SizeOffsetType> PredecessorSizeOffsets;
932 for (auto *PredBB : predecessors(&BB)) {
933 PredecessorSizeOffsets.push_back(findLoadSizeOffset(
934 Load, *PredBB, BasicBlock::iterator(PredBB->getTerminator()),
935 VisitedBlocks, ScannedInstCount));
936 if (!bothKnown(PredecessorSizeOffsets.back()))
937 return Unknown();
938 }
939
940 if (PredecessorSizeOffsets.empty())
941 return Unknown();
942
943 return Known(std::accumulate(PredecessorSizeOffsets.begin() + 1,
944 PredecessorSizeOffsets.end(),
945 PredecessorSizeOffsets.front(),
946 [this](SizeOffsetType LHS, SizeOffsetType RHS) {
947 return combineSizeOffset(LHS, RHS);
948 }));
949}
950
952 if (!Options.AA) {
953 ++ObjectVisitorLoad;
954 return unknown();
955 }
956
958 unsigned ScannedInstCount = 0;
959 SizeOffsetType SO =
960 findLoadSizeOffset(LI, *LI.getParent(), BasicBlock::iterator(LI),
961 VisitedBlocks, ScannedInstCount);
962 if (!bothKnown(SO))
963 ++ObjectVisitorLoad;
964 return SO;
965}
966
967SizeOffsetType ObjectSizeOffsetVisitor::combineSizeOffset(SizeOffsetType LHS,
968 SizeOffsetType RHS) {
969 if (!bothKnown(LHS) || !bothKnown(RHS))
970 return unknown();
971
972 switch (Options.EvalMode) {
974 return (getSizeWithOverflow(LHS).slt(getSizeWithOverflow(RHS))) ? LHS : RHS;
976 return (getSizeWithOverflow(LHS).sgt(getSizeWithOverflow(RHS))) ? LHS : RHS;
978 return (getSizeWithOverflow(LHS).eq(getSizeWithOverflow(RHS))) ? LHS
979 : unknown();
981 return LHS == RHS && LHS.second.eq(RHS.second) ? LHS : unknown();
982 }
983 llvm_unreachable("missing an eval mode");
984}
985
987 if (PN.getNumIncomingValues() == 0)
988 return unknown();
989 auto IncomingValues = PN.incoming_values();
990 return std::accumulate(IncomingValues.begin() + 1, IncomingValues.end(),
991 compute(*IncomingValues.begin()),
992 [this](SizeOffsetType LHS, Value *VRHS) {
993 return combineSizeOffset(LHS, compute(VRHS));
994 });
995}
996
998 return combineSizeOffset(compute(I.getTrueValue()),
999 compute(I.getFalseValue()));
1000}
1001
1003 return std::make_pair(Zero, Zero);
1004}
1005
1007 LLVM_DEBUG(dbgs() << "ObjectSizeOffsetVisitor unknown instruction:" << I
1008 << '\n');
1009 return unknown();
1010}
1011
1013 const DataLayout &DL, const TargetLibraryInfo *TLI, LLVMContext &Context,
1014 ObjectSizeOpts EvalOpts)
1015 : DL(DL), TLI(TLI), Context(Context),
1018 [&](Instruction *I) { InsertedInstructions.insert(I); })),
1019 EvalOpts(EvalOpts) {
1020 // IntTy and Zero must be set for each compute() since the address space may
1021 // be different for later objects.
1022}
1023
1025 // XXX - Are vectors of pointers possible here?
1026 IntTy = cast<IntegerType>(DL.getIndexType(V->getType()));
1027 Zero = ConstantInt::get(IntTy, 0);
1028
1029 SizeOffsetEvalType Result = compute_(V);
1030
1031 if (!bothKnown(Result)) {
1032 // Erase everything that was computed in this iteration from the cache, so
1033 // that no dangling references are left behind. We could be a bit smarter if
1034 // we kept a dependency graph. It's probably not worth the complexity.
1035 for (const Value *SeenVal : SeenVals) {
1036 CacheMapTy::iterator CacheIt = CacheMap.find(SeenVal);
1037 // non-computable results can be safely cached
1038 if (CacheIt != CacheMap.end() && anyKnown(CacheIt->second))
1039 CacheMap.erase(CacheIt);
1040 }
1041
1042 // Erase any instructions we inserted as part of the traversal.
1043 for (Instruction *I : InsertedInstructions) {
1044 I->replaceAllUsesWith(PoisonValue::get(I->getType()));
1045 I->eraseFromParent();
1046 }
1047 }
1048
1049 SeenVals.clear();
1050 InsertedInstructions.clear();
1051 return Result;
1052}
1053
1054SizeOffsetEvalType ObjectSizeOffsetEvaluator::compute_(Value *V) {
1055 ObjectSizeOffsetVisitor Visitor(DL, TLI, Context, EvalOpts);
1056 SizeOffsetType Const = Visitor.compute(V);
1057 if (Visitor.bothKnown(Const))
1058 return std::make_pair(ConstantInt::get(Context, Const.first),
1059 ConstantInt::get(Context, Const.second));
1060
1061 V = V->stripPointerCasts();
1062
1063 // Check cache.
1064 CacheMapTy::iterator CacheIt = CacheMap.find(V);
1065 if (CacheIt != CacheMap.end())
1066 return CacheIt->second;
1067
1068 // Always generate code immediately before the instruction being
1069 // processed, so that the generated code dominates the same BBs.
1070 BuilderTy::InsertPointGuard Guard(Builder);
1071 if (Instruction *I = dyn_cast<Instruction>(V))
1072 Builder.SetInsertPoint(I);
1073
1074 // Now compute the size and offset.
1075 SizeOffsetEvalType Result;
1076
1077 // Record the pointers that were handled in this run, so that they can be
1078 // cleaned later if something fails. We also use this set to break cycles that
1079 // can occur in dead code.
1080 if (!SeenVals.insert(V).second) {
1081 Result = unknown();
1082 } else if (GEPOperator *GEP = dyn_cast<GEPOperator>(V)) {
1083 Result = visitGEPOperator(*GEP);
1084 } else if (Instruction *I = dyn_cast<Instruction>(V)) {
1085 Result = visit(*I);
1086 } else if (isa<Argument>(V) ||
1087 (isa<ConstantExpr>(V) &&
1088 cast<ConstantExpr>(V)->getOpcode() == Instruction::IntToPtr) ||
1089 isa<GlobalAlias>(V) ||
1090 isa<GlobalVariable>(V)) {
1091 // Ignore values where we cannot do more than ObjectSizeVisitor.
1092 Result = unknown();
1093 } else {
1094 LLVM_DEBUG(
1095 dbgs() << "ObjectSizeOffsetEvaluator::compute() unhandled value: " << *V
1096 << '\n');
1097 Result = unknown();
1098 }
1099
1100 // Don't reuse CacheIt since it may be invalid at this point.
1101 CacheMap[V] = Result;
1102 return Result;
1103}
1104
1106 if (!I.getAllocatedType()->isSized())
1107 return unknown();
1108
1109 // must be a VLA
1110 assert(I.isArrayAllocation());
1111
1112 // If needed, adjust the alloca's operand size to match the pointer indexing
1113 // size. Subsequent math operations expect the types to match.
1114 Value *ArraySize = Builder.CreateZExtOrTrunc(
1115 I.getArraySize(),
1116 DL.getIndexType(I.getContext(), DL.getAllocaAddrSpace()));
1117 assert(ArraySize->getType() == Zero->getType() &&
1118 "Expected zero constant to have pointer index type");
1119
1120 Value *Size = ConstantInt::get(ArraySize->getType(),
1121 DL.getTypeAllocSize(I.getAllocatedType()));
1122 Size = Builder.CreateMul(Size, ArraySize);
1123 return std::make_pair(Size, Zero);
1124}
1125
1127 std::optional<AllocFnsTy> FnData = getAllocationSize(&CB, TLI);
1128 if (!FnData)
1129 return unknown();
1130
1131 // Handle strdup-like functions separately.
1132 if (FnData->AllocTy == StrDupLike) {
1133 // TODO: implement evaluation of strdup/strndup
1134 return unknown();
1135 }
1136
1137 Value *FirstArg = CB.getArgOperand(FnData->FstParam);
1138 FirstArg = Builder.CreateZExtOrTrunc(FirstArg, IntTy);
1139 if (FnData->SndParam < 0)
1140 return std::make_pair(FirstArg, Zero);
1141
1142 Value *SecondArg = CB.getArgOperand(FnData->SndParam);
1143 SecondArg = Builder.CreateZExtOrTrunc(SecondArg, IntTy);
1144 Value *Size = Builder.CreateMul(FirstArg, SecondArg);
1145 return std::make_pair(Size, Zero);
1146}
1147
1150 return unknown();
1151}
1152
1155 return unknown();
1156}
1157
1160 SizeOffsetEvalType PtrData = compute_(GEP.getPointerOperand());
1161 if (!bothKnown(PtrData))
1162 return unknown();
1163
1164 Value *Offset = emitGEPOffset(&Builder, DL, &GEP, /*NoAssumptions=*/true);
1165 Offset = Builder.CreateAdd(PtrData.second, Offset);
1166 return std::make_pair(PtrData.first, Offset);
1167}
1168
1170 // clueless
1171 return unknown();
1172}
1173
1175 return unknown();
1176}
1177
1179 // Create 2 PHIs: one for size and another for offset.
1180 PHINode *SizePHI = Builder.CreatePHI(IntTy, PHI.getNumIncomingValues());
1181 PHINode *OffsetPHI = Builder.CreatePHI(IntTy, PHI.getNumIncomingValues());
1182
1183 // Insert right away in the cache to handle recursive PHIs.
1184 CacheMap[&PHI] = std::make_pair(SizePHI, OffsetPHI);
1185
1186 // Compute offset/size for each PHI incoming pointer.
1187 for (unsigned i = 0, e = PHI.getNumIncomingValues(); i != e; ++i) {
1188 Builder.SetInsertPoint(&*PHI.getIncomingBlock(i)->getFirstInsertionPt());
1189 SizeOffsetEvalType EdgeData = compute_(PHI.getIncomingValue(i));
1190
1191 if (!bothKnown(EdgeData)) {
1192 OffsetPHI->replaceAllUsesWith(PoisonValue::get(IntTy));
1193 OffsetPHI->eraseFromParent();
1194 InsertedInstructions.erase(OffsetPHI);
1195 SizePHI->replaceAllUsesWith(PoisonValue::get(IntTy));
1196 SizePHI->eraseFromParent();
1197 InsertedInstructions.erase(SizePHI);
1198 return unknown();
1199 }
1200 SizePHI->addIncoming(EdgeData.first, PHI.getIncomingBlock(i));
1201 OffsetPHI->addIncoming(EdgeData.second, PHI.getIncomingBlock(i));
1202 }
1203
1204 Value *Size = SizePHI, *Offset = OffsetPHI;
1205 if (Value *Tmp = SizePHI->hasConstantValue()) {
1206 Size = Tmp;
1207 SizePHI->replaceAllUsesWith(Size);
1208 SizePHI->eraseFromParent();
1209 InsertedInstructions.erase(SizePHI);
1210 }
1211 if (Value *Tmp = OffsetPHI->hasConstantValue()) {
1212 Offset = Tmp;
1213 OffsetPHI->replaceAllUsesWith(Offset);
1214 OffsetPHI->eraseFromParent();
1215 InsertedInstructions.erase(OffsetPHI);
1216 }
1217 return std::make_pair(Size, Offset);
1218}
1219
1221 SizeOffsetEvalType TrueSide = compute_(I.getTrueValue());
1222 SizeOffsetEvalType FalseSide = compute_(I.getFalseValue());
1223
1224 if (!bothKnown(TrueSide) || !bothKnown(FalseSide))
1225 return unknown();
1226 if (TrueSide == FalseSide)
1227 return TrueSide;
1228
1229 Value *Size = Builder.CreateSelect(I.getCondition(), TrueSide.first,
1230 FalseSide.first);
1231 Value *Offset = Builder.CreateSelect(I.getCondition(), TrueSide.second,
1232 FalseSide.second);
1233 return std::make_pair(Size, Offset);
1234}
1235
1237 LLVM_DEBUG(dbgs() << "ObjectSizeOffsetEvaluator unknown instruction:" << I
1238 << '\n');
1239 return unknown();
1240}
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL
amdgpu Simplify well known AMD library false FunctionCallee Callee
amdgpu Simplify well known AMD library false FunctionCallee Value * Arg
Rewrite undef for PHI
This file implements a class to represent arbitrary precision integral constant values and operations...
assume Assume Builder
This file contains the simple types necessary to represent the attributes associated with functions a...
BlockVerifier::State From
static GCRegistry::Add< ErlangGC > A("erlang", "erlang-compatible garbage collector")
This file contains the declarations for the subclasses of Constant, which represent the different fla...
#define LLVM_DEBUG(X)
Definition: Debug.h:101
uint64_t Size
Hexagon Common GEP
static LVOptions Options
Definition: LVOptions.cpp:25
#define F(x, y, z)
Definition: MD5.cpp:55
#define I(x, y, z)
Definition: MD5.cpp:58
MallocFamily
static AllocFnKind getAllocFnKind(const Value *V)
static APInt getSizeWithOverflow(const SizeOffsetType &Data)
static std::optional< AllocFnsTy > getAllocationDataForFunction(const Function *Callee, AllocType AllocTy, const TargetLibraryInfo *TLI)
Returns the allocation data for the given value if it's a call to a known allocation function.
static std::optional< AllocFnsTy > getAllocationData(const Value *V, AllocType AllocTy, const TargetLibraryInfo *TLI)
std::optional< FreeFnsTy > getFreeFunctionDataForFunction(const Function *Callee, const LibFunc TLIFn)
static std::optional< AllocFnsTy > getAllocationSize(const Value *V, const TargetLibraryInfo *TLI)
static bool checkFnAllocKind(const Value *V, AllocFnKind Wanted)
StringRef mangledNameForMallocFamily(const MallocFamily &Family)
static bool CheckedZextOrTrunc(APInt &I, unsigned IntTyBits)
When we're compiling N-bit code, and the user uses parameters that are greater than N bits (e....
static const std::pair< LibFunc, FreeFnsTy > FreeFnData[]
static const std::pair< LibFunc, AllocFnsTy > AllocationFnData[]
AllocType
@ MallocLike
@ AnyAlloc
@ AllocLike
@ StrDupLike
@ OpNewLike
@ MallocOrOpNewLike
static const Function * getCalledFunction(const Value *V, bool &IsNoBuiltin)
LLVMContext & Context
#define P(N)
@ SI
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
This file contains some templates that are useful if you are working with the STL at all.
This file defines the 'Statistic' class, which is designed to be an easy way to expose various metric...
#define STATISTIC(VARNAME, DESC)
Definition: Statistic.h:167
static std::optional< unsigned > getOpcode(ArrayRef< VPValue * > Values)
Returns the opcode of Values or ~0 if they do not all agree.
Definition: VPlanSLP.cpp:191
Value * RHS
Value * LHS
AliasResult alias(const MemoryLocation &LocA, const MemoryLocation &LocB)
The main low level interface to the alias analysis implementation.
Class for arbitrary precision integers.
Definition: APInt.h:75
uint64_t getZExtValue() const
Get zero extended value.
Definition: APInt.h:1498
static APInt getZero(unsigned numBits)
Get the '0' value for the specified bit-width.
Definition: APInt.h:177
The possible results of an alias query.
Definition: AliasAnalysis.h:83
@ NoAlias
The two locations do not alias at all.
@ MustAlias
The two locations precisely alias each other.
an instruction to allocate memory on the stack
Definition: Instructions.h:58
This class represents an incoming formal argument to a Function.
Definition: Argument.h:28
uint64_t getValueAsInt() const
Return the attribute's value as an integer.
Definition: Attributes.cpp:296
std::pair< unsigned, std::optional< unsigned > > getAllocSizeArgs() const
Returns the argument numbers for the allocsize attribute.
Definition: Attributes.cpp:368
StringRef getValueAsString() const
Return the attribute's value as a string.
Definition: Attributes.cpp:317
bool isValid() const
Return true if the attribute is any kind of attribute.
Definition: Attributes.h:187
LLVM Basic Block Representation.
Definition: BasicBlock.h:56
iterator begin()
Instruction iterator methods.
Definition: BasicBlock.h:323
InstListType::iterator iterator
Instruction iterators...
Definition: BasicBlock.h:87
Base class for all callable instructions (InvokeInst and CallInst) Holds everything related to callin...
Definition: InstrTypes.h:1190
Function * getCalledFunction() const
Returns the function called, or null if this is an indirect function invocation or the function signa...
Definition: InstrTypes.h:1412
Value * getArgOperand(unsigned i) const
Definition: InstrTypes.h:1357
Value * getArgOperandWithAttribute(Attribute::AttrKind Kind) const
If one of the arguments has the specified attribute, returns its operand value.
@ ICMP_EQ
equal
Definition: InstrTypes.h:732
This is the shared class of boolean and integer constants.
Definition: Constants.h:78
static Constant * get(Type *Ty, uint64_t V, bool IsSigned=false)
If Ty is a vector type, return a Constant with a splat of the given value.
Definition: Constants.cpp:888
A constant pointer value that points to null.
Definition: Constants.h:533
PointerType * getType() const
Specialize the getType() method to always return an PointerType, which reduces the amount of casting ...
Definition: Constants.h:549
This is an important base class in LLVM.
Definition: Constant.h:41
static Constant * getNullValue(Type *Ty)
Constructor to create a '0' constant of arbitrary type.
Definition: Constants.cpp:356
A parsed version of the target data layout string in and methods for querying it.
Definition: DataLayout.h:110
unsigned getIndexTypeSizeInBits(Type *Ty) const
Layout size of the index used in GEP calculation.
Definition: DataLayout.cpp:772
unsigned getAllocaAddrSpace() const
Definition: DataLayout.h:276
IntegerType * getIndexType(LLVMContext &C, unsigned AddressSpace) const
Returns the type of a GEP index in AddressSpace.
Definition: DataLayout.cpp:908
TypeSize getTypeAllocSize(Type *Ty) const
Returns the offset in bytes between successive objects of the specified type, including alignment pad...
Definition: DataLayout.h:500
iterator find(const_arg_type_t< KeyT > Val)
Definition: DenseMap.h:155
bool erase(const KeyT &Val)
Definition: DenseMap.h:329
DenseMapIterator< KeyT, ValueT, KeyInfoT, BucketT > iterator
Definition: DenseMap.h:71
iterator end()
Definition: DenseMap.h:84
This instruction extracts a single (scalar) element from a VectorType value.
This instruction extracts a struct member or array element value from an aggregate value.
FunctionType * getFunctionType()
Definition: DerivedTypes.h:182
Class to represent function types.
Definition: DerivedTypes.h:103
unsigned getNumParams() const
Return the number of fixed parameters this function type requires.
Definition: DerivedTypes.h:139
Type * getParamType(unsigned i) const
Parameter type accessors.
Definition: DerivedTypes.h:135
Type * getReturnType() const
Definition: DerivedTypes.h:124
LLVMContext & getContext() const
getContext - Return a reference to the LLVMContext associated with this function.
Definition: Function.cpp:319
const Constant * getAliasee() const
Definition: GlobalAlias.h:84
MaybeAlign getAlign() const
Returns the alignment of the given variable or function.
Definition: GlobalObject.h:79
bool isInterposable() const
Return true if this global's definition can be substituted with an arbitrary definition at link time ...
Definition: Globals.cpp:100
Type * getValueType() const
Definition: GlobalValue.h:292
bool hasDefinitiveInitializer() const
hasDefinitiveInitializer - Whether the global variable has an initializer, and any other instances of...
Value * CreateZExtOrTrunc(Value *V, Type *DestTy, const Twine &Name="")
Create a ZExt or Trunc from the integer value V to DestTy.
Definition: IRBuilder.h:1940
Value * CreateSelect(Value *C, Value *True, Value *False, const Twine &Name="", Instruction *MDFrom=nullptr)
Definition: IRBuilder.cpp:1134
PHINode * CreatePHI(Type *Ty, unsigned NumReservedValues, const Twine &Name="")
Definition: IRBuilder.h:2292
Value * CreateAdd(Value *LHS, Value *RHS, const Twine &Name="", bool HasNUW=false, bool HasNSW=false)
Definition: IRBuilder.h:1256
void SetInsertPoint(BasicBlock *TheBB)
This specifies that created instructions should be appended to the end of the specified block.
Definition: IRBuilder.h:180
Value * CreateMul(Value *LHS, Value *RHS, const Twine &Name="", bool HasNUW=false, bool HasNSW=false)
Definition: IRBuilder.h:1290
Provides an 'InsertHelper' that calls a user-provided callback after performing the default insertion...
Definition: IRBuilder.h:76
This provides a uniform API for creating instructions and inserting them into a basic block: either a...
Definition: IRBuilder.h:2564
const Module * getModule() const
Return the module owning the function this instruction belongs to or nullptr it the function does not...
Definition: Instruction.cpp:70
const BasicBlock * getParent() const
Definition: Instruction.h:90
const Function * getFunction() const
Return the function this instruction belongs to.
Definition: Instruction.cpp:74
SymbolTableList< Instruction >::iterator eraseFromParent()
This method unlinks 'this' from the containing basic block and deletes it.
Definition: Instruction.cpp:82
This class represents a cast from an integer to a pointer.
A wrapper class for inspecting calls to intrinsic functions.
Definition: IntrinsicInst.h:47
Intrinsic::ID getIntrinsicID() const
Return the intrinsic ID of this intrinsic.
Definition: IntrinsicInst.h:54
This is an important class for using LLVM in a threaded context.
Definition: LLVMContext.h:67
An instruction for reading from memory.
Definition: Instructions.h:177
const DataLayout & getDataLayout() const
Get the data layout for the module's target platform.
Definition: Module.cpp:398
Evaluate the size and offset of an object pointed to by a Value*.
SizeOffsetEvalType visitExtractValueInst(ExtractValueInst &I)
SizeOffsetEvalType visitExtractElementInst(ExtractElementInst &I)
SizeOffsetEvalType visitPHINode(PHINode &PHI)
SizeOffsetEvalType visitSelectInst(SelectInst &I)
static SizeOffsetEvalType unknown()
SizeOffsetEvalType compute(Value *V)
bool anyKnown(SizeOffsetEvalType SizeOffset)
ObjectSizeOffsetEvaluator(const DataLayout &DL, const TargetLibraryInfo *TLI, LLVMContext &Context, ObjectSizeOpts EvalOpts={})
SizeOffsetEvalType visitCallBase(CallBase &CB)
SizeOffsetEvalType visitInstruction(Instruction &I)
SizeOffsetEvalType visitAllocaInst(AllocaInst &I)
bool bothKnown(SizeOffsetEvalType SizeOffset)
SizeOffsetEvalType visitIntToPtrInst(IntToPtrInst &)
SizeOffsetEvalType visitLoadInst(LoadInst &I)
SizeOffsetEvalType visitGEPOperator(GEPOperator &GEP)
Evaluate the size and offset of an object pointed to by a Value* statically.
SizeOffsetType visitAllocaInst(AllocaInst &I)
SizeOffsetType visitArgument(Argument &A)
SizeOffsetType visitGlobalVariable(GlobalVariable &GV)
SizeOffsetType visitSelectInst(SelectInst &I)
ObjectSizeOffsetVisitor(const DataLayout &DL, const TargetLibraryInfo *TLI, LLVMContext &Context, ObjectSizeOpts Options={})
SizeOffsetType visitCallBase(CallBase &CB)
SizeOffsetType visitExtractValueInst(ExtractValueInst &I)
SizeOffsetType visitConstantPointerNull(ConstantPointerNull &)
SizeOffsetType visitExtractElementInst(ExtractElementInst &I)
static bool bothKnown(const SizeOffsetType &SizeOffset)
SizeOffsetType visitUndefValue(UndefValue &)
SizeOffsetType visitGlobalAlias(GlobalAlias &GA)
SizeOffsetType visitIntToPtrInst(IntToPtrInst &)
static bool knownSize(const SizeOffsetType &SizeOffset)
SizeOffsetType visitLoadInst(LoadInst &I)
static bool knownOffset(const SizeOffsetType &SizeOffset)
SizeOffsetType visitInstruction(Instruction &I)
SizeOffsetType compute(Value *V)
SizeOffsetType visitPHINode(PHINode &)
void addIncoming(Value *V, BasicBlock *BB)
Add an incoming value to the end of the PHI list.
op_range incoming_values()
Value * hasConstantValue() const
If the specified PHI node always merges together the same value, return the value,...
unsigned getNumIncomingValues() const
Return the number of incoming edges.
unsigned getAddressSpace() const
Return the address space of the Pointer type.
Definition: DerivedTypes.h:693
static PoisonValue * get(Type *T)
Static factory methods - Return an 'poison' object of the specified type.
Definition: Constants.cpp:1743
This class represents the LLVM 'select' instruction.
std::pair< iterator, bool > insert(PtrType Ptr)
Inserts Ptr if and only if there is no element in the container equal to Ptr.
Definition: SmallPtrSet.h:365
bool empty() const
Definition: SmallVector.h:94
void push_back(const T &Elt)
Definition: SmallVector.h:416
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1200
StringRef - Represent a constant reference to a string, i.e.
Definition: StringRef.h:50
TargetFolder - Create constants with target dependent folding.
Definition: TargetFolder.h:34
Provides information about what library functions are available for the current target.
bool has(LibFunc F) const
Tests whether a library function is available.
bool getLibFunc(StringRef funcName, LibFunc &F) const
Searches for a particular function name.
The instances of the Type class are immutable: once they are created, they are never changed.
Definition: Type.h:45
bool isPointerTy() const
True if this is an instance of PointerType.
Definition: Type.h:256
bool isSized(SmallPtrSetImpl< Type * > *Visited=nullptr) const
Return true if it makes sense to take the size of this type.
Definition: Type.h:302
bool isVoidTy() const
Return true if this is 'void'.
Definition: Type.h:140
'undef' values are things that do not have specified contents.
Definition: Constants.h:1370
static UndefValue * get(Type *T)
Static factory methods - Return an 'undef' object of the specified type.
Definition: Constants.cpp:1724
Value * getOperand(unsigned i) const
Definition: User.h:169
LLVM Value Representation.
Definition: Value.h:74
Type * getType() const
All values are typed, get the type of this value.
Definition: Value.h:255
void replaceAllUsesWith(Value *V)
Change all uses of this to point to a new Value.
Definition: Value.cpp:535
constexpr bool isScalable() const
Returns whether the quantity is scaled by a runtime quantity (vscale).
Definition: TypeSize.h:166
constexpr ScalarTy getKnownMinValue() const
Returns the minimum value this quantity can represent.
Definition: TypeSize.h:163
An efficient, type-erasing, non-owning reference to a callable.
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
@ C
The default llvm calling convention, compatible with C.
Definition: CallingConv.h:34
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
@ Offset
Definition: DWP.cpp:440
Constant * getInitialValueOfAllocation(const Value *V, const TargetLibraryInfo *TLI, Type *Ty)
If this is a call to an allocation function that initializes memory to a fixed value,...
bool isUIntN(unsigned N, uint64_t x)
Checks if an unsigned integer fits into the given (dynamic) bit width.
Definition: MathExtras.h:256
std::pair< APInt, APInt > SizeOffsetType
AllocFnKind
Definition: Attributes.h:50
bool isRemovableAlloc(const CallBase *V, const TargetLibraryInfo *TLI)
Return true if this is a call to an allocation function that does not have side effects that we are r...
std::optional< StringRef > getAllocationFamily(const Value *I, const TargetLibraryInfo *TLI)
If a function is part of an allocation family (e.g.
Value * lowerObjectSizeCall(IntrinsicInst *ObjectSize, const DataLayout &DL, const TargetLibraryInfo *TLI, bool MustSucceed)
Try to turn a call to @llvm.objectsize into an integer value of the given Type.
Value * getAllocAlignment(const CallBase *V, const TargetLibraryInfo *TLI)
Gets the alignment argument for an aligned_alloc-like function, using either built-in knowledge based...
std::pair< Value *, Value * > SizeOffsetEvalType
bool isLibFreeFunction(const Function *F, const LibFunc TLIFn)
isLibFreeFunction - Returns true if the function is a builtin free()
Value * getReallocatedOperand(const CallBase *CB)
If this is a call to a realloc function, return the reallocated operand.
bool isAllocLikeFn(const Value *V, const TargetLibraryInfo *TLI)
Tests if a value is a call or invoke to a library function that allocates memory (either malloc,...
bool getObjectSize(const Value *Ptr, uint64_t &Size, const DataLayout &DL, const TargetLibraryInfo *TLI, ObjectSizeOpts Opts={})
Compute the size of the object pointed by Ptr.
Value * emitGEPOffset(IRBuilderBase *Builder, const DataLayout &DL, User *GEP, bool NoAssumptions=false)
Given a getelementptr instruction/constantexpr, emit the code necessary to compute the offset from th...
Definition: Local.cpp:22
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:163
uint64_t GetStringLength(const Value *V, unsigned CharSize=8)
If we can compute the length of the string pointed to by the specified pointer, return 'len+1'.
bool isMallocOrCallocLikeFn(const Value *V, const TargetLibraryInfo *TLI)
Tests if a value is a call or invoke to a library function that allocates memory similar to malloc or...
bool isReallocLikeFn(const Function *F)
Tests if a function is a call or invoke to a library function that reallocates memory (e....
uint64_t alignTo(uint64_t Size, Align A)
Returns a multiple of A needed to store Size bytes.
Definition: Alignment.h:155
Value * getFreedOperand(const CallBase *CB, const TargetLibraryInfo *TLI)
If this if a call to a free function, return the freed operand.
auto find_if(R &&Range, UnaryPredicate P)
Provide wrappers to std::find_if which take ranges instead of having to pass begin/end explicitly.
Definition: STLExtras.h:1846
auto predecessors(const MachineBasicBlock *BB)
bool isAllocationFn(const Value *V, const TargetLibraryInfo *TLI)
Tests if a value is a call or invoke to a library function that allocates or reallocates memory (eith...
std::optional< APInt > getAllocSize(const CallBase *CB, const TargetLibraryInfo *TLI, function_ref< const Value *(const Value *)> Mapper=[](const Value *V) { return V;})
Return the size of the requested allocation.
std::optional< bool > isImpliedByDomCondition(const Value *Cond, const Instruction *ContextI, const DataLayout &DL)
Return the boolean condition value in the context of the given instruction if it is known based on do...
bool isNewLikeFn(const Value *V, const TargetLibraryInfo *TLI)
Tests if a value is a call or invoke to a library function that allocates memory via new.
MallocFamily Family
unsigned NumParams
AllocType AllocTy
MallocFamily Family
unsigned NumParams
This struct is a compact representation of a valid (power of two) or undefined (0) alignment.
Definition: Alignment.h:117
Various options to control the behavior of getObjectSize.
bool NullIsUnknownSize
If this is true, null pointers in address space 0 will be treated as though they can't be evaluated.
Mode EvalMode
How we want to evaluate this object's size.
AAResults * AA
If set, used for more accurate evaluation.
bool RoundToAlign
Whether to round the result up to the alignment of allocas, byval arguments, and global variables.
@ ExactUnderlyingSizeAndOffset
All branches must be known and have the same underlying size and offset to be merged.
@ Max
Same as Min, except we pick the maximum size of all of the branches.
@ Min
Evaluate all branches of an unknown condition.
@ ExactSizeFromOffset
All branches must be known and have the same size, starting from the offset, to be merged.