[FunctionAttrs] Infer willreturn for functions without loops

[nikic]

Summary

If a function doesn't contain loops and does not call non-willreturn functions, then it is willreturn. Handling of the loop case is left as an exercise to the reader ;)

I think this should give us enough inference to move forward with D94106.

[jdoerfert]

I still think we should check to enable a light-attributor run in the beginning of the pipeline. The logic seems sound, could be improved since this does initialize the fixpoint computation with a pessimistic starting value. One comment below, the rest is OK for merging.

lib/Transforms/IPO/FunctionAttrs.cpp

1443

I never used this function. Does it handle irreducible control flow properly? Maybe we want a test just to be sure.

[nikic]

Add test for infinite recursion and irreducible flow.

[nikic]

In D94633#2498420, @jdoerfert wrote:

I still think we should check to enable a light-attributor run in the beginning of the pipeline.

I was hoping to get the willreturn-related bugs fixed in time for LLVM 12, so sticking to the existing infrastructure seems like the safer bet :) It probably makes more sense to enable the attributor after branching rather than before.

The logic seems sound, could be improved since this does initialize the fixpoint computation with a pessimistic starting value. One comment below, the rest is OK for merging.

I thought about this, but I don't think that we can use an optimistic fixpoint here without some much more sophisticated analysis. Just naively assuming "willreturn until proven otherwise" will incorrectly mark infinite recursion as willreturn:

; Not willreturn.
define void @willreturn_recursion() {
  tail call void @willreturn_recursion()
  ret void
}

Without mustprogress, I believe that function is well-defined (or at least with musttail it's well-defined for sure). Inferring willreturn for a non-trivial SCC (without mustprogress) would require proving that the recursion is finite. And as the current code doesn't even handle finite loops, this is a bit out of scope...

lib/Transforms/IPO/FunctionAttrs.cpp

1443

I believe it will just pick some possible choice of backedges for the irreducible case, which is good enough for this purpose. I've added a test.

[fhahn]

lib/Transforms/IPO/FunctionAttrs.cpp

1441

We do not really need to find all back edges, wouldn't it be sufficient to just traverse the CFG and exit once we found a cycle?

1447

You could use the instruction() iterator range to directly iterate over all instructions, e.g.

return all_of(instructions(F), [](const Instruction &I){
  const auto *CB = dyn_cast<CallBase>(&I);
  return !CB || CB->hasFnAttr(Attribute::WillReturn);
});

[nikic]

Use all_of(instructions(F)).

[nikic]

lib/Transforms/IPO/FunctionAttrs.cpp

1441

I don't think FindFunctionBackedges is expensive enough to warrant reimplementing it here. Note that just keeping a visited set doesn't cut it, as that would detect any join point. You need to perform a DFS search, and doing that non-recursively is ugly enough that I'd rather not repeat it.

[jdoerfert]

EDIT: I'm fine with this patch, FWIW.

In D94633#2498642, @nikic wrote:

In D94633#2498420, @jdoerfert wrote:

I still think we should check to enable a light-attributor run in the beginning of the pipeline.

I was hoping to get the willreturn-related bugs fixed in time for LLVM 12, so sticking to the existing infrastructure seems like the safer bet :) It probably makes more sense to enable the attributor after branching rather than before.

Fair. As I said, we can enable it in a restricted, lightweight mode first. Could you remind me which bugs?

The logic seems sound, could be improved since this does initialize the fixpoint computation with a pessimistic starting value. One comment below, the rest is OK for merging.

I thought about this, but I don't think that we can use an optimistic fixpoint here without some much more sophisticated analysis. Just naively assuming "willreturn until proven otherwise" will incorrectly mark infinite recursion as willreturn:

; Not willreturn.
define void @willreturn_recursion() {
  tail call void @willreturn_recursion()
  ret void
}

So, I run this through the Attributor: https://opt.godbolt.org/z/TqsK86
Not what we were looking for, so here is the non-trivial version: https://opt.godbolt.org/z/rbeedM

Without mustprogress, I believe that function is well-defined (or at least with musttail it's well-defined for sure). Inferring willreturn for a non-trivial SCC (without mustprogress) would require proving that the recursion is finite. And as the current code doesn't even handle finite loops, this is a bit out of scope...

I don't disagree. My concern is that we should add more sophisitcated the logic in the Attributor instead. We had some initial patches wrt. finite loops, but I don't think they went in.

[nikic]

In D94633#2498743, @jdoerfert wrote:

EDIT: I'm fine with this patch, FWIW.

In D94633#2498642, @nikic wrote:

In D94633#2498420, @jdoerfert wrote:

I still think we should check to enable a light-attributor run in the beginning of the pipeline.

I was hoping to get the willreturn-related bugs fixed in time for LLVM 12, so sticking to the existing infrastructure seems like the safer bet :) It probably makes more sense to enable the attributor after branching rather than before.

Fair. As I said, we can enable it in a restricted, lightweight mode first. Could you remind me which bugs?

D94106 fixes the important one, though isGuaranteedToTransferExecutionToSuccessor is also buggy for languages without forward progress. Functions with infinite loops getting optimized away is the number one Rust miscompile by quite a margin...

The logic seems sound, could be improved since this does initialize the fixpoint computation with a pessimistic starting value. One comment below, the rest is OK for merging.

I thought about this, but I don't think that we can use an optimistic fixpoint here without some much more sophisticated analysis. Just naively assuming "willreturn until proven otherwise" will incorrectly mark infinite recursion as willreturn:

; Not willreturn.
define void @willreturn_recursion() {
  tail call void @willreturn_recursion()
  ret void
}

So, I run this through the Attributor: https://opt.godbolt.org/z/TqsK86
Not what we were looking for, so here is the non-trivial version: https://opt.godbolt.org/z/rbeedM

Just to make sure we're on the same page, both of those would be bugs in attributor right? The first one shouldn't be unreachable, and the second one shouldn't be willreturn, at least not without more information than is contained in that IR.

lib/Transforms/IPO/FunctionAttrs.cpp

1441

I ran some tests to check the compile-time impact. For this patch as-is: https://llvm-compile-time-tracker.com/compare.php?from=17fb21f875f4aaf6ad2cf9499cb75d76588167f2&to=335a834be8fe9a571fdbeea1262989c704ba91cf&stat=instructions There is a 0.1% regression. However, if I comment out the setWillReturn call, I get: http://llvm-compile-time-tracker.com/compare.php?from=17fb21f875f4aaf6ad2cf9499cb75d76588167f2&to=1b9a75cff1543e5ca29dea0dd56b111312901d98&stat=instructions So it seems that the impact here is due to second-order effects. The FindFunctionBackedges call itself doesn't appear to be problematic.

[jdoerfert]

In D94633#2499063, @nikic wrote:

In D94633#2498743, @jdoerfert wrote:

EDIT: I'm fine with this patch, FWIW.

In D94633#2498642, @nikic wrote:

In D94633#2498420, @jdoerfert wrote:

I still think we should check to enable a light-attributor run in the beginning of the pipeline.

I was hoping to get the willreturn-related bugs fixed in time for LLVM 12, so sticking to the existing infrastructure seems like the safer bet :) It probably makes more sense to enable the attributor after branching rather than before.

Fair. As I said, we can enable it in a restricted, lightweight mode first. Could you remind me which bugs?

D94106 fixes the important one, though isGuaranteedToTransferExecutionToSuccessor is also buggy for languages without forward progress. Functions with infinite loops getting optimized away is the number one Rust miscompile by quite a margin...

Right. We should not delete non-mustprogress non-side-effect calls. Probably requires changes in a few more places.

The logic seems sound, could be improved since this does initialize the fixpoint computation with a pessimistic starting value. One comment below, the rest is OK for merging.

I thought about this, but I don't think that we can use an optimistic fixpoint here without some much more sophisticated analysis. Just naively assuming "willreturn until proven otherwise" will incorrectly mark infinite recursion as willreturn:

; Not willreturn.
define void @willreturn_recursion() {
  tail call void @willreturn_recursion()
  ret void
}

So, I run this through the Attributor: https://opt.godbolt.org/z/TqsK86
Not what we were looking for, so here is the non-trivial version: https://opt.godbolt.org/z/rbeedM

Just to make sure we're on the same page, both of those would be bugs in attributor right? The first one shouldn't be unreachable, and the second one shouldn't be willreturn, at least not without more information than is contained in that IR.

I agree for the first one. Mustprogress is missing for unreachable to correct. The second one is correct, or am I missing something?

[nikic]

In D94633#2499465, @jdoerfert wrote:

The logic seems sound, could be improved since this does initialize the fixpoint computation with a pessimistic starting value. One comment below, the rest is OK for merging.

I thought about this, but I don't think that we can use an optimistic fixpoint here without some much more sophisticated analysis. Just naively assuming "willreturn until proven otherwise" will incorrectly mark infinite recursion as willreturn:

; Not willreturn.
define void @willreturn_recursion() {
  tail call void @willreturn_recursion()
  ret void
}

So, I run this through the Attributor: https://opt.godbolt.org/z/TqsK86
Not what we were looking for, so here is the non-trivial version: https://opt.godbolt.org/z/rbeedM

Just to make sure we're on the same page, both of those would be bugs in attributor right? The first one shouldn't be unreachable, and the second one shouldn't be willreturn, at least not without more information than is contained in that IR.

I agree for the first one. Mustprogress is missing for unreachable to correct. The second one is correct, or am I missing something?

Nope, the second one is indeed correct, I misread the output. Sorry for the noise!

[nikic]

Any further concerns for this change?

[jdoerfert]

LGTM

[nikic]

lib/Transforms/IPO/FunctionAttrs.cpp

1441

I've looked a bit closer into what causes the compile-time regression, and apparently it is the setWillReturn() call itself. Adding an attribute is quite expensive (we create AttributeBuilders for the original attributes and the new attribute, merge them, reconstruct an attribute set from that, look up the interned set...) Something that can be optimized, but otherwise not related to this patch.

lib/Transforms/IPO/FunctionAttrs.cpp

 #include "llvm/ADT/SCCIterator.h"
 #include "llvm/ADT/STLExtras.h"
 #include "llvm/ADT/SetVector.h"
 #include "llvm/ADT/SmallPtrSet.h"
 #include "llvm/ADT/SmallVector.h"
 #include "llvm/ADT/Statistic.h"
 #include "llvm/Analysis/AssumptionCache.h"
 #include "llvm/Analysis/BasicAliasAnalysis.h"
+#include "llvm/Analysis/CFG.h"
 #include "llvm/Analysis/CGSCCPassManager.h"
 #include "llvm/Analysis/CallGraph.h"
 #include "llvm/Analysis/CallGraphSCCPass.h"
 #include "llvm/Analysis/CaptureTracking.h"
 #include "llvm/Analysis/LazyCallGraph.h"
 #include "llvm/Analysis/MemoryBuiltins.h"
 #include "llvm/Analysis/MemoryLocation.h"
 #include "llvm/Analysis/ValueTracking.h"
if (none_of(*F, basicBlockCanReturn)) {
       F->setDoesNotReturn();
       Changed = true;
     }
   }
 
   return Changed;
 }
 
+static bool functionWillReturn(const Function &F) {
+  // 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.
+  return all_of(instructions(F), [](const Instruction &I) {
+    const auto *CB = dyn_cast<CallBase>(&I);
+    return !CB || CB->hasFnAttr(Attribute::WillReturn);
+  });
+}
+
 // Set the willreturn function attribute if possible.
 static bool addWillReturn(const SCCNodeSet &SCCNodes) {
   bool Changed = false;
 
   for (Function *F : SCCNodes) {
-    if (!F || !F->onlyReadsMemory() || !F->mustProgress() || F->willReturn())
+    if (!F || F->willReturn() || !functionWillReturn(*F))
       continue;
 
     F->setWillReturn();
     NumWillReturn++;
     Changed = true;
   }
 
   return Changed;

test/Analysis/TypeBasedAliasAnalysis/functionattrs.ll

 define i32 @test3_no(i8* %p) nounwind {
   %t = va_arg i8* %p, i32, !tbaa !2
   ret i32 %t
 }
 
 declare void @callee(i32* %p) nounwind
 declare void @llvm.memcpy.p0i8.p0i8.i64(i8*, i8*, i64, i1) nounwind
 
-; CHECK: attributes #0 = { norecurse nounwind readnone }
-; CHECK: attributes #1 = { nofree norecurse nounwind writeonly }
+; CHECK: attributes #0 = { norecurse nounwind readnone willreturn }
+; CHECK: attributes #1 = { nofree norecurse nounwind willreturn writeonly }
 ; CHECK: attributes #2 = { nounwind readonly }
 ; CHECK: attributes #3 = { nounwind }
-; CHECK: attributes #4 = { nounwind readnone }
-; CHECK: attributes #5 = { nofree nounwind }
-; CHECK: attributes #6 = { nofree norecurse nounwind }
+; CHECK: attributes #4 = { nounwind readnone willreturn }
+; CHECK: attributes #5 = { nofree nounwind willreturn }
+; CHECK: attributes #6 = { nofree norecurse nounwind willreturn }
 ; CHECK: attributes #7 = { argmemonly nofree nosync nounwind willreturn }
 
 ; Root note.
 !0 = !{ }
 
 ; Invariant memory.
 !1 = !{!3, !3, i64 0, i1 1 }
 ; Not invariant memory.
 !2 = !{!3, !3, i64 0, i1 0 }
 !3 = !{ !"foo", !0 }

test/CodeGen/AMDGPU/inline-attr.ll

 ; RUN: opt -mtriple=amdgcn--amdhsa -S -O3 -enable-unsafe-fp-math %s  | FileCheck -check-prefix=GCN -check-prefix=UNSAFE %s
 ; RUN: opt -mtriple=amdgcn--amdhsa -S -O3 -enable-no-nans-fp-math %s | FileCheck -check-prefix=GCN -check-prefix=NONANS %s
 ; RUN: opt -mtriple=amdgcn--amdhsa -S -O3 -enable-no-infs-fp-math %s | FileCheck -check-prefix=GCN -check-prefix=NOINFS %s
 
 ; GCN: define float @foo(float %x) local_unnamed_addr #0 {
 ; GCN: define amdgpu_kernel void @caller(float addrspace(1)* nocapture %p) local_unnamed_addr #1 {
 ; GCN: %mul.i = fmul float %load, 1.500000e+01
 
-; UNSAFE: attributes #0 = { norecurse nounwind readnone "unsafe-fp-math"="true" }
-; UNSAFE: attributes #1 = { nofree norecurse nounwind "less-precise-fpmad"="false" "no-infs-fp-math"="false" "no-nans-fp-math"="false" "unsafe-fp-math"="true" }
+; UNSAFE: attributes #0 = { norecurse nounwind readnone willreturn "unsafe-fp-math"="true" }
+; UNSAFE: attributes #1 = { nofree norecurse nounwind willreturn "less-precise-fpmad"="false" "no-infs-fp-math"="false" "no-nans-fp-math"="false" "unsafe-fp-math"="true" }
 
-; NOINFS: attributes #0 = { norecurse nounwind readnone "no-infs-fp-math"="true" }
-; NOINFS: attributes #1 = { nofree norecurse nounwind "less-precise-fpmad"="false" "no-infs-fp-math"="true" "no-nans-fp-math"="false" "unsafe-fp-math"="false" }
+; NOINFS: attributes #0 = { norecurse nounwind readnone willreturn "no-infs-fp-math"="true" }
+; NOINFS: attributes #1 = { nofree norecurse nounwind willreturn "less-precise-fpmad"="false" "no-infs-fp-math"="true" "no-nans-fp-math"="false" "unsafe-fp-math"="false" }
 
-; NONANS: attributes #0 = { norecurse nounwind readnone "no-nans-fp-math"="true" }
-; NONANS: attributes #1 = { nofree norecurse nounwind "less-precise-fpmad"="false" "no-infs-fp-math"="false" "no-nans-fp-math"="true" "unsafe-fp-math"="false" }
+; NONANS: attributes #0 = { norecurse nounwind readnone willreturn "no-nans-fp-math"="true" }
+; NONANS: attributes #1 = { nofree norecurse nounwind willreturn "less-precise-fpmad"="false" "no-infs-fp-math"="false" "no-nans-fp-math"="true" "unsafe-fp-math"="false" }
 
 define float @foo(float %x) #0 {
 entry:
   %mul = fmul float %x, 1.500000e+01
   ret float %mul
 }
 
 define amdgpu_kernel void @caller(float addrspace(1)* %p) #1 {

test/CodeGenOpenCL/convergent.cl

 
 // CHECK-LABEL: @assume_convergent_asm
 // CHECK: tail call void asm sideeffect "s_barrier", ""() #5
 kernel void assume_convergent_asm()
 {
   __asm__ volatile("s_barrier");
 }
 
-// CHECK: attributes #0 = { nofree noinline norecurse nounwind "
+// CHECK: attributes #0 = { nofree noinline norecurse nounwind willreturn "
 // CHECK: attributes #1 = { {{[^}]*}}convergent{{[^}]*}} }
 // CHECK: attributes #2 = { {{[^}]*}}convergent{{[^}]*}} }
 // CHECK: attributes #3 = { {{[^}]*}}convergent noduplicate{{[^}]*}} }
 // CHECK: attributes #4 = { {{[^}]*}}convergent{{[^}]*}} }
 // CHECK: attributes #5 = { {{[^}]*}}convergent{{[^}]*}} }
 // CHECK: attributes #6 = { {{[^}]*}}convergent noduplicate{{[^}]*}} }

test/Transforms/FunctionAttrs/atomic.ll

 ; A function with an Acquire load is not readonly.
 define i32 @test2(i32* %x) uwtable ssp {
 ; CHECK: define i32 @test2(i32* nocapture readonly %x) #1 {
 entry:
   %r = load atomic i32, i32* %x seq_cst, align 4
   ret i32 %r
 }
 
-; CHECK: attributes #0 = { norecurse nounwind readnone ssp uwtable }
-; CHECK: attributes #1 = { nofree norecurse nounwind ssp uwtable }
+; CHECK: attributes #0 = { norecurse nounwind readnone ssp uwtable willreturn }
+; CHECK: attributes #1 = { nofree norecurse nounwind ssp uwtable willreturn }

test/Transforms/FunctionAttrs/incompatible_fn_attrs.ll

 ; CHECK: define i32* @given_inaccessible_or_argmem_infer_readnone(i32* readnone returned %p) #0 {
 entry:
   ret i32* %p
 }
 
 attributes #0 = { argmemonly }
 attributes #1 = { inaccessiblememonly }
 attributes #2 = { inaccessiblemem_or_argmemonly }
-; CHECK: attributes #0 = { norecurse nounwind readnone }
+; CHECK: attributes #0 = { norecurse nounwind readnone willreturn }
 ; CHECK-NOT: attributes

test/Transforms/FunctionAttrs/nofree.ll

 attributes #2 = { nounwind }
 attributes #3 = { norecurse nounwind readonly uwtable }
 attributes #4 = { nobuiltin nounwind }
 attributes #5 = { builtin nounwind }
 
 ; CHECK: attributes #0 = { uwtable }
 ; CHECK: attributes #1 = { nounwind uwtable }
 ; CHECK: attributes #2 = { nounwind }
-; CHECK: attributes #3 = { norecurse nounwind readonly uwtable }
+; CHECK: attributes #3 = { norecurse nounwind readonly uwtable willreturn }
 ; CHECK: attributes #4 = { nobuiltin nounwind }
 ; CHECK: attributes #5 = { builtin nounwind }
 

test/Transforms/FunctionAttrs/optnone.ll

; CHECK: (i8* %p) #1 {
   ret void
 }
 
 declare i8 @strlen(i8*) noinline optnone
 ; CHECK-LABEL: @strlen
 ; CHECK: (i8*) #1
 
 ; CHECK-LABEL: attributes #0
-; CHECK: = { norecurse nounwind readnone }
+; CHECK: = { norecurse nounwind readnone willreturn }
 ; CHECK-LABEL: attributes #1
 ; CHECK: = { noinline optnone }

test/Transforms/FunctionAttrs/willreturn.ll

A:
   ret i64 10
 
 B:
   %val = landingpad { i8*, i32 }
            catch i8* null
   ret i64 0
 }
 
+; Function without loops or non-willreturn calls will return.
 define void @willreturn_no_loop(i1 %c, i32* %p) {
-; CHECK-NOT: Function Attrs: {{.*}}willreturn
-; CHECK: define void @willreturn_no_loop(
+; CHECK: Function Attrs: willreturn
+; CHECK-NEXT: define void @willreturn_no_loop(
 ;
   br i1 %c, label %if, label %else
 
 if:
   load atomic i32, i32* %p seq_cst, align 4
   call void @fn_willreturn()
   br label %end
 
 else:
   store atomic i32 0, i32* %p seq_cst, align 4
   br label %end
 
 end:
   ret void
 }
 
+; Calls a function that is not guaranteed to return, not willreturn.
 define void @willreturn_non_returning_function(i1 %c, i32* %p) {
 ; CHECK-NOT: Function Attrs: {{.*}}willreturn
 ; CHECK: define void @willreturn_non_returning_function(
 ;
   call void @unknown_fn()
   ret void
 }
 
+; Infinite loop without mustprogress, will not return.
 define void @willreturn_loop() {
 ; CHECK-NOT: Function Attrs: {{.*}}willreturn
 ; CHECK: define void @willreturn_loop(
 ;
   br label %loop
 
 loop:
   br label %loop
 }
 
+; Finite loop. Could be willreturn but not detected.
+; FIXME
 define void @willreturn_finite_loop() {
 ; CHECK-NOT: Function Attrs: {{.*}}willreturn
 ; CHECK: define void @willreturn_finite_loop(
 ;
 entry:
   br label %loop
 
 loop:
   %i = phi i32 [ 0, %entry], [ %i.inc, %loop ]
   %i.inc = add nuw i32 %i, 1
   %c = icmp ne i32 %i.inc, 100
   br i1 %c, label %loop, label %end
 
 end:
   ret void
 }
 
+; Infinite recursion without mustprogress, will not return.
+define void @willreturn_recursion() {
+; CHECK-NOT: Function Attrs: {{.*}}willreturn
+; CHECK: define void @willreturn_recursion(
+;
+  tail call void @willreturn_recursion()
+  ret void
+}
+
+; Irreducible infinite loop, will not return.
+define void @willreturn_irreducible(i1 %c) {
+; CHECK-NOT: Function Attrs: {{.*}}willreturn
+; CHECK: define void @willreturn_irreducible(
+;
+  br i1 %c, label %bb1, label %bb2
+
+bb1:
+  br label %bb2
+
+bb2:
+  br label %bb1
+}
+
 declare i64 @fn_noread() readnone
 declare void @fn_willreturn() willreturn

test/Transforms/FunctionAttrs/writeonly.ll

 
 ; CHECK: define void @nouses-argworn-funwo(i32* nocapture readnone %.aaa) #2 {
 define void @nouses-argworn-funwo(i32* writeonly %.aaa) {
 nouses-argworn-funwo_entry:
   store i8 0, i8* getelementptr inbounds (%_type_of_d-ccc, %_type_of_d-ccc* @d-ccc, i32 0, i32 3)
   ret void
 }
 
-; CHECK: attributes #0 = { {{.*}} readnone }
-; CHECK: attributes #1 = { {{.*}} readonly }
+; CHECK: attributes #0 = { {{.*}} readnone {{.*}} }
+; CHECK: attributes #1 = { {{.*}} readonly {{.*}} }
 ; CHECK: attributes #2 = { {{.*}} writeonly }

test/Transforms/InferFunctionAttrs/norecurse_debug.ll

 !17 = !{!""}
 !18 = !DILocation(line: 3, column: 14, scope: !2)
 !19 = !DILocation(line: 7, column: 6, scope: !2)
 !24 = !DILocation(line: 7, column: 14, scope: !2)
 !27 = !DILocation(line: 9, column: 20, scope: !2)
 !28 = !DILocation(line: 9, column: 18, scope: !2)
 !29 = !DILocation(line: 10, column: 1, scope: !2)
 
-; CHECK: attributes #0 = { nofree norecurse nounwind }
+; CHECK: attributes #0 = { nofree norecurse nounwind willreturn }
 ; CHECK-NOT: foo.coefficient1