[RFC][GVN] Remove redundant load by GVN

[shiva0217]

Summary

Remove redundant load LI by GVN in following case:

lw      a0, Addr1 <- LItoSI
sw      a0, Addr2 <- SI
lw      a0, Addr1 <- LI

If LI and LItoSI load from the same address, the value load from LItoSI could propagate to LI even if Addr1 alias to Addr2.
Therefore, LI could eliminate by GVN in this case.

[• dberlin]

This isn't correct in the face of atomics and volatiles, and IMHO, MemoryDependence should not be performing this optimization.
If you want, teach GVN to requery MemDep in these cases.

[shiva0217]

In D44891#1048252, @dberlin wrote:

This isn't correct in the face of atomics and volatiles, and IMHO, MemoryDependence should not be performing this optimization.
If you want, teach GVN to requery MemDep in these cases.

Hi @dberlin.
The patch code will not apply when face atomics and volatiles due to MemoryDependence has atomic and volatile checking before entering this part.
It detects the case in the summary, and then MemDep will not clobber "LItoSI" load value by store and then GVN could remove "QueryInst" load by requiring MemDep.
So the patch will not perform optimization by itself, it will let GVN deal with it.

[• dberlin]

Sorry, again, i don't think this is a thing memdep should be doing.
If GVN can't handle this sanely, that's on GVN.
So i'm not going t approve this.

[shiva0217]

Hi @dberlin. Thanks for your comments. I update the patch as your suggestion.
Currently, I implement in GVN.cpp: GVN::AnalyzeLoadAvailability.
Is that the place you expect to implement?

[lebedev.ri]

lib/Transforms/Scalar/GVN.cpp

894

Missing test coverage

[shiva0217]

Update the test case to address @lebedev.ri 's comments.

[shiva0217]

Hi @dberlin. Sorry, I didn't get your point in the first place. I moved the implementation from MemDep to GVN. Could you help me to check that is there anything missing? Thanks again to point me to the right direction.

lib/Transforms/Scalar/GVN.cpp

if (StoreInst *DepSI = dyn_cast<StoreInst>(DepInfo.getInst())) {
           analyzeLoadFromClobberingStore(LI->getType(), Address, DepSI, DL);
         if (Offset != -1) {
           Res = AvailableValue::get(DepSI->getValueOperand(), Offset);
           return true;
         }
       }
     }
 
+    // To remove LI in following case:
+    //     load  a0, Addr1 <- LItoSI
+    //     store a0, Addr2 <- DepSI
+    //     load  a0, Addr1 <- LI
+    // If LI and LItoSI load from same address, the value load from LItoSI
+    // could propagate to LI even if Addr1 alias to Addr2.
+    if (StoreInst *DepSI = dyn_cast<StoreInst>(DepInfo.getInst())) {
+      if (Address && !LI->isAtomic() && !LI->isVolatile()) {
+        if (LoadInst *LItoSI = dyn_cast<LoadInst>(DepSI->getValueOperand())) {
+          if (!LItoSI->isAtomic() && !LItoSI->isVolatile() &&
+              (LItoSI->getPointerOperand() == LI->getPointerOperand() &&
+              (LItoSI != LI))) {
+            Res = AvailableValue::get(DepSI->getValueOperand(), 0);
+            return true;
+          }
+        }
+      }
+    }
+
     // Check to see if we have something like this:
     //    load i32* P
     //    load i8* (P+1)
     // if we have this, replace the later with an extraction from the former.
     if (LoadInst *DepLI = dyn_cast<LoadInst>(DepInfo.getInst())) {
       // If this is a clobber and L is the first instruction in its block, then
       // we have the first instruction in the entry block.
       // Can't forward from non-atomic to atomic without violating memory model.

test/Transforms/GVN/remove-redundant-load.ll

+; RUN: opt -S -memdep -gvn -basicaa < %s | FileCheck %s
+; CHECK-LABEL: @test(
+; CHECK: %1 = load i32, i32* %Addr1
+; CHECK: store i32 %1, i32* %Addr2
+; CHECK: ret i32 %1
+define i32 @test(i32* %Addr1, i32* %Addr2) {
+ %1 = load i32, i32* %Addr1
+ store i32 %1, i32* %Addr2
+ %2 = load i32, i32* %Addr1
+ ret i32 %2
+}
+
+; CHECK-LABEL: @test_atomic(
+; CHECK: %1 = load atomic i32, i32* %Addr1 unordered, align 4
+; CHECK: store i32 %1, i32* %Addr2
+; CHECK: %2 = load i32, i32* %Addr1
+; CHECK: ret i32 %2
+define i32 @test_atomic(i32* %Addr1, i32* %Addr2) {
+ %1 = load atomic i32, i32* %Addr1 unordered, align 4
+ store i32 %1, i32* %Addr2
+ %2 = load i32, i32* %Addr1
+ ret i32 %2
+}
+
+; CHECK-LABEL: @test_volatile(
+; CHECK: %1 = load volatile i32, i32* %Addr
+; CHECK: store i32 %1, i32* %Addr2
+; CHECK: %2 = load i32, i32* %Addr1
+; CHECK: ret i32 %2
+define i32 @test_volatile(i32* %Addr1, i32* %Addr2) {
+ %1 = load volatile i32, i32* %Addr1
+ store i32 %1, i32* %Addr2
+ %2 = load i32, i32* %Addr1
+ ret i32 %2
+}