Page MenuHomePhabricator

Add must alias info to ModRefInfo.
ClosedPublic

Authored by asbirlea on Oct 12 2017, 3:39 PM.

Details

Summary

Add an additional bit to ModRefInfo, MRI_Must, to be set for known must aliases.
Conservatively this bit will not be set (equivalent to MayAlias or NoAlias).

Notes:

  • MRI_Must is almost entirely set in the AAResults methods, the remaining changes are trying to preserve it.
  • Only some small changes to make custom AA passes set MRI_Must (BasicAA).
  • GlobalsModRef already declares a bit of the same value as MRI_Must (MayReadAnyGlobal). No changes to shift the value of MayReadAnyGlobal (see AlignedMap). FunctionInfo.getModRef() masks out everything except MRI_ModRef, so correctness is preserved, but the MRI_Must info is not set/used.
  • There are cases where the MRI_Must is not set, e.g. 2 calls that only read will return MRI_NoModRef, though they may read from exactly the same location.

Diff Detail

Repository
rL LLVM

Event Timeline

There are a very large number of changes, so older changes are hidden. Show Older Changes
asbirlea added inline comments.Nov 22 2017, 10:54 AM
lib/Analysis/AliasAnalysis.cpp
327 ↗(On Diff #121957)

Right now getArgModRefInfo never sets MRI_Must.
I tried to document this in ModRef enum and before getArgModRefInfo method declaration. Do you think I should also add an assert here (and above) ?

lib/Analysis/GlobalsModRef.cpp
87 ↗(On Diff #118852)

I'm confused. If MayReadAnyGlobal = 2, it will trigger the static assert below for overlapping with MRI_ModRef.

nlopes added a subscriber: nlopes.Nov 23 2017, 2:56 AM
nlopes added inline comments.
lib/Analysis/AliasAnalysis.cpp
506 ↗(On Diff #123985)

AtomicCmpXchgInst must read, but may not write (depending on the value read).
I think the only safe value here is MRI_ModRef, since the current lattice doesn't have a more precise value for MustRead & MayReadWithMustAlias.

nlopes added inline comments.Nov 23 2017, 2:58 AM
lib/Analysis/AliasAnalysis.cpp
506 ↗(On Diff #123985)

gah, I meant MustRef & MayModWithMustAlias.

(We've discussed the meat of this patch offline, but I had some stray comments from earlier)

lib/Analysis/AliasAnalysis.cpp
327 ↗(On Diff #121957)

If your code will be incorrect when someone changes getArgModRefInfo to return results with MRI_Must set then you should definitely assert this.

562 ↗(On Diff #121957)

Here's a reason for why I think a bool is better here -- right now looking at just the return statement in isolation, ModRefInfo(R | M), it isn't obvious that we're at most adding the MRI_Must bit to R (since M could be MRI_Mod, for instance). But if we have ModRefInfo(R | (MustAlias ? MRI_Must : MRI_NoModeRef)) then just by looking at the expression and nothing else we know that we're at most setting the MRI_Must bit.

asbirlea updated this revision to Diff 125646.Dec 5 2017, 4:17 PM

Rebase and address comments.

asbirlea marked 10 inline comments as done.Dec 5 2017, 4:28 PM

Updated, PTAL.

lib/Analysis/AliasAnalysis.cpp
327 ↗(On Diff #121957)

Should not be an issue anymore. If getArgModRefInfo returns results with MRI_Must, result should still be correct.

562 ↗(On Diff #121957)

Ack, updated.

506 ↗(On Diff #123985)

I updated the comments above for the MRI_Must* bits. MustRef & MayModWithMustAlias should have Must bit set.

asbirlea updated this revision to Diff 125652.Dec 5 2017, 4:31 PM
asbirlea marked 3 inline comments as done.

Nit: periods.

sanjoy requested changes to this revision.Dec 5 2017, 9:18 PM

Some minor nits inline, but I thought we were going with making bitwise MRI_Must be 0 (and MRI_NoModRef be 4) so that & works as expected?

include/llvm/Analysis/AliasAnalysis.h
111 ↗(On Diff #125652)

(Minor) I'd remove "conservative" -- it is understood that these things are conservatively correct.

115 ↗(On Diff #125652)

This is for calls that are known to be argmemonly, right?

122 ↗(On Diff #125652)

I think this comment can be improved.

  • Instead of starting with details on how we infer MRI_Must let's first describe what it means, followed by this note.
  • I don't think we need a laundry list of examples here. I think it is better to just mention that we don't always return the most precise possible and add a "c.f. getArgModRefInfo, callCapturesBefore etc.".
127 ↗(On Diff #125652)

"default" is a bit confusing here. How about just leaving out the second part, and commenting "MRI_Must is provided for completeness, but no routines will return only MRI_Must today".

654 ↗(On Diff #125652)

The comma is unnecessary.

lib/Analysis/AliasAnalysisEvaluator.cpp
261 ↗(On Diff #125652)

Unnecessary move? (Not a big deal, but avoid this will make the diff slightly smaller)

This revision now requires changes to proceed.Dec 5 2017, 9:18 PM
asbirlea updated this revision to Diff 126437.Dec 11 2017, 1:34 PM
asbirlea edited edge metadata.
asbirlea marked 4 inline comments as done.

Address comments and rebase on ToT.

sanjoy requested changes to this revision.Dec 11 2017, 10:56 PM

Unless you have a specific reason not to, I think we should merge https://reviews.llvm.org/D41091 into this one -- that'll make the patch easier to review (usually these kinds of things go the other way -- splitting the patch makes it easier to review :) ).

Meanwhile, I have some minor comments inline.

include/llvm/Analysis/AliasAnalysis.h
122 ↗(On Diff #126437)

Nit s/MRI_Must/ModRefInfo::Must/ here and elsewhere

lib/Analysis/BasicAliasAnalysis.cpp
824 ↗(On Diff #126437)

Add a comment here on why tracking MustAlias this way is correct despite the early exit (IIUC this is because if Result = ModRefInfo::ModRef the we don't use MustAlias)?

lib/Analysis/GlobalsModRef.cpp
132 ↗(On Diff #126437)

This isn't clearing the must bit though, right? It is clearing the MayReadAnyGlobal bit?

Also the inline here is redundant -- member functions defined within their class are implicitly inline.

This revision now requires changes to proceed.Dec 11 2017, 10:56 PM
asbirlea updated this revision to Diff 126801.Dec 13 2017, 11:56 AM

Address comments and merge in D41091.

asbirlea updated this revision to Diff 126805.Dec 13 2017, 12:03 PM
asbirlea marked 2 inline comments as done.

Remove remaining MRI_ instances.

Issue (?): rephrase comments to clarify Must is cleared not set when MustAlias exists.
Possible reverse clearMust si setMust?

asbirlea updated this revision to Diff 126833.Dec 13 2017, 1:54 PM

Added comment to clarify what setting Must means.

Ready for review, PTAL.

sanjoy requested changes to this revision.Dec 14 2017, 12:56 AM

I think we can break this patch up further -- how about this breakdown:

  1. Remove the changes related to calls from this patch and do something conservative there. That'll reduce the complexity of this patch a bit. I also have a comment about our treatment of calls inline, which we can discuss on the subsequent patch that proper support for calls. (Let me know if splitting this up will be annoying, and we can think of some other strategy.)
  2. Make the refactoring I suggested inline in GlobalsModRef.cpp and rebase on top of it.

With both (1) and (2) done, this patch should be ready to go in modulo minor nits.

include/llvm/Analysis/AliasAnalysis.h
114 ↗(On Diff #126833)

How about moving this meta-comment and the definition of Must to the end of the enum?

lib/Analysis/AliasAnalysis.cpp
196 ↗(On Diff #126833)

I'm not sure about this treatment of calls. For a query between instructions like stores and loads that only touch one location the meaning of Must is pretty clear -- MustRef (say) means the store does not write to any location other than the location the load reads from. However, generalizing this to calls seems to mean that a MustRef between a call and a load would imply that the call does not write to any location other than what the load reads. This means we can't ignore NoAlias arguments -- a NoAlias (as opposed to Must) result should also set MayAlias to false.

535 ↗(On Diff #126833)

It may be better to instead add this as a comment on the return instruction, as "Not returning MustModRef since we've not seen all the arguments" etc.

566 ↗(On Diff #126833)

"incomplete" is a bit vague -- how about just leaving a comment on the return statement as "Not returning MustModRef since we've not seen all the arguments" or something like that?

lib/Analysis/GlobalsModRef.cpp
148 ↗(On Diff #126833)

I wouldn't break the abstraction here this way. Instead, I think it is better to have:

int ModRefInfoToInteger(ModRefInfo mri) {
  switch (clearMust(mri)) {
  case NoModRef:
    return 0;
  case Mod:
    return 1;
  case Ref:
    return 2;
  case ModRef:
    return 3;
  }
}

int IntegerToModRef(ModRefInfo mri) {
  // Inverse of the above
}

and use these to "encode" and "decode" an opaque ModRefInfo instance to a 2 bit integer and back.

(You may even want to do this as a separate NFC change and land it independently.)

This revision now requires changes to proceed.Dec 14 2017, 12:56 AM
asbirlea updated this revision to Diff 127043.Dec 14 2017, 4:10 PM
asbirlea marked 3 inline comments as done.

Address comments.

PTAL.

lib/Analysis/AliasAnalysis.cpp
196 ↗(On Diff #126833)

Having looked at this again, it appears safe to set Must in this case, but I'm also quite ok with separating this into a separate patch.
I added the path to set MayAlias here and below getMRI(CS, CS), and these can be removed in a subsequent patch.

lib/Analysis/GlobalsModRef.cpp
148 ↗(On Diff #126833)

I tried this and ended up with a more confusing code, and harder to maintain.
The general idea of encoding 2 bits and using that in GlobalsModRef is tempting for me, but in practice it looks like it complicates the code unnecessarily. I can be convinced otherwise, and this can be an add-on clean-up patch in that case.

sanjoy requested changes to this revision.Dec 18 2017, 1:33 PM

Mostly minor stuff. The main non-nit comment I have is that the various places we're handling calls don't seem consistent with each other.

lib/Analysis/AliasAnalysis.cpp
201 ↗(On Diff #127043)

How about:

bool MustAlias = true;
AliasResult ArgAlias = ...
MustAlias &= ArgAlias == MustAlias;

?

291 ↗(On Diff #127043)

Given that you're setting MustAliasFound even if !isMustSet(ModRefCS1) perhaps it should be called something else?

Secondly, how about structuring this as:

bool MustAlias = true;
MustAias &= isMustSet(ModRefCS1);

?

Finally, I don't think MustAliasFound is necessary anymore -- if there were no MustAlias results and there was at least one argument, then we'd have cleared out MustAlias, so no need to track MustAliasFound I think?

299 ↗(On Diff #127043)

Unrelated to your change, but this is the second time I've been confused by this phrase. The variable Result sounds like it is the value we're going to return. But it isn't -- it is just the ModRef information we've computed till before this algorithm on arguments.

What do you think about (in a separate change) splitting out this loop (and the one after) into a separate function, in which Result will be passed as an argument with a more mnemonic name? Of course, this is totally unrelated to your change, so I'll understand if you don't think it is a good use of your time. :)

303 ↗(On Diff #127043)

I think we can simplify this a bit -- just keep track of the number of arguments you've seen to be MustAlias, and check that it is equal to the number of actual function args. That way we're not using MayAlias to track "have seen a may-alias OR have early exited".

345 ↗(On Diff #127043)

The comments I made on the previous loop also apply here.

591 ↗(On Diff #127043)

Should you be clearing MustAlias even if AR == NoAlias like you're doing in the other cases?

lib/Analysis/BasicAliasAnalysis.cpp
810 ↗(On Diff #127043)

Same comment here w.r.t. setting MustAlias when AR == NoAlias.

864 ↗(On Diff #127043)

Going by our current definition ("Must means no other location is Ref'ed or Mod'ed") this can't return Must right?

This revision now requires changes to proceed.Dec 18 2017, 1:33 PM
asbirlea updated this revision to Diff 127914.Dec 21 2017, 10:44 AM
asbirlea marked 20 inline comments as done.

Address comments.

lib/Analysis/AliasAnalysis.cpp
291 ↗(On Diff #127043)

Also renamed bool MustAlias to bool IsMustAlias to avoid confusion with AliasResult MustAlias.

299 ↗(On Diff #127043)

Feedback noted. I may do this in a future patch :).

303 ↗(On Diff #127043)

I think that actually complicates the code. Either keeping track of the number of arguments seen so far, or of all must alias arguments, or setting a different variable on early exit, they add more baggage than using a bool to track "have seen a may-alias OR have early exited".
The comment should make this choice clear.

sanjoy accepted this revision.Dec 21 2017, 11:15 AM

lgtm!

include/llvm/Analysis/AliasAnalysisEvaluator.h
41 ↗(On Diff #127914)

Another cleanup that might be worth doing as a separate change -- change these fields to use the C++11 member initializer like int64_6 MustCount = 0;.

This revision is now accepted and ready to land.Dec 21 2017, 11:15 AM
This revision was automatically updated to reflect the committed changes.

A slightly late review comment:

llvm/trunk/lib/Analysis/AliasAnalysis.cpp
551

You need IsMustAlias (or AllOperandsMustAlias or what have you) here too; as is this shadows the MustAlias AliasResult, and AR != MustAlias below on line 568 now compares with this bool instead of with the enum value as intended. (Are we missing test coverage here?)

(found by msvc warning 4805 which I had enabled locally for a bit.)

asbirlea marked an inline comment as done.Apr 30 2018, 1:18 PM
asbirlea added inline comments.
llvm/trunk/lib/Analysis/AliasAnalysis.cpp
551

Should be fixed in r331222, thanks for the catch!
I'll look into expanding test coverage when starting to use the Must info.

asbirlea marked 2 inline comments as done.Apr 30 2018, 1:19 PM