Page MenuHomePhabricator

Track whether the size of a MemoryLocation is precise
ClosedPublic

Authored by george.burgess.iv on Mar 21 2018, 11:42 AM.

Details

Summary

In the vast majority of cases, we hand AA precise sizes for MemoryLocations, rather than upper-bounds. BasicAA has a few checks that assume the sizes passed in are precise, which breaks down when we start passing in upper-bounds that might include conditionally-executed UB (which is what AliasSetTracker is doing right now, and which caused PR36228). The most straightforward way to fix this without penalizing AA seems to be passing an extra "I guarantee you this size is precise" bit along.

Passing this bit in a minimally invasive way appears difficult in pathological cases (read: massive sizes), and we're already sort of treating this Size as an Optional<uint64_t>, so I figured I'd wrap this up in its own type to make the properties of MemoryLocation sizes more obvious/hopefully easier to deal with.

As a natural part of this refactoring, PR36228 gets fixed.

If this lands, I will do the following cleanups (...which there's a lot of, but the majority are trivial):

  • Replace all uses of MemoryLocation::UnknownSize with LocationSize::unknown() + remove MemoryLocation::UnknownSize
  • Replace the various resulting Loc == LocationSize::unknown()s with the shorter, equivalent !Loc.hasValue()
  • Migrate users of the implicit LocationSize(uint64_t) ctor to LocationSize::precise or LocationSize::upperBound
  • Remove the LocationSize(uint64_t) ctor, which will force callers of AA APIs to reason about/be explicit about the precision of the LocationSize they're passing.

The last two bullets are the bits that I hope will prevent future bugs like this (and catch other existing ones, if any). :)

Any thoughts/comments welcome, as always.

Diff Detail

Repository
rL LLVM

Event Timeline

There are a very large number of changes, so older changes are hidden. Show Older Changes

I like the direction in general. I've reviewed this patch and it LGTM (as well as the overall plan).
There are still a few corner cases we need to fix regarding the meaning of size -1, but I guess it's an orthogonal fix. Right now I don't know exactly what -1 size is: does it mean potentially access the whole object, or access the object from the current offset and potentially until the end?

include/llvm/Analysis/AliasSetTracker.h
74 ↗(On Diff #139337)

This is changing the semantics slightly. Before it would update Size if Newsize=-1. Is this intended?

78 ↗(On Diff #139337)

Access size can be zero. Is it safe to do the above? You could use the map tombstone instead perhaps?

george.burgess.iv marked an inline comment as done.

Addressed comments + tweaked mapTombstone and mapEntry so they call the hacky "direct" constructor.

george.burgess.iv marked an inline comment as done.Mar 28 2018, 3:13 PM

Thanks for the comments!

include/llvm/Analysis/AliasSetTracker.h
74 ↗(On Diff #139337)

I don't see how it's a functionality change. If !Size.hasValue(), that's the equivalent to Size == UINT64_MAX in the old code, which would result in updates never happening. If NewSize != Size, we'll conditionally update to the greater size (with the upper-bound bit definitely set). Am I missing something?

In any case, I removed the hasValue() check here, since we should handle !hasValue() correctly in Size.combineWith(NewSize).

78 ↗(On Diff #139337)

Good catch. I used the empty key since that's what we appear to use for AAInfo

LGTM, but I would wait for another review due to the size of the change.

lib/Analysis/BasicAliasAnalysis.cpp
1716 ↗(On Diff #140142)

isPrecise() should be enough since UnknownSize() isn't precise. This pattern appears a couple more times.

george.burgess.iv marked 2 inline comments as done.

Addressed feedback

I would wait for another review

Will do. Thanks again!

lib/Analysis/BasicAliasAnalysis.cpp
1716 ↗(On Diff #140142)

Good catch.

I am concerned that you doing too many things in one patch and that the mix of refactoring and functional changes may contain hard to spot bugs. In particular, the absence of hasValue checks in various updated logic worries me.

I strongly request that you separate a patch which simply factors out a LocationSize type with the exact same semantics as the existing code. Once landed, you can introduce the new precise concept on top of that.

include/llvm/Analysis/MemoryLocation.h
35 ↗(On Diff #140655)

I think you mean: must be exactly N bytes. If not, I'm confused.

108 ↗(On Diff #140655)

If the two are precise and equal, this downgrades to imprecise.

lib/Analysis/AliasSetTracker.cpp
631 ↗(On Diff #140655)

looks like we probably need a print(OS) method on LocationSize.

lib/Analysis/BasicAliasAnalysis.cpp
1054 ↗(On Diff #140655)

Don't you need to check that we have a value here?

1122 ↗(On Diff #140655)

Same here.

george.burgess.iv marked an inline comment as done.

I am concerned that you doing too many things in one patch and that the mix of refactoring and functional changes may contain hard to spot bugs.

Right. I tried to reduce that as much as possible here, but it's still pretty large. :/

In particular, the absence of hasValue checks in various updated logic worries me.

Yeah, this is a casualty of the reducing mentioned above. x.hasValue() and x != MemoryLocation::Unknown are identical at the moment. While there wasn't anything too crazy WRT finding these checks (e.g. I didn't find any "well, the callers of X all verify this, ...", they can be pretty nonlocal even in a function.

I strongly request that you separate a patch which simply factors out a LocationSize type with the exact same semantics as the existing code. Once landed, you can introduce the new precise concept on top of that.

Works for me! Part one is D45581. Once we're happy with that, I'll rebase this patch on top of it. :)

include/llvm/Analysis/MemoryLocation.h
35 ↗(On Diff #140655)

Yeah, I could've worded this better. I was trying to say "block of bytes that the MemoryLocation references" (e.g. a store i32 1, i32* %a implies that %a must be *at least* 4 bytes large). Will update with the rebase.

108 ↗(On Diff #140655)

Shouldn't the Other == *this check handle that case?

lib/Analysis/AliasSetTracker.cpp
631 ↗(On Diff #140655)

Added in the new patch; good call. :)

lib/Analysis/BasicAliasAnalysis.cpp
1054 ↗(On Diff #140655)

There's a check near the top of the function (line 1002) for V1Size == MemoryLocation::UnknownSize || V2Size == MemoryLocation::UnknownSize. It's annoying that it's so far away, though. :/

Happy to unwrap V1Size and V2Size into unsigneds directly after the check if you think that'd be clearer.

1122 ↗(On Diff #140655)

(Same function, so the above reply applies here)

george.burgess.iv marked an inline comment as done.

Rebase now that our LocationSize changes are in

lib/Analysis/BasicAliasAnalysis.cpp
1054 ↗(On Diff #140655)

Happy to unwrap V1Size and V2Size into unsigneds directly after the check if you think that'd be clearer.

(I've done this across BasicAA in hopes of making things a bit clearer. Please let me know if you disagree)

1188 ↗(On Diff #140655)

Not a BasicAA expert, but since I see "negative offset" and an int64_t cast here, I wanted to highlight that this LocationSize change eats the sign bit of ObjectAccessSize. I assume that ObjectAccessSize should always be positive and the int64_t cast exists just to keep the >= comparison signed, but...

nlopes added inline comments.Jun 12 2018, 1:29 AM
lib/Analysis/MemoryDependenceAnalysis.cpp
1115 ↗(On Diff #149050)

Why is it ok to ignore precision here?
If we did an alias query before with precise size, and the new one is with upper-bound, the results don't seem reusable.
(I have no clue how this function works; so I don't know if the above case can happen)

george.burgess.iv marked an inline comment as done.

Rebase + address feedback

lib/Analysis/MemoryDependenceAnalysis.cpp
1115 ↗(On Diff #149050)

I was trying to keep this as close to NFC as possible, but yeah, good point.

I tried bootstrapping clang with assertions about the size either being unknown or precise, and no assertions fired, so it doesn't appear that known-but-imprecise values can reach here (or if they do, they do so very rarely).

Switched to always throwing out the cached data if the precision differs (we can do better if we know the value is now precise, too). Happy to swap to what you suggested if you feel that's better, though. Like you, I'm not super familiar with memdep...

reames requested changes to this revision.Aug 6 2018, 3:34 PM

This change is *still* too large to comfortably review in one pass. I *strongly encourage* you to take a look through this and take every opportunity to split off small NFC refactorings to reduce the diff length and complexity. I've highlighted a couple options for you, but there are likely others.

lib/Analysis/MemoryDependenceAnalysis.cpp
1115 ↗(On Diff #153386)

This does not look NFC.

lib/Transforms/Scalar/DeadStoreElimination.cpp
352 ↗(On Diff #153386)

If I'm reading this write, you can extract the majority of the mechanical updates to this function by adding the two variables to the old style code. Please do so shrink the diff. Also, make const.

This revision now requires changes to proceed.Aug 6 2018, 3:34 PM
george.burgess.iv marked an inline comment as done.

Shrunk the diff as requested; the few pre-commit patches required to make this build are available as one patch in https://reviews.llvm.org/D52245 .

include/llvm/Analysis/AliasSetTracker.h
100 ↗(On Diff #166019)

(This is a functional change if we try to call getSize() before setting a size. In my tests a few months ago, this was never done in practice, and it frankly makes no sense to me to try to get an unset size. :)

I'll bootstrap clang once more to verify that this assert isn't tripped before committing)

lib/Analysis/MemoryDependenceAnalysis.cpp
1115 ↗(On Diff #153386)

You're correct; it adds a case where if the preciseness of CacheInfo->Size isn't the same as Loc.Size's, we'll throw everything out.

As noted in the comment, I can't get an imprecise value to land here in practice. If you'd rather I put an assertion about that here instead of CacheInfo->Size.isPrecise() != Loc.Size.isPrecise(), I'm happy to do so, but the rest of this should turn into the equivalent of what was CacheInfo->Size < Loc.Size.

reames requested changes to this revision.Sep 19 2018, 3:58 PM

Mostly minor comments. I considered giving a conditional LGTM, but decided it warranted one last round. I think this is very close to landing.

include/llvm/Analysis/MemoryLocation.h
112 ↗(On Diff #166019)

Can we pick a different name? Maybe: union?

This is returning a result which is conservatively correct for uses of either. combineWith doesn't make that obvious.

35 ↗(On Diff #140655)

Looks like this update got lost?

JFYI, I consider clarity on this point essential.

lib/Analysis/BasicAliasAnalysis.cpp
1718 ↗(On Diff #166019)

This is definitely a warranted functional change, but please add a test case which reflects the change.

1779 ↗(On Diff #166019)

Same testing comment here.

lib/Analysis/MemoryDependenceAnalysis.cpp
1140 ↗(On Diff #166019)

This looks to have very different behaviour than previously. Unless I'm misreading nesting, you’re recomputing any time the sizes are equal which is odd.

This revision now requires changes to proceed.Sep 19 2018, 3:58 PM
george.burgess.iv marked 3 inline comments as done.

Address feedback

include/llvm/Analysis/MemoryLocation.h
35 ↗(On Diff #140655)

Good catch; sorry for dropping this. Please let me know if you'd like me to expand further.

lib/Analysis/BasicAliasAnalysis.cpp
1718 ↗(On Diff #166019)

Added tests for both of these. It's not obvious to me how to get an imprecise size when directly testing BasicAA, so I opted for unittests. I'll do the newly-added // FIXME: This is duplicated between this file and MemorySSATest. Refactor. in a follow-up commit, in the interest of keeping this diff small.

lib/Analysis/MemoryDependenceAnalysis.cpp
1140 ↗(On Diff #166019)

Yeah, this is one level of nesting deeper than it was previously (it's odd to me that phab doesn't point this out). In particular, the CacheInfo->Size != Loc.Size check guards this

reames requested changes to this revision.Oct 2 2018, 6:36 AM
reames added inline comments.
include/llvm/Analysis/MemoryLocation.h
35 ↗(On Diff #140655)

Reading through this again, I think we have a semantic problem here. The previous semantics of MemoryLocation was that we had a memory region which was guaranteed to be at least as large as the memory actually dereferenced. Your documented new semantics now indicate that the accessed region is *larger* than the MemLoc when that MemLoc is precise. This now means that to know whether a MemLoc is inclusive of the access we *must* check the precise bit.

I am not okay with that change.

I would be okay with either of the following:

  1. Precise means "accesses exactly N bytes". (i.e. still bounded from above, but now also bounded from below with the same value)
  2. We replace "precise" with a MinSize field. A memory location would then guarantee that the actual access was bounded from below by MinSize and above by Size.

I recommend (1) for the moment since I think that's what you've actually implemented. (2) would be more generic, but would be basically starting over.

This revision now requires changes to proceed.Oct 2 2018, 6:36 AM
george.burgess.iv added inline comments.
include/llvm/Analysis/MemoryLocation.h
35 ↗(On Diff #140655)

Option one is what I was going for initially, but I see I tripped over myself a bit (mostly, the last sentence was meant to apply only to imprecise memory locations, though I made that wholly unclear :) ). Reworded.

As for #2, yeah, we can do that if there's a great need for it, but I'm happy to start with something simpler.

reames accepted this revision.Oct 4 2018, 2:05 AM

LGTM w/one optional, but strongly recommended change.

include/llvm/Analysis/MemoryLocation.h
88 ↗(On Diff #168132)

This implicit switch of all callers makes me nervous. I'm willing to trust that you've audited all the callers, but my advice (which I would follow if doing this myself) would be to submit this patch with the constructor defaulting to imprecise locations. Then, in a separate patch, flip the default. Specifically, the motivation is so that if you've missed something in your audit, most of the infrastructure can stay in tree and not need to be reverted while you debug.

This revision is now accepted and ready to land.Oct 4 2018, 2:05 AM

Woo! Thank you very much for the review (and for bearing with me in your repeated requests to minimize this patch :) ).

Since there's quite a few pieces to this, I'll probably just land it all slowly over a few days, pending our last discussion here being settled.

include/llvm/Analysis/MemoryLocation.h
88 ↗(On Diff #168132)

I'm not sure I understand. All MemoryLocations are implicitly precise today, so the most functionality-preserving thing we can do here is to treat all of them as precise by default.

Treating them all as imprecise would certainly fix any existing, yet-to-be-reported bugs where we're passing 'imprecise' MemoryLocations around. The hope is to find those places as a part of the migration to explicitly use ::precise/::upperBound, though.

Does that make sense? Or am I missing something?

reames added inline comments.Oct 7 2018, 8:19 PM
include/llvm/Analysis/MemoryLocation.h
88 ↗(On Diff #168132)

I think the problem is that we sometimes assume MemLocs are precise, and sometimes assume they're conservative. :)

I'm fine with you landing with either default. I defer to your judgement.

This revision was automatically updated to reflect the committed changes.