[LICM&MSSA] Limit store hoisting.

[asbirlea]

Summary

If there is no clobbering access for a store inside the loop, that store
can only be hoisted if there are no interfearing loads.
A more general verification introduced here: there are no loads that are
not optimized to an access outside the loop.
Addresses PR40586.

[george.burgess.iv]

Thanks for this!

lib/Transforms/Scalar/LICM.cpp

121

I don't think that this will play nicely in threaded environments (ThinLTO?)

An alternative might be to stick it into LICM as a member, then pass it to canSinkOrHoistInst as a param, though I don't know this code well enough to say whether that's the best approach

1194

Why does optimizedness matter here? MemoryUses should always have valid defining accesses; I imagine that a valid-but-not-fully-optimal one would be good enough as long as it points outside of the loop

[asbirlea]

Address comments.

[asbirlea]

lib/Transforms/Scalar/LICM.cpp

121

Ack, passed as param (renamed for clarity of it's meaning).

1194

Indeed, removed.

[george.burgess.iv]

LGTM; thanks!

lib/Transforms/Scalar/LICM.cpp

 // (default), LICM calls MemorySSAWalker's getClobberingMemoryAccess, which
 // gets perfect accuracy. When flag is enabled, LICM will call into MemorySSA's
 // getDefiningAccess, which may not be precise, since optimizeUses is capped.
 static cl::opt<bool> EnableLicmCap(
     "enable-licm-cap", cl::init(false), cl::Hidden,
     cl::desc("Enable imprecision in LICM (uses MemorySSA cap) in "
              "pathological cases, in exchange for faster compile"));
 
+static bool LocalDisablePromotion = false;
+
 // Experimentally, memory promotion carries less importance than sinking and
 // hoisting. Limit when we do promotion when using MemorySSA, in order to save
 // compile time.
 static cl::opt<unsigned> AccessCapForMSSAPromotion(
     "max-acc-licm-promotion", cl::init(250), cl::Hidden,
     cl::desc("[LICM & MemorySSA] When MSSA in LICM is disabled, this has no "
              "effect. When MSSA in LICM is enabled, then this is the maximum "
              "number of accesses allowed to be present in a loop in order to "
bool LoopInvariantCodeMotion::runOnLoop(
     TargetLibraryInfo *TLI, TargetTransformInfo *TTI, ScalarEvolution *SE,
     MemorySSA *MSSA, OptimizationRemarkEmitter *ORE, bool DeleteAST) {
   bool Changed = false;
 
   assert(L->isLCSSAForm(*DT) && "Loop is not in LCSSA form.");
 
   std::unique_ptr<AliasSetTracker> CurAST;
   std::unique_ptr<MemorySSAUpdater> MSSAU;
-  bool LocalDisablePromotion = false;
+  LocalDisablePromotion = false;
+
   if (!MSSA) {
     LLVM_DEBUG(dbgs() << "LICM: Using Alias Set Tracker.\n");
     CurAST = collectAliasInfoForLoop(L, LI, AA);
   } else {
     LLVM_DEBUG(dbgs() << "LICM: Using MemorySSA.\n");
     MSSAU = make_unique<MemorySSAUpdater>(MSSA);
 
     unsigned AccessCapCount = 0;
if (CurAST) {
         return false;
       assert(UniqueI == SI && "AS must contain SI");
       return true;
     } else { // MSSAU
       if (isOnlyMemoryAccess(SI, CurLoop, MSSAU))
         return true;
       if (!EnableLicmCap) {
         auto *Source = MSSA->getSkipSelfWalker()->getClobberingMemoryAccess(SI);
-        if (MSSA->isLiveOnEntryDef(Source) ||
-            !CurLoop->contains(Source->getBlock()))
-          return true;
+        // 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())) || LocalDisablePromotion)
+          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)) {
+                if (!MU->isOptimized())
+                  return false;
+                auto *MD = MU->getDefiningAccess();
+                if (!MSSA->isLiveOnEntryDef(MD) &&
+                    CurLoop->contains(MD->getBlock()))
+                  return false;
+              }
       }
       return false;
     }
   }
 
   assert(!I.mayReadOrWriteMemory() && "unhandled aliasing");
 
   // We've established mechanical ability and aliasing, it's up to the caller

test/Transforms/LICM/store-hoisting.ll

-; RUN: opt -S -basicaa -licm %s | FileCheck %s
-; RUN: opt -aa-pipeline=basic-aa -passes='require<aa>,require<targetir>,require<scalar-evolution>,require<opt-remark-emit>,loop(licm)' < %s -S | FileCheck %s
+; RUN: opt -S -basicaa -licm %s | FileCheck -check-prefixes=CHECK,AST %s
+; RUN: opt -S -basicaa -licm -enable-mssa-loop-dependency=true %s | FileCheck  -check-prefixes=CHECK,MSSA %s
+; RUN: opt -aa-pipeline=basic-aa -passes='require<aa>,require<targetir>,require<scalar-evolution>,require<opt-remark-emit>,loop(licm)' < %s -S | FileCheck -check-prefixes=CHECK,AST %s
 
 define void @test(i32* %loc) {
 ; CHECK-LABEL: @test
 ; CHECK-LABEL: entry:
 ; CHECK: store i32 0, i32* %loc
 ; CHECK-LABEL: loop:
 entry:
   br label %loop

 exit1:
   ret void
 exit2:
   ret void
 }
 
 define i32* @false_negative_2use(i32* %loc) {
 ; CHECK-LABEL: @false_negative_2use
-; CHECK-LABEL: exit:
-; CHECK: store i32 0, i32* %loc
+; AST-LABEL: exit:
+; AST: store i32 0, i32* %loc
+; MSSA-LABEL: entry:
+; MSSA: store i32 0, i32* %loc
+; MSSA-LABEL: loop:
 entry:
   br label %loop
 
 loop:
   %iv = phi i32 [0, %entry], [%iv.next, %loop]
   store i32 0, i32* %loc
   %iv.next = add i32 %iv, 1
   %cmp = icmp slt i32 %iv, 200
loop:
   %iv.next = add i32 %iv, 1
   %cmp = icmp slt i32 %iv, 200
   br i1 %cmp, label %loop, label %exit
 
 exit:
   ret void
 }
 
+; Hoisting the store is actually valid here, as it dominates the load.
 define void @neg_ref(i32* %loc) {
 ; CHECK-LABEL: @neg_ref
 ; CHECK-LABEL: exit1:
 ; CHECK: store i32 0, i32* %loc
 ; CHECK-LABEL: exit2:
 ; CHECK: store i32 0, i32* %loc
 entry:
   br label %loop
backedge:
   br i1 %cmp, label %loop, label %exit2
 
 exit1:
   ret void
 exit2:
   ret void
 }
 
+; Hoisting the store here leads to a miscompile.
+define void @neg_ref2(i32* %loc) {
+; CHECK-LABEL: @neg_ref2
+; CHECK-LABEL: exit1:
+; CHECK: store i32 0, i32* %loc
+; CHECK-LABEL: exit2:
+; CHECK: store i32 0, i32* %loc
+entry:
+  store i32 198, i32* %loc
+  br label %loop
+
+loop:
+  %iv = phi i32 [0, %entry], [%iv.next, %backedge]
+  %v = load i32, i32* %loc
+  store i32 0, i32* %loc
+  %earlycnd = icmp eq i32 %v, 198
+  br i1 %earlycnd, label %exit1, label %backedge
+  
+backedge:
+  %iv.next = add i32 %iv, 1
+  %cmp = icmp slt i32 %iv, 200
+  br i1 %cmp, label %loop, label %exit2
+
+exit1:
+  ret void
+exit2:
+  ret void
+}
+
 declare void @modref()
 
 define void @neg_modref(i32* %loc) {
 ; CHECK-LABEL: @neg_modref
 ; CHECK-LABEL: loop:
 ; CHECK: store i32 0, i32* %loc
 ; CHECK-LABEL: exit:
 entry: