Index: llvm/include/llvm/Analysis/MemoryBuiltins.h =================================================================== --- llvm/include/llvm/Analysis/MemoryBuiltins.h +++ 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; @@ -229,6 +233,9 @@ SizeOffsetType visitInstruction(Instruction &I); private: + SizeOffsetType findLoadSizeOffset(LoadInst &LoadFrom, BasicBlock &BB, + BasicBlock::iterator From, + SmallPtrSetImpl &Visited); SizeOffsetType combineSizeOffset(SizeOffsetType LHS, SizeOffsetType RHS); SizeOffsetType computeImpl(Value *V); bool CheckedZextOrTrunc(APInt &I); Index: llvm/lib/Analysis/MemoryBuiltins.cpp =================================================================== --- llvm/lib/Analysis/MemoryBuiltins.cpp +++ 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,107 @@ return unknown(); } -SizeOffsetType ObjectSizeOffsetVisitor::visitLoadInst(LoadInst&) { - ++ObjectVisitorLoad; - return unknown(); +SizeOffsetType ObjectSizeOffsetVisitor::findLoadSizeOffset( + LoadInst &Load, BasicBlock &BB, BasicBlock::iterator From, + SmallPtrSetImpl &Visited) { + if (!Visited.insert(&BB).second) + return unknown(); + + auto Unknown = [this]() { + ++ObjectVisitorLoad; + return unknown(); + }; + + do { + Instruction &I = *From; + if (!I.mayWriteToMemory()) + continue; + + if (auto *SI = dyn_cast(&I)) { + // Minimal work if we don't have alias analysis. + if (!Options.AA) { + if (SI->getOperand(1) == Load.getOperand(0)) + return compute(SI->getOperand(0)); + else + return Unknown(); + } + AliasResult AR = Options.AA->alias(SI->getOperand(1), &Load); + switch ((AliasResult::Kind)AR) { + case AliasResult::NoAlias: + continue; + case AliasResult::MustAlias: + return compute(SI->getOperand(0)); + default: + return Unknown(); + } + } + + if (auto *CB = dyn_cast(&I)) { + Function *Callee = CB->getCalledFunction(); + // Bail out on indirect call. + if (!Callee) + return Unknown(); + + // posix_memalign case. It assumes that posix_memalign doesn't fail :-/ + LibFunc TLIFn; + if (!TLI || !TLI->getLibFunc(*CB->getCalledFunction(), TLIFn) || + !TLI->has(TLIFn)) + return Unknown(); + + if (TLIFn != LibFunc_posix_memalign) + // TODO: There's probably more interesting case to support here. + return Unknown(); + + // Without aliasing information, modifying a pointer may modify the one + // we're loading from. + if (!Options.AA) { + if (CB->getOperand(0) != Load.getOperand(0)) + return Unknown(); + } else { + // Thanks to aliasing information we can be a lot more precise. + AliasResult AR = + Options.AA->alias(CB->getOperand(0), Load.getOperand(0)); + switch ((AliasResult::Kind)AR) { + case AliasResult::NoAlias: + continue; + case AliasResult::MustAlias: + break; + default: + return Unknown(); + } + } + + Value *Size = CB->getOperand(2); + auto *C = dyn_cast(Size); + if (!C) + return unknown(); + + return {C->getValue(), APInt(C->getValue().getBitWidth(), 0)}; + } + + return Unknown(); + } while (From-- != BB.begin()); + + SmallVector PredecessorSizeOffsets; + for (auto *PredBB : predecessors(&BB)) + PredecessorSizeOffsets.push_back(findLoadSizeOffset( + Load, *PredBB, BasicBlock::iterator(PredBB->getTerminator()), Visited)); + + if (PredecessorSizeOffsets.empty()) + return Unknown(); + + return std::accumulate(PredecessorSizeOffsets.begin() + 1, + PredecessorSizeOffsets.end(), + PredecessorSizeOffsets.front(), + [this](SizeOffsetType LHS, SizeOffsetType RHS) { + return combineSizeOffset(LHS, RHS); + }); +} + +SizeOffsetType ObjectSizeOffsetVisitor::visitLoadInst(LoadInst &LI) { + SmallPtrSet Visited; + return findLoadSizeOffset(LI, *LI.getParent(), BasicBlock::iterator(LI), + Visited); } SizeOffsetType ObjectSizeOffsetVisitor::combineSizeOffset(SizeOffsetType LHS, @@ -1017,7 +1126,7 @@ return unknown(); } -SizeOffsetEvalType ObjectSizeOffsetEvaluator::visitLoadInst(LoadInst&) { +SizeOffsetEvalType ObjectSizeOffsetEvaluator::visitLoadInst(LoadInst &LI) { return unknown(); } Index: llvm/lib/Transforms/InstCombine/InstCombineCalls.cpp =================================================================== --- llvm/lib/Transforms/InstCombine/InstCombineCalls.cpp +++ 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: { Index: llvm/lib/Transforms/InstCombine/InstructionCombining.cpp =================================================================== --- llvm/lib/Transforms/InstCombine/InstructionCombining.cpp +++ 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. Index: llvm/test/Transforms/InstCombine/builtin-object-size-posix-memalign.ll =================================================================== --- /dev/null +++ llvm/test/Transforms/InstCombine/builtin-object-size-posix-memalign.ll @@ -0,0 +1,120 @@ +; 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 +} + +define dso_local i64 @check_posix_memalign_arg(i8** noalias noundef %obj) { +; CHECK-LABEL: @check_posix_memalign_arg( +; CHECK-NEXT: entry: +; CHECK-NEXT: [[CALL:%.*]] = call i32 @posix_memalign(i8** noundef [[OBJ:%.*]], i64 noundef 8, i64 noundef 10) +; CHECK-NEXT: [[TOBOOL_NOT:%.*]] = icmp eq i32 [[CALL]], 0 +; CHECK-NEXT: br i1 [[TOBOOL_NOT]], label [[COND_FALSE:%.*]], label [[EXIT:%.*]] +; CHECK: cond.false: +; CHECK-NEXT: br label [[EXIT]] +; CHECK: exit: +; CHECK-NEXT: [[COND:%.*]] = phi i64 [ -2, [[ENTRY:%.*]] ], [ 10, [[COND_FALSE]] ] +; CHECK-NEXT: ret i64 [[COND]] +; +entry: + %call = call i32 @posix_memalign(i8** noundef %obj, i64 noundef 8, i64 noundef 10) + %tobool = icmp ne i32 %call, 0 + br i1 %tobool, label %exit, label %cond.false + +cond.false: + %val = load i8*, i8** %obj + %objsize = call i64 @llvm.objectsize.i64.p0i8(i8* %val, i1 false, i1 true, i1 false) + br label %exit + +exit: + %cond = phi i64 [ -2, %entry ], [ %objsize, %cond.false ] + ret i64 %cond + +} + Index: llvm/test/Transforms/LowerConstantIntrinsics/builtin-object-size-load.ll =================================================================== --- /dev/null +++ llvm/test/Transforms/LowerConstantIntrinsics/builtin-object-size-load.ll @@ -0,0 +1,46 @@ +; NOTE: Assertions have been autogenerated by utils/update_test_checks.py +; RUN: opt -lower-constant-intrinsics -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 i64 @llvm.objectsize.i64.p0i8(i8*, i1 immarg, i1 immarg, i1 immarg) + + +define dso_local i64 @check_store_load(i1 %cond) local_unnamed_addr { +; CHECK-LABEL: @check_store_load( +; CHECK-NEXT: entry: +; CHECK-NEXT: [[HOLDER:%.*]] = alloca i8*, align 8 +; CHECK-NEXT: [[PTR0:%.*]] = alloca i8, i64 10, align 1 +; CHECK-NEXT: br i1 [[COND:%.*]], label [[IF_THEN:%.*]], label [[IF_END:%.*]] +; CHECK: if.then: +; CHECK-NEXT: store i8* [[PTR0]], i8** [[HOLDER]], align 8 +; CHECK-NEXT: br label [[RETURN:%.*]] +; CHECK: if.end: +; CHECK-NEXT: [[PTR1:%.*]] = alloca i8, i64 12, align 1 +; CHECK-NEXT: store i8* [[PTR1]], i8** [[HOLDER]], align 8 +; CHECK-NEXT: br label [[RETURN]] +; CHECK: return: +; CHECK-NEXT: [[HELD:%.*]] = load i8*, i8** [[HOLDER]], align 8 +; CHECK-NEXT: ret i64 12 +; +entry: + %holder = alloca i8* + %ptr0 = alloca i8, i64 10 + br i1 %cond, label %if.then, label %if.end + +if.then: + store i8* %ptr0, i8** %holder + br label %return + +if.end: + %ptr1 = alloca i8, i64 12 + store i8* %ptr1, i8** %holder + br label %return + +return: + %held = load i8*, i8** %holder + %objsize = call i64 @llvm.objectsize.i64.p0i8(i8* %held, i1 false, i1 true, i1 false) + ret i64 %objsize + +}