Index: llvm/include/llvm/Transforms/IPO/Attributor.h =================================================================== --- llvm/include/llvm/Transforms/IPO/Attributor.h +++ llvm/include/llvm/Transforms/IPO/Attributor.h @@ -582,6 +582,38 @@ static constexpr Attribute::AttrKind ID = Attribute::Returned; }; + +/// An abstract attribute for willreturn. +struct AAWillReturn : public AbstractAttribute { + + /// See AbstractAttribute::AbstractAttribute(...). + AAWillReturn(Function &F, InformationCache &InfoCache) + : AbstractAttribute(F, InfoCache) {} + + /// Return the deduced attributes in \p Attrs. + virtual void + getDeducedAttributes(SmallVectorImpl &Attrs) const override { + LLVMContext &Ctx = AnchoredVal.getContext(); + Attrs.emplace_back(Attribute::get(Ctx, "willreturn")); + } + + /// See AbstractAttribute::getAttrKind() + virtual Attribute::AttrKind getAttrKind() const override { + return Attribute::None; + } + + /// Return true if "willreturn" is known. + bool isKnownWillReturn() const; + + /// Return true if "willreturn" is assumed. + bool isAssumedWillReturn() const; + + /// The identifier used by the Attributor for this class of attributes. + /// FIXME: I use Attribute::None + 2 for now. + static constexpr Attribute::AttrKind ID = + Attribute::AttrKind(Attribute::None + 2); +}; + } // end namespace llvm #endif // LLVM_TRANSFORMS_IPO_FUNCTIONATTRS_H Index: llvm/lib/Transforms/IPO/Attributor.cpp =================================================================== --- llvm/lib/Transforms/IPO/Attributor.cpp +++ llvm/lib/Transforms/IPO/Attributor.cpp @@ -14,6 +14,7 @@ //===----------------------------------------------------------------------===// #include "llvm/Transforms/IPO/Attributor.h" +#include "llvm/ADT/DepthFirstIterator.h" #include "llvm/ADT/SetVector.h" #include "llvm/ADT/SmallPtrSet.h" #include "llvm/ADT/SmallVector.h" @@ -1031,6 +1032,116 @@ return ChangeStatus::CHANGED; } +/// ------------------------ Will-Return Attributes ---------------------------- + +struct AAWillReturnImpl : public AAWillReturn, BooleanState { + + /// See AbstractAttribute::AbstractAttribute(...). + AAWillReturnImpl(Function &F, InformationCache &InfoCache) + : AAWillReturn(F, InfoCache) {} + + /// See AAWillReturn::isKnownWillReturn(). + bool isKnownWillReturn() const { return getKnown(); } + + /// See AAWillReturn::isAssumedWillReturn(). + bool isAssumedWillReturn() 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() ? "willreturn" : "may-noreturn"; + } +}; + +struct AAWillReturnFunction final : AAWillReturnImpl { + + /// See AbstractAttribute::AbstractAttribute(...). + AAWillReturnFunction(Function &F, InformationCache &InfoCache) + : AAWillReturnImpl(F, InfoCache) {} + + /// See AbstractAttribute::getManifestPosition(). + virtual ManifestPosition getManifestPosition() const override { + return MP_FUNCTION; + } + + /// See AbstractAttribute::initialize(...). + virtual void initialize(Attributor &A) override; + + /// See AbstractAttribute::updateImpl(...). + virtual ChangeStatus updateImpl(Attributor &A) override; +}; + +// Helper function that checks whether a function has any cycle. +bool containsCycle(Function &F) { + SmallPtrSet Visited; + + // Traverse BB by dfs and check whether successor is already visited. + for (BasicBlock *BB : depth_first(&F)) { + Visited.insert(BB); + for (auto *SuccBB : successors(BB)) { + if (Visited.count(SuccBB)) + return true; + } + } + return false; +} + +// Helper function that checks the function have a loop which might become an +// endless loop +// FIXME: Any cycle is regarded as endless loop for now. +// We have to allow some patterns. +bool containsPossiblyEndlessLoop(Function &F) { return containsCycle(F); } + +void AAWillReturnFunction::initialize(Attributor &A) { + Function &F = getAnchorScope(); + + if (containsPossiblyEndlessLoop(F)) + indicatePessimisticFixpoint(); +} + +ChangeStatus AAWillReturnFunction::updateImpl(Attributor &A) { + Function &F = getAnchorScope(); + + // The map from instruction opcodes to those instructions in the function. + auto &OpcodeInstMap = InfoCache.getOpcodeInstMapForFunction(F); + + for (unsigned Opcode : + {(unsigned)Instruction::Invoke, (unsigned)Instruction::CallBr, + (unsigned)Instruction::Call}) { + for (Instruction *I : OpcodeInstMap[Opcode]) { + auto ICS = ImmutableCallSite(I); + + // Assume that all intrinsic without noreturn are willreturn + if (isa(I) && !ICS.hasFnAttr(Attribute::NoReturn)) { + continue; + } + + auto *WillReturnAA = A.getAAFor(*this, *I); + if ((!WillReturnAA || !WillReturnAA->isValidState() || + !WillReturnAA->isAssumedWillReturn()) && + !ICS.hasFnAttr("willreturn")) { + indicatePessimisticFixpoint(); + return ChangeStatus::CHANGED; + } + + // FIXME: Prohibit any recursion for now + auto *NoRecurseAA = A.getAAFor(*this, *I); + if ((!NoRecurseAA || !NoRecurseAA->isValidState() || + !NoRecurseAA->isAssumedNoRecurse()) && + !ICS.hasFnAttr(Attribute::NoRecurse)) { + indicatePessimisticFixpoint(); + return ChangeStatus::CHANGED; + } + } + } + + return ChangeStatus::UNCHANGED; +} /// ---------------------------------------------------------------------------- /// Attributor @@ -1190,6 +1301,9 @@ // Every function might be "no-return". registerAA(*new AANoReturnFunction(F, InfoCache)); + // Every function might be "will-return". + registerAA(*new AAWillReturnFunction(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. Index: llvm/test/Transforms/FunctionAttrs/willreturn.ll =================================================================== --- llvm/test/Transforms/FunctionAttrs/willreturn.ll +++ llvm/test/Transforms/FunctionAttrs/willreturn.ll @@ -1,4 +1,6 @@ ; RUN: opt -functionattrs -S < %s | FileCheck %s --check-prefix=FNATTR +; RUN: opt -attributor -S < %s | FileCheck %s --check-prefix=ATTRIBUTOR + target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128" @@ -7,9 +9,10 @@ ; TEST 1 (positive case) -; FIXME: missing "willreturn" ; FNATTR: Function Attrs: noinline norecurse nounwind readnone uwtable ; FNATTR-NEXT: define void @only_return() +; ATTRIBUTOR: Function Attrs: noinline norecurse nounwind uwtable "nofree" "willreturn" +; ATTRIBUTOR-NEXT: define void @only_return() define void @only_return() #0 { ret void } @@ -25,6 +28,8 @@ ; FIXME: missing "willreturn" ; FNATTR: Function Attrs: noinline nounwind readnone uwtable ; FNATTR-NEXT: define i32 @fib(i32) +; ATTRIBUTOR: Function Attrs: noinline nounwind uwtable "nofree" +; ATTRIBUTOR-NEXT: define i32 @fib(i32) local_unnamed_addr define i32 @fib(i32) local_unnamed_addr #0 { %2 = icmp slt i32 %0, 2 br i1 %2, label %9, label %3 @@ -54,6 +59,9 @@ ; FNATTR: Function Attrs: noinline norecurse nounwind readnone uwtable ; FNATTR-NOT: "willreturn" ; FNATTR-NEXT: define i32 @fact_maybe_not_halt(i32) local_unnamed_addr +; ATTRIBUTOR: Function Attrs: noinline norecurse nounwind uwtable "nofree" +; ATTRIBUTOR-NOT: "willreturn" +; ATTRIBUTOR-NEXT: define i32 @fact_maybe_not_halt(i32) local_unnamed_addr define i32 @fact_maybe_not_halt(i32) local_unnamed_addr #0 { %2 = icmp eq i32 %0, 0 br i1 %2, label %11, label %3 @@ -87,6 +95,8 @@ ; FIXME: missing "willreturn" ; FNATTR: Function Attrs: noinline norecurse nounwind readnone uwtable ; FNATTR-NEXT: define i32 @fact_loop(i32) +; ATTRIBUTOR: Function Attrs: noinline norecurse nounwind uwtable "nofree" +; ATTRIBUTOR-NEXT: define i32 @fact_loop(i32) local_unnamed_addr define i32 @fact_loop(i32) local_unnamed_addr #0 { %2 = icmp slt i32 %0, 1 br i1 %2, label %3, label %5 @@ -116,6 +126,9 @@ ; FNATTR: Function Attrs: noinline nounwind readnone uwtable ; FNATTR-NOT: "willreturn" ; FNATTR-NEXT: define void @mutual_recursion1() +; ATTRIBUTOR: Function Attrs: noinline noreturn nounwind uwtable "nofree" +; ATTRIBUTOR-NOT: "willreturn" +; ATTRIBUTOR-NEXT: define void @mutual_recursion1() define void @mutual_recursion1() #0 { call void @mutual_recursion2() ret void @@ -125,6 +138,9 @@ ; FNATTR: Function Attrs: noinline nounwind readnone uwtable ; FNATTR-NOT: "willreturn" ; FNATTR-NEXT: define void @mutual_recursion2() +; ATTRIBUTOR: Function Attrs: noinline noreturn nounwind uwtable "nofree" +; ATTRIBUTOR-NOT: "willreturn" +; ATTRIBUTOR-NEXT: define void @mutual_recursion2() define void @mutual_recursion2() #0 { call void @mutual_recursion1() ret void @@ -135,11 +151,16 @@ ; call exit/abort (has noreturn attribute) ; FNATTR: Function Attrs: noreturn ; FNATTR-NEXT: declare void @exit(i32) local_unnamed_addr +; ATTRIBUTOR: Function Attrs: noreturn +; ATTRIBUTOR-NEXT: declare void @exit(i32) local_unnamed_add declare void @exit(i32) local_unnamed_addr noreturn ; FNATTR: Function Attrs: noinline nounwind uwtable ; FNATTR-NOT: "willreturn" ; FNATTR-NEXT: define void @only_exit() +; ATTRIBUTOR: Function Attrs: noinline noreturn nounwind uwtable +; ATTRIBUTOR-NOT: "willreturn" +; ATTRIBUTOR-NEXT: define void @only_exit() local_unnamed_addr define void @only_exit() local_unnamed_addr #0 { tail call void @exit(i32 0) unreachable @@ -158,6 +179,9 @@ ; FNATTR: Function Attrs: noinline nounwind uwtable ; FNATTR-NOT: "willreturn" ; FNATTR-NEXT: define void @conditional_exit(i32, i32* nocapture readonly) local_unnamed_addr +; ATTRIBUTOR: Function Attrs: noinline nounwind uwtable +; ATTRIBUTOR-NOT: "willreturn" +; ATTRIBUTOR-NEXT: define void @conditional_exit(i32, i32* nocapture readonly) local_unnamed_addr define void @conditional_exit(i32, i32* nocapture readonly) local_unnamed_addr #0 { %3 = icmp eq i32 %0, 0 br i1 %3, label %5, label %4 @@ -183,11 +207,14 @@ ; Call intrinsic function ; FNATTRS: Function Attrs: noinline readnone speculatable ; FNATTRS-NEXT: declare float @llvm.floor.f32(float) +; ATTRIBUTOR: Function Attrs: nounwind readnone speculatable +; ATTRIBUTOR-NEXT: declare float @llvm.floor.f32(float declare float @llvm.floor.f32(float) -; FIXME: missing "willreturn" ; FNATTRS: Function Attrs: noinline nounwind uwtable ; FNATTRS-NEXT: define void @call_floor(float %a) +; ATTRIBUTOR: Function Attrs: noinline norecurse nounwind uwtable "willreturn" +; ATTRIBUTOR-NEXT: define void @call_floor(float %a) define void @call_floor(float %a) #0 { tail call float @llvm.floor.f32(float %a) ret void @@ -200,11 +227,17 @@ ; FNATTR: Function Attrs: noinline nounwind uwtable ; FNATTR-NOT: "willreturn" ; FNATTR-NEXT: declare void @maybe_noreturn() +; ATTRIBUTOR: Function Attrs: noinline nounwind uwtable +; ATTRIBUTOR-NOT: "willreturn" +; ATTRIBUTOR-NEXT: declare void @maybe_noreturn() declare void @maybe_noreturn() #0 ; FNATTR: Function Attrs: noinline nounwind uwtable ; FNATTR-NOT: "willreturn" ; FNATTR-NEXT: define void @call_maybe_noreturn() +; ATTRIBUTOR: Function Attrs: noinline nounwind uwtable +; ATTRIBUTOR-NOT: "willreturn" +; ATTRIBUTOR-NEXT: define void @call_maybe_noreturn() define void @call_maybe_noreturn() #0 { tail call void @maybe_noreturn() ret void @@ -216,11 +249,15 @@ ; FNATTR: Function Attrs: "willreturn" ; FNATTR-NEXT: declare void @will_return() +; ATTRIBUTOR: Function Attrs: "willreturn" +; ATTRIBUTOR-NEXT: declare void @will_return() declare void @will_return() "willreturn" ; FIXME: missing "willreturn" ; FNATTR: Function Attrs: noinline nounwind uwtable ; FNATTR-NEXT: define void @f1() +; ATTRIBUTOR: Function Attrs: noinline nounwind uwtable +; ATTRIBUTOR-NEXT: define void @f1() define void @f1() #0 { tail call void @will_return() ret void @@ -229,6 +266,8 @@ ; FIXME: missing "willreturn" ; FNATTR: Function Attrs: noinline nounwind uwtable ; FNATTR-NEXT: define void @f2() +; ATTRIBUTOR: Function Attrs: noinline nounwind uwtable +; ATTRIBUTOR-NEXT: define void @f2() define void @f2() #0 { tail call void @f1() ret void @@ -241,6 +280,9 @@ ; FNATTR: Function Attrs: noinline nounwind uwtable ; FNATTR-NOT: "willreturn" ; FNATTR-NEXT: define void @call_will_return_but_has_loop() +; ATTRIBUTOR: Function Attrs: noinline noreturn nounwind uwtable +; ATTRIBUTOR-NOT: "willreturn" +; ATTRIBUTOR-NEXT: define void @call_will_return_but_has_loop() define void @call_will_return_but_has_loop() #0 { br label %label1 label1: @@ -256,11 +298,14 @@ ; FNATTR: Function Attrs: noinline uwtable "willreturn" ; FNATTR-NEXT: declare i1 @maybe_raise_exception() +; ATTRIBUTOR: Function Attrs: noinline uwtable "willreturn" +; ATTRIBUTOR-NEXT: declare i1 @maybe_raise_exception() declare i1 @maybe_raise_exception() #1 "willreturn" ; FIXME: missing "willreturn" ; FNATTR: Function Attrs: nounwind ; FNATTR-NEXT: define void @invoke_test() +; ATTRIBUTOR: define void @invoke_test() define void @invoke_test() personality i32 (...)* @__gxx_personality_v0 { invoke i1 @maybe_raise_exception() to label %N unwind label %F @@ -288,6 +333,8 @@ ; FIXME: missing "willreturn" ; FNATTR: Function Attrs: noinline norecurse nounwind readonly uwtable ; FNATTR-NEXT: define i32 @loop_constant_trip_count(i32* nocapture readonly) +; ATTRIBUTOR: Function Attrs: noinline norecurse nounwind uwtable "nofree" +; ATTRIBUTOR-NEXT: define i32 @loop_constant_trip_count(i32* nocapture readonly) define i32 @loop_constant_trip_count(i32* nocapture readonly) #0 { br label %3 @@ -319,6 +366,9 @@ ; FNATTR: Function Attrs: noinline norecurse nounwind readonly uwtable ; FNATTR-NOT: "willreturn" ; FNATTR-NEXT: define i32 @loop_trip_count_unbound(i32, i32, i32* nocapture readonly, i32) local_unnamed_addr +; ATTRIBUTOR: Function Attrs: noinline norecurse nounwind uwtable "nofree" +; ATTRIBUTOR-NOT: "willreturn" +; ATTRIBUTOR-NEXT: define i32 @loop_trip_count_unbound(i32, i32, i32* nocapture readonly, i32) local_unnamed_addr define i32 @loop_trip_count_unbound(i32, i32, i32* nocapture readonly, i32) local_unnamed_addr #0 { %5 = icmp eq i32 %0, %1 br i1 %5, label %6, label %8 @@ -354,6 +404,8 @@ ; FIXME: missing "willreturn" ; FNATTR: Function Attrs: noinline norecurse nounwind readonly uwtable ; FNATTR-NEXT: define i32 @loop_trip_dec(i32, i32* nocapture readonly) +; ATTRIBUTOR: Function Attrs: noinline norecurse nounwind uwtable "nofree" +; ATTRIBUTOR-NEXT: define i32 @loop_trip_dec(i32, i32* nocapture readonly) local_unnamed_addr define i32 @loop_trip_dec(i32, i32* nocapture readonly) local_unnamed_addr #0 { %3 = icmp sgt i32 %0, -1 @@ -384,6 +436,8 @@ ; FIXME: missing "willreturn" ; FNATTR: Function Attrs: noinline norecurse nounwind readnone uwtable ; FNATTR-NEXT: define i32 @multiple_return(i32 %a) +; ATTRIBUTOR: Function Attrs: noinline norecurse nounwind uwtable "nofree" "willreturn" +; ATTRIBUTOR-NEXT: define i32 @multiple_return(i32 %a) define i32 @multiple_return(i32 %a) #0 { %b = icmp eq i32 %a, 0 br i1 %b, label %t, label %f @@ -401,6 +455,8 @@ ; FIXME: missing "willreturn" ; FNATTR: Function Attrs: noinline nounwind uwtable ; FNATTR-NEXT: define void @unreachable_exit_positive1() +; ATTRIBUTOR: Function Attrs: noinline nounwind uwtable +; ATTRIBUTOR-NEXT: define void @unreachable_exit_positive1() define void @unreachable_exit_positive1() #0 { tail call void @will_return() ret void @@ -413,6 +469,8 @@ ; FIXME: missing "willreturn" ; FNATTR: Function Attrs: noinline nounwind uwtable ; FNATTR-NEXT: define i32 @unreachable_exit_positive2(i32) +; ATTRIBUTOR: Function Attrs: noinline nounwind uwtable +; ATTRIBUTOR-NEXT: define i32 @unreachable_exit_positive2(i32) define i32 @unreachable_exit_positive2(i32) local_unnamed_addr #0 { %2 = icmp slt i32 %0, 1 br i1 %2, label %3, label %5 @@ -439,6 +497,9 @@ ; FNATTR: Function Attrs: noinline nounwind uwtable ; FNATTR-NOT: "willreturn" ; FNATTR-NEXT: define void @unreachable_exit_negative1() +; ATTRIBUTOR: Function Attrs: noinline nounwind uwtable +; ATTRIBUTOR-NOT: "willreturn" +; ATTRIBUTOR-NEXT: define void @unreachable_exit_negative1() define void @unreachable_exit_negative1() #0 { tail call void @exit(i32 0) ret void @@ -451,6 +512,9 @@ ; FNATTR: Function Attrs: noinline nounwind uwtable ; FNATTR-NOT: "willreturn" ; FNATTR-NEXT: define void @unreachable_exit_negative2() +; ATTRIBUTOR: Function Attrs: noinline noreturn nounwind uwtable +; ATTRIBUTOR-NOT: "willreturn" +; ATTRIBUTOR-NEXT: define void @unreachable_exit_negative2() define void @unreachable_exit_negative2() #0 { br label %L1 @@ -464,6 +528,23 @@ unreachable } +; FNATTR: Function Attrs: noreturn nounwind +; FNATTR-NEXT: declare void @llvm.eh.sjlj.longjmp(i8*) +; ATTRIBUTOR: Function Attrs: noreturn nounwind +; ATTRIBUTOR-NEXT: declare void @llvm.eh.sjlj.longjmp(i8*) +declare void @llvm.eh.sjlj.longjmp(i8*) + +; FNATTR: Function Attrs: noinline nounwind uwtable +; FNATTR-NOT: "willreturn" +; FNATTR-NEXT: define void @call_longjmp(i8* nocapture readnone) local_unnamed_addr #3 { +; ATTRIBUTOR: Function Attrs: noinline nounwind uwtable +; ATTRIBUTOR-NOT: "willreturn" +; ATTRIBUTOR-NEXT: define void @call_longjmp(i8* nocapture readnone) local_unnamed_addr +define void @call_longjmp(i8* nocapture readnone) local_unnamed_addr #0 { + tail call void @llvm.eh.sjlj.longjmp(i8* %0) + ret void +} + attributes #0 = { nounwind uwtable noinline } attributes #1 = { uwtable noinline }