[AliasAnalysis] Limit `MemoryLocation` retrieval to valid intrinsic arguments.

[bryant]

Summary

MemoryLocations can only be retrieved from certain arguments of intrinsic calls.
For instance, MemoryLocation::getForArgument would only work on lifetime.end's
second argument.

Currently, getModRefInfo avoids MemoryLocation-ing the wrong argument by
first checking that the argument type is a pointer. This check is inadequate.
For instance, invariant.end has two pointer arguments:

declare void @llvm.invariant.end.p0i8(
    {}* <start>,
    i64 <size>,
    i8* nocapture <ptr>
)

This patch attempts to address this discrepancy.

[hfinkel]

I don't think this is the right solution to this problem. Instead, how about making sure these arguments are tagged with the readnone attribute and then teach AA to ignore those arguments?

[bryant]

Yeah, I wasn't too sure about my fix. Conditioning on Attribute::ReadNone makes way more sense. I'll have a new patch shortly.

[bryant]

• arg 0 of invariant.end is now explicitly readnone.
• don't getForArgument arguments that are readnone.

[reames]

lib/Analysis/AliasAnalysis.cpp

177

I'm missing something here. *Why* is it problematic to ask for a memory location of the parameter to invariant_end? I would expect that to just work.

[bryant]

lib/Analysis/AliasAnalysis.cpp

177

Here are the type sigs for the invariant intrinsics:

declare {}* @llvm.invariant.start.p0i8(i64 <size>, i8* nocapture <ptr>)
declare void @llvm.invariant.end.p0i8({}* readnone <start>, i64 <size>, i8* nocapture <ptr>)

And the semantics for invariant.start:

This intrinsic indicates that until an `llvm.invariant.end` that uses the return value, the referenced memory location is constant and unchanging.

So if I were to venture a guess, the {}* opaque return is meant to be used as a token, not a real memory address. Only the <ptr> parameter of both is a legit pointer, so getForArgument is likewise restricted to that.

(As an aside: Why not have invariant.start return a real pointer to <ptr> with the desired memory semantics?)

I am definitely not an expert on this and defer to Hal for a real explanation.

[hfinkel]

lib/Analysis/AliasAnalysis.cpp

177

Yes, I think this explanation is correct. That pointer is not really a pointer, but rather just a token value used to pair the starting and ending intrinsics. I'm not sure why it is a pointer value at all, but that seems somewhat orthogonal. We could also solve this particular problem by tagging the token return value with noalias, but I think this is more-general solution (although we could do both). In short, this is something we should be doing anyway.

test/Analysis/BasicAA/getforargument-crash.ll

4

You don't have readnone on the first argument; adding it would make it more clear what's going on.

13

Please also add a test case with a regular external function with a readnone argument, showing that it does not alias with some other load/store to that same address.

[bryant]

test/Analysis/BasicAA/getforargument-crash.ll

13

Attempting to construct this second test makes me doubt whether short-circuiting readnone arguments is the right fix. I've tried this IR:

declare void @f(i8* readnone) argmemonly

define i8 @leave_readnone_untouched() {
  %a = alloca i8
  store i8 undef, i8* %a
  call void @f(i8* %a)
  %rv = load i8, i8* %a
  ret i8 %rv
}

With the patch, AA won't bother to examine f's argument, and conclude that NoModRef: Ptr: i8* %a <-> call void @f(i8* %a).

Without the patch, AA would examine the argument and call BasicAAResult::getModRefInfo(CS = f, ArgIdx = 0), which already possesses the savvy to return NoModRef on account of the readnone, and ultimately conclude the same result as before.

In light of this, what should the proper fix now be? It seems to me that the crash in my first test case purely results from the idiosyncrasies of the invariant intrinsics. In fact, they're the only ones in LangRef which use {}*, so it shouldn't be reproducible with any other intrinsic or function call.

[hfinkel]

test/Analysis/BasicAA/getforargument-crash.ll

13

Okay; maybe I misunderstood the problem. Why would this crash previously upon trying to get the MRI on the intrinsic's argument? Is it because of the type of the pointer?

[bryant]

test/Analysis/BasicAA/getforargument-crash.ll

13

The crash happens before MRI is checked. Before checking an argument's MRI, AA first checks if

1. the argument is even a pointer (because if it's not, then no memory is involved; {}* passes this), and
2. if the argument's MemoryLocation would even alias the original query location (this is where the crash happens), and finally, assuming that there might be an alias,
3. checks the MRI by calling AAResults::getArgModRefInfo which eventually descends into BasicAAResult::getModRefInfo

*Why* is it problematic to ask for a memory location of the parameter to invariant_end? I would expect that to just work.

I kind of see Philip's original point. What if we let step 1 pass, i.e., remove the check in MemoryLocation::getForArgument? I'm not entirely sure of the impact of doing this.

[hfinkel]

test/Analysis/BasicAA/getforargument-crash.ll

13

if the argument's MemoryLocation would even alias the original query location (this is where the crash happens), and finally, assuming that there might be an alias,

Yes, but why does it crash?

[bryant]

test/Analysis/BasicAA/getforargument-crash.ll

13

3. checks the MRI by calling AAResults::getArgModRefInfo which eventually descends into BasicAAResult::getModRefInfo

http://llvm-cs.pcc.me.uk/lib/Analysis/AliasAnalysis.cpp#179

MemoryLocation ArgLoc = MemoryLocation::getForArgument(CS = invariant.end, ArgIdx = 0, TLI);

http://llvm-cs.pcc.me.uk/lib/Analysis/MemoryLocation.cpp#123

case Intrinsic::invariant_end:
  assert(ArgIdx == 2 && "Invalid argument index");
  return MemoryLocation(
      Arg, cast<ConstantInt>(II->getArgOperand(1))->getZExtValue(), AATags);

13

step 2, not 3.

[hfinkel]

test/Analysis/BasicAA/getforargument-crash.ll

13

Ah, okay. I'm sorry for leading you down the wrong path here. Philip is right: that assert is not right. That call needs to work for all pointer-typed arguments. We should return some kind of memory location there (just a default one is fine). We should also tag the argument as readnone so that it does not affect anything.

[bryant]

test/Analysis/BasicAA/getforargument-crash.ll

13

So, have getForArgument return a MemoryLocation(Ptr = nullptr)? I think that might trigger an assert in the subsequent call to alias (here http://llvm-cs.pcc.me.uk/lib/Analysis/AliasAnalysis.cpp#180 ). Also, is it even right for getForArgument to return a null MemLoc? Also, if an additional check is inserted before the call to alias, then isn't this equivalent to my original patch that checks beforehand that getForArgument won't assert?

[bryant]

test/Analysis/BasicAA/getforargument-crash.ll

13

Ah, never mind.

[hfinkel]

test/Analysis/BasicAA/getforargument-crash.ll

13

Yep, it should be fine to return a MemoryLocation() (which represents an unknown location).

[bryant]

test/Analysis/BasicAA/getforargument-crash.ll

13

Actually, MemoryLocation(Ptr = nullptr) does crash, but MemoryLocation(Ptr = {}*, Size = 0) doesn't and furthermore never aliases anything besides itself. So I'll add the latter?

[bryant]

test/Analysis/BasicAA/getforargument-crash.ll

13

I wrote too soon. The latter version doesn't crash alias, but could alias other {}* and mess up alias results. But this is fixed with readnone.

[hfinkel]

test/Analysis/BasicAA/getforargument-crash.ll

13

Interesting. Making an aliasing query against MemoryLocation() crashes? We should have a representation for an "unknown location", I'd think, that just causes AA to return MayAlias. In any case, using the available value and Size=0 (or the default of UnknownSize) should be fine too. I'm fine with doing that.

[hfinkel]

test/Analysis/BasicAA/getforargument-crash.ll

13

Yes, I think we still need the readnone regardless.

[bryant]

• Return a dummy MemLoc for invariant.end's first argument.
• Add tests.

[bryant]

Should invariant.start be updated to declare nolias {}* @llvm.invariant.start.p0i8(i64 <size>, i8* nocapture <ptr>)? That way, the returned token is ensured not to mess with AA queries.

[hfinkel]

lib/Analysis/MemoryLocation.cpp

125 ↗

(On Diff #83815)

token gotten from -> token from

133 ↗

(On Diff #83815)

Use llvm_unreachable instead of assert(false).

docs/LangRef.rst

 ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
 
 Syntax:
 """""""
 This is an overloaded intrinsic. The memory object can belong to any address space.
 
 ::
 
-      declare void @llvm.invariant.end.p0i8({}* <start>, i64 <size>, i8* nocapture <ptr>)
+      declare void @llvm.invariant.end.p0i8({}* readnone <start>, i64 <size>, i8* nocapture <ptr>)
 
 Overview:
 """""""""
 
 The '``llvm.invariant.end``' intrinsic specifies that the contents of a
 memory object are mutable.
 
 Arguments:

include/llvm/IR/Intrinsics.td

def int_lifetime_end    : Intrinsic<[],
                                     [llvm_i64_ty, llvm_ptr_ty],
                                     [IntrArgMemOnly, NoCapture<1>]>;
 def int_invariant_start : Intrinsic<[llvm_descriptor_ty],
                                     [llvm_i64_ty, llvm_anyptr_ty],
                                     [IntrArgMemOnly, NoCapture<1>]>;
 def int_invariant_end   : Intrinsic<[],
                                     [llvm_descriptor_ty, llvm_i64_ty,
                                      llvm_anyptr_ty],
-                                    [IntrArgMemOnly, NoCapture<2>]>;
+                                    [IntrArgMemOnly, NoCapture<2>,
+                                     ReadNone<0>]>;
 
 def int_invariant_group_barrier : Intrinsic<[llvm_ptr_ty], 
                                             [llvm_ptr_ty], 
                                             [IntrNoMem]>;
 
 //===------------------------ Stackmap Intrinsics -------------------------===//
 //
 def int_experimental_stackmap : Intrinsic<[],

lib/Analysis/AliasAnalysis.cpp

if (onlyReadsMemory(MRB))
     Result = ModRefInfo(Result & MRI_Ref);
   else if (doesNotReadMemory(MRB))
     Result = ModRefInfo(Result & MRI_Mod);
 
   if (onlyAccessesArgPointees(MRB) || onlyAccessesInaccessibleOrArgMem(MRB)) {
     bool DoesAlias = false;
     ModRefInfo AllArgsMask = MRI_NoModRef;
     if (doesAccessArgPointees(MRB)) {
-      for (auto AI = CS.arg_begin(), AE = CS.arg_end(); AI != AE; ++AI) {
-        const Value *Arg = *AI;
-        if (!Arg->getType()->isPointerTy())
+      for (const auto &A : enumerate(CS.args())) {
+        const Value *Arg = A.Value;
+        unsigned ArgIdx = A.Index;
+        if (!Arg->getType()->isPointerTy() || CS.doesNotAccessMemory(ArgIdx))
           continue;
-        unsigned ArgIdx = std::distance(CS.arg_begin(), AI);
         MemoryLocation ArgLoc = MemoryLocation::getForArgument(CS, ArgIdx, TLI);
         AliasResult ArgAlias = alias(ArgLoc, Loc);
         if (ArgAlias != NoAlias) {
           ModRefInfo ArgMask = getArgModRefInfo(CS, ArgIdx);
           DoesAlias = true;
           AllArgsMask = ModRefInfo(AllArgsMask | ArgMask);
         }
       }
else if (doesNotReadMemory(CS1B))
     Result = ModRefInfo(Result & MRI_Mod);
 
   // If CS2 only access memory through arguments, accumulate the mod/ref
   // information from CS1's references to the memory referenced by
   // CS2's arguments.
   if (onlyAccessesArgPointees(CS2B)) {
     ModRefInfo R = MRI_NoModRef;
     if (doesAccessArgPointees(CS2B)) {
-      for (auto I = CS2.arg_begin(), E = CS2.arg_end(); I != E; ++I) {
-        const Value *Arg = *I;
-        if (!Arg->getType()->isPointerTy())
+      for (const auto &A : enumerate(CS2.args())) {
+        const Value *Arg = A.Value;
+        unsigned CS2ArgIdx = A.Index;
+        if (!Arg->getType()->isPointerTy() ||
+            CS2.doesNotAccessMemory(CS2ArgIdx))
           continue;
-        unsigned CS2ArgIdx = std::distance(CS2.arg_begin(), I);
         auto CS2ArgLoc = MemoryLocation::getForArgument(CS2, CS2ArgIdx, TLI);
 
         // ArgMask indicates what CS2 might do to CS2ArgLoc, and the dependence
         // of CS1 on that location is the inverse.
         ModRefInfo ArgMask = getArgModRefInfo(CS2, CS2ArgIdx);
         if (ArgMask == MRI_Mod)
           ArgMask = MRI_ModRef;
         else if (ArgMask == MRI_Ref)
if (onlyAccessesArgPointees(CS2B)) {
     return R;
   }
 
   // If CS1 only accesses memory through arguments, check if CS2 references
   // any of the memory referenced by CS1's arguments. If not, return NoModRef.
   if (onlyAccessesArgPointees(CS1B)) {
     ModRefInfo R = MRI_NoModRef;
     if (doesAccessArgPointees(CS1B)) {
-      for (auto I = CS1.arg_begin(), E = CS1.arg_end(); I != E; ++I) {
-        const Value *Arg = *I;
-        if (!Arg->getType()->isPointerTy())
+      for (const auto &A : enumerate(CS1.args())) {
+        const Value *Arg = A.Value;
+        unsigned CS1ArgIdx = A.Index;
+        if (!Arg->getType()->isPointerTy() ||
+            CS1.doesNotAccessMemory(CS1ArgIdx))
           continue;
-        unsigned CS1ArgIdx = std::distance(CS1.arg_begin(), I);
         auto CS1ArgLoc = MemoryLocation::getForArgument(CS1, CS1ArgIdx, TLI);
 
         // ArgMask indicates what CS1 might do to CS1ArgLoc; if CS1 might Mod
         // CS1ArgLoc, then we care about either a Mod or a Ref by CS2. If CS1
         // might Ref, then we care only about a Mod by CS2.
         ModRefInfo ArgMask = getArgModRefInfo(CS1, CS1ArgIdx);
         ModRefInfo ArgR = getModRefInfo(CS2, CS1ArgLoc);
         if (((ArgMask & MRI_Mod) != MRI_NoModRef &&

test/Analysis/BasicAA/getforargument-crash.ll

+; RUN: opt -basicaa -aa-eval -disable-output %s 2>/dev/null
+
+declare {}* @llvm.invariant.start(i64, i8* nocapture) nounwind readonly
+declare void @llvm.invariant.end({}*, i64, i8* nocapture) nounwind
+
+; Previously caused getModRefInfo to retrieve a MemoryLocation for an invalid
+; argument to the intrinsic.
+define void @tests.invariant.start.end() {
+  %a = alloca i8
+  %i = call {}* @llvm.invariant.start(i64 1, i8* %a)
+  call void @llvm.invariant.end({}* %i, i64 1, i8* %a)
+  ret void
+}