[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

883

llvm::all_of?

[jdoerfert]

llvm/lib/Transforms/IPO/Attributor.cpp

883

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

2036

no-return state?

[jdoerfert]

llvm/lib/Transforms/IPO/Attributor.cpp

2036

Good catch.

[Meinersbur]

llvm/lib/Transforms/IPO/Attributor.cpp

2022

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

Unrelated change?

llvm/test/Transforms/FunctionAttrs/fn_noreturn.ll

37

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

2022

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

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

37

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

Maybe add a TODO/FIXME remark about it?

llvm/test/Transforms/FunctionAttrs/fn_noreturn.ll

37

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

85

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

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

37

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.

85

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

85

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

85

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

85

@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

85

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

85

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

85

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/lib/Transforms/IPO/Attributor.cpp

 STATISTIC(NumFnWillReturn, "Number of functions marked willreturn");
 STATISTIC(NumFnArgumentNoAlias, "Number of function arguments marked noalias");
 STATISTIC(NumFnReturnedDereferenceable,
           "Number of function return values marked dereferenceable");
 STATISTIC(NumFnArgumentDereferenceable,
           "Number of function arguments marked dereferenceable");
 STATISTIC(NumCSArgumentDereferenceable,
           "Number of call site arguments marked dereferenceable");
+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
 // (when run with the first 5 abstract attributes). The results also indicate
 // that we never reach 32 iterations but always find a fixpoint sooner.
 //
 // This will become more evolved once we perform two interleaved fixpoint
case AbstractAttribute::MP_CALL_SITE_ARGUMENT:
       break;
     default:
       break;
     }
     break;
   case Attribute::WillReturn:
     NumFnWillReturn++;
     break;
+  case Attribute::NoReturn:
+    NumFnNoReturn++;
+    return;
   case Attribute::NoAlias:
     NumFnArgumentNoAlias++;
     return;
   default:
     return;
   }
 }
 
case Instruction::AtomicCmpXchg: {
     // Otherwise it is non-relaxed.
     if (Success != AtomicOrdering::Unordered &&
         Success != AtomicOrdering::Monotonic)
       return true;
     if (Failure != AtomicOrdering::Unordered &&
         Failure != AtomicOrdering::Monotonic)
       return true;
     return false;
   }
   default:
     llvm_unreachable(
         "New atomic operations need to be known in the attributor.");
   }
 
   // Relaxed.
   if (Ordering == AtomicOrdering::Unordered ||
       Ordering == AtomicOrdering::Monotonic)
ChangeStatus AADereferenceableCallSiteArgument::updateImpl(Attributor &A) {
   takeAssumedDerefBytesMinimum(
       computeAssumedDerefenceableBytes(A, V, IsNonNull, IsGlobal));
   updateAssumedNonNullGlobalState(IsNonNull, IsGlobal);
 
   return BeforeState == static_cast<DerefState>(*this) ? ChangeStatus::UNCHANGED
                                                        : ChangeStatus::CHANGED;
 }
 
+/// ------------------ Function No-Return Attribute ----------------------------
+struct AANoReturnFunction final : public AANoReturn, BooleanState {
+
+  AANoReturnFunction(Function &F, InformationCache &InfoCache)
+      : AANoReturn(F, InfoCache) {}
+
+  /// See AbstractAttribute::getState()
+  /// {
+  AbstractState &getState() override { return *this; }
+  const AbstractState &getState() const override { return *this; }
+  /// }
+
+  /// Return true if the underlying object is known to never return.
+  bool isKnownNoReturn() const override { return getKnown(); }
+
+  /// Return true if the underlying object is assumed to never return.
+  bool isAssumedNoReturn() const override { return getAssumed(); }
+
+  /// See AbstractAttribute::getManifestPosition().
+  ManifestPosition getManifestPosition() const override { return MP_FUNCTION; }
+
+  /// See AbstractAttribute::getAsStr().
+  const std::string getAsStr() const override {
+    return getAssumed() ? "noreturn" : "may-return";
+  }
+
+  /// See AbstractAttribute::initialize(...).
+  void initialize(Attributor &A) override {
+    Function &F = getAnchorScope();
+    if (F.hasFnAttribute(getAttrKind()))
+      indicateOptimisticFixpoint();
+  }
+
+  /// See AbstractAttribute::updateImpl(Attributor &A).
+  virtual ChangeStatus updateImpl(Attributor &A) override {
+    Function &F = getAnchorScope();
+
+    std::function<bool(Value &)> Pred = [](Value &) {
+      // Any potential return value means the function might return, thus it
+      // is not "no-return".
+      return false;
+    };
+
+    // Use the absence of returned values to justify no-return.
+    auto *AARetVal = A.getAAFor<AAReturnedValues>(*this, F);
+    if (AARetVal && AARetVal->checkForallReturnedValues(Pred)) {
+      if (AARetVal->getState().isAtFixpoint())
+        indicateOptimisticFixpoint();
+      return ChangeStatus::UNCHANGED;
+    }
+
+    // Fallthrough, reached if we failed to keep the no-capture state.
+    indicatePessimisticFixpoint();
+    return ChangeStatus::CHANGED;
+  }
+};
+
 /// ----------------------------------------------------------------------------
 ///                               Attributor
 /// ----------------------------------------------------------------------------
 
 bool Attributor::checkForAllCallSites(Function &F,
                                       std::function<bool(CallSite)> &Pred,
                                       bool RequireAllCallSites) {
   // We can try to determine information from
void Attributor::identifyDefaultAbstractAttributes(
   registerAA(*new AANoUnwindFunction(F, InfoCache));
 
   // Every function might be marked "nosync"
   registerAA(*new AANoSyncFunction(F, InfoCache));
 
   // Every function might be "no-free".
   registerAA(*new AANoFreeFunction(F, InfoCache));
 
+  // Every function might be "no-return".
+  registerAA(*new AANoReturnFunction(F, InfoCache));
+
   // 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.
     if (!Whitelist || Whitelist->count(AAReturnedValues::ID))
       registerAA(*new AAReturnedValuesImpl(F, InfoCache));
 

llvm/test/Transforms/FunctionAttrs/arg_nocapture.ll

 ; RUN: opt -functionattrs -attributor -attributor-disable=false -S < %s | FileCheck %s
-; RUN: opt -functionattrs -attributor -attributor-disable=false -attributor-verify=true -S < %s | FileCheck %s
 ;
 ; Test cases specifically designed for the "no-capture" argument attribute.
 ; We use FIXME's to indicate problems and missing attributes.
 ;
 target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
 
 ; TEST comparison against NULL
 ;

llvm/test/Transforms/FunctionAttrs/fn_noreturn.ll

 ; RUN: opt -functionattrs -attributor -attributor-disable=false -S < %s | FileCheck %s
-; RUN: opt -functionattrs -attributor -attributor-disable=false -attributor-verify=true -S < %s | FileCheck %s
 ;
 ; Test cases specifically designed for the "no-return" function attribute.
 ; We use FIXME's to indicate problems and missing attributes.
-;
-; TEST 1: singleton SCC void return type
-; TEST 2: singleton SCC int return type with a lot of recursive calls
-; TEST 3: endless loop, no return instruction
-; TEST 4: endless loop, dead return instruction
-; TEST 5: all paths contain a no-return function call
-;
+
 target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
 
 
-; TEST 1
+; TEST 1, singleton SCC void return type
 ;
 ; void srec0() {
 ;   return srec0();
 ; }
 ;
 ; FIXME: no-return missing
 ; CHECK: Function Attrs: nofree noinline nosync nounwind readnone uwtable
 ; CHECK: define void @srec0()
 ;
 define void @srec0() #0 {
 entry:
   call void @srec0()
   ret void
 }
 
 
-; TEST 2
+; TEST 2: singleton SCC int return type with a lot of recursive calls
 ;
 ; 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: Function Attrs: nofree noinline nosync nounwind readnone uwtable
+; CHECK: Function Attrs: nofree noinline noreturn nosync nounwind readnone uwtable
 ; CHECK: define i32 @srec16(i32 %a)
 ;
 define 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)
   %call9 = call i32 @srec16(i32 %call8)
   %call10 = call i32 @srec16(i32 %call9)
   %call11 = call i32 @srec16(i32 %call10)
   %call12 = call i32 @srec16(i32 %call11)
   %call13 = call i32 @srec16(i32 %call12)
   %call14 = call i32 @srec16(i32 %call13)
   %call15 = call i32 @srec16(i32 %call14)
+  br label %exit
+
+exit:
   ret i32 %call15
 }
 
 
-; TEST 3
+; TEST 3: endless loop, no return instruction
 ;
 ; int endless_loop(int a) {
 ;   while (1);
 ; }
 ;
-; FIXME: no-return missing
-; CHECK: Function Attrs: nofree noinline norecurse nosync nounwind readnone uwtable
+; CHECK: Function Attrs: nofree noinline norecurse noreturn nosync nounwind readnone uwtable
 ; CHECK: define i32 @endless_loop(i32 %a)
 ;
 define i32 @endless_loop(i32 %a) #0 {
 entry:
   br label %while.body
 
 while.body:                                       ; preds = %entry, %while.body
   br label %while.body
 }
 
 
-; TEST 4
+; TEST 4: endless loop, dead return instruction
 ;
 ; int endless_loop(int a) {
 ;   while (1);
 ;   return a;
 ; }
 ;
-; FIXME: no-return missing
+; FIXME: no-return missing (D65243 should fix this)
 ; CHECK: Function Attrs: nofree noinline norecurse nosync nounwind readnone uwtable
 ; CHECK: define i32 @dead_return(i32 returned %a)
 ;
 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!
   ret i32 %a
 }
 
 
-; TEST 5
+; TEST 5: all paths contain a no-return function call
 ;
 ; int multiple_noreturn_calls(int a) {
 ;   return a == 0 ? endless_loop(a) : srec16(a);
 ; }
 ;
-; FIXME: no-return missing
-; CHECK: Function Attrs: nofree noinline nosync nounwind readnone uwtable
+; CHECK: Function Attrs: nofree noinline noreturn nosync nounwind readnone uwtable
 ; CHECK: define i32 @multiple_noreturn_calls(i32 %a)
 ;
 define 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