diff options
Diffstat (limited to 'llvm/lib/Analysis/MemoryBuiltins.cpp')
| -rw-r--r-- | llvm/lib/Analysis/MemoryBuiltins.cpp | 524 |
1 files changed, 374 insertions, 150 deletions
diff --git a/llvm/lib/Analysis/MemoryBuiltins.cpp b/llvm/lib/Analysis/MemoryBuiltins.cpp index 208f93aa1ac6..91501b04448e 100644 --- a/llvm/lib/Analysis/MemoryBuiltins.cpp +++ b/llvm/lib/Analysis/MemoryBuiltins.cpp @@ -17,7 +17,7 @@ #include "llvm/ADT/Optional.h" #include "llvm/ADT/STLExtras.h" #include "llvm/ADT/Statistic.h" -#include "llvm/ADT/StringRef.h" +#include "llvm/Analysis/AliasAnalysis.h" #include "llvm/Analysis/TargetFolder.h" #include "llvm/Analysis/TargetLibraryInfo.h" #include "llvm/Analysis/Utils/Local.h" @@ -43,6 +43,8 @@ #include <cassert> #include <cstdint> #include <iterator> +#include <numeric> +#include <type_traits> #include <utility> using namespace llvm; @@ -62,6 +64,42 @@ enum AllocType : uint8_t { AnyAlloc = AllocLike | ReallocLike }; +enum class MallocFamily { + Malloc, + CPPNew, // new(unsigned int) + CPPNewAligned, // new(unsigned int, align_val_t) + CPPNewArray, // new[](unsigned int) + CPPNewArrayAligned, // new[](unsigned long, align_val_t) + MSVCNew, // new(unsigned int) + MSVCArrayNew, // new[](unsigned int) + VecMalloc, + KmpcAllocShared, +}; + +StringRef mangledNameForMallocFamily(const MallocFamily &Family) { + switch (Family) { + case MallocFamily::Malloc: + return "malloc"; + case MallocFamily::CPPNew: + return "_Znwm"; + case MallocFamily::CPPNewAligned: + return "_ZnwmSt11align_val_t"; + case MallocFamily::CPPNewArray: + return "_Znam"; + case MallocFamily::CPPNewArrayAligned: + return "_ZnamSt11align_val_t"; + case MallocFamily::MSVCNew: + return "??2@YAPAXI@Z"; + case MallocFamily::MSVCArrayNew: + return "??_U@YAPAXI@Z"; + case MallocFamily::VecMalloc: + return "vec_malloc"; + case MallocFamily::KmpcAllocShared: + return "__kmpc_alloc_shared"; + } + llvm_unreachable("missing an alloc family"); +} + struct AllocFnsTy { AllocType AllocTy; unsigned NumParams; @@ -69,50 +107,55 @@ struct AllocFnsTy { int FstParam, SndParam; // Alignment parameter for aligned_alloc and aligned new int AlignParam; + // Name of default allocator function to group malloc/free calls by family + MallocFamily Family; }; +// clang-format off // FIXME: certain users need more information. E.g., SimplifyLibCalls needs to // know which functions are nounwind, noalias, nocapture parameters, etc. static const std::pair<LibFunc, AllocFnsTy> AllocationFnData[] = { - {LibFunc_malloc, {MallocLike, 1, 0, -1, -1}}, - {LibFunc_vec_malloc, {MallocLike, 1, 0, -1, -1}}, - {LibFunc_valloc, {MallocLike, 1, 0, -1, -1}}, - {LibFunc_Znwj, {OpNewLike, 1, 0, -1, -1}}, // new(unsigned int) - {LibFunc_ZnwjRKSt9nothrow_t, {MallocLike, 2, 0, -1, -1}}, // new(unsigned int, nothrow) - {LibFunc_ZnwjSt11align_val_t, {OpNewLike, 2, 0, -1, 1}}, // new(unsigned int, align_val_t) - {LibFunc_ZnwjSt11align_val_tRKSt9nothrow_t, {MallocLike, 3, 0, -1, 1}}, // new(unsigned int, align_val_t, nothrow) - {LibFunc_Znwm, {OpNewLike, 1, 0, -1, -1}}, // new(unsigned long) - {LibFunc_ZnwmRKSt9nothrow_t, {MallocLike, 2, 0, -1, -1}}, // new(unsigned long, nothrow) - {LibFunc_ZnwmSt11align_val_t, {OpNewLike, 2, 0, -1, 1}}, // new(unsigned long, align_val_t) - {LibFunc_ZnwmSt11align_val_tRKSt9nothrow_t, {MallocLike, 3, 0, -1, 1}}, // new(unsigned long, align_val_t, nothrow) - {LibFunc_Znaj, {OpNewLike, 1, 0, -1, -1}}, // new[](unsigned int) - {LibFunc_ZnajRKSt9nothrow_t, {MallocLike, 2, 0, -1, -1}}, // new[](unsigned int, nothrow) - {LibFunc_ZnajSt11align_val_t, {OpNewLike, 2, 0, -1, 1}}, // new[](unsigned int, align_val_t) - {LibFunc_ZnajSt11align_val_tRKSt9nothrow_t, {MallocLike, 3, 0, -1, 1}}, // new[](unsigned int, align_val_t, nothrow) - {LibFunc_Znam, {OpNewLike, 1, 0, -1, -1}}, // new[](unsigned long) - {LibFunc_ZnamRKSt9nothrow_t, {MallocLike, 2, 0, -1, -1}}, // new[](unsigned long, nothrow) - {LibFunc_ZnamSt11align_val_t, {OpNewLike, 2, 0, -1, 1}}, // new[](unsigned long, align_val_t) - {LibFunc_ZnamSt11align_val_tRKSt9nothrow_t, {MallocLike, 3, 0, -1, 1}}, // new[](unsigned long, align_val_t, nothrow) - {LibFunc_msvc_new_int, {OpNewLike, 1, 0, -1, -1}}, // new(unsigned int) - {LibFunc_msvc_new_int_nothrow, {MallocLike, 2, 0, -1, -1}}, // new(unsigned int, nothrow) - {LibFunc_msvc_new_longlong, {OpNewLike, 1, 0, -1, -1}}, // new(unsigned long long) - {LibFunc_msvc_new_longlong_nothrow, {MallocLike, 2, 0, -1, -1}}, // new(unsigned long long, nothrow) - {LibFunc_msvc_new_array_int, {OpNewLike, 1, 0, -1, -1}}, // new[](unsigned int) - {LibFunc_msvc_new_array_int_nothrow, {MallocLike, 2, 0, -1, -1}}, // new[](unsigned int, nothrow) - {LibFunc_msvc_new_array_longlong, {OpNewLike, 1, 0, -1, -1}}, // new[](unsigned long long) - {LibFunc_msvc_new_array_longlong_nothrow, {MallocLike, 2, 0, -1, -1}}, // new[](unsigned long long, nothrow) - {LibFunc_aligned_alloc, {AlignedAllocLike, 2, 1, -1, 0}}, - {LibFunc_memalign, {AlignedAllocLike, 2, 1, -1, 0}}, - {LibFunc_calloc, {CallocLike, 2, 0, 1, -1}}, - {LibFunc_vec_calloc, {CallocLike, 2, 0, 1, -1}}, - {LibFunc_realloc, {ReallocLike, 2, 1, -1, -1}}, - {LibFunc_vec_realloc, {ReallocLike, 2, 1, -1, -1}}, - {LibFunc_reallocf, {ReallocLike, 2, 1, -1, -1}}, - {LibFunc_strdup, {StrDupLike, 1, -1, -1, -1}}, - {LibFunc_strndup, {StrDupLike, 2, 1, -1, -1}}, - {LibFunc___kmpc_alloc_shared, {MallocLike, 1, 0, -1, -1}}, - // TODO: Handle "int posix_memalign(void **, size_t, size_t)" + {LibFunc_malloc, {MallocLike, 1, 0, -1, -1, MallocFamily::Malloc}}, + {LibFunc_vec_malloc, {MallocLike, 1, 0, -1, -1, MallocFamily::VecMalloc}}, + {LibFunc_valloc, {MallocLike, 1, 0, -1, -1, MallocFamily::Malloc}}, + {LibFunc_Znwj, {OpNewLike, 1, 0, -1, -1, MallocFamily::CPPNew}}, // new(unsigned int) + {LibFunc_ZnwjRKSt9nothrow_t, {MallocLike, 2, 0, -1, -1, MallocFamily::CPPNew}}, // new(unsigned int, nothrow) + {LibFunc_ZnwjSt11align_val_t, {OpNewLike, 2, 0, -1, 1, MallocFamily::CPPNewAligned}}, // new(unsigned int, align_val_t) + {LibFunc_ZnwjSt11align_val_tRKSt9nothrow_t, {MallocLike, 3, 0, -1, 1, MallocFamily::CPPNewAligned}}, // new(unsigned int, align_val_t, nothrow) + {LibFunc_Znwm, {OpNewLike, 1, 0, -1, -1, MallocFamily::CPPNew}}, // new(unsigned long) + {LibFunc_ZnwmRKSt9nothrow_t, {MallocLike, 2, 0, -1, -1, MallocFamily::CPPNew}}, // new(unsigned long, nothrow) + {LibFunc_ZnwmSt11align_val_t, {OpNewLike, 2, 0, -1, 1, MallocFamily::CPPNewAligned}}, // new(unsigned long, align_val_t) + {LibFunc_ZnwmSt11align_val_tRKSt9nothrow_t, {MallocLike, 3, 0, -1, 1, MallocFamily::CPPNewAligned}}, // new(unsigned long, align_val_t, nothrow) + {LibFunc_Znaj, {OpNewLike, 1, 0, -1, -1, MallocFamily::CPPNewArray}}, // new[](unsigned int) + {LibFunc_ZnajRKSt9nothrow_t, {MallocLike, 2, 0, -1, -1, MallocFamily::CPPNewArray}}, // new[](unsigned int, nothrow) + {LibFunc_ZnajSt11align_val_t, {OpNewLike, 2, 0, -1, 1, MallocFamily::CPPNewArrayAligned}}, // new[](unsigned int, align_val_t) + {LibFunc_ZnajSt11align_val_tRKSt9nothrow_t, {MallocLike, 3, 0, -1, 1, MallocFamily::CPPNewArrayAligned}}, // new[](unsigned int, align_val_t, nothrow) + {LibFunc_Znam, {OpNewLike, 1, 0, -1, -1, MallocFamily::CPPNewArray}}, // new[](unsigned long) + {LibFunc_ZnamRKSt9nothrow_t, {MallocLike, 2, 0, -1, -1, MallocFamily::CPPNewArray}}, // new[](unsigned long, nothrow) + {LibFunc_ZnamSt11align_val_t, {OpNewLike, 2, 0, -1, 1, MallocFamily::CPPNewArrayAligned}}, // new[](unsigned long, align_val_t) + {LibFunc_ZnamSt11align_val_tRKSt9nothrow_t, {MallocLike, 3, 0, -1, 1, MallocFamily::CPPNewArrayAligned}}, // new[](unsigned long, align_val_t, nothrow) + {LibFunc_msvc_new_int, {OpNewLike, 1, 0, -1, -1, MallocFamily::MSVCNew}}, // new(unsigned int) + {LibFunc_msvc_new_int_nothrow, {MallocLike, 2, 0, -1, -1, MallocFamily::MSVCNew}}, // new(unsigned int, nothrow) + {LibFunc_msvc_new_longlong, {OpNewLike, 1, 0, -1, -1, MallocFamily::MSVCNew}}, // new(unsigned long long) + {LibFunc_msvc_new_longlong_nothrow, {MallocLike, 2, 0, -1, -1, MallocFamily::MSVCNew}}, // new(unsigned long long, nothrow) + {LibFunc_msvc_new_array_int, {OpNewLike, 1, 0, -1, -1, MallocFamily::MSVCArrayNew}}, // new[](unsigned int) + {LibFunc_msvc_new_array_int_nothrow, {MallocLike, 2, 0, -1, -1, MallocFamily::MSVCArrayNew}}, // new[](unsigned int, nothrow) + {LibFunc_msvc_new_array_longlong, {OpNewLike, 1, 0, -1, -1, MallocFamily::MSVCArrayNew}}, // new[](unsigned long long) + {LibFunc_msvc_new_array_longlong_nothrow, {MallocLike, 2, 0, -1, -1, MallocFamily::MSVCArrayNew}}, // new[](unsigned long long, nothrow) + {LibFunc_aligned_alloc, {AlignedAllocLike, 2, 1, -1, 0, MallocFamily::Malloc}}, + {LibFunc_memalign, {AlignedAllocLike, 2, 1, -1, 0, MallocFamily::Malloc}}, + {LibFunc_calloc, {CallocLike, 2, 0, 1, -1, MallocFamily::Malloc}}, + {LibFunc_vec_calloc, {CallocLike, 2, 0, 1, -1, MallocFamily::VecMalloc}}, + {LibFunc_realloc, {ReallocLike, 2, 1, -1, -1, MallocFamily::Malloc}}, + {LibFunc_vec_realloc, {ReallocLike, 2, 1, -1, -1, MallocFamily::VecMalloc}}, + {LibFunc_reallocf, {ReallocLike, 2, 1, -1, -1, MallocFamily::Malloc}}, + {LibFunc_strdup, {StrDupLike, 1, -1, -1, -1, MallocFamily::Malloc}}, + {LibFunc_dunder_strdup, {StrDupLike, 1, -1, -1, -1, MallocFamily::Malloc}}, + {LibFunc_strndup, {StrDupLike, 2, 1, -1, -1, MallocFamily::Malloc}}, + {LibFunc_dunder_strndup, {StrDupLike, 2, 1, -1, -1, MallocFamily::Malloc}}, + {LibFunc___kmpc_alloc_shared, {MallocLike, 1, 0, -1, -1, MallocFamily::KmpcAllocShared}}, }; +// clang-format on static const Function *getCalledFunction(const Value *V, bool &IsNoBuiltin) { @@ -217,7 +260,7 @@ static Optional<AllocFnsTy> getAllocationSize(const Value *V, Result.AllocTy = MallocLike; Result.NumParams = Callee->getNumOperands(); Result.FstParam = Args.first; - Result.SndParam = Args.second.getValueOr(-1); + Result.SndParam = Args.second.value_or(-1); // Allocsize has no way to specify an alignment argument Result.AlignParam = -1; return Result; @@ -227,54 +270,53 @@ static Optional<AllocFnsTy> getAllocationSize(const Value *V, /// allocates or reallocates memory (either malloc, calloc, realloc, or strdup /// like). bool llvm::isAllocationFn(const Value *V, const TargetLibraryInfo *TLI) { - return getAllocationData(V, AnyAlloc, TLI).hasValue(); + return getAllocationData(V, AnyAlloc, TLI).has_value(); } bool llvm::isAllocationFn( const Value *V, function_ref<const TargetLibraryInfo &(Function &)> GetTLI) { - return getAllocationData(V, AnyAlloc, GetTLI).hasValue(); + return getAllocationData(V, AnyAlloc, GetTLI).has_value(); } /// Tests if a value is a call or invoke to a library function that /// allocates uninitialized memory (such as malloc). static bool isMallocLikeFn(const Value *V, const TargetLibraryInfo *TLI) { - return getAllocationData(V, MallocOrOpNewLike, TLI).hasValue(); + return getAllocationData(V, MallocOrOpNewLike, TLI).has_value(); } /// Tests if a value is a call or invoke to a library function that /// allocates uninitialized memory with alignment (such as aligned_alloc). static bool isAlignedAllocLikeFn(const Value *V, const TargetLibraryInfo *TLI) { - return getAllocationData(V, AlignedAllocLike, TLI) - .hasValue(); + return getAllocationData(V, AlignedAllocLike, TLI).has_value(); } /// Tests if a value is a call or invoke to a library function that /// allocates zero-filled memory (such as calloc). static bool isCallocLikeFn(const Value *V, const TargetLibraryInfo *TLI) { - return getAllocationData(V, CallocLike, TLI).hasValue(); + return getAllocationData(V, CallocLike, TLI).has_value(); } /// Tests if a value is a call or invoke to a library function that /// allocates memory similar to malloc or calloc. bool llvm::isMallocOrCallocLikeFn(const Value *V, const TargetLibraryInfo *TLI) { - return getAllocationData(V, MallocOrCallocLike, TLI).hasValue(); + return getAllocationData(V, MallocOrCallocLike, TLI).has_value(); } /// Tests if a value is a call or invoke to a library function that /// allocates memory (either malloc, calloc, or strdup like). bool llvm::isAllocLikeFn(const Value *V, const TargetLibraryInfo *TLI) { - return getAllocationData(V, AllocLike, TLI).hasValue(); + return getAllocationData(V, AllocLike, TLI).has_value(); } /// Tests if a value is a call or invoke to a library function that /// reallocates memory (e.g., realloc). bool llvm::isReallocLikeFn(const Value *V, const TargetLibraryInfo *TLI) { - return getAllocationData(V, ReallocLike, TLI).hasValue(); + return getAllocationData(V, ReallocLike, TLI).has_value(); } /// Tests if a functions is a call or invoke to a library function that /// reallocates memory (e.g., realloc). bool llvm::isReallocLikeFn(const Function *F, const TargetLibraryInfo *TLI) { - return getAllocationDataForFunction(F, ReallocLike, TLI).hasValue(); + return getAllocationDataForFunction(F, ReallocLike, TLI).has_value(); } bool llvm::isAllocRemovable(const CallBase *CB, const TargetLibraryInfo *TLI) { @@ -291,13 +333,11 @@ bool llvm::isAllocRemovable(const CallBase *CB, const TargetLibraryInfo *TLI) { Value *llvm::getAllocAlignment(const CallBase *V, const TargetLibraryInfo *TLI) { - assert(isAllocationFn(V, TLI)); - const Optional<AllocFnsTy> FnData = getAllocationData(V, AnyAlloc, TLI); - if (!FnData.hasValue() || FnData->AlignParam < 0) { - return nullptr; + if (FnData && FnData->AlignParam >= 0) { + return V->getOperand(FnData->AlignParam); } - return V->getOperand(FnData->AlignParam); + return V->getArgOperandWithAttribute(Attribute::AllocAlign); } /// When we're compiling N-bit code, and the user uses parameters that are @@ -344,7 +384,7 @@ llvm::getAllocSize(const CallBase *CB, if (!Arg) return None; - APInt MaxSize = Arg->getValue().zextOrSelf(IntTyBits); + APInt MaxSize = Arg->getValue().zext(IntTyBits); if (Size.ugt(MaxSize)) Size = MaxSize + 1; } @@ -379,10 +419,12 @@ llvm::getAllocSize(const CallBase *CB, return Size; } -Constant *llvm::getInitialValueOfAllocation(const CallBase *Alloc, +Constant *llvm::getInitialValueOfAllocation(const Value *V, const TargetLibraryInfo *TLI, Type *Ty) { - assert(isAllocationFn(Alloc, TLI)); + auto *Alloc = dyn_cast<CallBase>(V); + if (!Alloc) + return nullptr; // malloc and aligned_alloc are uninitialized (undef) if (isMallocLikeFn(Alloc, TLI) || isAlignedAllocLikeFn(Alloc, TLI)) @@ -395,43 +437,81 @@ Constant *llvm::getInitialValueOfAllocation(const CallBase *Alloc, return nullptr; } +struct FreeFnsTy { + unsigned NumParams; + // Name of default allocator function to group malloc/free calls by family + MallocFamily Family; +}; + +// clang-format off +static const std::pair<LibFunc, FreeFnsTy> FreeFnData[] = { + {LibFunc_free, {1, MallocFamily::Malloc}}, + {LibFunc_vec_free, {1, MallocFamily::VecMalloc}}, + {LibFunc_ZdlPv, {1, MallocFamily::CPPNew}}, // operator delete(void*) + {LibFunc_ZdaPv, {1, MallocFamily::CPPNewArray}}, // operator delete[](void*) + {LibFunc_msvc_delete_ptr32, {1, MallocFamily::MSVCNew}}, // operator delete(void*) + {LibFunc_msvc_delete_ptr64, {1, MallocFamily::MSVCNew}}, // operator delete(void*) + {LibFunc_msvc_delete_array_ptr32, {1, MallocFamily::MSVCArrayNew}}, // operator delete[](void*) + {LibFunc_msvc_delete_array_ptr64, {1, MallocFamily::MSVCArrayNew}}, // operator delete[](void*) + {LibFunc_ZdlPvj, {2, MallocFamily::CPPNew}}, // delete(void*, uint) + {LibFunc_ZdlPvm, {2, MallocFamily::CPPNew}}, // delete(void*, ulong) + {LibFunc_ZdlPvRKSt9nothrow_t, {2, MallocFamily::CPPNew}}, // delete(void*, nothrow) + {LibFunc_ZdlPvSt11align_val_t, {2, MallocFamily::CPPNewAligned}}, // delete(void*, align_val_t) + {LibFunc_ZdaPvj, {2, MallocFamily::CPPNewArray}}, // delete[](void*, uint) + {LibFunc_ZdaPvm, {2, MallocFamily::CPPNewArray}}, // delete[](void*, ulong) + {LibFunc_ZdaPvRKSt9nothrow_t, {2, MallocFamily::CPPNewArray}}, // delete[](void*, nothrow) + {LibFunc_ZdaPvSt11align_val_t, {2, MallocFamily::CPPNewArrayAligned}}, // delete[](void*, align_val_t) + {LibFunc_msvc_delete_ptr32_int, {2, MallocFamily::MSVCNew}}, // delete(void*, uint) + {LibFunc_msvc_delete_ptr64_longlong, {2, MallocFamily::MSVCNew}}, // delete(void*, ulonglong) + {LibFunc_msvc_delete_ptr32_nothrow, {2, MallocFamily::MSVCNew}}, // delete(void*, nothrow) + {LibFunc_msvc_delete_ptr64_nothrow, {2, MallocFamily::MSVCNew}}, // delete(void*, nothrow) + {LibFunc_msvc_delete_array_ptr32_int, {2, MallocFamily::MSVCArrayNew}}, // delete[](void*, uint) + {LibFunc_msvc_delete_array_ptr64_longlong, {2, MallocFamily::MSVCArrayNew}}, // delete[](void*, ulonglong) + {LibFunc_msvc_delete_array_ptr32_nothrow, {2, MallocFamily::MSVCArrayNew}}, // delete[](void*, nothrow) + {LibFunc_msvc_delete_array_ptr64_nothrow, {2, MallocFamily::MSVCArrayNew}}, // delete[](void*, nothrow) + {LibFunc___kmpc_free_shared, {2, MallocFamily::KmpcAllocShared}}, // OpenMP Offloading RTL free + {LibFunc_ZdlPvSt11align_val_tRKSt9nothrow_t, {3, MallocFamily::CPPNewAligned}}, // delete(void*, align_val_t, nothrow) + {LibFunc_ZdaPvSt11align_val_tRKSt9nothrow_t, {3, MallocFamily::CPPNewArrayAligned}}, // delete[](void*, align_val_t, nothrow) + {LibFunc_ZdlPvjSt11align_val_t, {3, MallocFamily::CPPNewAligned}}, // delete(void*, unsigned int, align_val_t) + {LibFunc_ZdlPvmSt11align_val_t, {3, MallocFamily::CPPNewAligned}}, // delete(void*, unsigned long, align_val_t) + {LibFunc_ZdaPvjSt11align_val_t, {3, MallocFamily::CPPNewArrayAligned}}, // delete[](void*, unsigned int, align_val_t) + {LibFunc_ZdaPvmSt11align_val_t, {3, MallocFamily::CPPNewArrayAligned}}, // delete[](void*, unsigned long, align_val_t) +}; +// clang-format on + +Optional<FreeFnsTy> getFreeFunctionDataForFunction(const Function *Callee, + const LibFunc TLIFn) { + const auto *Iter = + find_if(FreeFnData, [TLIFn](const std::pair<LibFunc, FreeFnsTy> &P) { + return P.first == TLIFn; + }); + if (Iter == std::end(FreeFnData)) + return None; + return Iter->second; +} + +Optional<StringRef> llvm::getAllocationFamily(const Value *I, + const TargetLibraryInfo *TLI) { + bool IsNoBuiltin; + const Function *Callee = getCalledFunction(I, IsNoBuiltin); + if (Callee == nullptr || IsNoBuiltin) + return None; + LibFunc TLIFn; + if (!TLI || !TLI->getLibFunc(*Callee, TLIFn) || !TLI->has(TLIFn)) + return None; + const auto AllocData = getAllocationDataForFunction(Callee, AnyAlloc, TLI); + if (AllocData) + return mangledNameForMallocFamily(AllocData.getValue().Family); + const auto FreeData = getFreeFunctionDataForFunction(Callee, TLIFn); + if (FreeData) + return mangledNameForMallocFamily(FreeData.getValue().Family); + return None; +} + /// isLibFreeFunction - Returns true if the function is a builtin free() bool llvm::isLibFreeFunction(const Function *F, const LibFunc TLIFn) { - unsigned ExpectedNumParams; - if (TLIFn == LibFunc_free || - TLIFn == LibFunc_ZdlPv || // operator delete(void*) - TLIFn == LibFunc_ZdaPv || // operator delete[](void*) - TLIFn == LibFunc_msvc_delete_ptr32 || // operator delete(void*) - TLIFn == LibFunc_msvc_delete_ptr64 || // operator delete(void*) - TLIFn == LibFunc_msvc_delete_array_ptr32 || // operator delete[](void*) - TLIFn == LibFunc_msvc_delete_array_ptr64) // operator delete[](void*) - ExpectedNumParams = 1; - else if (TLIFn == LibFunc_ZdlPvj || // delete(void*, uint) - TLIFn == LibFunc_ZdlPvm || // delete(void*, ulong) - TLIFn == LibFunc_ZdlPvRKSt9nothrow_t || // delete(void*, nothrow) - TLIFn == LibFunc_ZdlPvSt11align_val_t || // delete(void*, align_val_t) - TLIFn == LibFunc_ZdaPvj || // delete[](void*, uint) - TLIFn == LibFunc_ZdaPvm || // delete[](void*, ulong) - TLIFn == LibFunc_ZdaPvRKSt9nothrow_t || // delete[](void*, nothrow) - TLIFn == LibFunc_ZdaPvSt11align_val_t || // delete[](void*, align_val_t) - TLIFn == LibFunc_msvc_delete_ptr32_int || // delete(void*, uint) - TLIFn == LibFunc_msvc_delete_ptr64_longlong || // delete(void*, ulonglong) - TLIFn == LibFunc_msvc_delete_ptr32_nothrow || // delete(void*, nothrow) - TLIFn == LibFunc_msvc_delete_ptr64_nothrow || // delete(void*, nothrow) - TLIFn == LibFunc_msvc_delete_array_ptr32_int || // delete[](void*, uint) - TLIFn == LibFunc_msvc_delete_array_ptr64_longlong || // delete[](void*, ulonglong) - TLIFn == LibFunc_msvc_delete_array_ptr32_nothrow || // delete[](void*, nothrow) - TLIFn == LibFunc_msvc_delete_array_ptr64_nothrow || // delete[](void*, nothrow) - TLIFn == LibFunc___kmpc_free_shared) // OpenMP Offloading RTL free - ExpectedNumParams = 2; - else if (TLIFn == LibFunc_ZdaPvSt11align_val_tRKSt9nothrow_t || // delete(void*, align_val_t, nothrow) - TLIFn == LibFunc_ZdlPvSt11align_val_tRKSt9nothrow_t || // delete[](void*, align_val_t, nothrow) - TLIFn == LibFunc_ZdlPvjSt11align_val_t || // delete(void*, unsigned long, align_val_t) - TLIFn == LibFunc_ZdlPvmSt11align_val_t || // delete(void*, unsigned long, align_val_t) - TLIFn == LibFunc_ZdaPvjSt11align_val_t || // delete[](void*, unsigned int, align_val_t) - TLIFn == LibFunc_ZdaPvmSt11align_val_t) // delete[](void*, unsigned long, align_val_t) - ExpectedNumParams = 3; - else + Optional<FreeFnsTy> FnData = getFreeFunctionDataForFunction(F, TLIFn); + if (!FnData) return false; // Check free prototype. @@ -440,7 +520,7 @@ bool llvm::isLibFreeFunction(const Function *F, const LibFunc TLIFn) { FunctionType *FTy = F->getFunctionType(); if (!FTy->getReturnType()->isVoidTy()) return false; - if (FTy->getNumParams() != ExpectedNumParams) + if (FTy->getNumParams() != FnData->NumParams) return false; if (FTy->getParamType(0) != Type::getInt8PtrTy(F->getContext())) return false; @@ -491,11 +571,21 @@ Value *llvm::lowerObjectSizeCall(IntrinsicInst *ObjectSize, const DataLayout &DL, const TargetLibraryInfo *TLI, bool MustSucceed) { + return lowerObjectSizeCall(ObjectSize, DL, TLI, /*AAResults=*/nullptr, + MustSucceed); +} + +Value *llvm::lowerObjectSizeCall(IntrinsicInst *ObjectSize, + const DataLayout &DL, + const TargetLibraryInfo *TLI, AAResults *AA, + bool MustSucceed) { assert(ObjectSize->getIntrinsicID() == Intrinsic::objectsize && "ObjectSize must be a call to llvm.objectsize!"); bool MaxVal = cast<ConstantInt>(ObjectSize->getArgOperand(1))->isZero(); ObjectSizeOpts EvalOptions; + EvalOptions.AA = AA; + // Unless we have to fold this to something, try to be as accurate as // possible. if (MustSucceed) @@ -559,7 +649,7 @@ STATISTIC(ObjectVisitorLoad, APInt ObjectSizeOffsetVisitor::align(APInt Size, MaybeAlign Alignment) { if (Options.RoundToAlign && Alignment) - return APInt(IntTyBits, alignTo(Size.getZExtValue(), Alignment)); + return APInt(IntTyBits, alignTo(Size.getZExtValue(), *Alignment)); return Size; } @@ -573,18 +663,48 @@ ObjectSizeOffsetVisitor::ObjectSizeOffsetVisitor(const DataLayout &DL, } SizeOffsetType ObjectSizeOffsetVisitor::compute(Value *V) { + unsigned InitialIntTyBits = DL.getIndexTypeSizeInBits(V->getType()); + + // Stripping pointer casts can strip address space casts which can change the + // index type size. The invariant is that we use the value type to determine + // the index type size and if we stripped address space casts we have to + // readjust the APInt as we pass it upwards in order for the APInt to match + // the type the caller passed in. + APInt Offset(InitialIntTyBits, 0); + V = V->stripAndAccumulateConstantOffsets( + DL, Offset, /* AllowNonInbounds */ true, /* AllowInvariantGroup */ true); + + // Later we use the index type size and zero but it will match the type of the + // value that is passed to computeImpl. IntTyBits = DL.getIndexTypeSizeInBits(V->getType()); Zero = APInt::getZero(IntTyBits); - V = V->stripPointerCasts(); + bool IndexTypeSizeChanged = InitialIntTyBits != IntTyBits; + if (!IndexTypeSizeChanged && Offset.isZero()) + return computeImpl(V); + + // We stripped an address space cast that changed the index type size or we + // accumulated some constant offset (or both). Readjust the bit width to match + // the argument index type size and apply the offset, as required. + SizeOffsetType SOT = computeImpl(V); + if (IndexTypeSizeChanged) { + if (knownSize(SOT) && !::CheckedZextOrTrunc(SOT.first, InitialIntTyBits)) + SOT.first = APInt(); + if (knownOffset(SOT) && !::CheckedZextOrTrunc(SOT.second, InitialIntTyBits)) + SOT.second = APInt(); + } + // If the computed offset is "unknown" we cannot add the stripped offset. + return {SOT.first, + SOT.second.getBitWidth() > 1 ? SOT.second + Offset : SOT.second}; +} + +SizeOffsetType ObjectSizeOffsetVisitor::computeImpl(Value *V) { if (Instruction *I = dyn_cast<Instruction>(V)) { // If we have already seen this instruction, bail out. Cycles can happen in // unreachable code after constant propagation. if (!SeenInsts.insert(I).second) return unknown(); - if (GEPOperator *GEP = dyn_cast<GEPOperator>(V)) - return visitGEPOperator(*GEP); return visit(*I); } if (Argument *A = dyn_cast<Argument>(V)) @@ -597,12 +717,6 @@ SizeOffsetType ObjectSizeOffsetVisitor::compute(Value *V) { return visitGlobalVariable(*GV); if (UndefValue *UV = dyn_cast<UndefValue>(V)) return visitUndefValue(*UV); - if (ConstantExpr *CE = dyn_cast<ConstantExpr>(V)) { - if (CE->getOpcode() == Instruction::IntToPtr) - return unknown(); // clueless - if (CE->getOpcode() == Instruction::GetElementPtr) - return visitGEPOperator(cast<GEPOperator>(*CE)); - } LLVM_DEBUG(dbgs() << "ObjectSizeOffsetVisitor::compute() unhandled value: " << *V << '\n'); @@ -617,10 +731,10 @@ SizeOffsetType ObjectSizeOffsetVisitor::visitAllocaInst(AllocaInst &I) { if (!I.getAllocatedType()->isSized()) return unknown(); - if (isa<ScalableVectorType>(I.getAllocatedType())) + TypeSize ElemSize = DL.getTypeAllocSize(I.getAllocatedType()); + if (ElemSize.isScalable() && Options.EvalMode != ObjectSizeOpts::Mode::Min) return unknown(); - - APInt Size(IntTyBits, DL.getTypeAllocSize(I.getAllocatedType())); + APInt Size(IntTyBits, ElemSize.getKnownMinSize()); if (!I.isArrayAllocation()) return std::make_pair(align(Size, I.getAlign()), Zero); @@ -682,15 +796,6 @@ ObjectSizeOffsetVisitor::visitExtractValueInst(ExtractValueInst&) { return unknown(); } -SizeOffsetType ObjectSizeOffsetVisitor::visitGEPOperator(GEPOperator &GEP) { - SizeOffsetType PtrData = compute(GEP.getPointerOperand()); - APInt Offset(DL.getIndexTypeSizeInBits(GEP.getPointerOperand()->getType()), 0); - if (!bothKnown(PtrData) || !GEP.accumulateConstantOffset(DL, Offset)) - return unknown(); - - return std::make_pair(PtrData.first, PtrData.second + Offset); -} - SizeOffsetType ObjectSizeOffsetVisitor::visitGlobalAlias(GlobalAlias &GA) { if (GA.isInterposable()) return unknown(); @@ -710,42 +815,161 @@ SizeOffsetType ObjectSizeOffsetVisitor::visitIntToPtrInst(IntToPtrInst&) { return unknown(); } -SizeOffsetType ObjectSizeOffsetVisitor::visitLoadInst(LoadInst&) { - ++ObjectVisitorLoad; - return unknown(); -} +SizeOffsetType ObjectSizeOffsetVisitor::findLoadSizeOffset( + LoadInst &Load, BasicBlock &BB, BasicBlock::iterator From, + SmallDenseMap<BasicBlock *, SizeOffsetType, 8> &VisitedBlocks, + unsigned &ScannedInstCount) { + constexpr unsigned MaxInstsToScan = 128; + + auto Where = VisitedBlocks.find(&BB); + if (Where != VisitedBlocks.end()) + return Where->second; + + auto Unknown = [this, &BB, &VisitedBlocks]() { + return VisitedBlocks[&BB] = unknown(); + }; + auto Known = [&BB, &VisitedBlocks](SizeOffsetType SO) { + return VisitedBlocks[&BB] = SO; + }; + + do { + Instruction &I = *From; + + if (I.isDebugOrPseudoInst()) + continue; + + if (++ScannedInstCount > MaxInstsToScan) + return Unknown(); + + if (!I.mayWriteToMemory()) + continue; + + if (auto *SI = dyn_cast<StoreInst>(&I)) { + AliasResult AR = + Options.AA->alias(SI->getPointerOperand(), Load.getPointerOperand()); + switch ((AliasResult::Kind)AR) { + case AliasResult::NoAlias: + continue; + case AliasResult::MustAlias: + if (SI->getValueOperand()->getType()->isPointerTy()) + return Known(compute(SI->getValueOperand())); + else + return Unknown(); // No handling of non-pointer values by `compute`. + default: + return Unknown(); + } + } -SizeOffsetType ObjectSizeOffsetVisitor::visitPHINode(PHINode&) { - // too complex to analyze statically. - return unknown(); + if (auto *CB = dyn_cast<CallBase>(&I)) { + Function *Callee = CB->getCalledFunction(); + // Bail out on indirect call. + if (!Callee) + return Unknown(); + + LibFunc TLIFn; + if (!TLI || !TLI->getLibFunc(*CB->getCalledFunction(), TLIFn) || + !TLI->has(TLIFn)) + return Unknown(); + + // TODO: There's probably more interesting case to support here. + if (TLIFn != LibFunc_posix_memalign) + return Unknown(); + + AliasResult AR = + Options.AA->alias(CB->getOperand(0), Load.getPointerOperand()); + switch ((AliasResult::Kind)AR) { + case AliasResult::NoAlias: + continue; + case AliasResult::MustAlias: + break; + default: + return Unknown(); + } + + // Is the error status of posix_memalign correctly checked? If not it + // would be incorrect to assume it succeeds and load doesn't see the + // previous value. + Optional<bool> Checked = isImpliedByDomCondition( + ICmpInst::ICMP_EQ, CB, ConstantInt::get(CB->getType(), 0), &Load, DL); + if (!Checked || !*Checked) + return Unknown(); + + Value *Size = CB->getOperand(2); + auto *C = dyn_cast<ConstantInt>(Size); + if (!C) + return Unknown(); + + return Known({C->getValue(), APInt(C->getValue().getBitWidth(), 0)}); + } + + return Unknown(); + } while (From-- != BB.begin()); + + SmallVector<SizeOffsetType> PredecessorSizeOffsets; + for (auto *PredBB : predecessors(&BB)) { + PredecessorSizeOffsets.push_back(findLoadSizeOffset( + Load, *PredBB, BasicBlock::iterator(PredBB->getTerminator()), + VisitedBlocks, ScannedInstCount)); + if (!bothKnown(PredecessorSizeOffsets.back())) + return Unknown(); + } + + if (PredecessorSizeOffsets.empty()) + return Unknown(); + + return Known(std::accumulate(PredecessorSizeOffsets.begin() + 1, + PredecessorSizeOffsets.end(), + PredecessorSizeOffsets.front(), + [this](SizeOffsetType LHS, SizeOffsetType RHS) { + return combineSizeOffset(LHS, RHS); + })); } -SizeOffsetType ObjectSizeOffsetVisitor::visitSelectInst(SelectInst &I) { - SizeOffsetType TrueSide = compute(I.getTrueValue()); - SizeOffsetType FalseSide = compute(I.getFalseValue()); - if (bothKnown(TrueSide) && bothKnown(FalseSide)) { - if (TrueSide == FalseSide) { - return TrueSide; - } +SizeOffsetType ObjectSizeOffsetVisitor::visitLoadInst(LoadInst &LI) { + if (!Options.AA) { + ++ObjectVisitorLoad; + return unknown(); + } - APInt TrueResult = getSizeWithOverflow(TrueSide); - APInt FalseResult = getSizeWithOverflow(FalseSide); + SmallDenseMap<BasicBlock *, SizeOffsetType, 8> VisitedBlocks; + unsigned ScannedInstCount = 0; + SizeOffsetType SO = + findLoadSizeOffset(LI, *LI.getParent(), BasicBlock::iterator(LI), + VisitedBlocks, ScannedInstCount); + if (!bothKnown(SO)) + ++ObjectVisitorLoad; + return SO; +} - if (TrueResult == FalseResult) { - return TrueSide; - } - if (Options.EvalMode == ObjectSizeOpts::Mode::Min) { - if (TrueResult.slt(FalseResult)) - return TrueSide; - return FalseSide; - } - if (Options.EvalMode == ObjectSizeOpts::Mode::Max) { - if (TrueResult.sgt(FalseResult)) - return TrueSide; - return FalseSide; - } +SizeOffsetType ObjectSizeOffsetVisitor::combineSizeOffset(SizeOffsetType LHS, + SizeOffsetType RHS) { + if (!bothKnown(LHS) || !bothKnown(RHS)) + return unknown(); + + switch (Options.EvalMode) { + case ObjectSizeOpts::Mode::Min: + return (getSizeWithOverflow(LHS).slt(getSizeWithOverflow(RHS))) ? LHS : RHS; + case ObjectSizeOpts::Mode::Max: + return (getSizeWithOverflow(LHS).sgt(getSizeWithOverflow(RHS))) ? LHS : RHS; + case ObjectSizeOpts::Mode::Exact: + return (getSizeWithOverflow(LHS).eq(getSizeWithOverflow(RHS))) ? LHS + : unknown(); } - return unknown(); + llvm_unreachable("missing an eval mode"); +} + +SizeOffsetType ObjectSizeOffsetVisitor::visitPHINode(PHINode &PN) { + auto IncomingValues = PN.incoming_values(); + return std::accumulate(IncomingValues.begin() + 1, IncomingValues.end(), + compute(*IncomingValues.begin()), + [this](SizeOffsetType LHS, Value *VRHS) { + return combineSizeOffset(LHS, compute(VRHS)); + }); +} + +SizeOffsetType ObjectSizeOffsetVisitor::visitSelectInst(SelectInst &I) { + return combineSizeOffset(compute(I.getTrueValue()), + compute(I.getFalseValue())); } SizeOffsetType ObjectSizeOffsetVisitor::visitUndefValue(UndefValue&) { @@ -790,7 +1014,7 @@ SizeOffsetEvalType ObjectSizeOffsetEvaluator::compute(Value *V) { // Erase any instructions we inserted as part of the traversal. for (Instruction *I : InsertedInstructions) { - I->replaceAllUsesWith(UndefValue::get(I->getType())); + I->replaceAllUsesWith(PoisonValue::get(I->getType())); I->eraseFromParent(); } } @@ -919,7 +1143,7 @@ SizeOffsetEvalType ObjectSizeOffsetEvaluator::visitIntToPtrInst(IntToPtrInst&) { return unknown(); } -SizeOffsetEvalType ObjectSizeOffsetEvaluator::visitLoadInst(LoadInst&) { +SizeOffsetEvalType ObjectSizeOffsetEvaluator::visitLoadInst(LoadInst &LI) { return unknown(); } @@ -937,10 +1161,10 @@ SizeOffsetEvalType ObjectSizeOffsetEvaluator::visitPHINode(PHINode &PHI) { SizeOffsetEvalType EdgeData = compute_(PHI.getIncomingValue(i)); if (!bothKnown(EdgeData)) { - OffsetPHI->replaceAllUsesWith(UndefValue::get(IntTy)); + OffsetPHI->replaceAllUsesWith(PoisonValue::get(IntTy)); OffsetPHI->eraseFromParent(); InsertedInstructions.erase(OffsetPHI); - SizePHI->replaceAllUsesWith(UndefValue::get(IntTy)); + SizePHI->replaceAllUsesWith(PoisonValue::get(IntTy)); SizePHI->eraseFromParent(); InsertedInstructions.erase(SizePHI); return unknown(); |