This is an archive of the discontinued LLVM Phabricator instance.

[GlobalsAA] Teach GlobalsAA about nocapture
ClosedPublic

Authored by jmolloy on Sep 14 2015, 7:46 AM.

Details

Summary

Arguments to function calls marked "nocapture" can be marked as
non-escaping. However, nocapture is defined in terms of the lifetime
of the callee, and if the callee can directly or indirectly recurse to
the caller, the semantics of nocapture are invalid.

Therefore, we eagerly discover all known non-recursive functions and
then, in AnalyzeUsesOfPointer() we can query that set for nocapture
arguments.

This means that we can't be so optimistic in
getModRefInfo(ImmutableCallsite) - previously we assumed all call
arguments never aliased with an escaping global. Now we need to check,
because a global could now be passed as an argument but still not
escape.

This also solves a related conformance problem: MemCpyOptimizer can
turn non-escaping stores of globals into calls to intrinsics like
llvm.memcpy/llvm/memset. This confuses GlobalsAA, which knows the
global can't escape and so returns NoModRef when queried, when
obviously a memcpy/memset call does indeed reference and modify its
arguments.

This addresses PR24800, PR24801, and PR24802

Diff Detail

Repository
rL LLVM

Event Timeline

jmolloy updated this revision to Diff 34668.Sep 14 2015, 7:46 AM
jmolloy retitled this revision from to [GlobalsAA] Teach GlobalsAA about memory intrinsics.
jmolloy updated this object.
jmolloy added reviewers: chandlerc, majnemer, hfinkel.
jmolloy set the repository for this revision to rL LLVM.
jmolloy added a subscriber: llvm-commits.
aadg added a subscriber: aadg.Sep 14 2015, 8:02 AM

Hi James,

See comment below.

lib/Analysis/GlobalsModRef.cpp
776–782

Shouldn't we also handle the isVolatile argument ? As anything could happen when this is a volatile operation, I think we should always return MRI_ModRef when it is set.

hfinkel edited edge metadata.Sep 14 2015, 9:06 AM

Actually, I wonder if the right solution here is somewhat more general. As I recall, generally speaking, GMR cannot use 'nocapture' attributes on functions parameters because:

  1. It cannot use nocapture on the parent function's arguments because nocapture is a statement only about appearances to the caller, not a guarantee about what happens inside the function itself.
  2. It cannot use nocapture on attributes on the call instructions because it is possible that the function is directly or indirectly recursive, and so (1) applies.

And, so, we can honor nocapture for any function calls which we can prove are not directly or indirectly recursive with the current function. This seems like something we could do given that we have a callgraph, and perhaps can assert more generally for all intrinsics?

lib/Analysis/GlobalsModRef.cpp
776–782

I agree with James's response (from the list, which is seems did not make it into Phabricator); volatility and aliasing are orthogonal concepts, and while we do imply aliasing affects to volatile operations (and atomics) in various places (for reasons that I'm sure seemed convenient at the time), it is really not a good thing, and I see no reason to do so here.

sanjoy added a subscriber: sanjoy.Sep 14 2015, 9:19 AM
sanjoy added inline comments.
lib/Analysis/GlobalsModRef.cpp
771

I'd rather have this be a lambda that takes an argument index instead of an eagerly populated vector, given that for most intrinsics this isn't used.

776

Can we do something more precise here if the intrinsic is readonly or readnone?

aadg added inline comments.Sep 14 2015, 9:56 AM
lib/Analysis/GlobalsModRef.cpp
776–782

Ok, I agree checking the volatileness should not be done here, but at the place where the aliasing information is used.

jmolloy updated this revision to Diff 34798.Sep 15 2015, 5:03 AM
jmolloy edited edge metadata.

Hi all,

Updated diff addressing Sanjoy's comments.

Cheers,

James

jmolloy updated this revision to Diff 34799.Sep 15 2015, 5:04 AM

And update the test to specifically enable GMR in the pass pipeline now the switch has been flipped off again.

jmolloy updated this revision to Diff 34990.Sep 17 2015, 7:20 AM
jmolloy retitled this revision from [GlobalsAA] Teach GlobalsAA about memory intrinsics to [GlobalsAA] Teach GlobalsAA about nocapture.
jmolloy updated this object.

Hi Hal,

OK, what you said makes sense. I've updated this patch to handle nocapture properly, which indeed is a superset of the functionality in the previous patch.

Cheers,

James

jmolloy updated this revision to Diff 34991.Sep 17 2015, 7:21 AM
jmolloy updated this revision to Diff 34992.Sep 17 2015, 7:24 AM

I think that the check that you would really want to do is: are the caller and the callee in the same connected component? Can you cache enough information from the CallGraphSCC iteration to check that directly?

jmolloy updated this revision to Diff 35011.Sep 17 2015, 9:25 AM

Hi Hal,

That makes sense, it'd be less conservative. This updated patch does that - it iterates through the SCCs, assigning a numeric ID to each and storing a map of Function -> SCC ID that we can query later.

Cheers,

James

jmolloy updated this revision to Diff 35012.Sep 17 2015, 9:27 AM

Hi Hal,

Did you have any more comments on this?

Cheers,

James

hfinkel added inline comments.Sep 23 2015, 12:02 AM
lib/Analysis/GlobalsModRef.cpp
777

This check does not seem conservative enough. GetUnderlyingObject has a depth limit, and cannot look through PHIs/selects. Since we know that GV is not captured as a precondition of this function (which we should explicitly document), calling GetUnderlyingObjects with no depth limit might be conservatively correct, although I'm afraid of unbounded compile-time in that case, Alternatively, you can call GetUnderlyingObject (or better, GetUnderlyingObjects), but return conservatively if not all returned objects are such that isIdentifiedObject returns true.

jmolloy updated this revision to Diff 35663.Sep 24 2015, 11:51 AM

Hi Hal,

That makes total sense. This new patch makes sure all objects were identified and if not, returns ConservativeResult.

Cheers,

James

hfinkel accepted this revision.Sep 25 2015, 5:50 AM
hfinkel edited edge metadata.

LGTM.

This revision is now accepted and ready to land.Sep 25 2015, 5:50 AM
jmolloy closed this revision.Sep 25 2015, 8:41 AM

Thanks, r248576.