Page MenuHomePhabricator

Expose must/may alias info in MemorySSA.
ClosedPublic

Authored by asbirlea on Oct 4 2017, 4:49 PM.

Details

Summary

Building MemorySSA gathers alias information for Defs/Uses.
Store and expose this information when optimizing uses (when building MemorySSA),
and when optimizing defs or updating uses (getClobberingMemoryAccess).
Current patch does not propagate alias information through MemoryPhis.

Diff Detail

Repository
rL LLVM

Event Timeline

asbirlea created this revision.Oct 4 2017, 4:49 PM
asbirlea edited reviewers, added: george.burgess.iv; removed: gbiv.Oct 4 2017, 4:53 PM
dberlin added inline comments.Oct 4 2017, 6:30 PM
lib/Analysis/MemorySSA.cpp
269 ↗(On Diff #117763)

It is possible for a call to must-alias a single thing, no?

297 ↗(On Diff #117763)

So this is going to double the number of alias calls, unfortunately. I suspect it will make building significantly slower, since roughly *all* time is spent there.

Do you have perf numbers to say one way or the other?

(unfortunately, ->alias is not const, so it will call it again)
I think we may need to finally implement some small LRU aliasing cache or something to make this fast enough.

Or

  1. Optionally pass the aliasing result into getModRefInfo, which would be a really weird API).
  2. Optionally return the aliasing result from getModRefInfo, which may make more sense.
2116 ↗(On Diff #117763)

I'm a little concerned about saying we must-alias the live on entry def.
It's abstractly true, but i wonder if stuff will get confusingly broken.

LiveOnEntry is really equivalent to "something before this function" not "one specific thing".

Thoughts?

Thanks for the patch!

include/llvm/Analysis/MemorySSA.h
264 ↗(On Diff #117763)

If we're going to call resetOptimized() outside of tests, we should probably remove this bit of the comment.

284 ↗(On Diff #117763)

Should be. In isOptimized(), we check to see if OptimizedID is the ID of the defining access. If we're setting the operand to something else, we should observe a different ID.

IIRC, this was necessary to make things like RAUW work without us having to manually deoptimize everything. If that's broken somehow, we shouldn't be papering over it here.

296 ↗(On Diff #117763)

Nit: Can we pack this in a PtrIntPair with MemoryInst?

lib/Analysis/MemorySSA.cpp
240 ↗(On Diff #117763)

I'd mildly prefer that we return a struct { bool IsClobber, IsMustAlias; }; or similar from this instead. That way, it's more clear what we want to hand back for FoundMustAlias in all cases.

(Moreover, there are quite a few paths in this function that don't try to set FoundMustAlias. It doesn't seem that's intentional.)

292 ↗(On Diff #117763)

Nit: no else after if (...) return ...;

303 ↗(On Diff #117763)

Same "please make this part of the return value" nit

881 ↗(On Diff #117763)

Do we need to set Q.FoundMustAlias here, as well?

2116 ↗(On Diff #117763)

I was thinking this could be solved by using "Clobber" in the name instead of "Alias", but I don't know if "Clobber" would imply something else that's subtly wrong.

That said, it may be a better idea to just have passes that don't care about MustAlias vs LiveOnEntry to roll their own helper:

bool isMustAlias(const MemoryAccess *MA) {
  return MA->definingIsMustAlias() || MA->getDefiningAccess() == MSSA->getLiveOnEntryDef();
}

...So we can have isMustAlias just mean isMustAlias :)

asbirlea updated this revision to Diff 117867.Oct 5 2017, 12:35 PM
asbirlea marked 5 inline comments as done.

Address most comments.

asbirlea marked an inline comment as done.Oct 5 2017, 12:37 PM

Updates - part1.

include/llvm/Analysis/MemorySSA.h
284 ↗(On Diff #117763)

Got it! Removing this, keeping above comment.

lib/Analysis/MemorySSA.cpp
240 ↗(On Diff #117763)

I did not mean to set it on all paths, since FoundMustAlias should not be modified for NoAlias. I missed the case when it needs to reset to May.

Updating to return pair, where isMustAlias should be ignored if !IsClobber.

269 ↗(On Diff #117763)

That's true. I didn't add that because I didn't see how we would use the must info here.

If we know the call does not modify and it's a must alias, then we could consider some transformation (read: promotion). In practice, we won't promote calls, so keeping FoundMustAlias = false (i.e. may) should be conservative.
The right thing is reseting to may for calls:
if(I != MRI_NoModRef) FoundMustAlias = false;
(instead of keeping the given value).

297 ↗(On Diff #117763)

Ack, looking into how to best address this one.

881 ↗(On Diff #117763)

Intended to keep the default (=false) for Phis.

2116 ↗(On Diff #117763)

Right now definingIsMayAlias and definingIsMustAlias are opposites. Since an optimized access skipped over NoAlias.
For optimized accesses May means "I found the defining location and it may alias this access."
For unoptimized accesses, the default is May.

I was planning to couple isOptimized() and definingIsMustAlias() to determine if a May alias was found.

Must with LOE is equivalent to "The defining access is not a MayAlias".
Perhaps I should only

  • keep the definingIsMayAlias() accessor
  • setDefiningToMayAlias(bool Arg) setter //Arg=false means Must or LOE

Thoughts?

asbirlea marked 4 inline comments as done.Oct 5 2017, 12:39 PM
dberlin added inline comments.Oct 6 2017, 7:56 AM
lib/Analysis/MemorySSA.cpp
269 ↗(On Diff #117763)

I would do the right thing for calls, IMHO, if we can.
(especially since we have to solve the double alias() call issue for other things anyway).

While LICM may not promote them, PRE definitely does (and GCC tests that it does).

This is true even through function pointers.
Here's the non-aliasing version to give you an idea (the aliasing version is longer)

double f(double a)
 {
   double b;
   double c,d;
   double (*fp) (double) __attribute__ ((const));

 double (*fp) (double) __attribute__ ((const));
   /* Partially redundant call */
   if (a < 2.0)
     {
       fp = sin;
       c = fp (a);
     }
   else
     {
       c = 1.0;
       fp = cos;
     }
   d = fp (a);
   return d + c;
 }

the fp call will get pushed into the else branch.
In the equivalent loop, we could promote it (PRE could promote it too if you let it speculate)
If we determine it is a must-alias of a single thing, we could do the same.
If we determine it's a must-alias of a set of things, we could do the same
If we determine it's a must-alias of the live on entry def, etc

dberlin edited edge metadata.Oct 9 2017, 7:04 PM

I'd reuse the type we already have to express alias results.
While you don't care about partial alias, it makes all code have the same meaning for the same thing :)

include/llvm/Analysis/MemorySSA.h
258 ↗(On Diff #117867)

Why not just have definingAliasType() and use the AliasResult type here?

Then this looks like any other aliasing code.

277 ↗(On Diff #117867)

IMHO, setDefiningAliasType(AliasResult)

281 ↗(On Diff #117867)

Take an AliasResult AliasType = MayAlias)

lib/Analysis/MemorySSA.cpp
241 ↗(On Diff #117867)

Just use AliasResult for the second part here.

(I'd suggest using ModRefType for the first but i believe nothing wants it right now)

asbirlea updated this revision to Diff 121963.Nov 7 2017, 12:54 PM

Use AliasResult to store alias information with the defining type.
Use MRI_Must bit to avoid double queries to AA.

Gentle ping. Also blocked on dependent patch.

nlopes added a subscriber: nlopes.Nov 22 2017, 9:43 AM

The concept looks interesting to me. I'll let the experts review the patch, though (I just skimmed over it).
Out of curiosity, what are the clients you envision could use this functionality?
I can imagine that we can do store forwarding with a mustalias MemUse if stored size >= load size. Also, a mustalias MemDef can kill the previous MemDef if it has no other uses (2 stores to same location).
Are there any other uses cases? Can it be used to simplify more complex optimizations? Even better, are there missing blocks that would be needed to simplify these optimizations? (tricky question; just wondering if you have some thoughts on that).

Please excuse my academic curiosity :)

An immediate usecase I have in LICM, is in very large testcases where I want to rely on MemorySSA's threshhold for optimizing MemUses.
I need to use getDefiningAccess() on a Use and query if the result given is May_Alias or Must_Alias. If the Use is not optimized, the result will always be MayAlias. If optimized, it may be May or Must.
Alias info is needed to avoid an additional AA.alias call when creating mssa alias sets for promotion.

It can certainly be used for more complex optimizations, aliasing between MemDefs is the most interesting to me. Since in MemorySSA all stores clobber all stores (until optimized), must alias info could be used to shortcut def alias chains. AFAIK this is done for MemUses, I don't think it's done for MemDefs.

An immediate usecase I have in LICM, is in very large testcases where I want to rely on MemorySSA's threshhold for optimizing MemUses.
I need to use getDefiningAccess() on a Use and query if the result given is May_Alias or Must_Alias. If the Use is not optimized, the result will always be MayAlias. If optimized, it may be May or Must.
Alias info is needed to avoid an additional AA.alias call when creating mssa alias sets for promotion.

It can certainly be used for more complex optimizations, aliasing between MemDefs is the most interesting to me. Since in MemorySSA all stores clobber all stores (until optimized), must alias info could be used to shortcut def alias chains. AFAIK this is done for MemUses, I don't think it's done for MemDefs.

Cool, makes sense. Thank you!
Nuno

asbirlea updated this revision to Diff 128070.Dec 22 2017, 11:29 PM
asbirlea marked 9 inline comments as done.

Rebase after ModRefInfo and MemorySSA changes.

asbirlea updated this revision to Diff 130460.Jan 18 2018, 11:15 AM

API change and review ping.

asbirlea updated this revision to Diff 130491.Jan 18 2018, 1:53 PM

clang-format

Overall approach looks good to me. Just a few naming/refactoring nits and I'm happy to stamp this. Sorry for taking so long to get back to it

include/llvm/Analysis/MemorySSA.h
258 ↗(On Diff #130491)

Is this the type of the defining access, or of the optimized access? (They're identical for Uses, but not for Defs) I assume it's the latter, but if not, the rest of this comment is just noise. :)

In a perfect world, I think the right thing here would be to hide this and have the walker return it as part of getClobberingMemoryAccess(). I also realize that we have workarounds in place because MSSA's walker takes ~forever in some cases, so this 'ideal' API probably won't work so well yet. :(

So, as a compromise, might it be good to rename this getOptimizedAccessType(), with a comment that it might disappear and become part of the walker's return value instead?

275 ↗(On Diff #130491)

Continuing with my assumption that AliasWithDefining is talking about the optimized access, can we rename to setOptimizedAccessType?

296 ↗(On Diff #117763)

ping :)

lib/Analysis/MemorySSA.cpp
2116 ↗(On Diff #117763)

(So... I had "That WFM. If we decide to go that way, please also add a comment explaining what it means if definingIsMayAlias returns false." that I never submitted. Is this thread still relevant? I don't see definingIsMayAlias anywhere but here...)

255 ↗(On Diff #130491)

Nit: parens are redundant

509 ↗(On Diff #130491)

Nit: no else after a return

2074 ↗(On Diff #130491)

Nit: reflow this comment to 80-cols, please. (In vim, gq will do what you want. Otherwise, joining the lines + running clang-tidy should split it up properly.)

unittests/Analysis/MemorySSA.cpp
1067 ↗(On Diff #130491)

Nit: it looks like (?) we're iterating over the same list in the same order in the other two loops. Can we pop it in a local array or initializer_list or something, then use that as the container for these loops?

asbirlea updated this revision to Diff 137327.Mar 6 2018, 10:53 PM
asbirlea marked 12 inline comments as done.

Address comments.

asbirlea added inline comments.Mar 6 2018, 10:55 PM
include/llvm/Analysis/MemorySSA.h
296 ↗(On Diff #117763)

Done, using 3 bits, 2 for AliasResult and 1 for None.

lib/Analysis/MemorySSA.cpp
2116 ↗(On Diff #117763)

I used dberlin's advice to "use the AliasResult type", so the only accessor now is definingAccessType() renamed to getOptimizedAccessType(). This returns an AliasResult. The setter also gets an AliasResult.
Per offline discussion, updated to use an Optional<AliasResult>, where None is used when the optimized access is LiveOnEntry.

A bundle of nitpicks for you. LGTM assuming those get addressed.

Thanks for working on this!

include/llvm/Analysis/MemorySSA.h
310 ↗(On Diff #137327)

nit: newFunctionsShouldStartWithALowerCaseLetter :)

310 ↗(On Diff #137327)

nit: static?

313 ↗(On Diff #137327)

Nit: (int)OAR.getValueOr(4);? Or does that require awkward casting? If it does need additional casting, I'm happy with this as-is.

316 ↗(On Diff #137327)

Same casing + static nits

317 ↗(On Diff #137327)

Should this accept 6 and 7? I thought the values were {May,Must,Partial,No}Alias (for 0-3) and None (for 4)

319 ↗(On Diff #137327)

Nit: if (

lib/Analysis/MemorySSA.cpp
2116 ↗(On Diff #117763)

SGTM.

This revision is now accepted and ready to land.Mar 7 2018, 10:40 AM
asbirlea updated this revision to Diff 137483.Mar 7 2018, 2:25 PM
asbirlea marked 9 inline comments as done.

Address comments.

include/llvm/Analysis/MemorySSA.h
313 ↗(On Diff #137327)

The value given as OR is expected to be of the same type inside the Optional, in this case AliasResult. I think it's not a casting issue, but a correctness one; casting the 4 to AliasResult is UB.
Leaving as is, but please correct me if I'm wrong.

include/llvm/Analysis/MemorySSA.h
313 ↗(On Diff #137327)

Ick, yeah, good call. WFM!

Thank you very much for the review!

This revision was automatically updated to reflect the committed changes.