[funcattrs] Infer nosync from instruction walk

[reames]

Summary

Pretty straightforward use of existing infrastructure and port of the attributor inference rules for nosync.

A couple points of interest:

• I deliberately switched from "monotonic or better" to "unordered or better". This is simply me being conservative and is better in line with the rest of the optimizer. We treat monotonic conservatively pretty much everywhere.
• The operand bundle test change is suspicious. It looks like we might have missed something here, but if so, it's an issue with the existing nofree inference as well. I'm going to take a closer look at that separately.
• I needed to keep the previous inference from readnone. This surprised me, but made sense once I realized readonly inference goes to lengths to reason about local vs non-local memory and that writes to local memory are okay. This is fine for the purpose of nosync, but would e.g. prevent us from inferring nofree from readnone - which is slightly surprising.

[jdoerfert]

Pretty straightforward use of existing infrastructure and port of the attributor inference rules for nosync.

port = duplication, where does this stop?

[reames]

In D99769#2665218, @jdoerfert wrote:

Pretty straightforward use of existing infrastructure and port of the attributor inference rules for nosync.

port = duplication, where does this stop?

When the folks working on attributor do the work to stabilize it and get it on by default. I don't know exactly how much work that is, but I suspect quite a bit.

[reames]

ping

[sstefan1]

I'm doing some testing with a lightweight attributor enabled by default. Can this wait few more days, until I get some results? If the numbers are good, maybe we won't need this after all?

[fhahn]

In D99769#2665277, @reames wrote:

In D99769#2665218, @jdoerfert wrote:

Pretty straightforward use of existing infrastructure and port of the attributor inference rules for nosync.

port = duplication, where does this stop?

When the folks working on attributor do the work to stabilize it and get it on by default. I don't know exactly how much work that is, but I suspect quite a bit.

The duplication is a bit unfortunate, but it provides a stable path forward, with less uncertainty than the lightweight attributor pass. At the moment, FunctionAttrs is the default way to do this kind of reasoning and IMO this 'duplication' seems like a reasonable trade-off, especially if Philip is happy to provide a patch even if the code becomes unused at some point. I think this also provides indirect benefits for the attributor, as it exposes a small subset of the reasoning by default and enables other passes to make use of the additional attributes right now.

In D99769#2676226, @sstefan1 wrote:

I'm doing some testing with a lightweight attributor enabled by default. Can this wait few more days, until I get some results? If the numbers are good, maybe we won't need this after all?

That's great, but I think 'using a lightweight attributor pass by default' requires at least the following steps 1) add the pass with option to enable it, 2) have people test it, 3) collect data to make a convincing case for enabling it, 4) flip the default and deal with the fallout. I am not sure this can be done in a few days.

I'd recommend to start with sharing a patch that adds this lightweight attributor pass, so we can start with getting consensus what the scope of this pass should be and go from there (without tying ourselves to any particular timeframe)

[reames]

+1 to @fhahn's comments

[sstefan1]

In D99769#2676275, @fhahn wrote:

In D99769#2676226, @sstefan1 wrote:

I'm doing some testing with a lightweight attributor enabled by default. Can this wait few more days, until I get some results? If the numbers are good, maybe we won't need this after all?

That's great, but I think 'using a lightweight attributor pass by default' requires at least the following steps 1) add the pass with option to enable it, 2) have people test it, 3) collect data to make a convincing case for enabling it, 4) flip the default and deal with the fallout. I am not sure this can be done in a few days.

I'd recommend to start with sharing a patch that adds this lightweight attributor pass, so we can start with getting consensus what the scope of this pass should be and go from there (without tying ourselves to any particular timeframe)

Sounds good to me. I agree it is better not to rush things.

Just for clarification: a lightweight attributor wouldn't be a separate pass, but a regular attributor pass just with fewer abstract attributes initialised by default. I'll start with that and we'll see how it goes.

[jdoerfert]

In D99769#2676275, @fhahn wrote:

In D99769#2665277, @reames wrote:

In D99769#2665218, @jdoerfert wrote:

Pretty straightforward use of existing infrastructure and port of the attributor inference rules for nosync.

port = duplication, where does this stop?

When the folks working on attributor do the work to stabilize it and get it on by default. I don't know exactly how much work that is, but I suspect quite a bit.

What I'm saying is that it seems off to argue for duplication of code/work to avoid work, especially since this makes the end goal harder to achieve.
TBH, I believe the judgement would look different if someone would propose workaround #5 that duplicates functionality to avoid looking into a proper solution.

The duplication is a bit unfortunate, but it provides a stable path forward, with less uncertainty than the lightweight attributor pass. At the moment, FunctionAttrs is the default way to do this kind of reasoning and IMO this 'duplication' seems like a reasonable trade-off, especially if Philip is happy to provide a patch even if the code becomes unused at some point. I think this also provides indirect benefits for the attributor, as it exposes a small subset of the reasoning by default and enables other passes to make use of the additional attributes right now.

This is arguably only true if people that fix errors in the FunctionAttr pass transfer those fixes and tests to the Attributor.
As with all duplication this is likely not to happen at all, or maybe just not all the time. I certainly doubt it will.
I see the point for a solution now, obviously, however, we could at least try to minimize duplication so fixes would transfer automatically.
For example, why do we need the (basically) same static methods twice instead of exposing them?
static AANoSync::isNoSyncIntrinsic could be called by the FunctionAttr pass and we would actually expose a subset of the reasoning through the same code.
Asking to expose common functionality in helper functions is really not something specific to the Attributor and there needs to be a good reason to avoid it in favor of copy & paste.

---

All in all, I don't think the logic that is applied here wrt. development is sensible. If nobody even tries to run the Attributor to solve their problem but
instead cherry picks logic out of it, and copies it, we are moving away from enabling it and not closer. To be concrete, what I am missing here is a sentence that reads like:
"I tried to alternatively run the Attributor only for nosync deduction. I created and Attributor object in the addNoSyncAttr method, restricted deduction
to AANoSync and seeded the functions I was interested in. The result was ... and therefore we should ...."
You can argue this is too much work but I doubt it is, and it seems people are guessing mostly when it comes to this which leads me to believe they haven't tried.
I also doubt we would make the same decisions in other places. I mean, it is common to ask people to compare to alternative designs, especially if those are already
available. FWIW, setting up a single attribute deduction with the Attributor should be a much easier task than requests to implement an alternative solution.

[reames]

Johannes,

Sorry for not replying to your points inline, phab makes that difficult for long intermixed replies.

I am glad to see that work is being done towards enabling Attributor by default. So as to avoid duplicating a long comment, I will point you to my comment on that review (https://reviews.llvm.org/D100339#2686153) to explain my concerns on that direction.

On the broader topic, I am happy to discuss the workflow implications offline. Honestly, I think you've got the wrong end of the stick here. If I accept the premise of your argument, my actual takeaway is that I should resist all efforts to add experimental code before it has been widely discussed and accepted as the agreed upon path forward. I think we can all agree that's not a desirable outcome. I also think it's out of sync with long standing practice in the community.

Again, if you want to talk on the workflow stuff, let's talk offline. There's a bunch of subtleties that is far too easy to loose in written conversation. I, in particular, seem very prone to that. :)

[reames]

Had not intended to reopen.

llvm/lib/Transforms/IPO/FunctionAttrs.cpp

for (Function *F : SCCNodes) {
     F->setWillReturn();
     NumWillReturn++;
     Changed = true;
   }
 
   return Changed;
 }
 
-// Infer the nosync attribute.  For the moment, the inference is trivial
-// and relies on the readnone attribute already being infered.  This will
-// be replaced with a more robust implementation in the near future.
+// Return true if this is an atomic which has an ordering stronger than
+// unordered.  Note that this is different than the predicate we use in
+// Attributor.  Here we chose to be conservative and consider monotonic
+// operations potentially synchronizing.  We generally don't do much with
+// monotonic operations, so this is simply risk reduction.
+static bool isOrderedAtomic(Instruction *I) {
+  if (!I->isAtomic())
+    return false;
+
+  if (auto *FI = dyn_cast<FenceInst>(I))
+    // All legal orderings for fence are stronger than monotonic.
+    return FI->getSyncScopeID() != SyncScope::SingleThread;
+  else if (isa<AtomicCmpXchgInst>(I) || isa<AtomicRMWInst>(I))
+    return true;
+  else if (auto *SI = dyn_cast<StoreInst>(I))
+    return !SI->isUnordered();
+  else if (auto *LI = dyn_cast<LoadInst>(I))
+    return !LI->isUnordered();
+  else {
+    llvm_unreachable("unknown atomic instruction?");
+  }
+}
+
+static bool InstrBreaksNoSync(Instruction &I, const SCCNodeSet &SCCNodes) {
+  // Volatile may synchronize
+  if (I.isVolatile())
+    return true;
+
+  // An ordered atomic may synchronize.  (See comment about on monotonic.)
+  if (isOrderedAtomic(&I))
+    return true;
+
+  auto *CB = dyn_cast<CallBase>(&I);
+  if (!CB)
+    // Non call site cases covered by the two checks above
+    return false;
+
+  if (CB->hasFnAttr(Attribute::NoSync))
+    return false;
+
+  // readnone + not convergent implies nosync
+  // (This is needed to initialize inference from declarations which aren't
+  //  explicitly nosync, but are readnone and not convergent.)
+  if (CB->hasFnAttr(Attribute::ReadNone) &&
+      !CB->hasFnAttr(Attribute::Convergent))
+    return false;
+
+  // Non volatile memset/memcpy/memmoves are nosync
+  // NOTE: Only intrinsics with volatile flags should be handled here.  All
+  // others should be marked in Intrinsics.td.
+  if (auto *MI = dyn_cast<MemIntrinsic>(&I))
+    if (!MI->isVolatile())
+      return false;
+
+  // Speculatively assume in SCC.
+  if (Function *Callee = CB->getCalledFunction())
+    if (SCCNodes.contains(Callee))
+      return false;
+
+  return true;
+}
+
+// Infer the nosync attribute.
 static bool addNoSyncAttr(const SCCNodeSet &SCCNodes) {
-  bool Changed = false;
+  AttributeInferer AI;
+  AI.registerAttrInference(AttributeInferer::InferenceDescriptor{
+      Attribute::NoSync,
+      // Skip already marked functions.
+      [](const Function &F) { return F.hasNoSync(); },
+      // Instructions that break nosync assumption.
+      [&SCCNodes](Instruction &I) {
+        return InstrBreaksNoSync(I, SCCNodes);
+      },
+      [](Function &F) {
+        LLVM_DEBUG(dbgs()
+                   << "Adding nosync attr to fn " << F.getName() << "\n");
+        F.setNoSync();
+        ++NumNoSync;
+      },
+      /* RequiresExactDefinition= */ true});
+  bool Changed = AI.run(SCCNodes);
 
+  // readnone + not convergent implies nosync
+  // (This is here so that we don't have to duplicate the function local
+  //  memory reasoning of the readnone analysis.)
   for (Function *F : SCCNodes) {
     if (!F || F->hasNoSync())
       continue;
-
-    // readnone + not convergent implies nosync
     if (!F->doesNotAccessMemory() || F->isConvergent())
       continue;
-
     F->setNoSync();
     NumNoSync++;
     Changed = true;
   }
-
   return Changed;
 }
 
 static SCCNodesResult createSCCNodeSet(ArrayRef<Function *> Functions) {
   SCCNodesResult Res;
   Res.HasUnknownCall = false;
   for (Function *F : Functions) {
     if (!F || F->hasOptNone() || F->hasFnAttribute(Attribute::Naked)) {

llvm/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 nosync nounwind readnone willreturn }
-; CHECK: attributes #1 = { nofree norecurse nounwind willreturn writeonly }
+; CHECK: attributes #1 = { nofree norecurse nosync nounwind willreturn writeonly }
 ; CHECK: attributes #2 = { nounwind readonly }
 ; CHECK: attributes #3 = { nounwind }
 ; CHECK: attributes #4 = { nosync nounwind readnone willreturn }
-; CHECK: attributes #5 = { nofree nounwind willreturn }
-; CHECK: attributes #6 = { nofree norecurse nounwind willreturn }
+; CHECK: attributes #5 = { nofree nosync nounwind willreturn }
+; CHECK: attributes #6 = { nofree norecurse nosync 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 }

llvm/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 nosync 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" }
+; UNSAFE: attributes #1 = { nofree norecurse nosync nounwind willreturn "less-precise-fpmad"="false" "no-infs-fp-math"="false" "no-nans-fp-math"="false" "unsafe-fp-math"="true" }
 
 ; NOINFS: attributes #0 = { norecurse nosync 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" }
+; NOINFS: attributes #1 = { nofree norecurse nosync nounwind willreturn "less-precise-fpmad"="false" "no-infs-fp-math"="true" "no-nans-fp-math"="false" "unsafe-fp-math"="false" }
 
 ; NONANS: attributes #0 = { norecurse nosync 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" }
+; NONANS: attributes #1 = { nofree norecurse nosync 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 {

llvm/test/Transforms/FunctionAttrs/nofree.ll

entry:
   %0 = bitcast i32* %a to i8*
   tail call void @free(i8* %0) #2
   ret void
 }
 
 declare void @free(i8* nocapture) local_unnamed_addr #2
 
 define i32 @_Z4foo3Pi(i32* nocapture readonly %a) local_unnamed_addr #3 {
-; CHECK: Function Attrs: norecurse nounwind readonly uwtable willreturn
+; CHECK: Function Attrs: norecurse nosync nounwind readonly uwtable willreturn
 ; CHECK-LABEL: @_Z4foo3Pi(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[TMP0:%.*]] = load i32, i32* [[A:%.*]], align 4
 ; CHECK-NEXT:    ret i32 [[TMP0]]
 ;
 entry:
   %0 = load i32, i32* %a, align 4
   ret i32 %0

llvm/test/Transforms/FunctionAttrs/nosync.ll

 ; CHECK-NEXT:    ret void
 ;
   fence seq_cst
   ret void
 }
 
 ; singlethread fences are okay
 define void @test9(i8* %p) {
-; CHECK: Function Attrs: nofree norecurse nounwind willreturn
+; CHECK: Function Attrs: nofree norecurse nosync nounwind willreturn
 ; CHECK-LABEL: @test9(
 ; CHECK-NEXT:    fence syncscope("singlethread") seq_cst
 ; CHECK-NEXT:    ret void
 ;
   fence syncscope("singlethread") seq_cst
   ret void
 }
 

 ; CHECK-NEXT:    [[TMP2:%.*]] = load atomic i32, i32* [[TMP0:%.*]] acquire, align 4
 ; CHECK-NEXT:    ret i32 [[TMP2]]
 ;
   %2 = load atomic i32, i32* %0 acquire, align 4
   ret i32 %2
 }
 
 define i32 @load_unordered(i32* nocapture readonly %0) norecurse nounwind uwtable {
-; CHECK: Function Attrs: norecurse nounwind readonly uwtable willreturn
+; CHECK: Function Attrs: norecurse nosync nounwind readonly uwtable willreturn
 ; CHECK-LABEL: @load_unordered(
 ; CHECK-NEXT:    [[TMP2:%.*]] = load atomic i32, i32* [[TMP0:%.*]] unordered, align 4
 ; CHECK-NEXT:    ret i32 [[TMP2]]
 ;
   %2 = load atomic i32, i32* %0 unordered, align 4
   ret i32 %2
 }
 
 ; atomic store with unordered ordering.
 define void @store_unordered(i32* nocapture %0) norecurse nounwind uwtable {
-; CHECK: Function Attrs: nofree norecurse nounwind uwtable willreturn writeonly
+; CHECK: Function Attrs: nofree norecurse nosync nounwind uwtable willreturn writeonly
 ; CHECK-LABEL: @store_unordered(
 ; CHECK-NEXT:    store atomic i32 10, i32* [[TMP0:%.*]] unordered, align 4
 ; CHECK-NEXT:    ret void
 ;
   store atomic i32 10, i32* %0 unordered, align 4
   ret void
 }
 
;
   ret i32 %2
 }
 
 ; CHECK: Function Attrs: noinline nosync nounwind uwtable
 ; CHECK-NEXT: declare void @nosync_function()
 declare void @nosync_function() noinline nounwind uwtable nosync
 
 define void @call_nosync_function() nounwind uwtable noinline {
-; CHECK: Function Attrs: noinline nounwind uwtable
+; CHECK: Function Attrs: noinline nosync nounwind uwtable
 ; CHECK-LABEL: @call_nosync_function(
-; CHECK-NEXT:    tail call void @nosync_function() #[[ATTR7:[0-9]+]]
+; CHECK-NEXT:    tail call void @nosync_function() #[[ATTR8:[0-9]+]]
 ; CHECK-NEXT:    ret void
 ;
   tail call void @nosync_function() noinline nounwind uwtable
   ret void
 }
 
 ; CHECK: Function Attrs: noinline nounwind uwtable
 ; CHECK-NEXT: declare void @might_sync()
 declare void @might_sync() noinline nounwind uwtable
 
 define void @call_might_sync() nounwind uwtable noinline {
 ; CHECK: Function Attrs: noinline nounwind uwtable
 ; CHECK-LABEL: @call_might_sync(
-; CHECK-NEXT:    tail call void @might_sync() #[[ATTR7]]
+; CHECK-NEXT:    tail call void @might_sync() #[[ATTR8]]
 ; CHECK-NEXT:    ret void
 ;
   tail call void @might_sync() noinline nounwind uwtable
   ret void
 }
 
 declare void @llvm.memcpy(i8* %dest, i8* %src, i32 %len, i1 %isvolatile)
 declare void @llvm.memset(i8* %dest, i8 %val, i32 %len, i1 %isvolatile)
 
 ; negative, checking volatile intrinsics.
 define i32 @memcpy_volatile(i8* %ptr1, i8* %ptr2) {
 ; CHECK: Function Attrs: nofree nounwind willreturn
 ; CHECK-LABEL: @memcpy_volatile(
 ; CHECK-NEXT:    call void @llvm.memcpy.p0i8.p0i8.i32(i8* [[PTR1:%.*]], i8* [[PTR2:%.*]], i32 8, i1 true)
 ; CHECK-NEXT:    ret i32 4
 ;
   call void @llvm.memcpy(i8* %ptr1, i8* %ptr2, i32 8, i1 1)
   ret i32 4
 }
 
 ; positive, non-volatile intrinsic.
 define i32 @memset_non_volatile(i8* %ptr1, i8 %val) {
-; CHECK: Function Attrs: nofree nounwind willreturn writeonly
+; CHECK: Function Attrs: nofree nosync nounwind willreturn writeonly
 ; CHECK-LABEL: @memset_non_volatile(
 ; CHECK-NEXT:    call void @llvm.memset.p0i8.i32(i8* [[PTR1:%.*]], i8 [[VAL:%.*]], i32 8, i1 false)
 ; CHECK-NEXT:    ret i32 4
 ;
   call void @llvm.memset(i8* %ptr1, i8 %val, i32 8, i1 0)
   ret i32 4
 }
 

llvm/test/Transforms/FunctionAttrs/operand-bundles-scc.ll

 ; RUN: opt -S -function-attrs < %s | FileCheck %s
 ; RUN: opt -S -passes=function-attrs < %s | FileCheck %s
 
 define void @f() {
 ; CHECK-LABEL:  define void @f() #0 {
  call void @g() [ "unknown"() ]
  ret void
 }
 
 define void @g() {
 ; CHECK-LABEL:  define void @g() #0 {
  call void @f()
  ret void
 }
 
 
-; CHECK: attributes #0 = { nofree nounwind }
+; CHECK: attributes #0 = { nofree nosync nounwind }

llvm/test/Transforms/FunctionAttrs/read-write-scc.ll

 
 define void @bar() {
 ; CHECK-LABEL: define void @bar() #0 {
   %i = load i32, i32* @i
   call void @foo()
   ret void
 }
 
-; CHECK: attributes #0 = { nofree nounwind }
+; CHECK: attributes #0 = { nofree nosync nounwind }

llvm/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 willreturn }
+; CHECK: attributes #0 = { nofree norecurse nosync nounwind willreturn }
 ; CHECK-NOT: foo.coefficient1