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,164 @@ } }; +/// -------------------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())); + AssumedLiveBlocks.insert(&(F.getEntryBlock())); + 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 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) { + if (NoReturnAA && NoReturnAA->isAssumedNoReturn()) { + NoReturnCalls.insert(I); + return false; + } + + if (ICS.hasFnAttr(Attribute::NoReturn)) { + NoReturnCalls.insert(I); + return false; + } + } + + I = I->getNextNode(); + } + + // get new paths (reachable blocks). + for (BasicBlock *SuccBB : successors(BB)) { + Instruction *Inst = &(SuccBB->front()); + AssumedLiveBlocks.insert(SuccBB); + ToBeExploredPaths.insert(Inst); + } + + return true;; +} + +ChangeStatus AAIsDeadFunction::updateImpl(Attributor &A) { + Function &F = getAnchorScope(); + + // Temporary collection to iterate over existing noreturn instructions. This + // will alow easier modification of NoReturnCalls collection + SmallVector NoReturnChanged; + ChangeStatus Status = ChangeStatus::UNCHANGED; + + for (Instruction *I : NoReturnCalls) + NoReturnChanged.push_back(I); + + for (Instruction *I : NoReturnChanged) { + size_t Size = ToBeExploredPaths.size(); + + // Still noreturn. + if (!explorePath(A, I)) + continue; + + NoReturnCalls.erase(I); + + // No new paths. + if (Size == ToBeExploredPaths.size()) + continue; + + // At least one new path. + Status = ChangeStatus::CHANGED; + + // explore new paths. + while (Size != ToBeExploredPaths.size()) + explorePath(A, ToBeExploredPaths[Size++]); + } + + LLVM_DEBUG(dbgs() << "[AAIsDead] AssumedLiveBlocks: " + << AssumedLiveBlocks.size() + << "Total number of blocks: " << F.size() << "\n"); + + return Status; +} + /// ---------------------------------------------------------------------------- /// Attributor /// ---------------------------------------------------------------------------- @@ -1134,6 +1294,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,208 @@ +; 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 +} + +; TEST 3: All blocks are live. + +; CHECK: define i32 @all_live(i32 %a) +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 @normal_call() + %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 4: Undefined behvior, taken from LangRef. +; FIXME: Should be able to detect undefined behavior. + +; CHECK define @ub(i32) +define void @ub(i32* ) { + %poison = sub nuw i32 0, 1 ; Results in a poison value. + %still_poison = and i32 %poison, 0 ; 0, but also poison. + %poison_yet_again = getelementptr i32, i32* %0, i32 %still_poison + store i32 0, i32* %poison_yet_again ; Undefined behavior due to store to poison. + ret void +} + +define void @inf_loop() #0 { +entry: + br label %while.body + +while.body: ; preds = %entry, %while.body + br label %while.body +} + +; TEST 5: Infinite loop. +; FIXME: Detect infloops, and mark affected blocks dead. + +define i32 @test5(i32, i32) #0 { + %3 = icmp sgt i32 %0, %1 + br i1 %3, label %cond.if, label %cond.elseif + +cond.if: ; preds = %2 + %4 = tail call i32 @bar() + br label %cond.end + +cond.elseif: ; preds = %2 + call void @inf_loop() + %5 = icmp slt i32 %0, %1 + br i1 %5, label %cond.end, label %cond.else + +cond.else: ; preds = %cond.elseif + %6 = tail call i32 @foo() + br label %cond.end + +cond.end: ; preds = %cond.if, %cond.else, %cond.elseif + %7 = phi i32 [ %1, %cond.elseif ], [ 0, %cond.else ], [ 0, %cond.if ] + ret i32 %7 +} + +define void @rec() #0 { +entry: + call void @rec() + ret void +} + +; TEST 6: Recursion +; FIXME: everything after first block should be marked dead +; and unreachable should be put after call to @rec(). + +define i32 @test6(i32, i32) #0 { + call void @rec() + %3 = icmp sgt i32 %0, %1 + br i1 %3, label %cond.if, label %cond.elseif + +cond.if: ; preds = %2 + %4 = tail call i32 @bar() + br label %cond.end + +cond.elseif: ; preds = %2 + call void @rec() + %5 = icmp slt i32 %0, %1 + br i1 %5, label %cond.end, label %cond.else + +cond.else: ; preds = %cond.elseif + %6 = tail call i32 @foo() + br label %cond.end + +cond.end: ; preds = %cond.if, %cond.else, %cond.elseif + %7 = phi i32 [ %1, %cond.elseif ], [ 0, %cond.else ], [ 0, %cond.if ] + ret i32 %7 +} +; TEST 7: Recursion +; FIXME: contains recursive call to itself in cond.elseif block + +define i32 @test7(i32, i32) #0 { + %3 = icmp sgt i32 %0, %1 + br i1 %3, label %cond.if, label %cond.elseif + +cond.if: ; preds = %2 + %4 = tail call i32 @bar() + br label %cond.end + +cond.elseif: ; preds = %2 + %5 = tail call i32 @test7(i32 %0, i32 %1) + %6 = icmp slt i32 %0, %1 + br i1 %6, label %cond.end, label %cond.else + +cond.else: ; preds = %cond.elseif + %7 = tail call i32 @foo() + br label %cond.end + +cond.end: ; preds = %cond.if, %cond.else, %cond.elseif + %8 = phi i32 [ %1, %cond.elseif ], [ 0, %cond.else ], [ 0, %cond.if ] + ret i32 %8 +} + +; TEST 8: Only first block is live. + +define i32 @first_block_no_return(i32 %a) #0 { +entry: + call void @no_return_call() + %cmp = icmp eq i32 %a, 0 + br i1 %cmp, label %cond.true, label %cond.false + +cond.true: ; preds = %entry + call void @normal_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 +}