[Attributor] Deduce the "no-return" attribute for functions

[jdoerfert]

Summary

A function is "no-return" if we never reach a return instruction.

We use this logic to identify and mark "no-return" functions. This works
when the AAReturnedValues abstract attribute uses AAIsDead (D65243) and
because AAIsDead relies on AANoReturn.

[jdoerfert]

Minor adjustment to prior patches

[jdoerfert]

Minor changes

[xbolva00]

llvm/lib/Transforms/IPO/Attributor.cpp

589

llvm::all_of?

[jdoerfert]

llvm/lib/Transforms/IPO/Attributor.cpp

589

I can change that, it'll probably appear again in other patches for now.

[jdoerfert]

I'll update this one after AAIsDead is available (see D64162).

[jdoerfert]

Simplify the no-return deduction based on liveness and returned values

[sstefan1]

llvm/lib/Transforms/IPO/Attributor.cpp

735

no-return state?

[jdoerfert]

llvm/lib/Transforms/IPO/Attributor.cpp

735

Good catch.

[Meinersbur]

llvm/lib/Transforms/IPO/Attributor.cpp

721

Generally, lambdas should not be a given a type since each lambda has its own, compiler-private type. In this case, a std::function is needed anyway to be passed as an argument of checkForallReturnedValues.

Have you considered changing checkForallReturnedValues to accept an llvm::function_ref such that the std::function overhead is not required?

llvm/test/Transforms/FunctionAttrs/arg_nocapture.ll

2 ↗

(On Diff #211672)

Unrelated change?

llvm/test/Transforms/FunctionAttrs/fn_noreturn.ll

40

Out of curiosity, where/how does the Attributor determine this is an infinite recursion? Wouldn't a single recursive call be enough?

[jdoerfert]

llvm/lib/Transforms/IPO/Attributor.cpp

721

I thought about it at some point after the interface was created. I'll look into it eventually but not in this commit.

llvm/test/Transforms/FunctionAttrs/arg_nocapture.ll

2 ↗

(On Diff #211672)

no.

"Verification" is tricky right now, we haven't found a good system yet. This change will break "verification" but not because it actually does something wrong but because the "verification" is not smart enough. As I said, we do not have a good way of replacing the mechanism yet so I disable it here for now.

llvm/test/Transforms/FunctionAttrs/fn_noreturn.ll

40

A single call is sufficient, when I wrote the test I had something else in mind though.
No-return is now deduced here because:

• Initially we assume %call is noreturn,
• which causes %call1 and the rest to be dead (AAIsDead),
• which causes the return to be never encountered by AAReturnedValues (after D65243),
• which causes %call to stay assumed noreturn.

So a single call suffices.

The cascade might be a nice test to make sure we do not go down the rabbit hole.

[Meinersbur]

llvm/test/Transforms/FunctionAttrs/arg_nocapture.ll

2 ↗

(On Diff #211672)

Maybe add a TODO/FIXME remark about it?

llvm/test/Transforms/FunctionAttrs/fn_noreturn.ll

40

On windows, you can catch a stackoverflow exception. E.g. in this program:

#include <cstdlib>
#include <cstdio>

void overflow() {
  overflow();
}

int catchoverflow() {
  __try  {
    overflow();
    printf("Exception NOT caught\n");
    return 0;
  } 
  __except(true) {
    printf("Exception caught\n");
    return 1;
  }
  return 2;
}

int main() {
  auto result = catchoverflow();
  printf("Done execution result=%i\n", result);
  return EXIT_SUCCESS;
}

results in (compiled with either msvc or clang-cl):

Exception caught
Done execution result=1

The LLVM-IR for this contains:

entry:
  %retval = alloca i32, align 4
  %__exception_code = alloca i32, align 4
  invoke void @"?overflow@@YAXXZ"() #6
          to label %invoke.cont unwind label %catch.dispatch

catch.dispatch:                                   ; preds = %invoke.cont, %entry
  %0 = catchswitch within none [label %__except] unwind to caller

(entire file:

stackoverflow-clang.ll8 KBDownload

)

Would catchoverflow() still get a noreturn attribute?

[Meinersbur]

llvm/test/Transforms/FunctionAttrs/fn_noreturn.ll

83–84

I think this loop should not be noreturn. The loop deletion pass will remove this loop (due to not having side-effects), simplifying it to

entry:
  ret i32 %a

which obviously returns.

[jdoerfert]

llvm/test/Transforms/FunctionAttrs/arg_nocapture.ll

2 ↗

(On Diff #211672)

There is a remark about the problems with the verifier flag already. Coming up with a proper solution to the verification challenge is on my list.

llvm/test/Transforms/FunctionAttrs/fn_noreturn.ll

40

As we discussed in person, stack overflows are currently not part of the LLVM-IR model. I add tests for this and fix the AAIsDead handling of invoke. I will also improve the langref in the next version.

83–84

1. I think noreturn is fine, and loop deletion will not, better should not, delete the loop because it is not sound.

2. Assuming it did for a moment, we would not execute ret i32 %a but unreachable. There is no way to connect the return block to the loop. Assuming there was, what happens if we would have a side effect after the loop:

define i32 @dead_return(i32 %a) #0 {
entry:
  br label %while.body

while.body:                                       ; preds = %entry, %while.body
  br label %while.body

return:                                           ; No predecessors!
  call void foo();
  ret i32 %a
}

Now, depending on the pass order, the call would be removed (it is not reachable from the entry) or executed, if we assume the loop would actually be deleted and the unconnected block would be executed.

3. The situation where we delete an "endless" loops is

define i32 @conditionally_dead_return(i32 %a, i1 %const_cnd) #0 {
entry:
  br label %while.body

while.body:                                       ; preds = %entry, %while.body
  br i1 %const_cnd, label %return, label %while.body

return:                                           ; preds = %while.body
  call void foo();
  ret i32 %a
}

Now the loop is conditionally endless and still without side-effect. We cannot mark it as noreturn but we can actually delete the loop as we require forward progress. That means in the original example above we can remove the loop and put unreachable there as well.

[Meinersbur]

llvm/test/Transforms/FunctionAttrs/fn_noreturn.ll

83–84

I had a different structure in mind, namely:

while.body:
  br i1 false label %return, label %while.body

(i.e. the return bb is still connected)

However, LoopDeletion might remove it since it is allowed to assume that loops without sideeffects to terminate (as inherited from C/C++). That is, infinite loops without sideeffects are undefined behavior. To avoid this, front-end with different semantics can insert an [[ https://llvm.org/docs/LangRef.html#llvm-sideeffect-intrinsic | llvm.sideffect ]] intrinsic.

Since it is undefined behavior, we may indeed assume noreturn. Sorry for the false alert.

PS: For some reason, LoopDeletion has not been tough this when llvm.sideeffect was added in D38336. It still uses ScalarEvolution to ensure that infinite loops are never removed. I guess the second part of D38336 has never landed.

[nikic]

llvm/test/Transforms/FunctionAttrs/fn_noreturn.ll

83–84

Wait, isn't the current consensus that LLVM IR itself does not have a forward-progress requirement? llvm.sideeffect() is a workaround (and a pretty bad one in terms of optimization impact, to the point that likely nobody uses it), but eventually LLVM should handle loops without forward-progress correctly. (The recently introduced willreturn attribute should solve a large part of the problem in practice, because it can replace the incorrect readonly-based reasoning that is currently used in its place.)

[jdoerfert]

llvm/test/Transforms/FunctionAttrs/fn_noreturn.ll

83–84

@nikic I might misunderstand but: I thought the reason we have llvm.sideeffect() is because LLVM-IR does require forward-progress. So, if you have a no-side-effect potentially endless loop, it can be removed because the forward-progress requirement guarantees it cannot be endless. If you want a true endless loop you need a side-effect, thus, llvm.sideffect(). Please correct me if I'm wrong.

(This does not impact the noreturn logic above though and I will fix the invoke issue in AAIsDead now.)

[nikic]

llvm/test/Transforms/FunctionAttrs/fn_noreturn.ll

83–84

Here's how I understand the current state to be, based on https://bugs.llvm.org/show_bug.cgi?id=965 (maybe @efriedma can confirm whether this is right?)

• Forward-progress is a C++ concept. C does not have a forward-progress guarantee, so LLVM needs to support this (and well).
• LLVM IR has no forward-progress guarantee (currently by omission -- it seems like LangRef should make an explicit mention in either direction).
• In practice, infinite loops are not well-supported yet, which is why llvm.sideeffect() exists as a workaround.
• If necessary for good optimization, a new function attribute may be added to opt-in to forward-progress for use by C++ frontends.

[jdoerfert]

More test, small fixes, review comments integrated

[jdoerfert]

Add stackoverflow example, positive and negative

[Meinersbur]

llvm/test/Transforms/FunctionAttrs/fn_noreturn.ll

83–84

Forward-progress is a C++ concept. C does not have a forward-progress guarantee, so LLVM needs to support this (and well).

C11 section 6.8.5:

An iteration statement whose controlling expression is not a constant expression) that performs no input/output operations, does not access volatile objects, and performs no synchronization or atomic operations in its body, controlling expression, or (in the case of a for statement) its expression-3, may be assumed by the implementation to terminate.[157])

[157] This is intended to allow compiler transformations such as removal of empty loops even when termination cannot be proven.

There are of course other front-ends with different semantics of endless loop, which is why llvm.sideeffect has been added. This seems to be the accepted solution after discussion in D38336.

llvm/test/Transforms/FunctionAttrs/nofree-attributor.ll

70–78 ↗

(On Diff #213199)

Why the changes that add control flow to existing tests?

llvm/test/Transforms/FunctionAttrs/noreturn_stackoverflow.ll

1 ↗

(On Diff #213199)

Thank you for adding this test.

7 ↗

(On Diff #213199)

Could you add some lines about what is supposed to happen in both overflow tests? Probably not everyone is familiar with Windows SEH.

31 ↗

(On Diff #213199)

My example showed that invoke ?overflow@@YAXXZ can leave through the unwind edge (even with the printf after the recursive call) and then return. Why is this then marked as noreturn?

If we want to allow the compiler to assume that stack overflow do not happen, including not throwing an SEH exception, I'd like to wait for the result of the RFC.

[nikic]

llvm/test/Transforms/FunctionAttrs/fn_noreturn.ll

83–84

Thanks for the comments, looks like I (and the Rust community as a whole) completely misunderstood LLVM's stance on this issue. I will submit a LangRef patch to clarify this.

[jdoerfert]

llvm/test/Transforms/FunctionAttrs/nofree-attributor.ll

70–78 ↗

(On Diff #213199)

because the test becomes meaningless otherwise, e.g., the instructions with the effect we want to test for (here free) would be dead.

llvm/test/Transforms/FunctionAttrs/noreturn_stackoverflow.ll

7 ↗

(On Diff #213199)

What is supposed to happen (except what is checked below)? I am not familiar with the windows SEH and I'm unsure why this actually matters. As the comment states, we ignore the possibility of a stackoverflow.

31 ↗

(On Diff #213199)

This is noreturn because it unconditionally invokes a function that is noreturn and nounwind and we do not handle other "exceptions".
The case where the invoked function is noreturn but not nounwind is below. There, the caller is neither marked as noreturn nor nounwind.

If we want to allow the compiler to assume that stack overflow do not happen, including not throwing an SEH exception

We already assume that and we already optimize under that assumptions (your test with O3 doesn't feature a stack overflow).

I'd like to wait for the result of the RFC.

I would prefer not to wait.
I'm unsure what you want to see here other than this behavior? Do you want to assume any function can throw SEH exceptions under windows? If that would be the result of a lang ref change we can disable this deduction under windows.

[jdoerfert]

Add more tests for invoke +noreturn [+nounwind] [+async exceptions].
The problematic behavior was fixed in

https://reviews.llvm.org/rG924d2138fce43e9bcca98d06dccad28927d74c26

and is tested now.

[Meinersbur]

LGTM

Thank you for adding the extensive test cases with different EHPersonalities.

[jdoerfert]

Closed by https://reviews.llvm.org/rGe83f303938a5

llvm/include/llvm/Transforms/IPO/Attributor.h

 /// NOTE: If the state obtained via getState() is the "worst possible", thus if
 ///       getState(),isValidState() returns false, no information provided
 ///       by this class should be used for reasoning.
 struct AbstractAttribute {
 
   /// 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
   /// \p AnchoredVal.
   AbstractAttribute(Value *AssociatedVal, Value &AnchoredVal)
       : AssociatedVal(AssociatedVal), AnchoredVal(AnchoredVal) {}
 
   /// An abstract attribute associated with and anchored at \p V.

llvm/lib/Transforms/IPO/Attributor.cpp

 #include "llvm/ADT/SmallPtrSet.h"
 #include "llvm/ADT/SmallVector.h"
 #include "llvm/ADT/Statistic.h"
 #include "llvm/Analysis/CallGraph.h"
 #include "llvm/Analysis/CallGraphSCCPass.h"
 #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"
 #include "llvm/Support/raw_ostream.h"
 #include <cassert>
 
 using namespace llvm;
 
 #define DEBUG_TYPE "attributor"
 
 STATISTIC(NumFnWithExactDefinition,
           "Number of function with exact definitions");
 STATISTIC(NumFnWithoutExactDefinition,
           "Number of function without exact definitions");
 
 STATISTIC(NumFnUniqueReturned, "Number of function with unique return");
 STATISTIC(NumFnKnownReturns, "Number of function with known return values");
 STATISTIC(NumFnArgumentReturned,
           "Number of function arguments marked returned");
 
+STATISTIC(NumFnNoReturn, "Number of functions marked noreturn");
+
 // TODO: Determine a good default value.
 static cl::opt<unsigned>
     MaxFixpointIterations("attributor-max-iterations", cl::Hidden,
                           cl::desc("Maximal number of fixpoint iterations."),
                           cl::init(32));
 
 static cl::opt<bool> DisableAttributor(
     "attributor-disable", cl::Hidden,
     cl::desc("Disable the attributor inter-procedural deduction pass."),
     cl::init(false));
 
 /// Logic operators for the change status enum class.
 ///
 ///{
 ChangeStatus llvm::operator|(ChangeStatus l, ChangeStatus r) {
   return l == ChangeStatus::CHANGED ? l : r;
 }
 ChangeStatus llvm::operator&(ChangeStatus l, ChangeStatus r) {
   return l == ChangeStatus::UNCHANGED ? l : r;
 }
 ///}
 
+/// 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 <typename BaseTy, BaseTy InitKnown, BaseTy InitAssumed>
+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<bool, 0, 1>;
+
 /// Helper to adjust the statistics.
 static void bookkeeping(AbstractAttribute::ManifestPosition MP,
                         const Attribute &Attr) {
   switch (Attr.getKindAsEnum()) {
   case Attribute::Returned:
     NumFnArgumentReturned++;
     return;
+  case Attribute::NoReturn:
+    NumFnNoReturn++;
+    return;
   default:
     return;
   }
 }
 
 /// Recursively collect returned values, starting from \p V but look through
 /// through select/phi/casts.
 static void collectValuesRecursively(
for (const Attribute &Attr : Attrs) {
       Arg.addAttr(Attr);
 
       // Bookkeeping.
       Changed = ChangeStatus::CHANGED;
       bookkeeping(MP_ARGUMENT, Attr);
     }
     break;
   }
+  case MP_FUNCTION: {
+    Function &F = cast<Function>(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;
 }
 
 /// --------------------- Function Return Values -------------------------------
 
 /// "Attribute" that collects all potential returned values and the return
ChangeStatus AAReturnedValuesImpl::updateImpl(Attributor &A) {
   if (!HasCallSite) {
     indicateFixpoint(/* Optimistic */ true);
     return ChangeStatus::CHANGED;
   }
 
   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<Function>(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<AANoReturn>(*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<ReturnInst *, 2> &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<AANoReturn>(*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<AAReturnedValuesImpl>(*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
 /// ----------------------------------------------------------------------------
 
 ChangeStatus Attributor::run(SmallVectorImpl<Function *> &SCC) {
   if (DisableAttributor)
     return ChangeStatus::UNCHANGED;
 
LLVM_DEBUG(dbgs() << "\n\n[Attributor] #Iteration: " << IterationCounter
                       << ", Worklist size: " << Worklist.size() << "\n");
 
     for (AbstractAttribute *ChangedAA : ChangedAAs) {
       auto &QuerriedAAs = QueryMap[ChangedAA];
       Worklist.insert(QuerriedAAs.begin(), QuerriedAAs.end());
     }
 
     ChangedAAs.clear();
 
     // Update all abstract attribute in the worklist.
     for (AbstractAttribute *AA : Worklist)
       if (AA->update(*this) == ChangeStatus::CHANGED)
         ChangedAAs.push_back(AA);
 
     Worklist.clear();
     Worklist.insert(ChangedAAs.begin(), ChangedAAs.end());
 
   } while (!Worklist.empty() && ++IterationCounter < MaxFixpointIterations);
 
   LLVM_DEBUG(dbgs() << "\n[Attributor] Fixpoint iteration done after: "
                     << IterationCounter << "/" << MaxFixpointIterations
                     << " iterations\n");
 
   // Reset abstract arguments not settled in a sound fixpoint by now.
   SmallPtrSet<AbstractAttribute *, 32> Visited;
   for (unsigned u = 0; u < ChangedAAs.size(); u++) {
     AbstractAttribute *ChangedAA = ChangedAAs[u];
     if (!Visited.insert(ChangedAA).second)
       continue;
 
     AbstractState &State = ChangedAA->getState();
void Attributor::identifyAbstractAttributes(Function &F) {
   // Return attributes are only appropriate if the return type is non void.
   Type *ReturnType = F.getReturnType();
   if (!ReturnType->isVoidTy()) {
     // Argument attribute "returned" --- Create only one per function even
     // though it is an argument attribute.
     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.
   auto &InstOpcodeMap = FuncInstOpcodeMap[&F];
   for (Instruction &I : instructions(&F)) {
     bool IsInteresting = false;
     switch (I.getOpcode()) {
     default:
raw_ostream &llvm::operator<<(raw_ostream &OS, ChangeStatus S) {
   return OS << (S == ChangeStatus::CHANGED ? "changed" : "unchanged");
 }
 
 raw_ostream &llvm::operator<<(raw_ostream &OS,
                               AbstractAttribute::ManifestPosition AP) {
   switch (AP) {
   case AbstractAttribute::MP_ARGUMENT:
     return OS << "arg";
+  case AbstractAttribute::MP_FUNCTION:
+    return OS << "fn";
   }
   llvm_unreachable("Unknown attribute position!");
 }
 
 raw_ostream &llvm::operator<<(raw_ostream &OS, const AbstractState &S) {
   return OS << (!S.isValidState() ? "top" : (S.isAtFixpoint() ? "fix" : ""));
 }
 

llvm/test/Transforms/FunctionAttrs/arg_returned.ll

 
 ; TEST 3
 ;
 ; int* ret0(int *a) {
 ;   return *a ? a : ret0(ret0(ret0(...ret0(a)...)));
 ; }
 ;
 ; 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
   %tobool = icmp ne i32 %v, 0
   %call = call i32* @ret0(i32* %a)
   %call1 = call i32* @ret0(i32* %call)
   %call2 = call i32* @ret0(i32* %call1)
   %call3 = call i32* @ret0(i32* %call2)
r:
   ret i32* %phi
 }
 
 
 attributes #0 = { noinline nounwind uwtable }
 
 ; 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 }

llvm/test/Transforms/FunctionAttrs/fn_noreturn.ll

 
 
 ; TEST 1
 ;
 ; void srec0() {
 ;   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:
   call void @srec0()
   ret void
 }
 
 
 ; TEST 2
 ;
 ; int srec16(int a) {
 ;   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:
   %call = call i32 @srec16(i32 %a)
   %call1 = call i32 @srec16(i32 %call)
   %call2 = call i32 @srec16(i32 %call1)
   %call3 = call i32 @srec16(i32 %call2)
   %call4 = call i32 @srec16(i32 %call3)
   %call5 = call i32 @srec16(i32 %call4)
   %call6 = call i32 @srec16(i32 %call5)
   %call7 = call i32 @srec16(i32 %call6)
   %call8 = call i32 @srec16(i32 %call7)

 
 
 ; TEST 3
 ;
 ; int endless_loop(int a) {
 ;   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:
   br label %while.body
 
 while.body:                                       ; preds = %entry, %while.body
   br label %while.body
 }
 
 
 ; TEST 4
 ;
 ; int endless_loop(int a) {
 ;   while (1);
 ;   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:
   br label %while.body
 
 while.body:                                       ; preds = %entry, %while.body
   br label %while.body
 
 return:                                           ; No predecessors!
   ret i32 %a
 }
 
 
 ; TEST 5
 ;
 ; int multiple_noreturn_calls(int a) {
 ;   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:
   %cmp = icmp eq i32 %a, 0
   br i1 %cmp, label %cond.true, label %cond.false
 
 cond.true:                                        ; preds = %entry
   %call = call i32 @endless_loop(i32 %a)
   br label %cond.end
 
 cond.false:                                       ; preds = %entry
   %call1 = call i32 @srec16(i32 %a)
   br label %cond.end
 
 cond.end:                                         ; preds = %cond.false, %cond.true
   %cond = phi i32 [ %call, %cond.true ], [ %call1, %cond.false ]
   ret i32 %cond
 }
 
 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 }