[MemDep] Don't use cached results from a previous larger query

[sunfish]

Summary

When a memdep query finds a cached result from a previous query that had a larger size, don't reuse the cached results, because aliasing queries with a greater size aren't always more conservative. For example, BasicAA knows that accesses larger than the size of underlying objects don't alias those objects.

This could increase compile time in the case of many queries to the same pointer with successively smaller sizes, though this is uncommon.

Fixes PR35519.

[sanjoy]

lib/Analysis/MemoryDependenceAnalysis.cpp

1127–1129

You can still use the result if CacheInfo->Size is UnknownSize, right?

And, secondly, any reason to not add the size to the cache key as well?

[sunfish]

This adds a fix for the testcase reported in PR35519; see the change in MemCpyOptimizer.cpp. The code for merging stores into a memset wasn't properly updating memdep's query cache.

This isn't ready for final review yet:

• I plan to add a reduced testcase. (It's complex to write as the bug requires a specific sequence of events -- one optimization happens in a way that leaves the cache in an incorrect state, then a second optimization relies on the cache).
• I plan to address @sanjoy's review feedback.

[sunfish]

• Fixes debug info updating.
• Adds a proper testcase for the memset merging caching bug.

[sunfish]

lib/Analysis/MemoryDependenceAnalysis.cpp

1127–1129

Yes, I think reusing the result from an UnknownSize query would be conservatively correct, though it would be less precise. Also, yes, we could add the size, and the AATags too for that matter, to the key, however it would make the DenseMap use more memory.

My expectation, which seems supported by some ad-hoc experiments, is that repeated queries with the same pointer and differing sizes aren't very common. Assuming this is true in general, it seems best to avoid pessimizing common cases to optimize it.

[sunfish]

The issue reported in PR35519 is now fixed, there's a testcase now, and I responded to @sanjoy's comment above.

[hfinkel]

LGTM

This is a pretty awful implicit contract. Hopefully, we'll update this pass to use MemorySSA soon.

lib/Transforms/Scalar/MemCpyOptimizer.cpp

495

Please include the fact that you're talking about MemDep here, such as:

... on the removed instructions in MemoryDependenceAnalysis, the...

[sunfish]

lib/Transforms/Scalar/MemCpyOptimizer.cpp

495

Done.

lib/Analysis/MemoryDependenceAnalysis.cpp

bool MemoryDependenceResults::getNonLocalPointerDepFromBB(
   // already have one.
   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.
   if (!Pair.second) {
-    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.
+    if (CacheInfo->Size != Loc.Size) {
+      // The query's Size differs from the cached one. Throw out the
+      // cached data and proceed with the query at the new 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();
-    } else if (CacheInfo->Size > Loc.Size) {
-      // 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);
     }
 
     // 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();

lib/Transforms/Scalar/MemCpyOptimizer.cpp

for (const MemsetRange &Range : Ranges) {
     // Determine alignment
     unsigned Alignment = Range.Alignment;
     if (Alignment == 0) {
       Type *EltType =
         cast<PointerType>(StartPtr->getType())->getElementType();
       Alignment = DL.getABITypeAlignment(EltType);
     }
 
-    AMemSet =
-      Builder.CreateMemSet(StartPtr, ByteVal, Range.End-Range.Start, Alignment);
+    // Remember the debug location.
+    DebugLoc Loc;
+    if (!Range.TheStores.empty())
+      Loc = Range.TheStores[0]->getDebugLoc();
 
     DEBUG(dbgs() << "Replace stores:\n";
           for (Instruction *SI : Range.TheStores)
-            dbgs() << *SI << '\n';
-          dbgs() << "With: " << *AMemSet << '\n');
-
-    if (!Range.TheStores.empty())
-      AMemSet->setDebugLoc(Range.TheStores[0]->getDebugLoc());
+            dbgs() << *SI << '\n');
 
     // Zap all the stores.
     for (Instruction *SI : Range.TheStores) {
       MD->removeInstruction(SI);
       SI->eraseFromParent();
     }
+
+    // Create the memset after removing the stores, so that if there any cached
+    // non-local dependencies on the removed instructions, the cache entries
+    // are updated to "dirty" entries pointing below the memset, so subsequent
+    // queries include the memset.
+    AMemSet =
+      Builder.CreateMemSet(StartPtr, ByteVal, Range.End-Range.Start, Alignment);
+    if (!Range.TheStores.empty())
+      AMemSet->setDebugLoc(Loc);
+
+    DEBUG(dbgs() << "With: " << *AMemSet << '\n');
+
     ++NumMemSetInfer;
   }
 
   return AMemSet;
 }
 
 static unsigned findCommonAlignment(const DataLayout &DL, const StoreInst *SI,
                                      const LoadInst *LI) {

test/Transforms/MemCpyOpt/merge-into-memset.ll

+; RUN: opt < %s -memcpyopt -S | FileCheck %s
+; Update cached non-local dependence information when merging stores into memset.
+
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+
+; Don't delete the memcpy in %if.then, even though it depends on an instruction
+; which will be deleted.
+
+; CHECK-LABEL: @foo
+define void @foo(i1 %c, i8* %d, i8* %e, i8* %f) {
+entry:
+  %tmp = alloca [50 x i8], align 8
+  %tmp4 = bitcast [50 x i8]* %tmp to i8*
+  %tmp1 = getelementptr inbounds i8, i8* %tmp4, i64 1
+  call void @llvm.memset.p0i8.i64(i8* nonnull %d, i8 0, i64 10, i32 1, i1 false), !dbg !5
+  store i8 0, i8* %tmp4, align 8, !dbg !5
+; CHECK: call void @llvm.memset.p0i8.i64(i8* nonnull %d, i8 0, i64 10, i32 1, i1 false), !dbg !5
+  call void @llvm.memcpy.p0i8.p0i8.i64(i8* nonnull %tmp1, i8* nonnull %d, i64 10, i32 1, i1 false)
+  br i1 %c, label %if.then, label %exit
+
+if.then:
+; CHECK: if.then:
+; CHECK: call void @llvm.memcpy.p0i8.p0i8.i64(i8* %f, i8* nonnull %tmp4, i64 30, i32 8, i1 false)
+  call void @llvm.memcpy.p0i8.p0i8.i64(i8* %f, i8* nonnull %tmp4, i64 30, i32 8, i1 false)
+  br label %exit
+
+exit:
+  ret void
+}
+
+declare void @llvm.memcpy.p0i8.p0i8.i64(i8*, i8*, i64, i32, i1)
+declare void @llvm.memset.p0i8.i64(i8*, i8, i64, i32, i1)
+
+!llvm.dbg.cu = !{!0}
+!llvm.module.flags = !{!3, !4}
+
+!0 = distinct !DICompileUnit(language: DW_LANG_Rust, file: !1, isOptimized: false, runtimeVersion: 0, emissionKind: FullDebug, enums: !2)
+!1 = !DIFile(filename: "t.rs", directory: "/tmp")
+!2 = !{}
+!3 = !{i32 2, !"Dwarf Version", i32 4}
+!4 = !{i32 2, !"Debug Info Version", i32 3}
+!5 = !DILocation(line: 8, column: 5, scope: !6)
+!6 = distinct !DISubprogram(name: "bar", scope: !1, file: !1, line: 5, type: !7, isLocal: false, isDefinition: true, scopeLine: 5, flags: DIFlagPrototyped, isOptimized: false, unit: !0, variables: !2)
+!7 = !DISubroutineType(types: !8)
+!8 = !{null}

test/Transforms/MemCpyOpt/mixed-sizes.ll

+; RUN: opt < %s -memcpyopt -S | FileCheck %s
+; Handle memcpy-memcpy dependencies of differing sizes correctly.
+
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+
+; Don't delete the second memcpy, even though there's an earlier
+; memcpy with a larger size from the same address.
+
+; CHECK-LABEL: @foo
+define i32 @foo(i1 %z) {
+entry:
+  %a = alloca [10 x i32]
+  %s = alloca [10 x i32]
+  %0 = bitcast [10 x i32]* %a to i8*
+  %1 = bitcast [10 x i32]* %s to i8*
+  call void @llvm.memset.p0i8.i64(i8* nonnull %1, i8 0, i64 40, i32 16, i1 false)
+  %arrayidx = getelementptr inbounds [10 x i32], [10 x i32]* %a, i64 0, i64 0
+  store i32 1, i32* %arrayidx
+  %scevgep = getelementptr [10 x i32], [10 x i32]* %s, i64 0, i64 1
+  %scevgep7 = bitcast i32* %scevgep to i8*
+  br i1 %z, label %for.body3.lr.ph, label %for.inc7.1
+
+for.body3.lr.ph:                                  ; preds = %entry
+  call void @llvm.memcpy.p0i8.p0i8.i64(i8* %0, i8* %scevgep7, i64 17179869180, i32 4, i1 false)
+  br label %for.inc7.1
+
+for.inc7.1:
+; CHECK: for.inc7.1:
+  call void @llvm.memcpy.p0i8.p0i8.i64(i8* %0, i8* %scevgep7, i64 4, i32 4, i1 false)
+; CHECK: call void @llvm.memcpy.p0i8.p0i8.i64(i8* %0, i8* %scevgep7, i64 4, i32 4, i1 false)
+  %2 = load i32, i32* %arrayidx
+  ret i32 %2
+}
+
+declare void @llvm.memcpy.p0i8.p0i8.i64(i8*, i8*, i64, i32, i1)
+declare void @llvm.memset.p0i8.i64(i8*, i8, i64, i32, i1)