[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

269

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

370

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

238–240

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/include/llvm/Analysis/AliasAnalysis.h

static FunctionModRefBehavior none() {
     return FunctionModRefBehavior();
   }
 
   /// Create FunctionModRefBehavior that can read any memory.
   static FunctionModRefBehavior readOnly() {
     return anyLoc(ModRefInfo::Ref);
   }
 
+  /// Create FunctionModRefBehavior that can write any memory.
+  static FunctionModRefBehavior writeOnly() {
+    return anyLoc(ModRefInfo::Mod);
+  }
+
   /// Create FunctionModRefBehavior that can only access argument memory.
   static FunctionModRefBehavior argMemOnly(ModRefInfo MR) {
     return FunctionModRefBehavior(ArgMem, MR);
   }
 
   /// Create FunctionModRefBehavior that can only access inaccessible memory.
   static FunctionModRefBehavior inaccessibleMemOnly(ModRefInfo MR) {
     return FunctionModRefBehavior(InaccessibleMem, MR);
public:
   }
 
   /// Intersect with another FunctionModRefBehavior.
   FunctionModRefBehavior &operator&=(FunctionModRefBehavior Other) {
     Data &= Other.Data;
     return *this;
   }
 
+  /// Union (in-place) with another FunctionModRefBehavior.
+  FunctionModRefBehavior operator|(FunctionModRefBehavior Other) const {
+    return FunctionModRefBehavior(Data | Other.Data);
+  }
+
+  /// Union with another FunctionModRefBehavior.
+  FunctionModRefBehavior &operator|=(FunctionModRefBehavior Other) {
+    Data |= Other.Data;
+    return *this;
+  }
+
   /// Check whether this is the same as another FunctionModRefBehavior.
   bool operator==(FunctionModRefBehavior Other) const {
     return Data == Other.Data;
   }
 
   /// Check whether this is different from another FunctionModRefBehavior.
   bool operator!=(FunctionModRefBehavior Other) const {
     return !operator==(Other);

llvm/lib/Analysis/AliasAnalysis.cpp

for (const auto &AA : AAs) {
 
     // 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())
+  auto MRB = getModRefBehavior(Call).withoutLoc(
+      FunctionModRefBehavior::InaccessibleMem);
+  if (MRB.doesNotAccessMemory())
     return ModRefInfo::NoModRef;
 
-  // TODO: Exclude inaccessible memory location here.
-  Result &= MRB.getModRef();
-
-  if (MRB.onlyAccessesArgPointees() || MRB.onlyAccessesInaccessibleOrArgMem()) {
+  ModRefInfo ArgMR = MRB.getModRef(FunctionModRefBehavior::ArgMem);
+  ModRefInfo OtherMR =
+      MRB.withoutLoc(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 = FunctionModRefBehavior::anyLoc(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))