Page MenuHomePhabricator

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

Authored by bryant on Jan 5 2017, 8:44 PM.

Details

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.

Diff Detail

Repository
rL LLVM

Event Timeline

bryant updated this revision to Diff 83342.Jan 5 2017, 8:44 PM
bryant retitled this revision from to [AA] Limit `MemoryLocation` retrieval to valid intrinsic arguments..
bryant updated this object.
bryant added reviewers: hfinkel, reames, sanjoy, dberlin.
bryant set the repository for this revision to rL LLVM.
bryant added a subscriber: llvm-commits.
bryant retitled this revision from [AA] Limit `MemoryLocation` retrieval to valid intrinsic arguments. to [AliasAnalysis] Limit `MemoryLocation` retrieval to valid intrinsic arguments..Jan 5 2017, 8:53 PM
hfinkel edited edge metadata.Jan 6 2017, 6:04 AM

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?

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 updated this revision to Diff 83386.Jan 6 2017, 11:13 AM
bryant edited edge metadata.
  • arg 0 of invariant.end is now explicitly readnone.
  • don't getForArgument arguments that are readnone.
reames added inline comments.Jan 6 2017, 12:08 PM
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 added inline comments.Jan 6 2017, 7:32 PM
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 added inline comments.Jan 8 2017, 1:26 PM
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 added inline comments.Jan 9 2017, 7:51 AM
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 added inline comments.Jan 9 2017, 9:42 AM
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 added inline comments.Jan 10 2017, 6:04 AM
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 added inline comments.Jan 10 2017, 6:26 AM
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 added inline comments.Jan 10 2017, 6:30 AM
test/Analysis/BasicAA/getforargument-crash.ll
14
  1. 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 added inline comments.Jan 10 2017, 6:34 AM
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 added inline comments.Jan 10 2017, 7:39 AM
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 added inline comments.Jan 10 2017, 8:11 AM
test/Analysis/BasicAA/getforargument-crash.ll
14

Ah, never mind.

hfinkel added inline comments.Jan 10 2017, 8:17 AM
test/Analysis/BasicAA/getforargument-crash.ll
14

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

bryant added inline comments.Jan 10 2017, 8:23 AM
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 added inline comments.Jan 10 2017, 8:29 AM
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 added inline comments.Jan 10 2017, 8:29 AM
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 added inline comments.Jan 10 2017, 8:33 AM
test/Analysis/BasicAA/getforargument-crash.ll
14

Yes, I think we still need the readnone regardless.

bryant updated this revision to Diff 83815.Jan 10 2017, 8:58 AM
  • Return a dummy MemLoc for invariant.end's first argument.
  • Add tests.

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 added inline comments.Jan 10 2017, 11:30 AM
lib/Analysis/MemoryLocation.cpp
125

token gotten from -> token from

133

Use llvm_unreachable instead of assert(false).

reames resigned from this revision.Mar 25 2020, 11:17 AM