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(BasicBlock *BB) const = 0; - /// Returns true if nounwind is known. - virtual bool isKnownNoUnwind() const = 0; + /// Returns true if nounwind is known. + virtual bool isKnownDead(BasicBlock *BB) 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 @@ -15,6 +15,7 @@ #include "llvm/Transforms/IPO/Attributor.h" +#include "llvm/ADT/STLExtras.h" #include "llvm/ADT/SetVector.h" #include "llvm/ADT/SmallPtrSet.h" #include "llvm/ADT/SmallVector.h" @@ -30,6 +31,7 @@ #include "llvm/Support/CommandLine.h" #include "llvm/Support/Debug.h" #include "llvm/Support/raw_ostream.h" +#include "llvm/Transforms/Utils/BasicBlockUtils.h" #include using namespace llvm; @@ -992,6 +994,152 @@ } }; +/// -------------------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(); + + ToBeExploredPaths.insert(&(F.getEntryBlock().front())); + for (size_t i = 0; i < ToBeExploredPaths.size(); ++i) + explorePath(A, ToBeExploredPaths[i]); + } + + /// True if path had no dead instructions. + bool explorePath(Attributor &A, Instruction *I); + + const std::string getAsStr() const override { + return getAssumed() ? "dead" : "maybe-dead"; + } + + /// See AbstractAttribute::manifest(...). + ChangeStatus manifest(Attributor &A) override { + assert(getState().isValidState() && + "Attempted to manifest an invalid state!"); + assert(getAssociatedValue() && + "Attempted to manifest an attribute without associated value!"); + + ChangeStatus HasChanged = ChangeStatus::UNCHANGED; + + for (Instruction *I : NoReturnCalls) { + auto *Unreachable = new UnreachableInst(I->getContext()); + BasicBlock *BB = I->getParent(); + SplitBlock(BB, I->getNextNode()); + ReplaceInstWithInst(BB->getTerminator(), Unreachable); + HasChanged = ChangeStatus::CHANGED; + } + + return HasChanged; + } + + /// See AbstractAttribute::updateImpl(...). + ChangeStatus updateImpl(Attributor &A) override; + + /// See AAIsDead::isAssumedDead(). + bool isAssumedDead(BasicBlock *BB) const override { + if (!getAssumed()) + return false; + if (AssumedLiveBlocks.count(BB)) + return false; + return true; + } + + /// See AAIsDead::isKnownDead(). + bool isKnownDead(BasicBlock *BB) const override { + if (!getKnown()) + return false; + if (getKnown() != getAssumed()) + return false; + if (AssumedLiveBlocks.count(BB)) + return false; + return true; + } + + /// Collection of to be explored paths. + SmallSetVector ToBeExploredPaths; + + /// 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; +}; + +bool AAIsDeadFunction::explorePath(Attributor &A, Instruction *I) { + BasicBlock *BB = I->getParent(); + + while (I) { + ImmutableCallSite ICS(I); + auto *NoReturnAA = A.getAAFor(*this, *I); + + if (ICS && ((NoReturnAA && (NoReturnAA->isAssumedNoReturn())) || + ICS.hasFnAttr(Attribute::NoReturn))) { + NoReturnCalls.insert(I); + return false; + } + + I = I->getNextNode(); + } + + // get new paths (reachable blocks). + bool HasNewPath = false; + for (BasicBlock *SuccBB : successors(BB)) { + Instruction *Inst = &(SuccBB->front()); + AssumedLiveBlocks.insert(SuccBB); + if (!ToBeExploredPaths.count(Inst)) { + ToBeExploredPaths.insert(Inst); + HasNewPath = true; + } + } + return HasNewPath; +} + +ChangeStatus AAIsDeadFunction::updateImpl(Attributor &A) { + Function &F = getAnchorScope(); + + for (auto *I : NoReturnCalls) { + size_t Size = ToBeExploredPaths.size(); + + // Still noreturn. + if (!explorePath(A, I)) + continue; + + // No new paths. + if (Size == ToBeExploredPaths.size()) + continue; + + while (Size != ToBeExploredPaths.size()) + explorePath(A, ToBeExploredPaths[Size++]); + } + + LLVM_DEBUG(dbgs() << "[AAIsDead] AssumedLiveBlocks: " + << AssumedLiveBlocks.size() + << "Total number of blocks: " << F.size() << "\n"); + + if (AssumedLiveBlocks.size() < F.size()) + return ChangeStatus::UNCHANGED; + + return ChangeStatus::CHANGED; +} + /// ---------------------------------------------------------------------------- /// Attributor /// ---------------------------------------------------------------------------- @@ -1134,6 +1282,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,59 @@ +; RUN: opt -attributor --attributor-disable=false -S < %s | FileCheck %s + +declare void @no_return_call() noreturn + +declare void @normal_call() + +declare i32 @foo() + +declare i32 @bar() + +; 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() + ; CHECK: unreachable + %call = call i32 @foo() + br label %cond.end + +cond.false: ; preds = %entry + call void @normal_call() + %call1 = call i32 @bar() + 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_dead(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() + ; CHECK: unreachable + %call = call i32 @foo() + br label %cond.end + +cond.false: ; preds = %entry + call void @no_return_call() + ; CHECK: unreachable + %call1 = call i32 @bar() + br label %cond.end + +cond.end: ; preds = %cond.false, %cond.true + %cond = phi i32 [ %call, %cond.true ], [ %call1, %cond.false ] + ret i32 %cond +}