diff --git a/llvm/include/llvm/Transforms/IPO/Attributor.h b/llvm/include/llvm/Transforms/IPO/Attributor.h --- a/llvm/include/llvm/Transforms/IPO/Attributor.h +++ b/llvm/include/llvm/Transforms/IPO/Attributor.h @@ -683,22 +683,44 @@ static constexpr Attribute::AttrKind ID = Attribute::NoAlias; }; +/// An abstract interface for all nosync attributes. struct AANoUnwind : public AbstractAttribute { - /// An abstract interface for all nosync attributes. - AANoUnwind(Value &V, InformationCache &InfoCache) - : AbstractAttribute(V, InfoCache) {} - /// See AbstractAttribute::getAttrKind()/ - virtual Attribute::AttrKind getAttrKind() const override { return ID; } + /// See AbstractAttribute::AbstractAttribute(...). + AANoUnwind(Value &V, InformationCache &InfoCache) + : AbstractAttribute(V, InfoCache) {} + + /// See AbstractAttribute::getAttrKind()/ + virtual Attribute::AttrKind getAttrKind() const override { return ID; } + + static constexpr Attribute::AttrKind ID = + Attribute::AttrKind(Attribute::NoUnwind); + + /// Returns true if nounwind is assumed. + virtual bool isAssumedNoUnwind() const = 0; + + /// Returns true if nounwind is known. + virtual bool isKnownNoUnwind() const = 0; +}; + +/// An abstract interface for liveness abstract attribute. +struct AAIsDead : public AbstractAttribute { + + /// See AbstractAttribute::AbstractAttribute(...). + AAIsDead(Value &V, InformationCache &InfoCache) + : AbstractAttribute(V, InfoCache) {} + + /// See AbstractAttribute::getAttrKind() + virtual Attribute::AttrKind getAttrKind() const override { return ID; } - static constexpr Attribute::AttrKind ID = - Attribute::AttrKind(Attribute::NoUnwind); + static constexpr Attribute::AttrKind ID = + Attribute::AttrKind(Attribute::EndAttrKinds + 1); - /// Returns true if nounwind is assumed. - virtual bool isAssumedNoUnwind() const = 0; + /// Returns true if nounwind is assumed. + virtual bool isAssumedDead() const = 0; - /// Returns true if nounwind is known. - virtual bool isKnownNoUnwind() const = 0; + /// Returns true if nounwind is known. + virtual bool isKnownDead() const = 0; }; } // end namespace llvm diff --git a/llvm/lib/Transforms/IPO/Attributor.cpp b/llvm/lib/Transforms/IPO/Attributor.cpp --- a/llvm/lib/Transforms/IPO/Attributor.cpp +++ b/llvm/lib/Transforms/IPO/Attributor.cpp @@ -992,6 +992,123 @@ } }; +/// -------------------AAIsDead Function Attribute----------------------- + +struct AAIsDeadFunction : AAIsDead, BooleanState { + + AAIsDeadFunction(Function &F, InformationCache &InfoCache) + : AAIsDead(F, InfoCache) {} + + /// See AbstractAttribute::getState() + /// { + AbstractState &getState() override { return *this; } + const AbstractState &getState() const override { return *this; } + /// } + + /// See AbstractAttribute::getManifestPosition(). + virtual ManifestPosition getManifestPosition() const override { + return MP_FUNCTION; + } + + void initialize(Attributor &A) override { + Function &F = getAnchorScope(); + + for (Instruction &I : instructions(&F)) { + ImmutableCallSite ICS(&I); + auto *NoReturnAA = A.getAAFor(*this, I); + + if (ICS && + (NoReturnAA || NoReturnAA->isAssumedNoReturn() || + NoReturnAA->isKnownNoReturn()) && + ICS.hasFnAttr(Attribute::NoReturn)) { + NoReturnCalls.insert(&I); + /// If the block contains a noreturn call, it is assumed dead. + AssumedDeadBlocks.insert(I.getParent()); + } + } + } + + virtual const std::string getAsStr() const override { + return getAssumed() ? "dead" : "maybe-dead"; + } + + /// See AbstractAttribute::updateImpl(...). + virtual ChangeStatus updateImpl(Attributor &A) override; + + /// See AAIsDead::isAssumedDead(). + virtual bool isAssumedDead() const override { return getAssumed(); } + + /// See AAIsDead::isKnownDead(). + virtual bool isKnownDead() const override { return getKnown(); } + + /// Collection of all assumed dead BasicBlocks. + DenseSet AssumedDeadBlocks; + + /// Collection of all assumed live BasicBlocks. + DenseSet AssumedLiveBlocks; + + /// Collection of calls with noreturn attribute, assumed or knwon. + DenseSet NoReturnCalls; +}; + +ChangeStatus AAIsDeadFunction::updateImpl(Attributor &A) { + Function &F = getAnchorScope(); + + for (auto *I : NoReturnCalls) { + ImmutableCallSite ICS(I); + auto *NoReturnAA = A.getAAFor(*this, *I); + + if (ICS && + (NoReturnAA || NoReturnAA->isAssumedNoReturn() || + NoReturnAA->isKnownNoReturn()) && + ICS.hasFnAttr(Attribute::NoReturn)) + continue; + + /// Check if we can assume this block to be live. + BasicBlock *BB = I->getParent(); + for (BasicBlock *PredBB : predecessors(BB)) { + /// If atleast one block is live, current block is also live. + if (AssumedDeadBlocks.find(PredBB) != AssumedDeadBlocks.end()) { + AssumedDeadBlocks.erase(BB); + AssumedLiveBlocks.insert(BB); + } + } + } + + auto &OpcodeInstMap = InfoCache.getOpcodeInstMapForFunction(F); + auto Opcodes = {(unsigned)Instruction::Invoke, (unsigned)Instruction::Call, + (unsigned)Instruction::CallBr}; + + /// Check if some other calls became noreturn in the mean time. + for (unsigned Opcode : Opcodes) { + for (Instruction *I : OpcodeInstMap[Opcode]) { + if (NoReturnCalls.find(I) != NoReturnCalls.end()) + continue; + + ImmutableCallSite ICS(I); + auto *NoReturnAA = A.getAAFor(*this, *I); + + if (ICS && + (!NoReturnAA || !NoReturnAA->isAssumedNoReturn() || + !NoReturnAA->isKnownNoReturn()) && + !ICS.hasFnAttr(Attribute::NoReturn)) + continue; + + /// Check if we can assume this block to be live. + BasicBlock *BB = I->getParent(); + for (BasicBlock *PredBB : predecessors(BB)) { + /// If atleast one block is live, current block is also live. + if (AssumedDeadBlocks.find(PredBB) != AssumedDeadBlocks.end()) { + AssumedDeadBlocks.erase(BB); + AssumedLiveBlocks.insert(BB); + } + } + } + } + + return ChangeStatus::UNCHANGED; +} + /// ---------------------------------------------------------------------------- /// Attributor /// ---------------------------------------------------------------------------- @@ -1134,6 +1251,9 @@ Function &F, InformationCache &InfoCache, DenseSet *Whitelist) { + // Check for dead BasicBlocks in every function. + registerAA(*new AAIsDeadFunction(F, InfoCache)); + // Return attributes are only appropriate if the return type is non void. Type *ReturnType = F.getReturnType(); if (!ReturnType->isVoidTy()) { diff --git a/llvm/test/Transforms/FunctionAttrs/liveness.ll b/llvm/test/Transforms/FunctionAttrs/liveness.ll new file mode 100644 --- /dev/null +++ b/llvm/test/Transforms/FunctionAttrs/liveness.ll @@ -0,0 +1,52 @@ +; RUN: opt -attributor --attributor-disable=false -S < %s | FileCheck %s + +declare void @no_return_call() noreturn + +declare void @normal_call() + +; TEST 1: cond.true is dead, but cond.end is not, since cond.false is live + +; This is just an example. For example we can put a sync call in a +; dead block and check if it is deduced. + +define i32 @dead_block_present(i32 %a) #0 { +entry: + %cmp = icmp eq i32 %a, 0 + br i1 %cmp, label %cond.true, label %cond.false + +cond.true: ; preds = %entry + call void @no_return_call() + %call = call i32 @endless_loop(i32 %a) + br label %cond.end + +cond.false: ; preds = %entry + call void @normal_call() + %call1 = call i32 @srec16(i32 %a) + br label %cond.end + +cond.end: ; preds = %cond.false, %cond.true + %cond = phi i32 [ %call, %cond.true ], [ %call1, %cond.false ] + ret i32 %cond +} + +; TEST 2: both cond.true and cond.false are dead, therfore cond.end is dead as well. + +define i32 @all_live(i32 %a) #0 { +entry: + %cmp = icmp eq i32 %a, 0 + br i1 %cmp, label %cond.true, label %cond.false + +cond.true: ; preds = %entry + call void @no_return_call() + %call = call i32 @endless_loop(i32 %a) + br label %cond.end + +cond.false: ; preds = %entry + call void @no_return_call() + %call1 = call i32 @srec16(i32 %a) + br label %cond.end + +cond.end: ; preds = %cond.false, %cond.true + %cond = phi i32 [ %call, %cond.true ], [ %call1, %cond.false ] + ret i32 %cond +}