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 @@ -23,6 +23,7 @@ #include "llvm/Analysis/GlobalsModRef.h" #include "llvm/IR/Argument.h" #include "llvm/IR/Attributes.h" +#include "llvm/IR/CFG.h" #include "llvm/IR/InstIterator.h" #include "llvm/Support/CommandLine.h" #include "llvm/Support/Debug.h" @@ -49,6 +50,8 @@ STATISTIC(NumFnArgumentReturned, "Number of function arguments marked returned"); +STATISTIC(NumFnNoReturn, "Number of functions marked noreturn"); + // TODO: Determine a good default value. // // In the LLVM-TS and SPEC2006, 32 seems to not induce compile time overheads @@ -176,6 +179,9 @@ case Attribute::Returned: NumFnArgumentReturned++; return; + case Attribute::NoReturn: + NumFnNoReturn++; + return; default: return; } @@ -689,6 +695,150 @@ return Changed; } +/// ------------------ Function No-Return Attribute ---------------------------- + +struct AANoReturn : public AbstractAttribute, BooleanState { + + AANoReturn(Value &V) : AbstractAttribute(V) {} + + /// Return true if the underlying object is known to never return. + bool isKnownNoReturn() const { return getKnown(); } + + /// Return true if the underlying object is assumed to never return. + bool isAssumedNoReturn() const { return getAssumed(); } + + /// See AbstractAttribute::getState(...). + virtual AbstractState &getState() override { return *this; } + + /// See AbstractAttribute::getState(...). + virtual const AbstractState &getState() const override { return *this; } + + /// See AbstractAttribute::getAsStr() + virtual const std::string getAsStr() const override { + return getAssumed() ? "no-return" : "may-return"; + } + + /// See AbstractAttribute::getAttrKind() + virtual 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; +}; + +struct AANoReturnFunction final : public AANoReturn { + + AANoReturnFunction(Function &F) : AANoReturn(F) {} + + /// See AbstractAttribute::initialize(...). + void initialize(Attributor &A) override { + Function &F = getAssociatedFunction(); + if (F.hasFnAttribute(getAttrKind())) + indicateFixpoint(/* Optimistic */ true); + } + + /// Return the associated function. + Function &getAssociatedFunction() { + return cast(getAnchoredValue()); + } + + /// Helper function that checks if we assume \p I to be dead. + bool isDeadInst(Attributor &A, const Instruction *I, bool &WasKnown) { + // TODO: This should probably live somewhere else. + + const BasicBlock *BB = I->getParent(); + if (BB != &BB->getParent()->getEntryBlock() && + pred_begin(BB) == pred_end(BB)) + return true; + + // Check if we assume no-return for any "previous" instruction. + while ((I = I->getPrevNode())) { + const AANoReturn *PrevInstNoReturnAA = A.getAAFor(*this, *I); + if (!PrevInstNoReturnAA || + !PrevInstNoReturnAA->getState().isValidState() || + !PrevInstNoReturnAA->isAssumedNoReturn()) + continue; + + WasKnown &= PrevInstNoReturnAA->isKnownNoReturn(); + return true; + } + + return false; + } + + /// Helper function that checks if we can justify no-return given a + /// returned value and the return instructions it can be returned through. + bool isValidReturnValue(Attributor &A, const Value *ReturnValue, + const SmallPtrSet &ReturnInsts, + bool &WasKnown) { + + if (std::all_of( + ReturnInsts.begin(), ReturnInsts.end(), + [&](const ReturnInst *RI) { return isDeadInst(A, RI, WasKnown); })) + return true; + + ImmutableCallSite ICS(ReturnValue); + if (ICS && ICS.getCalledFunction()) + if (ICS.getCalledFunction()->hasFnAttribute(Attribute::NoReturn)) + return true; + + // Check if we assume no-return for the return value. + const AANoReturn *ReturnValueNoReturnAA = + A.getAAFor(*this, *ReturnValue); + if (!ReturnValueNoReturnAA || + !ReturnValueNoReturnAA->getState().isValidState() || + !ReturnValueNoReturnAA->isAssumedNoReturn()) + return false; + + WasKnown &= ReturnValueNoReturnAA->isKnownNoReturn(); + return true; + } + + /// See AbstractAttribute::updateImpl(Attributor &A). + virtual ChangeStatus updateImpl(Attributor &A) override { + Function &F = getAssociatedFunction(); + + // Flag to decide if we are at a fixpoint already. + bool EverythingWasKnown = true; + + // Use the set of returned values to justify no-return. + const AAReturnedValuesImpl *RVAA = + A.getAAFor(*this, F); + if (RVAA && RVAA->getState().isValidState()) { + + auto IsValidReturnValue = + [&](AAReturnedValuesImpl::const_iterator::value_type &It) { + return isValidReturnValue(A, It.first, It.second, + EverythingWasKnown); + }; + if (std::all_of(RVAA->begin(), RVAA->end(), IsValidReturnValue)) { + if (EverythingWasKnown && RVAA->getState().isAtFixpoint()) + indicateFixpoint(/* Optimistic */ true); + return ChangeStatus::UNCHANGED; + } + } else { + auto &OpcodeInstMap = A.getOpcodeInstMapForFunction(F); + auto &ReturnInsts = OpcodeInstMap[Instruction::Ret]; + if (std::all_of(ReturnInsts.begin(), ReturnInsts.end(), + [&](const Instruction *RI) { + return isDeadInst(A, RI, EverythingWasKnown); + })) { + if (EverythingWasKnown) + indicateFixpoint(/* Optimistic */ true); + return ChangeStatus::UNCHANGED; + } + } + + // Fallthrough if we failed to keep the no-capture state. + indicateFixpoint(/* Optimistic */ false); + return ChangeStatus::CHANGED; + } + + /// See AbstractAttribute::getManifestPosition(). + virtual ManifestPosition getManifestPosition() const override { + return MP_FUNCTION; + } +}; + /// ---------------------------------------------------------------------------- /// Attributor /// ---------------------------------------------------------------------------- @@ -878,6 +1028,9 @@ registerAA(*new AAReturnedValuesImpl(F)); } + // Every function might be "no-return". + registerAA(*new AANoReturnFunction(F)); + // Walk all instructions to find more attribute opportunities and also // interesting instructions that might be querried by abstract attributes // during their initialziation or update. diff --git a/llvm/test/Transforms/FunctionAttrs/arg_nocapture.ll b/llvm/test/Transforms/FunctionAttrs/arg_nocapture.ll --- a/llvm/test/Transforms/FunctionAttrs/arg_nocapture.ll +++ b/llvm/test/Transforms/FunctionAttrs/arg_nocapture.ll @@ -102,8 +102,7 @@ ; ; Other arguments are possible here due to the no-return behavior. ; -; FIXME: no-return missing -; CHECK: define dso_local noalias nonnull i32* @srec16(i32* nocapture readnone %a) [[NoInlineNoUnwindReadnoneUwtable:#[0-9]*]] +; CHECK: define dso_local noalias nonnull i32* @srec16(i32* nocapture readnone %a) [[NoInlineNoReturnNoUnwindReadnoneUwtable:#[0-9]*]] ; define dso_local i32* @srec16(i32* %a) #0 { entry: @@ -471,4 +470,4 @@ attributes #0 = { noinline nounwind uwtable } -; CHECK: attributes [[NoInlineNoUnwindReadnoneUwtable]] = { noinline nounwind readnone uwtable } +; CHECK: attributes [[NoInlineNoReturnNoUnwindReadnoneUwtable]] = { noinline noreturn nounwind readnone uwtable } diff --git a/llvm/test/Transforms/FunctionAttrs/arg_returned.ll b/llvm/test/Transforms/FunctionAttrs/arg_returned.ll --- a/llvm/test/Transforms/FunctionAttrs/arg_returned.ll +++ b/llvm/test/Transforms/FunctionAttrs/arg_returned.ll @@ -267,8 +267,8 @@ ; } ; ; FEW_IT: define dso_local i32* @ret0(i32* %a) -; FNATTR: define dso_local i32* @ret0(i32* readonly %a) [[NoInlineNoUnwindReadonlyUwtable:#[0-9]*]] -; BOTH: define dso_local i32* @ret0(i32* readonly returned %a) [[NoInlineNoUnwindReadonlyUwtable:#[0-9]*]] +; FNATTR: define dso_local i32* @ret0(i32* readonly %a) [[NoInlineNoUnwindUwtable:#[0-9]*]] +; BOTH: define dso_local i32* @ret0(i32* readonly returned %a) [[NoInlineNoReturnNoUnwindReadonlyUwtable:#[0-9]*]] define dso_local i32* @ret0(i32* %a) #0 { entry: %v = load i32, i32* %a, align 4 @@ -618,5 +618,6 @@ ; BOTH-DAG: attributes [[NoInlineNoRecurseNoUnwindReadnoneUwtable]] = { noinline norecurse nounwind readnone uwtable } ; BOTH-DAG: attributes [[NoInlineNoUnwindReadnoneUwtable]] = { noinline nounwind readnone uwtable } -; BOTH-DAG: attributes [[NoInlineNoUnwindReadonlyUwtable]] = { noinline nounwind readonly uwtable } +; BOTH-DAG: attributes [[NoInlineNoReturnNoUnwindReadonlyUwtable]] = { noinline noreturn nounwind readonly uwtable } +; BOTH-DAG: attributes [[NoInlineNoUnwindUwtable]] = { noinline nounwind uwtable } ; BOTH-DAG: attributes [[NoInlineNoRecurseNoUnwindUwtable]] = { noinline norecurse nounwind uwtable } diff --git a/llvm/test/Transforms/FunctionAttrs/fn_noreturn.ll b/llvm/test/Transforms/FunctionAttrs/fn_noreturn.ll --- a/llvm/test/Transforms/FunctionAttrs/fn_noreturn.ll +++ b/llvm/test/Transforms/FunctionAttrs/fn_noreturn.ll @@ -18,8 +18,7 @@ ; return srec0(); ; } ; -; FIXME: no-return missing -; CHECK: define dso_local void @srec0() [[NoInlineNoUnwindReadnoneUwtable:#[0-9]]] +; CHECK: define dso_local void @srec0() [[NoInlineNoReturnNoUnwindReadnoneUwtable:#[0-9]]] ; define dso_local void @srec0() #0 { entry: @@ -34,8 +33,7 @@ ; return srec16(srec16(srec16(srec16(srec16(srec16(srec16(srec16(srec16(srec16(srec16(srec16(srec16(srec16(srec16(srec16(a)))))))))))))))); ; } ; -; FIXME: no-return missing -; CHECK: define dso_local i32 @srec16(i32 %a) [[NoInlineNoUnwindReadnoneUwtable]] +; CHECK: define dso_local i32 @srec16(i32 %a) [[NoInlineNoReturnNoUnwindReadnoneUwtable]] ; define dso_local i32 @srec16(i32 %a) #0 { entry: @@ -65,8 +63,7 @@ ; while (1); ; } ; -; FIXME: no-return missing -; CHECK: define dso_local i32 @endless_loop(i32 %a) [[NoInlineNoRecurseNoUnwindReadnoneUwtable:#[0-9]]] +; CHECK: define dso_local i32 @endless_loop(i32 %a) [[NoInlineNoRecurseNoReturnNoUnwindReadnoneUwtable:#[0-9]]] ; define dso_local i32 @endless_loop(i32 %a) #0 { entry: @@ -84,8 +81,7 @@ ; return a; ; } ; -; FIXME: no-return missing -; CHECK: define dso_local i32 @dead_return(i32 returned %a) [[NoInlineNoRecurseNoUnwindReadnoneUwtable]] +; CHECK: define dso_local i32 @dead_return(i32 returned %a) [[NoInlineNoRecurseNoReturnNoUnwindReadnoneUwtable]] ; define dso_local i32 @dead_return(i32 %a) #0 { entry: @@ -105,8 +101,7 @@ ; return a == 0 ? endless_loop(a) : srec16(a); ; } ; -; FIXME: no-return missing -; CHECK: define dso_local i32 @multiple_noreturn_calls(i32 %a) [[NoInlineNoUnwindReadnoneUwtable]] +; CHECK: define dso_local i32 @multiple_noreturn_calls(i32 %a) [[NoInlineNoReturnNoUnwindReadnoneUwtable]] ; define dso_local i32 @multiple_noreturn_calls(i32 %a) #0 { entry: @@ -128,5 +123,5 @@ attributes #0 = { noinline nounwind uwtable } -; CHECK-DAG: attributes [[NoInlineNoUnwindReadnoneUwtable]] = { noinline nounwind readnone uwtable } -; CHECK-DAG: attributes [[NoInlineNoRecurseNoUnwindReadnoneUwtable]] = { noinline norecurse nounwind readnone uwtable } +; CHECK-DAG: attributes [[NoInlineNoReturnNoUnwindReadnoneUwtable]] = { noinline noreturn nounwind readnone uwtable } +; CHECK-DAG: attributes [[NoInlineNoRecurseNoReturnNoUnwindReadnoneUwtable]] = { noinline norecurse noreturn nounwind readnone uwtable }