GVN-hoist: fix store past load dependence analysis (PR30216)

[sebpop]

Summary

To hoist stores past loads, we used to search for potential
conflicting loads on the hoisting path by following a MemorySSA
def-def link from the store to be hoisted to the previous
defining memory access, and from there we followed the def-use
chains to all the uses that occur on the hoisting path. The
problem is that the def-def link may point to a store that does
not alias with the store to be hoisted, and so the loads that are
walked may not alias with the store to be hoisted, and even as in
the testcase of PR30216, the loads that may alias with the store
to be hoisted are not visited.

The current patch visits all loads on the path from the store to
be hoisted to the hoisting position and uses the alias analysis
to ask whether the store may alias the load. I was not able to
use the MemorySSA functionality to ask for whether load and
store are clobbered: I'm not sure which function to call, so I
used a call to AA->isNoAlias().

Store past store is still working as before using a MemorySSA
query: I added an extra test to pr30216.ll to make sure store
past store does not regress.

[gberry]

I ran into the lack of an interface for this query in MemorySSA as well in the EarlyCSE changes I was working on. I think what you want is to be able to call instructionClobbersQuery() since that knows about special intrinsics and meta-data as well.

[sebpop]

On Thu, Sep 15, 2016 at 11:11 AM, Daniel Berlin <[e-mail]> wrote:

Sadly, I think this will fail when the use-opt limit is hit.

What about committing the patch that I already sent:

The current patch visits all loads on the path from the store to
be hoisted to the hoisting position and uses the alias analysis
to ask whether the store may alias the load.

I think the patch is already quite efficient in terms of compile time
because we limit the hoist distance to avoid register pressure issues.
Because the number of instructions on the path is bounded, we
will also have the bounds on the number of alias questions asked.

Danny, is it okay to commit the patch as it is?

[• dberlin]

Fix these, otherwise looks fine

llvm/lib/Transforms/Scalar/GVNHoist.cpp

347

Rather than repeatedly call firstInBB, can't you just set a boolean when you hit OldPt?

351

Ditto. If it's the same BB, the before relationship is entirely controlled by whether you have hit NewPt or not.

[sebpop]

llvm/lib/Transforms/Scalar/GVNHoist.cpp

347

This assumes that "for (const MemoryAccess &MA : *Acc)" iterates through memory accesses in the same order as they appear in the instruction stream. If this property holds, I could replace the "continue" with a "break": there are no other mem accesses to check after OldPt.

351

Yes, for this one I can use a bool.

[sebpop]

Updated to address the comments from Danny.

[sebpop]

Added back the testcase that I missed to git add in the previous commit.

llvm/lib/Transforms/Scalar/GVNHoist.cpp

private:
   bool firstInBB(const Instruction *I1, const Instruction *I2) {
     assert (I1->getParent() == I2->getParent());
     unsigned I1DFS = DFSNumber.lookup(I1);
     unsigned I2DFS = DFSNumber.lookup(I2);
     assert (I1DFS && I2DFS);
     return I1DFS < I2DFS;
   }
 
-  // Return true when there are users of Def in BB.
-  bool hasMemoryUseOnPath(MemoryAccess *Def, const BasicBlock *BB,
-                          const Instruction *OldPt) {
-    const BasicBlock *DefBB = Def->getBlock();
+  // Return true when there are memory uses of Def in BB.
+  bool hasMemoryUseOnPath(const Instruction *NewPt, MemoryDef *Def, const BasicBlock *BB) {
+    const Instruction *OldPt = Def->getMemoryInst();
     const BasicBlock *OldBB = OldPt->getParent();
+    const BasicBlock *NewBB = NewPt->getParent();
 
-    for (User *U : Def->users())
-      if (auto *MU = dyn_cast<MemoryUse>(U)) {
-        // FIXME: MU->getBlock() does not get updated when we move the instruction.
-        BasicBlock *UBB = MU->getMemoryInst()->getParent();
-        // Only analyze uses in BB.
-        if (BB != UBB)
-          continue;
+    MemoryLocation DefLoc = MemoryLocation::get(OldPt);
+    const MemorySSA::AccessList *Acc = MSSA->getBlockAccesses(BB);
+    for (const MemoryAccess &MA : *Acc) {
+      auto *MU = dyn_cast<MemoryUse>(&MA);
+      if (!MU)
 
-        // A use in the same block as the Def is on the path.
-        if (UBB == DefBB) {
-          assert(MSSA->locallyDominates(Def, MU) && "def not dominating use");
-          return true;
-        }
+      // Do not check whether MU aliases Def when MU occurs after OldPt.
+      if (BB == OldBB && firstInBB(OldPt, MU->getMemoryInst()))
+        continue;
 
-        if (UBB != OldBB)
-          return true;
+      // Do not check whether MU aliases Def when MU occurs before NewPt.
+      if (BB == NewBB && firstInBB(MU->getMemoryInst(), NewPt))
+        continue;
 
-        // It is only harmful to hoist when the use is before OldPt.
-        if (firstInBB(MU->getMemoryInst(), OldPt))
-          return true;
-      }
+      if (!AA->isNoAlias(DefLoc, MemoryLocation::get(MU->getMemoryInst())))
 
     return false;
   }
 
   // Return true when there are exception handling or loads of memory Def
-  // between OldPt and NewPt.
+  // between Def and NewPt.  This function is only called for stores: Def is
+  // the MemoryDef of the store to be hoisted.
 
   // Decrement by 1 NBBsOnAllPaths for each block between HoistPt and BB, and
   // return true when the counter NBBsOnAllPaths reaces 0, except when it is
   // initialized to -1 which is unlimited.
-  bool hasEHOrLoadsOnPath(const Instruction *NewPt, const Instruction *OldPt,
-                          MemoryAccess *Def, int &NBBsOnAllPaths) {
+  bool hasEHOrLoadsOnPath(const Instruction *NewPt, MemoryDef *Def,
+                          int &NBBsOnAllPaths) {
     const BasicBlock *NewBB = NewPt->getParent();
-    const BasicBlock *OldBB = OldPt->getParent();
+    const BasicBlock *OldBB = Def->getBlock();
     assert(DT->dominates(NewBB, OldBB) && "invalid path");
-    assert(DT->dominates(Def->getBlock(), NewBB) &&
+    assert(DT->dominates(Def->getDefiningAccess()->getBlock(), NewBB) &&
            "def does not dominate new hoisting point");
 
     // Walk all basic blocks reachable in depth-first iteration on the inverse
     // CFG from OldBB to NewBB. These blocks are all the blocks that may be
     // executed between the execution of NewBB and OldBB. Hoisting an expression
     // from OldBB into NewBB has to be safe on all execution paths.
     for (auto I = idf_begin(OldBB), E = idf_end(OldBB); I != E;) {
       if (*I == NewBB) {
         // Stop traversal when reaching HoistPt.
         I.skipChildren();
         continue;
       }
 
       // Impossible to hoist with exceptions on the path.
       if (hasEH(*I))
         return true;
 
       // Check that we do not move a store past loads.
-      if (hasMemoryUseOnPath(Def, *I, OldPt))
+      if (hasMemoryUseOnPath(NewPt, Def, *I))
         return true;
 
       // Stop walk once the limit is reached.
       if (NBBsOnAllPaths == 0)
         return true;
 
       // -1 is unlimited number of blocks on all paths.
       if (NBBsOnAllPaths != -1)
bool safeToHoistLdSt(const Instruction *NewPt, const Instruction *OldPt,
     if (NewBB == DBB && !MSSA->isLiveOnEntryDef(D))
       if (auto *UD = dyn_cast<MemoryUseOrDef>(D))
         if (firstInBB(NewPt, UD->getMemoryInst()))
           // Cannot move the load or store to NewPt above its definition in D.
           return false;
 
     // Check for unsafe hoistings due to side effects.
     if (K == InsKind::Store) {
-      if (hasEHOrLoadsOnPath(NewPt, OldPt, D, NBBsOnAllPaths))
+      if (hasEHOrLoadsOnPath(NewPt, dyn_cast<MemoryDef>(U), NBBsOnAllPaths))
         return false;
     } else if (hasEHOnPath(NewBB, OldBB, NBBsOnAllPaths))
       return false;
 
     if (UBB == NewBB) {
       if (DT->properlyDominates(DBB, NewBB))
         return true;
       assert(UBB == DBB);

llvm/test/Transforms/GVN/pr28626.ll

-; RUN: opt -S -gvn-hoist < %s | FileCheck %s
-target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
-target triple = "x86_64-unknown-linux-gnu"
-
-define void @test1(i1 %a, i1** %d) {
-entry:
-  %0 = load i1*, i1** %d, align 8
-  br i1 %a, label %if.then, label %if.else
-
-if.then:                                          ; preds = %entry
-  br label %if.end
-
-if.else:                                          ; preds = %entry
-  br label %if.end
-
-if.end:                                           ; preds = %if.else, %if.then
-  %c.0 = phi i1 [ 1, %if.then ], [ 0, %if.else ]
-  br i1 %c.0, label %if.then2, label %if.else3
-
-if.then2:                                         ; preds = %if.end
-  %rc = getelementptr inbounds i1, i1* %0, i64 0
-  store i1 %c.0, i1* %rc, align 4
-  br label %if.end6
-
-if.else3:                                         ; preds = %if.end
-  %rc5 = getelementptr inbounds i1, i1* %0, i64 0
-  store i1 %c.0, i1* %rc5, align 4
-  br label %if.end6
-
-if.end6:                                          ; preds = %if.else3, %if.then2
-  ret void
-}
-
-; CHECK-LABEL: define void @test1(
-; CHECK:  %[[load:.*]] = load i1*, i1** %d, align 8
-; CHECK:  %[[phi:.*]] = phi i1 [ true, {{.*}} ], [ false, {{.*}} ]
-
-; CHECK: %[[gep0:.*]] = getelementptr inbounds i1, i1* %[[load]], i64 0
-; CHECK: store i1 %[[phi]], i1* %[[gep0]], align 4
-
-; Check that store instructions are hoisted.
-; CHECK-NOT: store
 

llvm/test/Transforms/GVNHoist/pr28626.ll

+; RUN: opt -S -gvn-hoist < %s | FileCheck %s
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+target triple = "x86_64-unknown-linux-gnu"
+
+define void @test1(i1 %a, i1** %d) {
+entry:
+  %0 = load i1*, i1** %d, align 8
+  br i1 %a, label %if.then, label %if.else
+
+if.then:                                          ; preds = %entry
+  br label %if.end
+
+if.else:                                          ; preds = %entry
+  br label %if.end
+
+if.end:                                           ; preds = %if.else, %if.then
+  %c.0 = phi i1 [ 1, %if.then ], [ 0, %if.else ]
+  br i1 %c.0, label %if.then2, label %if.else3
+
+if.then2:                                         ; preds = %if.end
+  %rc = getelementptr inbounds i1, i1* %0, i64 0
+  store i1 %c.0, i1* %rc, align 4
+  br label %if.end6
+
+if.else3:                                         ; preds = %if.end
+  %rc5 = getelementptr inbounds i1, i1* %0, i64 0
+  store i1 %c.0, i1* %rc5, align 4
+  br label %if.end6
+
+if.end6:                                          ; preds = %if.else3, %if.then2
+  ret void
+}
+
+; CHECK-LABEL: define void @test1(
+; CHECK:  %[[load:.*]] = load i1*, i1** %d, align 8
+; CHECK:  %[[phi:.*]] = phi i1 [ true, {{.*}} ], [ false, {{.*}} ]
+
+; CHECK: %[[gep0:.*]] = getelementptr inbounds i1, i1* %[[load]], i64 0
+; CHECK: store i1 %[[phi]], i1* %[[gep0]], align 4
+
+; Check that store instructions are hoisted.
+; CHECK-NOT: store
 No newline at end of file

llvm/test/Transforms/GVNHoist/pr30216.ll

+; RUN: opt -S -gvn-hoist < %s | FileCheck %s
+
+; Make sure the two stores @B do not get hoisted past the load @B.
+
+; CHECK-LABEL: define i8* @Foo
+; CHECK: store
+; CHECK: store
+; CHECK: load
+; CHECK: store
+
+@A = external global i8
+@B = external global i8*
+
+define i8* @Foo() {
+  store i8 0, i8* @A
+  br i1 undef, label %if.then, label %if.else
+
+if.then:
+  store i8* null, i8** @B
+  ret i8* null
+
+if.else:
+  %1 = load i8*, i8** @B
+  store i8* null, i8** @B
+  ret i8* %1
+}
+
+; Make sure the two stores @B do not get hoisted past the store @GlobalVar.
+
+; CHECK-LABEL: define i8* @Fun
+; CHECK: store
+; CHECK: store
+; CHECK: store
+; CHECK: store
+; CHECK: load
+
+@GlobalVar = internal global i8 0
+
+define i8* @Fun() {
+  store i8 0, i8* @A
+  br i1 undef, label %if.then, label %if.else
+
+if.then:
+  store i8* null, i8** @B
+  ret i8* null
+
+if.else:
+  store i8 0, i8* @GlobalVar
+  store i8* null, i8** @B
+  %1 = load i8*, i8** @B
+  ret i8* %1
+}