[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

1467

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.

1481

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.

1486

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

1497

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

1467

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

1486

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

1497

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

1497

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.

1516

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

1517

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

1520

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

1517

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

1520

Removed.

[reames]

LGTM w/minor comments.

llvm/lib/Transforms/Scalar/GVN.cpp

1468

Type: In order

1512

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

1518

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

1518

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

1518

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

1512

Shouldn't it be a part of canBeFreed?

[reames]

LGTM

llvm/include/llvm/Transforms/Scalar/GVN.h

private:
   /// ValuesPerBlock.  If not, add it to UnavailableBlocks.
   void AnalyzeLoadAvailability(LoadInst *Load, LoadDepVect &Deps,
                                AvailValInBlkVect &ValuesPerBlock,
                                UnavailBlkVect &UnavailableBlocks);
 
   bool PerformLoadPRE(LoadInst *Load, AvailValInBlkVect &ValuesPerBlock,
                       UnavailBlkVect &UnavailableBlocks);
 
+  bool PerformLoopLoadPRE(LoadInst *Load, AvailValInBlkVect &ValuesPerBlock,
+                      UnavailBlkVect &UnavailableBlocks);
+
   /// Eliminates partially redundant \p Load, replacing it with \p
   /// AvailableLoads (connected by Phis if needed).
   void eliminatePartiallyRedundantLoad(
       LoadInst *Load, AvailValInBlkVect &ValuesPerBlock,
       MapVector<BasicBlock *, Value *> &AvailableLoads);
 
   // Other helper routines
   bool processInstruction(Instruction *I);

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");
 
 static cl::opt<bool> GVNEnablePRE("enable-pre", cl::init(true), cl::Hidden);
for (Instruction *I : NewInsts) {
     VN.lookupOrAdd(I);
   }
 
   eliminatePartiallyRedundantLoad(Load, ValuesPerBlock, PredLoads);
   ++NumPRELoad;
   return true;
 }
 
+bool GVN::PerformLoopLoadPRE(LoadInst *Load, AvailValInBlkVect &ValuesPerBlock,
+                         UnavailBlkVect &UnavailableBlocks) {
+  if (!LI)
+    return false;
+
+  const Loop *L = LI->getLoopFor(Load->getParent());
+  // TODO: Generalize to other loop blocks that dominate the latch.
+  if (!L || L->getHeader() != Load->getParent())
+    return false;
+
+  BasicBlock *Preheader = L->getLoopPreheader();
+  BasicBlock *Latch = L->getLoopLatch();
+  if (!Preheader || !Latch)
+    return false;
+
+  // We can side-exit before the load is executed.
+  if (ICF->isDominatedByICFIFromSameBlock(Load))
+    return false;
+
+  unsigned UnavailableLoopBlocks = 0;
+  for (auto *Blocker : UnavailableBlocks) {
+    // Blockers from outside the loop are handled in preheader.
+    if (!L->contains(Blocker))
+      continue;
+    // Do not sink into inner loops.
+    if (L != LI->getLoopFor(Blocker))
+      return false;
+
+    UnavailableLoopBlocks++;
+    // So far, only PRE into not-mustexecute blocks.
+    if (DT->dominates(Blocker, Latch)) {
+      return false;
+    }
+
+    if (!isa<BranchInst>(Blocker->getTerminator()))
+      return false;
+  }
+
+  // TODO: We could do it if we had block frequency info here.
+  if (UnavailableLoopBlocks != 1)
+    return false;
+
+  // TODO: Support critical edge splitting if blocker has more than 1 successor.
+  Value *LoadPtr = Load->getPointerOperand();
+  MapVector<BasicBlock *, Value *> AvailableLoads;
+  for (auto *Blocker : UnavailableBlocks)
+    AvailableLoads[Blocker] = LoadPtr;
+  AvailableLoads[Preheader] = LoadPtr;
+
+  LLVM_DEBUG(dbgs() << "GVN REMOVING PRE LOOP LOAD: " << *Load << '\n');
+  eliminatePartiallyRedundantLoad(Load, ValuesPerBlock, AvailableLoads);
+  ++NumPRELoopLoad;
+  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;
 
bool GVN::processNonLocalLoad(LoadInst *Load) {
   }
 
   // Step 4: Eliminate partial redundancy.
   if (!isPREEnabled() || !isLoadPREEnabled())
     return Changed;
   if (!isLoadInLoopPREEnabled() && LI && LI->getLoopFor(Load->getParent()))
     return Changed;
 
-  return Changed || PerformLoadPRE(Load, ValuesPerBlock, UnavailableBlocks);
+  return Changed || PerformLoadPRE(Load, ValuesPerBlock, UnavailableBlocks) || PerformLoopLoadPRE(Load, ValuesPerBlock, UnavailableBlocks);
 }
 
 static bool impliesEquivalanceIfTrue(CmpInst* Cmp) {
   if (Cmp->getPredicate() == CmpInst::Predicate::ICMP_EQ)
     return true;
 
   // Floating point comparisons can be equal, but not equivalent.  Cases:
   // NaNs for unordered operators

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_PRE:%.*]] = 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_PRE]], [[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_PRE1:%.*]] = load i32, i32* [[P]], align 4
 ; CHECK-NEXT:    br label [[BACKEDGE]]
 ; CHECK:       backedge:
+; CHECK-NEXT:    [[X2]] = phi i32 [ [[X_PRE1]], [[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_PRE:%.*]] = 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_PRE]], [[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_PRE1:%.*]] = 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_PRE1]], [[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_PRE:%.*]] = 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_PRE]], [[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_PRE1:%.*]] = 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_PRE1]], [[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_PRE:%.*]] = 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_PRE]], [[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_PRE1:%.*]] = load i32, i32* [[P]], align 4
 ; CHECK-NEXT:    br label [[SIDE_EXITING]]
 ; CHECK:       side_exiting:
+; CHECK-NEXT:    [[X3:%.*]] = phi i32 [ [[X_PRE1]], [[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_PRE:%.*]] = 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_PRE]], [[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_PRE1:%.*]] = load i32, i32* [[P]], align 4
 ; CHECK-NEXT:    br label [[BACKEDGE]]
 ; CHECK:       backedge:
+; CHECK-NEXT:    [[X2]] = phi i32 [ [[X_PRE1]], [[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