[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 ↗

(On Diff #83386)

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 ↗

(On Diff #83386)

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 ↗

(On Diff #83386)

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

5

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

14

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

14

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

14

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

14

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

14

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

14

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);

14

step 2, not 3.

[hfinkel]

test/Analysis/BasicAA/getforargument-crash.ll

14

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

14

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

14

Ah, never mind.

[hfinkel]

test/Analysis/BasicAA/getforargument-crash.ll

14

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

[bryant]

test/Analysis/BasicAA/getforargument-crash.ll

14

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

14

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

14

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

14

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

token gotten from -> token from

133

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/MemoryLocation.cpp

if (const IntrinsicInst *II = dyn_cast<IntrinsicInst>(CS.getInstruction())) {
     case Intrinsic::lifetime_start:
     case Intrinsic::lifetime_end:
     case Intrinsic::invariant_start:
       assert(ArgIdx == 1 && "Invalid argument index");
       return MemoryLocation(
           Arg, cast<ConstantInt>(II->getArgOperand(0))->getZExtValue(), AATags);
 
     case Intrinsic::invariant_end:
-      assert(ArgIdx == 2 && "Invalid argument index");
+      if (ArgIdx == 0)
+        // Technically, this is a token gotten from a previous invariant_start
+        // and not a true pointer, so return a dummy MemoryLocation.
+        return MemoryLocation(Arg, 0);
+      else if (ArgIdx == 2)
         return MemoryLocation(
-          Arg, cast<ConstantInt>(II->getArgOperand(1))->getZExtValue(), AATags);
+            Arg, cast<ConstantInt>(II->getArgOperand(1))->getZExtValue(),
+            AATags);
+      // For all other argument indices, this call is invalid.
+      assert(false && "Invalid argument index");
 
     case Intrinsic::arm_neon_vld1:
       assert(ArgIdx == 0 && "Invalid argument index");
       // LLVM's vld1 and vst1 intrinsics currently only support a single
       // vector register.
       return MemoryLocation(Arg, DL.getTypeStoreSize(II->getType()), AATags);
 
     case Intrinsic::arm_neon_vst1:

test/Analysis/BasicAA/getforargument-crash.ll

+; RUN: opt -disable-output 2>&1 -basicaa -aa-eval -print-all-alias-modref-info \
+; RUN:      %s 2>&1 | FileCheck %s
+
+declare {}* @llvm.invariant.start(i64, i8* nocapture) nounwind readonly
+declare void @llvm.invariant.end({}* readnone, i64, i8* nocapture) nounwind
+declare void @f({}*)
+
+; Previously caused getModRefInfo to retrieve a MemoryLocation for an invalid
+; argument to the intrinsic.
+define void @tests_invariant_start_end() {
+; CHECK-LABEL: 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
+}
+
+; Prove that invariant.end's first argument is readnone.
+define void @it_really_is_readnone({}* %g) {
+; CHECK-LABEL: it_really_is_readnone
+  %a = alloca i8
+  %i = call {}* @llvm.invariant.start(i64 1, i8* %a)
+  call void @f({}* %g)
+  call void @llvm.invariant.end({}* %i, i64 1, i8* %a)
+; CHECK: NoModRef:   call void @f({}* %g) <->   call void @llvm.invariant.end.p0i8({}* %1, i64 1, i8* %a)
+  ret void
+}