diff --git a/llvm/include/llvm/Analysis/MemoryBuiltins.h b/llvm/include/llvm/Analysis/MemoryBuiltins.h --- a/llvm/include/llvm/Analysis/MemoryBuiltins.h +++ b/llvm/include/llvm/Analysis/MemoryBuiltins.h @@ -28,6 +28,7 @@ namespace llvm { class AllocaInst; +class AAResults; class Argument; class CallInst; class ConstantPointerNull; @@ -152,6 +153,8 @@ /// though they can't be evaluated. Otherwise, null is always considered to /// point to a 0 byte region of memory. bool NullIsUnknownSize = false; + /// If set, used for more accurate evaluation + AAResults *AA = nullptr; }; /// Compute the size of the object pointed by Ptr. Returns true and the @@ -171,8 +174,9 @@ /// argument of the call to objectsize. Value *lowerObjectSizeCall(IntrinsicInst *ObjectSize, const DataLayout &DL, const TargetLibraryInfo *TLI, bool MustSucceed); - - +Value *lowerObjectSizeCall(IntrinsicInst *ObjectSize, const DataLayout &DL, + const TargetLibraryInfo *TLI, AAResults *AA, + bool MustSucceed); using SizeOffsetType = std::pair; diff --git a/llvm/lib/Analysis/MemoryBuiltins.cpp b/llvm/lib/Analysis/MemoryBuiltins.cpp --- a/llvm/lib/Analysis/MemoryBuiltins.cpp +++ b/llvm/lib/Analysis/MemoryBuiltins.cpp @@ -17,6 +17,7 @@ #include "llvm/ADT/Optional.h" #include "llvm/ADT/STLExtras.h" #include "llvm/ADT/Statistic.h" +#include "llvm/Analysis/AliasAnalysis.h" #include "llvm/Analysis/TargetFolder.h" #include "llvm/Analysis/TargetLibraryInfo.h" #include "llvm/Analysis/Utils/Local.h" @@ -153,7 +154,6 @@ {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}}, - // TODO: Handle "int posix_memalign(void **, size_t, size_t)" }; // clang-format on @@ -576,11 +576,22 @@ 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(ObjectSize->getArgOperand(1))->isZero(); ObjectSizeOpts EvalOptions; + if (AA) + EvalOptions.AA = AA; + // Unless we have to fold this to something, try to be as accurate as // possible. if (MustSucceed) @@ -810,9 +821,113 @@ return unknown(); } -SizeOffsetType ObjectSizeOffsetVisitor::visitLoadInst(LoadInst&) { - ++ObjectVisitorLoad; - return unknown(); +SizeOffsetType ObjectSizeOffsetVisitor::visitLoadInst(LoadInst &LI) { + /* + * Poor's man tracking of the origin of the loaded address. The sole goal of + * this function to handle an allocation pattern based on posix_memalign: + * + * void* buffer; + * posix_memalign(&buffer, 8, 128); + * + * Note however that it also catches situation where the loaded address is + * always used to store known buffers to. + * + * We only consider loads from alloca or arguments with `noalias` attributes + * to avoid any aliasing issue. + */ + + auto Unknown = [this]() { + ++ObjectVisitorLoad; + return unknown(); + }; + + Value *LoadingFrom = LI.getOperand(0)->stripPointerCasts(); + Argument *A = dyn_cast(LoadingFrom); + if (!(isa(LoadingFrom) || (A && A->hasNoAliasAttr()))) + return Unknown(); + + /* + * Walk through users of the memory address we're loading from. All the users + * must store value at this address for this analysis to be valid. + */ + SmallVector WorkList; + for (User *U : LoadingFrom->users()) + WorkList.push_back(U); + + SmallSet Visited; + Visited.insert(&LI); + SmallVector SizeOffsets; + + while (!WorkList.empty()) { + Value *V = WorkList.pop_back_val(); + if (Visited.count(V)) + continue; + + // Ignore bit casts. + if (isa(V)) { + for (User *U : V->users()) + WorkList.push_back(U); + continue; + } + + // Track posix_memalign. + if (auto *CB = dyn_cast(V)) { + Function *Callee = CB->getCalledFunction(); + // Bail out on indirect call. + if (!Callee) + return Unknown(); + + // These users can safely be ignored. + auto ID = CB->getIntrinsicID(); + switch (ID) { + case Intrinsic::lifetime_start: + case Intrinsic::lifetime_end: + continue; + default:; + } + + // posix_memalign case. + LibFunc TLIFn; + if (!TLI || !TLI->getLibFunc(*CB->getCalledFunction(), TLIFn) || + !TLI->has(TLIFn)) + return Unknown(); + + if (TLIFn != LibFunc_posix_memalign) + return unknown(); + + Value *Size = CB->getOperand(2); + auto *C = dyn_cast(Size); + if (!C) + return Unknown(); + + SizeOffsets.push_back( + {C->getValue(), APInt(C->getValue().getBitWidth(), 0)}); + } + + // Are we storing a computable value? + else if (auto *SI = dyn_cast(V)) { + if (Options.AA && Options.AA->isNoAlias(SI->getOperand(0), &LI)) { + // According to AA, this store is dead at `LI` point, so skip it. + continue; + } + auto SizeOffset = compute(SI->getOperand(0)); + SizeOffsets.push_back(SizeOffset); + } + + // Bail out. + else { + return Unknown(); + } + } + + if (SizeOffsets.empty()) + return Unknown(); + + return std::accumulate(SizeOffsets.begin() + 1, SizeOffsets.end(), + SizeOffsets.front(), + [this](SizeOffsetType LHS, SizeOffsetType RHS) { + return combineSizeOffset(LHS, RHS); + }); } SizeOffsetType ObjectSizeOffsetVisitor::combineSizeOffset(SizeOffsetType LHS, diff --git a/llvm/lib/Transforms/InstCombine/InstCombineCalls.cpp b/llvm/lib/Transforms/InstCombine/InstCombineCalls.cpp --- a/llvm/lib/Transforms/InstCombine/InstCombineCalls.cpp +++ b/llvm/lib/Transforms/InstCombine/InstCombineCalls.cpp @@ -1184,7 +1184,7 @@ Intrinsic::ID IID = II->getIntrinsicID(); switch (IID) { case Intrinsic::objectsize: - if (Value *V = lowerObjectSizeCall(II, DL, &TLI, /*MustSucceed=*/false)) + if (Value *V = lowerObjectSizeCall(II, DL, &TLI, AA, /*MustSucceed=*/false)) return replaceInstUsesWith(CI, V); return nullptr; case Intrinsic::abs: { diff --git a/llvm/lib/Transforms/InstCombine/InstructionCombining.cpp b/llvm/lib/Transforms/InstCombine/InstructionCombining.cpp --- a/llvm/lib/Transforms/InstCombine/InstructionCombining.cpp +++ b/llvm/lib/Transforms/InstCombine/InstructionCombining.cpp @@ -2810,7 +2810,7 @@ if (IntrinsicInst *II = dyn_cast(I)) { if (II->getIntrinsicID() == Intrinsic::objectsize) { Value *Result = - lowerObjectSizeCall(II, DL, &TLI, /*MustSucceed=*/true); + lowerObjectSizeCall(II, DL, &TLI, AA, /*MustSucceed=*/true); replaceInstUsesWith(*I, Result); eraseInstFromFunction(*I); Users[i] = nullptr; // Skip examining in the next loop. diff --git a/llvm/test/Transforms/InstCombine/builtin-object-size-posix-memalign.ll b/llvm/test/Transforms/InstCombine/builtin-object-size-posix-memalign.ll new file mode 100644 --- /dev/null +++ b/llvm/test/Transforms/InstCombine/builtin-object-size-posix-memalign.ll @@ -0,0 +1,93 @@ +; NOTE: Assertions have been autogenerated by utils/update_test_checks.py +; RUN: opt -instcombine -S < %s | FileCheck %s + +target datalayout = "e-m:e-p270:32:32-p271:32:32-p272:64:64-i64:64-f80:128-n8:16:32:64-S128" +target triple = "x86_64-unknown-linux-gnu" + +declare dso_local i32 @posix_memalign(i8** noundef, i64 noundef, i64 noundef) +declare i64 @llvm.objectsize.i64.p0i8(i8*, i1 immarg, i1 immarg, i1 immarg) + + +define dso_local i64 @check_posix_memalign(i32 noundef %n) local_unnamed_addr { +; CHECK-LABEL: @check_posix_memalign( +; CHECK-NEXT: entry: +; CHECK-NEXT: [[PTR:%.*]] = alloca i8*, align 8 +; CHECK-NEXT: [[CALL:%.*]] = call i32 @posix_memalign(i8** noundef nonnull [[PTR]], i64 noundef 8, i64 noundef 17) +; CHECK-NEXT: [[TOBOOL_NOT:%.*]] = icmp eq i32 [[CALL]], 0 +; CHECK-NEXT: br i1 [[TOBOOL_NOT]], label [[IF_END:%.*]], label [[IF_THEN:%.*]] +; CHECK: if.then: +; CHECK-NEXT: br label [[RETURN:%.*]] +; CHECK: if.end: +; CHECK-NEXT: br label [[RETURN]] +; CHECK: return: +; CHECK-NEXT: [[STOREMERGE:%.*]] = phi i64 [ 17, [[IF_END]] ], [ -1, [[IF_THEN]] ] +; CHECK-NEXT: ret i64 [[STOREMERGE]] +; +entry: + %retval = alloca i64 + %ptr = alloca i8* + %call = call i32 @posix_memalign(i8** noundef %ptr, i64 noundef 8, i64 noundef 17) + %tobool = icmp ne i32 %call, 0 + br i1 %tobool, label %if.then, label %if.end + +if.then: + store i64 -1, i64* %retval, align 8 + br label %return + +if.end: + %0 = load i8*, i8** %ptr, align 8 + %1 = call i64 @llvm.objectsize.i64.p0i8(i8* %0, i1 false, i1 true, i1 false) + store i64 %1, i64* %retval, align 8 + br label %return + +return: + %2 = load i64, i64* %retval, align 8 + ret i64 %2 + +} + + +define dso_local i64 @check_posix_memalign_null() { +; CHECK-LABEL: @check_posix_memalign_null( +; CHECK-NEXT: entry: +; CHECK-NEXT: [[PTR:%.*]] = alloca float*, align 8 +; CHECK-NEXT: store float* null, float** [[PTR]], align 8 +; CHECK-NEXT: [[TMP0:%.*]] = bitcast float** [[PTR]] to i8** +; CHECK-NEXT: [[CALL:%.*]] = call i32 @posix_memalign(i8** noundef nonnull [[TMP0]], i64 noundef 8, i64 noundef 17) +; CHECK-NEXT: [[TOBOOL_NOT:%.*]] = icmp eq i32 [[CALL]], 0 +; CHECK-NEXT: br i1 [[TOBOOL_NOT]], label [[IF_END:%.*]], label [[IF_THEN:%.*]] +; CHECK: if.then: +; CHECK-NEXT: br label [[RETURN:%.*]] +; CHECK: if.end: +; CHECK-NEXT: br label [[RETURN]] +; CHECK: return: +; CHECK-NEXT: [[STOREMERGE:%.*]] = phi i64 [ 17, [[IF_END]] ], [ -2, [[IF_THEN]] ] +; CHECK-NEXT: ret i64 [[STOREMERGE]] +; +entry: + %retval = alloca i64 + %ptr = alloca float* + ; Make sure we handle this kind of idiomatic initialization. + store float* null, float** %ptr + %0 = bitcast float** %ptr to i8** + %call = call i32 @posix_memalign(i8** noundef %0, i64 noundef 8, i64 noundef 17) + %tobool = icmp ne i32 %call, 0 + br i1 %tobool, label %if.then, label %if.end + +if.then: + store i64 -2, i64* %retval + br label %return + +if.end: + %1 = load float*, float** %ptr + %2 = bitcast float* %1 to i8* + %3 = call i64 @llvm.objectsize.i64.p0i8(i8* %2, i1 false, i1 true, i1 false) + store i64 %3, i64* %retval + br label %return + +return: + %4 = load i64, i64* %retval + ret i64 %4 +} + +