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