This is an archive of the discontinued LLVM Phabricator instance.

[DependenceAnalysis] Memory dependence analysis internal caching mechanism is broken in presence of TBAA (PR42733).
ClosedPublic

Authored by ebrevnov on Jan 20 2020, 4:38 AM.

Details

Summary

There is a flaw in memory dependence analysis caching mechanism when memory accesses with TBAA are involved. Assume we first analysed and cached results for access with TBAA. Later we request dependence for the same memory but without TBAA (or different TBAA). By design these two queries should share one entry in the internal cache which corresponds to a general access (without TBAA). Thus upon second request internal cached is cleared and we continue analysis for access as if there is no TBAA.

The problem is that even though internal cache is cleared the set of visited nodes is not. That means we won't traverse visited nodes again and populate internal cache with the corresponding dependence results. So we end up with internal cache in an incomplete state. Current implementation tries to signal that situation by resetting CacheInfo->Pair at line 1104. But that doesn't actually help since later code ignores this invalidation and relies on 'Cache->empty()' property to decide on cache completeness.

Diff Detail

Event Timeline

ebrevnov created this revision.Jan 20 2020, 4:38 AM
Herald added a project: Restricted Project. · View Herald TranscriptJan 20 2020, 4:38 AM
ebrevnov updated this revision to Diff 239249.Jan 21 2020, 1:21 AM

Added regression test.

ebrevnov retitled this revision from [WIP][DependenceAnalysis] Fix for PR42733. to [DependenceAnalysis] Memory dependence analysis internal caching mechanism is broken in presence of TBAA (PR42733)..Jan 21 2020, 1:57 AM
ebrevnov edited the summary of this revision. (Show Details)
ebrevnov added reviewers: reames, jdoerfert.

Please excuse me for hijacking the review, but what is _exact_ meaning of BBSkipFirstBlockPair?
(I asked on llvm-dev@, but got no answer). Does it marks BB where query starts? Or first block where we've found something relevant? Anything else?

llvm/lib/Analysis/MemoryDependenceAnalysis.cpp
1133

This is confusing. How can empty cache be incomplete? Can valid cache be incomplete? Invalid cache?

Also, can we make it part of cache API, not external entity?

Please excuse me for hijacking the review, but what is _exact_ meaning of BBSkipFirstBlockPair?
(I asked on llvm-dev@, but got no answer). Does it marks BB where query starts? Or first block where we've found something relevant? Anything else?

BBSkipFirstBlockPair - keeps pair of BasicBlock and flag indicating whether dependencies in the BasicBlock itself were taken into account or not. Other way to think about this flag is whether calculated dependencies for the beginning or the end of the BasicBlock. If BasicBlock is not null then underlying cache represents all dependencies for particular memory address at this BasicBlock (this is what I mean by "complete" cache). If BasicBlock is null then underlying cache may have some dependence information but it doesn't represent all dependencies (this is what I mean by "incomplete" cache). Please note that information in the cache still valid it just not full. Probably it's better to use "Inexact" instead of "Incomplete" because opposite situation is possible as well (when cache has extra dependencies).

ebrevnov marked an inline comment as done.Jan 22 2020, 9:12 PM
ebrevnov added inline comments.
llvm/lib/Analysis/MemoryDependenceAnalysis.cpp
1133

This is confusing. How can empty cache be incomplete? Can valid cache be incomplete? Invalid cache?

One way to think about it is as of two level cache. Second level cache doesn't know anything about first level cache. It always by design contains valid information. Thus empty cache is always valid since it doesn't contain any wrong data. But from the point of first level cache second level cache is "incomplete" if it doesn't contain all the required information. Hopefully that description helps... at least a bit :-)

Also, can we make it part of cache API, not external entity?

Could you clarify?

dantrushin added inline comments.Jan 23 2020, 7:56 AM
llvm/lib/Analysis/MemoryDependenceAnalysis.cpp
1133

Cache->incomplete() or something like that

ebrevnov marked an inline comment as done.Feb 4 2020, 2:54 AM
ebrevnov added inline comments.
llvm/lib/Analysis/MemoryDependenceAnalysis.cpp
1133

Essentially, we already have this facility. This is done by setting and resetting BB in CacheInfo->Pair.
In our case "isIncomplete" signals local state of the cache which is used to calculate actual state of the cache. Even though it's possible to carry local state with the cache I think it makes sense to do as it may cause confusion.

I would like us to move with this review as fast as possible since we have multiple occurrences of this issue in different places...

PING.. I'm going to wait couple more days on that before committing. Please provide your feedback if any.

I don't know how this cache works, people familiar with it need to take a look.

It looks like the change that introduced isInvariantLoad was reverted in commit 446acafb82b5c116b6c94c11d4ac4db7641fa58d, so it's a bit hard to review this with current trunk. Is there any problem with memory dependence analysis as it is, or is there a problem only with isInvariantLoad?

It looks like the change that introduced isInvariantLoad was reverted in commit 446acafb82b5c116b6c94c11d4ac4db7641fa58d, so it's a bit hard to review this with current trunk. Is there any problem with memory dependence analysis as it is, or is there a problem only with isInvariantLoad?

I understand you concern, sorry for the inconvenience. I've just landed isInvariantLoad fix and rebased this one. That shouldn't be an issue any more. This problem is completely separate from isInvariantLoad.

john.brawn accepted this revision.Feb 14 2020, 10:01 AM

LGTM, though with a suggestion for adjusting a comment to be clearer.

I do think though that MemoryDependenceAnalysis could do with an overhaul, as it's by now accumulated enough little fixes here and there that figuring out what's going on is way more difficult than it should be. In particular we could do with making the cache state explicit in NonLocalPointerInfo, instead of trying to infer it from from the other members. I may try doing that myself, but unfortunately I'm swamped with other things and won't have a chance for at least a week or so.

llvm/lib/Analysis/MemoryDependenceAnalysis.cpp
1052–1054

The comment here (and below) is a bit confusing, as my initial reading of it was "If the list of visited blocks hasn't been cleared, wouldn't clearing it fix things?". As I understand it, the problem is actually: we may have visited some block and stored information for it in NonLocalDeps and this has now been lost, and as we only ever visit a given block once for a given pointer value this guarantees that the final result will be incomplete.

I think a better comment would be something like

// The cache is cleared (in the above line) so we will have lost information
// about blocks we have already visited. We therefore must assume that
// the cache information is incomplete.
This revision is now accepted and ready to land.Feb 14 2020, 10:01 AM
ebrevnov marked 2 inline comments as done.Feb 21 2020, 2:53 AM

LGTM, though with a suggestion for adjusting a comment to be clearer.

I do think though that MemoryDependenceAnalysis could do with an overhaul, as it's by now accumulated enough little fixes here and there that figuring out what's going on is way more difficult than it should be. In particular we could do with making the cache state explicit in NonLocalPointerInfo, instead of trying to infer it from from the other members. I may try doing that myself, but unfortunately I'm swamped with other things and won't have a chance for at least a week or so.

Agree. There should be ways to make things easier for understanding...

llvm/lib/Analysis/MemoryDependenceAnalysis.cpp
1052–1054

I like your wording. Fixed.

This revision was automatically updated to reflect the committed changes.
ebrevnov marked an inline comment as done.