[GVN][AA][C++] Should we propagate equalities for noalias pointers?

IR & Optimizations
1

I came across a (possibly poorly written) C code and TOT LLVM is removing the stores in the else clause of the code.

A test case below (real code does some computation in if and an “in-place” version of the same computation in else):

void foo(const int * __restrict src,
         int * __restrict  dst) {
    if (src != dst)
        dst[0] = src[0];
    else
        dst[1] = src[0];
}

The problem is that GVN propagates the values from the equality src == dst, and replaces dst[1] = src[0] with src[1] = src[0].

Now we will have a store to src, which is noalias readonly, so instcombine will remove it at a later stage. Removing a store to constant pointer seems okay but I feel like GVN should not be propagating equalities for noalias pointers.

Not sure what language standard says about this but no other compiler (GCC,MSVC) is doing this.

Godbolt link: Compiler Explorer
Does doing something like this make sense?

diff --git a/llvm/lib/Transforms/Scalar/GVN.cpp b/llvm/lib/Transforms/Scalar/GVN.cpp
--- a/llvm/lib/Transforms/Scalar/GVN.cpp
+++ b/llvm/lib/Transforms/Scalar/GVN.cpp
@@ -2360,6 +2360,23 @@ bool GVNPass::propagateEquality(Value *LHS, Value *RHS,
     if (isa<Constant>(LHS) && isa<Constant>(RHS))
       continue;

+    // Don't try to propagate equalities for noalias pointers.
+    if (isa<PointerType>(LHS->getType()) &&
+        !getAliasAnalysis()->alias(LHS, RHS))
+      continue;

IR:

define void @foo(i32* noalias noundef readonly %src,
                 i32* noalias noundef writeonly %dst) {
entry:
  %cmp.not = icmp eq i32* %src, %dst
  br i1 %cmp.not, label %if.else, label %if.then

if.then:
  %0 = load i32, i32* %src, align 4
  store i32 %0, i32* %dst, align 4
  br label %if.end

if.else:
  %1 = load i32, i32* %src, align 4
  %arrayidx3 = getelementptr inbounds i32, i32* %dst, i32 1 ; <<<<<<<<<<<<---- gvn replaces dst with src
  store i32 %1, i32* %arrayidx3, align 4
  br label %if.end

if.end:
  ret void
}
2

The callee marked them as restrict pointers (llvm noalias) which is a promise that they do not point to the same address, so it seems that is all just dead code you are referring to

3

Looks like an instance of LLVM Memory Model needs more rigor to avoid undesired optimization results · Issue #34577 · llvm/llvm-project · GitHub . Your suggested solution is a bit hacky, but probably fine as an incremental step.

CC @aqjune @nlopes @fhahn @nikic

4

Hi,

I think we can update canReplacePointersIfEqual in llvm-project/Loads.h at main · llvm/llvm-project · GitHub to consider this case.
GVN is not using this function yet, so perhaps GVNPass::propagateEquality needs to be updated to call this as well.