This is an archive of the discontinued LLVM Phabricator instance.

[AliasSetTracker] Correctly handle changing size of an entry
ClosedPublic

Authored by mkuper on Apr 9 2016, 5:37 PM.

Details

Summary

If the size of an AST entry changes, we also need to make sure we perform necessary alias set merges, as the new size may overlap pointers in other sets.
We happen to run into this with memset, because memset allows an entry for a i8* pointer to have a decidedly non-i8 size.

There's some ugliness here because even if getEntryFor(Pointer).hasAliasSet() is true, findAliasSetForPointer(Pointer, ...) will not necessarily find an alias set - as a pointer may not alias anything, including itself (e.g. undef). I'm not sure whether that is a bug or a feature...

This fixes PR27262.

Diff Detail

Repository
rL LLVM

Event Timeline

mkuper updated this revision to Diff 53163.Apr 9 2016, 5:37 PM
mkuper retitled this revision from to [AliasSetTracker] Correctly handle changing size of an entry.
mkuper updated this object.
mkuper added reviewers: spatel, hfinkel.
mkuper added a subscriber: llvm-commits.
hfinkel added inline comments.Apr 11 2016, 3:04 PM
lib/Analysis/AliasSetTracker.cpp
278 ↗(On Diff #53163)

Saying "Use findAliasSetForPointer for its merging side effect." implies that findAliasSetForPointer does other things too. If it did, it would be reasonable to split the behavior. However, merging together all alias sets aliasing the provided pointer is exactly what findAliasSetForPointer does. I think this is worth saying. Instead of:

// Use findAliasSetForPointer for its merging side effect.

how about:

// Merging together all alias sets which alias a particular pointer is exactly what findAliasSetForPointer does.
282 ↗(On Diff #53163)

What is the right alias set for undef?

mkuper added inline comments.Apr 11 2016, 3:38 PM
lib/Analysis/AliasSetTracker.cpp
278 ↗(On Diff #53163)

I agree it doesn't make sense to split the behavior out, since it's basically all it does - hence the comment, otherwise I would have just split it out. :-)
The problem is that findAliasSetForPointer is not really a good name for what it does. But I don't have any better ideas, "mergeAliasSetsForPointer" that returns the resulting alias set doesn't look much better.

Anyway, this is bike-shedding, if you prefer just changing the comment, I'm ok with that.
Let me know what you think.

282 ↗(On Diff #53163)

An alias set that contains only undef - it can never be merged with anything else, since undef aliases nothing.

I guess this makes sense - getAliasSetForPointer() needs to return *something*, and returning a set that contains only undef means we'll get an alias set that aliases nothing else, as expected. I guess this isn't as precise as we'd idally like, because it means we merge "different" undefs, which should not alias each-other.

BTW, this isn't necessarily a problem only for undef. The issue is that alias(X,X) apparently doesn't have to hold, in general.

hfinkel added inline comments.Apr 13 2016, 5:15 PM
lib/Analysis/AliasSetTracker.cpp
278 ↗(On Diff #53163)

Indeed :-) -- I also could not think of a better name. Thus I suggested just changing the comment.

FWIW, I do like "mergeAliasSetsForPointer" better than "findAliasSetForPointer".

282 ↗(On Diff #53163)

An alias set that contains only undef - it can never be merged with anything else, since undef aliases nothing.

I guess this makes sense - getAliasSetForPointer() needs to return *something*, and returning a set that contains only undef means we'll get an alias set that aliases nothing else, as expected. I guess this isn't as precise as we'd idally like, because it means we merge "different" undefs, which should not alias each-other.

Wouldn't it make the most sense for each undef to get its own set? I don't see why we should merge them since different undefs don't mutually alias.

BTW, this isn't necessarily a problem only for undef. The issue is that alias(X,X) apparently doesn't have to hold, in general.

Really? That seems wrong.

mkuper added inline comments.Apr 13 2016, 6:46 PM
lib/Analysis/AliasSetTracker.cpp
278 ↗(On Diff #53163)

Then I'd prefer to change the name, and be done with this. :-)

282 ↗(On Diff #53163)

Wouldn't it make the most sense for each undef to get its own set? I don't see why we should merge them since different undefs don't mutually alias.

AFAIK, we can't actually distinguish between "different" undefs, since there is only one UndefValue of each type. So I don't think there's a way to do that.

Really? That seems wrong.

Yes, it seemed wrong to me too. I talked to Mehdi on IRC about it, and he convinced me that it's reasonable.

In any case, this definitely happens for undefs right now (at least since r236511), and I don't see any guarantee that this can't happen for other values. Another case where basic-aa will return NoAlias is if the size is 0.
Also, if I understand correctly, basic-aa is supposed to give MayAlias (instead of MustAlias) for alias(X,X) if X is loop-iteration dependent, but this doesn't seem enforced, and I'm pretty sure we may get a NoAlias in these cases as well.

hfinkel accepted this revision.Apr 13 2016, 7:49 PM
hfinkel edited edge metadata.
hfinkel added inline comments.
lib/Analysis/AliasSetTracker.cpp
278 ↗(On Diff #53163)

Good, please go ahead.

282 ↗(On Diff #53163)

AFAIK, we can't actually distinguish between "different" undefs, since there is only one UndefValue of each type. So I don't think there's a way to do that.

That's correct. But that does not mean that you can't get back a different alias set whenever you put in an undef pointer.

Another case where basic-aa will return NoAlias is if the size is 0.

That seems okay.

Also, if I understand correctly, basic-aa is supposed to give MayAlias (instead of MustAlias) for alias(X,X) if X is loop-iteration dependent, but this doesn't seem enforced, and I'm pretty sure we may get a NoAlias in these cases as well.

That does not sound right either; I don't see why being loop dependent matters. For the aliasing query to be well defined, it must refer to values within the same loop iteration.

In any case, this LGTM. Please, however, file a bug report on this alias(X, X) uncertainty. We should get some documented resolution on this matter.

This revision is now accepted and ready to land.Apr 13 2016, 7:49 PM

Thanks, Hal, will do.

This revision was automatically updated to reflect the committed changes.