[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

1197

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).

1197

Indeed, removed.

[george.burgess.iv]

LGTM; thanks!

include/llvm/Transforms/Utils/LoopUtils.h

 /// uses before definitions, allowing us to sink a loop body in one pass without
 /// iteration. Takes DomTreeNode, AliasAnalysis, LoopInfo, DominatorTree,
 /// DataLayout, TargetLibraryInfo, Loop, AliasSet information for all
 /// instructions of the loop and loop safety information as
 /// arguments. Diagnostics is emitted via \p ORE. It returns changed status.
 bool sinkRegion(DomTreeNode *, AliasAnalysis *, LoopInfo *, DominatorTree *,
                 TargetLibraryInfo *, TargetTransformInfo *, Loop *,
                 AliasSetTracker *, MemorySSAUpdater *, ICFLoopSafetyInfo *,
-                OptimizationRemarkEmitter *ORE);
+                bool, OptimizationRemarkEmitter *);
 
 /// Walk the specified region of the CFG (defined by all blocks
 /// dominated by the specified block, and that are in the current loop) in depth
 /// first order w.r.t the DominatorTree.  This allows us to visit definitions
 /// before uses, allowing us to hoist a loop body in one pass without iteration.
 /// Takes DomTreeNode, AliasAnalysis, LoopInfo, DominatorTree, DataLayout,
 /// TargetLibraryInfo, Loop, AliasSet information for all instructions of the
 /// loop and loop safety information as arguments. Diagnostics is emitted via \p
 /// ORE. It returns changed status.
 bool hoistRegion(DomTreeNode *, AliasAnalysis *, LoopInfo *, DominatorTree *,
                  TargetLibraryInfo *, Loop *, AliasSetTracker *,
-                 MemorySSAUpdater *, ICFLoopSafetyInfo *,
-                 OptimizationRemarkEmitter *ORE);
+                 MemorySSAUpdater *, ICFLoopSafetyInfo *, bool,
+                 OptimizationRemarkEmitter *);
 
 /// This function deletes dead loops. The caller of this function needs to
 /// guarantee that the loop is infact dead.
 /// The function requires a bunch or prerequisites to be present:
 ///   - The loop needs to be in LCSSA form
 ///   - The loop needs to have a Preheader
 ///   - A unique dedicated exit block must exist
 ///

 /// \p TargetExecutesOncePerLoop is true only when it is guaranteed that the
 /// target executes at most once per execution of the loop body.  This is used
 /// to assess the legality of duplicating atomic loads.  Generally, this is
 /// true when moving out of loop and not true when moving into loops.
 /// If \p ORE is set use it to emit optimization remarks.
 bool canSinkOrHoistInst(Instruction &I, AAResults *AA, DominatorTree *DT,
                         Loop *CurLoop, AliasSetTracker *CurAST,
                         MemorySSAUpdater *MSSAU, bool TargetExecutesOncePerLoop,
+                        bool NoOfMemAccessesTooLarge,
                         OptimizationRemarkEmitter *ORE = nullptr);
 
 /// Returns a Min/Max operation corresponding to MinMaxRecurrenceKind.
 Value *createMinMaxOp(IRBuilder<> &Builder,
                       RecurrenceDescriptor::MinMaxRecurrenceKind RK,
                       Value *Left, Value *Right);
 
 /// Generates an ordered vector reduction using extracts to reduce the value.

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"));
 
 // 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 "
              "enable memory promotion."));
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;
+  bool NoOfMemAccTooLarge = 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;
     for (auto *BB : L->getBlocks()) {
       if (auto *Accesses = MSSA->getBlockAccesses(BB)) {
         for (const auto &MA : *Accesses) {
           (void)MA;
           AccessCapCount++;
           if (AccessCapCount > AccessCapForMSSAPromotion) {
-            LocalDisablePromotion = true;
+            NoOfMemAccTooLarge = true;
             break;
           }
         }
       }
-      if (LocalDisablePromotion)
+      if (NoOfMemAccTooLarge)
         break;
     }
   }
 
   // Get the preheader block to move instructions into...
   BasicBlock *Preheader = L->getLoopPreheader();
 
   // Compute loop safety information.
   ICFLoopSafetyInfo SafetyInfo(DT);
   SafetyInfo.computeLoopSafetyInfo(L);
 
   // We want to visit all of the instructions in this loop... that are not parts
   // of our subloops (they have already had their invariants hoisted out of
   // their loop, into this loop, so there is no need to process the BODIES of
   // the subloops).
   //
   // Traverse the body of the loop in depth first order on the dominator tree so
   // that we are guaranteed to see definitions before we see uses.  This allows
   // us to sink instructions in one pass, without iteration.  After sinking
   // instructions, we perform another pass to hoist them out of the loop.
   //
   if (L->hasDedicatedExits())
     Changed |= sinkRegion(DT->getNode(L->getHeader()), AA, LI, DT, TLI, TTI, L,
-                          CurAST.get(), MSSAU.get(), &SafetyInfo, ORE);
+                          CurAST.get(), MSSAU.get(), &SafetyInfo,
+                          NoOfMemAccTooLarge, ORE);
   if (Preheader)
     Changed |= hoistRegion(DT->getNode(L->getHeader()), AA, LI, DT, TLI, L,
-                           CurAST.get(), MSSAU.get(), &SafetyInfo, ORE);
+                           CurAST.get(), MSSAU.get(), &SafetyInfo,
+                           NoOfMemAccTooLarge, ORE);
 
   // Now that all loop invariants have been removed from the loop, promote any
   // memory references to scalars that we can.
   // Don't sink stores from loops without dedicated block exits. Exits
   // containing indirect branches are not transformed by loop simplify,
   // make sure we catch that. An additional load may be generated in the
   // preheader for SSA updater, so also avoid sinking when no preheader
   // is available.
   if (!DisablePromotion && Preheader && L->hasDedicatedExits() &&
-      !LocalDisablePromotion) {
+      !NoOfMemAccTooLarge) {
     // Figure out the loop exits and their insertion points
     SmallVector<BasicBlock *, 8> ExitBlocks;
     L->getUniqueExitBlocks(ExitBlocks);
 
     // We can't insert into a catchswitch.
     bool HasCatchSwitch = llvm::any_of(ExitBlocks, [](BasicBlock *Exit) {
       return isa<CatchSwitchInst>(Exit->getTerminator());
     });

 /// the specified block, and that are in the current loop) in reverse depth
 /// first order w.r.t the DominatorTree.  This allows us to visit uses before
 /// definitions, allowing us to sink a loop body in one pass without iteration.
 ///
 bool llvm::sinkRegion(DomTreeNode *N, AliasAnalysis *AA, LoopInfo *LI,
                       DominatorTree *DT, TargetLibraryInfo *TLI,
                       TargetTransformInfo *TTI, Loop *CurLoop,
                       AliasSetTracker *CurAST, MemorySSAUpdater *MSSAU,
-                      ICFLoopSafetyInfo *SafetyInfo,
+                      ICFLoopSafetyInfo *SafetyInfo, bool NoOfMemAccTooLarge,
                       OptimizationRemarkEmitter *ORE) {
 
   // Verify inputs.
   assert(N != nullptr && AA != nullptr && LI != nullptr && DT != nullptr &&
          CurLoop != nullptr && SafetyInfo != nullptr &&
          "Unexpected input to sinkRegion.");
   assert(((CurAST != nullptr) ^ (MSSAU != nullptr)) &&
          "Either AliasSetTracker or MemorySSA should be initialized.");
for (BasicBlock::iterator II = BB->end(); II != BB->begin();) {
 
       // Check to see if we can sink this instruction to the exit blocks
       // of the loop.  We can do this if the all users of the instruction are
       // outside of the loop.  In this case, it doesn't even matter if the
       // operands of the instruction are loop invariant.
       //
       bool FreeInLoop = false;
       if (isNotUsedOrFreeInLoop(I, CurLoop, SafetyInfo, TTI, FreeInLoop) &&
-          canSinkOrHoistInst(I, AA, DT, CurLoop, CurAST, MSSAU, true, ORE) &&
+          canSinkOrHoistInst(I, AA, DT, CurLoop, CurAST, MSSAU, true,
+                             NoOfMemAccTooLarge, ORE) &&
           !I.mayHaveSideEffects()) {
         if (sink(I, LI, DT, CurLoop, SafetyInfo, MSSAU, ORE, FreeInLoop)) {
           if (!FreeInLoop) {
             ++II;
             eraseInstruction(I, *SafetyInfo, CurAST, MSSAU);
           }
           Changed = true;
         }

 /// Walk the specified region of the CFG (defined by all blocks dominated by
 /// the specified block, and that are in the current loop) in depth first
 /// order w.r.t the DominatorTree.  This allows us to visit definitions before
 /// uses, allowing us to hoist a loop body in one pass without iteration.
 ///
 bool llvm::hoistRegion(DomTreeNode *N, AliasAnalysis *AA, LoopInfo *LI,
                        DominatorTree *DT, TargetLibraryInfo *TLI, Loop *CurLoop,
                        AliasSetTracker *CurAST, MemorySSAUpdater *MSSAU,
-                       ICFLoopSafetyInfo *SafetyInfo,
+                       ICFLoopSafetyInfo *SafetyInfo, bool NoOfMemAccTooLarge,
                        OptimizationRemarkEmitter *ORE) {
   // Verify inputs.
   assert(N != nullptr && AA != nullptr && LI != nullptr && DT != nullptr &&
          CurLoop != nullptr && SafetyInfo != nullptr &&
          "Unexpected input to hoistRegion.");
   assert(((CurAST != nullptr) ^ (MSSAU != nullptr)) &&
          "Either AliasSetTracker or MemorySSA should be initialized.");
 
for (BasicBlock::iterator II = BB->begin(), E = BB->end(); II != E;) {
 
       // Try hoisting the instruction out to the preheader.  We can only do
       // this if all of the operands of the instruction are loop invariant and
       // if it is safe to hoist the instruction.
       // TODO: It may be safe to hoist if we are hoisting to a conditional block
       // and we have accurately duplicated the control flow from the loop header
       // to that block.
       if (CurLoop->hasLoopInvariantOperands(&I) &&
-          canSinkOrHoistInst(I, AA, DT, CurLoop, CurAST, MSSAU, true, ORE) &&
+          canSinkOrHoistInst(I, AA, DT, CurLoop, CurAST, MSSAU, true,
+                             NoOfMemAccTooLarge, ORE) &&
           isSafeToExecuteUnconditionally(
               I, DT, CurLoop, SafetyInfo, ORE,
               CurLoop->getLoopPreheader()->getTerminator())) {
         hoist(I, DT, CurLoop, CFH.getOrCreateHoistedBlock(BB), SafetyInfo,
               MSSAU, ORE);
         HoistedInstructions.push_back(&I);
         Changed = true;
         continue;
bool isOnlyMemoryAccess(const Instruction *I, const Loop *L,
   return true;
 }
 }
 
 bool llvm::canSinkOrHoistInst(Instruction &I, AAResults *AA, DominatorTree *DT,
                               Loop *CurLoop, AliasSetTracker *CurAST,
                               MemorySSAUpdater *MSSAU,
                               bool TargetExecutesOncePerLoop,
+                              bool NoOfMemAccTooLarge,
                               OptimizationRemarkEmitter *ORE) {
   // If we don't understand the instruction, bail early.
   if (!isHoistableAndSinkableInst(I))
     return false;
 
   MemorySSA *MSSA = MSSAU ? MSSAU->getMemorySSA() : nullptr;
 
   // Loads have extra constraints we have to verify before we can hoist them.
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())) ||
+            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 false;
     }
   }
 
   assert(!I.mayReadOrWriteMemory() && "unhandled aliasing");
 
   // We've established mechanical ability and aliasing, it's up to the caller

lib/Transforms/Scalar/LoopSink.cpp

static bool sinkLoopInvariantInstructions(Loop &L, AAResults &AA, LoopInfo &LI,
   // Traverse preheader's instructions in reverse order becaue if A depends
   // on B (A appears after B), A needs to be sinked first before B can be
   // sinked.
   for (auto II = Preheader->rbegin(), E = Preheader->rend(); II != E;) {
     Instruction *I = &*II++;
     // No need to check for instruction's operands are loop invariant.
     assert(L.hasLoopInvariantOperands(I) &&
            "Insts in a loop's preheader should have loop invariant operands!");
-    if (!canSinkOrHoistInst(*I, &AA, &DT, &L, &CurAST, nullptr, false))
+    if (!canSinkOrHoistInst(*I, &AA, &DT, &L, &CurAST, nullptr, false, false))
       continue;
     if (sinkInstruction(L, *I, ColdLoopBBs, LoopBlockNumber, LI, DT, BFI))
       Changed = true;
   }
 
   if (Changed && SE)
     SE->forgetLoopDispositions(&L);
   return Changed;

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: