1468 lines · 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-exception6//7//===----------------------------------------------------------------------===//8//9// This family of functions identifies calls to builtin functions that allocate10// 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 <utility>48 49using namespace llvm;50 51#define DEBUG_TYPE "memory-builtins"52 53static cl::opt<unsigned> ObjectSizeOffsetVisitorMaxVisitInstructions(54 "object-size-offset-visitor-max-visit-instructions",55 cl::desc("Maximum number of instructions for ObjectSizeOffsetVisitor to "56 "look at"),57 cl::init(100));58 59enum AllocType : uint8_t {60 OpNewLike = 1<<0, // allocates; never returns null61 MallocLike = 1<<1, // allocates; may return null62 StrDupLike = 1<<2,63 MallocOrOpNewLike = MallocLike | OpNewLike,64 AllocLike = MallocOrOpNewLike | StrDupLike,65 AnyAlloc = AllocLike66};67 68enum class MallocFamily {69 Malloc,70 CPPNew, // new(unsigned int)71 CPPNewAligned, // new(unsigned int, align_val_t)72 CPPNewArray, // new[](unsigned int)73 CPPNewArrayAligned, // new[](unsigned long, align_val_t)74 MSVCNew, // new(unsigned int)75 MSVCArrayNew, // new[](unsigned int)76 VecMalloc,77 KmpcAllocShared,78};79 80StringRef mangledNameForMallocFamily(const MallocFamily &Family) {81 switch (Family) {82 case MallocFamily::Malloc:83 return "malloc";84 case MallocFamily::CPPNew:85 return "_Znwm";86 case MallocFamily::CPPNewAligned:87 return "_ZnwmSt11align_val_t";88 case MallocFamily::CPPNewArray:89 return "_Znam";90 case MallocFamily::CPPNewArrayAligned:91 return "_ZnamSt11align_val_t";92 case MallocFamily::MSVCNew:93 return "??2@YAPAXI@Z";94 case MallocFamily::MSVCArrayNew:95 return "??_U@YAPAXI@Z";96 case MallocFamily::VecMalloc:97 return "vec_malloc";98 case MallocFamily::KmpcAllocShared:99 return "__kmpc_alloc_shared";100 }101 llvm_unreachable("missing an alloc family");102}103 104struct AllocFnsTy {105 AllocType AllocTy;106 unsigned NumParams;107 // First and Second size parameters (or -1 if unused)108 int FstParam, SndParam;109 // Alignment parameter for aligned_alloc and aligned new110 int AlignParam;111 // Name of default allocator function to group malloc/free calls by family112 MallocFamily Family;113};114 115// clang-format off116// FIXME: certain users need more information. E.g., SimplifyLibCalls needs to117// know which functions are nounwind, noalias, nocapture parameters, etc.118static const std::pair<LibFunc, AllocFnsTy> AllocationFnData[] = {119 {LibFunc_Znwj, {OpNewLike, 1, 0, -1, -1, MallocFamily::CPPNew}}, // new(unsigned int)120 {LibFunc_ZnwjRKSt9nothrow_t, {MallocLike, 2, 0, -1, -1, MallocFamily::CPPNew}}, // new(unsigned int, nothrow)121 {LibFunc_ZnwjSt11align_val_t, {OpNewLike, 2, 0, -1, 1, MallocFamily::CPPNewAligned}}, // new(unsigned int, align_val_t)122 {LibFunc_ZnwjSt11align_val_tRKSt9nothrow_t, {MallocLike, 3, 0, -1, 1, MallocFamily::CPPNewAligned}}, // new(unsigned int, align_val_t, nothrow)123 {LibFunc_Znwm, {OpNewLike, 1, 0, -1, -1, MallocFamily::CPPNew}}, // new(unsigned long)124 {LibFunc_Znwm12__hot_cold_t, {OpNewLike, 2, 0, -1, -1, MallocFamily::CPPNew}}, // new(unsigned long, __hot_cold_t)125 {LibFunc_ZnwmRKSt9nothrow_t, {MallocLike, 2, 0, -1, -1, MallocFamily::CPPNew}}, // new(unsigned long, nothrow)126 {LibFunc_ZnwmRKSt9nothrow_t12__hot_cold_t, {MallocLike, 3, 0, -1, -1, MallocFamily::CPPNew}}, // new(unsigned long, nothrow, __hot_cold_t)127 {LibFunc_ZnwmSt11align_val_t, {OpNewLike, 2, 0, -1, 1, MallocFamily::CPPNewAligned}}, // new(unsigned long, align_val_t)128 {LibFunc_ZnwmSt11align_val_t12__hot_cold_t, {OpNewLike, 3, 0, -1, 1, MallocFamily::CPPNewAligned}}, // new(unsigned long, align_val_t, __hot_cold_t)129 {LibFunc_ZnwmSt11align_val_tRKSt9nothrow_t, {MallocLike, 3, 0, -1, 1, MallocFamily::CPPNewAligned}}, // new(unsigned long, align_val_t, nothrow)130 {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)131 {LibFunc_Znaj, {OpNewLike, 1, 0, -1, -1, MallocFamily::CPPNewArray}}, // new[](unsigned int)132 {LibFunc_ZnajRKSt9nothrow_t, {MallocLike, 2, 0, -1, -1, MallocFamily::CPPNewArray}}, // new[](unsigned int, nothrow)133 {LibFunc_ZnajSt11align_val_t, {OpNewLike, 2, 0, -1, 1, MallocFamily::CPPNewArrayAligned}}, // new[](unsigned int, align_val_t)134 {LibFunc_ZnajSt11align_val_tRKSt9nothrow_t, {MallocLike, 3, 0, -1, 1, MallocFamily::CPPNewArrayAligned}}, // new[](unsigned int, align_val_t, nothrow)135 {LibFunc_Znam, {OpNewLike, 1, 0, -1, -1, MallocFamily::CPPNewArray}}, // new[](unsigned long)136 {LibFunc_Znam12__hot_cold_t, {OpNewLike, 2, 0, -1, -1, MallocFamily::CPPNew}}, // new[](unsigned long, __hot_cold_t)137 {LibFunc_ZnamRKSt9nothrow_t, {MallocLike, 2, 0, -1, -1, MallocFamily::CPPNewArray}}, // new[](unsigned long, nothrow)138 {LibFunc_ZnamRKSt9nothrow_t12__hot_cold_t, {MallocLike, 3, 0, -1, -1, MallocFamily::CPPNew}}, // new[](unsigned long, nothrow, __hot_cold_t)139 {LibFunc_ZnamSt11align_val_t, {OpNewLike, 2, 0, -1, 1, MallocFamily::CPPNewArrayAligned}}, // new[](unsigned long, align_val_t)140 {LibFunc_ZnamSt11align_val_t12__hot_cold_t, {OpNewLike, 3, 0, -1, 1, MallocFamily::CPPNewAligned}}, // new[](unsigned long, align_val_t, __hot_cold_t)141 {LibFunc_ZnamSt11align_val_tRKSt9nothrow_t, {MallocLike, 3, 0, -1, 1, MallocFamily::CPPNewArrayAligned}}, // new[](unsigned long, align_val_t, nothrow)142 {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)143 {LibFunc_msvc_new_int, {OpNewLike, 1, 0, -1, -1, MallocFamily::MSVCNew}}, // new(unsigned int)144 {LibFunc_msvc_new_int_nothrow, {MallocLike, 2, 0, -1, -1, MallocFamily::MSVCNew}}, // new(unsigned int, nothrow)145 {LibFunc_msvc_new_longlong, {OpNewLike, 1, 0, -1, -1, MallocFamily::MSVCNew}}, // new(unsigned long long)146 {LibFunc_msvc_new_longlong_nothrow, {MallocLike, 2, 0, -1, -1, MallocFamily::MSVCNew}}, // new(unsigned long long, nothrow)147 {LibFunc_msvc_new_array_int, {OpNewLike, 1, 0, -1, -1, MallocFamily::MSVCArrayNew}}, // new[](unsigned int)148 {LibFunc_msvc_new_array_int_nothrow, {MallocLike, 2, 0, -1, -1, MallocFamily::MSVCArrayNew}}, // new[](unsigned int, nothrow)149 {LibFunc_msvc_new_array_longlong, {OpNewLike, 1, 0, -1, -1, MallocFamily::MSVCArrayNew}}, // new[](unsigned long long)150 {LibFunc_msvc_new_array_longlong_nothrow, {MallocLike, 2, 0, -1, -1, MallocFamily::MSVCArrayNew}}, // new[](unsigned long long, nothrow)151 {LibFunc_strdup, {StrDupLike, 1, -1, -1, -1, MallocFamily::Malloc}},152 {LibFunc_dunder_strdup, {StrDupLike, 1, -1, -1, -1, MallocFamily::Malloc}},153 {LibFunc_strndup, {StrDupLike, 2, 1, -1, -1, MallocFamily::Malloc}},154 {LibFunc_dunder_strndup, {StrDupLike, 2, 1, -1, -1, MallocFamily::Malloc}},155 {LibFunc___kmpc_alloc_shared, {MallocLike, 1, 0, -1, -1, MallocFamily::KmpcAllocShared}},156};157// clang-format on158 159static const Function *getCalledFunction(const Value *V) {160 // Don't care about intrinsics in this case.161 if (isa<IntrinsicInst>(V))162 return nullptr;163 164 const auto *CB = dyn_cast<CallBase>(V);165 if (!CB)166 return nullptr;167 168 if (CB->isNoBuiltin())169 return nullptr;170 171 return CB->getCalledFunction();172}173 174/// Returns the allocation data for the given value if it's a call to a known175/// allocation function.176static std::optional<AllocFnsTy>177getAllocationDataForFunction(const Function *Callee, AllocType AllocTy,178 const TargetLibraryInfo *TLI) {179 // Don't perform a slow TLI lookup, if this function doesn't return a pointer180 // and thus can't be an allocation function.181 if (!Callee->getReturnType()->isPointerTy())182 return std::nullopt;183 184 // Make sure that the function is available.185 LibFunc TLIFn;186 if (!TLI || !TLI->getLibFunc(*Callee, TLIFn) || !TLI->has(TLIFn))187 return std::nullopt;188 189 const auto *Iter = find_if(190 AllocationFnData, [TLIFn](const std::pair<LibFunc, AllocFnsTy> &P) {191 return P.first == TLIFn;192 });193 194 if (Iter == std::end(AllocationFnData))195 return std::nullopt;196 197 const AllocFnsTy *FnData = &Iter->second;198 if ((FnData->AllocTy & AllocTy) != FnData->AllocTy)199 return std::nullopt;200 201 // Check function prototype.202 int FstParam = FnData->FstParam;203 int SndParam = FnData->SndParam;204 FunctionType *FTy = Callee->getFunctionType();205 206 if (FTy->getReturnType()->isPointerTy() &&207 FTy->getNumParams() == FnData->NumParams &&208 (FstParam < 0 ||209 (FTy->getParamType(FstParam)->isIntegerTy(32) ||210 FTy->getParamType(FstParam)->isIntegerTy(64))) &&211 (SndParam < 0 ||212 FTy->getParamType(SndParam)->isIntegerTy(32) ||213 FTy->getParamType(SndParam)->isIntegerTy(64)))214 return *FnData;215 return std::nullopt;216}217 218static std::optional<AllocFnsTy>219getAllocationData(const Value *V, AllocType AllocTy,220 const TargetLibraryInfo *TLI) {221 if (const Function *Callee = getCalledFunction(V))222 return getAllocationDataForFunction(Callee, AllocTy, TLI);223 return std::nullopt;224}225 226static std::optional<AllocFnsTy>227getAllocationData(const Value *V, AllocType AllocTy,228 function_ref<const TargetLibraryInfo &(Function &)> GetTLI) {229 if (const Function *Callee = getCalledFunction(V))230 return getAllocationDataForFunction(231 Callee, AllocTy, &GetTLI(const_cast<Function &>(*Callee)));232 return std::nullopt;233}234 235static std::optional<AllocFnsTy>236getAllocationSize(const CallBase *CB, const TargetLibraryInfo *TLI) {237 if (const Function *Callee = getCalledFunction(CB)) {238 // Prefer to use existing information over allocsize. This will give us an239 // accurate AllocTy.240 if (std::optional<AllocFnsTy> Data =241 getAllocationDataForFunction(Callee, AnyAlloc, TLI))242 return Data;243 }244 245 Attribute Attr = CB->getFnAttr(Attribute::AllocSize);246 if (Attr == Attribute())247 return std::nullopt;248 249 std::pair<unsigned, std::optional<unsigned>> Args = Attr.getAllocSizeArgs();250 251 AllocFnsTy Result;252 // Because allocsize only tells us how many bytes are allocated, we're not253 // really allowed to assume anything, so we use MallocLike.254 Result.AllocTy = MallocLike;255 Result.NumParams = CB->arg_size();256 Result.FstParam = Args.first;257 Result.SndParam = Args.second.value_or(-1);258 // Allocsize has no way to specify an alignment argument259 Result.AlignParam = -1;260 return Result;261}262 263static AllocFnKind getAllocFnKind(const Value *V) {264 if (const auto *CB = dyn_cast<CallBase>(V)) {265 Attribute Attr = CB->getFnAttr(Attribute::AllocKind);266 if (Attr.isValid())267 return AllocFnKind(Attr.getValueAsInt());268 }269 return AllocFnKind::Unknown;270}271 272static AllocFnKind getAllocFnKind(const Function *F) {273 return F->getAttributes().getAllocKind();274}275 276static bool checkFnAllocKind(const Value *V, AllocFnKind Wanted) {277 return (getAllocFnKind(V) & Wanted) != AllocFnKind::Unknown;278}279 280static bool checkFnAllocKind(const Function *F, AllocFnKind Wanted) {281 return (getAllocFnKind(F) & Wanted) != AllocFnKind::Unknown;282}283 284/// Tests if a value is a call or invoke to a library function that285/// allocates or reallocates memory (either malloc, calloc, realloc, or strdup286/// like).287bool llvm::isAllocationFn(const Value *V, const TargetLibraryInfo *TLI) {288 return getAllocationData(V, AnyAlloc, TLI).has_value() ||289 checkFnAllocKind(V, AllocFnKind::Alloc | AllocFnKind::Realloc);290}291bool llvm::isAllocationFn(292 const Value *V,293 function_ref<const TargetLibraryInfo &(Function &)> GetTLI) {294 return getAllocationData(V, AnyAlloc, GetTLI).has_value() ||295 checkFnAllocKind(V, AllocFnKind::Alloc | AllocFnKind::Realloc);296}297 298/// Tests if a value is a call or invoke to a library function that299/// allocates memory via new.300bool llvm::isNewLikeFn(const Value *V, const TargetLibraryInfo *TLI) {301 return getAllocationData(V, OpNewLike, TLI).has_value();302}303 304/// Tests if a value is a call or invoke to a library function that305/// allocates memory similar to malloc or calloc.306bool llvm::isMallocOrCallocLikeFn(const Value *V, const TargetLibraryInfo *TLI) {307 // TODO: Function behavior does not match name.308 return getAllocationData(V, MallocOrOpNewLike, TLI).has_value();309}310 311/// Tests if a value is a call or invoke to a library function that312/// allocates memory (either malloc, calloc, or strdup like).313bool llvm::isAllocLikeFn(const Value *V, const TargetLibraryInfo *TLI) {314 return getAllocationData(V, AllocLike, TLI).has_value() ||315 checkFnAllocKind(V, AllocFnKind::Alloc);316}317 318/// Tests if a functions is a call or invoke to a library function that319/// reallocates memory (e.g., realloc).320bool llvm::isReallocLikeFn(const Function *F) {321 return checkFnAllocKind(F, AllocFnKind::Realloc);322}323 324Value *llvm::getReallocatedOperand(const CallBase *CB) {325 if (checkFnAllocKind(CB, AllocFnKind::Realloc))326 return CB->getArgOperandWithAttribute(Attribute::AllocatedPointer);327 return nullptr;328}329 330bool llvm::isRemovableAlloc(const CallBase *CB, const TargetLibraryInfo *TLI) {331 // Note: Removability is highly dependent on the source language. For332 // example, recent C++ requires direct calls to the global allocation333 // [basic.stc.dynamic.allocation] to be observable unless part of a new334 // expression [expr.new paragraph 13].335 336 // Historically we've treated the C family allocation routines and operator337 // new as removable338 return isAllocLikeFn(CB, TLI);339}340 341Value *llvm::getAllocAlignment(const CallBase *V,342 const TargetLibraryInfo *TLI) {343 const std::optional<AllocFnsTy> FnData = getAllocationData(V, AnyAlloc, TLI);344 if (FnData && FnData->AlignParam >= 0) {345 return V->getOperand(FnData->AlignParam);346 }347 return V->getArgOperandWithAttribute(Attribute::AllocAlign);348}349 350/// When we're compiling N-bit code, and the user uses parameters that are351/// greater than N bits (e.g. uint64_t on a 32-bit build), we can run into352/// trouble with APInt size issues. This function handles resizing + overflow353/// checks for us. Check and zext or trunc \p I depending on IntTyBits and354/// I's value.355static bool CheckedZextOrTrunc(APInt &I, unsigned IntTyBits) {356 // More bits than we can handle. Checking the bit width isn't necessary, but357 // it's faster than checking active bits, and should give `false` in the358 // vast majority of cases.359 if (I.getBitWidth() > IntTyBits && I.getActiveBits() > IntTyBits)360 return false;361 if (I.getBitWidth() != IntTyBits)362 I = I.zextOrTrunc(IntTyBits);363 return true;364}365 366std::optional<APInt>367llvm::getAllocSize(const CallBase *CB, const TargetLibraryInfo *TLI,368 function_ref<const Value *(const Value *)> Mapper) {369 // Note: This handles both explicitly listed allocation functions and370 // allocsize. The code structure could stand to be cleaned up a bit.371 std::optional<AllocFnsTy> FnData = getAllocationSize(CB, TLI);372 if (!FnData)373 return std::nullopt;374 375 // Get the index type for this address space, results and intermediate376 // computations are performed at that width.377 auto &DL = CB->getDataLayout();378 const unsigned IntTyBits = DL.getIndexTypeSizeInBits(CB->getType());379 380 // Handle strdup-like functions separately.381 if (FnData->AllocTy == StrDupLike) {382 APInt Size(IntTyBits, GetStringLength(Mapper(CB->getArgOperand(0))));383 if (!Size)384 return std::nullopt;385 386 // Strndup limits strlen.387 if (FnData->FstParam > 0) {388 const ConstantInt *Arg =389 dyn_cast<ConstantInt>(Mapper(CB->getArgOperand(FnData->FstParam)));390 if (!Arg)391 return std::nullopt;392 393 APInt MaxSize = Arg->getValue().zext(IntTyBits);394 if (Size.ugt(MaxSize))395 Size = MaxSize + 1;396 }397 return Size;398 }399 400 const ConstantInt *Arg =401 dyn_cast<ConstantInt>(Mapper(CB->getArgOperand(FnData->FstParam)));402 if (!Arg)403 return std::nullopt;404 405 APInt Size = Arg->getValue();406 if (!CheckedZextOrTrunc(Size, IntTyBits))407 return std::nullopt;408 409 // Size is determined by just 1 parameter.410 if (FnData->SndParam < 0)411 return Size;412 413 Arg = dyn_cast<ConstantInt>(Mapper(CB->getArgOperand(FnData->SndParam)));414 if (!Arg)415 return std::nullopt;416 417 APInt NumElems = Arg->getValue();418 if (!CheckedZextOrTrunc(NumElems, IntTyBits))419 return std::nullopt;420 421 bool Overflow;422 Size = Size.umul_ov(NumElems, Overflow);423 if (Overflow)424 return std::nullopt;425 return Size;426}427 428Constant *llvm::getInitialValueOfAllocation(const Value *V,429 const TargetLibraryInfo *TLI,430 Type *Ty) {431 if (isa<AllocaInst>(V))432 return UndefValue::get(Ty);433 434 auto *Alloc = dyn_cast<CallBase>(V);435 if (!Alloc)436 return nullptr;437 438 // malloc are uninitialized (undef)439 if (getAllocationData(Alloc, MallocOrOpNewLike, TLI).has_value())440 return UndefValue::get(Ty);441 442 AllocFnKind AK = getAllocFnKind(Alloc);443 if ((AK & AllocFnKind::Uninitialized) != AllocFnKind::Unknown)444 return UndefValue::get(Ty);445 if ((AK & AllocFnKind::Zeroed) != AllocFnKind::Unknown)446 return Constant::getNullValue(Ty);447 448 return nullptr;449}450 451struct FreeFnsTy {452 unsigned NumParams;453 // Name of default allocator function to group malloc/free calls by family454 MallocFamily Family;455};456 457// clang-format off458static const std::pair<LibFunc, FreeFnsTy> FreeFnData[] = {459 {LibFunc_ZdlPv, {1, MallocFamily::CPPNew}}, // operator delete(void*)460 {LibFunc_ZdaPv, {1, MallocFamily::CPPNewArray}}, // operator delete[](void*)461 {LibFunc_msvc_delete_ptr32, {1, MallocFamily::MSVCNew}}, // operator delete(void*)462 {LibFunc_msvc_delete_ptr64, {1, MallocFamily::MSVCNew}}, // operator delete(void*)463 {LibFunc_msvc_delete_array_ptr32, {1, MallocFamily::MSVCArrayNew}}, // operator delete[](void*)464 {LibFunc_msvc_delete_array_ptr64, {1, MallocFamily::MSVCArrayNew}}, // operator delete[](void*)465 {LibFunc_ZdlPvj, {2, MallocFamily::CPPNew}}, // delete(void*, uint)466 {LibFunc_ZdlPvm, {2, MallocFamily::CPPNew}}, // delete(void*, ulong)467 {LibFunc_ZdlPvRKSt9nothrow_t, {2, MallocFamily::CPPNew}}, // delete(void*, nothrow)468 {LibFunc_ZdlPvSt11align_val_t, {2, MallocFamily::CPPNewAligned}}, // delete(void*, align_val_t)469 {LibFunc_ZdaPvj, {2, MallocFamily::CPPNewArray}}, // delete[](void*, uint)470 {LibFunc_ZdaPvm, {2, MallocFamily::CPPNewArray}}, // delete[](void*, ulong)471 {LibFunc_ZdaPvRKSt9nothrow_t, {2, MallocFamily::CPPNewArray}}, // delete[](void*, nothrow)472 {LibFunc_ZdaPvSt11align_val_t, {2, MallocFamily::CPPNewArrayAligned}}, // delete[](void*, align_val_t)473 {LibFunc_msvc_delete_ptr32_int, {2, MallocFamily::MSVCNew}}, // delete(void*, uint)474 {LibFunc_msvc_delete_ptr64_longlong, {2, MallocFamily::MSVCNew}}, // delete(void*, ulonglong)475 {LibFunc_msvc_delete_ptr32_nothrow, {2, MallocFamily::MSVCNew}}, // delete(void*, nothrow)476 {LibFunc_msvc_delete_ptr64_nothrow, {2, MallocFamily::MSVCNew}}, // delete(void*, nothrow)477 {LibFunc_msvc_delete_array_ptr32_int, {2, MallocFamily::MSVCArrayNew}}, // delete[](void*, uint)478 {LibFunc_msvc_delete_array_ptr64_longlong, {2, MallocFamily::MSVCArrayNew}}, // delete[](void*, ulonglong)479 {LibFunc_msvc_delete_array_ptr32_nothrow, {2, MallocFamily::MSVCArrayNew}}, // delete[](void*, nothrow)480 {LibFunc_msvc_delete_array_ptr64_nothrow, {2, MallocFamily::MSVCArrayNew}}, // delete[](void*, nothrow)481 {LibFunc___kmpc_free_shared, {2, MallocFamily::KmpcAllocShared}}, // OpenMP Offloading RTL free482 {LibFunc_ZdlPvSt11align_val_tRKSt9nothrow_t, {3, MallocFamily::CPPNewAligned}}, // delete(void*, align_val_t, nothrow)483 {LibFunc_ZdaPvSt11align_val_tRKSt9nothrow_t, {3, MallocFamily::CPPNewArrayAligned}}, // delete[](void*, align_val_t, nothrow)484 {LibFunc_ZdlPvjSt11align_val_t, {3, MallocFamily::CPPNewAligned}}, // delete(void*, unsigned int, align_val_t)485 {LibFunc_ZdlPvmSt11align_val_t, {3, MallocFamily::CPPNewAligned}}, // delete(void*, unsigned long, align_val_t)486 {LibFunc_ZdaPvjSt11align_val_t, {3, MallocFamily::CPPNewArrayAligned}}, // delete[](void*, unsigned int, align_val_t)487 {LibFunc_ZdaPvmSt11align_val_t, {3, MallocFamily::CPPNewArrayAligned}}, // delete[](void*, unsigned long, align_val_t)488};489// clang-format on490 491std::optional<FreeFnsTy> getFreeFunctionDataForFunction(const Function *Callee,492 const LibFunc TLIFn) {493 const auto *Iter =494 find_if(FreeFnData, [TLIFn](const std::pair<LibFunc, FreeFnsTy> &P) {495 return P.first == TLIFn;496 });497 if (Iter == std::end(FreeFnData))498 return std::nullopt;499 return Iter->second;500}501 502std::optional<StringRef>503llvm::getAllocationFamily(const Value *I, const TargetLibraryInfo *TLI) {504 if (const Function *Callee = getCalledFunction(I)) {505 LibFunc TLIFn;506 if (TLI && TLI->getLibFunc(*Callee, TLIFn) && TLI->has(TLIFn)) {507 // Callee is some known library function.508 const auto AllocData =509 getAllocationDataForFunction(Callee, AnyAlloc, TLI);510 if (AllocData)511 return mangledNameForMallocFamily(AllocData->Family);512 const auto FreeData = getFreeFunctionDataForFunction(Callee, TLIFn);513 if (FreeData)514 return mangledNameForMallocFamily(FreeData->Family);515 }516 }517 518 // Callee isn't a known library function, still check attributes.519 if (checkFnAllocKind(I, AllocFnKind::Free | AllocFnKind::Alloc |520 AllocFnKind::Realloc)) {521 Attribute Attr = cast<CallBase>(I)->getFnAttr("alloc-family");522 if (Attr.isValid())523 return Attr.getValueAsString();524 }525 return std::nullopt;526}527 528/// isLibFreeFunction - Returns true if the function is a builtin free()529bool llvm::isLibFreeFunction(const Function *F, const LibFunc TLIFn) {530 std::optional<FreeFnsTy> FnData = getFreeFunctionDataForFunction(F, TLIFn);531 if (!FnData)532 return checkFnAllocKind(F, AllocFnKind::Free);533 534 // Check free prototype.535 // FIXME: workaround for PR5130, this will be obsolete when a nobuiltin536 // attribute will exist.537 FunctionType *FTy = F->getFunctionType();538 if (!FTy->getReturnType()->isVoidTy())539 return false;540 if (FTy->getNumParams() != FnData->NumParams)541 return false;542 if (!FTy->getParamType(0)->isPointerTy())543 return false;544 545 return true;546}547 548Value *llvm::getFreedOperand(const CallBase *CB, const TargetLibraryInfo *TLI) {549 if (const Function *Callee = getCalledFunction(CB)) {550 LibFunc TLIFn;551 if (TLI && TLI->getLibFunc(*Callee, TLIFn) && TLI->has(TLIFn) &&552 isLibFreeFunction(Callee, TLIFn)) {553 // All currently supported free functions free the first argument.554 return CB->getArgOperand(0);555 }556 }557 558 if (checkFnAllocKind(CB, AllocFnKind::Free))559 return CB->getArgOperandWithAttribute(Attribute::AllocatedPointer);560 561 return nullptr;562}563 564//===----------------------------------------------------------------------===//565// Utility functions to compute size of objects.566//567static APInt getSizeWithOverflow(const SizeOffsetAPInt &Data) {568 APInt Size = Data.Size;569 APInt Offset = Data.Offset;570 571 if (Offset.isNegative() || Size.ult(Offset))572 return APInt::getZero(Size.getBitWidth());573 574 return Size - Offset;575}576 577/// Compute the size of the object pointed by Ptr. Returns true and the578/// object size in Size if successful, and false otherwise.579/// If RoundToAlign is true, then Size is rounded up to the alignment of580/// allocas, byval arguments, and global variables.581bool llvm::getObjectSize(const Value *Ptr, uint64_t &Size, const DataLayout &DL,582 const TargetLibraryInfo *TLI, ObjectSizeOpts Opts) {583 ObjectSizeOffsetVisitor Visitor(DL, TLI, Ptr->getContext(), Opts);584 SizeOffsetAPInt Data = Visitor.compute(const_cast<Value *>(Ptr));585 if (!Data.bothKnown())586 return false;587 588 Size = getSizeWithOverflow(Data).getZExtValue();589 return true;590}591 592std::optional<TypeSize> llvm::getBaseObjectSize(const Value *Ptr,593 const DataLayout &DL,594 const TargetLibraryInfo *TLI,595 ObjectSizeOpts Opts) {596 assert(Opts.EvalMode == ObjectSizeOpts::Mode::ExactSizeFromOffset &&597 "Other modes are currently not supported");598 599 auto Align = [&](TypeSize Size, MaybeAlign Alignment) {600 if (Opts.RoundToAlign && Alignment && !Size.isScalable())601 return TypeSize::getFixed(alignTo(Size.getFixedValue(), *Alignment));602 return Size;603 };604 605 if (isa<UndefValue>(Ptr))606 return TypeSize::getZero();607 608 if (isa<ConstantPointerNull>(Ptr)) {609 if (Opts.NullIsUnknownSize || Ptr->getType()->getPointerAddressSpace())610 return std::nullopt;611 return TypeSize::getZero();612 }613 614 if (auto *GV = dyn_cast<GlobalVariable>(Ptr)) {615 if (!GV->getValueType()->isSized() || GV->hasExternalWeakLinkage() ||616 !GV->hasInitializer() || GV->isInterposable())617 return std::nullopt;618 return Align(DL.getTypeAllocSize(GV->getValueType()), GV->getAlign());619 }620 621 if (auto *A = dyn_cast<Argument>(Ptr)) {622 Type *MemoryTy = A->getPointeeInMemoryValueType();623 if (!MemoryTy || !MemoryTy->isSized())624 return std::nullopt;625 return Align(DL.getTypeAllocSize(MemoryTy), A->getParamAlign());626 }627 628 if (auto *AI = dyn_cast<AllocaInst>(Ptr)) {629 if (std::optional<TypeSize> Size = AI->getAllocationSize(DL))630 return Align(*Size, AI->getAlign());631 return std::nullopt;632 }633 634 if (auto *CB = dyn_cast<CallBase>(Ptr)) {635 if (std::optional<APInt> Size = getAllocSize(CB, TLI)) {636 if (std::optional<uint64_t> ZExtSize = Size->tryZExtValue())637 return TypeSize::getFixed(*ZExtSize);638 }639 return std::nullopt;640 }641 642 return std::nullopt;643}644 645Value *llvm::lowerObjectSizeCall(IntrinsicInst *ObjectSize,646 const DataLayout &DL,647 const TargetLibraryInfo *TLI,648 bool MustSucceed) {649 return lowerObjectSizeCall(ObjectSize, DL, TLI, /*AAResults=*/nullptr,650 MustSucceed);651}652 653Value *llvm::lowerObjectSizeCall(654 IntrinsicInst *ObjectSize, const DataLayout &DL,655 const TargetLibraryInfo *TLI, AAResults *AA, bool MustSucceed,656 SmallVectorImpl<Instruction *> *InsertedInstructions) {657 assert(ObjectSize->getIntrinsicID() == Intrinsic::objectsize &&658 "ObjectSize must be a call to llvm.objectsize!");659 660 bool MaxVal = cast<ConstantInt>(ObjectSize->getArgOperand(1))->isZero();661 ObjectSizeOpts EvalOptions;662 EvalOptions.AA = AA;663 664 // Unless we have to fold this to something, try to be as accurate as665 // possible.666 if (MustSucceed)667 EvalOptions.EvalMode =668 MaxVal ? ObjectSizeOpts::Mode::Max : ObjectSizeOpts::Mode::Min;669 else670 EvalOptions.EvalMode = ObjectSizeOpts::Mode::ExactSizeFromOffset;671 672 EvalOptions.NullIsUnknownSize =673 cast<ConstantInt>(ObjectSize->getArgOperand(2))->isOne();674 675 auto *ResultType = cast<IntegerType>(ObjectSize->getType());676 bool StaticOnly = cast<ConstantInt>(ObjectSize->getArgOperand(3))->isZero();677 if (StaticOnly) {678 // FIXME: Does it make sense to just return a failure value if the size won't679 // fit in the output and `!MustSucceed`?680 uint64_t Size;681 if (getObjectSize(ObjectSize->getArgOperand(0), Size, DL, TLI, EvalOptions) &&682 isUIntN(ResultType->getBitWidth(), Size))683 return ConstantInt::get(ResultType, Size);684 } else {685 LLVMContext &Ctx = ObjectSize->getFunction()->getContext();686 ObjectSizeOffsetEvaluator Eval(DL, TLI, Ctx, EvalOptions);687 SizeOffsetValue SizeOffsetPair = Eval.compute(ObjectSize->getArgOperand(0));688 689 if (SizeOffsetPair != ObjectSizeOffsetEvaluator::unknown()) {690 IRBuilder<TargetFolder, IRBuilderCallbackInserter> Builder(691 Ctx, TargetFolder(DL), IRBuilderCallbackInserter([&](Instruction *I) {692 if (InsertedInstructions)693 InsertedInstructions->push_back(I);694 }));695 Builder.SetInsertPoint(ObjectSize);696 697 Value *Size = SizeOffsetPair.Size;698 Value *Offset = SizeOffsetPair.Offset;699 700 // If we've outside the end of the object, then we can always access701 // exactly 0 bytes.702 Value *ResultSize = Builder.CreateSub(Size, Offset);703 Value *UseZero = Builder.CreateICmpULT(Size, Offset);704 ResultSize = Builder.CreateZExtOrTrunc(ResultSize, ResultType);705 Value *Ret = Builder.CreateSelect(706 UseZero, ConstantInt::get(ResultType, 0), ResultSize);707 708 // The non-constant size expression cannot evaluate to -1.709 if (!isa<Constant>(Size) || !isa<Constant>(Offset))710 Builder.CreateAssumption(711 Builder.CreateICmpNE(Ret, ConstantInt::get(ResultType, -1)));712 713 return Ret;714 }715 }716 717 if (!MustSucceed)718 return nullptr;719 720 return MaxVal ? Constant::getAllOnesValue(ResultType)721 : Constant::getNullValue(ResultType);722}723 724STATISTIC(ObjectVisitorArgument,725 "Number of arguments with unsolved size and offset");726STATISTIC(ObjectVisitorLoad,727 "Number of load instructions with unsolved size and offset");728 729static std::optional<APInt>730combinePossibleConstantValues(std::optional<APInt> LHS,731 std::optional<APInt> RHS,732 ObjectSizeOpts::Mode EvalMode) {733 if (!LHS || !RHS)734 return std::nullopt;735 if (EvalMode == ObjectSizeOpts::Mode::Max)736 return LHS->sge(*RHS) ? *LHS : *RHS;737 else738 return LHS->sle(*RHS) ? *LHS : *RHS;739}740 741static std::optional<APInt> aggregatePossibleConstantValuesImpl(742 const Value *V, ObjectSizeOpts::Mode EvalMode, unsigned recursionDepth) {743 constexpr unsigned maxRecursionDepth = 4;744 if (recursionDepth == maxRecursionDepth)745 return std::nullopt;746 747 if (const auto *CI = dyn_cast<ConstantInt>(V)) {748 return CI->getValue();749 } else if (const auto *SI = dyn_cast<SelectInst>(V)) {750 return combinePossibleConstantValues(751 aggregatePossibleConstantValuesImpl(SI->getTrueValue(), EvalMode,752 recursionDepth + 1),753 aggregatePossibleConstantValuesImpl(SI->getFalseValue(), EvalMode,754 recursionDepth + 1),755 EvalMode);756 } else if (const auto *PN = dyn_cast<PHINode>(V)) {757 unsigned Count = PN->getNumIncomingValues();758 if (Count == 0)759 return std::nullopt;760 auto Acc = aggregatePossibleConstantValuesImpl(761 PN->getIncomingValue(0), EvalMode, recursionDepth + 1);762 for (unsigned I = 1; Acc && I < Count; ++I) {763 auto Tmp = aggregatePossibleConstantValuesImpl(764 PN->getIncomingValue(I), EvalMode, recursionDepth + 1);765 Acc = combinePossibleConstantValues(Acc, Tmp, EvalMode);766 }767 return Acc;768 }769 770 return std::nullopt;771}772 773static std::optional<APInt>774aggregatePossibleConstantValues(const Value *V, ObjectSizeOpts::Mode EvalMode) {775 if (auto *CI = dyn_cast<ConstantInt>(V))776 return CI->getValue();777 778 if (EvalMode != ObjectSizeOpts::Mode::Min &&779 EvalMode != ObjectSizeOpts::Mode::Max)780 return std::nullopt;781 782 // Not using computeConstantRange here because we cannot guarantee it's not783 // doing optimization based on UB which we want to avoid when expanding784 // __builtin_object_size.785 return aggregatePossibleConstantValuesImpl(V, EvalMode, 0u);786}787 788/// Align \p Size according to \p Alignment. If \p Size is greater than789/// getSignedMaxValue(), set it as unknown as we can only represent signed value790/// in OffsetSpan.791APInt ObjectSizeOffsetVisitor::align(APInt Size, MaybeAlign Alignment) {792 if (Options.RoundToAlign && Alignment)793 Size = APInt(IntTyBits, alignTo(Size.getZExtValue(), *Alignment));794 795 return Size.isNegative() ? APInt() : Size;796}797 798ObjectSizeOffsetVisitor::ObjectSizeOffsetVisitor(const DataLayout &DL,799 const TargetLibraryInfo *TLI,800 LLVMContext &Context,801 ObjectSizeOpts Options)802 : DL(DL), TLI(TLI), Options(Options) {803 // Pointer size must be rechecked for each object visited since it could have804 // a different address space.805}806 807SizeOffsetAPInt ObjectSizeOffsetVisitor::compute(Value *V) {808 InstructionsVisited = 0;809 OffsetSpan Span = computeImpl(V);810 811 // In ExactSizeFromOffset mode, we don't care about the Before Field, so allow812 // us to overwrite it if needs be.813 if (Span.knownAfter() && !Span.knownBefore() &&814 Options.EvalMode == ObjectSizeOpts::Mode::ExactSizeFromOffset)815 Span.Before = APInt::getZero(Span.After.getBitWidth());816 817 if (!Span.bothKnown())818 return {};819 820 return {Span.Before + Span.After, Span.Before};821}822 823OffsetSpan ObjectSizeOffsetVisitor::computeImpl(Value *V) {824 unsigned InitialIntTyBits = DL.getIndexTypeSizeInBits(V->getType());825 826 // Stripping pointer casts can strip address space casts which can change the827 // index type size. The invariant is that we use the value type to determine828 // the index type size and if we stripped address space casts we have to829 // readjust the APInt as we pass it upwards in order for the APInt to match830 // the type the caller passed in.831 APInt Offset(InitialIntTyBits, 0);832 V = V->stripAndAccumulateConstantOffsets(833 DL, Offset, /* AllowNonInbounds */ true, /* AllowInvariantGroup */ true);834 835 // Give it another try with approximated analysis. We don't start with this836 // one because stripAndAccumulateConstantOffsets behaves differently wrt.837 // overflows if we provide an external Analysis.838 if ((Options.EvalMode == ObjectSizeOpts::Mode::Min ||839 Options.EvalMode == ObjectSizeOpts::Mode::Max) &&840 isa<GEPOperator>(V)) {841 // External Analysis used to compute the Min/Max value of individual Offsets842 // within a GEP.843 ObjectSizeOpts::Mode EvalMode =844 Options.EvalMode == ObjectSizeOpts::Mode::Min845 ? ObjectSizeOpts::Mode::Max846 : ObjectSizeOpts::Mode::Min;847 auto OffsetRangeAnalysis = [EvalMode](Value &VOffset, APInt &Offset) {848 if (auto PossibleOffset =849 aggregatePossibleConstantValues(&VOffset, EvalMode)) {850 Offset = *PossibleOffset;851 return true;852 }853 return false;854 };855 856 V = V->stripAndAccumulateConstantOffsets(857 DL, Offset, /* AllowNonInbounds */ true, /* AllowInvariantGroup */ true,858 /*ExternalAnalysis=*/OffsetRangeAnalysis);859 }860 861 // Later we use the index type size and zero but it will match the type of the862 // value that is passed to computeImpl.863 IntTyBits = DL.getIndexTypeSizeInBits(V->getType());864 Zero = APInt::getZero(IntTyBits);865 OffsetSpan ORT = computeValue(V);866 867 bool IndexTypeSizeChanged = InitialIntTyBits != IntTyBits;868 if (!IndexTypeSizeChanged && Offset.isZero())869 return ORT;870 871 // We stripped an address space cast that changed the index type size or we872 // accumulated some constant offset (or both). Readjust the bit width to match873 // the argument index type size and apply the offset, as required.874 if (IndexTypeSizeChanged) {875 if (ORT.knownBefore() &&876 !::CheckedZextOrTrunc(ORT.Before, InitialIntTyBits))877 ORT.Before = APInt();878 if (ORT.knownAfter() && !::CheckedZextOrTrunc(ORT.After, InitialIntTyBits))879 ORT.After = APInt();880 }881 // If the computed bound is "unknown" we cannot add the stripped offset.882 if (ORT.knownBefore()) {883 bool Overflow;884 ORT.Before = ORT.Before.sadd_ov(Offset, Overflow);885 if (Overflow)886 ORT.Before = APInt();887 }888 if (ORT.knownAfter()) {889 bool Overflow;890 ORT.After = ORT.After.ssub_ov(Offset, Overflow);891 if (Overflow)892 ORT.After = APInt();893 }894 895 // We end up pointing on a location that's outside of the original object.896 if (ORT.knownBefore() && ORT.Before.isNegative()) {897 // This means that we *may* be accessing memory before the allocation.898 // Conservatively return an unknown size.899 //900 // TODO: working with ranges instead of value would make it possible to take901 // a better decision.902 if (Options.EvalMode == ObjectSizeOpts::Mode::Min ||903 Options.EvalMode == ObjectSizeOpts::Mode::Max) {904 return ObjectSizeOffsetVisitor::unknown();905 }906 // Otherwise it's fine, caller can handle negative offset.907 }908 return ORT;909}910 911OffsetSpan ObjectSizeOffsetVisitor::computeValue(Value *V) {912 if (Instruction *I = dyn_cast<Instruction>(V)) {913 // If we have already seen this instruction, bail out. Cycles can happen in914 // unreachable code after constant propagation.915 auto P = SeenInsts.try_emplace(I, ObjectSizeOffsetVisitor::unknown());916 if (!P.second)917 return P.first->second;918 ++InstructionsVisited;919 if (InstructionsVisited > ObjectSizeOffsetVisitorMaxVisitInstructions)920 return ObjectSizeOffsetVisitor::unknown();921 OffsetSpan Res = visit(*I);922 // Cache the result for later visits. If we happened to visit this during923 // the above recursion, we would consider it unknown until now.924 SeenInsts[I] = Res;925 return Res;926 }927 if (Argument *A = dyn_cast<Argument>(V))928 return visitArgument(*A);929 if (ConstantPointerNull *P = dyn_cast<ConstantPointerNull>(V))930 return visitConstantPointerNull(*P);931 if (GlobalAlias *GA = dyn_cast<GlobalAlias>(V))932 return visitGlobalAlias(*GA);933 if (GlobalVariable *GV = dyn_cast<GlobalVariable>(V))934 return visitGlobalVariable(*GV);935 if (UndefValue *UV = dyn_cast<UndefValue>(V))936 return visitUndefValue(*UV);937 938 LLVM_DEBUG(dbgs() << "ObjectSizeOffsetVisitor::compute() unhandled value: "939 << *V << '\n');940 return ObjectSizeOffsetVisitor::unknown();941}942 943bool ObjectSizeOffsetVisitor::CheckedZextOrTrunc(APInt &I) {944 return ::CheckedZextOrTrunc(I, IntTyBits);945}946 947OffsetSpan ObjectSizeOffsetVisitor::visitAllocaInst(AllocaInst &I) {948 TypeSize ElemSize = DL.getTypeAllocSize(I.getAllocatedType());949 if (ElemSize.isScalable() && Options.EvalMode != ObjectSizeOpts::Mode::Min)950 return ObjectSizeOffsetVisitor::unknown();951 if (!isUIntN(IntTyBits, ElemSize.getKnownMinValue()))952 return ObjectSizeOffsetVisitor::unknown();953 APInt Size(IntTyBits, ElemSize.getKnownMinValue());954 955 if (!I.isArrayAllocation())956 return OffsetSpan(Zero, align(Size, I.getAlign()));957 958 Value *ArraySize = I.getArraySize();959 if (auto PossibleSize =960 aggregatePossibleConstantValues(ArraySize, Options.EvalMode)) {961 APInt NumElems = *PossibleSize;962 if (!CheckedZextOrTrunc(NumElems))963 return ObjectSizeOffsetVisitor::unknown();964 965 bool Overflow;966 Size = Size.umul_ov(NumElems, Overflow);967 968 return Overflow ? ObjectSizeOffsetVisitor::unknown()969 : OffsetSpan(Zero, align(Size, I.getAlign()));970 }971 return ObjectSizeOffsetVisitor::unknown();972}973 974OffsetSpan ObjectSizeOffsetVisitor::visitArgument(Argument &A) {975 Type *MemoryTy = A.getPointeeInMemoryValueType();976 // No interprocedural analysis is done at the moment.977 if (!MemoryTy|| !MemoryTy->isSized()) {978 ++ObjectVisitorArgument;979 return ObjectSizeOffsetVisitor::unknown();980 }981 982 APInt Size(IntTyBits, DL.getTypeAllocSize(MemoryTy));983 return OffsetSpan(Zero, align(Size, A.getParamAlign()));984}985 986OffsetSpan ObjectSizeOffsetVisitor::visitCallBase(CallBase &CB) {987 auto Mapper = [this](const Value *V) -> const Value * {988 if (!V->getType()->isIntegerTy())989 return V;990 991 if (auto PossibleBound =992 aggregatePossibleConstantValues(V, Options.EvalMode))993 return ConstantInt::get(V->getType(), *PossibleBound);994 995 return V;996 };997 998 if (std::optional<APInt> Size = getAllocSize(&CB, TLI, Mapper)) {999 // Very large unsigned value cannot be represented as OffsetSpan.1000 if (Size->isNegative())1001 return ObjectSizeOffsetVisitor::unknown();1002 return OffsetSpan(Zero, *Size);1003 }1004 return ObjectSizeOffsetVisitor::unknown();1005}1006 1007OffsetSpan1008ObjectSizeOffsetVisitor::visitConstantPointerNull(ConstantPointerNull &CPN) {1009 // If null is unknown, there's nothing we can do. Additionally, non-zero1010 // address spaces can make use of null, so we don't presume to know anything1011 // about that.1012 //1013 // TODO: How should this work with address space casts? We currently just drop1014 // them on the floor, but it's unclear what we should do when a NULL from1015 // addrspace(1) gets casted to addrspace(0) (or vice-versa).1016 if (Options.NullIsUnknownSize || CPN.getType()->getAddressSpace())1017 return ObjectSizeOffsetVisitor::unknown();1018 return OffsetSpan(Zero, Zero);1019}1020 1021OffsetSpan1022ObjectSizeOffsetVisitor::visitExtractElementInst(ExtractElementInst &) {1023 return ObjectSizeOffsetVisitor::unknown();1024}1025 1026OffsetSpan ObjectSizeOffsetVisitor::visitExtractValueInst(ExtractValueInst &) {1027 // Easy cases were already folded by previous passes.1028 return ObjectSizeOffsetVisitor::unknown();1029}1030 1031OffsetSpan ObjectSizeOffsetVisitor::visitGlobalAlias(GlobalAlias &GA) {1032 if (GA.isInterposable())1033 return ObjectSizeOffsetVisitor::unknown();1034 return computeImpl(GA.getAliasee());1035}1036 1037OffsetSpan ObjectSizeOffsetVisitor::visitGlobalVariable(GlobalVariable &GV) {1038 if (!GV.getValueType()->isSized() || GV.hasExternalWeakLinkage() ||1039 ((!GV.hasInitializer() || GV.isInterposable()) &&1040 Options.EvalMode != ObjectSizeOpts::Mode::Min))1041 return ObjectSizeOffsetVisitor::unknown();1042 1043 APInt Size(IntTyBits, DL.getTypeAllocSize(GV.getValueType()));1044 return OffsetSpan(Zero, align(Size, GV.getAlign()));1045}1046 1047OffsetSpan ObjectSizeOffsetVisitor::visitIntToPtrInst(IntToPtrInst &) {1048 // clueless1049 return ObjectSizeOffsetVisitor::unknown();1050}1051 1052OffsetSpan ObjectSizeOffsetVisitor::findLoadOffsetRange(1053 LoadInst &Load, BasicBlock &BB, BasicBlock::iterator From,1054 SmallDenseMap<BasicBlock *, OffsetSpan, 8> &VisitedBlocks,1055 unsigned &ScannedInstCount) {1056 constexpr unsigned MaxInstsToScan = 128;1057 1058 auto Where = VisitedBlocks.find(&BB);1059 if (Where != VisitedBlocks.end())1060 return Where->second;1061 1062 auto Unknown = [&BB, &VisitedBlocks]() {1063 return VisitedBlocks[&BB] = ObjectSizeOffsetVisitor::unknown();1064 };1065 auto Known = [&BB, &VisitedBlocks](OffsetSpan SO) {1066 return VisitedBlocks[&BB] = SO;1067 };1068 1069 do {1070 Instruction &I = *From;1071 1072 if (I.isDebugOrPseudoInst())1073 continue;1074 1075 if (++ScannedInstCount > MaxInstsToScan)1076 return Unknown();1077 1078 if (!I.mayWriteToMemory())1079 continue;1080 1081 if (auto *SI = dyn_cast<StoreInst>(&I)) {1082 AliasResult AR =1083 Options.AA->alias(SI->getPointerOperand(), Load.getPointerOperand());1084 switch ((AliasResult::Kind)AR) {1085 case AliasResult::NoAlias:1086 continue;1087 case AliasResult::MustAlias:1088 if (SI->getValueOperand()->getType()->isPointerTy())1089 return Known(computeImpl(SI->getValueOperand()));1090 else1091 return Unknown(); // No handling of non-pointer values by `compute`.1092 default:1093 return Unknown();1094 }1095 }1096 1097 if (auto *CB = dyn_cast<CallBase>(&I)) {1098 Function *Callee = CB->getCalledFunction();1099 // Bail out on indirect call.1100 if (!Callee)1101 return Unknown();1102 1103 LibFunc TLIFn;1104 if (!TLI || !TLI->getLibFunc(*CB->getCalledFunction(), TLIFn) ||1105 !TLI->has(TLIFn))1106 return Unknown();1107 1108 // TODO: There's probably more interesting case to support here.1109 if (TLIFn != LibFunc_posix_memalign)1110 return Unknown();1111 1112 AliasResult AR =1113 Options.AA->alias(CB->getOperand(0), Load.getPointerOperand());1114 switch ((AliasResult::Kind)AR) {1115 case AliasResult::NoAlias:1116 continue;1117 case AliasResult::MustAlias:1118 break;1119 default:1120 return Unknown();1121 }1122 1123 // Is the error status of posix_memalign correctly checked? If not it1124 // would be incorrect to assume it succeeds and load doesn't see the1125 // previous value.1126 std::optional<bool> Checked = isImpliedByDomCondition(1127 ICmpInst::ICMP_EQ, CB, ConstantInt::get(CB->getType(), 0), &Load, DL);1128 if (!Checked || !*Checked)1129 return Unknown();1130 1131 Value *Size = CB->getOperand(2);1132 auto *C = dyn_cast<ConstantInt>(Size);1133 if (!C)1134 return Unknown();1135 1136 APInt CSize = C->getValue();1137 if (CSize.isNegative())1138 return Unknown();1139 1140 return Known({APInt(CSize.getBitWidth(), 0), CSize});1141 }1142 1143 return Unknown();1144 } while (From-- != BB.begin());1145 1146 SmallVector<OffsetSpan> PredecessorSizeOffsets;1147 for (auto *PredBB : predecessors(&BB)) {1148 PredecessorSizeOffsets.push_back(findLoadOffsetRange(1149 Load, *PredBB, BasicBlock::iterator(PredBB->getTerminator()),1150 VisitedBlocks, ScannedInstCount));1151 if (!PredecessorSizeOffsets.back().bothKnown())1152 return Unknown();1153 }1154 1155 if (PredecessorSizeOffsets.empty())1156 return Unknown();1157 1158 return Known(std::accumulate(1159 PredecessorSizeOffsets.begin() + 1, PredecessorSizeOffsets.end(),1160 PredecessorSizeOffsets.front(), [this](OffsetSpan LHS, OffsetSpan RHS) {1161 return combineOffsetRange(LHS, RHS);1162 }));1163}1164 1165OffsetSpan ObjectSizeOffsetVisitor::visitLoadInst(LoadInst &LI) {1166 if (!Options.AA) {1167 ++ObjectVisitorLoad;1168 return ObjectSizeOffsetVisitor::unknown();1169 }1170 1171 SmallDenseMap<BasicBlock *, OffsetSpan, 8> VisitedBlocks;1172 unsigned ScannedInstCount = 0;1173 OffsetSpan SO =1174 findLoadOffsetRange(LI, *LI.getParent(), BasicBlock::iterator(LI),1175 VisitedBlocks, ScannedInstCount);1176 if (!SO.bothKnown())1177 ++ObjectVisitorLoad;1178 return SO;1179}1180 1181OffsetSpan ObjectSizeOffsetVisitor::combineOffsetRange(OffsetSpan LHS,1182 OffsetSpan RHS) {1183 if (!LHS.bothKnown() || !RHS.bothKnown())1184 return ObjectSizeOffsetVisitor::unknown();1185 1186 switch (Options.EvalMode) {1187 case ObjectSizeOpts::Mode::Min:1188 return {LHS.Before.slt(RHS.Before) ? LHS.Before : RHS.Before,1189 LHS.After.slt(RHS.After) ? LHS.After : RHS.After};1190 case ObjectSizeOpts::Mode::Max: {1191 return {LHS.Before.sgt(RHS.Before) ? LHS.Before : RHS.Before,1192 LHS.After.sgt(RHS.After) ? LHS.After : RHS.After};1193 }1194 case ObjectSizeOpts::Mode::ExactSizeFromOffset:1195 return {LHS.Before.eq(RHS.Before) ? LHS.Before : APInt(),1196 LHS.After.eq(RHS.After) ? LHS.After : APInt()};1197 case ObjectSizeOpts::Mode::ExactUnderlyingSizeAndOffset:1198 return (LHS == RHS) ? LHS : ObjectSizeOffsetVisitor::unknown();1199 }1200 llvm_unreachable("missing an eval mode");1201}1202 1203OffsetSpan ObjectSizeOffsetVisitor::visitPHINode(PHINode &PN) {1204 if (PN.getNumIncomingValues() == 0)1205 return ObjectSizeOffsetVisitor::unknown();1206 auto IncomingValues = PN.incoming_values();1207 return std::accumulate(IncomingValues.begin() + 1, IncomingValues.end(),1208 computeImpl(*IncomingValues.begin()),1209 [this](OffsetSpan LHS, Value *VRHS) {1210 return combineOffsetRange(LHS, computeImpl(VRHS));1211 });1212}1213 1214OffsetSpan ObjectSizeOffsetVisitor::visitSelectInst(SelectInst &I) {1215 return combineOffsetRange(computeImpl(I.getTrueValue()),1216 computeImpl(I.getFalseValue()));1217}1218 1219OffsetSpan ObjectSizeOffsetVisitor::visitUndefValue(UndefValue &) {1220 return OffsetSpan(Zero, Zero);1221}1222 1223OffsetSpan ObjectSizeOffsetVisitor::visitInstruction(Instruction &I) {1224 LLVM_DEBUG(dbgs() << "ObjectSizeOffsetVisitor unknown instruction:" << I1225 << '\n');1226 return ObjectSizeOffsetVisitor::unknown();1227}1228 1229// Just set these right here...1230SizeOffsetValue::SizeOffsetValue(const SizeOffsetWeakTrackingVH &SOT)1231 : SizeOffsetType(SOT.Size, SOT.Offset) {}1232 1233ObjectSizeOffsetEvaluator::ObjectSizeOffsetEvaluator(1234 const DataLayout &DL, const TargetLibraryInfo *TLI, LLVMContext &Context,1235 ObjectSizeOpts EvalOpts)1236 : DL(DL), TLI(TLI), Context(Context),1237 Builder(Context, TargetFolder(DL),1238 IRBuilderCallbackInserter(1239 [&](Instruction *I) { InsertedInstructions.insert(I); })),1240 EvalOpts(EvalOpts) {1241 // IntTy and Zero must be set for each compute() since the address space may1242 // be different for later objects.1243}1244 1245SizeOffsetValue ObjectSizeOffsetEvaluator::compute(Value *V) {1246 // XXX - Are vectors of pointers possible here?1247 IntTy = cast<IntegerType>(DL.getIndexType(V->getType()));1248 Zero = ConstantInt::get(IntTy, 0);1249 1250 SizeOffsetValue Result = compute_(V);1251 1252 if (!Result.bothKnown()) {1253 // Erase everything that was computed in this iteration from the cache, so1254 // that no dangling references are left behind. We could be a bit smarter if1255 // we kept a dependency graph. It's probably not worth the complexity.1256 for (const Value *SeenVal : SeenVals) {1257 CacheMapTy::iterator CacheIt = CacheMap.find(SeenVal);1258 // non-computable results can be safely cached1259 if (CacheIt != CacheMap.end() && CacheIt->second.anyKnown())1260 CacheMap.erase(CacheIt);1261 }1262 1263 // Erase any instructions we inserted as part of the traversal.1264 for (Instruction *I : InsertedInstructions) {1265 I->replaceAllUsesWith(PoisonValue::get(I->getType()));1266 I->eraseFromParent();1267 }1268 }1269 1270 SeenVals.clear();1271 InsertedInstructions.clear();1272 return Result;1273}1274 1275SizeOffsetValue ObjectSizeOffsetEvaluator::compute_(Value *V) {1276 1277 // Only trust ObjectSizeOffsetVisitor in exact mode, otherwise fallback on1278 // dynamic computation.1279 ObjectSizeOpts VisitorEvalOpts(EvalOpts);1280 VisitorEvalOpts.EvalMode = ObjectSizeOpts::Mode::ExactUnderlyingSizeAndOffset;1281 ObjectSizeOffsetVisitor Visitor(DL, TLI, Context, VisitorEvalOpts);1282 1283 SizeOffsetAPInt Const = Visitor.compute(V);1284 if (Const.bothKnown())1285 return SizeOffsetValue(ConstantInt::get(Context, Const.Size),1286 ConstantInt::get(Context, Const.Offset));1287 1288 V = V->stripPointerCasts();1289 1290 // Check cache.1291 CacheMapTy::iterator CacheIt = CacheMap.find(V);1292 if (CacheIt != CacheMap.end())1293 return CacheIt->second;1294 1295 // Always generate code immediately before the instruction being1296 // processed, so that the generated code dominates the same BBs.1297 BuilderTy::InsertPointGuard Guard(Builder);1298 if (Instruction *I = dyn_cast<Instruction>(V))1299 Builder.SetInsertPoint(I);1300 1301 // Now compute the size and offset.1302 SizeOffsetValue Result;1303 1304 // Record the pointers that were handled in this run, so that they can be1305 // cleaned later if something fails. We also use this set to break cycles that1306 // can occur in dead code.1307 if (!SeenVals.insert(V).second) {1308 Result = ObjectSizeOffsetEvaluator::unknown();1309 } else if (GEPOperator *GEP = dyn_cast<GEPOperator>(V)) {1310 Result = visitGEPOperator(*GEP);1311 } else if (Instruction *I = dyn_cast<Instruction>(V)) {1312 Result = visit(*I);1313 } else if (isa<Argument>(V) ||1314 (isa<ConstantExpr>(V) &&1315 cast<ConstantExpr>(V)->getOpcode() == Instruction::IntToPtr) ||1316 isa<GlobalAlias>(V) ||1317 isa<GlobalVariable>(V)) {1318 // Ignore values where we cannot do more than ObjectSizeVisitor.1319 Result = ObjectSizeOffsetEvaluator::unknown();1320 } else {1321 LLVM_DEBUG(1322 dbgs() << "ObjectSizeOffsetEvaluator::compute() unhandled value: " << *V1323 << '\n');1324 Result = ObjectSizeOffsetEvaluator::unknown();1325 }1326 1327 // Don't reuse CacheIt since it may be invalid at this point.1328 CacheMap[V] = SizeOffsetWeakTrackingVH(Result);1329 return Result;1330}1331 1332SizeOffsetValue ObjectSizeOffsetEvaluator::visitAllocaInst(AllocaInst &I) {1333 if (!I.getAllocatedType()->isSized())1334 return ObjectSizeOffsetEvaluator::unknown();1335 1336 // must be a VLA or vscale.1337 assert(I.isArrayAllocation() || I.getAllocatedType()->isScalableTy());1338 1339 // If needed, adjust the alloca's operand size to match the pointer indexing1340 // size. Subsequent math operations expect the types to match.1341 Value *ArraySize = Builder.CreateZExtOrTrunc(1342 I.getArraySize(),1343 DL.getIndexType(I.getContext(), DL.getAllocaAddrSpace()));1344 assert(ArraySize->getType() == Zero->getType() &&1345 "Expected zero constant to have pointer index type");1346 1347 Value *Size = Builder.CreateTypeSize(1348 ArraySize->getType(), DL.getTypeAllocSize(I.getAllocatedType()));1349 Size = Builder.CreateMul(Size, ArraySize);1350 return SizeOffsetValue(Size, Zero);1351}1352 1353SizeOffsetValue ObjectSizeOffsetEvaluator::visitCallBase(CallBase &CB) {1354 std::optional<AllocFnsTy> FnData = getAllocationSize(&CB, TLI);1355 if (!FnData)1356 return ObjectSizeOffsetEvaluator::unknown();1357 1358 // Handle strdup-like functions separately.1359 if (FnData->AllocTy == StrDupLike) {1360 // TODO: implement evaluation of strdup/strndup1361 return ObjectSizeOffsetEvaluator::unknown();1362 }1363 1364 Value *FirstArg = CB.getArgOperand(FnData->FstParam);1365 FirstArg = Builder.CreateZExtOrTrunc(FirstArg, IntTy);1366 if (FnData->SndParam < 0)1367 return SizeOffsetValue(FirstArg, Zero);1368 1369 Value *SecondArg = CB.getArgOperand(FnData->SndParam);1370 SecondArg = Builder.CreateZExtOrTrunc(SecondArg, IntTy);1371 Value *Size = Builder.CreateMul(FirstArg, SecondArg);1372 return SizeOffsetValue(Size, Zero);1373}1374 1375SizeOffsetValue1376ObjectSizeOffsetEvaluator::visitExtractElementInst(ExtractElementInst &) {1377 return ObjectSizeOffsetEvaluator::unknown();1378}1379 1380SizeOffsetValue1381ObjectSizeOffsetEvaluator::visitExtractValueInst(ExtractValueInst &) {1382 return ObjectSizeOffsetEvaluator::unknown();1383}1384 1385SizeOffsetValue ObjectSizeOffsetEvaluator::visitGEPOperator(GEPOperator &GEP) {1386 SizeOffsetValue PtrData = compute_(GEP.getPointerOperand());1387 if (!PtrData.bothKnown())1388 return ObjectSizeOffsetEvaluator::unknown();1389 1390 Value *Offset = emitGEPOffset(&Builder, DL, &GEP, /*NoAssumptions=*/true);1391 Offset = Builder.CreateAdd(PtrData.Offset, Offset);1392 return SizeOffsetValue(PtrData.Size, Offset);1393}1394 1395SizeOffsetValue ObjectSizeOffsetEvaluator::visitIntToPtrInst(IntToPtrInst &) {1396 // clueless1397 return ObjectSizeOffsetEvaluator::unknown();1398}1399 1400SizeOffsetValue ObjectSizeOffsetEvaluator::visitLoadInst(LoadInst &LI) {1401 return ObjectSizeOffsetEvaluator::unknown();1402}1403 1404SizeOffsetValue ObjectSizeOffsetEvaluator::visitPHINode(PHINode &PHI) {1405 // Create 2 PHIs: one for size and another for offset.1406 PHINode *SizePHI = Builder.CreatePHI(IntTy, PHI.getNumIncomingValues());1407 PHINode *OffsetPHI = Builder.CreatePHI(IntTy, PHI.getNumIncomingValues());1408 1409 // Insert right away in the cache to handle recursive PHIs.1410 CacheMap[&PHI] = SizeOffsetWeakTrackingVH(SizePHI, OffsetPHI);1411 1412 // Compute offset/size for each PHI incoming pointer.1413 for (unsigned i = 0, e = PHI.getNumIncomingValues(); i != e; ++i) {1414 BasicBlock *IncomingBlock = PHI.getIncomingBlock(i);1415 Builder.SetInsertPoint(IncomingBlock, IncomingBlock->getFirstInsertionPt());1416 SizeOffsetValue EdgeData = compute_(PHI.getIncomingValue(i));1417 1418 if (!EdgeData.bothKnown()) {1419 OffsetPHI->replaceAllUsesWith(PoisonValue::get(IntTy));1420 OffsetPHI->eraseFromParent();1421 InsertedInstructions.erase(OffsetPHI);1422 SizePHI->replaceAllUsesWith(PoisonValue::get(IntTy));1423 SizePHI->eraseFromParent();1424 InsertedInstructions.erase(SizePHI);1425 return ObjectSizeOffsetEvaluator::unknown();1426 }1427 SizePHI->addIncoming(EdgeData.Size, IncomingBlock);1428 OffsetPHI->addIncoming(EdgeData.Offset, IncomingBlock);1429 }1430 1431 Value *Size = SizePHI, *Offset = OffsetPHI;1432 if (Value *Tmp = SizePHI->hasConstantValue()) {1433 Size = Tmp;1434 SizePHI->replaceAllUsesWith(Size);1435 SizePHI->eraseFromParent();1436 InsertedInstructions.erase(SizePHI);1437 }1438 if (Value *Tmp = OffsetPHI->hasConstantValue()) {1439 Offset = Tmp;1440 OffsetPHI->replaceAllUsesWith(Offset);1441 OffsetPHI->eraseFromParent();1442 InsertedInstructions.erase(OffsetPHI);1443 }1444 return SizeOffsetValue(Size, Offset);1445}1446 1447SizeOffsetValue ObjectSizeOffsetEvaluator::visitSelectInst(SelectInst &I) {1448 SizeOffsetValue TrueSide = compute_(I.getTrueValue());1449 SizeOffsetValue FalseSide = compute_(I.getFalseValue());1450 1451 if (!TrueSide.bothKnown() || !FalseSide.bothKnown())1452 return ObjectSizeOffsetEvaluator::unknown();1453 if (TrueSide == FalseSide)1454 return TrueSide;1455 1456 Value *Size =1457 Builder.CreateSelect(I.getCondition(), TrueSide.Size, FalseSide.Size);1458 Value *Offset =1459 Builder.CreateSelect(I.getCondition(), TrueSide.Offset, FalseSide.Offset);1460 return SizeOffsetValue(Size, Offset);1461}1462 1463SizeOffsetValue ObjectSizeOffsetEvaluator::visitInstruction(Instruction &I) {1464 LLVM_DEBUG(dbgs() << "ObjectSizeOffsetEvaluator unknown instruction:" << I1465 << '\n');1466 return ObjectSizeOffsetEvaluator::unknown();1467}1468