[MemoryDependencyAnalysis] Delete cache infos if CacheInfo->size != Loc.size

[StephenFan]

Summary

In the past, if the size value of CacheInfo was greater than Loc's size
value, the CacheInfo would not be dropped and we repalced Loc's size
with CacheInfo's size to compute the dependencies. However it caused two
problems:

1. With a greater Loc size, we might get a imprecise result which shows in test GVN/PRE/rle.ll.

2.If we have a pointer value that can be translated to a block twice(%array.2.phi.2 in pr53599.ll), using a greater size may cause dependencies of smaller size been added to greater size's CacheInfo. And then some non-redundant load instructions would be deleted.

Compile time differences:https://llvm-compile-time-tracker.com/compare.php?from=18eb31c096167a1f6185f05338494c82a509ff9e&to=65fba50ce274460ad88f90e0ae29d36869e42d71&stat=instructions:u

Fixes: https://github.com/llvm/llvm-project/issues/63559 and https://github.com/llvm/llvm-project/issues/63611

[StephenFan]

Also fixes another issue.

[nikic]

2.If we have a pointer value that can be translated to a block twice(%array.2.phi.2 in pr53599.ll), using a greater size may cause dependencies of smaller size been added to greater size's CacheInfo. And then some non-redundant load instructions would be deleted.

Could you please explain this part in more detail? I don't really get why working with the greater size is not conservatively correct.

[StephenFan]

In D154323#4469551, @nikic wrote:

2.If we have a pointer value that can be translated to a block twice(%array.2.phi.2 in pr53599.ll), using a greater size may cause dependencies of smaller size been added to greater size's CacheInfo. And then some non-redundant load instructions would be deleted.

Could you please explain this part in more detail? I don't really get why working with the greater size is not conservatively correct.

Consider this example:

entry:
  %array.2 = ...

header:
  %array.2.phi.1 = phi ptr [ %array.2, %entry ], [ %array.2.phi.2, %latch ]
  br ..., label %merge, label %then_block

then_block:
  %array.2.remat = ...
  br label %merge

merge:
  %array.2.phi.2 = phi ptr [ %array.2.phi.1, %header ], [ %array.2.remat, %then_block]
  br ..., label %iter.peel, label %side_exit

iter.peel:
  %clobber_array.2.phi.2_with_size_8 = ...
  %clobber_array.2.phi.2_with_size_16 = ...
  br ..., label %latch, label %side_exit

latch:
  %clobber_array.2.phi.2 = ...
  br i1 %test_i5, label %return, label %header

side_exit:
  %val.array.2.1 = load atomic i64, ptr %array.2.phi.2 unordered, align 8

First of all, assume there is only one NonLocalDefsCache entry which its key is
(%array.2.phi.1, true), and the size is 16

1. we want to get the clobber of instruction %val.array.2.1 = load atomic i64, ptr %array.2.phi.2 unordered, align 8 , so we need to get %array.2.phi.2's pointer dependency. According to the implementation, before the query starts, we would insert an entry to NonLocalPointerDeps which is (%array.2.phi.2, true) and with size 8. The predecessors of block %side_exit are %merge and %iter.peel. These two blocks would be added to the worklist.
2. We first choose %merge block, there is no dependency in %merge, so we do PhiTranslation for %array.2.phi.2. For (%array.2.remat, %then_block), nothing happens. For (%array.2.phi.1, %header), there is a cache entry in NonLocalDefsCache with size 16. But currently, the Loc's size is 8. According to the implementation, we will redo the query with cache's size, which is 16.
3. At this point, we were querying (%array.2.phi.1, %header) with size 16. At the %header block, there is no any dependency. So then we do PhiTranslation for %array.2.phi.1. For (%array.2, %entry), nothing happens. For (%array.2.phi.2, %latch), since in Step 1, we have inserted a cache entry with size 8. According to the implementation, we will clear the cache entry and set the size from 8 to 16. then we find a clobber which is %clobber_array.2.phi.2. The query returns since we have found a clobber.
4. But according to Step 1, at this point, we just finished the query of %merge. We still need to search to %iter.peel And unfortunately, we thought the cache entry size of %array.2.phi.2 is 8, but actually, it has been set to 16 in Step 3. And because the Loc size is still 8, we would only find %clobber_array.2.phi.2_with_size_8. Then we add this clobber info (%iter.peel, %clobber_array.2.phi.2_with_size_8) to the cache. Okay, then the error has existed since we query a clobber with size 8, but added to a size 16 cache.

[nikic]

A concern I have is: Can the same also happen with AATags and not just Size? The logic there is very similar. And while just clearing the cache entry for Size mismatch is probably okay, I don't think this would work for AATags (which will often differ).

llvm/lib/Analysis/MemoryDependenceAnalysis.cpp

std::pair<CachedNonLocalPointerInfo::iterator, bool> Pair =
       NonLocalPointerDeps.insert(std::make_pair(CacheKey, InitialNLPI));
   NonLocalPointerInfo *CacheInfo = &Pair.first->second;
 
   // If we already have a cache entry for this CacheKey, we may need to do some
   // work to reconcile the cache entry and the current query.
   // Invariant loads don't participate in caching. Thus no need to reconcile.
   if (!isInvariantLoad && !Pair.second) {
     if (CacheInfo->Size != Loc.Size) {
-      bool ThrowOutEverything;
-      if (CacheInfo->Size.hasValue() && Loc.Size.hasValue()) {
-        // FIXME: We may be able to do better in the face of results with mixed
-        // precision. We don't appear to get them in practice, though, so just
-        // be conservative.
-        ThrowOutEverything =
-            CacheInfo->Size.isPrecise() != Loc.Size.isPrecise() ||
-            CacheInfo->Size.getValue() < Loc.Size.getValue();
-      } else {
-        // For our purposes, unknown size > all others.
-        ThrowOutEverything = !Loc.Size.hasValue();
-      }
-
-      if (ThrowOutEverything) {
-        // 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) so we will have lost
-        // information about blocks we have already visited. We therefore must
-        // assume that the cache information is 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, IsIncomplete);
-      }
+      // The query's Size is not the same as the cached one. Throw out the
+      // cached data and proceed with the query at the new size.
     }
 
     // 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();

llvm/test/Analysis/MemoryDependenceAnalysis/pr63559.ll

+; NOTE: Assertions have been autogenerated by utils/update_test_checks.py UTC_ARGS: --version 2
+; RUN: opt -passes=gvn -S %s | FileCheck %s
+
+define void @test(ptr %array, i32 %v0, i32 %v1, i32 %v2) {
+; CHECK-LABEL: define void @test
+; CHECK-SAME: (ptr [[ARRAY:%.*]], i32 [[V0:%.*]], i32 [[V1:%.*]], i32 [[V2:%.*]]) {
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[ARRAY_2:%.*]] = getelementptr inbounds i8, ptr [[ARRAY]], i64 32
+; CHECK-NEXT:    [[ARRAY_3:%.*]] = getelementptr inbounds i8, ptr [[ARRAY]], i64 40
+; CHECK-NEXT:    br label [[HEADER:%.*]]
+; CHECK:       header:
+; CHECK-NEXT:    [[ARRAY_2_PHI_1:%.*]] = phi ptr [ [[ARRAY_2]], [[ENTRY:%.*]] ], [ [[ARRAY_2_PHI_2:%.*]], [[LATCH:%.*]] ]
+; CHECK-NEXT:    [[ARRAY_3_PHI_1:%.*]] = phi ptr [ [[ARRAY_3]], [[ENTRY]] ], [ [[ARRAY_3_PHI_2:%.*]], [[LATCH]] ]
+; CHECK-NEXT:    [[LOCAL_I5:%.*]] = phi i64 [ 4, [[ENTRY]] ], [ [[LOCAL_I5_NEXT:%.*]], [[LATCH]] ]
+; CHECK-NEXT:    [[V18:%.*]] = icmp eq i32 [[V1]], 0
+; CHECK-NEXT:    br i1 [[V18]], label [[MERGE:%.*]], label [[THEN_BLOCK:%.*]]
+; CHECK:       then_block:
+; CHECK-NEXT:    [[ARRAY_RELOC_1:%.*]] = call ptr @realloc(ptr [[ARRAY]])
+; CHECK-NEXT:    [[ARRAY_2_REMAT:%.*]] = getelementptr inbounds i8, ptr [[ARRAY_RELOC_1]], i64 32
+; CHECK-NEXT:    [[ARRAY_3_REMAT:%.*]] = getelementptr inbounds i8, ptr [[ARRAY_RELOC_1]], i64 40
+; CHECK-NEXT:    br label [[MERGE]]
+; CHECK:       merge:
+; CHECK-NEXT:    [[ARRAY_3_PHI_2]] = phi ptr [ [[ARRAY_3_PHI_1]], [[HEADER]] ], [ [[ARRAY_3_REMAT]], [[THEN_BLOCK]] ]
+; CHECK-NEXT:    [[ARRAY_2_PHI_2]] = phi ptr [ [[ARRAY_2_PHI_1]], [[HEADER]] ], [ [[ARRAY_2_REMAT]], [[THEN_BLOCK]] ]
+; CHECK-NEXT:    [[V22:%.*]] = icmp eq i32 [[V0]], 0
+; CHECK-NEXT:    br i1 [[V22]], label [[ITER_PEEL:%.*]], label [[SIDE_EXIT:%.*]]
+; CHECK:       iter.peel:
+; CHECK-NEXT:    [[VAL_ARRAY_2_3_1:%.*]] = load <2 x i64>, ptr [[ARRAY_2_PHI_2]], align 8
+; CHECK-NEXT:    [[V24:%.*]] = insertelement <2 x i64> poison, i64 [[LOCAL_I5]], i64 0
+; CHECK-NEXT:    [[V25:%.*]] = shufflevector <2 x i64> [[V24]], <2 x i64> poison, <2 x i32> zeroinitializer
+; CHECK-NEXT:    [[VAL_ARRAY_2_3_2:%.*]] = add <2 x i64> [[VAL_ARRAY_2_3_1]], [[V25]]
+; CHECK-NEXT:    store <2 x i64> [[VAL_ARRAY_2_3_2]], ptr [[ARRAY_2_PHI_2]], align 8
+; CHECK-NEXT:    [[VAL_ARRAY_3_1:%.*]] = load atomic i64, ptr [[ARRAY_3_PHI_2]] unordered, align 8
+; CHECK-NEXT:    [[VAL_ARRAY_3_2:%.*]] = mul i64 [[VAL_ARRAY_3_1]], -1802
+; CHECK-NEXT:    store atomic i64 [[VAL_ARRAY_3_2]], ptr [[ARRAY_3_PHI_2]] unordered, align 8
+; CHECK-NEXT:    [[V30:%.*]] = icmp eq i32 [[V2]], 0
+; CHECK-NEXT:    br i1 [[V30]], label [[LATCH]], label [[SIDE_EXIT]]
+; CHECK:       latch:
+; CHECK-NEXT:    [[VAL_ARRAY_2_3_3:%.*]] = load <2 x i64>, ptr [[ARRAY_2_PHI_2]], align 8
+; CHECK-NEXT:    [[VAL_ARRAY_2_3_4:%.*]] = add <2 x i64> [[VAL_ARRAY_2_3_3]], [[V25]]
+; CHECK-NEXT:    store <2 x i64> [[VAL_ARRAY_2_3_4]], ptr [[ARRAY_2_PHI_2]], align 8
+; CHECK-NEXT:    [[LOCAL_I5_NEXT]] = add nuw nsw i64 [[LOCAL_I5]], 2
+; CHECK-NEXT:    [[TEST_I5:%.*]] = icmp ugt i64 [[LOCAL_I5]], 250
+; CHECK-NEXT:    br i1 [[TEST_I5]], label [[RETURN:%.*]], label [[HEADER]]
+; CHECK:       return:
+; CHECK-NEXT:    ret void
+; CHECK:       side_exit:
+; CHECK-NEXT:    [[VAL_ARRAY_2_1:%.*]] = load atomic i64, ptr [[ARRAY_2_PHI_2]] unordered, align 8
+; CHECK-NEXT:    [[VAL_ARRAY_2_2:%.*]] = add i64 [[VAL_ARRAY_2_1]], [[LOCAL_I5]]
+; CHECK-NEXT:    store atomic i64 [[VAL_ARRAY_2_2]], ptr [[ARRAY_2_PHI_2]] unordered, align 8
+; CHECK-NEXT:    ret void
+;
+entry:
+  %array.2 = getelementptr inbounds i8, ptr %array, i64 32
+  %array.3 = getelementptr inbounds i8, ptr %array, i64 40
+  br label %header
+
+header:
+  %array.2.phi.1 = phi ptr [ %array.2, %entry ], [ %array.2.phi.2, %latch ]
+  %array.3.phi.1 = phi ptr [ %array.3, %entry ], [ %array.3.phi.2, %latch ]
+  %local_i5 = phi i64 [ 4, %entry ], [ %local_i5.next, %latch ]
+  %v18 = icmp eq i32 %v1, 0
+  br i1 %v18, label %merge, label %then_block
+
+then_block:
+  %array.reloc.1 = call ptr @realloc(ptr %array)
+  %array.2.remat = getelementptr inbounds i8, ptr %array.reloc.1, i64 32
+  %array.3.remat = getelementptr inbounds i8, ptr %array.reloc.1, i64 40
+  br label %merge
+
+merge:
+  %array.3.phi.2 = phi ptr [ %array.3.phi.1, %header ], [ %array.3.remat, %then_block ]
+  %array.2.phi.2 = phi ptr [ %array.2.phi.1, %header ], [ %array.2.remat, %then_block ]
+  %v22 = icmp eq i32 %v0, 0
+  br i1 %v22, label %iter.peel, label %side_exit
+
+iter.peel:
+  %val.array.2_3.1 = load <2 x i64>, ptr %array.2.phi.2, align 8
+  %v24 = insertelement <2 x i64> poison, i64 %local_i5, i64 0
+  %v25 = shufflevector <2 x i64> %v24, <2 x i64> poison, <2 x i32> zeroinitializer
+  %val.array.2_3.2 = add <2 x i64> %val.array.2_3.1, %v25
+  store <2 x i64> %val.array.2_3.2, ptr %array.2.phi.2, align 8
+  %val.array.3.1 = load atomic i64, ptr %array.3.phi.2 unordered, align 8
+  %val.array.3.2 = mul i64 %val.array.3.1, -1802
+  store atomic i64 %val.array.3.2, ptr %array.3.phi.2 unordered, align 8
+  %v30 = icmp eq i32 %v2, 0
+  br i1 %v30, label %latch, label %side_exit
+
+latch:
+  %val.array.2_3.3 = load <2 x i64>, ptr %array.2.phi.2, align 8
+  %val.array.2_3.4 = add <2 x i64> %val.array.2_3.3, %v25
+  store <2 x i64> %val.array.2_3.4, ptr %array.2.phi.2, align 8
+  %local_i5.next= add nuw nsw i64 %local_i5, 2
+  %test_i5 = icmp ugt i64 %local_i5, 250
+  br i1 %test_i5, label %return, label %header
+
+return:
+  ret void
+
+side_exit:
+  %array.2.phi.2.lcssa = phi ptr [ %array.2.phi.2, %iter.peel ], [ %array.2.phi.2, %merge ]
+  %val.array.2.1 = load atomic i64, ptr %array.2.phi.2.lcssa unordered, align 8
+  %val.array.2.2 = add i64 %val.array.2.1, %local_i5
+  store atomic i64 %val.array.2.2, ptr %array.2.phi.2.lcssa unordered, align 8
+  ret void
+}
+
+declare ptr @realloc(ptr)

llvm/test/Transforms/GVN/PRE/rle.ll

 ; LE-NEXT:    [[P_1:%.*]] = getelementptr i8, ptr [[P:%.*]], i64 1
 ; LE-NEXT:    [[V_1:%.*]] = load i8, ptr [[P_1]], align 1
 ; LE-NEXT:    call void @use.i8(i8 [[V_1]])
 ; LE-NEXT:    [[V_1_32:%.*]] = load i32, ptr [[P_1]], align 4
 ; LE-NEXT:    call void @use.i32(i32 [[V_1_32]])
 ; LE-NEXT:    [[TMP0:%.*]] = trunc i32 [[V_1_32]] to i8
 ; LE-NEXT:    br label [[LOOP:%.*]]
 ; LE:       loop:
-; LE-NEXT:    [[V_I:%.*]] = phi i8 [ [[TMP0]], [[ENTRY:%.*]] ], [ [[V_I_PRE:%.*]], [[LOOP_LOOP_CRIT_EDGE:%.*]] ]
+; LE-NEXT:    [[V_I:%.*]] = phi i8 [ [[TMP0]], [[ENTRY:%.*]] ], [ [[TMP2:%.*]], [[LOOP_LOOP_CRIT_EDGE:%.*]] ]
 ; LE-NEXT:    [[I:%.*]] = phi i64 [ 1, [[ENTRY]] ], [ [[I_INC:%.*]], [[LOOP_LOOP_CRIT_EDGE]] ]
 ; LE-NEXT:    [[P_I:%.*]] = getelementptr i8, ptr [[P]], i64 [[I]]
 ; LE-NEXT:    call void @use.i8(i8 [[V_I]])
 ; LE-NEXT:    [[V_I_32:%.*]] = load i32, ptr [[P_I]], align 4
 ; LE-NEXT:    call void @use.i32(i32 [[V_I_32]])
 ; LE-NEXT:    [[I_INC]] = add i64 [[I]], 1
 ; LE-NEXT:    [[CMP:%.*]] = icmp ne i64 [[I_INC]], 64
+; LE-NEXT:    [[TMP1:%.*]] = lshr i32 [[V_I_32]], 8
+; LE-NEXT:    [[TMP2]] = trunc i32 [[TMP1]] to i8
 ; LE-NEXT:    br i1 [[CMP]], label [[LOOP_LOOP_CRIT_EDGE]], label [[EXIT:%.*]]
 ; LE:       loop.loop_crit_edge:
-; LE-NEXT:    [[P_I_PHI_TRANS_INSERT:%.*]] = getelementptr i8, ptr [[P]], i64 [[I_INC]]
-; LE-NEXT:    [[V_I_PRE]] = load i8, ptr [[P_I_PHI_TRANS_INSERT]], align 1
 ; LE-NEXT:    br label [[LOOP]]
 ; LE:       exit:
 ; LE-NEXT:    ret void
 ;
 ; BE-LABEL: @load_load_partial_alias_loop(
 ; BE-NEXT:  entry:
 ; BE-NEXT:    [[P_1:%.*]] = getelementptr i8, ptr [[P:%.*]], i64 1
 ; BE-NEXT:    [[V_1:%.*]] = load i8, ptr [[P_1]], align 1
 ; BE-NEXT:    call void @use.i8(i8 [[V_1]])
 ; BE-NEXT:    [[V_1_32:%.*]] = load i32, ptr [[P_1]], align 4
 ; BE-NEXT:    call void @use.i32(i32 [[V_1_32]])
 ; BE-NEXT:    [[TMP0:%.*]] = lshr i32 [[V_1_32]], 24
 ; BE-NEXT:    [[TMP1:%.*]] = trunc i32 [[TMP0]] to i8
 ; BE-NEXT:    br label [[LOOP:%.*]]
 ; BE:       loop:
-; BE-NEXT:    [[V_I:%.*]] = phi i8 [ [[TMP1]], [[ENTRY:%.*]] ], [ [[V_I_PRE:%.*]], [[LOOP_LOOP_CRIT_EDGE:%.*]] ]
+; BE-NEXT:    [[V_I:%.*]] = phi i8 [ [[TMP1]], [[ENTRY:%.*]] ], [ [[TMP3:%.*]], [[LOOP_LOOP_CRIT_EDGE:%.*]] ]
 ; BE-NEXT:    [[I:%.*]] = phi i64 [ 1, [[ENTRY]] ], [ [[I_INC:%.*]], [[LOOP_LOOP_CRIT_EDGE]] ]
 ; BE-NEXT:    [[P_I:%.*]] = getelementptr i8, ptr [[P]], i64 [[I]]
 ; BE-NEXT:    call void @use.i8(i8 [[V_I]])
 ; BE-NEXT:    [[V_I_32:%.*]] = load i32, ptr [[P_I]], align 4
 ; BE-NEXT:    call void @use.i32(i32 [[V_I_32]])
 ; BE-NEXT:    [[I_INC]] = add i64 [[I]], 1
 ; BE-NEXT:    [[CMP:%.*]] = icmp ne i64 [[I_INC]], 64
+; BE-NEXT:    [[TMP2:%.*]] = lshr i32 [[V_I_32]], 16
+; BE-NEXT:    [[TMP3]] = trunc i32 [[TMP2]] to i8
 ; BE-NEXT:    br i1 [[CMP]], label [[LOOP_LOOP_CRIT_EDGE]], label [[EXIT:%.*]]
 ; BE:       loop.loop_crit_edge:
-; BE-NEXT:    [[P_I_PHI_TRANS_INSERT:%.*]] = getelementptr i8, ptr [[P]], i64 [[I_INC]]
-; BE-NEXT:    [[V_I_PRE]] = load i8, ptr [[P_I_PHI_TRANS_INSERT]], align 1
 ; BE-NEXT:    br label [[LOOP]]
 ; BE:       exit:
 ; BE-NEXT:    ret void
 ;
 entry:
   %P.1 = getelementptr i8, ptr %P, i64 1
   %v.1 = load i8, ptr %P.1
   call void @use.i8(i8 %v.1)