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 @@ -131,6 +131,7 @@ /// The positions attributes can be manifested in. enum ManifestPosition { MP_ARGUMENT, ///< An attribute for a function argument. + MP_FUNCTION, ///< An attribute for a function as a whole. }; /// An abstract attribute associated with \p AssociatedVal and anchored at 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" @@ -43,6 +44,8 @@ STATISTIC(NumFnArgumentReturned, "Number of function arguments marked returned"); +STATISTIC(NumFnNoReturn, "Number of functions marked noreturn"); + // TODO: Determine a good default value. static cl::opt MaxFixpointIterations("attributor-max-iterations", cl::Hidden, @@ -65,6 +68,44 @@ } ///} +/// Simple state with integers encoding. The worst/known and best/assumed state +/// encodings, as well as the underlying integer type, are provided as template +/// parameters. +template +struct IntegerState : public AbstractState { + IntegerState() : Known(InitKnown), Assumed(InitAssumed) {} + + /// See AbstractState::isValidState() + bool isValidState() const override { return Assumed != InitKnown; } + + /// See AbstractState::isAtFixpoint() + bool isAtFixpoint() const override { return Assumed == Known; } + + /// See AbstractState::indicateFixpoint(...) + void indicateFixpoint(bool Optimistic) override { + if (Optimistic) + Known = Assumed; + else + Assumed = Known; + } + + /// Return the known (integer) state. + BaseTy getKnown() const { return Known; } + + /// Return the assumed (integer) state. + BaseTy getAssumed() const { return Assumed; } + +protected: + /// The known state encoding in an integer of type BaseTy. + BaseTy Known; + + /// The assumed state encoding in an integer of type BaseTy. + BaseTy Assumed; +}; + +/// Specialization of the integer state for booleans. +using BooleanState = IntegerState; + /// Helper to adjust the statistics. static void bookkeeping(AbstractAttribute::ManifestPosition MP, const Attribute &Attr) { @@ -72,6 +113,9 @@ case Attribute::Returned: NumFnArgumentReturned++; return; + case Attribute::NoReturn: + NumFnNoReturn++; + return; default: return; } @@ -163,6 +207,23 @@ } break; } + case MP_FUNCTION: { + Function &F = cast(getAnchoredValue()); + for (const Attribute &Attr : Attrs) { + if (F.hasFnAttribute(Attr.getKindAsEnum())) { + const Attribute &ExistingAttr = F.getFnAttribute(Attr.getKindAsEnum()); + if (!ExistingAttr.isIntAttribute() || + ExistingAttr.getValueAsInt() >= Attr.getValueAsInt()) + continue; + } + + F.addFnAttr(Attr); + + // Bookkeeping. + bookkeeping(MP_FUNCTION, Attr); + } + break; + } } return Changed; @@ -449,6 +510,145 @@ 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())) { + AANoReturn *PrevInstNoReturnAA = A.getAAFor(*this, *I); + if (!PrevInstNoReturnAA || !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. + AANoReturn *ReturnValueNoReturnAA = + A.getAAFor(*this, *ReturnValue); + if (!ReturnValueNoReturnAA || !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. + AAReturnedValuesImpl *RVAA = A.getAAFor(*this, F); + if (RVAA && RVAA->getState().isValidState()) { + + auto IsValidReturnValue = + [&](AAReturnedValuesImpl::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 /// ---------------------------------------------------------------------------- @@ -629,6 +829,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. @@ -658,6 +861,8 @@ switch (AP) { case AbstractAttribute::MP_ARGUMENT: return OS << "arg"; + case AbstractAttribute::MP_FUNCTION: + return OS << "fn"; } llvm_unreachable("Unknown attribute position!"); } 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 }