[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 ↗

(On Diff #140195)

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/Analysis/MemoryDependenceAnalysis.cpp

if (StoreInst *SI = dyn_cast<StoreInst>(Inst)) {
       AliasResult R = AA.alias(StoreLoc, MemLoc);
 
       if (R == NoAlias)
         continue;
       if (R == MustAlias)
         return MemDepResult::getDef(Inst);
       if (isInvariantLoad)
         continue;
+
+      // To remove QueryInst in following case:
+      //        lw      a0, Addr1 <- LItoSI
+      //        sw      a0, Addr2 <- SI
+      //        lw      a0, Addr1 <- QueryInst
+      //
+      // Originally, QueryInst can't remove by GVN due to Addr1 may alias
+      // with Addr2.
+      // However, QueryInst and LItoSI load from same address, so even Addr1
+      // alias to Addr2,the value load from LItoSI could propagate to QueryInst.
+      // MemLoc is the load address of QueryInst.
+      // LoadLoc is the load address of LItoSI.
+      if (LoadInst *LItoSI = dyn_cast<LoadInst>(SI->getValueOperand())) {
+        MemoryLocation LoadLoc = MemoryLocation::get(LItoSI);
+        AliasResult R = AA.alias(LoadLoc, MemLoc);
+        if (R == MustAlias)
+          continue;
+      }
+
       return MemDepResult::getClobber(Inst);
     }
 
     // If this is an allocation, and if we know that the accessed pointer is to
     // the allocation, return Def.  This means that there is no dependence and
     // the access can be optimized based on that.  For example, a load could
     // turn into undef.  Note that we can bypass the allocation itself when
     // looking for a clobber in many cases; that's an alias property and is

test/Analysis/MemoryDependenceAnalysis/memdep-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
+}