Allow value forwarding past release fences in GVN

[reames]

Summary

This is the GVN companion to http://reviews.llvm.org/D11434. See the description there for a higher level discussion of release fence semantics.

I *think* this patch is correct, but I would definitely appreciate really careful review. Because MDA is used by both GVN and DeadStoreElimination, I had to restrict the dependency bypass to only apply for loads. This feels like an utter hack, but we don't seem to have a meaningful return value for "reads but does not clobber". As a result, I need to return a clobber result for DSE, but skip this instruction for GVN. We have the same pattern in other places, but ... yuck.

[jfb]

test/Transforms/DeadStoreElimination/fence.ll

12 ↗

(On Diff #30414)

Same as in D11434: the second store can be eliminated because this is a race. You still need to store the second value, so it would be nice to have 5 and something else, and a comment that explains that you can but choose not to.

test/Transforms/GVN/fence.ll

42 ↗

(On Diff #30414)

It would be good to also explain that this is racy, but we choose to not exercise our optimization right. Putting a loop and having proper code here would defeat the optimizer, whereas this test is the most basic check that the optimizer is being nice.

[hfinkel]

test/Transforms/GVN/fence.ll

42 ↗

(On Diff #30414)

While I understand the value of small test cases, is it not simple to construct a non-racy test case?

[reames]

Given the associated EarlyCSE patch just landed, I plan to update this revision in the next few days. The source code won't change, but I plan to revise the tests slightly to try to avoid obvious races. Given I don't claim to be an expert in the intricacies of the C++ memory model, we'll see how successful I am.

[reames]

Revive an old review thread. The associated EarlyCSE change has landed and hasn't appeared to turn up any problems. I've tried to revise the test cases to be clear about what's going on and why.

[reames]

ping

[reames]

@JF - Can I get a review for this one? It came up again on a benchmark I'm looking at and I'd really like to get it in.

[jfb]

Two comments and then this is good. I'm much more comfortable testing that we're doing exactly what we think we are!

lib/Analysis/MemoryDependenceAnalysis.cpp

705 ↗

(On Diff #42206)

Typo: "isn't".

test/Transforms/DeadStoreElimination/fence.ll

13 ↗

(On Diff #42206)

I think this still applies. I'd like another test which does:

; CHECK: store i32 42
; CHECK: fence release
; CHECK: store i32 1
; CHECK: ret
  store i32 42, i32* %addr.i, align 4
  fence release
  store i32 1, i32* %addr.i, align 4
  ret void

I want the test to ensure that it's not just about the store value being the same at the same address, but also that the values being equal doesn't matter. If we decide to optimize further then the result would be:

; CHECK: store i32 1
; CHECK: fence release
; CHECK: ret

[reames]

Once comments are addressed (~20 minutes from now, waiting for build), do you want another round of review?

lib/Analysis/MemoryDependenceAnalysis.cpp

705 ↗

(On Diff #42206)

inst is instruction. I'll rephrase as:
"if the query instruction is a store."

test/Transforms/DeadStoreElimination/fence.ll

13 ↗

(On Diff #42206)

Will add this test and comment appropriately.

[jfb]

In D11436#383764, @reames wrote:

Once comments are addressed (~20 minutes from now, waiting for build), do you want another round of review?

No that's good.

lib/Analysis/MemoryDependenceAnalysis.cpp

705 ↗

(On Diff #42206)

Oops yes!

llvm/trunk/lib/Analysis/MemoryDependenceAnalysis.cpp

if (isa<AllocaInst>(Inst) || isNoAliasFn(Inst, &TLI)) {
       const Value *AccessPtr = GetUnderlyingObject(MemLoc.Ptr, DL);
       if (AccessPtr == Inst || AA.isMustAlias(Inst, AccessPtr))
         return MemDepResult::getDef(Inst);
     }
 
     if (isInvariantLoad)
       continue;
 
+    // A release fence requires that all stores complete before it, but does
+    // not prevent the reordering of following loads or stores 'before' the
+    // fence.  As a result, we look past it when finding a dependency for
+    // loads.  DSE uses this to find preceeding stores to delete and thus we
+    // can't bypass the fence if the query instruction is a store.
+    if (FenceInst *FI = dyn_cast<FenceInst>(Inst))
+      if (isLoad && FI->getOrdering() == Release)
+        continue;
+    
     // See if this instruction (e.g. a call or vaarg) mod/ref's the pointer.
     ModRefInfo MR = AA.getModRefInfo(Inst, MemLoc);
     // If necessary, perform additional analysis.
     if (MR == MRI_ModRef)
       MR = AA.callCapturesBefore(Inst, MemLoc, &DT, &OBB);
     switch (MR) {
     case MRI_NoModRef:
       // If the call has no effect on the queried pointer, just ignore it.

llvm/trunk/test/Transforms/DeadStoreElimination/fence.ll

+; RUN: opt -S -basicaa -dse < %s | FileCheck %s
+
+; We conservative choose to prevent dead store elimination
+; across release or stronger fences.  It's not required 
+; (since the must still be a race on %addd.i), but
+; it is conservatively correct.  A legal optimization
+; could hoist the second store above the fence, and then
+; DSE one of them.
+define void @test1(i32* %addr.i) {
+; CHECK-LABEL: @test1
+; CHECK: store i32 5
+; CHECK: fence
+; CHECK: store i32 5
+; CHECK: ret
+  store i32 5, i32* %addr.i, align 4
+  fence release
+  store i32 5, i32* %addr.i, align 4
+  ret void
+}
+
+; Same as previous, but with different values.  If we ever optimize 
+; this more aggressively, this allows us to check that the correct
+; store is retained (the 'i32 1' store in this case)
+define void @test1b(i32* %addr.i) {
+; CHECK-LABEL: @test1b
+; CHECK: store i32 42
+; CHECK: fence release
+; CHECK: store i32 1
+; CHECK: ret
+  store i32 42, i32* %addr.i, align 4
+  fence release
+  store i32 1, i32* %addr.i, align 4
+  ret void
+}
+
+; We *could* DSE across this fence, but don't.  No other thread can
+; observe the order of the acquire fence and the store.
+define void @test2(i32* %addr.i) {
+; CHECK-LABEL: @test2
+; CHECK: store
+; CHECK: fence
+; CHECK: store
+; CHECK: ret
+  store i32 5, i32* %addr.i, align 4
+  fence acquire
+  store i32 5, i32* %addr.i, align 4
+  ret void
+}

llvm/trunk/test/Transforms/GVN/fence.ll

+; RUN: opt -S -basicaa -gvn < %s | FileCheck %s
+
+; We can value forward across the fence since we can (semantically) 
+; reorder the following load before the fence.
+define i32 @test(i32* %addr.i) {
+; CHECK-LABEL: @test
+; CHECK: store
+; CHECK: fence
+; CHECK-NOT: load
+; CHECK: ret
+  store i32 5, i32* %addr.i, align 4
+  fence release
+  %a = load i32, i32* %addr.i, align 4
+  ret i32 %a
+}
+
+; Same as above
+define i32 @test2(i32* %addr.i) {
+; CHECK-LABEL: @test2
+; CHECK-NEXT: fence
+; CHECK-NOT: load
+; CHECK: ret
+  %a = load i32, i32* %addr.i, align 4
+  fence release
+  %a2 = load i32, i32* %addr.i, align 4
+  %res = sub i32 %a, %a2
+  ret i32 %res
+}
+
+; We can not value forward across an acquire barrier since we might
+; be syncronizing with another thread storing to the same variable
+; followed by a release fence.  This is not so much enforcing an
+; ordering property (though it is that too), but a liveness 
+; property.  We expect to eventually see the value of store by
+; another thread when spinning on that location.  
+define i32 @test3(i32* noalias %addr.i, i32* noalias %otheraddr) {
+; CHECK-LABEL: @test3
+; CHECK: load
+; CHECK: fence
+; CHECK: load
+; CHECK: ret i32 %res
+  ; the following code is intented to model the unrolling of
+  ; two iterations in a spin loop of the form:
+  ;   do { fence acquire: tmp = *%addr.i; ) while (!tmp);
+  ; It's hopefully clear that allowing PRE to turn this into:
+  ;   if (!*%addr.i) while(true) {} would be unfortunate
+  fence acquire
+  %a = load i32, i32* %addr.i, align 4
+  fence acquire
+  %a2 = load i32, i32* %addr.i, align 4
+  %res = sub i32 %a, %a2
+  ret i32 %res
+}
+
+; Another example of why forwarding across an acquire fence is problematic
+; can be seen in a normal locking operation.  Say we had:
+; *p = 5; unlock(l); lock(l); use(p);
+; forwarding the store to p would be invalid.  A reasonable implementation
+; of unlock and lock might be:
+; unlock() { atomicrmw sub %l, 1 unordered; fence release }
+; lock() { 
+;   do {
+;     %res = cmpxchg %p, 0, 1, monotonic monotonic
+;   } while(!%res.success)
+;   fence acquire;
+; }
+; Given we chose to forward across the release fence, we clearly can't forward
+; across the acquire fence as well.
+