[Attributor] AANoRecurse check all call sites for `norecurse`

[jdoerfert]

Summary

If all call sites are in norecurse functions we can derive norecurse
as the ReversePostOrderFunctionAttrsPass does. This should make
ReversePostOrderFunctionAttrsLegacyPass obsolete once the Attributor is
enabled.

[merge_guards_bot]

Unit tests: unknown.

clang-tidy: fail. Please fix clang-tidy findings.

clang-format: pass.

Build artifacts: diff.json, clang-tidy.txt, clang-format.patch, CMakeCache.txt, console-log.txt

[uenoku]

llvm/lib/Transforms/IPO/Attributor.cpp

2107

Don't we need to return?

[jdoerfert]

llvm/lib/Transforms/IPO/Attributor.cpp

2107

We return in the next line either way. If the checkForAllCallSites returned true we can *at least* assume noreturn. Or did I misunderstand your question?

[uenoku]

llvm/lib/Transforms/IPO/Attributor.cpp

2107

I mean we need to return ChangeStatus::CHANGED here, isn't it?

[jdoerfert]

llvm/lib/Transforms/IPO/Attributor.cpp

2107

The assumed state didn't change so I returned UNCHANGED. This is what indicateOptimisticFixpoint returns as well. So far I used the changestatus (only) for the assumed not the known state. I'm not convinced it is useful to indicate "changes" in the known state alone, though I'm open to arguments here.

[uenoku]

llvm/lib/Transforms/IPO/Attributor.cpp

2107

Oh, I misunderstood that indicateOptimistic returns Changed. Thanks. I agree we shouldn't use the changestatus for known state.

[uenoku]

LGTM

llvm/lib/Transforms/IPO/Attributor.cpp

 
 struct AANoRecurseFunction final : AANoRecurseImpl {
   AANoRecurseFunction(const IRPosition &IRP) : AANoRecurseImpl(IRP) {}
 
   /// See AbstractAttribute::initialize(...).
   void initialize(Attributor &A) override {
     AANoRecurseImpl::initialize(A);
     if (const Function *F = getAnchorScope())
-      if (A.getInfoCache().getSccSize(*F) == 1)
-        return;
+      if (A.getInfoCache().getSccSize(*F) != 1)
         indicatePessimisticFixpoint();
   }
 
   /// See AbstractAttribute::updateImpl(...).
   ChangeStatus updateImpl(Attributor &A) override {
 
+    // If all live call sites are known to be no-recurse, we are as well.
+    auto CallSitePred = [&](AbstractCallSite ACS) {
+      const auto &NoRecurseAA = A.getAAFor<AANoRecurse>(
+          *this, IRPosition::function(*ACS.getInstruction()->getFunction()),
+          /* TrackDependence */ false, DepClassTy::OPTIONAL);
+      return NoRecurseAA.isKnownNoRecurse();
+    };
+    bool AllCallSitesKnown;
+    if (A.checkForAllCallSites(CallSitePred, *this, true, AllCallSitesKnown)) {
+      // If we know all call sites and all are known no-recurse, we are done.
+      // If all known call sites, which might not be all that exist, are known
+      // to be no-recurse, we are not done but we can continue to assume
+      // no-recurse. If one of the call sites we have not visited will become
+      // live, another update is triggered.
+      if (AllCallSitesKnown)
+        indicateOptimisticFixpoint();
+      return ChangeStatus::UNCHANGED;
+    }
+
+    // If the above check does not hold anymore we look at the calls.
     auto CheckForNoRecurse = [&](Instruction &I) {
       ImmutableCallSite ICS(&I);
       if (ICS.hasFnAttr(Attribute::NoRecurse))
         return true;
 
       const auto &NoRecurseAA =
           A.getAAFor<AANoRecurse>(*this, IRPosition::callsite_function(ICS));
       if (!NoRecurseAA.isAssumedNoRecurse())

llvm/test/Transforms/Attributor/ArgumentPromotion/dbg.ll

 ;
   ret void
 }
 
 define void @caller(i32** %Y, %struct.pair* %P) {
 ; CHECK-LABEL: define {{[^@]+}}@caller
 ; CHECK-SAME: (i32** nocapture readonly [[Y:%.*]], %struct.pair* nocapture nofree readonly [[P:%.*]])
 ; CHECK-NEXT:    call void @test(i32** nocapture readonly align 8 [[Y]]), !dbg !4
-; CHECK-NEXT:    call void @test_byval(), !dbg !5
+; CHECK-NEXT:    call void @test_byval() #1, !dbg !5
 ; CHECK-NEXT:    ret void
 ;
   call void @test(i32** %Y), !dbg !1
 
   call void @test_byval(%struct.pair* %P), !dbg !6
   ret void
 }
 

llvm/test/Transforms/Attributor/ArgumentPromotion/nonzero-address-spaces.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py UTC_ARGS: --function-signature --scrub-attributes
-; RUN: opt -S -passes=attributor -aa-pipeline='basic-aa' -attributor-disable=false -attributor-max-iterations-verify -attributor-max-iterations=1 < %s | FileCheck %s
+; RUN: opt -S -passes=attributor -aa-pipeline='basic-aa' -attributor-disable=false -attributor-max-iterations-verify -attributor-max-iterations=2 < %s | FileCheck %s
 
 ; ArgumentPromotion should preserve the default function address space
 ; from the data layout.
 
 target datalayout = "e-P1-p:16:8-i8:8-i16:8-i32:8-i64:8-f32:8-f64:8-n8-a:8"
 
 @g = common global i32 0, align 4
 

llvm/test/Transforms/Attributor/IPConstantProp/multiple_callbacks.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py UTC_ARGS: --function-signature --scrub-attributes
-; RUN: opt -S -passes=attributor -aa-pipeline='basic-aa' -attributor-disable=false -attributor-max-iterations-verify -attributor-max-iterations=1 < %s | FileCheck %s
+; RUN: opt -S -passes=attributor -aa-pipeline='basic-aa' -attributor-disable=false -attributor-max-iterations-verify -attributor-max-iterations=3 < %s | FileCheck %s
 ;
 ;
 ;                            /---------------------------------------|
 ;                            |                /----------------------|----|
 ;                            |                |                /-----|    |
 ;                            V                V                V     |    |
 ;    void broker(int (*cb0)(int), int (*cb1)(int), int (*cb2)(int), int, int);
 ;

llvm/test/Transforms/Attributor/internal-noalias.ll

-; RUN: opt -S -passes=attributor -aa-pipeline='basic-aa' -attributor-disable=false -attributor-max-iterations-verify -attributor-annotate-decl-cs -attributor-max-iterations=5 < %s | FileCheck %s
+; RUN: opt -S -passes=attributor -aa-pipeline='basic-aa' -attributor-disable=false -attributor-max-iterations-verify -attributor-annotate-decl-cs -attributor-max-iterations=6 < %s | FileCheck %s
 
 define dso_local i32 @visible(i32* noalias %A, i32* noalias %B) #0 {
 entry:
   %call1 = call i32 @noalias_args(i32* %A, i32* %B)
   %call2 = call i32 @noalias_args_argmem(i32* %A, i32* %B)
   %add = add nsw i32 %call1, %call2
   ret i32 %add
 }

llvm/test/Transforms/Attributor/norecurse.ll

-; RUN: opt -passes=attributor --attributor-disable=false -attributor-max-iterations-verify -attributor-annotate-decl-cs -attributor-max-iterations=2 -S < %s | FileCheck %s --check-prefixes=ATTRIBUTOR
+; RUN: opt -passes=attributor --attributor-disable=false -attributor-max-iterations-verify -attributor-annotate-decl-cs -attributor-max-iterations=4 -S < %s | FileCheck %s --check-prefixes=ATTRIBUTOR
 ; Copied from Transforms/FunctoinAttrs/norecurse.ll
 
 ; ATTRIBUTOR: Function Attrs: nofree norecurse nosync nounwind readnone willreturn
 ; ATTRIBUTOR-NEXT: define i32 @leaf()
 define i32 @leaf() {
   ret i32 1
 }
 
define void @intrinsic(i8* %dest, i8* %src, i32 %len) {
   ret void
 }
 
 ; ATTRIBUTOR: Function Attrs
 ; ATTRIBUTOR-NEXT: declare void @llvm.memcpy.p0i8.p0i8.i32
 declare void @llvm.memcpy.p0i8.p0i8.i32(i8*, i8*, i32, i1)
 
 ; ATTRIBUTOR: Function Attrs
-; FIXME: missing "norecurse"
-; ATTRIBUTOR-SAME: nosync readnone
+; ATTRIBUTOR-SAME: norecurse nosync readnone
 define internal i32 @called_by_norecurse() {
   %a = call i32 @k()
   ret i32 %a
 }
 ; ATTRIBUTOR: Function Attrs
 ; ATTRIBUTOR-NEXT: define void @m()
 define void @m() norecurse {
   %a = call i32 @called_by_norecurse()
   ret void
 }
 
 ; ATTRIBUTOR: Function Attrs
-; FIXME: missing "norecurse"
-; ATTRIBUTOR-SAME: nosync
+; ATTRIBUTOR-SAME: norecurse nosync readnone
+; ATTRIBUTOR-NEXT: @called_by_norecurse_indirectly
 define internal i32 @called_by_norecurse_indirectly() {
   %a = call i32 @k()
   ret i32 %a
 }
-define internal void @o() {
+; ATTRIBUTOR: Function Attrs
+; ATTRIBUTOR-SAME: norecurse nosync readnone
+; ATTRIBUTOR-NEXT: @o
+define internal i32 @o() {
   %a = call i32 @called_by_norecurse_indirectly()
-  ret void
+  ret i32 %a
 }
-define void @p() norecurse {
-  call void @o()
-  ret void
+define i32 @p() norecurse {
+  %a = call i32 @o()
+  ret i32 %a
 }
 
 ; ATTRIBUTOR: Function Attrs: nofree nosync nounwind
 ; ATTRIBUTOR-NEXT: define void @f(i32 %x)
 define void @f(i32 %x)  {
 entry:
   %x.addr = alloca i32, align 4
   store i32 %x, i32* %x.addr, align 4