llvm/lib/Analysis/MemoryBuiltins.cpp

   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
  50 using namespace llvm;
  51
  52 #define DEBUG_TYPE "memory-builtins"
  53
  54 static 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
  60 enum 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
  69 enum 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
  81 StringRef 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
 105 struct 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.
 119 static 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
 160 static 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.
 179 static std::optional<AllocFnsTy>
 180 getAllocationDataForFunction(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
 221 static std::optional<AllocFnsTy>
 222 getAllocationData(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
 231 static std::optional<AllocFnsTy>
 232 getAllocationData(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
 242 static std::optional<AllocFnsTy>
 243 getAllocationSize(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
 275 static 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
 284 static AllocFnKind getAllocFnKind(const Function *F) {
 285   return F->getAttributes().getAllocKind();
 286 }
 287
 288 static bool checkFnAllocKind(const Value *V, AllocFnKind Wanted) {
 289   return (getAllocFnKind(V) & Wanted) != AllocFnKind::Unknown;
 290 }
 291
 292 static 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).
 299 bool llvm::isAllocationFn(const Value *V, const TargetLibraryInfo *TLI) {
 300   return getAllocationData(V, AnyAlloc, TLI).has_value() ||
 301          checkFnAllocKind(V, AllocFnKind::Alloc | AllocFnKind::Realloc);
 302 }
 303 bool 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.
 312 bool 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.
 318 bool 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).
 325 bool 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).
 332 bool llvm::isReallocLikeFn(const Function *F) {
 333   return checkFnAllocKind(F, AllocFnKind::Realloc);
 334 }
 335
 336 Value *llvm::getReallocatedOperand(const CallBase *CB) {
 337   if (checkFnAllocKind(CB, AllocFnKind::Realloc))
 338     return CB->getArgOperandWithAttribute(Attribute::AllocatedPointer);
 339   return nullptr;
 340 }
 341
 342 bool 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
 353 Value *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.
 367 static 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
 378 std::optional<APInt>
 379 llvm::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
 440 Constant *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
 460 struct 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
 467 static 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
 500 std::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
 511 std::optional<StringRef>
 512 llvm::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()
 539 bool 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
 558 Value *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 //
 580 static 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.
 592 bool 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
 603 Value *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
 611 Value *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
 681 STATISTIC(ObjectVisitorArgument,
 682           "Number of arguments with unsolved size and offset");
 683 STATISTIC(ObjectVisitorLoad,
 684           "Number of load instructions with unsolved size and offset");
 685
 686 APInt ObjectSizeOffsetVisitor::align(APInt Size, MaybeAlign Alignment) {
 687   if (Options.RoundToAlign && Alignment)
 688     return APInt(IntTyBits, alignTo(Size.getZExtValue(), *Alignment));
 689   return Size;
 690 }
 691
 692 ObjectSizeOffsetVisitor::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
 701 SizeOffsetAPInt ObjectSizeOffsetVisitor::compute(Value *V) {
 702   InstructionsVisited = 0;
 703   return computeImpl(V);
 704 }
 705
 706 SizeOffsetAPInt 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
 744 SizeOffsetAPInt 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
 776 bool ObjectSizeOffsetVisitor::CheckedZextOrTrunc(APInt &I) {
 777   return ::CheckedZextOrTrunc(I, IntTyBits);
 778 }
 779
 780 SizeOffsetAPInt 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
 802 SizeOffsetAPInt 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
 814 SizeOffsetAPInt ObjectSizeOffsetVisitor::visitCallBase(CallBase &CB) {
 815   if (std::optional<APInt> Size = getAllocSize(&CB, TLI))
 816     return SizeOffsetAPInt(*Size, Zero);
 817   return ObjectSizeOffsetVisitor::unknown();
 818 }
 819
 820 SizeOffsetAPInt
 821 ObjectSizeOffsetVisitor::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
 834 SizeOffsetAPInt
 835 ObjectSizeOffsetVisitor::visitExtractElementInst(ExtractElementInst &) {
 836   return ObjectSizeOffsetVisitor::unknown();
 837 }
 838
 839 SizeOffsetAPInt
 840 ObjectSizeOffsetVisitor::visitExtractValueInst(ExtractValueInst &) {
 841   // Easy cases were already folded by previous passes.
 842   return ObjectSizeOffsetVisitor::unknown();
 843 }
 844
 845 SizeOffsetAPInt ObjectSizeOffsetVisitor::visitGlobalAlias(GlobalAlias &GA) {
 846   if (GA.isInterposable())
 847     return ObjectSizeOffsetVisitor::unknown();
 848   return computeImpl(GA.getAliasee());
 849 }
 850
 851 SizeOffsetAPInt
 852 ObjectSizeOffsetVisitor::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
 862 SizeOffsetAPInt ObjectSizeOffsetVisitor::visitIntToPtrInst(IntToPtrInst &) {
 863   // clueless
 864   return ObjectSizeOffsetVisitor::unknown();
 865 }
 866
 867 SizeOffsetAPInt 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
 977 SizeOffsetAPInt 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
 993 SizeOffsetAPInt
 994 ObjectSizeOffsetVisitor::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
1014 SizeOffsetAPInt 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
1025 SizeOffsetAPInt ObjectSizeOffsetVisitor::visitSelectInst(SelectInst &I) {
1026   return combineSizeOffset(computeImpl(I.getTrueValue()),
1027                            computeImpl(I.getFalseValue()));
1028 }
1029
1030 SizeOffsetAPInt ObjectSizeOffsetVisitor::visitUndefValue(UndefValue &) {
1031   return SizeOffsetAPInt(Zero, Zero);
1032 }
1033
1034 SizeOffsetAPInt 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...
1041 SizeOffsetValue::SizeOffsetValue(const SizeOffsetWeakTrackingVH &SOT)
1042     : SizeOffsetType(SOT.Size, SOT.Offset) {}
1043
1044 ObjectSizeOffsetEvaluator::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
1056 SizeOffsetValue 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
1086 SizeOffsetValue 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
1137 SizeOffsetValue 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
1158 SizeOffsetValue 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
1180 SizeOffsetValue
1181 ObjectSizeOffsetEvaluator::visitExtractElementInst(ExtractElementInst &) {
1182   return ObjectSizeOffsetEvaluator::unknown();
1183 }
1184
1185 SizeOffsetValue
1186 ObjectSizeOffsetEvaluator::visitExtractValueInst(ExtractValueInst &) {
1187   return ObjectSizeOffsetEvaluator::unknown();
1188 }
1189
1190 SizeOffsetValue 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
1200 SizeOffsetValue ObjectSizeOffsetEvaluator::visitIntToPtrInst(IntToPtrInst &) {
1201   // clueless
1202   return ObjectSizeOffsetEvaluator::unknown();
1203 }
1204
1205 SizeOffsetValue ObjectSizeOffsetEvaluator::visitLoadInst(LoadInst &LI) {
1206   return ObjectSizeOffsetEvaluator::unknown();
1207 }
1208
1209 SizeOffsetValue 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
1252 SizeOffsetValue 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
1268 SizeOffsetValue ObjectSizeOffsetEvaluator::visitInstruction(Instruction &I) {
1269   LLVM_DEBUG(dbgs() << "ObjectSizeOffsetEvaluator unknown instruction:" << I
1270                     << '\n');
1271   return ObjectSizeOffsetEvaluator::unknown();
1272 }