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 @@ -784,6 +784,47 @@ /// The identifier used by the Attributor for this class of attributes. static constexpr Attribute::AttrKind ID = Attribute::WillReturn; }; + +/// An AbstractAttribute for noreturn. +struct AANoReturn : public AbstractAttribute, BooleanState { + + /// See AbstractAttribute::AbstractAttribute(...). + AANoReturn(Value &V, InformationCache &InfoCache) + : AbstractAttribute(V, InfoCache) {} + + /// Return true if the underlying object is known to never return. + virtual bool isKnownNoReturn() const = 0; + + /// Return true if the underlying object is assumed to never return. + virtual bool isAssumedNoReturn() const = 0; + + /// See AbstractAttribute::getAttrKind() + Attribute::AttrKind getAttrKind() const override { return ID; } + + /// The identifier used by the Attributor for this class of attributes. + static constexpr Attribute::AttrKind ID = Attribute::NoReturn; +}; + +/// 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() + Attribute::AttrKind getAttrKind() const override { return ID; } + + static constexpr Attribute::AttrKind ID = + Attribute::AttrKind(Attribute::EndAttrKinds + 1); + + /// Returns true if \p BB is assumed dead. + virtual bool isAssumedDead(BasicBlock *BB) const = 0; + + /// Returns true if \p BB is known dead. + virtual bool isKnownDead(BasicBlock *BB) const = 0; +}; + } // end namespace llvm #endif // LLVM_TRANSFORMS_IPO_FUNCTIONATTRS_H 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 @@ -16,6 +16,7 @@ #include "llvm/Transforms/IPO/Attributor.h" #include "llvm/ADT/DepthFirstIterator.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; @@ -1311,6 +1313,182 @@ return ChangeStatus::UNCHANGED; } +/// -------------------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(). + 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]); + } + + /// Explores new instructions starting from \p I. If instruction is dead, stop + /// and return true if it discovered a new instruction. + bool explorePath(Attributor &A, Instruction *I); + + const std::string getAsStr() const override { + return "LiveBBs(" + std::to_string(AssumedLiveBlocks.size()) + "/" + + std::to_string(getAnchorScope().size()) + ")"; + } + + /// See AbstractAttribute::manifest(...). + ChangeStatus manifest(Attributor &A) override { + assert(getState().isValidState() && + "Attempted to manifest an invalid state!"); + + ChangeStatus HasChanged = ChangeStatus::UNCHANGED; + + for (Instruction *I : NoReturnCalls) { + auto *Unreachable = new UnreachableInst(I->getContext()); + + /// Invoke is replaced with a call and unreachable is placed after it. + if (auto *II = dyn_cast(I)) { + Function *F = II->getCalledFunction(); + CallInst *CI = CallInst::Create(F->getFunctionType(), F); + ReplaceInstWithInst(II, CI); + CI->getParent()->getInstList().push_back(Unreachable); + LLVM_DEBUG(dbgs() << "[AAIsDead] Replaced invoke with call inst\n"); + continue; + } + + 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; + return !AssumedLiveBlocks.count(BB); + // if (AssumedLiveBlocks.count(BB)) + // return false; + // return true; + } + + /// See AAIsDead::isKnownDead(). + bool isKnownDead(BasicBlock *BB) const override { + if (!getKnown()) + return false; + return !AssumedLiveBlocks.count(BB); + // 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); + + if (ICS) { + auto *NoReturnAA = A.getAAFor(*this, *I); + + if (NoReturnAA && NoReturnAA->isAssumedNoReturn()) { + if (!NoReturnCalls.insert(I).second) + // If I is already in the NoReturnCalls set, then it stayed noreturn + // and we didn't discover any new instructions. + return false; + + // Discovered new noreturn call, return true to indicate that I is not + // noreturn anymore and should be deleted from NoReturnCalls. + return true; + } + + if (ICS.hasFnAttr(Attribute::NoReturn)) { + if(!NoReturnCalls.insert(I).second) + return false; + + return true; + } + } + + 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 /// ---------------------------------------------------------------------------- @@ -1522,6 +1700,9 @@ // Every function might be "will-return". registerAA(*new AAWillReturnFunction(F, InfoCache)); + // Check for dead BasicBlocks in every function. + registerAA(*new AAIsDeadFunction(F, InfoCache)); + // Walk all instructions to find more attribute opportunities and also // interesting instructions that might be queried by abstract attributes // during their initialization or update. 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,250 @@ +; 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 @foo_noreturn() noreturn + +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: call void @no_return_call() + ; CHECK-NEXT: 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: call void @no_return_call() + ; CHECK-NEXT: unreachable + %call = call i32 @foo() + br label %cond.end + +cond.false: ; preds = %entry + call void @no_return_call() + ; CHECK: call void @no_return_call() + ; CHECK-NEXT: 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 +} + +declare i32 @__gxx_personality_v0(...) + +; 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_noreturn() + 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 noreturn invoke instruction replaced by a call and an unreachable instruction +; put after it. + +; CHECK: define i32 @invoke_noreturn(i32 %a) +define i32 @invoke_noreturn(i32 %a) personality i8* bitcast (i32 (...)* @__gxx_personality_v0 to i8*) { +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 = invoke i32 @foo_noreturn() to label %continue + unwind label %cleanup + ; CHECK: call i32 @foo_noreturn() + ; CHECK-NEXT unreachable + +cond.false: ; preds = %entry + call void @normal_call() + %call1 = call i32 @bar() + br label %cond.end + +cond.end: ; preds = %cond.false, %continue + %cond = phi i32 [ %call, %continue ], [ %call1, %cond.false ] + ret i32 %cond + +continue: + br label %cond.end + +cleanup: + %res = landingpad { i8*, i32 } + catch i8* null + ret i32 0 +} + +; TEST 5: 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 6: 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 7: 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 8: 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 9: Only first block is live. + +define i32 @first_block_no_return(i32 %a) #0 { +entry: + call void @no_return_call() + ; CHECK: call void @no_return_call() + ; CHECK-NEXT: unreachable + %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 +}