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_ZnwmRKSt9nothrow_t, {MallocLike, 2, 0, -1, -1, MallocFamily::CPPNew}}, // new(unsigned long, nothrow)
119 {LibFunc_ZnwmSt11align_val_t, {OpNewLike, 2, 0, -1, 1, MallocFamily::CPPNewAligned}}, // new(unsigned long, align_val_t)
120 {LibFunc_ZnwmSt11align_val_tRKSt9nothrow_t, {MallocLike, 3, 0, -1, 1, MallocFamily::CPPNewAligned}}, // new(unsigned long, align_val_t, nothrow)
121 {LibFunc_Znaj, {OpNewLike, 1, 0, -1, -1, MallocFamily::CPPNewArray}}, // new[](unsigned int)
122 {LibFunc_ZnajRKSt9nothrow_t, {MallocLike, 2, 0, -1, -1, MallocFamily::CPPNewArray}}, // new[](unsigned int, nothrow)
123 {LibFunc_ZnajSt11align_val_t, {OpNewLike, 2, 0, -1, 1, MallocFamily::CPPNewArrayAligned}}, // new[](unsigned int, align_val_t)
124 {LibFunc_ZnajSt11align_val_tRKSt9nothrow_t, {MallocLike, 3, 0, -1, 1, MallocFamily::CPPNewArrayAligned}}, // new[](unsigned int, align_val_t, nothrow)
125 {LibFunc_Znam, {OpNewLike, 1, 0, -1, -1, MallocFamily::CPPNewArray}}, // new[](unsigned long)
126 {LibFunc_ZnamRKSt9nothrow_t, {MallocLike, 2, 0, -1, -1, MallocFamily::CPPNewArray}}, // new[](unsigned long, nothrow)
127 {LibFunc_ZnamSt11align_val_t, {OpNewLike, 2, 0, -1, 1, MallocFamily::CPPNewArrayAligned}}, // new[](unsigned long, align_val_t)
128 {LibFunc_ZnamSt11align_val_tRKSt9nothrow_t, {MallocLike, 3, 0, -1, 1, MallocFamily::CPPNewArrayAligned}}, // new[](unsigned long, align_val_t, nothrow)
129 {LibFunc_msvc_new_int, {OpNewLike, 1, 0, -1, -1, MallocFamily::MSVCNew}}, // new(unsigned int)
130 {LibFunc_msvc_new_int_nothrow, {MallocLike, 2, 0, -1, -1, MallocFamily::MSVCNew}}, // new(unsigned int, nothrow)
131 {LibFunc_msvc_new_longlong, {OpNewLike, 1, 0, -1, -1, MallocFamily::MSVCNew}}, // new(unsigned long long)
132 {LibFunc_msvc_new_longlong_nothrow, {MallocLike, 2, 0, -1, -1, MallocFamily::MSVCNew}}, // new(unsigned long long, nothrow)
133 {LibFunc_msvc_new_array_int, {OpNewLike, 1, 0, -1, -1, MallocFamily::MSVCArrayNew}}, // new[](unsigned int)
134 {LibFunc_msvc_new_array_int_nothrow, {MallocLike, 2, 0, -1, -1, MallocFamily::MSVCArrayNew}}, // new[](unsigned int, nothrow)
135 {LibFunc_msvc_new_array_longlong, {OpNewLike, 1, 0, -1, -1, MallocFamily::MSVCArrayNew}}, // new[](unsigned long long)
136 {LibFunc_msvc_new_array_longlong_nothrow, {MallocLike, 2, 0, -1, -1, MallocFamily::MSVCArrayNew}}, // new[](unsigned long long, nothrow)
137 {LibFunc_strdup, {StrDupLike, 1, -1, -1, -1, MallocFamily::Malloc}},
138 {LibFunc_dunder_strdup, {StrDupLike, 1, -1, -1, -1, MallocFamily::Malloc}},
139 {LibFunc_strndup, {StrDupLike, 2, 1, -1, -1, MallocFamily::Malloc}},
140 {LibFunc_dunder_strndup, {StrDupLike, 2, 1, -1, -1, MallocFamily::Malloc}},
141 {LibFunc___kmpc_alloc_shared, {MallocLike, 1, 0, -1, -1, MallocFamily::KmpcAllocShared}},
142};
143// clang-format on
144
145static const Function *getCalledFunction(const Value *V,
146 bool &IsNoBuiltin) {
147 // Don't care about intrinsics in this case.
148 if (isa<IntrinsicInst>(V))
149 return nullptr;
150
151 const auto *CB = dyn_cast<CallBase>(V);
152 if (!CB)
153 return nullptr;
154
155 IsNoBuiltin = CB->isNoBuiltin();
156
157 if (const Function *Callee = CB->getCalledFunction())
158 return Callee;
159 return nullptr;
160}
161
162/// Returns the allocation data for the given value if it's a call to a known
163/// allocation function.
164static std::optional<AllocFnsTy>
166 const TargetLibraryInfo *TLI) {
167 // Don't perform a slow TLI lookup, if this function doesn't return a pointer
168 // and thus can't be an allocation function.
169 if (!Callee->getReturnType()->isPointerTy())
170 return std::nullopt;
171
172 // Make sure that the function is available.
173 LibFunc TLIFn;
174 if (!TLI || !TLI->getLibFunc(*Callee, TLIFn) || !TLI->has(TLIFn))
175 return std::nullopt;
176
177 const auto *Iter = find_if(
178 AllocationFnData, [TLIFn](const std::pair<LibFunc, AllocFnsTy> &P) {
179 return P.first == TLIFn;
180 });
181
182 if (Iter == std::end(AllocationFnData))
183 return std::nullopt;
184
185 const AllocFnsTy *FnData = &Iter->second;
186 if ((FnData->AllocTy & AllocTy) != FnData->AllocTy)
187 return std::nullopt;
188
189 // Check function prototype.
190 int FstParam = FnData->FstParam;
191 int SndParam = FnData->SndParam;
193
194 if (FTy->getReturnType()->isPointerTy() &&
195 FTy->getNumParams() == FnData->NumParams &&
196 (FstParam < 0 ||
197 (FTy->getParamType(FstParam)->isIntegerTy(32) ||
198 FTy->getParamType(FstParam)->isIntegerTy(64))) &&
199 (SndParam < 0 ||
200 FTy->getParamType(SndParam)->isIntegerTy(32) ||
201 FTy->getParamType(SndParam)->isIntegerTy(64)))
202 return *FnData;
203 return std::nullopt;
204}
205
206static std::optional<AllocFnsTy>
208 const TargetLibraryInfo *TLI) {
209 bool IsNoBuiltinCall;
210 if (const Function *Callee = getCalledFunction(V, IsNoBuiltinCall))
211 if (!IsNoBuiltinCall)
212 return getAllocationDataForFunction(Callee, AllocTy, TLI);
213 return std::nullopt;
214}
215
216static std::optional<AllocFnsTy>
218 function_ref<const TargetLibraryInfo &(Function &)> GetTLI) {
219 bool IsNoBuiltinCall;
220 if (const Function *Callee = getCalledFunction(V, IsNoBuiltinCall))
221 if (!IsNoBuiltinCall)
223 Callee, AllocTy, &GetTLI(const_cast<Function &>(*Callee)));
224 return std::nullopt;
225}
226
227static std::optional<AllocFnsTy>
229 bool IsNoBuiltinCall;
230 const Function *Callee =
231 getCalledFunction(V, IsNoBuiltinCall);
232 if (!Callee)
233 return std::nullopt;
234
235 // Prefer to use existing information over allocsize. This will give us an
236 // accurate AllocTy.
237 if (!IsNoBuiltinCall)
238 if (std::optional<AllocFnsTy> Data =
240 return Data;
241
242 Attribute Attr = Callee->getFnAttribute(Attribute::AllocSize);
243 if (Attr == Attribute())
244 return std::nullopt;
245
246 std::pair<unsigned, std::optional<unsigned>> Args = Attr.getAllocSizeArgs();
247
248 AllocFnsTy Result;
249 // Because allocsize only tells us how many bytes are allocated, we're not
250 // really allowed to assume anything, so we use MallocLike.
251 Result.AllocTy = MallocLike;
252 Result.NumParams = Callee->getNumOperands();
253 Result.FstParam = Args.first;
254 Result.SndParam = Args.second.value_or(-1);
255 // Allocsize has no way to specify an alignment argument
256 Result.AlignParam = -1;
257 return Result;
258}
259
261 if (const auto *CB = dyn_cast<CallBase>(V)) {
262 Attribute Attr = CB->getFnAttr(Attribute::AllocKind);
263 if (Attr.isValid())
264 return AllocFnKind(Attr.getValueAsInt());
265 }
266 return AllocFnKind::Unknown;
267}
268
270 Attribute Attr = F->getFnAttribute(Attribute::AllocKind);
271 if (Attr.isValid())
272 return AllocFnKind(Attr.getValueAsInt());
273 return AllocFnKind::Unknown;
274}
275
276static bool checkFnAllocKind(const Value *V, AllocFnKind Wanted) {
277 return (getAllocFnKind(V) & Wanted) != AllocFnKind::Unknown;
278}
279
280static bool checkFnAllocKind(const Function *F, AllocFnKind Wanted) {
281 return (getAllocFnKind(F) & Wanted) != AllocFnKind::Unknown;
282}
283
284/// Tests if a value is a call or invoke to a library function that
285/// allocates or reallocates memory (either malloc, calloc, realloc, or strdup
286/// like).
287bool llvm::isAllocationFn(const Value *V, const TargetLibraryInfo *TLI) {
288 return getAllocationData(V, AnyAlloc, TLI).has_value() ||
289 checkFnAllocKind(V, AllocFnKind::Alloc | AllocFnKind::Realloc);
290}
292 const Value *V,
293 function_ref<const TargetLibraryInfo &(Function &)> GetTLI) {
294 return getAllocationData(V, AnyAlloc, GetTLI).has_value() ||
295 checkFnAllocKind(V, AllocFnKind::Alloc | AllocFnKind::Realloc);
296}
297
298/// Tests if a value is a call or invoke to a library function that
299/// allocates memory via new.
300bool llvm::isNewLikeFn(const Value *V, const TargetLibraryInfo *TLI) {
301 return getAllocationData(V, OpNewLike, TLI).has_value();
302}
303
304/// Tests if a value is a call or invoke to a library function that
305/// allocates memory similar to malloc or calloc.
307 // TODO: Function behavior does not match name.
308 return getAllocationData(V, MallocOrOpNewLike, TLI).has_value();
309}
310
311/// Tests if a value is a call or invoke to a library function that
312/// allocates memory (either malloc, calloc, or strdup like).
313bool llvm::isAllocLikeFn(const Value *V, const TargetLibraryInfo *TLI) {
314 return getAllocationData(V, AllocLike, TLI).has_value() ||
315 checkFnAllocKind(V, AllocFnKind::Alloc);
316}
317
318/// Tests if a functions is a call or invoke to a library function that
319/// reallocates memory (e.g., realloc).
321 return checkFnAllocKind(F, AllocFnKind::Realloc);
322}
323
325 if (checkFnAllocKind(CB, AllocFnKind::Realloc))
326 return CB->getArgOperandWithAttribute(Attribute::AllocatedPointer);
327 return nullptr;
328}
329
331 // Note: Removability is highly dependent on the source language. For
332 // example, recent C++ requires direct calls to the global allocation
333 // [basic.stc.dynamic.allocation] to be observable unless part of a new
334 // expression [expr.new paragraph 13].
335
336 // Historically we've treated the C family allocation routines and operator
337 // new as removable
338 return isAllocLikeFn(CB, TLI);
339}
340
342 const TargetLibraryInfo *TLI) {
343 const std::optional<AllocFnsTy> FnData = getAllocationData(V, AnyAlloc, TLI);
344 if (FnData && FnData->AlignParam >= 0) {
345 return V->getOperand(FnData->AlignParam);
346 }
347 return V->getArgOperandWithAttribute(Attribute::AllocAlign);
348}
349
350/// When we're compiling N-bit code, and the user uses parameters that are
351/// greater than N bits (e.g. uint64_t on a 32-bit build), we can run into
352/// trouble with APInt size issues. This function handles resizing + overflow
353/// checks for us. Check and zext or trunc \p I depending on IntTyBits and
354/// I's value.
355static bool CheckedZextOrTrunc(APInt &I, unsigned IntTyBits) {
356 // More bits than we can handle. Checking the bit width isn't necessary, but
357 // it's faster than checking active bits, and should give `false` in the
358 // vast majority of cases.
359 if (I.getBitWidth() > IntTyBits && I.getActiveBits() > IntTyBits)
360 return false;
361 if (I.getBitWidth() != IntTyBits)
362 I = I.zextOrTrunc(IntTyBits);
363 return true;
364}
365
366std::optional<APInt>
368 function_ref<const Value *(const Value *)> Mapper) {
369 // Note: This handles both explicitly listed allocation functions and
370 // allocsize. The code structure could stand to be cleaned up a bit.
371 std::optional<AllocFnsTy> FnData = getAllocationSize(CB, TLI);
372 if (!FnData)
373 return std::nullopt;
374
375 // Get the index type for this address space, results and intermediate
376 // computations are performed at that width.
377 auto &DL = CB->getModule()->getDataLayout();
378 const unsigned IntTyBits = DL.getIndexTypeSizeInBits(CB->getType());
379
380 // Handle strdup-like functions separately.
381 if (FnData->AllocTy == StrDupLike) {
382 APInt Size(IntTyBits, GetStringLength(Mapper(CB->getArgOperand(0))));
383 if (!Size)
384 return std::nullopt;
385
386 // Strndup limits strlen.
387 if (FnData->FstParam > 0) {
388 const ConstantInt *Arg =
389 dyn_cast<ConstantInt>(Mapper(CB->getArgOperand(FnData->FstParam)));
390 if (!Arg)
391 return std::nullopt;
392
393 APInt MaxSize = Arg->getValue().zext(IntTyBits);
394 if (Size.ugt(MaxSize))
395 Size = MaxSize + 1;
396 }
397 return Size;
398 }
399
400 const ConstantInt *Arg =
401 dyn_cast<ConstantInt>(Mapper(CB->getArgOperand(FnData->FstParam)));
402 if (!Arg)
403 return std::nullopt;
404
405 APInt Size = Arg->getValue();
406 if (!CheckedZextOrTrunc(Size, IntTyBits))
407 return std::nullopt;
408
409 // Size is determined by just 1 parameter.
410 if (FnData->SndParam < 0)
411 return Size;
412
413 Arg = dyn_cast<ConstantInt>(Mapper(CB->getArgOperand(FnData->SndParam)));
414 if (!Arg)
415 return std::nullopt;
416
417 APInt NumElems = Arg->getValue();
418 if (!CheckedZextOrTrunc(NumElems, IntTyBits))
419 return std::nullopt;
420
421 bool Overflow;
422 Size = Size.umul_ov(NumElems, Overflow);
423 if (Overflow)
424 return std::nullopt;
425 return Size;
426}
427
429 const TargetLibraryInfo *TLI,
430 Type *Ty) {
431 auto *Alloc = dyn_cast<CallBase>(V);
432 if (!Alloc)
433 return nullptr;
434
435 // malloc are uninitialized (undef)
436 if (getAllocationData(Alloc, MallocOrOpNewLike, TLI).has_value())
437 return UndefValue::get(Ty);
438
439 AllocFnKind AK = getAllocFnKind(Alloc);
440 if ((AK & AllocFnKind::Uninitialized) != AllocFnKind::Unknown)
441 return UndefValue::get(Ty);
442 if ((AK & AllocFnKind::Zeroed) != AllocFnKind::Unknown)
443 return Constant::getNullValue(Ty);
444
445 return nullptr;
446}
447
448struct FreeFnsTy {
449 unsigned NumParams;
450 // Name of default allocator function to group malloc/free calls by family
452};
453
454// clang-format off
455static const std::pair<LibFunc, FreeFnsTy> FreeFnData[] = {
456 {LibFunc_ZdlPv, {1, MallocFamily::CPPNew}}, // operator delete(void*)
457 {LibFunc_ZdaPv, {1, MallocFamily::CPPNewArray}}, // operator delete[](void*)
458 {LibFunc_msvc_delete_ptr32, {1, MallocFamily::MSVCNew}}, // operator delete(void*)
459 {LibFunc_msvc_delete_ptr64, {1, MallocFamily::MSVCNew}}, // operator delete(void*)
460 {LibFunc_msvc_delete_array_ptr32, {1, MallocFamily::MSVCArrayNew}}, // operator delete[](void*)
461 {LibFunc_msvc_delete_array_ptr64, {1, MallocFamily::MSVCArrayNew}}, // operator delete[](void*)
462 {LibFunc_ZdlPvj, {2, MallocFamily::CPPNew}}, // delete(void*, uint)
463 {LibFunc_ZdlPvm, {2, MallocFamily::CPPNew}}, // delete(void*, ulong)
464 {LibFunc_ZdlPvRKSt9nothrow_t, {2, MallocFamily::CPPNew}}, // delete(void*, nothrow)
465 {LibFunc_ZdlPvSt11align_val_t, {2, MallocFamily::CPPNewAligned}}, // delete(void*, align_val_t)
466 {LibFunc_ZdaPvj, {2, MallocFamily::CPPNewArray}}, // delete[](void*, uint)
467 {LibFunc_ZdaPvm, {2, MallocFamily::CPPNewArray}}, // delete[](void*, ulong)
468 {LibFunc_ZdaPvRKSt9nothrow_t, {2, MallocFamily::CPPNewArray}}, // delete[](void*, nothrow)
469 {LibFunc_ZdaPvSt11align_val_t, {2, MallocFamily::CPPNewArrayAligned}}, // delete[](void*, align_val_t)
470 {LibFunc_msvc_delete_ptr32_int, {2, MallocFamily::MSVCNew}}, // delete(void*, uint)
471 {LibFunc_msvc_delete_ptr64_longlong, {2, MallocFamily::MSVCNew}}, // delete(void*, ulonglong)
472 {LibFunc_msvc_delete_ptr32_nothrow, {2, MallocFamily::MSVCNew}}, // delete(void*, nothrow)
473 {LibFunc_msvc_delete_ptr64_nothrow, {2, MallocFamily::MSVCNew}}, // delete(void*, nothrow)
474 {LibFunc_msvc_delete_array_ptr32_int, {2, MallocFamily::MSVCArrayNew}}, // delete[](void*, uint)
475 {LibFunc_msvc_delete_array_ptr64_longlong, {2, MallocFamily::MSVCArrayNew}}, // delete[](void*, ulonglong)
476 {LibFunc_msvc_delete_array_ptr32_nothrow, {2, MallocFamily::MSVCArrayNew}}, // delete[](void*, nothrow)
477 {LibFunc_msvc_delete_array_ptr64_nothrow, {2, MallocFamily::MSVCArrayNew}}, // delete[](void*, nothrow)
478 {LibFunc___kmpc_free_shared, {2, MallocFamily::KmpcAllocShared}}, // OpenMP Offloading RTL free
479 {LibFunc_ZdlPvSt11align_val_tRKSt9nothrow_t, {3, MallocFamily::CPPNewAligned}}, // delete(void*, align_val_t, nothrow)
480 {LibFunc_ZdaPvSt11align_val_tRKSt9nothrow_t, {3, MallocFamily::CPPNewArrayAligned}}, // delete[](void*, align_val_t, nothrow)
481 {LibFunc_ZdlPvjSt11align_val_t, {3, MallocFamily::CPPNewAligned}}, // delete(void*, unsigned int, align_val_t)
482 {LibFunc_ZdlPvmSt11align_val_t, {3, MallocFamily::CPPNewAligned}}, // delete(void*, unsigned long, align_val_t)
483 {LibFunc_ZdaPvjSt11align_val_t, {3, MallocFamily::CPPNewArrayAligned}}, // delete[](void*, unsigned int, align_val_t)
484 {LibFunc_ZdaPvmSt11align_val_t, {3, MallocFamily::CPPNewArrayAligned}}, // delete[](void*, unsigned long, align_val_t)
485};
486// clang-format on
487
488std::optional<FreeFnsTy> getFreeFunctionDataForFunction(const Function *Callee,
489 const LibFunc TLIFn) {
490 const auto *Iter =
491 find_if(FreeFnData, [TLIFn](const std::pair<LibFunc, FreeFnsTy> &P) {
492 return P.first == TLIFn;
493 });
494 if (Iter == std::end(FreeFnData))
495 return std::nullopt;
496 return Iter->second;
497}
498
499std::optional<StringRef>
501 bool IsNoBuiltin;
502 const Function *Callee = getCalledFunction(I, IsNoBuiltin);
503 if (Callee == nullptr || IsNoBuiltin)
504 return std::nullopt;
505 LibFunc TLIFn;
506
507 if (TLI && TLI->getLibFunc(*Callee, TLIFn) && TLI->has(TLIFn)) {
508 // Callee is some known library function.
509 const auto AllocData = getAllocationDataForFunction(Callee, AnyAlloc, TLI);
510 if (AllocData)
511 return mangledNameForMallocFamily(AllocData->Family);
512 const auto FreeData = getFreeFunctionDataForFunction(Callee, TLIFn);
513 if (FreeData)
514 return mangledNameForMallocFamily(FreeData->Family);
515 }
516 // Callee isn't a known library function, still check attributes.
517 if (checkFnAllocKind(I, AllocFnKind::Free | AllocFnKind::Alloc |
518 AllocFnKind::Realloc)) {
519 Attribute Attr = cast<CallBase>(I)->getFnAttr("alloc-family");
520 if (Attr.isValid())
521 return Attr.getValueAsString();
522 }
523 return std::nullopt;
524}
525
526/// isLibFreeFunction - Returns true if the function is a builtin free()
527bool llvm::isLibFreeFunction(const Function *F, const LibFunc TLIFn) {
528 std::optional<FreeFnsTy> FnData = getFreeFunctionDataForFunction(F, TLIFn);
529 if (!FnData)
530 return checkFnAllocKind(F, AllocFnKind::Free);
531
532 // Check free prototype.
533 // FIXME: workaround for PR5130, this will be obsolete when a nobuiltin
534 // attribute will exist.
535 FunctionType *FTy = F->getFunctionType();
536 if (!FTy->getReturnType()->isVoidTy())
537 return false;
538 if (FTy->getNumParams() != FnData->NumParams)
539 return false;
540 if (!FTy->getParamType(0)->isPointerTy())
541 return false;
542
543 return true;
544}
545
547 bool IsNoBuiltinCall;
548 const Function *Callee = getCalledFunction(CB, IsNoBuiltinCall);
549 if (Callee == nullptr || IsNoBuiltinCall)
550 return nullptr;
551
552 LibFunc TLIFn;
553 if (TLI && TLI->getLibFunc(*Callee, TLIFn) && TLI->has(TLIFn) &&
554 isLibFreeFunction(Callee, TLIFn)) {
555 // All currently supported free functions free the first argument.
556 return CB->getArgOperand(0);
557 }
558
559 if (checkFnAllocKind(CB, AllocFnKind::Free))
560 return CB->getArgOperandWithAttribute(Attribute::AllocatedPointer);
561
562 return nullptr;
563}
564
565//===----------------------------------------------------------------------===//
566// Utility functions to compute size of objects.
567//
569 if (Data.second.isNegative() || Data.first.ult(Data.second))
570 return APInt(Data.first.getBitWidth(), 0);
571 return Data.first - Data.second;
572}
573
574/// Compute the size of the object pointed by Ptr. Returns true and the
575/// object size in Size if successful, and false otherwise.
576/// If RoundToAlign is true, then Size is rounded up to the alignment of
577/// allocas, byval arguments, and global variables.
579 const TargetLibraryInfo *TLI, ObjectSizeOpts Opts) {
580 ObjectSizeOffsetVisitor Visitor(DL, TLI, Ptr->getContext(), Opts);
581 SizeOffsetType Data = Visitor.compute(const_cast<Value*>(Ptr));
582 if (!Visitor.bothKnown(Data))
583 return false;
584
586 return true;
587}
588
590 const DataLayout &DL,
591 const TargetLibraryInfo *TLI,
592 bool MustSucceed) {
593 return lowerObjectSizeCall(ObjectSize, DL, TLI, /*AAResults=*/nullptr,
594 MustSucceed);
595}
596
598 const DataLayout &DL,
599 const TargetLibraryInfo *TLI, AAResults *AA,
600 bool MustSucceed) {
601 assert(ObjectSize->getIntrinsicID() == Intrinsic::objectsize &&
602 "ObjectSize must be a call to llvm.objectsize!");
603
604 bool MaxVal = cast<ConstantInt>(ObjectSize->getArgOperand(1))->isZero();
605 ObjectSizeOpts EvalOptions;
606 EvalOptions.AA = AA;
607
608 // Unless we have to fold this to something, try to be as accurate as
609 // possible.
610 if (MustSucceed)
611 EvalOptions.EvalMode =
612 MaxVal ? ObjectSizeOpts::Mode::Max : ObjectSizeOpts::Mode::Min;
613 else
614 EvalOptions.EvalMode = ObjectSizeOpts::Mode::ExactSizeFromOffset;
615
616 EvalOptions.NullIsUnknownSize =
617 cast<ConstantInt>(ObjectSize->getArgOperand(2))->isOne();
618
619 auto *ResultType = cast<IntegerType>(ObjectSize->getType());
620 bool StaticOnly = cast<ConstantInt>(ObjectSize->getArgOperand(3))->isZero();
621 if (StaticOnly) {
622 // FIXME: Does it make sense to just return a failure value if the size won't
623 // fit in the output and `!MustSucceed`?
625 if (getObjectSize(ObjectSize->getArgOperand(0), Size, DL, TLI, EvalOptions) &&
626 isUIntN(ResultType->getBitWidth(), Size))
627 return ConstantInt::get(ResultType, Size);
628 } else {
629 LLVMContext &Ctx = ObjectSize->getFunction()->getContext();
630 ObjectSizeOffsetEvaluator Eval(DL, TLI, Ctx, EvalOptions);
631 SizeOffsetEvalType SizeOffsetPair =
632 Eval.compute(ObjectSize->getArgOperand(0));
633
634 if (SizeOffsetPair != ObjectSizeOffsetEvaluator::unknown()) {
636 Builder.SetInsertPoint(ObjectSize);
637
638 // If we've outside the end of the object, then we can always access
639 // exactly 0 bytes.
640 Value *ResultSize =
641 Builder.CreateSub(SizeOffsetPair.first, SizeOffsetPair.second);
642 Value *UseZero =
643 Builder.CreateICmpULT(SizeOffsetPair.first, SizeOffsetPair.second);
644 ResultSize = Builder.CreateZExtOrTrunc(ResultSize, ResultType);
645 Value *Ret = Builder.CreateSelect(
646 UseZero, ConstantInt::get(ResultType, 0), ResultSize);
647
648 // The non-constant size expression cannot evaluate to -1.
649 if (!isa<Constant>(SizeOffsetPair.first) ||
650 !isa<Constant>(SizeOffsetPair.second))
651 Builder.CreateAssumption(
652 Builder.CreateICmpNE(Ret, ConstantInt::get(ResultType, -1)));
653
654 return Ret;
655 }
656 }
657
658 if (!MustSucceed)
659 return nullptr;
660
661 return ConstantInt::get(ResultType, MaxVal ? -1ULL : 0);
662}
663
664STATISTIC(ObjectVisitorArgument,
665 "Number of arguments with unsolved size and offset");
666STATISTIC(ObjectVisitorLoad,
667 "Number of load instructions with unsolved size and offset");
668
669APInt ObjectSizeOffsetVisitor::align(APInt Size, MaybeAlign Alignment) {
670 if (Options.RoundToAlign && Alignment)
671 return APInt(IntTyBits, alignTo(Size.getZExtValue(), *Alignment));
672 return Size;
673}
674
676 const TargetLibraryInfo *TLI,
677 LLVMContext &Context,
679 : DL(DL), TLI(TLI), Options(Options) {
680 // Pointer size must be rechecked for each object visited since it could have
681 // a different address space.
682}
683
685 unsigned InitialIntTyBits = DL.getIndexTypeSizeInBits(V->getType());
686
687 // Stripping pointer casts can strip address space casts which can change the
688 // index type size. The invariant is that we use the value type to determine
689 // the index type size and if we stripped address space casts we have to
690 // readjust the APInt as we pass it upwards in order for the APInt to match
691 // the type the caller passed in.
692 APInt Offset(InitialIntTyBits, 0);
694 DL, Offset, /* AllowNonInbounds */ true, /* AllowInvariantGroup */ true);
695
696 // Later we use the index type size and zero but it will match the type of the
697 // value that is passed to computeImpl.
698 IntTyBits = DL.getIndexTypeSizeInBits(V->getType());
699 Zero = APInt::getZero(IntTyBits);
700
701 bool IndexTypeSizeChanged = InitialIntTyBits != IntTyBits;
702 if (!IndexTypeSizeChanged && Offset.isZero())
703 return computeImpl(V);
704
705 // We stripped an address space cast that changed the index type size or we
706 // accumulated some constant offset (or both). Readjust the bit width to match
707 // the argument index type size and apply the offset, as required.
708 SizeOffsetType SOT = computeImpl(V);
709 if (IndexTypeSizeChanged) {
710 if (knownSize(SOT) && !::CheckedZextOrTrunc(SOT.first, InitialIntTyBits))
711 SOT.first = APInt();
712 if (knownOffset(SOT) && !::CheckedZextOrTrunc(SOT.second, InitialIntTyBits))
713 SOT.second = APInt();
714 }
715 // If the computed offset is "unknown" we cannot add the stripped offset.
716 return {SOT.first,
717 SOT.second.getBitWidth() > 1 ? SOT.second + Offset : SOT.second};
718}
719
720SizeOffsetType ObjectSizeOffsetVisitor::computeImpl(Value *V) {
721 if (Instruction *I = dyn_cast<Instruction>(V)) {
722 // If we have already seen this instruction, bail out. Cycles can happen in
723 // unreachable code after constant propagation.
724 if (!SeenInsts.insert(I).second)
725 return unknown();
726
727 return visit(*I);
728 }
729 if (Argument *A = dyn_cast<Argument>(V))
730 return visitArgument(*A);
731 if (ConstantPointerNull *P = dyn_cast<ConstantPointerNull>(V))
733 if (GlobalAlias *GA = dyn_cast<GlobalAlias>(V))
734 return visitGlobalAlias(*GA);
735 if (GlobalVariable *GV = dyn_cast<GlobalVariable>(V))
736 return visitGlobalVariable(*GV);
737 if (UndefValue *UV = dyn_cast<UndefValue>(V))
738 return visitUndefValue(*UV);
739
740 LLVM_DEBUG(dbgs() << "ObjectSizeOffsetVisitor::compute() unhandled value: "
741 << *V << '\n');
742 return unknown();
743}
744
745bool ObjectSizeOffsetVisitor::CheckedZextOrTrunc(APInt &I) {
746 return ::CheckedZextOrTrunc(I, IntTyBits);
747}
748
750 TypeSize ElemSize = DL.getTypeAllocSize(I.getAllocatedType());
751 if (ElemSize.isScalable() && Options.EvalMode != ObjectSizeOpts::Mode::Min)
752 return unknown();
753 APInt Size(IntTyBits, ElemSize.getKnownMinValue());
754 if (!I.isArrayAllocation())
755 return std::make_pair(align(Size, I.getAlign()), Zero);
756
757 Value *ArraySize = I.getArraySize();
758 if (const ConstantInt *C = dyn_cast<ConstantInt>(ArraySize)) {
759 APInt NumElems = C->getValue();
760 if (!CheckedZextOrTrunc(NumElems))
761 return unknown();
762
763 bool Overflow;
764 Size = Size.umul_ov(NumElems, Overflow);
765 return Overflow ? unknown()
766 : std::make_pair(align(Size, I.getAlign()), Zero);
767 }
768 return unknown();
769}
770
772 Type *MemoryTy = A.getPointeeInMemoryValueType();
773 // No interprocedural analysis is done at the moment.
774 if (!MemoryTy|| !MemoryTy->isSized()) {
775 ++ObjectVisitorArgument;
776 return unknown();
777 }
778
779 APInt Size(IntTyBits, DL.getTypeAllocSize(MemoryTy));
780 return std::make_pair(align(Size, A.getParamAlign()), Zero);
781}
782
784 if (std::optional<APInt> Size = getAllocSize(&CB, TLI))
785 return std::make_pair(*Size, Zero);
786 return unknown();
787}
788
791 // If null is unknown, there's nothing we can do. Additionally, non-zero
792 // address spaces can make use of null, so we don't presume to know anything
793 // about that.
794 //
795 // TODO: How should this work with address space casts? We currently just drop
796 // them on the floor, but it's unclear what we should do when a NULL from
797 // addrspace(1) gets casted to addrspace(0) (or vice-versa).
798 if (Options.NullIsUnknownSize || CPN.getType()->getAddressSpace())
799 return unknown();
800 return std::make_pair(Zero, Zero);
801}
802
805 return unknown();
806}
807
810 // Easy cases were already folded by previous passes.
811 return unknown();
812}
813
815 if (GA.isInterposable())
816 return unknown();
817 return compute(GA.getAliasee());
818}
819
821 if (!GV.hasDefinitiveInitializer())
822 return unknown();
823
824 APInt Size(IntTyBits, DL.getTypeAllocSize(GV.getValueType()));
825 return std::make_pair(align(Size, GV.getAlign()), Zero);
826}
827
829 // clueless
830 return unknown();
831}
832
833SizeOffsetType ObjectSizeOffsetVisitor::findLoadSizeOffset(
836 unsigned &ScannedInstCount) {
837 constexpr unsigned MaxInstsToScan = 128;
838
839 auto Where = VisitedBlocks.find(&BB);
840 if (Where != VisitedBlocks.end())
841 return Where->second;
842
843 auto Unknown = [this, &BB, &VisitedBlocks]() {
844 return VisitedBlocks[&BB] = unknown();
845 };
846 auto Known = [&BB, &VisitedBlocks](SizeOffsetType SO) {
847 return VisitedBlocks[&BB] = SO;
848 };
849
850 do {
851 Instruction &I = *From;
852
853 if (I.isDebugOrPseudoInst())
854 continue;
855
856 if (++ScannedInstCount > MaxInstsToScan)
857 return Unknown();
858
859 if (!I.mayWriteToMemory())
860 continue;
861
862 if (auto *SI = dyn_cast<StoreInst>(&I)) {
863 AliasResult AR =
864 Options.AA->alias(SI->getPointerOperand(), Load.getPointerOperand());
865 switch ((AliasResult::Kind)AR) {
867 continue;
869 if (SI->getValueOperand()->getType()->isPointerTy())
870 return Known(compute(SI->getValueOperand()));
871 else
872 return Unknown(); // No handling of non-pointer values by `compute`.
873 default:
874 return Unknown();
875 }
876 }
877
878 if (auto *CB = dyn_cast<CallBase>(&I)) {
880 // Bail out on indirect call.
881 if (!Callee)
882 return Unknown();
883
884 LibFunc TLIFn;
885 if (!TLI || !TLI->getLibFunc(*CB->getCalledFunction(), TLIFn) ||
886 !TLI->has(TLIFn))
887 return Unknown();
888
889 // TODO: There's probably more interesting case to support here.
890 if (TLIFn != LibFunc_posix_memalign)
891 return Unknown();
892
893 AliasResult AR =
894 Options.AA->alias(CB->getOperand(0), Load.getPointerOperand());
895 switch ((AliasResult::Kind)AR) {
897 continue;
899 break;
900 default:
901 return Unknown();
902 }
903
904 // Is the error status of posix_memalign correctly checked? If not it
905 // would be incorrect to assume it succeeds and load doesn't see the
906 // previous value.
907 std::optional<bool> Checked = isImpliedByDomCondition(
908 ICmpInst::ICMP_EQ, CB, ConstantInt::get(CB->getType(), 0), &Load, DL);
909 if (!Checked || !*Checked)
910 return Unknown();
911
912 Value *Size = CB->getOperand(2);
913 auto *C = dyn_cast<ConstantInt>(Size);
914 if (!C)
915 return Unknown();
916
917 return Known({C->getValue(), APInt(C->getValue().getBitWidth(), 0)});
918 }
919
920 return Unknown();
921 } while (From-- != BB.begin());
922
923 SmallVector<SizeOffsetType> PredecessorSizeOffsets;
924 for (auto *PredBB : predecessors(&BB)) {
925 PredecessorSizeOffsets.push_back(findLoadSizeOffset(
926 Load, *PredBB, BasicBlock::iterator(PredBB->getTerminator()),
927 VisitedBlocks, ScannedInstCount));
928 if (!bothKnown(PredecessorSizeOffsets.back()))
929 return Unknown();
930 }
931
932 if (PredecessorSizeOffsets.empty())
933 return Unknown();
934
935 return Known(std::accumulate(PredecessorSizeOffsets.begin() + 1,
936 PredecessorSizeOffsets.end(),
937 PredecessorSizeOffsets.front(),
938 [this](SizeOffsetType LHS, SizeOffsetType RHS) {
939 return combineSizeOffset(LHS, RHS);
940 }));
941}
942
944 if (!Options.AA) {
945 ++ObjectVisitorLoad;
946 return unknown();
947 }
948
950 unsigned ScannedInstCount = 0;
951 SizeOffsetType SO =
952 findLoadSizeOffset(LI, *LI.getParent(), BasicBlock::iterator(LI),
953 VisitedBlocks, ScannedInstCount);
954 if (!bothKnown(SO))
955 ++ObjectVisitorLoad;
956 return SO;
957}
958
959SizeOffsetType ObjectSizeOffsetVisitor::combineSizeOffset(SizeOffsetType LHS,
960 SizeOffsetType RHS) {
961 if (!bothKnown(LHS) || !bothKnown(RHS))
962 return unknown();
963
964 switch (Options.EvalMode) {
966 return (getSizeWithOverflow(LHS).slt(getSizeWithOverflow(RHS))) ? LHS : RHS;
968 return (getSizeWithOverflow(LHS).sgt(getSizeWithOverflow(RHS))) ? LHS : RHS;
970 return (getSizeWithOverflow(LHS).eq(getSizeWithOverflow(RHS))) ? LHS
971 : unknown();
973 return LHS == RHS && LHS.second.eq(RHS.second) ? LHS : unknown();
974 }
975 llvm_unreachable("missing an eval mode");
976}
977
979 auto IncomingValues = PN.incoming_values();
980 return std::accumulate(IncomingValues.begin() + 1, IncomingValues.end(),
981 compute(*IncomingValues.begin()),
982 [this](SizeOffsetType LHS, Value *VRHS) {
983 return combineSizeOffset(LHS, compute(VRHS));
984 });
985}
986
988 return combineSizeOffset(compute(I.getTrueValue()),
989 compute(I.getFalseValue()));
990}
991
993 return std::make_pair(Zero, Zero);
994}
995
997 LLVM_DEBUG(dbgs() << "ObjectSizeOffsetVisitor unknown instruction:" << I
998 << '\n');
999 return unknown();
1000}
1001
1003 const DataLayout &DL, const TargetLibraryInfo *TLI, LLVMContext &Context,
1004 ObjectSizeOpts EvalOpts)
1005 : DL(DL), TLI(TLI), Context(Context),
1008 [&](Instruction *I) { InsertedInstructions.insert(I); })),
1009 EvalOpts(EvalOpts) {
1010 // IntTy and Zero must be set for each compute() since the address space may
1011 // be different for later objects.
1012}
1013
1015 // XXX - Are vectors of pointers possible here?
1016 IntTy = cast<IntegerType>(DL.getIndexType(V->getType()));
1017 Zero = ConstantInt::get(IntTy, 0);
1018
1019 SizeOffsetEvalType Result = compute_(V);
1020
1021 if (!bothKnown(Result)) {
1022 // Erase everything that was computed in this iteration from the cache, so
1023 // that no dangling references are left behind. We could be a bit smarter if
1024 // we kept a dependency graph. It's probably not worth the complexity.
1025 for (const Value *SeenVal : SeenVals) {
1026 CacheMapTy::iterator CacheIt = CacheMap.find(SeenVal);
1027 // non-computable results can be safely cached
1028 if (CacheIt != CacheMap.end() && anyKnown(CacheIt->second))
1029 CacheMap.erase(CacheIt);
1030 }
1031
1032 // Erase any instructions we inserted as part of the traversal.
1033 for (Instruction *I : InsertedInstructions) {
1034 I->replaceAllUsesWith(PoisonValue::get(I->getType()));
1035 I->eraseFromParent();
1036 }
1037 }
1038
1039 SeenVals.clear();
1040 InsertedInstructions.clear();
1041 return Result;
1042}
1043
1044SizeOffsetEvalType ObjectSizeOffsetEvaluator::compute_(Value *V) {
1045 ObjectSizeOffsetVisitor Visitor(DL, TLI, Context, EvalOpts);
1046 SizeOffsetType Const = Visitor.compute(V);
1047 if (Visitor.bothKnown(Const))
1048 return std::make_pair(ConstantInt::get(Context, Const.first),
1049 ConstantInt::get(Context, Const.second));
1050
1051 V = V->stripPointerCasts();
1052
1053 // Check cache.
1054 CacheMapTy::iterator CacheIt = CacheMap.find(V);
1055 if (CacheIt != CacheMap.end())
1056 return CacheIt->second;
1057
1058 // Always generate code immediately before the instruction being
1059 // processed, so that the generated code dominates the same BBs.
1060 BuilderTy::InsertPointGuard Guard(Builder);
1061 if (Instruction *I = dyn_cast<Instruction>(V))
1062 Builder.SetInsertPoint(I);
1063
1064 // Now compute the size and offset.
1065 SizeOffsetEvalType Result;
1066
1067 // Record the pointers that were handled in this run, so that they can be
1068 // cleaned later if something fails. We also use this set to break cycles that
1069 // can occur in dead code.
1070 if (!SeenVals.insert(V).second) {
1071 Result = unknown();
1072 } else if (GEPOperator *GEP = dyn_cast<GEPOperator>(V)) {
1073 Result = visitGEPOperator(*GEP);
1074 } else if (Instruction *I = dyn_cast<Instruction>(V)) {
1075 Result = visit(*I);
1076 } else if (isa<Argument>(V) ||
1077 (isa<ConstantExpr>(V) &&
1078 cast<ConstantExpr>(V)->getOpcode() == Instruction::IntToPtr) ||
1079 isa<GlobalAlias>(V) ||
1080 isa<GlobalVariable>(V)) {
1081 // Ignore values where we cannot do more than ObjectSizeVisitor.
1082 Result = unknown();
1083 } else {
1084 LLVM_DEBUG(
1085 dbgs() << "ObjectSizeOffsetEvaluator::compute() unhandled value: " << *V
1086 << '\n');
1087 Result = unknown();
1088 }
1089
1090 // Don't reuse CacheIt since it may be invalid at this point.
1091 CacheMap[V] = Result;
1092 return Result;
1093}
1094
1096 if (!I.getAllocatedType()->isSized())
1097 return unknown();
1098
1099 // must be a VLA
1100 assert(I.isArrayAllocation());
1101
1102 // If needed, adjust the alloca's operand size to match the pointer size.
1103 // Subsequent math operations expect the types to match.
1104 Value *ArraySize = Builder.CreateZExtOrTrunc(
1105 I.getArraySize(), DL.getIntPtrType(I.getContext()));
1106 assert(ArraySize->getType() == Zero->getType() &&
1107 "Expected zero constant to have pointer type");
1108
1109 Value *Size = ConstantInt::get(ArraySize->getType(),
1110 DL.getTypeAllocSize(I.getAllocatedType()));
1111 Size = Builder.CreateMul(Size, ArraySize);
1112 return std::make_pair(Size, Zero);
1113}
1114
1116 std::optional<AllocFnsTy> FnData = getAllocationSize(&CB, TLI);
1117 if (!FnData)
1118 return unknown();
1119
1120 // Handle strdup-like functions separately.
1121 if (FnData->AllocTy == StrDupLike) {
1122 // TODO: implement evaluation of strdup/strndup
1123 return unknown();
1124 }
1125
1126 Value *FirstArg = CB.getArgOperand(FnData->FstParam);
1127 FirstArg = Builder.CreateZExtOrTrunc(FirstArg, IntTy);
1128 if (FnData->SndParam < 0)
1129 return std::make_pair(FirstArg, Zero);
1130
1131 Value *SecondArg = CB.getArgOperand(FnData->SndParam);
1132 SecondArg = Builder.CreateZExtOrTrunc(SecondArg, IntTy);
1133 Value *Size = Builder.CreateMul(FirstArg, SecondArg);
1134 return std::make_pair(Size, Zero);
1135}
1136
1139 return unknown();
1140}
1141
1144 return unknown();
1145}
1146
1149 SizeOffsetEvalType PtrData = compute_(GEP.getPointerOperand());
1150 if (!bothKnown(PtrData))
1151 return unknown();
1152
1153 Value *Offset = emitGEPOffset(&Builder, DL, &GEP, /*NoAssumptions=*/true);
1154 Offset = Builder.CreateAdd(PtrData.second, Offset);
1155 return std::make_pair(PtrData.first, Offset);
1156}
1157
1159 // clueless
1160 return unknown();
1161}
1162
1164 return unknown();
1165}
1166
1168 // Create 2 PHIs: one for size and another for offset.
1169 PHINode *SizePHI = Builder.CreatePHI(IntTy, PHI.getNumIncomingValues());
1170 PHINode *OffsetPHI = Builder.CreatePHI(IntTy, PHI.getNumIncomingValues());
1171
1172 // Insert right away in the cache to handle recursive PHIs.
1173 CacheMap[&PHI] = std::make_pair(SizePHI, OffsetPHI);
1174
1175 // Compute offset/size for each PHI incoming pointer.
1176 for (unsigned i = 0, e = PHI.getNumIncomingValues(); i != e; ++i) {
1177 Builder.SetInsertPoint(&*PHI.getIncomingBlock(i)->getFirstInsertionPt());
1178 SizeOffsetEvalType EdgeData = compute_(PHI.getIncomingValue(i));
1179
1180 if (!bothKnown(EdgeData)) {
1181 OffsetPHI->replaceAllUsesWith(PoisonValue::get(IntTy));
1182 OffsetPHI->eraseFromParent();
1183 InsertedInstructions.erase(OffsetPHI);
1184 SizePHI->replaceAllUsesWith(PoisonValue::get(IntTy));
1185 SizePHI->eraseFromParent();
1186 InsertedInstructions.erase(SizePHI);
1187 return unknown();
1188 }
1189 SizePHI->addIncoming(EdgeData.first, PHI.getIncomingBlock(i));
1190 OffsetPHI->addIncoming(EdgeData.second, PHI.getIncomingBlock(i));
1191 }
1192
1193 Value *Size = SizePHI, *Offset = OffsetPHI;
1194 if (Value *Tmp = SizePHI->hasConstantValue()) {
1195 Size = Tmp;
1196 SizePHI->replaceAllUsesWith(Size);
1197 SizePHI->eraseFromParent();
1198 InsertedInstructions.erase(SizePHI);
1199 }
1200 if (Value *Tmp = OffsetPHI->hasConstantValue()) {
1201 Offset = Tmp;
1202 OffsetPHI->replaceAllUsesWith(Offset);
1203 OffsetPHI->eraseFromParent();
1204 InsertedInstructions.erase(OffsetPHI);
1205 }
1206 return std::make_pair(Size, Offset);
1207}
1208
1210 SizeOffsetEvalType TrueSide = compute_(I.getTrueValue());
1211 SizeOffsetEvalType FalseSide = compute_(I.getFalseValue());
1212
1213 if (!bothKnown(TrueSide) || !bothKnown(FalseSide))
1214 return unknown();
1215 if (TrueSide == FalseSide)
1216 return TrueSide;
1217
1218 Value *Size = Builder.CreateSelect(I.getCondition(), TrueSide.first,
1219 FalseSide.first);
1220 Value *Offset = Builder.CreateSelect(I.getCondition(), TrueSide.second,
1221 FalseSide.second);
1222 return std::make_pair(Size, Offset);
1223}
1224
1226 LLVM_DEBUG(dbgs() << "ObjectSizeOffsetEvaluator unknown instruction:" << I
1227 << '\n');
1228 return unknown();
1229}
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:1494
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:291
std::pair< unsigned, std::optional< unsigned > > getAllocSizeArgs() const
Returns the argument numbers for the allocsize attribute.
Definition: Attributes.cpp:363
StringRef getValueAsString() const
Return the attribute's value as a string.
Definition: Attributes.cpp:312
bool isValid() const
Return true if the attribute is any kind of attribute.
Definition: Attributes.h:185
LLVM Basic Block Representation.
Definition: BasicBlock.h:56
iterator begin()
Instruction iterator methods.
Definition: BasicBlock.h:314
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:1184
Function * getCalledFunction() const
Returns the function called, or null if this is an indirect function invocation or the function signa...
Definition: InstrTypes.h:1406
Value * getArgOperand(unsigned i) const
Definition: InstrTypes.h:1351
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:739
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:887
A constant pointer value that points to null.
Definition: Constants.h:534
PointerType * getType() const
Specialize the getType() method to always return an PointerType, which reduces the amount of casting ...
Definition: Constants.h:550
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:114
IntegerType * getIntPtrType(LLVMContext &C, unsigned AddressSpace=0) const
Returns an integer type with size at least as big as that of a pointer in the given address space.
Definition: DataLayout.cpp:849
unsigned getIndexTypeSizeInBits(Type *Ty) const
Layout size of the index used in GEP calculation.
Definition: DataLayout.cpp:735
TypeSize getTypeAllocSize(Type *Ty) const
Returns the offset in bytes between successive objects of the specified type, including alignment pad...
Definition: DataLayout.h:507
Type * getIndexType(Type *PtrTy) const
Returns the type of a GEP index.
Definition: DataLayout.cpp:876
iterator find(const_arg_type_t< KeyT > Val)
Definition: DenseMap.h:150
bool erase(const KeyT &Val)
Definition: DenseMap.h:302
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:315
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:102
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:1926
Value * CreateSelect(Value *C, Value *True, Value *False, const Twine &Name="", Instruction *MDFrom=nullptr)
Definition: IRBuilder.cpp:1126
PHINode * CreatePHI(Type *Ty, unsigned NumReservedValues, const Twine &Name="")
Definition: IRBuilder.h:2278
Value * CreateAdd(Value *LHS, Value *RHS, const Twine &Name="", bool HasNUW=false, bool HasNSW=false)
Definition: IRBuilder.h:1242
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:1276
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:2550
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 getAddressSpace() const
Return the address space of the Pointer type.
Definition: DerivedTypes.h:682
static PoisonValue * get(Type *T)
Static factory methods - Return an 'poison' object of the specified type.
Definition: Constants.cpp:1759
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:249
bool isSized(SmallPtrSetImpl< Type * > *Visited=nullptr) const
Return true if it makes sense to take the size of this type.
Definition: Type.h:295
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:1382
static UndefValue * get(Type *T)
Static factory methods - Return an 'undef' object of the specified type.
Definition: Constants.cpp:1740
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
const Value * stripAndAccumulateConstantOffsets(const DataLayout &DL, APInt &Offset, bool AllowNonInbounds, bool AllowInvariantGroup=false, function_ref< bool(Value &Value, APInt &Offset)> ExternalAnalysis=nullptr) const
Accumulate the constant offset this value has compared to a base pointer.
void replaceAllUsesWith(Value *V)
Change all uses of this to point to a new Value.
Definition: Value.cpp:532
const Value * stripPointerCasts() const
Strip off pointer casts, all-zero GEPs and address space casts.
Definition: Value.cpp:685
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:406
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:252
std::pair< APInt, APInt > SizeOffsetType
AllocFnKind
Definition: Attributes.h:49
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:1762
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.