This is an archive of the discontinued LLVM Phabricator instance.

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.

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
278

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

303

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.
2133

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

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

284

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.

294

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

lib/Analysis/MemorySSA.cpp
237–251

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.)

296–310

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

298

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

895

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

2133

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

Got it! Removing this, keeping above comment.

lib/Analysis/MemorySSA.cpp
237–251

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.

278

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).

303

Ack, looking into how to best address this one.

895

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

2133

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
278

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

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

Then this looks like any other aliasing code.

277

IMHO, setDefiningAliasType(AliasResult)

281

Take an AliasResult AliasType = MayAlias)

lib/Analysis/MemorySSA.cpp
241

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

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?

277–282

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

294

ping :)

lib/Analysis/MemorySSA.cpp
265

Nit: parens are redundant

535

Nit: no else after a return

2103

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.)

2133

(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...)

unittests/Analysis/MemorySSA.cpp
1067

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
294

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

lib/Analysis/MemorySSA.cpp
2133

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
296

nit: newFunctionsShouldStartWithALowerCaseLetter :)

296

nit: static?

299

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

302

Same casing + static nits

303

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

305

Nit: if (

lib/Analysis/MemorySSA.cpp
2133

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
299

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
299

Ick, yeah, good call. WFM!

Thank you very much for the review!

This revision was automatically updated to reflect the committed changes.