LICM: Hoist LOAD without STORE

[djtodoro]

Summary

When doing load/store promotion within LICM, if we cannot prove that it is safe to sink the store we won't hoist the load, even though we can prove the load could be dereferenced and moved outside the loop. This patch implements the load promotion by moving it in the loop preheader by inserting proper PHI in the loop. The store is kept as is in the loop. By doing this, we avoid doing the load from a memory location in each iteration.

Please consider this small example:

loop {
  var = *ptr;
  if (var) break;
  *ptr= var + 1;
}

After this patch, it will be:

var0 = *ptr;
loop {
  var1 = phi (var0, var2);
  if (var1) break;
  var2 = var1 + 1;
  *ptr = var2;
}

This addresses some problems from [0].

[0] https://bugs.llvm.org/show_bug.cgi?id=51193

[lebedev.ri]

This seems to be in-line with our recent discussions about whether on not LICM is a general canonicalization pass,
or should it have target-specific configurations. @reames thoughts? (to be noted, this more applies to D113290, if it was done without a target hook it would not be a question)

[efriedma]

llvm/lib/Transforms/Scalar/LICM.cpp

2001

Maybe move this explanation to the definition of the variable "ShouldTryLoadHoistingOnly", since that's where it's relevant.

2300

Not sure I understand what you're doing with SavedInsts here.

If I'm following correctly, SavedInsts is empty the first time this is called from LoopInvariantCodeMotion::runOnLoop. On subsequent iterations, it contains the stores that correspond to loads that were optimized.

If you're trying to prevent an infinite loop, this isn't the way to do it; promoteLoopAccessesToScalars should just return false if there aren't any loads to promote. If you're just trying to save a little work in subsequent iterations, please leave it out for now; if there's actually some significant compile-time gain here, we can look into it as a followup.

llvm/test/Transforms/LICM/AArch64/hoist-load-without-store.ll

20 ↗

(On Diff #385082)

I'd like to see check lines for the PHI nodes.

Do we want any other tests here? Doesn't feel right to have just one test. I guess the cases where this transforms fails are generally covered by other tests, though, so not sure what we'd need to cover.

[lebedev.ri]

llvm/lib/Transforms/Scalar/LICM.cpp

120–125

This is really ambiguous to me. Is this talking about
*only* about hoisting loads, and preventing hoisting stores,
or hoisting loads even if we can't hoist the store?

[reames]

This needs much clearer motivation - specifically a clear explanation of what you're trying to achieve and why. Please consider that motivation blocking for further review.

[lebedev.ri]

In D113289#3135476, @reames wrote:

This needs much clearer motivation - specifically a clear explanation of what you're trying to achieve and why. Please consider that motivation blocking for further review.

FWIW, i think the general idea behind this is *really* important, "partial" mem2reg is still a win ; D113520 is somewhat related.

[djtodoro]

Thanks a lot for your comments!

In D113289#3135476, @reames wrote:

This needs much clearer motivation - specifically a clear explanation of what you're trying to achieve and why. Please consider that motivation blocking for further review.

I've updated the summary as a first step.

llvm/lib/Transforms/Scalar/LICM.cpp

120–125

Oh, I agree...

2001

Makes sense.

2300

Hmm, actually it doesn't improve anything, we should simply return false if there is no load to promote.

llvm/test/Transforms/LICM/AArch64/hoist-load-without-store.ll

20 ↗

(On Diff #385082)

The more tests the better. I'll try to make some other tests as well. As a starting point, I'll update the CHECKS for this one.

[djtodoro]

• Addressing comments
• Improving && reducing the test

[efriedma]

The new summary describing the optimization is a bit confusing to try to parse. I'd suggest splitting into three paragraphs:

1. What LLVM currently does on the testcase.
2. How the current patch changes the code generation, and why it's an improvement.
3. Potential future directions (fallow-store-data-races etc.)

[reames]

Ok, let me describe back to you what you're trying to do. Give a case like:

loop {
  a = *g;
  if (a) break;
  *g = a + 1
}

Where g is some loop invariant address, you want to produce a form which looks like this:

a0 = *g
loop {
  a1 = phi (a0, a2)
  if (a1) break;
  a2 = a1 + 1
  *g = a2;
}

Assuming I've correctly described that, I agree this is valuable. I'm honestly a bit shocked we didn't already handle it. However, this should absolutely not be target dependent. It should simply be always enabled.

llvm/lib/Transforms/Scalar/LICM.cpp

1863

Please name this CanInsertStoresInExitBlocks and invert the code appropriately.

2118

Please move this above the if block. Next to the SawAtomic/SawNotAtomic is a good place.

2215–2218

This block simplifies with the removal of the flag.

llvm/lib/Transforms/Utils/SSAUpdater.cpp

446

I see what you're doing here, but this is really ugly. I think we need to separate the set of uses being visited from the set of uses being *deleted*.

Please add a "shouldDelete(Inst)" callback on the LoadAndStorePromoter, default it to answering yes, then implement that in the sub-class. Still not great, but at least a bit better.

llvm/test/Transforms/LICM/AArch64/hoist-load-without-store.ll

31 ↗

(On Diff #388452)

Please use the simplest test possible. An IR form of my example from the review is probably good. You must strip all irrelevant IR details (e.g. metadata arguments, globals, etc..).

[djtodoro]

In D113289#3147618, @reames wrote:

Ok, let me describe back to you what you're trying to do. Give a case like:

loop {
  a = *g;
  if (a) break;
  *g = a + 1
}

Where g is some loop invariant address, you want to produce a form which looks like this:

a0 = *g
loop {
  a1 = phi (a0, a2)
  if (a1) break;
  a2 = a1 + 1
  *g = a2;
}

Yep, that's it!

Assuming I've correctly described that, I agree this is valuable. I'm honestly a bit shocked we didn't already handle it. However, this should absolutely not be target dependent. It should simply be always enabled.

Thanks! I totally agree, so I removed the flag and abandoned the second patch from the stack that was target-dependent.

[djtodoro]

• removed the option (so this is enabled always)
• reduced the test
• refactored the code a bit

[reames]

Heading in the right direction.

In addition to the inline comments, please update and simplify the submission comment. The comment should not explain the motivating workload (except maybe as a link to a bug), and should instead focus on explaining the effect of the transform. i.e. use a more minimal example, and explain *why* we're implementing the transform.

llvm/lib/Transforms/Scalar/LICM.cpp

1863

Comment is stale.

1952

The whole preserveduses mechanism seems like overkill. The preserveuses set should simply be every store in the use set when CanInstertStoreInExistingBlocks is false. If it's not, I'm missing something and we probably need some comments/tests.

2217

You've already proven dereferenceability (i.e. load legality) above. This check should be:
if (!SafeToInsertStore && !FoundLoadToPromote)

return false;

llvm/lib/Transforms/Utils/SSAUpdater.cpp

450

Drop isa<StoreInst> from this check. The shouldDelete interface should handle this.

[djtodoro]

In D113289#3152152, @reames wrote:

Heading in the right direction.

In addition to the inline comments, please update and simplify the submission comment. The comment should not explain the motivating workload (except maybe as a link to a bug), and should instead focus on explaining the effect of the transform. i.e. use a more minimal example, and explain *why* we're implementing the transform.

It makes sense to me.

llvm/lib/Transforms/Scalar/LICM.cpp

1952

Yes... I've had some tests failing due to some other reason, but this shouldn't have been included. Thanks.

[djtodoro]

• Simplify the code a bit
• Address comments

[reames]

LGTM w/required changes before submission.

llvm/include/llvm/Transforms/Utils/SSAUpdater.h

173

Make this comment generic.

e.g. Will return true if a sub-class wants to keep one of the loads or stores after SSA construction.

llvm/lib/Transforms/Scalar/LICM.cpp

469

Whitespace only change - please remove.

llvm/test/Transforms/LICM/scalar-promote.ll

2

Please autogen this in a separate commit, then rebase your change over it so that diff is visible in commit.

[djtodoro]

@reames Thanks a lot for the comments!

llvm/include/llvm/Transforms/Utils/SSAUpdater.h

173

Actually opposite, but it makes sense.

llvm/test/Transforms/LICM/scalar-promote.ll

2

Sure. @nikic already addressed that with eee035235eb.

[djtodoro]

• Update the llvm/test/Transforms/LICM/scalar-promote-opaque-ptrs.ll

@lebedev.ri is this ok to go as is?

[lebedev.ri]

llvm/test/Transforms/LICM/hoist-load-without-store.ll

1

I mean, can you just commit this test file first, with proper check lines,
so that they are only changed by the following patch?

[djtodoro]

llvm/test/Transforms/LICM/hoist-load-without-store.ll

1

Got it! Sure. I'll do that.

I thought you wanted to double check the new changes in the failing tests.

[nikic]

llvm/test/Transforms/LICM/scalar-promote.ll

312

Comment should probably be updated.

[djtodoro]

llvm/test/Transforms/LICM/scalar-promote.ll

312

I'll do that before commiting. Thanks!

[uabelho]

I wrote an issue about LICM behaving differently with/without debug information with this patch:
https://github.com/llvm/llvm-project/issues/55915

llvm/include/llvm/Transforms/Utils/SSAUpdater.h

public:
   /// a load is RAUW'd another value.
   virtual void replaceLoadWithValue(LoadInst *LI, Value *V) const {}
 
   /// Called before each instruction is deleted.
   virtual void instructionDeleted(Instruction *I) const {}
 
   /// Called to update debug info associated with the instruction.
   virtual void updateDebugInfo(Instruction *I) const {}
+
+  /// Return false if a sub-class wants to keep one of the loads/stores
+  /// after the SSA construction.
+  virtual bool shouldDelete(Instruction *I) const { return true; }
 };
 
 } // end namespace llvm
 
 #endif // LLVM_TRANSFORMS_UTILS_SSAUPDATER_H

llvm/lib/Transforms/Scalar/LICM.cpp

static cl::opt<unsigned> HoistSinkColdnessThreshold(
     cl::desc("Relative coldness Threshold of hoisting/sinking destination "
              "block for LICM to be considered beneficial"));
 
 static cl::opt<uint32_t> MaxNumUsesTraversed(
     "licm-max-num-uses-traversed", cl::Hidden, cl::init(8),
     cl::desc("Max num uses visited for identifying load "
              "invariance in loop using invariant start (default = 8)"));
 
 // Experimental option to allow imprecision in LICM in pathological cases, in
 // exchange for faster compile. This is to be removed if MemorySSA starts to
 // address the same issue. This flag applies only when LICM uses MemorySSA
 // instead on AliasSetTracker. LICM calls MemorySSAWalker's
 // getClobberingMemoryAccess, up to the value of the Cap, getting perfect
 // accuracy. Afterwards, LICM will call into MemorySSA's getDefiningAccess,
 // which may not be precise, since optimizeUses is capped. The result is
 // correct, but we may not get as "far up" as possible to get which access is
 // clobbering the one queried.
 cl::opt<unsigned> llvm::SetLicmMssaOptCap(
     "licm-mssa-optimization-cap", cl::init(100), cl::Hidden,
     cl::desc("Enable imprecision in LICM in pathological cases, in exchange "
              "for faster compile. Caps the MemorySSA clobbering calls."));
 
if (!HasCatchSwitch) {
       bool Promoted = false;
       bool LocalPromoted;
       do {
         LocalPromoted = false;
         for (const SmallSetVector<Value *, 8> &PointerMustAliases :
              collectPromotionCandidates(MSSA, AA, L)) {
           LocalPromoted |= promoteLoopAccessesToScalars(
               PointerMustAliases, ExitBlocks, InsertPts, MSSAInsertPts, PIC,
               LI, DT, TLI, L, &MSSAU, &SafetyInfo, ORE);
         }
         Promoted |= LocalPromoted;
       } while (LocalPromoted);
 
       // Once we have promoted values across the loop body we have to
       // recursively reform LCSSA as any nested loop may now have values defined
       // within the loop used in the outer loop.
       // FIXME: This is really heavy handed. It would be a bit better to use an
class LoopPromoter : public LoadAndStorePromoter {
   PredIteratorCache &PredCache;
   MemorySSAUpdater *MSSAU;
   LoopInfo &LI;
   DebugLoc DL;
   Align Alignment;
   bool UnorderedAtomic;
   AAMDNodes AATags;
   ICFLoopSafetyInfo &SafetyInfo;
+  bool CanInsertStoresInExitBlocks;
 
   // We're about to add a use of V in a loop exit block.  Insert an LCSSA phi
   // (if legal) if doing so would add an out-of-loop use to an instruction
   // defined in-loop.
   Value *maybeInsertLCSSAPHI(Value *V, BasicBlock *BB) const {
     if (!LI.wouldBeOutOfLoopUseRequiringLCSSA(V, BB))
       return V;
 

 public:
   LoopPromoter(Value *SP, ArrayRef<const Instruction *> Insts, SSAUpdater &S,
                const SmallSetVector<Value *, 8> &PMA,
                SmallVectorImpl<BasicBlock *> &LEB,
                SmallVectorImpl<Instruction *> &LIP,
                SmallVectorImpl<MemoryAccess *> &MSSAIP, PredIteratorCache &PIC,
                MemorySSAUpdater *MSSAU, LoopInfo &li, DebugLoc dl,
                Align Alignment, bool UnorderedAtomic, const AAMDNodes &AATags,
-               ICFLoopSafetyInfo &SafetyInfo)
+               ICFLoopSafetyInfo &SafetyInfo, bool CanInsertStoresInExitBlocks)
       : LoadAndStorePromoter(Insts, S), SomePtr(SP), PointerMustAliases(PMA),
         LoopExitBlocks(LEB), LoopInsertPts(LIP), MSSAInsertPts(MSSAIP),
         PredCache(PIC), MSSAU(MSSAU), LI(li), DL(std::move(dl)),
         Alignment(Alignment), UnorderedAtomic(UnorderedAtomic), AATags(AATags),
-        SafetyInfo(SafetyInfo) {}
+        SafetyInfo(SafetyInfo),
+        CanInsertStoresInExitBlocks(CanInsertStoresInExitBlocks) {}
 
   bool isInstInList(Instruction *I,
                     const SmallVectorImpl<Instruction *> &) const override {
     Value *Ptr;
     if (LoadInst *LI = dyn_cast<LoadInst>(I))
       Ptr = LI->getOperand(0);
     else
       Ptr = cast<StoreInst>(I)->getPointerOperand();
     return PointerMustAliases.count(Ptr);
   }
 
-  void doExtraRewritesBeforeFinalDeletion() override {
+  void insertStoresInLoopExitBlocks() {
     // Insert stores after in the loop exit blocks.  Each exit block gets a
     // store of the live-out values that feed them.  Since we've already told
     // the SSA updater about the defs in the loop and the preheader
     // definition, it is all set and we can start using it.
     for (unsigned i = 0, e = LoopExitBlocks.size(); i != e; ++i) {
       BasicBlock *ExitBlock = LoopExitBlocks[i];
       Value *LiveInValue = SSA.GetValueInMiddleOfBlock(ExitBlock);
       LiveInValue = maybeInsertLCSSAPHI(LiveInValue, ExitBlock);
for (unsigned i = 0, e = LoopExitBlocks.size(); i != e; ++i) {
             MSSAU->createMemoryAccessAfter(NewSI, nullptr, MSSAInsertPoint);
       }
       MSSAInsertPts[i] = NewMemAcc;
       MSSAU->insertDef(cast<MemoryDef>(NewMemAcc), true);
       // FIXME: true for safety, false may still be correct.
     }
   }
 
+  void doExtraRewritesBeforeFinalDeletion() override {
+    if (CanInsertStoresInExitBlocks)
+      insertStoresInLoopExitBlocks();
+  }
+
   void instructionDeleted(Instruction *I) const override {
     SafetyInfo.removeInstruction(I);
     MSSAU->removeMemoryAccess(I);
   }
+
+  bool shouldDelete(Instruction *I) const override {
+    if (isa<StoreInst>(I))
+      return CanInsertStoresInExitBlocks;
+    return true;
+  }
 };
 
 bool isNotCapturedBeforeOrInLoop(const Value *V, const Loop *L,
                                  DominatorTree *DT) {
   // We can perform the captured-before check against any instruction in the
   // loop header, as the loop header is reachable from any instruction inside
   // the loop.
   // TODO: ReturnCaptures=true shouldn't be necessary here.

 } // namespace
 
 /// Try to promote memory values to scalars by sinking stores out of the
 /// loop and moving loads to before the loop.  We do this by looping over
 /// the stores in the loop, looking for stores to Must pointers which are
 /// loop invariant.
 ///
 bool llvm::promoteLoopAccessesToScalars(
     const SmallSetVector<Value *, 8> &PointerMustAliases,
     SmallVectorImpl<BasicBlock *> &ExitBlocks,
     SmallVectorImpl<Instruction *> &InsertPts,
     SmallVectorImpl<MemoryAccess *> &MSSAInsertPts, PredIteratorCache &PIC,
     LoopInfo *LI, DominatorTree *DT, const TargetLibraryInfo *TLI,
     Loop *CurLoop, MemorySSAUpdater *MSSAU, ICFLoopSafetyInfo *SafetyInfo,
     OptimizationRemarkEmitter *ORE) {
   // Verify inputs.
   assert(LI != nullptr && DT != nullptr && CurLoop != nullptr &&
bool llvm::promoteLoopAccessesToScalars(
   // blocks is reached, the original dynamic path would have taken us through
   // the store, so inserting a store into the exit block is safe. Note that this
   // is different from the store being guaranteed to execute. For instance,
   // if an exception is thrown on the first iteration of the loop, the original
   // store is never executed, but the exit blocks are not executed either.
 
   bool DereferenceableInPH = false;
   bool SafeToInsertStore = false;
+  bool FoundLoadToPromote = false;
 
   SmallVector<Instruction *, 64> LoopUses;
 
   // We start with an alignment of one and try to find instructions that allow
   // us to prove better alignment.
   Align Alignment;
   // Keep track of which types of access we see
   bool SawUnorderedAtomic = false;
for (User *U : ASIV->users()) {
       // If there is an non-load/store instruction in the loop, we can't promote
       // it.
       if (LoadInst *Load = dyn_cast<LoadInst>(UI)) {
         if (!Load->isUnordered())
           return false;
 
         SawUnorderedAtomic |= Load->isAtomic();
         SawNotAtomic |= !Load->isAtomic();
+        FoundLoadToPromote = true;
 
         Align InstAlignment = Load->getAlign();
 
         // Note that proving a load safe to speculate requires proving
         // sufficient alignment at the target location.  Proving it guaranteed
         // to execute does as well.  Thus we can increase our guaranteed
         // alignment as well.
         if (!DereferenceableInPH || (InstAlignment > Alignment))
           if (isSafeToExecuteUnconditionally(*Load, DT, TLI, CurLoop,
                                              SafetyInfo, ORE,
                                              Preheader->getTerminator())) {
             DereferenceableInPH = true;
             Alignment = std::max(Alignment, InstAlignment);
           }
       } else if (const StoreInst *Store = dyn_cast<StoreInst>(UI)) {
         // Stores *of* the pointer are not interesting, only stores *to* the
         // pointer.
         if (UI->getOperand(1) != ASIV)
           continue;
         if (!Store->isUnordered())
           return false;
 
         SawUnorderedAtomic |= Store->isAtomic();
if (!SafeToInsertStore) {
     else {
       Value *Object = getUnderlyingObject(SomePtr);
       SafeToInsertStore =
           (isAllocLikeFn(Object, TLI) || isa<AllocaInst>(Object)) &&
           isNotCapturedBeforeOrInLoop(Object, CurLoop, DT);
     }
   }
 
-  // If we've still failed to prove we can sink the store, give up.
-  if (!SafeToInsertStore)
+  // If we've still failed to prove we can sink the store, hoist the load
+  // only, if possible.
+  if (!SafeToInsertStore && !FoundLoadToPromote)
+    // If we cannot hoist the load either, give up.
     return false;
 
-  // Otherwise, this is safe to promote, lets do it!
-  LLVM_DEBUG(dbgs() << "LICM: Promoting value stored to in loop: " << *SomePtr
+  // Lets do the promotion!
+  if (SafeToInsertStore)
+    LLVM_DEBUG(dbgs() << "LICM: Promoting load/store of the value: " << *SomePtr
                       << '\n');
+  else
+    LLVM_DEBUG(dbgs() << "LICM: Promoting load of the value: " << *SomePtr
+                      << '\n');
+
   ORE->emit([&]() {
     return OptimizationRemark(DEBUG_TYPE, "PromoteLoopAccessesToScalar",
                               LoopUses[0])
            << "Moving accesses to memory location out of the loop";
   });
   ++NumPromoted;
 
   // Look at all the loop uses, and try to merge their locations.
   std::vector<const DILocation *> LoopUsesLocs;
   for (auto U : LoopUses)
     LoopUsesLocs.push_back(U->getDebugLoc().get());
   auto DL = DebugLoc(DILocation::getMergedLocations(LoopUsesLocs));
 
   // We use the SSAUpdater interface to insert phi nodes as required.
   SmallVector<PHINode *, 16> NewPHIs;
   SSAUpdater SSA(&NewPHIs);
   LoopPromoter Promoter(SomePtr, LoopUses, SSA, PointerMustAliases, ExitBlocks,
                         InsertPts, MSSAInsertPts, PIC, MSSAU, *LI, DL,
-                        Alignment, SawUnorderedAtomic, AATags, *SafetyInfo);
+                        Alignment, SawUnorderedAtomic, AATags, *SafetyInfo,
+                        SafeToInsertStore);
 
   // Set up the preheader to have a definition of the value.  It is the live-out
   // value from the preheader that uses in the loop will use.
   LoadInst *PreheaderLoad = new LoadInst(
       AccessTy, SomePtr, SomePtr->getName() + ".promoted",
       Preheader->getTerminator());
   if (SawUnorderedAtomic)
     PreheaderLoad->setOrdering(AtomicOrdering::Unordered);

 static SmallVector<SmallSetVector<Value *, 8>, 0>
 collectPromotionCandidates(MemorySSA *MSSA, AliasAnalysis *AA, Loop *L) {
   AliasSetTracker AST(*AA);
 
   auto IsPotentiallyPromotable = [L](const Instruction *I) {
     if (const auto *SI = dyn_cast<StoreInst>(I))
       return L->isLoopInvariant(SI->getPointerOperand());
     if (const auto *LI = dyn_cast<LoadInst>(I))
       return L->isLoopInvariant(LI->getPointerOperand());
     return false;
   };
 
   // Populate AST with potentially promotable accesses and remove them from
   // MaybePromotable, so they will not be checked again on the next iteration.
   SmallPtrSet<Value *, 16> AttemptingPromotion;
   foreachMemoryAccess(MSSA, L, [&](Instruction *I) {
     if (IsPotentiallyPromotable(I)) {

llvm/lib/Transforms/Utils/SSAUpdater.cpp

for (LoadInst *ALoad : LiveInLoads) {
     if (NewVal == ALoad) NewVal = UndefValue::get(NewVal->getType());
     ALoad->replaceAllUsesWith(NewVal);
     ReplacedLoads[ALoad] = NewVal;
   }
 
   // Allow the client to do stuff before we start nuking things.
   doExtraRewritesBeforeFinalDeletion();
 
   // Now that everything is rewritten, delete the old instructions from the
   // function.  They should all be dead now.
   for (Instruction *User : Insts) {
+    if (!shouldDelete(User))
+      continue;
+
     // If this is a load that still has uses, then the load must have been added
     // as a live value in the SSAUpdate data structure for a block (e.g. because
     // the loaded value was stored later).  In this case, we need to recursively
     // propagate the updates until we get to the real value.
     if (!User->use_empty()) {
       Value *NewVal = ReplacedLoads[User];
       assert(NewVal && "not a replaced load?");
 

llvm/test/Transforms/InstMerge/st_sink_bugfix_22613.ll

 ; ModuleID = 'bug.c'
 target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
 target triple = "x86_64-unknown-linux-gnu"
 
 ; RUN: opt -O2 -S < %s | FileCheck %s
 
 ; CHECK-LABEL: main
-; CHECK: if.end
-; CHECK: store
 ; CHECK: memset
 ; CHECK: if.then
 ; CHECK: store
-; CHECK: memset
+; CHECK: if.end
+; CHECK: store
+; CHECK: store
 
 @d = common global i32 0, align 4
 @b = common global i32 0, align 4
 @f = common global [1 x [3 x i8]] zeroinitializer, align 1
 @e = common global i32 0, align 4
 @c = common global i32 0, align 4
 @a = common global i32 0, align 4
 

llvm/test/Transforms/LICM/hoist-load-without-store.ll

+; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
+; RUN: opt -licm -S < %s | FileCheck %s
+
+;; C reproducer:
+;; void f(int *ptr, int n) {
+;;   for (int i = 0; i < n; ++i) {
+;;     int x = *ptr;
+;;     if (x)
+;;       break;
+;;
+;;     *ptr = x + 1;
+;;   }
+;; }
+
+define dso_local void @f(i32* nocapture %ptr, i32 %n) {
+; CHECK-LABEL: @f(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[CMP7:%.*]] = icmp slt i32 0, [[N:%.*]]
+; CHECK-NEXT:    br i1 [[CMP7]], label [[FOR_BODY_LR_PH:%.*]], label [[CLEANUP1:%.*]]
+; CHECK:       for.body.lr.ph:
+; CHECK-NEXT:    [[PTR_PROMOTED:%.*]] = load i32, i32* [[PTR:%.*]], align 4
+; CHECK-NEXT:    br label [[FOR_BODY:%.*]]
+; CHECK:       for.body:
+; CHECK-NEXT:    [[TMP0:%.*]] = phi i32 [ [[PTR_PROMOTED]], [[FOR_BODY_LR_PH]] ], [ 1, [[IF_END:%.*]] ]
+; CHECK-NEXT:    [[I_08:%.*]] = phi i32 [ 0, [[FOR_BODY_LR_PH]] ], [ [[INC:%.*]], [[IF_END]] ]
+; CHECK-NEXT:    [[TOBOOL_NOT:%.*]] = icmp eq i32 [[TMP0]], 0
+; CHECK-NEXT:    br i1 [[TOBOOL_NOT]], label [[IF_END]], label [[FOR_BODY_CLEANUP1_CRIT_EDGE:%.*]]
+; CHECK:       if.end:
+; CHECK-NEXT:    store i32 1, i32* [[PTR]], align 4
+; CHECK-NEXT:    [[INC]] = add nuw nsw i32 [[I_08]], 1
+; CHECK-NEXT:    [[CMP:%.*]] = icmp slt i32 [[INC]], [[N]]
+; CHECK-NEXT:    br i1 [[CMP]], label [[FOR_BODY]], label [[FOR_COND_CLEANUP1_CRIT_EDGE:%.*]]
+; CHECK:       for.body.cleanup1_crit_edge:
+; CHECK-NEXT:    br label [[CLEANUP1]]
+; CHECK:       for.cond.cleanup1_crit_edge:
+; CHECK-NEXT:    br label [[CLEANUP1]]
+; CHECK:       cleanup1:
+; CHECK-NEXT:    ret void
+;
+entry:
+  %cmp7 = icmp slt i32 0, %n
+  br i1 %cmp7, label %for.body.lr.ph, label %cleanup1
+
+for.body.lr.ph:                                   ; preds = %entry
+  br label %for.body
+
+for.body:                                         ; preds = %for.body.lr.ph, %if.end
+  %i.08 = phi i32 [ 0, %for.body.lr.ph ], [ %inc, %if.end ]
+  %0 = load i32, i32* %ptr, align 4
+  %tobool.not = icmp eq i32 %0, 0
+  br i1 %tobool.not, label %if.end, label %for.body.cleanup1_crit_edge
+
+if.end:                                           ; preds = %for.body
+  store i32 1, i32* %ptr, align 4
+  %inc = add nuw nsw i32 %i.08, 1
+  %cmp = icmp slt i32 %inc, %n
+  br i1 %cmp, label %for.body, label %for.cond.cleanup1_crit_edge
+
+for.body.cleanup1_crit_edge:                      ; preds = %for.body
+  br label %cleanup1
+
+for.cond.cleanup1_crit_edge:                      ; preds = %if.end
+  br label %cleanup1
+
+cleanup1:                                         ; preds = %for.cond.cleanup1_crit_edge, %for.body.cleanup1_crit_edge, %entry
+  ret void
+}

llvm/test/Transforms/LICM/promote-capture.ll

 }
 
 define void @test_captured_before_loop(i32 %len) {
 ; CHECK-LABEL: @test_captured_before_loop(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[COUNT:%.*]] = alloca i32, align 4
 ; CHECK-NEXT:    store i32 0, i32* [[COUNT]], align 4
 ; CHECK-NEXT:    call void @capture(i32* [[COUNT]])
+; CHECK-NEXT:    [[COUNT_PROMOTED:%.*]] = load i32, i32* [[COUNT]], align 4
 ; CHECK-NEXT:    br label [[LOOP:%.*]]
 ; CHECK:       loop:
-; CHECK-NEXT:    [[I:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ [[I_NEXT:%.*]], [[LATCH:%.*]] ]
+; CHECK-NEXT:    [[C_INC2:%.*]] = phi i32 [ [[COUNT_PROMOTED]], [[ENTRY:%.*]] ], [ [[C_INC1:%.*]], [[LATCH:%.*]] ]
+; CHECK-NEXT:    [[I:%.*]] = phi i32 [ 0, [[ENTRY]] ], [ [[I_NEXT:%.*]], [[LATCH]] ]
 ; CHECK-NEXT:    [[COND:%.*]] = call i1 @cond(i32 [[I]])
 ; CHECK-NEXT:    br i1 [[COND]], label [[IF:%.*]], label [[LATCH]]
 ; CHECK:       if:
-; CHECK-NEXT:    [[C:%.*]] = load i32, i32* [[COUNT]], align 4
-; CHECK-NEXT:    [[C_INC:%.*]] = add i32 [[C]], 1
+; CHECK-NEXT:    [[C_INC:%.*]] = add i32 [[C_INC2]], 1
 ; CHECK-NEXT:    store i32 [[C_INC]], i32* [[COUNT]], align 4
 ; CHECK-NEXT:    br label [[LATCH]]
 ; CHECK:       latch:
+; CHECK-NEXT:    [[C_INC1]] = phi i32 [ [[C_INC]], [[IF]] ], [ [[C_INC2]], [[LOOP]] ]
 ; CHECK-NEXT:    [[I_NEXT]] = add nuw i32 [[I]], 1
 ; CHECK-NEXT:    [[CMP:%.*]] = icmp eq i32 [[I_NEXT]], [[LEN:%.*]]
 ; CHECK-NEXT:    br i1 [[CMP]], label [[EXIT:%.*]], label [[LOOP]]
 ; CHECK:       exit:
 ; CHECK-NEXT:    ret void
 ;
 entry:
   %count = alloca i32

llvm/test/Transforms/LICM/scalar-promote-memmodel.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt < %s -basic-aa -licm -S | FileCheck %s
 ; RUN: opt -aa-pipeline=tbaa,basic-aa -passes='require<aa>,require<targetir>,require<scalar-evolution>,require<opt-remark-emit>,loop-mssa(licm)' -S %s | FileCheck %s
 
 ; Make sure we don't hoist a conditionally-executed store out of the loop;
 ; it would violate the concurrency memory model
 
 @g = common global i32 0, align 4
 
 define void @bar(i32 %n, i32 %b) nounwind uwtable ssp {
 ; CHECK-LABEL: @bar(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[TOBOOL:%.*]] = icmp eq i32 [[B:%.*]], 0
+; CHECK-NEXT:    [[G_PROMOTED:%.*]] = load i32, i32* @g, align 4
 ; CHECK-NEXT:    br label [[FOR_COND:%.*]]
 ; CHECK:       for.cond:
-; CHECK-NEXT:    [[I_0:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ [[INC5:%.*]], [[FOR_INC:%.*]] ]
+; CHECK-NEXT:    [[INC2:%.*]] = phi i32 [ [[G_PROMOTED]], [[ENTRY:%.*]] ], [ [[INC1:%.*]], [[FOR_INC:%.*]] ]
+; CHECK-NEXT:    [[I_0:%.*]] = phi i32 [ 0, [[ENTRY]] ], [ [[INC5:%.*]], [[FOR_INC]] ]
 ; CHECK-NEXT:    [[CMP:%.*]] = icmp slt i32 [[I_0]], [[N:%.*]]
 ; CHECK-NEXT:    br i1 [[CMP]], label [[FOR_BODY:%.*]], label [[FOR_END:%.*]]
 ; CHECK:       for.body:
 ; CHECK-NEXT:    br i1 [[TOBOOL]], label [[FOR_INC]], label [[IF_THEN:%.*]]
 ; CHECK:       if.then:
-; CHECK-NEXT:    [[TMP3:%.*]] = load i32, i32* @g, align 4
-; CHECK-NEXT:    [[INC:%.*]] = add nsw i32 [[TMP3]], 1
+; CHECK-NEXT:    [[INC:%.*]] = add nsw i32 [[INC2]], 1
 ; CHECK-NEXT:    store i32 [[INC]], i32* @g, align 4
 ; CHECK-NEXT:    br label [[FOR_INC]]
 ; CHECK:       for.inc:
+; CHECK-NEXT:    [[INC1]] = phi i32 [ [[INC]], [[IF_THEN]] ], [ [[INC2]], [[FOR_BODY]] ]
 ; CHECK-NEXT:    [[INC5]] = add nsw i32 [[I_0]], 1
 ; CHECK-NEXT:    br label [[FOR_COND]]
 ; CHECK:       for.end:
 ; CHECK-NEXT:    ret void
 ;
 entry:
   br label %for.cond
 

llvm/test/Transforms/LICM/scalar-promote-opaque-ptrs.ll

 }
 
 ; Make sure we don't promote if the store is really control-flow dependent.
 define i32 @test7bad() {
 ; CHECK-LABEL: @test7bad(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[LOCAL:%.*]] = alloca i32, align 4
 ; CHECK-NEXT:    call void @capture(ptr [[LOCAL]])
+; CHECK-NEXT:    [[LOCAL_PROMOTED:%.*]] = load i32, ptr [[LOCAL]], align 4
 ; CHECK-NEXT:    br label [[LOOP:%.*]]
 ; CHECK:       loop:
-; CHECK-NEXT:    [[J:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ [[NEXT:%.*]], [[ELSE:%.*]] ]
-; CHECK-NEXT:    [[X:%.*]] = load i32, ptr [[LOCAL]], align 4
-; CHECK-NEXT:    [[X2:%.*]] = call i32 @opaque(i32 [[X]])
+; CHECK-NEXT:    [[X22:%.*]] = phi i32 [ [[LOCAL_PROMOTED]], [[ENTRY:%.*]] ], [ [[X21:%.*]], [[ELSE:%.*]] ]
+; CHECK-NEXT:    [[J:%.*]] = phi i32 [ 0, [[ENTRY]] ], [ [[NEXT:%.*]], [[ELSE]] ]
+; CHECK-NEXT:    [[X2:%.*]] = call i32 @opaque(i32 [[X22]])
 ; CHECK-NEXT:    [[CMP:%.*]] = icmp eq i32 [[X2]], 0
 ; CHECK-NEXT:    br i1 [[CMP]], label [[IF:%.*]], label [[ELSE]]
 ; CHECK:       if:
 ; CHECK-NEXT:    store i32 [[X2]], ptr [[LOCAL]], align 4
 ; CHECK-NEXT:    br label [[ELSE]]
 ; CHECK:       else:
+; CHECK-NEXT:    [[X21]] = phi i32 [ [[X2]], [[IF]] ], [ [[X22]], [[LOOP]] ]
 ; CHECK-NEXT:    [[NEXT]] = add i32 [[J]], 1
 ; CHECK-NEXT:    [[COND:%.*]] = icmp eq i32 [[NEXT]], 0
 ; CHECK-NEXT:    br i1 [[COND]], label [[EXIT:%.*]], label [[LOOP]]
 ; CHECK:       exit:
 ; CHECK-NEXT:    [[RET:%.*]] = load i32, ptr [[LOCAL]], align 4
 ; CHECK-NEXT:    ret i32 [[RET]]
 ;
 entry:

llvm/test/Transforms/LICM/scalar-promote.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt < %s -basic-aa -tbaa -licm -S | FileCheck %s
 ; RUN: opt -aa-pipeline=tbaa,basic-aa -passes='require<aa>,require<targetir>,require<scalar-evolution>,require<opt-remark-emit>,loop-mssa(licm)' -S %s | FileCheck %s
 target datalayout = "E-p:64:64:64-a0:0:8-f32:32:32-f64:64:64-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:32:64-v64:64:64-v128:128:128"
 
 @X = global i32 7   ; <i32*> [#uses=4]
 
 define void @test1(i32 %i) {
 ; CHECK-LABEL: @test1(
 ; CHECK-NEXT:  Entry:
loop:
   %cond = icmp eq i32 %next, 0
   br i1 %cond, label %exit, label %loop
 
 exit:
   %ret = load i32, i32* %local
   ret i32 %ret
 }
 
 ; Make sure we don't promote if the store is really control-flow dependent.
 define i32 @test7bad() {
 ; CHECK-LABEL: @test7bad(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[LOCAL:%.*]] = alloca i32, align 4
 ; CHECK-NEXT:    call void @capture(i32* [[LOCAL]])
+; CHECK-NEXT:    [[LOCAL_PROMOTED:%.*]] = load i32, i32* [[LOCAL]], align 4
 ; CHECK-NEXT:    br label [[LOOP:%.*]]
 ; CHECK:       loop:
-; CHECK-NEXT:    [[J:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ [[NEXT:%.*]], [[ELSE:%.*]] ]
-; CHECK-NEXT:    [[X:%.*]] = load i32, i32* [[LOCAL]], align 4
-; CHECK-NEXT:    [[X2:%.*]] = call i32 @opaque(i32 [[X]])
+; CHECK-NEXT:    [[X22:%.*]] = phi i32 [ [[LOCAL_PROMOTED]], [[ENTRY:%.*]] ], [ [[X21:%.*]], [[ELSE:%.*]] ]
+; CHECK-NEXT:    [[J:%.*]] = phi i32 [ 0, [[ENTRY]] ], [ [[NEXT:%.*]], [[ELSE]] ]
+; CHECK-NEXT:    [[X2:%.*]] = call i32 @opaque(i32 [[X22]])
 ; CHECK-NEXT:    [[CMP:%.*]] = icmp eq i32 [[X2]], 0
 ; CHECK-NEXT:    br i1 [[CMP]], label [[IF:%.*]], label [[ELSE]]
 ; CHECK:       if:
 ; CHECK-NEXT:    store i32 [[X2]], i32* [[LOCAL]], align 4
 ; CHECK-NEXT:    br label [[ELSE]]
 ; CHECK:       else:
+; CHECK-NEXT:    [[X21]] = phi i32 [ [[X2]], [[IF]] ], [ [[X22]], [[LOOP]] ]
 ; CHECK-NEXT:    [[NEXT]] = add i32 [[J]], 1
 ; CHECK-NEXT:    [[COND:%.*]] = icmp eq i32 [[NEXT]], 0
 ; CHECK-NEXT:    br i1 [[COND]], label [[EXIT:%.*]], label [[LOOP]]
 ; CHECK:       exit:
 ; CHECK-NEXT:    [[RET:%.*]] = load i32, i32* [[LOCAL]], align 4
 ; CHECK-NEXT:    ret i32 [[RET]]
 ;
 entry: