This is an archive of the discontinued LLVM Phabricator instance.

[AA] Tracking per-location ModRef info in FunctionModRefBehavior (NFCI)
ClosedPublic

Authored by nikic on Aug 1 2022, 5:44 AM.

Details

Summary

Currently, FunctionModRefBehavior tracks whether the function reads or writes memory (ModRefInfo) and which locations it can access (argmem, inaccessiblemem and other). This patch changes it to track ModRef information per-location instead.

To give two examples of why this is useful:

  • D117095 highlights a weakness of ModRef modelling in the presence of operand bundled. For a memcpy call with deopt operand bundle, we want to say that it can read any memory, but only write argument memory. This would allow them to be treated like any other calls. However, we currently can't express this and have to say that it can read or write any memory. (cc @ebrevnov)
  • D127383 would ideally be modelled as a separate threadid location, where threadid Refs outside pre-split coroutines can be ignored (like other accesses to constant memory). The current representation does not allow modelling this precisely. (cc @ChuanqiXu)

The patch as implemented is intended to be NFC, but there are some obvious opportunities for improvements and simplification. To fully capitalize on this we would also want to change the way we represent memory attributes on functions, but that's a larger change, and I think it makes sense to separate out the FunctionModRefBehavior refactoring.

Diff Detail

Event Timeline

nikic created this revision.Aug 1 2022, 5:44 AM
nikic requested review of this revision.Aug 1 2022, 5:44 AM
Herald added a project: Restricted Project. · View Herald TranscriptAug 1 2022, 5:44 AM
nikic updated this revision to Diff 450722.Aug 8 2022, 1:02 AM

Rebase & ping

ebrevnov added a comment.EditedAug 29 2022, 9:14 AM

If nobody do it before I'll do my best to take a look this week.

Hi @nikic

Thanks for moving this forward! In general, the direction looks good to me. Before commenting on specific things I would like to discuss one high level thing. I found new FMRB interface a bit overloaded. It's was hard to quickly understand which API creates new FMRB instance and which makes in place update. My proposal would be:

  1. Make FMRB non-mutable (that would also allow to use static instances for common cases like none, unknown, etc...)
  2. Move location specific API from FMRB to Location. That would separate things out and allow to reduce total number of public API. For example, argMemOnly(ModRefInfo MR) would be not needed as one can simply instantiate FMRB through public constructor.
  3. Don't introduce withModRef & withoutLoc. Instead model operations through 'operator &' and 'operator |'

What do you think?

nikic added a comment.Sep 1 2022, 2:39 AM

Hi @nikic

Thanks for moving this forward! In general, the direction looks good to me. Before commenting on specific things I would like to discuss one high level thing. I found new FMRB interface a bit overloaded. It's was hard to quickly understand which API creates new FMRB instance and which makes in place update. My proposal would be:

  1. Make FMRB non-mutable (that would also allow to use static instances for common cases like none, unknown, etc...)

I think this makes sense, and would mostly be a matter of making setModRef private. withModRef (which returns a new instance) is intended as the public API.

  1. Move location specific API from FMRB to Location. That would separate things out and allow to reduce total number of public API. For example, argMemOnly(ModRefInfo MR) would be not needed as one can simply instantiate FMRB through public constructor.

I'm not sure I understand the suggested API here. Do you mean that instead of FunctionModRefBehavior::argMemOnly(MR) we should write FunctionModRefBehavior(FunctionModRefBehavior::ArgMem, MR), or something else?

  1. Don't introduce withModRef & withoutLoc. Instead model operations through 'operator &' and 'operator |'

I think this would be a bit inconvenient in that manipulating FMRB usually involves first unsetting the old MR for the location and then setting the new one. So FMRB.withModRef(Loc, NewMR) would have to become something like FMRB & ~FunctionModRefInfo(Loc, ModRefInfo::ModRef) | FunctionModRefInfo(Loc, NewMR), which is a bit of a mouthful.

Hi @nikic

Thanks for moving this forward! In general, the direction looks good to me. Before commenting on specific things I would like to discuss one high level thing. I found new FMRB interface a bit overloaded. It's was hard to quickly understand which API creates new FMRB instance and which makes in place update. My proposal would be:

  1. Make FMRB non-mutable (that would also allow to use static instances for common cases like none, unknown, etc...)

I think this makes sense, and would mostly be a matter of making setModRef private. withModRef (which returns a new instance) is intended as the public API.

Cool.

  1. Move location specific API from FMRB to Location. That would separate things out and allow to reduce total number of public API. For example, argMemOnly(ModRefInfo MR) would be not needed as one can simply instantiate FMRB through public constructor.

I'm not sure I understand the suggested API here. Do you mean that instead of FunctionModRefBehavior::argMemOnly(MR) we should write FunctionModRefBehavior(FunctionModRefBehavior::ArgMem, MR), or something else?

Yep, something like that, except, I was thinking about keeping FunctionModRefLocation top level and calling its member FunctionModRefLocation::argMemOnly() to get location.

  1. Don't introduce withModRef & withoutLoc. Instead model operations through 'operator &' and 'operator |'

I think this would be a bit inconvenient in that manipulating FMRB usually involves first unsetting the old MR for the location and then setting the new one. So FMRB.withModRef(Loc, NewMR) would have to become something like FMRB & ~FunctionModRefInfo(Loc, ModRefInfo::ModRef) | FunctionModRefInfo(Loc, NewMR), which is a bit of a mouthful.

Agree. Maybe we can find a bit better name(s). In particular 'withoutLoc' looks confusing.

nikic updated this revision to Diff 457276.Sep 1 2022, 8:01 AM
nikic edited the summary of this revision. (Show Details)

Rebase, remove setModRef from public API, include methods from D130980.

nikic updated this revision to Diff 457279.Sep 1 2022, 8:02 AM

Upload the correct patch...

This *is* a much cleaner way to handle ModRefBehavior.
I left some comments inline, some are nits that's up to you if you think they make sense.

I'm more curious if this change impacts compile-time, since it's being pretty general with the iteration over the number of locations possible and I'm not sure how much of that will be inlined.

llvm/include/llvm/Analysis/AliasAnalysis.h
301

Naming option: getWithModRef?

308

similar getWithoutLoc?

309

nit: I'd find this easier to read if it didn't defer to the withModRef API, even if it's 2 LoC longer.

FunctionModRefBehavior FMRB = *this;
FMRB.setModRef(Loc, ModRefInfo::NoModRef);
return FMRB;
352

Is this return isNoModRef(getModRef(Other)); ?

llvm/lib/Analysis/BasicAliasAnalysis.cpp
765

Not sure how much it's worth avoiding the setting anyLoc when it gets overwritten right after.
Suggestion would be to do:
:759 FunctionModRefBehavior Min;

:765

else
  Min = FunctionModRefBehavior::anyLoc(MR);
polly/lib/Analysis/ScopBuilder.cpp
1643

Shouldn't the check for does not access memory be kept here?
It's included in the onlyReadsMemory below, but it shouldn't add to GlobalReads.

if (FMRB.doesNotAccessMemory())
  return true;
nikic updated this revision to Diff 457521.Sep 2 2022, 12:59 AM
nikic marked 5 inline comments as done.

Address comments

nikic added a comment.Sep 2 2022, 1:00 AM

I'm more curious if this change impacts compile-time, since it's being pretty general with the iteration over the number of locations possible and I'm not sure how much of that will be inlined.

Yeah, I was concerned about compile-time impact as well, but the change doesn't not seem to have any measurable impact.

llvm/lib/Analysis/BasicAliasAnalysis.cpp
765

That would be nice, but C++ doesn't let us :( This would require a default constructor for FunctionModRefBehavior, and effectively initialize to FunctionModRefBehavior::none(). I don't think there is a good way to express this in C++ apart from either using some deeply nested ternaries or putting this in a separate function.

Generally, this makes sense to me. However, reading through, I spot a couple things which don't look NFC.

Can we find a way to stage this change? Here's one idea, but I'm open to others as well.

  1. Leave the AliasAnalysis accessors for the moment, canonicalize code to use them rather than direct comparison of FRM. (This just shrinks the patch.)
  2. Wrap the existing enum in a class of the same name. Add the accessor functions, and use them where obvious.
  3. Move the non-obvious ones into their own reviews.
  4. Change the representation of the class.

The things I spotted are minor, so I can be convinced to approve without splitting, but I would split if it were my patch, if only to convince myself I'd gotten it right.

llvm/lib/Analysis/BasicAliasAnalysis.cpp
784

This bit of code is repeated from the diff above. Seems like a candidate for a helper function. (In a follow up change please!)

llvm/lib/Analysis/GlobalsModRef.cpp
242

This change doesn't look nfc. Previously, the FunctionInfo could only improve AA results on the function. Now, you can get less precise results if you have a FunctionInfo.

llvm/lib/Analysis/TypeBasedAliasAnalysis.cpp
419

Same problem as above. Imagine the call was readnone.

nikic added inline comments.Sep 12 2022, 1:48 PM
llvm/lib/Analysis/BasicAliasAnalysis.cpp
784

These two pieces of code work on different types (Function and CallBase) -- but it's probably possible to reuse them with a templated function...

llvm/lib/Analysis/GlobalsModRef.cpp
242

The relevant detail here is that AAResultBase::getModRefBehavior(F) actually always returns FunctionModRefBehavior::unknown(), so there is no point in intersecting with it.

The reason why the code was written the way it was is probably a historical leftover: I believe that at some point in the past, this was how AA providers were chained. However, nowadays a different layer is responsible for performing the intersection (AAResults). Individual AA providers only return the best result they can produce based on their own information. It will then get intersected with the results from other AA providers by AAResults.

The AAResultBase methods are only default implementations returning the conservative result for the case where an AA provider does not wish to override a specific method.

I can land the removal of the intersection separately to make it more obvious that this patch doesn't change any behavior.

reames accepted this revision.Sep 12 2022, 1:56 PM

LGTM given @nikic's explanation of why my two concerns are actually addressed.

llvm/lib/Analysis/GlobalsModRef.cpp
242

If you could, I'd appreciate it.

This revision is now accepted and ready to land.Sep 12 2022, 1:56 PM
asbirlea accepted this revision.Sep 12 2022, 2:44 PM

LGTM.

llvm/lib/Analysis/BasicAliasAnalysis.cpp
765

Yes, I meant initializing to FunctionModRefBehavior::none(), to avoid one codepath of iterating the locations for argmem and/or inaccessible. But if for the whole patch compile-time is not affected, taking this out shouldn't make much of a difference.

ebrevnov accepted this revision.Sep 13 2022, 3:06 AM

I've left some NITs which are not blockers and can be addressed later. LGTM.

llvm/include/llvm/Analysis/AliasAnalysis.h
257

Naming suggestion: readWrite or canReadWrite or doReadWrite.

262

Naming suggestion: noReadWrite() or dontReadWrite.

263

Default constructor makes unnecessary dependence on internals of ModRefInfo. In particular, it relays on NoModRef being 0. My suggestion is to explicitly use anyLoc(ModRefInfo::NoModRef) here (default constructor can be removed then since this looks to be the only use)

308

Do we really need this API? Looks like it is simply a wrapper and equivalent to getWithModRef(Loc, ModRefInfo::NoModRef) call, which I find more readable. WDYT?

352

I believe "(in-place)" should be removed since it returns new instance.

363

I believe "(in-place)" should be removed since it returns new instance.

This revision was landed with ongoing or failed builds.Sep 14 2022, 7:35 AM
This revision was automatically updated to reflect the committed changes.
nikic marked 6 inline comments as done.
nikic added inline comments.Sep 14 2022, 7:40 AM
llvm/include/llvm/Analysis/AliasAnalysis.h
263

Removing the default constructor was a bit tricky because we still do need to initialize Data at some point. What I ended up doing is to drop anyLoc() and instead have a proper FunctionModRefBehavior constructor that only takes a ModRefInfo that applies to all locations.

For now, I have made this constructor explicit, so you have to write FunctionModRefBehavior(MR) or similar to use it. An option (regarding your two comments above) would be to make it non-explicit, so that for example ModRefInfo::Ref could be implicitly converted to FunctionModRefBehavior(ModRefInfo::Ref). I think if I did this, then there would be no need for methods like FunctionModRefBehavior::readOnly(), which has the benefit that there is no need to pick a name for them... It would blur the line between MR and FMRB at bit though. What do you think?

308

I feel like this API does add value -- the typical usage would be as in D130980 to get FMRB without inaccessiblemem or argmem.

Would it be clearer if this wasn't a generic method, but rather something specific to those, like FMRB.getWithoutInaccessibleMem()?

352

Right, the "in-place" comments were on the wrong operators...

ebrevnov added inline comments.Sep 14 2022, 10:02 PM
llvm/include/llvm/Analysis/AliasAnalysis.h
263

I'm a bit more in favor for the "explicit" version. I think current version is just good enough. Thanks!

308

I feel like this API does add value -- the typical usage would be as in D130980 to get FMRB without inaccessiblemem or argmem.

I personally think this API just makes things harder to understand.
We should either find better name or just use existing API (getWithModRef)

Let's look at the description of getWithoutLoc:

/// Get new FunctionModRefBehavior with NoModRef on the given Loc

This is stated in terms of setting/resetting mod/ref bits for some Loc. I'm having troubles to match this intent with "getWithoutLoc" name. Possible names could be:

resetModRef() or setNoModRef(), etc.

Or just use existing API and pass NoModRef explicitly:

FMRB.setModRef(Loc, ModRefInfo::NoModRef);

Currently we have:
getWithoutLoc(FunctionModRefBehavior::InaccessibleMem);

Would it be clearer if this wasn't a generic method, but rather something specific to those, like FMRB.getWithoutInaccessibleMem()?

I don't think it worths it.