[FuncAttrs] Add willreturn to readonly callsites in mustprogress fns.

[fhahn]

Summary

willreturn is now required by a number of passes in order to remove
function calls. Currently we fail to eliminate readonly function calls
in mustprogress functions, because we do not combine the mustprogress
info of the containing function with the readonly info at call sites.

This can lead to situations where calls that are guaranteed to return
are not eliminated from C++ code, as discussed on llvm-dev.
(https://lists.llvm.org/pipermail/llvm-dev/2021-February/148596.html)

This patch updates FunctionAttrs to add willreturn to readonly call
sites in mustprogress functions or willreturn function. This also allows
adding willreturn to the containing function, if all function calls can
be marked as willreturn.

Markgin callsites in a willreturn function as willreturn, can also be
helpful in the presence of inlining. There is a potentialcyclic dependency
between adding willreturn to functions and callsites in a function:
adding willreturn to callsites first enables adding willreturn to the
function in some cases. But adding willreturn to a function first
enables adding willreturn to more callsites.

For now, add it to callsites first.

[jeroen.dobbelaere]

llvm/lib/Transforms/IPO/FunctionAttrs.cpp

1508

Changed should be orred here.

[jdoerfert]

llvm/lib/Transforms/IPO/FunctionAttrs.cpp

1449

The comment is confusing. If the caller is willreturn the call site behavior doesn't matter. If the caller is "only" mustprogress the call site behavior matters.

1464

You could track if any call was not willreturn to avoid doing so in functionWillReturn.

[jdoerfert]

accidentally accepted, I think the logic is fine. I keep it under review in case you decide to do more than the two nits and reuse the traversal result. If not, the logic looks OK to me

[nikic]

After D96960 I don't think this change is really necessary anymore (at least it does not need an LLVM 12 backport). If the language has forward progress, then all function definitions will get annotated anyway, so only extern declarations are relevant. However, those will not be readyonly either -- unless they are explicitly annotated such, in which case they will also be annotated as willreturn after D96960.

(I do think that doing callsite attribute inference is *generally* valuable, the comment here is more along the lines that it does not seem necessary to implement this as a quick fix for just willreturn to prevent regressions.)

[jeroen.dobbelaere]

In D96949#2571873, @nikic wrote:

After D96960 I don't think this change is really necessary anymore (at least it does not need an LLVM 12 backport). If the language has forward progress, then all function definitions will get annotated anyway, so only extern declarations are relevant. However, those will not be readyonly either -- unless they are explicitly annotated such, in which case they will also be annotated as willreturn after D96960.

I am not sure if this is completely true. When looking at the test changes for D96960, I have the impression that a lot of __builtin_xxx functions might also need the 'willreturn' attribute. (and for 'C', it should be clang that adds the attribute).

[fhahn]

addressed comments.

In D96949#2571913, @jeroen.dobbelaere wrote:

In D96949#2571873, @nikic wrote:

After D96960 I don't think this change is really necessary anymore (at least it does not need an LLVM 12 backport). If the language has forward progress, then all function definitions will get annotated anyway, so only extern declarations are relevant. However, those will not be readyonly either -- unless they are explicitly annotated such, in which case they will also be annotated as willreturn after D96960.

I am not sure if this is completely true. When looking at the test changes for D96960, I have the impression that a lot of __builtin_xxx functions might also need the 'willreturn' attribute. (and for 'C', it should be clang that adds the attribute).

For C++ only, D96960 is probably sufficient.

But I think it should still be helpful when doing LTO with mixed C/C++ code (a C function definition can be determined to be readonly and will be willreturn when called in a C++ function). And there are other languages with different ways of marking functions as readonly.

[jdoerfert]

FWIW, having call site deduction is generally helpful, also for willreturn. I'd much rather spend time on a lightweight Attributor pass than this though, there it is part of the overall model anyway.

[fhahn]

llvm/lib/Transforms/IPO/FunctionAttrs.cpp

1449

updated

1464

I updated the code but due to the early exit I think we need to track the possibility that we did not analyze the call sites, so unfortunately it's a bit more complicated.

[jdoerfert]

llvm/lib/Transforms/IPO/FunctionAttrs.cpp

1464

Yeah, I see that now. The design here was not meant to couple those things. Unsure if this is better :(

1468

[nikic]

In D96949#2571913, @jeroen.dobbelaere wrote:

I am not sure if this is completely true. When looking at the test changes for D96960, I have the impression that a lot of __builtin_xxx functions might also need the 'willreturn' attribute. (and for 'C', it should be clang that adds the attribute).

That may well be, but in that case we really need to get the attribute directly on the __builtin functions, otherwise the issue would persist for C.

Do you have any particular examples? I would expect that most builtins get lowered to intrinsics and those should already have all the necessary attributes, but there's probably some cases that fell through.

[jeroen.dobbelaere]

In D96949#2571994, @nikic wrote:

Do you have any particular examples? I would expect that most builtins get lowered to intrinsics and those should already have all the necessary attributes, but there's probably some cases that fell through.

I am not able to figure out a useful one, based on the list in clang/test/CodeGen/complex-builtins.c and clang/test/CodeGen/complex-libcalls.c.
I do see expected optimization to happen, but at the same time I am not seeing that they get annotated with 'willreturn'.

[jdoerfert]

Reverse ping

llvm/lib/Transforms/IPO/FunctionAttrs.cpp

1468

Or even hoist to the continue above.

llvm/include/llvm/IR/InstrTypes.h

public:
 
   /// Determine if the call does not access or only reads memory.
   bool onlyReadsMemory() const {
     return doesNotAccessMemory() || hasFnAttr(Attribute::ReadOnly);
   }
 
   /// Returns true if this function is guaranteed to return.
   bool willReturn() const { return hasFnAttr(Attribute::WillReturn); }
+  void setWillReturn() {
+    addAttribute(AttributeList::FunctionIndex, Attribute::WillReturn);
+  }
 
   void setOnlyReadsMemory() {
     addAttribute(AttributeList::FunctionIndex, Attribute::ReadOnly);
   }
 
   /// Determine if the call does not access or only writes memory.
   bool doesNotReadMemory() const {
     return doesNotAccessMemory() || hasFnAttr(Attribute::WriteOnly);

llvm/lib/Transforms/IPO/FunctionAttrs.cpp

if (none_of(*F, basicBlockCanReturn)) {
       F->setDoesNotReturn();
       Changed = true;
     }
   }
 
   return Changed;
 }
 
-static bool functionWillReturn(const Function &F) {
+namespace {
+/// Helper to indicate whether all call sites in a function are willreturn, may
+/// return or that status is unknown because no analysis was done.
+enum class CallsiteStatusTy { AllWillReturn, MayNotReturn, Unknown };
+} // namespace
+
+// Add willreturn to callsites in F, if possible.
+static std::pair<bool, CallsiteStatus> callsitesWillReturn(Function &F) {
+  // Can only analyze functions with a definition.
+  if (F.isDeclaration())
+    return {false, CallsiteStatus::Unknown};
+
+  bool FnWillReturn = F.willReturn();
+  // Unless F must make progress or willreturn, we cannot add willreturn at
+  // callsites in the function.
+  if (!F.mustProgress() && !FnWillReturn)
+    return {false, CallsiteStatus::Unknown};
+
+  bool Changed = false;
+  CallsiteStatus AllCallsWillReturn = CallsiteStatus::AllWillReturn;
+  // Add willreturn to all callsites that only read memory or if the function
+  // itself is willreturn.
+  for (Instruction &I : instructions(F)) {
+    auto *CB = dyn_cast<CallBase>(&I);
+    if (!CB)
+      continue;
+
+    if (FnWillReturn || CB->onlyReadsMemory()) {
+      if (CB->willReturn())
+        continue;
+      CB->setWillReturn();
+      Changed = true;
+    } else {
+      AllCallsWillReturn = CallsiteStatus::MayNotReturn;
+    }
+  }
+  return {Changed, AllCallsWillReturn};
+}
+
+static bool functionWillReturn(const Function &F, CallsiteStatus CS) {
   // Must-progress function without side-effects must return.
   if (F.mustProgress() && F.onlyReadsMemory())
     return true;
 
   // Can only analyze functions with a definition.
   if (F.isDeclaration())
     return false;
 
   // Functions with loops require more sophisticated analysis, as the loop
   // may be infinite. For now, don't try to handle them.
   SmallVector<std::pair<const BasicBlock *, const BasicBlock *>> Backedges;
   FindFunctionBackedges(F, Backedges);
   if (!Backedges.empty())
     return false;
 
   // If there are no loops, then the function is willreturn if all calls in
   // it are willreturn.
+  if (CS == CallsiteStatus::Unknown)
     return all_of(instructions(F), [](const Instruction &I) {
       const auto *CB = dyn_cast<CallBase>(&I);
-    return !CB || CB->hasFnAttr(Attribute::WillReturn);
+      return !CB || CB->willReturn();
     });
+  return CS == CallsiteStatus::AllWillReturn;
 }
 
 // Set the willreturn function attribute if possible.
 static bool addWillReturn(const SCCNodeSet &SCCNodes) {
   bool Changed = false;
 
   for (Function *F : SCCNodes) {
-    if (!F || F->willReturn() || !functionWillReturn(*F))
+    if (!F)
       continue;
+    bool Modified;
+    CallsiteStatus CSStatus;
+    std::tie(Modified, CSStatus) = callsitesWillReturn(*F);
+    Changed |= Modified;
 
+    if (F->willReturn() || !functionWillReturn(*F, CSStatus))
+      continue;
     F->setWillReturn();
     NumWillReturn++;
     Changed = true;
   }
 
   return Changed;
 }
 

llvm/test/Transforms/FunctionAttrs/willreturn-callsites.ll

 ; RUN: opt -function-attrs -S %s | FileCheck %s
 
 declare void @decl_readonly() readonly
 declare void @decl_readnone() readnone
 declare void @decl_argmemonly(i32*) argmemonly
 declare void @decl_unknown()
 
 define void @test_fn_mustprogress(i32* %ptr) mustprogress {
 ; CHECK: Function Attrs: mustprogress
 ; CHECK-LABEL: @test_fn_mustprogress(
-; CHECK-NOT:     call void @decl_readonly() #
-; CHECK-NOT:     call void @decl_readnone() #
+; CHECK-NEXT:    call void @decl_readonly() [[WILLRETURN:#.*]]
+; CHECK-NEXT:    call void @decl_readnone() [[WILLRETURN]]
 ; CHECK-NOT:     call void @decl_unknown() #
 ; CHECK-NOT:     call void @decl_argmemonly(i32* [[PTR:%.*]]) #
 ; CHECK:         ret void
 ;
   call void @decl_readonly()
   call void @decl_readnone()
   call void @decl_unknown()
   call void @decl_argmemonly(i32* %ptr)
   ret void
 }
 
 define void @test_fn_willreturn(i32* %ptr) willreturn {
 ; CHECK: Function Attrs: willreturn
 ; CHECK-LABEL: @test_fn_willreturn(
-; CHECK-NOT:     call void @decl_readonly() #
-; CHECK-NOT :    call void @decl_readnone() #
-; CHECK-NOT:     call void @decl_unknown() #
-; CHECK-NOT:     call void @decl_argmemonly(i32* [[PTR:%.*]]) #
-; CHECK:         ret void
+; CHECK-NEXT:    call void @decl_readonly() [[WILLRETURN]]
+; CHECK-NEXT:    call void @decl_readnone() [[WILLRETURN]]
+; CHECK-NEXT:    call void @decl_unknown() [[WILLRETURN]]
+; CHECK-NEXT:    call void @decl_argmemonly(i32* [[PTR:%.*]]) [[WILLRETURN]]
+; CHECK-NEXT:    ret void
 ;
   call void @decl_readonly()
   call void @decl_readnone()
   call void @decl_unknown()
   call void @decl_argmemonly(i32* %ptr)
   ret void
 }
 
 define void @test_fn_mustprogress_readonly_calls(i32* %ptr) mustprogress {
 ; CHECK: Function Attrs: readonly willreturn mustprogress
 ; CHECK-LABEL: @test_fn_mustprogress_readonly_calls(
-; CHECK-NOT:     call void @decl_readonly() #
-; CHECK-NOT:     call void @decl_readnone() #
-; CHECK:         ret void
+; CHECK-NEXT:    call void @decl_readonly() [[WILLRETURN]]
+; CHECK-NEXT:    call void @decl_readnone() [[WILLRETURN]]
+; CHECK-NEXT:    ret void
 ;
   call void @decl_readonly()
   call void @decl_readnone()
   ret void
 }
 
 define void @test_fn_mustprogress_readonly_calls_but_stores(i32* %ptr) mustprogress {
-; CHECK: Function Attrs: nofree mustprogress
+; CHECK: Function Attrs: nofree willreturn mustprogress
 ; CHECK-LABEL: @test_fn_mustprogress_readonly_calls_but_stores(
-; CHECK-NOT:     call void @decl_readonly() #
-; CHECK-NOT:     call void @decl_readnone() #
-; CHECK:         store i32 0, i32* [[PTR:%.*]], align 4
+; CHECK-NEXT:    call void @decl_readonly() [[WILLRETURN]]
+; CHECK-NEXT:    call void @decl_readnone() [[WILLRETURN]]
+; CHECK-NEXT:    store i32 0, i32* [[PTR:%.*]], align 4
 ; CHECK-NEXT:    ret void
 ;
   call void @decl_readonly()
   call void @decl_readnone()
   store i32 0, i32* %ptr
   ret void
 }
+
+; CHECK: attributes [[WILLRETURN]] = { willreturn }