[AA] Model operand bundles more precisely

[nikic]

Summary

Based on D130896, we can model operand bundles more precisely. In addition to the baseline ModRefBehavior, a reading/clobbering operand bundle may also read/write all locations. For example, a memcpy with deopt bundle can read any memory, but only write argument memory.

This means that getModRefInfo() for memcpy with a pointer that does not alias the arguments results in Ref, rather than ModRef, without the need to implement any special handling.

Depends on D130896.

[nikic]

Update OperandBundles/basic-aa-argmemonly.ll test, which now optimizes as well.

[reames]

Replying only to this text from your description:
"For example, a memcpy with deopt bundle can read and write argument memory, but only read inaccessible and other memory."

I can't quite parse exactly what you mean here, but it *sounds* like you're saying the deopt bundle isn't allowed to read arbitrary (captured) memory. If so, we've talked ourselves into a bad result, because that's exactly what deopt needs to do.

Conceptually, "deopt" captures the abstract machine state of the running thread. The arguments to deopt are obviously part of that, but so is any memory which is a) visible from another thread, or b) visible from any of the captured state. So, in general, a deopt operand needs to read all memory which we can't *explicitly* prove hasn't been captured at or before the call.

[nikic]

In D130980#3762564, @reames wrote:

Replying only to this text from your description:
"For example, a memcpy with deopt bundle can read and write argument memory, but only read inaccessible and other memory."

I can't quite parse exactly what you mean here, but it *sounds* like you're saying the deopt bundle isn't allowed to read arbitrary (captured) memory. If so, we've talked ourselves into a bad result, because that's exactly what deopt needs to do.

Conceptually, "deopt" captures the abstract machine state of the running thread. The arguments to deopt are obviously part of that, but so is any memory which is a) visible from another thread, or b) visible from any of the captured state. So, in general, a deopt operand needs to read all memory which we can't *explicitly* prove hasn't been captured at or before the call.

The phrasing here was unnecessarily confusing. What we want to model is that memcpy+deopt can read any memory and write argument memory. Importantly, this excludes *writing* to captured memory.

[ebrevnov]

llvm/include/llvm/Analysis/AliasAnalysis.h

267 ↗

(On Diff #450723)

Was wondering why you missing this when looking into D130896. Not super critical but would be nice if you move it there.

368 ↗

(On Diff #450723)

Same suggestion as for writeOnly. Let's move it to the patch where API is introduced.

[nikic]

Rebase

[reames]

In D130980#3763305, @nikic wrote:

In D130980#3762564, @reames wrote:

Replying only to this text from your description:
"For example, a memcpy with deopt bundle can read and write argument memory, but only read inaccessible and other memory."

I can't quite parse exactly what you mean here, but it *sounds* like you're saying the deopt bundle isn't allowed to read arbitrary (captured) memory. If so, we've talked ourselves into a bad result, because that's exactly what deopt needs to do.

Conceptually, "deopt" captures the abstract machine state of the running thread. The arguments to deopt are obviously part of that, but so is any memory which is a) visible from another thread, or b) visible from any of the captured state. So, in general, a deopt operand needs to read all memory which we can't *explicitly* prove hasn't been captured at or before the call.

The phrasing here was unnecessarily confusing. What we want to model is that memcpy+deopt can read any memory and write argument memory. Importantly, this excludes *writing* to captured memory.

Ah, glad to hear we're on the same page.

[nikic]

Rebase

[nikic]

Ping :)

[reames]

LGTM

llvm/lib/Analysis/AliasAnalysis.cpp

237–238

After staring at this for a bit, I concluded this was correct, but the bit about explicitly ignoring the InaccessibleMem effects here is subtle, and might be worth an explicit call out. The current comment/structure makes it look like the ignoring InaccessibleMem in lower points might be a mistake.

llvm/lib/Analysis/AliasAnalysis.cpp

for (const auto &AA : AAs) {
     Result &= AA->getModRefInfo(Call, Loc, AAQI);
 
     // Early-exit the moment we reach the bottom of the lattice.
     if (isNoModRef(Result))
       return ModRefInfo::NoModRef;
   }
 
   // Try to refine the mod-ref info further using other API entry points to the
   // aggregate set of AA results.
-  auto MRB = getModRefBehavior(Call);
-  if (MRB.onlyAccessesInaccessibleMem())
-    return ModRefInfo::NoModRef;
 
-  // TODO: Exclude inaccessible memory location here.
-  Result &= MRB.getModRef();
+  // We can completely ignore inaccessible memory here, because MemoryLocations
+  // can only reference accessible memory.
+  auto MRB = getModRefBehavior(Call).getWithoutLoc(
+      FunctionModRefBehavior::InaccessibleMem);
+  if (MRB.doesNotAccessMemory())
+    return ModRefInfo::NoModRef;
 
-  if (MRB.onlyAccessesArgPointees() || MRB.onlyAccessesInaccessibleOrArgMem()) {
+  ModRefInfo ArgMR = MRB.getModRef(FunctionModRefBehavior::ArgMem);
+  ModRefInfo OtherMR =
+      MRB.getWithoutLoc(FunctionModRefBehavior::ArgMem).getModRef();
+  if ((ArgMR | OtherMR) != OtherMR) {
+    // Refine the modref info for argument memory. We only bother to do this
+    // if ArgMR is not a subset of OtherMR, otherwise this won't have an impact
+    // on the final result.
     ModRefInfo AllArgsMask = ModRefInfo::NoModRef;
-    if (MRB.doesAccessArgPointees()) {
-      for (const auto &I : llvm::enumerate(Call->args())) {
-        const Value *Arg = I.value();
-        if (!Arg->getType()->isPointerTy())
-          continue;
-        unsigned ArgIdx = I.index();
-        MemoryLocation ArgLoc =
-            MemoryLocation::getForArgument(Call, ArgIdx, TLI);
-        AliasResult ArgAlias = alias(ArgLoc, Loc, AAQI);
-        if (ArgAlias != AliasResult::NoAlias)
-          AllArgsMask |= getArgModRefInfo(Call, ArgIdx);
-      }
-    }
-    // Return NoModRef if no alias found with any argument.
-    if (isNoModRef(AllArgsMask))
-      return ModRefInfo::NoModRef;
-    // Logical & between other AA analyses and argument analysis.
-    Result &= AllArgsMask;
-  }
+      MemoryLocation ArgLoc = MemoryLocation::getForArgument(Call, ArgIdx, TLI);
+    ArgMR &= AllArgsMask;
+
+  Result &= ArgMR | OtherMR;
 
   // If Loc is a constant memory location, the call definitely could not
   // modify the memory location.
   if (isModSet(Result) && pointsToConstantMemory(Loc, AAQI, /*OrLocal*/ false))
     Result &= ModRefInfo::Ref;
 
   return Result;
 }

llvm/lib/Analysis/BasicAliasAnalysis.cpp

FunctionModRefBehavior BasicAAResult::getModRefBehavior(const CallBase *Call) {
   FunctionModRefBehavior Min(MR);
   if (Call->onlyAccessesArgMemory())
     Min = FunctionModRefBehavior::argMemOnly(MR);
   else if (Call->onlyAccessesInaccessibleMemory())
     Min = FunctionModRefBehavior::inaccessibleMemOnly(MR);
   else if (Call->onlyAccessesInaccessibleMemOrArgMem())
     Min = FunctionModRefBehavior::inaccessibleOrArgMemOnly(MR);
 
-  // If the call has operand bundles then aliasing attributes from the function
-  // it calls do not directly apply to the call.  This can be made more precise
-  // in the future.
-  if (!Call->hasOperandBundles())
-    if (const Function *F = Call->getCalledFunction())
-      Min &= getBestAAResults().getModRefBehavior(F);
+  if (const Function *F = Call->getCalledFunction()) {
+    FunctionModRefBehavior FMRB = getBestAAResults().getModRefBehavior(F);
+    // Operand bundles on the call may also read or write memory, in addition
+    // to the behavior of the called function.
+    if (Call->hasReadingOperandBundles())
+      FMRB |= FunctionModRefBehavior::readOnly();
+    if (Call->hasClobberingOperandBundles())
+      FMRB |= FunctionModRefBehavior::writeOnly();
+    Min &= FMRB;
+  }
 
   return Min;
 }
 
 /// Returns the behavior when calling the given function. For use when the call
 /// site is not known.
 FunctionModRefBehavior BasicAAResult::getModRefBehavior(const Function *F) {
   // If the function declares it doesn't access memory, we can't do better.
ModRefInfo BasicAAResult::getModRefInfo(const CallBase *Call,
   if (isMallocOrCallocLikeFn(Call, &TLI)) {
     // Be conservative if the accessed pointer may alias the allocation -
     // fallback to the generic handling below.
     if (getBestAAResults().alias(MemoryLocation::getBeforeOrAfter(Call), Loc,
                                  AAQI) == AliasResult::NoAlias)
       return ModRefInfo::NoModRef;
   }
 
-  // Ideally, there should be no need to special case for memcpy/memove
-  // intrinsics here since general machinery (based on memory attributes) should
-  // already handle it just fine. Unfortunately, it doesn't due to deficiency in
-  // operand bundles support. At the moment it's not clear if complexity behind
-  // enhancing general mechanism worths it.
-  // TODO: Consider improving operand bundles support in general mechanism.
-  if (auto *Inst = dyn_cast<AnyMemTransferInst>(Call)) {
-    AliasResult SrcAA =
-        getBestAAResults().alias(MemoryLocation::getForSource(Inst), Loc, AAQI);
-    AliasResult DestAA =
-        getBestAAResults().alias(MemoryLocation::getForDest(Inst), Loc, AAQI);
-    // It's also possible for Loc to alias both src and dest, or neither.
-    ModRefInfo rv = ModRefInfo::NoModRef;
-    if (SrcAA != AliasResult::NoAlias || Call->hasReadingOperandBundles())
-      rv |= ModRefInfo::Ref;
-    if (DestAA != AliasResult::NoAlias || Call->hasClobberingOperandBundles())
-      rv |= ModRefInfo::Mod;
-    return rv;
-  }
-
   // Guard intrinsics are marked as arbitrarily writing so that proper control
   // dependencies are maintained but they never mods any particular memory
   // location.
   //
   // *Unlike* assumes, guard intrinsics are modeled as reading memory since the
   // heap state at the point the guard is issued needs to be consistent in case
   // the guard invokes the "deopt" continuation.
   if (isIntrinsicCall(Call, Intrinsic::experimental_guard))

llvm/test/Feature/OperandBundles/basic-aa-argmemonly.ll

 }
 
 define i32 @test2(i32* %P, i32* noalias %P2) {
 ; Note: in this test we //can// GVN %v1 and %v2 into one value in theory.  Calls
 ; with deopt operand bundles are not argmemonly because they *read* the entire
 ; heap, but they don't write to any location in the heap if the callee does not
 ; deoptimize the caller.  This fact, combined with the fact that
 ; @argmemonly_function is, well, an argmemonly function, can be used to conclude
-; that %P is not written to at the callsite.  However LLVM currently cannot
-; describe the "does not write to non-args, and reads the entire heap" effect on
-; a callsite.
+; that %P is not written to at the callsite.
 
 ; CHECK-LABEL: @test2(
   %v1 = load i32, i32* %P
-; CHECK: %v1 = load i32, i32* %P
   call void @argmemonly_function(i32* %P2) [ "deopt"() ]
 ; CHECK: call void @argmemonly_function(
   %v2 = load i32, i32* %P
-; CHECK: %v2 = load i32, i32* %P
   %diff = sub i32 %v1, %v2
-; CHECK: %diff = sub i32 %v1, %v2
   ret i32 %diff
-; CHECK: ret i32 %diff
+; CHECK: ret i32 0
 }