[LICM & MemorySSA] Don't sink/hoist stores in the presence of ordered loads.

Summary:
Before this patch, if any Use existed in the loop, with a defining
access in the loop, we conservatively decide to not move the store.
What this approach was missing, is that ordered loads are not Uses, they're Defs
in MemorySSA. So, even when the clobbering walker does not find that
volatile load to interfere, we still cannot hoist a store past a
volatile load.
Resolves PR41140.

Reviewers: george.burgess.iv

Subscribers: sanjoy, jlebar, Prazek, llvm-commits

Tags: #llvm

Differential Revision: https://reviews.llvm.org/D59564

llvm-svn: 356588

2 files changed, 31 insertions, 27 deletions

diff --git a/llvm/lib/Transforms/Scalar/LICM.cpp b/llvm/lib/Transforms/Scalar/LICM.cpp
index 93ee25cbfb8..93f391ad013 100644
--- a/llvm/lib/Transforms/Scalar/LICM.cpp
+++ b/llvm/lib/Transforms/Scalar/LICM.cpp
@@ -1191,33 +1191,38 @@ bool llvm::canSinkOrHoistInst(Instruction &I, AAResults *AA, DominatorTree *DT,
     } else { // MSSAU
       if (isOnlyMemoryAccess(SI, CurLoop, MSSAU))
         return true;
-      if (*LicmMssaOptCounter < LicmMssaOptCap) {
+      // If there are more accesses than the Promotion cap, give up, we're not
+      // walking a list that long.
+      if (NoOfMemAccTooLarge)
+        return false;
+      // Check store only if there's still "quota" to check clobber.
+      if (*LicmMssaOptCounter >= LicmMssaOptCap)
+        return false;
+      // If there are interfering Uses (i.e. their defining access is in the
+      // loop), or ordered loads (stored as Defs!), don't move this store.
+      // Could do better here, but this is conservatively correct.
+      // TODO: Cache set of Uses on the first walk in runOnLoop, update when
+      // moving accesses. Can also extend to dominating uses.
+      for (auto *BB : CurLoop->getBlocks())
+        if (auto *Accesses = MSSA->getBlockAccesses(BB)) {
+          for (const auto &MA : *Accesses)
+            if (const auto *MU = dyn_cast<MemoryUse>(&MA)) {
+              auto *MD = MU->getDefiningAccess();
+              if (!MSSA->isLiveOnEntryDef(MD) &&
+                  CurLoop->contains(MD->getBlock()))
+                return false;
+            } else if (const auto *MD = dyn_cast<MemoryDef>(&MA))
+              if (auto *LI = dyn_cast<LoadInst>(MD->getMemoryInst())) {
+                assert(!LI->isUnordered() && "Expected unordered load");
+                return false;
+              }
+        }
+
         auto *Source = MSSA->getSkipSelfWalker()->getClobberingMemoryAccess(SI);
         (*LicmMssaOptCounter)++;
-        // If there are no clobbering Defs in the loop, we still need to check
-        // for interfering Uses. If there are more accesses than the Promotion
-        // cap, give up, we're not walking a list that long. Otherwise, walk the
-        // list, check each Use if it's optimized to an access outside the loop.
-        // If yes, store is safe to hoist. This is fairly restrictive, but
-        // conservatively correct.
-        // TODO: Cache set of Uses on the first walk in runOnLoop, update when
-        // moving accesses. Can also extend to dominating uses.
-        if ((!MSSA->isLiveOnEntryDef(Source) &&
-             CurLoop->contains(Source->getBlock())) ||
-            NoOfMemAccTooLarge)
-          return false;
-        for (auto *BB : CurLoop->getBlocks())
-          if (auto *Accesses = MSSA->getBlockAccesses(BB))
-            for (const auto &MA : *Accesses)
-              if (const auto *MU = dyn_cast<MemoryUse>(&MA)) {
-                auto *MD = MU->getDefiningAccess();
-                if (!MSSA->isLiveOnEntryDef(MD) &&
-                    CurLoop->contains(MD->getBlock()))
-                  return false;
-              }
-        return true;
-      }
-      return false;
+        // If there are no clobbering Defs in the loop, store is safe to hoist.
+        return MSSA->isLiveOnEntryDef(Source) ||
+               !CurLoop->contains(Source->getBlock());
     }
   }
 
diff --git a/llvm/test/Transforms/LICM/hoist-debuginvariant.ll b/llvm/test/Transforms/LICM/hoist-debuginvariant.ll
index 71aeb7549ce..6f851fb10b8 100644
--- a/llvm/test/Transforms/LICM/hoist-debuginvariant.ll
+++ b/llvm/test/Transforms/LICM/hoist-debuginvariant.ll
@@ -1,6 +1,6 @@
 ; RUN: opt < %s -licm -S | FileCheck %s
 ; RUN: opt < %s -strip-debug -licm -S | FileCheck %s
-; RUN: opt < %s -licm -enable-mssa-loop-dependency=true -verify-memoryssa -S | FileCheck %s --check-prefixes=CHECK,MSSA
+; RUN: opt < %s -licm -enable-mssa-loop-dependency=true -verify-memoryssa -S | FileCheck %s
 
 target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
 target triple = "x86_64-unknown-linux-gnu"
@@ -17,7 +17,6 @@ define void @fn1() !dbg !6 {
 ; CHECK-NEXT: [[_TMP2:%.*]] = load i32, i32* @a, align 4
 ; CHECK-NEXT: [[_TMP3:%.*]] = load i32, i32* @b, align 4
 ; CHECK-NEXT: [[_TMP4:%.*]] = sdiv i32 [[_TMP2]], [[_TMP3]]
-; MSSA-NEXT: store i32 [[_TMP4:%.*]], i32* @c, align 4
 ; CHECK-NEXT: br label [[BB3:%.*]]
 
   br label %bb3