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