[FunctionAttrs] Consider recursive argmem effects (PR63936)

[nikic]

Summary

When inspecting the function body, we can't simply ignore effects of functions in the SCC entirely, because an argmem access of a recursive call might result in an access to another location in the callee.

Fix this by separately tracking memory effects that would occur if the SCC accesses argmem, and then later add those.

Fixes https://github.com/llvm/llvm-project/issues/63936.

[goldstein.w.n]

llvm/lib/Transforms/IPO/FunctionAttrs.cpp

154–160

IMO Needs a comment describing what each item in the pair refers to.

[nikic]

Add comment describing return value.

[nikic]

Ping

[goldstein.w.n]

llvm/lib/Transforms/IPO/FunctionAttrs.cpp

183–187

This comment needs to be updated.

191

Maximum depth on recursion?

248

Style on &

[nikic]

Rebase over test changes, update comment.

[nikic]

llvm/lib/Transforms/IPO/FunctionAttrs.cpp

191

There is no recursion here.

248

Not sure what you mean here. The & is a bitwise and rather than a reference, so I think the style is correct?

[goldstein.w.n]

llvm/lib/Transforms/IPO/FunctionAttrs.cpp

177–178

Imo ME needs a different name, its extremely confusing to have it shadow the non-scoped version.

183–187

Imo ME needs a different name, its extremely confusing to have it shadow the non-scoped version.

280

I don't really understand the rationale behind creating a seperate recursive variable.

It seems the original intent is to track calls with bundled arguments for which apprently IRMemLocation is incomplete.
But if you only add back recursive args if memloc indicates mod/ref, doesn't that defeat the purpose?
If so, why not just update ME directly for bundled calls?

[nikic]

llvm/lib/Transforms/IPO/FunctionAttrs.cpp

280

Lets take a case like this:

define void @test_recursive_argmem_read(ptr %p) {
  %pval = load ptr, ptr %p
  call void @test_recursive_argmem_read(ptr %pval)
  ret void
}

At the point where we inspect the recursive @test_recursive_argmem_read call, we don't know whether that call will read or write %pval. (Well, in this specific example we do if we scan instructions from top to bottom, but generally we don't, because it depends on visitation order.)

We could just conservatively assume that all pointers passed to a recursive access will be read+write accessed and add the corresponding effects right away. That would be correct, but it would also be overly conservative. In this case, it is sufficient to only add read effects for the affected locations, we don't need to add any write effects.

[goldstein.w.n]

llvm/lib/Transforms/IPO/FunctionAttrs.cpp

280

But why do you need a seperate variable to track that? Can't that just as easily be added directly to ME?

[nikic]

llvm/lib/Transforms/IPO/FunctionAttrs.cpp

280

I don't really understand what you have in mind here. The current code does AddArgLocs(RecursiveArgME, ModRefInfo::ModRef), what would I replace it with?

I can replace it with AddArgLocs(ME, ModRefInfo::ModRef), but that would add unnecessary effects if the SCC is not argmem: readwrite.

[nikic]

Rebase over NFC changes.

[goldstein.w.n]

llvm/lib/Transforms/IPO/FunctionAttrs.cpp

280

I'm just wondering why we need a new variable at L171 (as opposed to just doing this all in ME on L169).
Why would that unduly add argmen: readwrite?

Sorry for this to be like pulling teeth, not super familiar with FunctionAttrs.

[nikic]

llvm/lib/Transforms/IPO/FunctionAttrs.cpp

280

This is what happens if you directly add to ME instead of using a separate variable: https://gist.github.com/nikic/ff98bde042030ce6ebaca392237f7e46

[goldstein.w.n]

llvm/lib/Transforms/IPO/FunctionAttrs.cpp

280

Is there some intuition for why that is?

[goldstein.w.n]

llvm/lib/Transforms/IPO/FunctionAttrs.cpp

192

Why is arg3 ModRefInfo::ModRef and not AAR.getMemoryEffects(Call).getModRef(IRMemLocation::ArgMem)?

[goldstein.w.n]

LGTM.

I'm only somewhat familiar with this system. No on else has come review this so approving, but maybe wait at least a day or two before pushing to give time to someone more familiar to review.

llvm/lib/Transforms/IPO/FunctionAttrs.cpp

280

Okay I see, its because we want to isolate only ArgMem affects and if you apply directly the ME it ends up setting things like other (thats what happening in the regressions at least).

That makes sense.

[aeubanks]

lgtm

[goldstein.w.n]

llvm/lib/Transforms/IPO/FunctionAttrs.cpp

192

Note: you could change this codes to:

MemoryEffects RecursiveArgME = MemoryEffects::none();
ModRefInfo ArgMR = ME.getModRef(IRMemLocation::ArgMem);
addArgLocs(RecursiveArgME, Call, ModRefInfo::ModRef, AAR);
if (ArgMR != ModRefInfo::NoModRef)
  ME |= RecursiveArgME & MemoryEffects(ArgMR);

and get rid of the returning pair logic.
Personally think thats cleaner but not particularly important.

[nikic]

llvm/lib/Transforms/IPO/FunctionAttrs.cpp

192

That's a complicated way of saying addArgLocs(ME, Call, ME.getModRef(IRMemLocation::ArgMem), AAR). The problem is that this uses the ME at the current point of the analysis -- however, additional effects may be added later (either in this function, or a different function in the same SCC), which we would fail to account for.

llvm/lib/Transforms/IPO/FunctionAttrs.cpp

 /// Returns the memory access attribute for function F using AAR for AA results,
 /// where SCCNodes is the current SCC.
 ///
 /// If ThisBody is true, this function may examine the function body and will
 /// return a result pertaining to this copy of the function. If it is false, the
 /// result will be based only on AA results for the function declaration; it
 /// will be assumed that some other (perhaps less optimized) version of the
 /// function may be selected at link time.
-static MemoryEffects checkFunctionMemoryAccess(Function &F, bool ThisBody,
-                                               AAResults &AAR,
-                                               const SCCNodeSet &SCCNodes) {
+///
+/// The return value is split into two parts: Memory effects that always apply,
+/// and additional memory effects that apply if any of the functions in the SCC
+/// can access argmem.
+static std::pair<MemoryEffects, MemoryEffects>
+checkFunctionMemoryAccess(Function &F, bool ThisBody, AAResults &AAR,
   MemoryEffects OrigME = AAR.getMemoryEffects(&F);
   if (OrigME.doesNotAccessMemory())
     // Already perfect!
-    return OrigME;
+    return {OrigME, MemoryEffects::none()};
 
   if (!ThisBody)
-    return OrigME;
+    return {OrigME, MemoryEffects::none()};
 
   MemoryEffects ME = MemoryEffects::none();
+  // Additional locations accessed if the SCC accesses argmem.
+  MemoryEffects RecursiveArgME = MemoryEffects::none();
+
   // Inalloca and preallocated arguments are always clobbered by the call.
   if (F.getAttributes().hasAttrSomewhere(Attribute::InAlloca) ||
       F.getAttributes().hasAttrSomewhere(Attribute::Preallocated))
     ME |= MemoryEffects::argMemOnly(ModRefInfo::ModRef);
 
   // Scan the function body for instructions that may read or write memory.
   for (Instruction &I : instructions(F)) {
     // Some instructions can be ignored even if they read or write memory.
     // Detect these now, skipping to the next instruction if one is found.
     if (auto *Call = dyn_cast<CallBase>(&I)) {
-      // Ignore calls to functions in the same SCC, as long as the call sites
-      // don't have operand bundles.  Calls with operand bundles are allowed to
-      // have memory effects not described by the memory effects of the call
-      // target.
+      // We can optimistically ignore calls to functions in the same SCC, with
+      // two caveats:
+      //  * Calls with operand bundles may have additional effects.
+      //  * Argument memory accesses may imply additional effects depending on
+      //    what the argument location is.
       if (!Call->hasOperandBundles() && Call->getCalledFunction() &&
-          SCCNodes.count(Call->getCalledFunction()))
+          SCCNodes.count(Call->getCalledFunction())) {
+        // Keep track of which additional locations are accessed if the SCC
+        // turns out to access argmem.
+        addArgLocs(RecursiveArgME, Call, ModRefInfo::ModRef, AAR);
         continue;
+      }
+
       MemoryEffects CallME = AAR.getMemoryEffects(Call);
 
       // If the call doesn't access memory, we're done.
       if (CallME.doesNotAccessMemory())
         continue;
 
       // A pseudo probe call shouldn't change any function attribute since it
       // doesn't translate to a real instruction. It comes with a memory access
for (Instruction &I : instructions(F)) {
 
     // Volatile operations may access inaccessible memory.
     if (I.isVolatile())
       ME |= MemoryEffects::inaccessibleMemOnly(MR);
 
     addLocAccess(ME, *Loc, MR, AAR);
   }
 
-  return OrigME & ME;
+  return {OrigME & ME, RecursiveArgME};
 }
 
 MemoryEffects llvm::computeFunctionBodyMemoryAccess(Function &F,
                                                     AAResults &AAR) {
-  return checkFunctionMemoryAccess(F, /*ThisBody=*/true, AAR, {});
+  return checkFunctionMemoryAccess(F, /*ThisBody=*/true, AAR, {}).first;
 }
 
 /// Deduce readonly/readnone/writeonly attributes for the SCC.
 template <typename AARGetterT>
 static void addMemoryAttrs(const SCCNodeSet &SCCNodes, AARGetterT &&AARGetter,
                            SmallSet<Function *, 8> &Changed) {
   MemoryEffects ME = MemoryEffects::none();
+  MemoryEffects RecursiveArgME = MemoryEffects::none();
   for (Function *F : SCCNodes) {
     // Call the callable parameter to look up AA results for this function.
     AAResults &AAR = AARGetter(*F);
     // Non-exact function definitions may not be selected at link time, and an
     // alternative version that writes to memory may be selected.  See the
     // comment on GlobalValue::isDefinitionExact for more details.
-    ME |= checkFunctionMemoryAccess(*F, F->hasExactDefinition(), AAR, SCCNodes);
+    auto [FnME, FnRecursiveArgME] =
+        checkFunctionMemoryAccess(*F, F->hasExactDefinition(), AAR, SCCNodes);
+    ME |= FnME;
+    RecursiveArgME |= FnRecursiveArgME;
     // Reached bottom of the lattice, we will not be able to improve the result.
     if (ME == MemoryEffects::unknown())
       return;
   }
 
+  // If the SCC accesses argmem, add recursive accesses resulting from that.
+  ModRefInfo ArgMR = ME.getModRef(IRMemLocation::ArgMem);
+  if (ArgMR != ModRefInfo::NoModRef)
+    ME |= RecursiveArgME & MemoryEffects(ArgMR);
+
   for (Function *F : SCCNodes) {
     MemoryEffects OldME = F->getMemoryEffects();
     MemoryEffects NewME = ME & OldME;
     if (NewME != OldME) {
       ++NumMemoryAttr;
       F->setMemoryEffects(NewME);
       Changed.insert(F);
     }

llvm/test/Transforms/FunctionAttrs/argmemonly.ll

;
   call void @fn_inaccessiblememonly()
   ret void
 }
 
 define void @test_inaccessiblememonly_readonly() {
 ; FNATTRS: Function Attrs: nofree memory(inaccessiblemem: read)
 ; FNATTRS-LABEL: define void @test_inaccessiblememonly_readonly
 ; FNATTRS-SAME: () #[[ATTR13:[0-9]+]] {
-; FNATTRS-NEXT:    call void @fn_inaccessiblememonly() #[[ATTR18:[0-9]+]]
+; FNATTRS-NEXT:    call void @fn_inaccessiblememonly() #[[ATTR19:[0-9]+]]
 ; FNATTRS-NEXT:    ret void
 ;
 ; ATTRIBUTOR: Function Attrs: nosync memory(inaccessiblemem: read)
 ; ATTRIBUTOR-LABEL: define void @test_inaccessiblememonly_readonly
 ; ATTRIBUTOR-SAME: () #[[ATTR12:[0-9]+]] {
 ; ATTRIBUTOR-NEXT:    call void @fn_inaccessiblememonly() #[[ATTR21:[0-9]+]]
 ; ATTRIBUTOR-NEXT:    ret void
 ;
   call void @fn_inaccessiblememonly() readonly
   ret void
 }
 
 define void @test_inaccessibleorargmemonly_readonly(ptr %arg) {
 ; FNATTRS: Function Attrs: nofree memory(argmem: read, inaccessiblemem: read)
 ; FNATTRS-LABEL: define void @test_inaccessibleorargmemonly_readonly
 ; FNATTRS-SAME: (ptr nocapture readonly [[ARG:%.*]]) #[[ATTR14:[0-9]+]] {
 ; FNATTRS-NEXT:    [[TMP1:%.*]] = load i32, ptr [[ARG]], align 4
-; FNATTRS-NEXT:    call void @fn_inaccessiblememonly() #[[ATTR18]]
+; FNATTRS-NEXT:    call void @fn_inaccessiblememonly() #[[ATTR19]]
 ; FNATTRS-NEXT:    ret void
 ;
 ; ATTRIBUTOR: Function Attrs: nosync memory(argmem: read, inaccessiblemem: read)
 ; ATTRIBUTOR-LABEL: define void @test_inaccessibleorargmemonly_readonly
 ; ATTRIBUTOR-SAME: (ptr nocapture nofree nonnull readonly [[ARG:%.*]]) #[[ATTR13:[0-9]+]] {
 ; ATTRIBUTOR-NEXT:    [[TMP1:%.*]] = load i32, ptr [[ARG]], align 4
 ; ATTRIBUTOR-NEXT:    call void @fn_inaccessiblememonly() #[[ATTR21]]
 ; ATTRIBUTOR-NEXT:    ret void
 ;
   load i32, ptr %arg
   call void @fn_inaccessiblememonly() readonly
   ret void
 }
 
 define void @test_inaccessibleorargmemonly_readwrite(ptr %arg) {
 ; FNATTRS: Function Attrs: memory(argmem: write, inaccessiblemem: read)
 ; FNATTRS-LABEL: define void @test_inaccessibleorargmemonly_readwrite
 ; FNATTRS-SAME: (ptr nocapture writeonly [[ARG:%.*]]) #[[ATTR15:[0-9]+]] {
 ; FNATTRS-NEXT:    store i32 0, ptr [[ARG]], align 4
-; FNATTRS-NEXT:    call void @fn_inaccessiblememonly() #[[ATTR18]]
+; FNATTRS-NEXT:    call void @fn_inaccessiblememonly() #[[ATTR19]]
 ; FNATTRS-NEXT:    ret void
 ;
 ; ATTRIBUTOR: Function Attrs: nosync memory(argmem: readwrite, inaccessiblemem: readwrite)
 ; ATTRIBUTOR-LABEL: define void @test_inaccessibleorargmemonly_readwrite
 ; ATTRIBUTOR-SAME: (ptr nocapture nofree nonnull writeonly [[ARG:%.*]]) #[[ATTR14:[0-9]+]] {
 ; ATTRIBUTOR-NEXT:    store i32 0, ptr [[ARG]], align 4
 ; ATTRIBUTOR-NEXT:    call void @fn_inaccessiblememonly() #[[ATTR21]]
 ; ATTRIBUTOR-NEXT:    ret void
 ;
   store i32 0, ptr %arg
   call void @fn_inaccessiblememonly() readonly
   ret void
 }
 
 define void @test_recursive_argmem_read(ptr %p) {
-; FNATTRS: Function Attrs: nofree nosync nounwind memory(argmem: read)
+; FNATTRS: Function Attrs: nofree nosync nounwind memory(read, inaccessiblemem: none)
 ; FNATTRS-LABEL: define void @test_recursive_argmem_read
 ; FNATTRS-SAME: (ptr nocapture readonly [[P:%.*]]) #[[ATTR16:[0-9]+]] {
 ; FNATTRS-NEXT:    [[PVAL:%.*]] = load ptr, ptr [[P]], align 8
 ; FNATTRS-NEXT:    call void @test_recursive_argmem_read(ptr [[PVAL]])
 ; FNATTRS-NEXT:    ret void
 ;
 ; ATTRIBUTOR: Function Attrs: nofree nosync nounwind memory(read)
 ; ATTRIBUTOR-LABEL: define void @test_recursive_argmem_read
 ; ATTRIBUTOR-SAME: (ptr nocapture nofree nonnull readonly [[P:%.*]]) #[[ATTR15:[0-9]+]] {
 ; ATTRIBUTOR-NEXT:    [[PVAL:%.*]] = load ptr, ptr [[P]], align 8
 ; ATTRIBUTOR-NEXT:    call void @test_recursive_argmem_read(ptr nocapture nofree readonly [[PVAL]]) #[[ATTR15]]
 ; ATTRIBUTOR-NEXT:    ret void
 ;
   %pval = load ptr, ptr %p
   call void @test_recursive_argmem_read(ptr %pval)
   ret void
 }
 
 define void @test_recursive_argmem_readwrite(ptr %p) {
-; FNATTRS: Function Attrs: nofree nosync nounwind memory(argmem: readwrite)
+; FNATTRS: Function Attrs: nofree nosync nounwind memory(readwrite, inaccessiblemem: none)
 ; FNATTRS-LABEL: define void @test_recursive_argmem_readwrite
 ; FNATTRS-SAME: (ptr nocapture [[P:%.*]]) #[[ATTR17:[0-9]+]] {
 ; FNATTRS-NEXT:    [[PVAL:%.*]] = load ptr, ptr [[P]], align 8
 ; FNATTRS-NEXT:    store i32 0, ptr [[P]], align 4
 ; FNATTRS-NEXT:    call void @test_recursive_argmem_readwrite(ptr [[PVAL]])
 ; FNATTRS-NEXT:    ret void
 ;
 ; ATTRIBUTOR: Function Attrs: nofree nosync nounwind
 ; ATTRIBUTOR-LABEL: define void @test_recursive_argmem_readwrite
 ; ATTRIBUTOR-SAME: (ptr nocapture nofree nonnull [[P:%.*]]) #[[ATTR16:[0-9]+]] {
 ; ATTRIBUTOR-NEXT:    [[PVAL:%.*]] = load ptr, ptr [[P]], align 8
 ; ATTRIBUTOR-NEXT:    store i32 0, ptr [[P]], align 4
 ; ATTRIBUTOR-NEXT:    call void @test_recursive_argmem_readwrite(ptr nocapture nofree [[PVAL]]) #[[ATTR16]]
 ; ATTRIBUTOR-NEXT:    ret void
 ;
   %pval = load ptr, ptr %p
   store i32 0, ptr %p
   call void @test_recursive_argmem_readwrite(ptr %pval)
   ret void
 }
 
 define void @test_recursive_argmem_read_alloca(ptr %p) {
 ; FNATTRS: Function Attrs: nofree nosync nounwind memory(argmem: read)
 ; FNATTRS-LABEL: define void @test_recursive_argmem_read_alloca
-; FNATTRS-SAME: (ptr nocapture readonly [[P:%.*]]) #[[ATTR16]] {
+; FNATTRS-SAME: (ptr nocapture readonly [[P:%.*]]) #[[ATTR18:[0-9]+]] {
 ; FNATTRS-NEXT:    [[A:%.*]] = alloca ptr, align 8
 ; FNATTRS-NEXT:    [[TMP1:%.*]] = load i32, ptr [[P]], align 4
 ; FNATTRS-NEXT:    call void @test_recursive_argmem_read_alloca(ptr [[A]])
 ; FNATTRS-NEXT:    ret void
 ;
 ; ATTRIBUTOR: Function Attrs: nofree nosync nounwind memory(argmem: read)
 ; ATTRIBUTOR-LABEL: define void @test_recursive_argmem_read_alloca
 ; ATTRIBUTOR-SAME: (ptr nocapture nofree nonnull readonly [[P:%.*]]) #[[ATTR17:[0-9]+]] {
 ; ATTRIBUTOR-NEXT:    [[A:%.*]] = alloca ptr, align 8
 ; ATTRIBUTOR-NEXT:    [[TMP1:%.*]] = load i32, ptr [[P]], align 4
 ; ATTRIBUTOR-NEXT:    call void @test_recursive_argmem_read_alloca(ptr nocapture nofree nonnull readonly [[A]]) #[[ATTR15]]
 ; ATTRIBUTOR-NEXT:    ret void
 ;
   %a = alloca ptr
   load i32, ptr %p
   call void @test_recursive_argmem_read_alloca(ptr %a)
   ret void
 }
 
 define void @test_scc_argmem_read_1(ptr %p) {
-; FNATTRS: Function Attrs: nofree nosync nounwind memory(argmem: read)
+; FNATTRS: Function Attrs: nofree nosync nounwind memory(read, inaccessiblemem: none)
 ; FNATTRS-LABEL: define void @test_scc_argmem_read_1
 ; FNATTRS-SAME: (ptr nocapture readonly [[P:%.*]]) #[[ATTR16]] {
 ; FNATTRS-NEXT:    [[PVAL:%.*]] = load ptr, ptr [[P]], align 8
 ; FNATTRS-NEXT:    call void @test_scc_argmem_read_2(ptr [[PVAL]])
 ; FNATTRS-NEXT:    ret void
 ;
 ; ATTRIBUTOR: Function Attrs: nofree nosync nounwind memory(read)
 ; ATTRIBUTOR-LABEL: define void @test_scc_argmem_read_1
 ; ATTRIBUTOR-SAME: (ptr nocapture nofree nonnull readonly [[P:%.*]]) #[[ATTR15]] {
 ; ATTRIBUTOR-NEXT:    [[PVAL:%.*]] = load ptr, ptr [[P]], align 8
 ; ATTRIBUTOR-NEXT:    call void @test_scc_argmem_read_2(ptr nocapture nofree readonly [[PVAL]]) #[[ATTR15]]
 ; ATTRIBUTOR-NEXT:    ret void
 ;
   %pval = load ptr, ptr %p
   call void @test_scc_argmem_read_2(ptr %pval)
   ret void
 }
 
 define void @test_scc_argmem_read_2(ptr %p) {
-; FNATTRS: Function Attrs: nofree nosync nounwind memory(argmem: read)
+; FNATTRS: Function Attrs: nofree nosync nounwind memory(read, inaccessiblemem: none)
 ; FNATTRS-LABEL: define void @test_scc_argmem_read_2
 ; FNATTRS-SAME: (ptr nocapture readonly [[P:%.*]]) #[[ATTR16]] {
 ; FNATTRS-NEXT:    call void @test_scc_argmem_read_1(ptr [[P]])
 ; FNATTRS-NEXT:    ret void
 ;
 ; ATTRIBUTOR: Function Attrs: nofree nosync nounwind memory(read)
 ; ATTRIBUTOR-LABEL: define void @test_scc_argmem_read_2
 ; ATTRIBUTOR-SAME: (ptr nocapture nofree readonly [[P:%.*]]) #[[ATTR15]] {
 ; ATTRIBUTOR-NEXT:    call void @test_scc_argmem_read_1(ptr nocapture nofree readonly [[P]]) #[[ATTR15]]
 ; ATTRIBUTOR-NEXT:    ret void
 ;
   call void @test_scc_argmem_read_1(ptr %p)
   ret void
 }