[GVN] Introduce loop load PRE

[mkazantsev]

Summary

This patch allows PRE of the following type of loads:

preheader:
  br label %loop

loop:
  br i1 ..., label %merge, label %clobber

clobber:
  call foo() // Clobbers %p
  br label %merge

merge:
  ...
  br i1 ..., label %loop, label %exit

Into

preheader:
  %x0 = load %p
  br label %loop

loop:
  %x.pre = phi(x0, x2)
  br i1 ..., label %merge, label %clobber

clobber:
  call foo() // Clobbers %p
  %x1 = load %p
  br label %merge

merge:
  x2 = phi(x.pre, x1)
  ...
  br i1 ..., label %loop, label %exit

So instead of loading from %p on every iteration, we load only when the actual clobber happens.
The typical pattern which it is trying to address is: hot loop, with all code inlined and
provably having no side effects, and some side-effecting calls on cold path.

The worst overhead from it is, if we always take clobber block, we make 1 more load
overall (in preheader). It only matters if loop has very few iteration. If clobber block is not taken
at least once, the transform is neutral or profitable.

There are several improvements prospect open up:

• We can sometimes be smarter in loop-exiting blocks via split of critical edges;
• If we have block frequency info, we can handle multiple clobbers. The only obstacle now is that we don't know if their sum is colder than the header.

[reames]

Just for context, I'd explored a very similar transform before in https://reviews.llvm.org/D7061. One really key difference between the prior attempt and this one is that previously I hadn't explicitly handled loops and instead tried to match this from the original IR. I don't think loop info was available at the time. Though, looking at the current code, it looks like LoopInfo is optional for the pass even now.

One other key detail that has changed is we now support speculation, and don't necessarily have to prove anticipation (which the earlier change struggled with.)

In general, I think the new approach is much more likely to be successful than the original since we're solving a subset of the problems.

[reames]

Code structure wise, I want to suggest we don't try to shove this new transformation into the existing performLoadPRE codepath. Several of the concerns of that code (e.g. address translation) don't apply for the loop case, and you have at least one bug (whether we need to check speculation safety) because of trying to reuse the code.

I'd suggest instead that you split out the last third or so of that function into a helper which blindly performs the insertion, and replacement, and then implement a second performLoopLoadPRE entry which checks the appropriate legality for the new transform.

I also seriously question whether this is worth doing in old-GVN at all. The only infrastructure you actually need for this is memory aliasing and speculation safety. I'd seriously suggest writing a standalone pass which uses MemorySSA and ValueTracking, and maybe reuses the extracted helper function mentioned above.

[mkazantsev]

I'm pretty sure that availability problem you are referencing does not exist. See last 2 tests with guards.

As for refactoring, I'm going to do it. Putting WIP in the patch.

[mkazantsev]

Looking more into the code, I don't think that loop PRE needs any other legality checks than what we have now.

[mkazantsev]

Split code out into different method. Haven't figured out yet how to make it in a separate pass with MemorySSA, but I think having it in GVN won't harm.

[reames]

Comments inline include one serious correctness issue.

This is much cleaner than the original patch. I was initially hesitant to take this at all - as opposed to using MemorySSA or NewGVN - but with the new structure this looks a lot less invasive.

llvm/lib/Transforms/Scalar/GVN.cpp

1514

Extend this comment to emphasize that this means we have proven the load must execute if the loop is entered, and is thus safe to hoist to the end of the preheader without introducing a new fault. Similarly, the in-loop clobber must be dominated by the original load and is thus fault safe.

Er, hm, there's an issue here I just realized. This isn't sound. The counter example here is when the clobber is a call to free and the loop actually runs one iteration.

You need to prove that LI is safe to execute in both locations. You have multiple options in terms of reasoning, I'll let you decide which you want to explore: speculation safety, must execute, or unfreeable allocations. The last (using allocas as an example for test), might be the easiest.

1528

Tweak this comment a bit to emphasize that this ensures the new load executes at most as often as the original, and likely less often.

1533

I don't understand this restriction. Why is a switch not allowed?

1544

I don't think this loop does what you want, except maybe by accident. You allowed blocks outside the loop, as a result, you can end up with a bunch of available addresses and a bunch of loads before the preheader. This will likely later be DCEd since the preheader load will be the one actually used by SSA gen.

I strongly suspect you want exactly two available load locations: preheader, and your one in-loop clobber block.

[mkazantsev]

llvm/lib/Transforms/Scalar/GVN.cpp

1514

Free on the last iteration (the loop may have multiple though) is a nasty case indeed...

1533

This was ogirinally the protection against invokes. Switch is allowed, will fix.

1544

Yes, this check was lost during the refactoring. I'm pretty sure that eliminatePartiallyRedundantLoad will deal with it correctly, but it's at least not obvious. Thanks for catching.

[mkazantsev]

Addressed comments, fixed bug with

[mkazantsev]

I'm planning to add support for pointers basing on D99135, maybe as follow-up or on top of this.

[reames]

Looks close to ready for an LGTM if you're willing to split patch as suggested.

llvm/lib/Transforms/Scalar/GVN.cpp

1544

continue the comment with something like:
"because we need a place to insert a copy of the load".

p.s. I'm fine with this in an initial patch, but you really should be using an alias check here as the trailing invoke might not alias the memory being PREed. Would make a good follow up patch.

1563

You can generalize the first check as !LoadPtr->canBeFreed()

1564

This last check is incorrect. Counter example:
for (i = 0; i < 1; i++)

v = o.f
if (c) {
  // this is loop block
  clobber();
}
atomic store g = o;
while(wait for other thread to free) {}

}

Can I ask you to pull this into a separate patch? (e.g. handle only the first two cases in this patch, and come back to the third in a follow on.)

1567

Style: hasFnAttribute(AttributeKind::NoFree) handles both of these cases. (Or will once D100226 lands).

[mkazantsev]

Reused canBeFreed.

Removed code related to nofree analysis for further follow-up.

Improved comments.

llvm/lib/Transforms/Scalar/GVN.cpp

1564

Good idea. Removed from this patch, need to make it more carefully.

1567

Removed.

[reames]

LGTM w/minor comments.

llvm/lib/Transforms/Scalar/GVN.cpp

1515

Type: In order

1559

In a follow up, please generalize by using stripping bitcasts and inbounds geps before calling canBeFreed. Please don't do this in the change being lgtmed now.

llvm/test/Transforms/GVN/PRE/pre-loop-load.ll

8–9

Please add a positive test (analogous to this one), but using an alloca.

[nikic]

llvm/lib/Transforms/Scalar/GVN.cpp

1565

Where do we check that LoadPtr is loop invariant (and thus available in preheader)?

llvm/test/Transforms/GVN/PRE/pre-loop-load.ll

45–46

This test looks broken. I think for it to do something useful you'll want to pass %p to may_free_memory (or another function). Otherwise the load is just undef and there is no clobber in the loop either.

[reames]

LGTM withdrawn due to issue noticed by Nikita. Please address and refresh.

llvm/lib/Transforms/Scalar/GVN.cpp

1565

Er good question, and good catch. I remember this being here, but maybe it got lost in rebase.

Max, please add back the check, and a test which would have caught this.

[mkazantsev]

llvm/lib/Transforms/Scalar/GVN.cpp

1565

Wow, I was sure it was there. Thanks for catching!

[mkazantsev]

Added loop invariant check. Test added as underlying patch.

[mkazantsev]

Typo fix

[mkazantsev]

llvm/lib/Transforms/Scalar/GVN.cpp

1559

Shouldn't it be a part of canBeFreed?

[reames]

LGTM

llvm/lib/Transforms/Scalar/GVN.cpp

 
 using namespace llvm;
 using namespace llvm::gvn;
 using namespace llvm::VNCoercion;
 using namespace PatternMatch;
 
 #define DEBUG_TYPE "gvn"
 
-STATISTIC(NumGVNInstr,  "Number of instructions deleted");
-STATISTIC(NumGVNLoad,   "Number of loads deleted");
-STATISTIC(NumGVNPRE,    "Number of instructions PRE'd");
-STATISTIC(NumGVNBlocks, "Number of blocks merged");
-STATISTIC(NumGVNSimpl,  "Number of instructions simplified");
-STATISTIC(NumGVNEqProp, "Number of equalities propagated");
-STATISTIC(NumPRELoad,   "Number of loads PRE'd");
+STATISTIC(NumGVNInstr,    "Number of instructions deleted");
+STATISTIC(NumGVNLoad,     "Number of loads deleted");
+STATISTIC(NumGVNPRE,      "Number of instructions PRE'd");
+STATISTIC(NumGVNBlocks,   "Number of blocks merged");
+STATISTIC(NumGVNSimpl,    "Number of instructions simplified");
+STATISTIC(NumGVNEqProp,   "Number of equalities propagated");
+STATISTIC(NumPRELoad,     "Number of loads PRE'd");
+STATISTIC(NumPRELoopLoad, "Number of loop loads PRE'd");
 
 STATISTIC(IsValueFullyAvailableInBlockNumSpeculationsMax,
           "Number of blocks speculated as available in "
           "IsValueFullyAvailableInBlock(), max");
 STATISTIC(MaxBBSpeculationCutoffReachedTimes,
           "Number of times we we reached gvn-max-block-speculations cut-off "
           "preventing further exploration");
 
bool GVN::PerformLoadPRE(LoadInst *Load, AvailValInBlkVect &ValuesPerBlock,
   // available.
   MapVector<BasicBlock *, Value *> PredLoads;
   DenseMap<BasicBlock *, AvailabilityState> FullyAvailableBlocks;
   for (const AvailableValueInBlock &AV : ValuesPerBlock)
     FullyAvailableBlocks[AV.BB] = AvailabilityState::Available;
   for (BasicBlock *UnavailableBB : UnavailableBlocks)
     FullyAvailableBlocks[UnavailableBB] = AvailabilityState::Unavailable;
 
+  SmallVector<BasicBlock *, 4> BlocksToProcess;
+  auto *L = LI ? LI->getLoopFor(LoadBB) : nullptr;
+  // If we are dealing with a load in loop in a block that executes on every
+  // iteration (such as loop header block), and its clobber does not execute on
+  // every loop iteration, we can perform PRE of this load to make it only if
+  // clobber has happened.
+  bool LoopLoadPRE = !Blockers.count(LoadBB) && L && L->getHeader() == LoadBB &&
+                     L->getLoopPreheader() && L->getLoopLatch();
+  // Non-invariant pointer won't be available in preheader.
+  if (LoopLoadPRE)
+    LoopLoadPRE = L->isLoopInvariant(Load->getPointerOperand());
+  // Make sure we are not PRE'ing into inner loops.
+  // TODO: We could actually, if we can block frequency info. Inner loop still
+  // may be colder than the header of outer loop if it executes on cold path.
+  if (LoopLoadPRE)
+    LoopLoadPRE = all_of(Blockers, [&](const BasicBlock *Blocker) {
+      return !L->contains(Blocker) ||
+             (LI->getLoopFor(Blocker) == L &&
+              !DT->dominates(Blocker, L->getLoopLatch()));
+    });
+
+  if (LoopLoadPRE) {
+    for (auto *BB : Blockers)
+      if (L->contains(BB))
+        BlocksToProcess.push_back(BB);
+    BlocksToProcess.push_back(L->getLoopPreheader());
+  } else {
+    for (auto *BB : predecessors(LoadBB))
+      BlocksToProcess.push_back(BB);
+  }
+
   SmallVector<BasicBlock *, 4> CriticalEdgePred;
-  for (BasicBlock *Pred : predecessors(LoadBB)) {
+  for (BasicBlock *Pred : BlocksToProcess) {
     // If any predecessor block is an EH pad that does not allow non-PHI
     // instructions before the terminator, we can't PRE the load.
     if (Pred->getTerminator()->isEHPad()) {
       LLVM_DEBUG(
           dbgs() << "COULD NOT PRE LOAD BECAUSE OF AN EH PAD PREDECESSOR '"
                  << Pred->getName() << "': " << *Load << '\n');
       return false;
     }
if (Pred->getTerminator()->getNumSuccessors() != 1) {
 
       if (LoadBB->isEHPad()) {
         LLVM_DEBUG(
             dbgs() << "COULD NOT PRE LOAD BECAUSE OF AN EH PAD CRITICAL EDGE '"
                    << Pred->getName() << "': " << *Load << '\n');
         return false;
       }
 
+      // FIXME: Implement critical edge splitting for loop mode. So far, we only
+      // insert loads in the blocks where they invalidate. We can support
+      // invokes when this is done.
+      if (LoopLoadPRE) {
+        if (isa<InvokeInst>(Pred->getTerminator())) {
+          LLVM_DEBUG(
+              dbgs() << "COULD NOT PRE LOAD BECAUSE OF INVOKE CRITICAL EDGE '"
+                     << Pred->getName() << "': " << *Load << '\n');
+          return false;
+        }
+        PredLoads[Pred] = nullptr;
+      } else {
         // Do not split backedge as it will break the canonical loop form.
-      if (!isLoadPRESplitBackedgeEnabled())
+        if (!isLoadPRESplitBackedgeEnabled()) {
           if (DT->dominates(LoadBB, Pred)) {
             LLVM_DEBUG(
                 dbgs()
                 << "COULD NOT PRE LOAD BECAUSE OF A BACKEDGE CRITICAL EDGE '"
                 << Pred->getName() << "': " << *Load << '\n');
             return false;
           }
-
+        }
         CriticalEdgePred.push_back(Pred);
+      }
     } else {
       // Only add the predecessors that will not be split for now.
       PredLoads[Pred] = nullptr;
     }
   }
 
   // Decide whether PRE is profitable for this load.
   unsigned NumUnavailablePreds = PredLoads.size() + CriticalEdgePred.size();
   assert(NumUnavailablePreds != 0 &&
          "Fully available value should already be eliminated!");
 
   // If this load is unavailable in multiple predecessors, reject it.
   // FIXME: If we could restructure the CFG, we could make a common pred with
   // all the preds that don't have an available Load and insert a new load into
   // that one block.
-  if (NumUnavailablePreds != 1)
+  // FIXME: For loop mode, we could not restrain ourselves by the number of
+  // in-loop clobbers. If the sum of their frequencies is less than the
+  // frequency of header, it is still a profitable thing to do. Unfortunately,
+  // we don't have frequency info to figure it out. For one in-loop block it is
+  // easy: header is not colder than any other loop block. Once we have the
+  // frequency info available, we can go with unlimited number of in-loop loads.
+  unsigned MaxUnavailableBlocks = LoopLoadPRE ? 2 : 1;
+  if (NumUnavailablePreds > MaxUnavailableBlocks)
       return false;
 
   // Now we know where we will insert load. We must ensure that it is safe
   // to speculatively execute the load at that points.
   if (MustEnsureSafetyOfSpeculativeExecution) {
     if (CriticalEdgePred.size())
       if (!isSafeToSpeculativelyExecute(Load, LoadBB->getFirstNonPHI(), DT))
         return false;
     for (auto &PL : PredLoads)
if (Instruction *I = dyn_cast<Instruction>(V))
     I->setDebugLoc(Load->getDebugLoc());
   if (V->getType()->isPtrOrPtrVectorTy())
     MD->invalidateCachedPointerInfo(V);
   markInstructionForDeletion(Load);
   ORE->emit([&]() {
     return OptimizationRemark(DEBUG_TYPE, "LoadPRE", Load)
            << "load eliminated by PRE";
   });
+  if (LoopLoadPRE)
+    ++NumPRELoopLoad;
+  else
     ++NumPRELoad;
   return true;
 }
 
 static void reportLoadElim(LoadInst *Load, Value *AvailableValue,
                            OptimizationRemarkEmitter *ORE) {
   using namespace ore;
 
   ORE->emit([&]() {
     return OptimizationRemark(DEBUG_TYPE, "LoadElim", Load)
            << "load of type " << NV("Type", Load->getType()) << " eliminated"
            << setExtraArgs() << " in favor of "
            << NV("InfavorOfValue", AvailableValue);
   });
 }
 
 /// Attempt to eliminate a load whose dependencies are
 /// non-local by performing PHI construction.
 bool GVN::processNonLocalLoad(LoadInst *Load) {
   // non-local speculations are not allowed under asan.
   if (Load->getParent()->getParent()->hasFnAttribute(
           Attribute::SanitizeAddress) ||
       Load->getParent()->getParent()->hasFnAttribute(
           Attribute::SanitizeHWAddress))
     return false;
 
   // Step 1: Find the non-local dependencies of the load.
   LoadDepVect Deps;
   MD->getNonLocalPointerDependency(Load, Deps);
 
   // If we had to process more than one hundred blocks to find the
   // dependencies, this load isn't worth worrying about.  Optimizing
   // it will be too expensive.
   unsigned NumDeps = Deps.size();
   if (NumDeps > MaxNumDeps)
     return false;
 
   // If we had a phi translation failure, we'll have a single entry which is a
   // clobber in the current block.  Reject this early.
   if (NumDeps == 1 &&
       !Deps[0].getResult().isDef() && !Deps[0].getResult().isClobber()) {
     LLVM_DEBUG(dbgs() << "GVN: non-local load "; Load->printAsOperand(dbgs());
                dbgs() << " has unknown dependencies\n";);
     return false;
   }
 
   bool Changed = false;
   // If this load follows a GEP, see if we can PRE the indices before analyzing.
   if (GetElementPtrInst *GEP =
           dyn_cast<GetElementPtrInst>(Load->getOperand(0))) {
     for (GetElementPtrInst::op_iterator OI = GEP->idx_begin(),
                                         OE = GEP->idx_end();
          OI != OE; ++OI)
       if (Instruction *I = dyn_cast<Instruction>(OI->get()))
         Changed |= performScalarPRE(I);
   }
 
   // Step 2: Analyze the availability of the load
   AvailValInBlkVect ValuesPerBlock;
   UnavailBlkVect UnavailableBlocks;
   AnalyzeLoadAvailability(Load, Deps, ValuesPerBlock, UnavailableBlocks);
 
   // If we have no predecessors that produce a known value for this load, exit
   // early.
   if (ValuesPerBlock.empty())
     return Changed;
 
   // Step 3: Eliminate fully redundancy.
   //
   // If all of the instructions we depend on produce a known value for this
   // load, then it is fully redundant and we can use PHI insertion to compute
   // its value.  Insert PHIs and remove the fully redundant value now.
   if (UnavailableBlocks.empty()) {
     LLVM_DEBUG(dbgs() << "GVN REMOVING NONLOCAL LOAD: " << *Load << '\n');
 
     // Perform PHI construction.
     Value *V = ConstructSSAForLoadSet(Load, ValuesPerBlock, *this);
     Load->replaceAllUsesWith(V);
 
     if (isa<PHINode>(V))
       V->takeName(Load);

llvm/test/Transforms/GVN/PRE/lpre-call-wrap.ll

 ; CHECK-LABEL: @_Z12testfunctionR1A(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[TMP0:%.*]] = getelementptr [[STRUCT_A:%.*]], %struct.A* [[ITER:%.*]], i32 0, i32 0
 ; CHECK-NEXT:    [[TMP1:%.*]] = load i32, i32* [[TMP0]], align 4
 ; CHECK-NEXT:    [[TMP2:%.*]] = icmp eq i32 [[TMP1]], 0
 ; CHECK-NEXT:    br i1 [[TMP2]], label [[RETURN:%.*]], label [[BB_NPH:%.*]]
 ; CHECK:       bb.nph:
 ; CHECK-NEXT:    [[TMP3:%.*]] = getelementptr [[STRUCT_A]], %struct.A* [[ITER]], i32 0, i32 1
+; CHECK-NEXT:    [[DOTPRE1:%.*]] = load i32, i32* [[TMP3]], align 4
 ; CHECK-NEXT:    br label [[BB:%.*]]
 ; CHECK:       bb:
-; CHECK-NEXT:    [[DOTRLE:%.*]] = phi i32 [ [[TMP1]], [[BB_NPH]] ], [ [[TMP7:%.*]], [[BB3_BACKEDGE:%.*]] ]
-; CHECK-NEXT:    [[TMP4:%.*]] = add i32 [[DOTRLE]], 1
-; CHECK-NEXT:    store i32 [[TMP4]], i32* [[TMP0]], align 4
-; CHECK-NEXT:    [[TMP5:%.*]] = load i32, i32* [[TMP3]], align 4
-; CHECK-NEXT:    [[TMP6:%.*]] = icmp eq i32 [[TMP4]], [[TMP5]]
+; CHECK-NEXT:    [[TMP4:%.*]] = phi i32 [ [[DOTPRE1]], [[BB_NPH]] ], [ [[TMP8:%.*]], [[BB3_BACKEDGE:%.*]] ]
+; CHECK-NEXT:    [[DOTRLE:%.*]] = phi i32 [ [[TMP1]], [[BB_NPH]] ], [ [[TMP7:%.*]], [[BB3_BACKEDGE]] ]
+; CHECK-NEXT:    [[TMP5:%.*]] = add i32 [[DOTRLE]], 1
+; CHECK-NEXT:    store i32 [[TMP5]], i32* [[TMP0]], align 4
+; CHECK-NEXT:    [[TMP6:%.*]] = icmp eq i32 [[TMP5]], [[TMP4]]
 ; CHECK-NEXT:    br i1 [[TMP6]], label [[BB1:%.*]], label [[BB3_BACKEDGE]]
 ; CHECK:       bb1:
 ; CHECK-NEXT:    tail call void @_Z1gv()
-; CHECK-NEXT:    [[DOTPRE:%.*]] = load i32, i32* [[TMP0]], align 4
+; CHECK-NEXT:    [[DOTPRE:%.*]] = load i32, i32* [[TMP3]], align 4
+; CHECK-NEXT:    [[DOTPRE2:%.*]] = load i32, i32* [[TMP0]], align 4
 ; CHECK-NEXT:    br label [[BB3_BACKEDGE]]
 ; CHECK:       bb3.backedge:
-; CHECK-NEXT:    [[TMP7]] = phi i32 [ [[DOTPRE]], [[BB1]] ], [ [[TMP4]], [[BB]] ]
-; CHECK-NEXT:    [[TMP8:%.*]] = icmp eq i32 [[TMP7]], 0
-; CHECK-NEXT:    br i1 [[TMP8]], label [[RETURN]], label [[BB]]
+; CHECK-NEXT:    [[TMP7]] = phi i32 [ [[DOTPRE2]], [[BB1]] ], [ [[TMP5]], [[BB]] ]
+; CHECK-NEXT:    [[TMP8]] = phi i32 [ [[DOTPRE]], [[BB1]] ], [ [[TMP4]], [[BB]] ]
+; CHECK-NEXT:    [[TMP9:%.*]] = icmp eq i32 [[TMP7]], 0
+; CHECK-NEXT:    br i1 [[TMP9]], label [[RETURN]], label [[BB]]
 ; CHECK:       return:
 ; CHECK-NEXT:    ret void
 ;
 entry:
   %0 = getelementptr %struct.A, %struct.A* %iter, i32 0, i32 0    ; <i32*> [#uses=3]
   %1 = load i32, i32* %0, align 4    ; <i32> [#uses=2]
   %2 = icmp eq i32 %1, 0    ; <i1> [#uses=1]
   br i1 %2, label %return, label %bb.nph

llvm/test/Transforms/GVN/PRE/pre-aliasning-path.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt -basic-aa -enable-load-pre -enable-pre -gvn -S < %s | FileCheck %s
 
 declare void @side_effect_0()
 
 declare void @side_effect_1(i32 %x)
 
 declare void @no_side_effect() readonly
 
-; TODO: We can PRE the load into the cold path, removing it from the hot path.
 define i32 @test_01(i32* %p) {
 ; CHECK-LABEL: @test_01(
 ; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[X_PRE1:%.*]] = load i32, i32* [[P:%.*]], align 4
 ; CHECK-NEXT:    br label [[LOOP:%.*]]
 ; CHECK:       loop:
-; CHECK-NEXT:    [[IV:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ [[IV_NEXT:%.*]], [[BACKEDGE:%.*]] ]
-; CHECK-NEXT:    [[X:%.*]] = load i32, i32* [[P:%.*]], align 4
+; CHECK-NEXT:    [[X:%.*]] = phi i32 [ [[X_PRE1]], [[ENTRY:%.*]] ], [ [[X2:%.*]], [[BACKEDGE:%.*]] ]
+; CHECK-NEXT:    [[IV:%.*]] = phi i32 [ 0, [[ENTRY]] ], [ [[IV_NEXT:%.*]], [[BACKEDGE]] ]
 ; CHECK-NEXT:    [[COND:%.*]] = icmp ult i32 [[X]], 100
 ; CHECK-NEXT:    br i1 [[COND]], label [[HOT_PATH:%.*]], label [[COLD_PATH:%.*]]
 ; CHECK:       hot_path:
 ; CHECK-NEXT:    br label [[BACKEDGE]]
 ; CHECK:       cold_path:
 ; CHECK-NEXT:    call void @side_effect_0()
+; CHECK-NEXT:    [[X_PRE:%.*]] = load i32, i32* [[P]], align 4
 ; CHECK-NEXT:    br label [[BACKEDGE]]
 ; CHECK:       backedge:
+; CHECK-NEXT:    [[X2]] = phi i32 [ [[X_PRE]], [[COLD_PATH]] ], [ [[X]], [[HOT_PATH]] ]
 ; CHECK-NEXT:    [[IV_NEXT]] = add i32 [[IV]], [[X]]
 ; CHECK-NEXT:    [[LOOP_COND:%.*]] = icmp ult i32 [[IV_NEXT]], 1000
 ; CHECK-NEXT:    br i1 [[LOOP_COND]], label [[LOOP]], label [[EXIT:%.*]]
 ; CHECK:       exit:
 ; CHECK-NEXT:    ret i32 [[X]]
 ;
 entry:
   br label %loop
backedge:
   %iv.next = add i32 %iv, %x
   %loop.cond = icmp ult i32 %iv.next, 1000
   br i1 %loop.cond, label %loop, label %exit
 
 exit:
   ret i32 %x
 }
 
-; TODO: We can PRE the load into the cold path, removing it from the hot path.
 define i32 @test_02(i32* %p) {
 ; CHECK-LABEL: @test_02(
 ; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[X_PRE1:%.*]] = load i32, i32* [[P:%.*]], align 4
 ; CHECK-NEXT:    br label [[LOOP:%.*]]
 ; CHECK:       loop:
-; CHECK-NEXT:    [[IV:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ [[IV_NEXT:%.*]], [[BACKEDGE:%.*]] ]
-; CHECK-NEXT:    [[X:%.*]] = load i32, i32* [[P:%.*]], align 4
+; CHECK-NEXT:    [[X:%.*]] = phi i32 [ [[X_PRE1]], [[ENTRY:%.*]] ], [ [[X2:%.*]], [[BACKEDGE:%.*]] ]
+; CHECK-NEXT:    [[IV:%.*]] = phi i32 [ 0, [[ENTRY]] ], [ [[IV_NEXT:%.*]], [[BACKEDGE]] ]
 ; CHECK-NEXT:    [[COND:%.*]] = icmp ult i32 [[X]], 100
 ; CHECK-NEXT:    br i1 [[COND]], label [[HOT_PATH:%.*]], label [[COLD_PATH:%.*]]
 ; CHECK:       hot_path:
 ; CHECK-NEXT:    br label [[BACKEDGE]]
 ; CHECK:       cold_path:
 ; CHECK-NEXT:    call void @side_effect_1(i32 [[X]])
+; CHECK-NEXT:    [[X_PRE:%.*]] = load i32, i32* [[P]], align 4
 ; CHECK-NEXT:    br label [[BACKEDGE]]
 ; CHECK:       backedge:
+; CHECK-NEXT:    [[X2]] = phi i32 [ [[X_PRE]], [[COLD_PATH]] ], [ [[X]], [[HOT_PATH]] ]
 ; CHECK-NEXT:    [[IV_NEXT]] = add i32 [[IV]], [[X]]
 ; CHECK-NEXT:    [[LOOP_COND:%.*]] = icmp ult i32 [[IV_NEXT]], 1000
 ; CHECK-NEXT:    br i1 [[LOOP_COND]], label [[LOOP]], label [[EXIT:%.*]]
 ; CHECK:       exit:
 ; CHECK-NEXT:    ret i32 [[X]]
 ;
 entry:
   br label %loop

llvm/test/Transforms/GVN/PRE/pre-loop-load.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt -basic-aa -enable-load-pre -enable-pre -gvn -S < %s | FileCheck %s
 
 declare void @side_effect()
 declare i1 @side_effect_cond()
 
 declare i32 @personality_function()
 
-; TODO: We can PRE the load away from the hot path.
 define i32 @test_load_on_cold_path(i32* %p) {
 ; CHECK-LABEL: @test_load_on_cold_path(
 ; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[X_PRE1:%.*]] = load i32, i32* [[P:%.*]], align 4
 ; CHECK-NEXT:    br label [[LOOP:%.*]]
 ; CHECK:       loop:
-; CHECK-NEXT:    [[IV:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ [[IV_NEXT:%.*]], [[BACKEDGE:%.*]] ]
-; CHECK-NEXT:    [[X:%.*]] = load i32, i32* [[P:%.*]], align 4
+; CHECK-NEXT:    [[X:%.*]] = phi i32 [ [[X_PRE1]], [[ENTRY:%.*]] ], [ [[X2:%.*]], [[BACKEDGE:%.*]] ]
+; CHECK-NEXT:    [[IV:%.*]] = phi i32 [ 0, [[ENTRY]] ], [ [[IV_NEXT:%.*]], [[BACKEDGE]] ]
 ; CHECK-NEXT:    [[COND:%.*]] = icmp ne i32 [[X]], 0
 ; CHECK-NEXT:    br i1 [[COND]], label [[HOT_PATH:%.*]], label [[COLD_PATH:%.*]]
 ; CHECK:       hot_path:
 ; CHECK-NEXT:    br label [[BACKEDGE]]
 ; CHECK:       cold_path:
 ; CHECK-NEXT:    call void @side_effect()
+; CHECK-NEXT:    [[X_PRE:%.*]] = load i32, i32* [[P]], align 4
 ; CHECK-NEXT:    br label [[BACKEDGE]]
 ; CHECK:       backedge:
+; CHECK-NEXT:    [[X2]] = phi i32 [ [[X_PRE]], [[COLD_PATH]] ], [ [[X]], [[HOT_PATH]] ]
 ; CHECK-NEXT:    [[IV_NEXT]] = add i32 [[IV]], [[X]]
 ; CHECK-NEXT:    [[LOOP_COND:%.*]] = icmp ult i32 [[IV_NEXT]], 1000
 ; CHECK-NEXT:    br i1 [[LOOP_COND]], label [[LOOP]], label [[EXIT:%.*]]
 ; CHECK:       exit:
 ; CHECK-NEXT:    ret i32 [[X]]
 ;
 entry:
   br label %loop
 
 loop:
   %iv = phi i32 [ 0, %entry], [%iv.next, %backedge]
   %x = load i32, i32* %p
   %cond = icmp ne i32 %x, 0
   br i1 %cond, label %hot_path, label %cold_path
 
 hot_path:
   br label %backedge
 
 cold_path:
   call void @side_effect()
   br label %backedge
 
 backedge:
   %iv.next = add i32 %iv, %x
   %loop.cond = icmp ult i32 %iv.next, 1000
   br i1 %loop.cond, label %loop, label %exit
 
 exit:

 exit:
   ret i32 %x
 }
 
 ; TODO: We can PRE via splitting of the critical edge in the cold path.
 define i32 @test_load_on_exiting_cold_path_01(i32* %p) {
 ; CHECK-LABEL: @test_load_on_exiting_cold_path_01(
 ; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[X_PRE1:%.*]] = load i32, i32* [[P:%.*]], align 4
 ; CHECK-NEXT:    br label [[LOOP:%.*]]
 ; CHECK:       loop:
-; CHECK-NEXT:    [[IV:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ [[IV_NEXT:%.*]], [[BACKEDGE:%.*]] ]
-; CHECK-NEXT:    [[X:%.*]] = load i32, i32* [[P:%.*]], align 4
+; CHECK-NEXT:    [[X:%.*]] = phi i32 [ [[X_PRE1]], [[ENTRY:%.*]] ], [ [[X2:%.*]], [[BACKEDGE:%.*]] ]
+; CHECK-NEXT:    [[IV:%.*]] = phi i32 [ 0, [[ENTRY]] ], [ [[IV_NEXT:%.*]], [[BACKEDGE]] ]
 ; CHECK-NEXT:    [[COND:%.*]] = icmp ne i32 [[X]], 0
 ; CHECK-NEXT:    br i1 [[COND]], label [[HOT_PATH:%.*]], label [[COLD_PATH:%.*]]
 ; CHECK:       hot_path:
 ; CHECK-NEXT:    br label [[BACKEDGE]]
 ; CHECK:       cold_path:
 ; CHECK-NEXT:    [[SIDE_COND:%.*]] = call i1 @side_effect_cond()
+; CHECK-NEXT:    [[X_PRE:%.*]] = load i32, i32* [[P]], align 4
 ; CHECK-NEXT:    br i1 [[SIDE_COND]], label [[BACKEDGE]], label [[COLD_EXIT:%.*]]
 ; CHECK:       backedge:
+; CHECK-NEXT:    [[X2]] = phi i32 [ [[X_PRE]], [[COLD_PATH]] ], [ [[X]], [[HOT_PATH]] ]
 ; CHECK-NEXT:    [[IV_NEXT]] = add i32 [[IV]], [[X]]
 ; CHECK-NEXT:    [[LOOP_COND:%.*]] = icmp ult i32 [[IV_NEXT]], 1000
 ; CHECK-NEXT:    br i1 [[LOOP_COND]], label [[LOOP]], label [[EXIT:%.*]]
 ; CHECK:       exit:
 ; CHECK-NEXT:    ret i32 [[X]]
 ; CHECK:       cold_exit:
 ; CHECK-NEXT:    ret i32 -1
 ;

 exit:
   ret i32 %x
 }
 
 ; TODO: We can PRE via splitting of the critical edge in the cold path. Make sure we only insert 1 load.
 define i32 @test_load_on_multi_exiting_cold_path(i32* %p) {
 ; CHECK-LABEL: @test_load_on_multi_exiting_cold_path(
 ; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[X_PRE1:%.*]] = load i32, i32* [[P:%.*]], align 4
 ; CHECK-NEXT:    br label [[LOOP:%.*]]
 ; CHECK:       loop:
-; CHECK-NEXT:    [[IV:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ [[IV_NEXT:%.*]], [[BACKEDGE:%.*]] ]
-; CHECK-NEXT:    [[X:%.*]] = load i32, i32* [[P:%.*]], align 4
+; CHECK-NEXT:    [[X:%.*]] = phi i32 [ [[X_PRE1]], [[ENTRY:%.*]] ], [ [[X2:%.*]], [[BACKEDGE:%.*]] ]
+; CHECK-NEXT:    [[IV:%.*]] = phi i32 [ 0, [[ENTRY]] ], [ [[IV_NEXT:%.*]], [[BACKEDGE]] ]
 ; CHECK-NEXT:    [[COND:%.*]] = icmp ne i32 [[X]], 0
 ; CHECK-NEXT:    br i1 [[COND]], label [[HOT_PATH:%.*]], label [[COLD_PATH_1:%.*]]
 ; CHECK:       hot_path:
 ; CHECK-NEXT:    br label [[BACKEDGE]]
 ; CHECK:       cold_path.1:
 ; CHECK-NEXT:    [[SIDE_COND_1:%.*]] = call i1 @side_effect_cond()
 ; CHECK-NEXT:    br i1 [[SIDE_COND_1]], label [[COLD_PATH_2:%.*]], label [[COLD_EXIT:%.*]]
 ; CHECK:       cold_path.2:
 ; CHECK-NEXT:    [[SIDE_COND_2:%.*]] = call i1 @side_effect_cond()
 ; CHECK-NEXT:    br i1 [[SIDE_COND_2]], label [[COLD_PATH_3:%.*]], label [[COLD_EXIT]]
 ; CHECK:       cold_path.3:
 ; CHECK-NEXT:    [[SIDE_COND_3:%.*]] = call i1 @side_effect_cond()
+; CHECK-NEXT:    [[X_PRE:%.*]] = load i32, i32* [[P]], align 4
 ; CHECK-NEXT:    br i1 [[SIDE_COND_3]], label [[BACKEDGE]], label [[COLD_EXIT]]
 ; CHECK:       backedge:
+; CHECK-NEXT:    [[X2]] = phi i32 [ [[X_PRE]], [[COLD_PATH_3]] ], [ [[X]], [[HOT_PATH]] ]
 ; CHECK-NEXT:    [[IV_NEXT]] = add i32 [[IV]], [[X]]
 ; CHECK-NEXT:    [[LOOP_COND:%.*]] = icmp ult i32 [[IV_NEXT]], 1000
 ; CHECK-NEXT:    br i1 [[LOOP_COND]], label [[LOOP]], label [[EXIT:%.*]]
 ; CHECK:       exit:
 ; CHECK-NEXT:    ret i32 [[X]]
 ; CHECK:       cold_exit:
 ; CHECK-NEXT:    ret i32 -1
 ;

 exit:
   ret i32 %x
 }
 
 ; TODO: We can PRE via split of critical edge.
 define i32 @test_side_exit_after_merge(i32* %p) {
 ; CHECK-LABEL: @test_side_exit_after_merge(
 ; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[X_PRE1:%.*]] = load i32, i32* [[P:%.*]], align 4
 ; CHECK-NEXT:    br label [[LOOP:%.*]]
 ; CHECK:       loop:
-; CHECK-NEXT:    [[IV:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ [[IV_NEXT:%.*]], [[BACKEDGE:%.*]] ]
-; CHECK-NEXT:    [[X:%.*]] = load i32, i32* [[P:%.*]], align 4
+; CHECK-NEXT:    [[X:%.*]] = phi i32 [ [[X_PRE1]], [[ENTRY:%.*]] ], [ [[X2:%.*]], [[BACKEDGE:%.*]] ]
+; CHECK-NEXT:    [[IV:%.*]] = phi i32 [ 0, [[ENTRY]] ], [ [[IV_NEXT:%.*]], [[BACKEDGE]] ]
 ; CHECK-NEXT:    [[COND:%.*]] = icmp ne i32 [[X]], 0
 ; CHECK-NEXT:    br i1 [[COND]], label [[HOT_PATH:%.*]], label [[COLD_PATH:%.*]]
 ; CHECK:       hot_path:
 ; CHECK-NEXT:    br label [[BACKEDGE]]
 ; CHECK:       cold_path:
 ; CHECK-NEXT:    [[COND_1:%.*]] = icmp ne i32 [[IV]], 1
 ; CHECK-NEXT:    br i1 [[COND_1]], label [[DO_CALL:%.*]], label [[SIDE_EXITING:%.*]]
 ; CHECK:       do_call:
 ; CHECK-NEXT:    [[SIDE_COND:%.*]] = call i1 @side_effect_cond()
+; CHECK-NEXT:    [[X_PRE:%.*]] = load i32, i32* [[P]], align 4
 ; CHECK-NEXT:    br label [[SIDE_EXITING]]
 ; CHECK:       side_exiting:
+; CHECK-NEXT:    [[X3:%.*]] = phi i32 [ [[X_PRE]], [[DO_CALL]] ], [ 0, [[COLD_PATH]] ]
 ; CHECK-NEXT:    [[SIDE_COND_PHI:%.*]] = phi i1 [ [[SIDE_COND]], [[DO_CALL]] ], [ true, [[COLD_PATH]] ]
 ; CHECK-NEXT:    br i1 [[SIDE_COND_PHI]], label [[BACKEDGE]], label [[COLD_EXIT:%.*]]
 ; CHECK:       backedge:
+; CHECK-NEXT:    [[X2]] = phi i32 [ [[X3]], [[SIDE_EXITING]] ], [ [[X]], [[HOT_PATH]] ]
 ; CHECK-NEXT:    [[IV_NEXT]] = add i32 [[IV]], [[X]]
 ; CHECK-NEXT:    [[LOOP_COND:%.*]] = icmp ult i32 [[IV_NEXT]], 1000
 ; CHECK-NEXT:    br i1 [[LOOP_COND]], label [[LOOP]], label [[EXIT:%.*]]
 ; CHECK:       exit:
 ; CHECK-NEXT:    ret i32 [[X]]
 ; CHECK:       cold_exit:
 ; CHECK-NEXT:    ret i32 -1
 ;

 
 exit:
   ret i32 %x
 }
 
 define i32 @test_guard_2(i32* %p, i32 %g) {
 ; CHECK-LABEL: @test_guard_2(
 ; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[X_PRE1:%.*]] = load i32, i32* [[P:%.*]], align 4
 ; CHECK-NEXT:    br label [[LOOP:%.*]]
 ; CHECK:       loop:
-; CHECK-NEXT:    [[IV:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ [[IV_NEXT:%.*]], [[BACKEDGE:%.*]] ]
+; CHECK-NEXT:    [[X:%.*]] = phi i32 [ [[X_PRE1]], [[ENTRY:%.*]] ], [ [[X2:%.*]], [[BACKEDGE:%.*]] ]
+; CHECK-NEXT:    [[IV:%.*]] = phi i32 [ 0, [[ENTRY]] ], [ [[IV_NEXT:%.*]], [[BACKEDGE]] ]
 ; CHECK-NEXT:    [[GUARD_COND:%.*]] = icmp ne i32 [[IV]], [[G:%.*]]
-; CHECK-NEXT:    [[X:%.*]] = load i32, i32* [[P:%.*]], align 4
 ; CHECK-NEXT:    call void (i1, ...) @llvm.experimental.guard(i1 [[GUARD_COND]]) [ "deopt"() ]
 ; CHECK-NEXT:    [[COND:%.*]] = icmp ult i32 [[X]], 100
 ; CHECK-NEXT:    br i1 [[COND]], label [[HOT_PATH:%.*]], label [[COLD_PATH:%.*]]
 ; CHECK:       hot_path:
 ; CHECK-NEXT:    br label [[BACKEDGE]]
 ; CHECK:       cold_path:
 ; CHECK-NEXT:    call void @side_effect()
+; CHECK-NEXT:    [[X_PRE:%.*]] = load i32, i32* [[P]], align 4
 ; CHECK-NEXT:    br label [[BACKEDGE]]
 ; CHECK:       backedge:
+; CHECK-NEXT:    [[X2]] = phi i32 [ [[X_PRE]], [[COLD_PATH]] ], [ [[X]], [[HOT_PATH]] ]
 ; CHECK-NEXT:    [[IV_NEXT]] = add i32 [[IV]], [[X]]
 ; CHECK-NEXT:    [[LOOP_COND:%.*]] = icmp ult i32 [[IV_NEXT]], 1000
 ; CHECK-NEXT:    br i1 [[LOOP_COND]], label [[LOOP]], label [[EXIT:%.*]]
 ; CHECK:       exit:
 ; CHECK-NEXT:    ret i32 [[X]]
 ;
 entry:
   br label %loop