DSEPass incorrectly eliminates store to captured (and later read) pointer

[mhjacobson]

llvm v20.1.3
macOS "Big Sur" 11.7.10 (20G1427)

I have this code:

declare i32 @printf(i8* noalias readonly, ...)
@fmt = constant [6 x i8] c"%hhd\0a\00"

define ptr @makeValue(ptr %p) noinline optnone memory(none) {
  ret ptr %p
}

define void @useValue(ptr %value) noinline optnone memory(argmem: read) {
  %val = load i8, ptr %value
  call i32 @printf(ptr @fmt, i8 %val)
  ret void
}

define i32 @main() {
entry:
  %1 = alloca i8, align 4
  store i8 42, ptr %1
  %value = call i64 @makeValue(ptr %1)
  call void @useValue(i64 %value)
  ret i32 0
}

opt --passes=dse transforms @main() to (https://godbolt.org/z/rhx1z9K4W):

define i32 @main() {
entry:
  %0 = alloca i8, align 4
  %value = call i64 @makeValue(ptr %0)
  call void @useValue(i64 %value)
  ret i32 0
}

i.e., it eliminates the store to %1, even though %1 is captured by the call to @makeValue() and ultimately read in @useValue().

I believe the memory annotations on @makeValue() and @useValue() are legal. Note that the noinline optnone are just to prevent the optimizer from seeing into the contents of the function, equivalent to if the functions were simply declared and implemented in another module.

[mhjacobson]

This change fixes the problem for me, but I'm not suggesting it's definitely the proper fix.

The first part of the change is just to get the call to @makeValue() to produce a MemorySSA entry; the second part is the real meat of the change where we avoid DSE.

diff --git a/llvm/lib/Analysis/MemorySSA.cpp b/llvm/lib/Analysis/MemorySSA.cpp
index 1583e0e31efc..f8a9ce2a0473 100644
--- a/llvm/lib/Analysis/MemorySSA.cpp
+++ b/llvm/lib/Analysis/MemorySSA.cpp
@@ -1777,11 +1777,40 @@ MemoryUseOrDef *MemorySSA::createNewAccess(Instruction *I,
     }
   }
 
+  bool HasCaptureArg = false;
+#if 1
+  // For non-call instructions, if they neither read nor write, skip.
+  // For calls that do not access memory (memory(none)), model captures by pointer args.
+  if (auto *CB = dyn_cast<CallBase>(I)) {
+    // If this call is declared memory(none), only allow it through if it has
+    // a pointer argument without nocapture (i.e., it may capture).
+    if (CB->doesNotAccessMemory()) {
+      for (unsigned i = 0, e = CB->arg_size(); i != e; ++i) {
+        Value *Arg = CB->getArgOperand(i);
+
+        if (Arg->getType()->isPointerTy() &&
+            !CB->paramHasAttr(i, Attribute::NoCapture)) {
+          HasCaptureArg = true;
+          break;
+        }
+      }
+
+      if (!HasCaptureArg)
+        return nullptr;
+      // Otherwise let it through; we'll force a def below if AA indicates none.
+    }
+    // For calls that do access memory (readonly, readwrite, etc.), always model.
+  } else {
+    if (!I->mayReadFromMemory() && !I->mayWriteToMemory())
+      return nullptr;
+  }
+#else
   // Using a nonstandard AA pipelines might leave us with unexpected modref
   // results for I, so add a check to not model instructions that may not read
   // from or write to memory. This is necessary for correctness.
   if (!I->mayReadFromMemory() && !I->mayWriteToMemory())
     return nullptr;
+#endif
 
   bool Def, Use;
   if (Template) {
@@ -1813,7 +1842,7 @@ MemoryUseOrDef *MemorySSA::createNewAccess(Instruction *I,
     // we can precisely represent both "what memory will this read/write/is
     // clobbered by" and "what instructions can I move this past".
     Def = isModSet(ModRef) || isOrdered(I);
-    Use = isRefSet(ModRef);
+    Use = isRefSet(ModRef) || HasCaptureArg;
   }
 
   // It's possible for an instruction to not modify memory at all. During
diff --git a/llvm/lib/Transforms/Scalar/DeadStoreElimination.cpp b/llvm/lib/Transforms/Scalar/DeadStoreElimination.cpp
index 0fdc3354753b..f2facdd6e2c2 100644
--- a/llvm/lib/Transforms/Scalar/DeadStoreElimination.cpp
+++ b/llvm/lib/Transforms/Scalar/DeadStoreElimination.cpp
@@ -1367,6 +1367,19 @@ struct DSEState {
     if (auto SI = dyn_cast<StoreInst>(UseInst))
       return isStrongerThan(SI->getOrdering(), AtomicOrdering::Monotonic);
 
+    // Treat any call that captures a pointer arg as a read clobber.
+    if (auto *CB = dyn_cast<CallBase>(UseInst)) {
+      for (unsigned i = 0, e = CB->arg_size(); i != e; ++i) {
+        Value *Arg = CB->getArgOperand(i);
+
+        // Pointer arg without nocapture may alias the stored location.
+        if (Arg->getType()->isPointerTy() &&
+            !CB->paramHasAttr(i, Attribute::NoCapture)) {
+          return true;
+        }
+      }
+    }
+
     if (!UseInst->mayReadFromMemory())
       return false;
 

[dtcxzyw]

The signature of the callee is mismatched with the called function.
After fixing this problem, DSE works as expected: https://godbolt.org/z/WKj8ETqes

cc @nikic

[mhjacobson]

Apologies — I was trying out a bunch of variants of this (attempting to bisect it down from where I originally encountered it). I think this case is valid and still hits it: https://godbolt.org/z/nd6x4naqr

[dtcxzyw]

define void @useValue(i64 %value) noinline optnone memory(argmem: read) {
  %pointer = inttoptr i64 %value to ptr
  %val = load i8, ptr %pointer
  call i32 @printf(ptr @fmt, i8 %val)
  ret void
}

memory(argmem: read) indicates that the optimizer only takes pointer arguments into account. You should mark this function as memory(read). Otherwise, it is UB.

[mhjacobson]

I see! Looks like the relevant code is this:

    // Refine the modref info for argument memory. We only bother to do this
    // if ArgMR is not a subset of OtherMR, otherwise this won't have an impact
    // on the final result.
    ModRefInfo AllArgsMask = ModRefInfo::NoModRef;
    for (const auto &I : llvm::enumerate(Call->args())) {
      const Value *Arg = I.value();
      if (!Arg->getType()->isPointerTy())
        continue;
      unsigned ArgIdx = I.index();
      MemoryLocation ArgLoc = MemoryLocation::getForArgument(Call, ArgIdx, TLI);
      AliasResult ArgAlias = alias(ArgLoc, Loc, AAQI, Call);
      if (ArgAlias != AliasResult::NoAlias)
        AllArgsMask |= getArgModRefInfo(Call, ArgIdx);
    }
    ArgMR &= AllArgsMask;

In my frontend, I'm storing pointers in an aggregate type, which I then pass to @useValue(). Marking @useValue() as memory(read) seems harsh, since it really does only read objects derived from that aggregate.

However, I agree that LangRef does define argmem as "This refers to accesses that are based on pointer arguments to the function."

[dtcxzyw]

As suggested by https://llvm.org/docs/Frontend/PerformanceTips.html#other-things-to-consider, please avoid using ptrtoint/inttoptr in the IR. It is harmful to pointer aliasing/capturing analysis.

[mhjacobson]

I'm not actually using ptrtoint in my frontend — I'm using an aggregate, like this: https://godbolt.org/z/6PMKoh3dE (also gets DSEed).

I simplified it to an i64 while reducing the test case, but I gather it would reproduce for any type can capture a pointer into a non-pointer.