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

[asbirlea]

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.

[george.burgess.iv]

Thanks for this!

lib/Transforms/Scalar/LICM.cpp

1196 ↗

(On Diff #191397)

Is this bit relevant to PR41140? If not, please commit separately.

1213 ↗

(On Diff #191397)

nit: please fold the if into this, e.g. else if (const auto *MD = dyn_cast<MemoryDef>(&MA))

1215 ↗

(On Diff #191397)

please clang-format

1216 ↗

(On Diff #191397)

Should this be an assertion? Loads are only Defs if they're volatile or have >= some strength of atomic ordering

1224 ↗

(On Diff #191397)

nit: please fold this into the return: return MSSA->isLiveOnEntryDef(Source) || !CurLoop->contains(...);

[asbirlea]

Address comments.

[asbirlea]

lib/Transforms/Scalar/LICM.cpp

1196 ↗

(On Diff #191397)

This was in the previous code, and it's needed. I just refactored the code a bit, and moved this check before calling getClobbering to get an early exit.
Also inverted the OptCap check in the latest update to decrease indent.

[george.burgess.iv]

LGTM; thanks!

llvm/trunk/lib/Transforms/Scalar/LICM.cpp

if (CurAST) {
       if (!UniqueI)
         // other memory op, give up
         return false;
       assert(UniqueI == SI && "AS must contain SI");
       return true;
     } else { // MSSAU
       if (isOnlyMemoryAccess(SI, CurLoop, MSSAU))
         return true;
-      if (*LicmMssaOptCounter < LicmMssaOptCap) {
-        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;
+      // 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.
+        if (auto *Accesses = MSSA->getBlockAccesses(BB)) {
+            } 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;
               }
-        return true;
         }
-      return false;
+
+        auto *Source = MSSA->getSkipSelfWalker()->getClobberingMemoryAccess(SI);
+        (*LicmMssaOptCounter)++;
+        // If there are no clobbering Defs in the loop, store is safe to hoist.
+        return MSSA->isLiveOnEntryDef(Source) ||
+               !CurLoop->contains(Source->getBlock());
     }
   }
 
   assert(!I.mayReadOrWriteMemory() && "unhandled aliasing");
 
   // We've established mechanical ability and aliasing, it's up to the caller
   // to check fault safety
   return true;

llvm/trunk/test/Transforms/LICM/hoist-debuginvariant.ll

 ; 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"
 
 ; Verify that the sdiv is hoisted out of the loop
 ; even in the presence of a preceding debug intrinsic.
 
 @a = global i32 0
 @b = global i32 0
 @c = global i32 0
 
 define void @fn1() !dbg !6 {
 ; CHECK-LABEL: @fn1(
 ; 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
 
 bb3:                                              ; preds = %bb3, %0
   call void @llvm.dbg.value(metadata i32* @c, metadata !10, metadata !DIExpression(DW_OP_deref)), !dbg !12
   %_tmp2 = load i32, i32* @a, align 4
   %_tmp3 = load i32, i32* @b, align 4