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

[ebrevnov]

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.

[ebrevnov]

Added regression test.

[dantrushin]

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

1173

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?

[ebrevnov]

In D73032#1833453, @dantrushin wrote:

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]

llvm/lib/Analysis/MemoryDependenceAnalysis.cpp

1173

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]

llvm/lib/Analysis/MemoryDependenceAnalysis.cpp

1173

Cache->incomplete() or something like that

[ebrevnov]

llvm/lib/Analysis/MemoryDependenceAnalysis.cpp

1173

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.

[ebrevnov]

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

[ebrevnov]

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

[jdoerfert]

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

[john.brawn]

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?

[ebrevnov]

Rebase

[ebrevnov]

In D73032#1874605, @john.brawn wrote:

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]

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

1086–1088

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.

[ebrevnov]

In D73032#1876719, @john.brawn wrote:

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

1086–1088

I like your wording. Fixed.

llvm/include/llvm/Analysis/MemoryDependenceAnalysis.h

MemDepResult getCallDependencyFrom(CallBase *Call, bool isReadOnlyCall,
                                      BasicBlock::iterator ScanIt,
                                      BasicBlock *BB);
   bool getNonLocalPointerDepFromBB(Instruction *QueryInst,
                                    const PHITransAddr &Pointer,
                                    const MemoryLocation &Loc, bool isLoad,
                                    BasicBlock *BB,
                                    SmallVectorImpl<NonLocalDepResult> &Result,
                                    DenseMap<BasicBlock *, Value *> &Visited,
-                                   bool SkipFirstBlock = false);
+                                   bool SkipFirstBlock = false,
+                                   bool IsIncomplete = false);
   MemDepResult GetNonLocalInfoForBlock(Instruction *QueryInst,
                                        const MemoryLocation &Loc, bool isLoad,
                                        BasicBlock *BB, NonLocalDepInfo *Cache,
                                        unsigned NumSortedEntries);
 
   void RemoveCachedNonLocalPointerDependencies(ValueIsLoadPair P);
 
   void verifyRemoved(Instruction *Inst) const;

llvm/lib/Analysis/MemoryDependenceAnalysis.cpp

 ///
 /// This function returns true on success, or false to indicate that it could
 /// not compute dependence information for some reason.  This should be treated
 /// as a clobber dependence on the first instruction in the predecessor block.
 bool MemoryDependenceResults::getNonLocalPointerDepFromBB(
     Instruction *QueryInst, const PHITransAddr &Pointer,
     const MemoryLocation &Loc, bool isLoad, BasicBlock *StartBB,
     SmallVectorImpl<NonLocalDepResult> &Result,
-    DenseMap<BasicBlock *, Value *> &Visited, bool SkipFirstBlock) {
+    DenseMap<BasicBlock *, Value *> &Visited, bool SkipFirstBlock,
+    bool IsIncomplete) {
   // Look up the cached info for Pointer.
   ValueIsLoadPair CacheKey(Pointer.getAddr(), isLoad);
 
   // Set up a temporary NLPI value. If the map doesn't yet have an entry for
   // CacheKey, this value will be inserted as the associated value. Otherwise,
   // it'll be ignored, and we'll have to check to see if the cached size and
   // aa tags are consistent with the current query.
   NonLocalPointerInfo InitialNLPI;
if (CacheInfo->Size != Loc.Size) {
         // The query's Size is greater than the cached one. Throw out the
         // cached data and proceed with the query at the greater size.
         CacheInfo->Pair = BBSkipFirstBlockPair();
         CacheInfo->Size = Loc.Size;
         for (auto &Entry : CacheInfo->NonLocalDeps)
           if (Instruction *Inst = Entry.getResult().getInst())
             RemoveFromReverseMap(ReverseNonLocalPtrDeps, Inst, CacheKey);
         CacheInfo->NonLocalDeps.clear();
+        // The cache is cleared (in the above line) but list of visited blocks
+        // is not. That means the cache will be missing information about
+        // visited blocks, thus incomplete.
+        IsIncomplete = true;
       } else {
         // This query's Size is less than the cached one. Conservatively restart
         // the query using the greater size.
         return getNonLocalPointerDepFromBB(
             QueryInst, Pointer, Loc.getWithNewSize(CacheInfo->Size), isLoad,
-            StartBB, Result, Visited, SkipFirstBlock);
+            StartBB, Result, Visited, SkipFirstBlock, IsIncomplete);
       }
     }
 
     // If the query's AATags are inconsistent with the cached one,
     // conservatively throw out the cached data and restart the query with
     // no tag if needed.
     if (CacheInfo->AATags != Loc.AATags) {
       if (CacheInfo->AATags) {
         CacheInfo->Pair = BBSkipFirstBlockPair();
         CacheInfo->AATags = AAMDNodes();
         for (auto &Entry : CacheInfo->NonLocalDeps)
           if (Instruction *Inst = Entry.getResult().getInst())
             RemoveFromReverseMap(ReverseNonLocalPtrDeps, Inst, CacheKey);
         CacheInfo->NonLocalDeps.clear();
+        // The cache is cleared (in the above line) but list of visited blocks
+        // is not. That means the cache will be missing information about
+        // visited blocks, thus incomplete.
+        IsIncomplete = true;
       }
       if (Loc.AATags)
         return getNonLocalPointerDepFromBB(
             QueryInst, Pointer, Loc.getWithoutAATags(), isLoad, StartBB, Result,
-            Visited, SkipFirstBlock);
+            Visited, SkipFirstBlock, IsIncomplete);
     }
   }
 
   NonLocalDepInfo *Cache = &CacheInfo->NonLocalDeps;
 
   // If we have valid cached information for exactly the block we are
   // investigating, just return it with no recomputation.
   // Don't use cached information for invariant loads since it is valid for
   // non-invariant loads only.
-  if (!isInvariantLoad &&
+  //
+  if (!IsIncomplete && !isInvariantLoad &&
       CacheInfo->Pair == BBSkipFirstBlockPair(StartBB, SkipFirstBlock)) {
     // We have a fully cached result for this query then we can just return the
     // cached results and populate the visited set.  However, we have to verify
     // that we don't already have conflicting results for these blocks.  Check
     // to ensure that if a block in the results set is in the visited set that
     // it was for the same pointer query.
     if (!Visited.empty()) {
       for (auto &Entry : *Cache) {
if (!IsIncomplete && !isInvariantLoad &&
     return true;
   }
 
   // Invariant loads don't affect cache in any way thus no need to update
   // CacheInfo as well.
   if (!isInvariantLoad) {
     // Otherwise, either this is a new block, a block with an invalid cache
     // pointer or one that we're about to invalidate by putting more info into
-    // it than its valid cache info.  If empty, the result will be valid cache
-    // info, otherwise it isn't.
-    if (Cache->empty())
+    // it than its valid cache info.  If empty and not explicitly indicated as
+    // incomplete, the result will be valid cache info, otherwise it isn't.
+    if (!IsIncomplete && Cache->empty())
       CacheInfo->Pair = BBSkipFirstBlockPair(StartBB, SkipFirstBlock);
     else
       CacheInfo->Pair = BBSkipFirstBlockPair();
   }
 
   SmallVector<BasicBlock *, 32> Worklist;
   Worklist.push_back(StartBB);
 

llvm/test/Analysis/MemoryDependenceAnalysis/memdep_with_tbaa.ll

+; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
+; RUN: opt -aa-pipeline=basic-aa -passes=gvn -S < %s | FileCheck %s
+
+; This test catches an issue in MemoryDependenceAnalysis caching mechanism in presense of TBAA.
+define i64 @foo(i64 addrspace(1)** %arg, i1 %arg1, i1 %arg2, i1 %arg3, i32 %arg4) {
+; CHECK-LABEL: @foo(
+; CHECK-NEXT:  bb:
+; CHECK-NEXT:    [[TMP:%.*]] = load atomic i64 addrspace(1)*, i64 addrspace(1)** [[ARG:%.*]] unordered, align 8
+; CHECK-NEXT:    [[TMP5:%.*]] = getelementptr inbounds i64, i64 addrspace(1)* [[TMP]], i64 8
+; CHECK-NEXT:    store atomic i64 0, i64 addrspace(1)* [[TMP5]] unordered, align 8
+; CHECK-NEXT:    br label [[BB6:%.*]]
+; CHECK:       bb6:
+; CHECK-NEXT:    [[TMP7:%.*]] = phi i64 [ 0, [[BB:%.*]] ], [ [[TMP22:%.*]], [[BB19:%.*]] ]
+; CHECK-NEXT:    br i1 [[ARG1:%.*]], label [[BB19]], label [[BB8:%.*]]
+; CHECK:       bb8:
+; CHECK-NEXT:    [[TMP9:%.*]] = load atomic i64 addrspace(1)*, i64 addrspace(1)** [[ARG]] unordered, align 8
+; CHECK-NEXT:    br i1 [[ARG2:%.*]], label [[BB11:%.*]], label [[BB10:%.*]]
+; CHECK:       bb10:
+; CHECK-NEXT:    br label [[BB15:%.*]]
+; CHECK:       bb11:
+; CHECK-NEXT:    br i1 [[ARG3:%.*]], label [[BB12:%.*]], label [[BB18:%.*]]
+; CHECK:       bb12:
+; CHECK-NEXT:    [[TMP14:%.*]] = getelementptr inbounds i64, i64 addrspace(1)* [[TMP9]], i64 8
+; CHECK-NEXT:    store atomic i64 1, i64 addrspace(1)* [[TMP14]] unordered, align 8
+; CHECK-NEXT:    ret i64 0
+; CHECK:       bb15:
+; CHECK-NEXT:    [[TMP16:%.*]] = phi i64 addrspace(1)* [ [[TMP9]], [[BB10]] ], [ [[TMP27:%.*]], [[BB26:%.*]] ]
+; CHECK-NEXT:    [[TMP17:%.*]] = phi i64 [ [[TMP7]], [[BB10]] ], [ 0, [[BB26]] ]
+; CHECK-NEXT:    switch i32 [[ARG4:%.*]], label [[BB19]] [
+; CHECK-NEXT:    i32 0, label [[BB26]]
+; CHECK-NEXT:    i32 1, label [[BB23:%.*]]
+; CHECK-NEXT:    ]
+; CHECK:       bb18:
+; CHECK-NEXT:    br label [[BB19]]
+; CHECK:       bb19:
+; CHECK-NEXT:    [[TMP20:%.*]] = phi i64 addrspace(1)* [ [[TMP16]], [[BB15]] ], [ inttoptr (i64 1 to i64 addrspace(1)*), [[BB6]] ], [ [[TMP9]], [[BB18]] ]
+; CHECK-NEXT:    [[TMP21:%.*]] = getelementptr inbounds i64, i64 addrspace(1)* [[TMP20]], i64 8
+; CHECK-NEXT:    [[TMP22]] = load atomic i64, i64 addrspace(1)* [[TMP21]] unordered, align 8, !tbaa !0
+; CHECK-NEXT:    br label [[BB6]]
+; CHECK:       bb23:
+; CHECK-NEXT:    [[TMP24:%.*]] = getelementptr inbounds i64, i64 addrspace(1)* [[TMP16]], i64 8
+; CHECK-NEXT:    [[TMP25:%.*]] = load atomic i64, i64 addrspace(1)* [[TMP24]] unordered, align 8
+; CHECK-NEXT:    call void @baz(i64 [[TMP25]]) #0
+; CHECK-NEXT:    ret i64 0
+; CHECK:       bb26:
+; CHECK-NEXT:    call void @bar()
+; CHECK-NEXT:    [[TMP27]] = load atomic i64 addrspace(1)*, i64 addrspace(1)** [[ARG]] unordered, align 8
+; CHECK-NEXT:    [[TMP28:%.*]] = getelementptr inbounds i64, i64 addrspace(1)* [[TMP27]], i64 8
+; CHECK-NEXT:    [[TMP29:%.*]] = load atomic i64, i64 addrspace(1)* [[TMP28]] unordered, align 8
+; CHECK-NEXT:    [[TMP30:%.*]] = getelementptr inbounds i64, i64 addrspace(1)* [[TMP27]], i64 40
+; CHECK-NEXT:    store atomic i64 [[TMP29]], i64 addrspace(1)* [[TMP30]] unordered, align 4
+; CHECK-NEXT:    br label [[BB15]]
+;
+bb:
+  %tmp = load atomic i64 addrspace(1)*, i64 addrspace(1)** %arg unordered, align 8
+  %tmp5 = getelementptr inbounds i64, i64 addrspace(1)* %tmp, i64 8
+  store atomic i64 0, i64 addrspace(1)* %tmp5 unordered, align 8
+  br label %bb6
+
+bb6:                                              ; preds = %bb19, %bb
+  %tmp7 = phi i64 [ 0, %bb ], [ %tmp22, %bb19 ]
+  %tmp111 = inttoptr i64 1 to i64 addrspace(1)*
+  br i1 %arg1, label %bb19, label %bb8
+
+bb8:                                              ; preds = %bb6
+  %tmp9 = load atomic i64 addrspace(1)*, i64 addrspace(1)** %arg unordered, align 8
+  br i1 %arg2, label %bb11, label %bb10
+
+bb10:                                             ; preds = %bb8
+  br label %bb15
+
+bb11:                                             ; preds = %bb8
+  br i1 %arg3, label %bb12, label %bb18
+
+bb12:                                             ; preds = %bb11
+  %tmp13 = phi i64 addrspace(1)* [ %tmp9, %bb11 ]
+  %tmp14 = getelementptr inbounds i64, i64 addrspace(1)* %tmp13, i64 8
+  store atomic i64 1, i64 addrspace(1)* %tmp14 unordered, align 8
+  ret i64 0
+
+bb15:                                             ; preds = %bb26, %bb10
+  %tmp16 = phi i64 addrspace(1)* [ %tmp9, %bb10 ], [ %tmp27, %bb26 ]
+  %tmp17 = phi i64 [ %tmp7, %bb10 ], [ 0, %bb26 ]
+  switch i32 %arg4, label %bb19 [
+  i32 0, label %bb26
+  i32 1, label %bb23
+  ]
+
+bb18:                                             ; preds = %bb11
+  br label %bb19
+
+bb19:                                             ; preds = %bb18, %bb15, %bb6
+  %tmp20 = phi i64 addrspace(1)* [ %tmp16, %bb15 ], [ %tmp111, %bb6 ], [ %tmp9, %bb18 ]
+  %tmp21 = getelementptr inbounds i64, i64 addrspace(1)* %tmp20, i64 8
+  %tmp22 = load atomic i64, i64 addrspace(1)* %tmp21 unordered, align 8, !tbaa !0
+  br label %bb6
+
+bb23:                                             ; preds = %bb15
+  %tmp24 = getelementptr inbounds i64, i64 addrspace(1)* %tmp16, i64 8
+  %tmp25 = load atomic i64, i64 addrspace(1)* %tmp24 unordered, align 8
+  call void @baz(i64 %tmp25) #0
+  ret i64 0
+
+bb26:                                             ; preds = %bb15
+  call void @bar()
+  %tmp27 = load atomic i64 addrspace(1)*, i64 addrspace(1)** %arg unordered, align 8
+  %tmp28 = getelementptr inbounds i64, i64 addrspace(1)* %tmp27, i64 8
+  %tmp29 = load atomic i64, i64 addrspace(1)* %tmp28 unordered, align 8
+  %tmp30 = getelementptr inbounds i64, i64 addrspace(1)* %tmp27, i64 40
+  store atomic i64 %tmp29, i64 addrspace(1)* %tmp30 unordered, align 4
+  br label %bb15
+}
+
+declare void @bar()
+
+; Function Attrs: inaccessiblememonly readonly
+declare void @baz(i64) #0
+
+attributes #0 = { inaccessiblememonly readonly }
+
+!0 = !{!1, !2, i64 8}
+!1 = !{!"Name", !2, i64 8}
+!2 = !{!"tbaa_local_fields", !3, i64 0}
+!3 = !{!"tbaa-access-type"}
+