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,189 @@ } }; +/// -------------------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.push_back(&(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()); + // Unreachable->insertAfter(I); + 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 (AssumedDeadBlocks.find(BB) != AssumedDeadBlocks.end()) + return true; + return false; + } + + /// See AAIsDead::isKnownDead(). + bool isKnownDead(BasicBlock *BB) const override { + if (!getKnown()) + return false; + if (getKnown() != getAssumed()) + return false; + if (AssumedDeadBlocks.find(BB) != AssumedDeadBlocks.end()) + return true; + return false; + } + + /// Map of to be explored paths. + SmallVector 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(); + + for (Instruction &Inst : *BB) { + ImmutableCallSite ICS(&Inst); + auto *NoReturnAA = A.getAAFor(*this, Inst); + + if (ICS) { + if ((NoReturnAA && (NoReturnAA->isAssumedNoReturn() || + NoReturnAA->isKnownNoReturn())) || + ICS.hasFnAttr(Attribute::NoReturn)) { + NoReturnCalls.insert(&Inst); + return false; + } + } + } + + // get new paths (reachable blocks). + Instruction *Terminator = BB->getTerminator(); + unsigned NumSucc = Terminator->getNumSuccessors(); + + for (unsigned i = 0; i < NumSucc; ++i) { + Instruction *Inst = &(Terminator->getSuccessor(i)->front()); + AssumedLiveBlocks.insert(Terminator->getSuccessor(i)); + if (!is_contained(ToBeExploredPaths, Inst)) + ToBeExploredPaths.push_back(Inst); + } + return true; +} + +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()) == 0) + continue; + + while(Size != ToBeExploredPaths.size()) + explorePath(A, ToBeExploredPaths[Size++]); + } + + // Remember DeadBlocks. + for (BasicBlock &BB : F) + if (AssumedLiveBlocks.find(&BB) == AssumedLiveBlocks.end()) + // If it is not in live set, then it is dead. + AssumedDeadBlocks.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); + } + } + } + } + + if (AssumedDeadBlocks.size() != 0) { + indicateOptimisticFixpoint(); + return ChangeStatus::CHANGED; + } + + return ChangeStatus::UNCHANGED; +} + /// ---------------------------------------------------------------------------- /// Attributor /// ---------------------------------------------------------------------------- @@ -1134,6 +1319,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 +}