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 @@ -871,26 +871,25 @@ Attribute::AttrKind(Attribute::EndAttrKinds + 1); /// Returns true if \p BB is assumed dead. - virtual bool isAssumedDead(BasicBlock *BB) const = 0; + virtual bool isAssumedDead(const BasicBlock *BB) const = 0; /// Returns true if \p BB is known dead. - virtual bool isKnownDead(BasicBlock *BB) const = 0; + virtual bool isKnownDead(const BasicBlock *BB) const = 0; /// Returns true if \p I is assumed dead. - virtual bool isAssumedDead(Instruction *I) const = 0; + virtual bool isAssumedDead(const Instruction *I) const = 0; /// Returns true if \p I is known dead. - virtual bool isKnownDead(Instruction *I) const = 0; + virtual bool isKnownDead(const Instruction *I) const = 0; /// This method is used to check if at least one instruction in a collection /// of instructions is live. template bool isLiveInstSet(T begin, T end) const { - for (T I = begin; I != end; ++I) { - assert(isa(*I) && "It has to be collection of Instructions"); - assert((*I)->getParent()->getParent() == &getAnchorScope() && + for (const auto &I : llvm::make_range(begin, end)) { + assert(I->getFunction() == &getAnchorScope() && "Instruction must be in the same anchor scope function."); - if (!isAssumedDead(*I)) + if (!isAssumedDead(I)) return true; } 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 @@ -605,7 +605,8 @@ /// Return an assumed unique return value if a single candidate is found. If /// there cannot be one, return a nullptr. If it is not clear yet, return the /// Optional::NoneType. - Optional getAssumedUniqueReturnValue(const AAIsDead *LivenessAA) const; + Optional + getAssumedUniqueReturnValue(const AAIsDead *LivenessAA) const; /// See AbstractState::checkForallReturnedValues(...). bool checkForallReturnedValues( @@ -678,7 +679,6 @@ std::function &)> Pred = [&](Value &RV, const SmallPtrSetImpl &RetInsts) -> bool { - // If all ReturnInsts are dead, then ReturnValue is dead as well // and can be ignored. if (LivenessAA && @@ -753,10 +753,6 @@ SmallPtrSet &ReturnInsts = It.second; Value *RV = It.first; - // Ignore dead ReturnValues. - if (LivenessAA && !LivenessAA->isLiveInstSet(ReturnInsts.begin(), ReturnInsts.end())) - continue; - LLVM_DEBUG(dbgs() << "[AAReturnedValues] Potentially returned value " << *RV << "\n"); @@ -770,6 +766,14 @@ // sites will be removed and we will fix the information for this state. HasCallSite = true; + // Ignore dead ReturnValues. + if (LivenessAA && + !LivenessAA->isLiveInstSet(ReturnInsts.begin(), ReturnInsts.end())) { + LLVM_DEBUG(dbgs() << "[AAReturnedValues] all returns are assumed dead, " + "skip it for now\n"); + continue; + } + // Try to find a assumed unique return value for the called function. auto *RetCSAA = A.getAAFor(*this, *RV); if (!RetCSAA) { @@ -1532,12 +1536,20 @@ ToBeExploredPaths.insert(&(F.getEntryBlock().front())); AssumedLiveBlocks.insert(&(F.getEntryBlock())); for (size_t i = 0; i < ToBeExploredPaths.size(); ++i) - explorePath(A, ToBeExploredPaths[i]); + if (const Instruction *NextNoReturnI = + findNextNoReturn(A, ToBeExploredPaths[i])) + NoReturnCalls.insert(NextNoReturnI); } - /// 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); + /// Find the next assumed noreturn instruction in the block of \p I starting + /// from, thus including, \p I. + /// + /// The caller is responsible to monitor the ToBeExploredPaths set as new + /// instructions discovered in other basic block will be placed in there. + /// + /// \returns The next assumed noreturn instructions in the block of \p I + /// starting from, thus including, \p I. + const Instruction *findNextNoReturn(Attributor &A, const Instruction *I); const std::string getAsStr() const override { return "LiveBBs(" + std::to_string(AssumedLiveBlocks.size()) + "/" + @@ -1551,18 +1563,31 @@ ChangeStatus HasChanged = ChangeStatus::UNCHANGED; - for (Instruction *I : NoReturnCalls) { + for (const Instruction *NRC : NoReturnCalls) { + Instruction *I = const_cast(NRC); BasicBlock *BB = I->getParent(); + Instruction *SplitPos = I->getNextNode(); - /// Invoke is replaced with a call and unreachable is placed after it. if (auto *II = dyn_cast(I)) { - changeToCall(II); - changeToUnreachable(BB->getTerminator(), /* UseLLVMTrap */ false); - LLVM_DEBUG(dbgs() << "[AAIsDead] Replaced invoke with call inst\n"); - continue; + /// Invoke is replaced with a call and unreachable is placed after it if + /// the callee is nounwind and noreturn. Otherwise, we keep the invoke + /// and only place an unreachable in the normal successor. + if (Function *Callee = II->getCalledFunction()) { + auto *AANoUnw = A.getAAFor(*this, *Callee); + if (Callee->hasFnAttribute(Attribute::NoUnwind) || + (AANoUnw && AANoUnw->isAssumedNoUnwind())) { + LLVM_DEBUG(dbgs() << "[AAIsDead] Replace invoke with call inst\n"); + changeToCall(II); + changeToUnreachable(BB->getTerminator(), /* UseLLVMTrap */ false); + continue; + } + } + + BB = II->getNormalDest(); + SplitPos = &BB->front(); } - SplitBlock(BB, I->getNextNode()); + SplitBlock(BB, SplitPos); changeToUnreachable(BB->getTerminator(), /* UseLLVMTrap */ false); HasChanged = ChangeStatus::CHANGED; } @@ -1574,7 +1599,7 @@ ChangeStatus updateImpl(Attributor &A) override; /// See AAIsDead::isAssumedDead(BasicBlock *). - bool isAssumedDead(BasicBlock *BB) const override { + bool isAssumedDead(const BasicBlock *BB) const override { assert(BB->getParent() == &getAnchorScope() && "BB must be in the same anchor scope function."); @@ -1584,16 +1609,16 @@ } /// See AAIsDead::isKnownDead(BasicBlock *). - bool isKnownDead(BasicBlock *BB) const override { + bool isKnownDead(const BasicBlock *BB) const override { return getKnown() && isAssumedDead(BB); } /// See AAIsDead::isAssumed(Instruction *I). - bool isAssumedDead(Instruction *I) const override { + bool isAssumedDead(const Instruction *I) const override { assert(I->getParent()->getParent() == &getAnchorScope() && "Instruction must be in the same anchor scope function."); - if(!getAssumed()) + if (!getAssumed()) return false; // If it is not in AssumedLiveBlocks then it for sure dead. @@ -1602,33 +1627,29 @@ return true; // If it is not after a noreturn call, than it is live. - if (!isAfterNoReturn(I)) - return false; - - // Definitely dead. - return true; + return isAfterNoReturn(I); } /// See AAIsDead::isKnownDead(Instruction *I). - bool isKnownDead(Instruction *I) const override { + bool isKnownDead(const Instruction *I) const override { return getKnown() && isAssumedDead(I); } /// Check if instruction is after noreturn call, in other words, assumed dead. - bool isAfterNoReturn(Instruction *I) const; + bool isAfterNoReturn(const Instruction *I) const; /// Collection of to be explored paths. - SmallSetVector ToBeExploredPaths; + SmallSetVector ToBeExploredPaths; /// Collection of all assumed live BasicBlocks. - DenseSet AssumedLiveBlocks; + DenseSet AssumedLiveBlocks; /// Collection of calls with noreturn attribute, assumed or knwon. - SmallSetVector NoReturnCalls; + SmallSetVector NoReturnCalls; }; -bool AAIsDeadFunction::isAfterNoReturn(Instruction *I) const { - Instruction *PrevI = I->getPrevNode(); +bool AAIsDeadFunction::isAfterNoReturn(const Instruction *I) const { + const Instruction *PrevI = I->getPrevNode(); while (PrevI) { if (NoReturnCalls.count(PrevI)) return true; @@ -1637,75 +1658,77 @@ return false; } -bool AAIsDeadFunction::explorePath(Attributor &A, Instruction *I) { - BasicBlock *BB = I->getParent(); +const Instruction *AAIsDeadFunction::findNextNoReturn(Attributor &A, + const Instruction *I) { + const BasicBlock *BB = I->getParent(); + + // TODO: We should have a function that determines if an "edge" is dead. + // Edges could be from an instruction to the next or from a terminator + // to the successor. For now, we need to special case the unwind block + // of InvokeInst below. while (I) { ImmutableCallSite ICS(I); if (ICS) { - auto *NoReturnAA = A.getAAFor(*this, *I); - - if (NoReturnAA && NoReturnAA->isAssumedNoReturn()) { - if (!NoReturnCalls.insert(I)) - // 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; + // Regarless of the no-return property of an invoke instruction we only + // learn that the regular successor is not reachable through this + // instruction but the unwind block might still be. + if (auto *Invoke = dyn_cast(I)) { + // Use nounwind to justify the unwind block is dead as well. + auto *AANoUnw = A.getAAFor(*this, *Invoke); + if (!AANoUnw || !AANoUnw->isAssumedNoUnwind()) { + AssumedLiveBlocks.insert(Invoke->getUnwindDest()); + ToBeExploredPaths.insert(&Invoke->getUnwindDest()->front()); + } } - if (ICS.hasFnAttr(Attribute::NoReturn)) { - if (!NoReturnCalls.insert(I)) - return false; - - return true; - } + auto *NoReturnAA = A.getAAFor(*this, *I); + if (ICS.hasFnAttr(Attribute::NoReturn) || + (NoReturnAA && NoReturnAA->isAssumedNoReturn())) + return I; } I = I->getNextNode(); } // get new paths (reachable blocks). - for (BasicBlock *SuccBB : successors(BB)) { - Instruction *Inst = &(SuccBB->front()); + for (const BasicBlock *SuccBB : successors(BB)) { AssumedLiveBlocks.insert(SuccBB); - ToBeExploredPaths.insert(Inst); + ToBeExploredPaths.insert(&SuccBB->front()); } - return true; + // No noreturn instruction found. + return nullptr; } ChangeStatus AAIsDeadFunction::updateImpl(Attributor &A) { // Temporary collection to iterate over existing noreturn instructions. This // will alow easier modification of NoReturnCalls collection - SmallVector NoReturnChanged; + SmallVector NoReturnChanged; ChangeStatus Status = ChangeStatus::UNCHANGED; - for (Instruction *I : NoReturnCalls) + for (const Instruction *I : NoReturnCalls) NoReturnChanged.push_back(I); - for (Instruction *I : NoReturnChanged) { + for (const Instruction *I : NoReturnChanged) { size_t Size = ToBeExploredPaths.size(); - // Still noreturn. - if (!explorePath(A, I)) - continue; - - NoReturnCalls.remove(I); - - // At least one new path. - Status = ChangeStatus::CHANGED; - - // No new paths. - if (Size == ToBeExploredPaths.size()) - continue; + const Instruction *NextNoReturnI = findNextNoReturn(A, I); + if (NextNoReturnI != I) { + Status = ChangeStatus::CHANGED; + NoReturnCalls.remove(I); + if (NextNoReturnI) + NoReturnCalls.insert(NextNoReturnI); + } - // explore new paths. - while (Size != ToBeExploredPaths.size()) - explorePath(A, ToBeExploredPaths[Size++]); + // Explore new paths. + while (Size != ToBeExploredPaths.size()) { + Status = ChangeStatus::CHANGED; + if (const Instruction *NextNoReturnI = + findNextNoReturn(A, ToBeExploredPaths[Size++])) + NoReturnCalls.insert(NextNoReturnI); + } } LLVM_DEBUG( diff --git a/llvm/test/Transforms/FunctionAttrs/liveness.ll b/llvm/test/Transforms/FunctionAttrs/liveness.ll --- a/llvm/test/Transforms/FunctionAttrs/liveness.ll +++ b/llvm/test/Transforms/FunctionAttrs/liveness.ll @@ -6,6 +6,8 @@ declare i32 @foo() +declare i32 @foo_noreturn_nounwind() noreturn nounwind + declare i32 @foo_noreturn() noreturn declare i32 @bar() nosync readnone @@ -134,8 +136,7 @@ ret i32 %cond } -; TEST 5 noreturn invoke instruction replaced by a call and an unreachable instruction -; put after it. +; TEST 5 noreturn invoke instruction with a unreachable normal successor block. ; CHECK: define i32 @invoke_noreturn(i32 %a) define i32 @invoke_noreturn(i32 %a) personality i8* bitcast (i32 (...)* @__gxx_personality_v0 to i8*) { @@ -147,8 +148,44 @@ call void @normal_call() %call = invoke i32 @foo_noreturn() to label %continue unwind label %cleanup - ; CHECK: call i32 @foo_noreturn() - ; CHECK-NEXT unreachable + ; CHECK: %call = invoke i32 @foo_noreturn() + ; CHECK-NEXT: to label %continue unwind label %cleanup + +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: + ; CHECK: continue: + ; CHECK-NEXT: unreachable + br label %cond.end + +cleanup: + %res = landingpad { i8*, i32 } + catch i8* null + ret i32 0 +} + +; TEST 4.1 noreturn invoke instruction replaced by a call and an unreachable instruction +; put after it. + +; CHECK: define i32 @invoke_noreturn_nounwind(i32 %a) +define i32 @invoke_noreturn_nounwind(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_nounwind() to label %continue + unwind label %cleanup + ; CHECK: call i32 @foo_noreturn_nounwind() + ; CHECK-NEXT: unreachable cond.false: ; preds = %entry call void @normal_call() @@ -171,7 +208,7 @@ ; TEST 6: Undefined behvior, taken from LangRef. ; FIXME: Should be able to detect undefined behavior. -; CHECK define @ub(i32) +; CHECK: define void @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.