[LICM] Make Loop ICM profile aware again

[modimo]

Summary

D65060 was reverted because it introduced non-determinism by using BFI counts from already freed blocks. The parent of this revision fixes that by using a VH callback on blocks to prevent this from happening and makes sure BFI data is passed correctly in LoopStandardAnalysisResults.

This re-introduces the previous optimization of using BFI data to prevent LICM from hoisting/sinking if the instruction will end up moving to a colder block.

Internally at Facebook this change results in a ~7% win in a CPU related metric in one of our big services by preventing hoisting cold code into a hot pre-header like the added test case demonstrates.

Testing:
ninja check

[asbirlea]

Thank you for the patch!

Could you include in the description the benefits seen from adding this, as a data point?

llvm/include/llvm/Transforms/Utils/LoopUtils.h

127

Nit: update comment to include arguments and not duplicate "information for all".

[modimo]

Fix merge issues with comment, updated description to include benefit we see from this change. Thanks @asbirlea for the quick review!

[modimo]

Remove unnecessary period

[wenlei]

Committed on behalf of @modimo.

[reames]

I'm sorry for coming to this very late, but I just noticed this patch due to discussion on another patch (D111806).

This change is inconsistent with the long standing design of LICM. LICM is a canonicalizing transform, and we specifically *do not* use any profitability metric therein. MachineLICM exists specifically to be the inverse transformation which is cost based. I see nothing in the example to make it clear why MachineLICM could not handle this case.

As evidenced by the very existence of the later patch, having this in tree sets a bad precedent. I believe this patch should be reverted.

Given it's been in tree for nearly a year, this clearly isn't immediately urgent. Given that, I'm going to give a couple of days for discussion before reverting this patch.

[lebedev.ri]

In D87551#3065340, @reames wrote:

I'm sorry for coming to this very late, but I just noticed this patch due to discussion on another patch (D111806).

This change is inconsistent with the long standing design of LICM. LICM is a canonicalizing transform, and we specifically *do not* use any profitability metric therein. MachineLICM exists specifically to be the inverse transformation which is cost based. I see nothing in the example to make it clear why MachineLICM could not handle this case.

As evidenced by the very existence of the later patch, having this in tree sets a bad precedent. I believe this patch should be reverted.

Given it's been in tree for nearly a year, this clearly isn't immediately urgent. Given that, I'm going to give a couple of days for discussion before reverting this patch.

FWIW, i agree with Philip on this.

While i'm sure that this, and many other, transform are easy wins,
they fundamentally do not fit the design of the pass(es). Creating initial divergence
opens a door for further changes of the same nature, and it's increasingly more
and more complicated to keep the door shut further down the line. The other example
is e.g. instcombine. We just can not afford to have a single canonical representation
except not really when $X || $Y || $z.

This must be rolled back.

[reames]

I will be reverting this change in the near future. See previously expressed comments on this review, and the recent llvm-dev thread titled "LICM as canonical form".

Note that I confirmed that both test cases checked in with this change are handled by LoopSink.

[wenlei]

This revert falls through the cracks, but recently we saw a 3% perf regression on a very large server workload due to compiler upgrade, and we tracked it down to this revert. It triggered investigation again, and I read through the comments on patches and "LICM as canonical form" thread - thanks for following up and the clarifications @reames.

It is perhaps an extreme case that we're looking at - we have a 400+ entry cold jump table (from switch) inside a loop, and hoisting defs from each of the 400+ jump targets all to loop pre-header killed the performance. The defs from the 400+ jump table targets all feed into a PHI-use afterwards, and that PHI is what blocked loop sink.

So it comes down to PHI uses. Loop sink currently blocks sinking to PHI-use: https://github.com/llvm/llvm-project/blob/main/llvm/lib/Transforms/Scalar/LoopSink.cpp#L181-L182. I think we can see through PHI and sink to the incoming block of the value being used - I gave it a try and that seems to address our problem. Testing on a few internal components showed that removing the limitation on sinking to PHI sometimes allows 2x more loop sink to happen. I will send up a patch.

llvm/include/llvm/Transforms/Utils/LoopUtils.h

 namespace llvm {
 
 template <typename T> class DomTreeNodeBase;
 using DomTreeNode = DomTreeNodeBase<BasicBlock>;
 class AAResults;
 class AliasSet;
 class AliasSetTracker;
 class BasicBlock;
+class BlockFrequencyInfo;
 class IRBuilderBase;
 class Loop;
 class LoopInfo;
 class MemoryAccess;
 class MemorySSA;
 class MemorySSAUpdater;
 class OptimizationRemarkEmitter;
 class PredIteratorCache;
struct SinkAndHoistLICMFlags {
   bool IsSink;
 };
 
 /// Walk the specified region of the CFG (defined by all blocks
 /// dominated by the specified block, and that are in the current loop) in
 /// reverse depth first order w.r.t the DominatorTree. This allows us to visit
 /// uses before definitions, allowing us to sink a loop body in one pass without
 /// iteration. Takes DomTreeNode, AAResults, LoopInfo, DominatorTree,
-/// TargetLibraryInfo, Loop, AliasSet information for all
+/// BlockFrequencyInfo, TargetLibraryInfo, Loop, AliasSet information for all
 /// instructions of the loop and loop safety information as
 /// arguments. Diagnostics is emitted via \p ORE. It returns changed status.
 bool sinkRegion(DomTreeNode *, AAResults *, LoopInfo *, DominatorTree *,
-                TargetLibraryInfo *, TargetTransformInfo *, Loop *,
-                AliasSetTracker *, MemorySSAUpdater *, ICFLoopSafetyInfo *,
+                BlockFrequencyInfo *, TargetLibraryInfo *,
+                TargetTransformInfo *, Loop *, AliasSetTracker *,
+                MemorySSAUpdater *, ICFLoopSafetyInfo *,
                 SinkAndHoistLICMFlags &, OptimizationRemarkEmitter *);
 
 /// Walk the specified region of the CFG (defined by all blocks
 /// dominated by the specified block, and that are in the current loop) in depth
 /// first order w.r.t the DominatorTree.  This allows us to visit definitions
 /// before uses, allowing us to hoist a loop body in one pass without iteration.
 /// Takes DomTreeNode, AAResults, LoopInfo, DominatorTree,
-/// TargetLibraryInfo, Loop, AliasSet information for all instructions of the
-/// loop and loop safety information as arguments. Diagnostics is emitted via \p
-/// ORE. It returns changed status.
+/// BlockFrequencyInfo, TargetLibraryInfo, Loop, AliasSet information for all
+/// instructions of the loop and loop safety information as arguments.
+/// Diagnostics is emitted via \p ORE. It returns changed status.
 bool hoistRegion(DomTreeNode *, AAResults *, LoopInfo *, DominatorTree *,
-                 TargetLibraryInfo *, Loop *, AliasSetTracker *,
-                 MemorySSAUpdater *, ScalarEvolution *, ICFLoopSafetyInfo *,
-                 SinkAndHoistLICMFlags &, OptimizationRemarkEmitter *);
+                 BlockFrequencyInfo *, TargetLibraryInfo *, Loop *,
+                 AliasSetTracker *, MemorySSAUpdater *, ScalarEvolution *,
+                 ICFLoopSafetyInfo *, SinkAndHoistLICMFlags &,
+                 OptimizationRemarkEmitter *);
 
 /// This function deletes dead loops. The caller of this function needs to
 /// guarantee that the loop is infact dead.
 /// The function requires a bunch or prerequisites to be present:
 ///   - The loop needs to be in LCSSA form
 ///   - The loop needs to have a Preheader
 ///   - A unique dedicated exit block must exist
 ///

llvm/lib/Passes/PassBuilder.cpp

if (!InnerPipeline.empty()) {
     }
     if (Name == "loop" || Name == "loop-mssa") {
       LoopPassManager LPM(DebugLogging);
       if (auto Err = parseLoopPassPipeline(LPM, InnerPipeline, VerifyEachPass,
                                            DebugLogging))
         return Err;
       // Add the nested pass manager with the appropriate adaptor.
       bool UseMemorySSA = (Name == "loop-mssa");
-      FPM.addPass(createFunctionToLoopPassAdaptor(
-          std::move(LPM), UseMemorySSA, /*UseBlockFrequencyInfo=*/false,
-          DebugLogging));
+      bool UseBFI =
+          std::any_of(InnerPipeline.begin(), InnerPipeline.end(),
+                      [](auto Pipeline) { return Pipeline.Name == "licm"; });
+      FPM.addPass(createFunctionToLoopPassAdaptor(std::move(LPM), UseMemorySSA,
+                                                  UseBFI, DebugLogging));
       return Error::success();
     }
     if (auto Count = parseRepeatPassName(Name)) {
       FunctionPassManager NestedFPM(DebugLogging);
       if (auto Err = parseFunctionPassPipeline(NestedFPM, InnerPipeline,
                                                VerifyEachPass, DebugLogging))
         return Err;
       FPM.addPass(createRepeatedPass(*Count, std::move(NestedFPM)));

llvm/lib/Transforms/Scalar/LICM.cpp

 //===----------------------------------------------------------------------===//
 
 #include "llvm/Transforms/Scalar/LICM.h"
 #include "llvm/ADT/SetOperations.h"
 #include "llvm/ADT/Statistic.h"
 #include "llvm/Analysis/AliasAnalysis.h"
 #include "llvm/Analysis/AliasSetTracker.h"
 #include "llvm/Analysis/BasicAliasAnalysis.h"
+#include "llvm/Analysis/BlockFrequencyInfo.h"
 #include "llvm/Analysis/CaptureTracking.h"
 #include "llvm/Analysis/ConstantFolding.h"
 #include "llvm/Analysis/GlobalsModRef.h"
 #include "llvm/Analysis/GuardUtils.h"
 #include "llvm/Analysis/LazyBlockFrequencyInfo.h"
 #include "llvm/Analysis/Loads.h"
 #include "llvm/Analysis/LoopInfo.h"
 #include "llvm/Analysis/LoopIterator.h"

 static cl::opt<bool>
     DisablePromotion("disable-licm-promotion", cl::Hidden, cl::init(false),
                      cl::desc("Disable memory promotion in LICM pass"));
 
 static cl::opt<bool> ControlFlowHoisting(
     "licm-control-flow-hoisting", cl::Hidden, cl::init(false),
     cl::desc("Enable control flow (and PHI) hoisting in LICM"));
 
+static cl::opt<unsigned> HoistSinkColdnessThreshold(
+    "licm-coldness-threshold", cl::Hidden, cl::init(4),
+    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)"));
 
 // Default value of zero implies we use the regular alias set tracker mechanism
 // instead of the cross product using AA to identify aliasing of the memory
 // location we are interested in.

 static bool isNotUsedOrFreeInLoop(const Instruction &I, const Loop *CurLoop,
                                   const LoopSafetyInfo *SafetyInfo,
                                   TargetTransformInfo *TTI, bool &FreeInLoop);
 static void hoist(Instruction &I, const DominatorTree *DT, const Loop *CurLoop,
                   BasicBlock *Dest, ICFLoopSafetyInfo *SafetyInfo,
                   MemorySSAUpdater *MSSAU, ScalarEvolution *SE,
                   OptimizationRemarkEmitter *ORE);
 static bool sink(Instruction &I, LoopInfo *LI, DominatorTree *DT,
-                 const Loop *CurLoop, ICFLoopSafetyInfo *SafetyInfo,
-                 MemorySSAUpdater *MSSAU, OptimizationRemarkEmitter *ORE);
+                 BlockFrequencyInfo *BFI, const Loop *CurLoop,
+                 ICFLoopSafetyInfo *SafetyInfo, MemorySSAUpdater *MSSAU,
+                 OptimizationRemarkEmitter *ORE);
 static bool isSafeToExecuteUnconditionally(Instruction &Inst,
                                            const DominatorTree *DT,
                                            const Loop *CurLoop,
                                            const LoopSafetyInfo *SafetyInfo,
                                            OptimizationRemarkEmitter *ORE,
                                            const Instruction *CtxI = nullptr);
 static bool pointerInvalidatedByLoop(MemoryLocation MemLoc,
                                      AliasSetTracker *CurAST, Loop *CurLoop,
bool LoopInvariantCodeMotion::runOnLoop(
   // Traverse the body of the loop in depth first order on the dominator tree so
   // that we are guaranteed to see definitions before we see uses.  This allows
   // us to sink instructions in one pass, without iteration.  After sinking
   // instructions, we perform another pass to hoist them out of the loop.
   SinkAndHoistLICMFlags Flags = {NoOfMemAccTooLarge, LicmMssaOptCounter,
                                  LicmMssaOptCap, LicmMssaNoAccForPromotionCap,
                                  /*IsSink=*/true};
   if (L->hasDedicatedExits())
-    Changed |= sinkRegion(DT->getNode(L->getHeader()), AA, LI, DT, TLI, TTI, L,
-                          CurAST.get(), MSSAU.get(), &SafetyInfo, Flags, ORE);
+    Changed |=
+        sinkRegion(DT->getNode(L->getHeader()), AA, LI, DT, BFI, TLI, TTI, L,
   Flags.IsSink = false;
   if (Preheader)
     Changed |=
-        hoistRegion(DT->getNode(L->getHeader()), AA, LI, DT, TLI, L,
+        hoistRegion(DT->getNode(L->getHeader()), AA, LI, DT, BFI, TLI, L,
                     CurAST.get(), MSSAU.get(), SE, &SafetyInfo, Flags, ORE);
 
   // Now that all loop invariants have been removed from the loop, promote any
   // memory references to scalars that we can.
   // Don't sink stores from loops without dedicated block exits. Exits
   // containing indirect branches are not transformed by loop simplify,
   // make sure we catch that. An additional load may be generated in the
   // preheader for SSA updater, so also avoid sinking when no preheader

 }
 
 /// Walk the specified region of the CFG (defined by all blocks dominated by
 /// the specified block, and that are in the current loop) in reverse depth
 /// first order w.r.t the DominatorTree.  This allows us to visit uses before
 /// definitions, allowing us to sink a loop body in one pass without iteration.
 ///
 bool llvm::sinkRegion(DomTreeNode *N, AAResults *AA, LoopInfo *LI,
-                      DominatorTree *DT, TargetLibraryInfo *TLI,
-                      TargetTransformInfo *TTI, Loop *CurLoop,
-                      AliasSetTracker *CurAST, MemorySSAUpdater *MSSAU,
-                      ICFLoopSafetyInfo *SafetyInfo,
+                      DominatorTree *DT, BlockFrequencyInfo *BFI,
+                      TargetLibraryInfo *TLI, TargetTransformInfo *TTI,
+                      Loop *CurLoop, AliasSetTracker *CurAST,
+                      MemorySSAUpdater *MSSAU, ICFLoopSafetyInfo *SafetyInfo,
                       SinkAndHoistLICMFlags &Flags,
                       OptimizationRemarkEmitter *ORE) {
 
   // Verify inputs.
   assert(N != nullptr && AA != nullptr && LI != nullptr && DT != nullptr &&
          CurLoop != nullptr && SafetyInfo != nullptr &&
          "Unexpected input to sinkRegion.");
   assert(((CurAST != nullptr) ^ (MSSAU != nullptr)) &&
for (BasicBlock::iterator II = BB->end(); II != BB->begin();) {
       // outside of the loop.  In this case, it doesn't even matter if the
       // operands of the instruction are loop invariant.
       //
       bool FreeInLoop = false;
       if (!I.mayHaveSideEffects() &&
           isNotUsedOrFreeInLoop(I, CurLoop, SafetyInfo, TTI, FreeInLoop) &&
           canSinkOrHoistInst(I, AA, DT, CurLoop, CurAST, MSSAU, true, &Flags,
                              ORE)) {
-        if (sink(I, LI, DT, CurLoop, SafetyInfo, MSSAU, ORE)) {
+        if (sink(I, LI, DT, BFI, CurLoop, SafetyInfo, MSSAU, ORE)) {
           if (!FreeInLoop) {
             ++II;
             salvageDebugInfo(I);
             eraseInstruction(I, *SafetyInfo, CurAST, MSSAU);
           }
           Changed = true;
         }
       }
BasicBlock *getOrCreateHoistedBlock(BasicBlock *BB) {
 
     assert(CurLoop->getLoopPreheader() &&
            "Hoisting blocks should not have destroyed preheader");
     return HoistDestinationMap[BB];
   }
 };
 } // namespace
 
+// Hoisting/sinking instruction out of a loop isn't always beneficial. It's only
+// only worthwhile if the destination block is actually colder than current
+// block.
+static bool worthSinkOrHoistInst(Instruction &I, BasicBlock *DstBlock,
+                                 OptimizationRemarkEmitter *ORE,
+                                 BlockFrequencyInfo *BFI) {
+  // Check block frequency only when runtime profile is available
+  // to avoid pathological cases. With static profile, lean towards
+  // hosting because it helps canonicalize the loop for vectorizer.
+  if (!DstBlock->getParent()->hasProfileData())
+    return true;
+
+  if (!HoistSinkColdnessThreshold || !BFI)
+    return true;
+
+  BasicBlock *SrcBlock = I.getParent();
+  if (BFI->getBlockFreq(DstBlock).getFrequency() / HoistSinkColdnessThreshold >
+      BFI->getBlockFreq(SrcBlock).getFrequency()) {
+    ORE->emit([&]() {
+      return OptimizationRemarkMissed(DEBUG_TYPE, "SinkHoistInst", &I)
+             << "failed to sink or hoist instruction because containing block "
+                "has lower frequency than destination block";
+    });
+    return false;
+  }
+
+  return true;
+}
+
 /// Walk the specified region of the CFG (defined by all blocks dominated by
 /// the specified block, and that are in the current loop) in depth first
 /// order w.r.t the DominatorTree.  This allows us to visit definitions before
 /// uses, allowing us to hoist a loop body in one pass without iteration.
 ///
 bool llvm::hoistRegion(DomTreeNode *N, AAResults *AA, LoopInfo *LI,
-                       DominatorTree *DT, TargetLibraryInfo *TLI, Loop *CurLoop,
+                       DominatorTree *DT, BlockFrequencyInfo *BFI,
+                       TargetLibraryInfo *TLI, Loop *CurLoop,
                        AliasSetTracker *CurAST, MemorySSAUpdater *MSSAU,
                        ScalarEvolution *SE, ICFLoopSafetyInfo *SafetyInfo,
                        SinkAndHoistLICMFlags &Flags,
                        OptimizationRemarkEmitter *ORE) {
   // Verify inputs.
   assert(N != nullptr && AA != nullptr && LI != nullptr && DT != nullptr &&
          CurLoop != nullptr && SafetyInfo != nullptr &&
          "Unexpected input to hoistRegion.");
for (BasicBlock::iterator II = BB->begin(), E = BB->end(); II != E;) {
         if (isInstructionTriviallyDead(&I, TLI))
           eraseInstruction(I, *SafetyInfo, CurAST, MSSAU);
         Changed = true;
         continue;
       }
 
       // Try hoisting the instruction out to the preheader.  We can only do
       // this if all of the operands of the instruction are loop invariant and
-      // if it is safe to hoist the instruction.
+      // if it is safe to hoist the instruction. We also check block frequency
+      // to make sure instruction only gets hoisted into colder blocks.
       // TODO: It may be safe to hoist if we are hoisting to a conditional block
       // and we have accurately duplicated the control flow from the loop header
       // to that block.
       if (CurLoop->hasLoopInvariantOperands(&I) &&
           canSinkOrHoistInst(I, AA, DT, CurLoop, CurAST, MSSAU, true, &Flags,
                              ORE) &&
+          worthSinkOrHoistInst(I, CurLoop->getLoopPreheader(), ORE, BFI) &&
           isSafeToExecuteUnconditionally(
               I, DT, CurLoop, SafetyInfo, ORE,
               CurLoop->getLoopPreheader()->getTerminator())) {
         hoist(I, DT, CurLoop, CFH.getOrCreateHoistedBlock(BB), SafetyInfo,
               MSSAU, SE, ORE);
         HoistedInstructions.push_back(&I);
         Changed = true;
         continue;

 }
 
 /// When an instruction is found to only be used outside of the loop, this
 /// function moves it to the exit blocks and patches up SSA form as needed.
 /// This method is guaranteed to remove the original instruction from its
 /// position, and may either delete it or move it to outside of the loop.
 ///
 static bool sink(Instruction &I, LoopInfo *LI, DominatorTree *DT,
-                 const Loop *CurLoop, ICFLoopSafetyInfo *SafetyInfo,
-                 MemorySSAUpdater *MSSAU, OptimizationRemarkEmitter *ORE) {
+                 BlockFrequencyInfo *BFI, const Loop *CurLoop,
+                 ICFLoopSafetyInfo *SafetyInfo, MemorySSAUpdater *MSSAU,
+                 OptimizationRemarkEmitter *ORE) {
   LLVM_DEBUG(dbgs() << "LICM sinking instruction: " << I << "\n");
   ORE->emit([&]() {
     return OptimizationRemark(DEBUG_TYPE, "InstSunk", &I)
            << "sinking " << ore::NV("Inst", &I);
   });
   bool Changed = false;
   if (isa<LoadInst>(I))
     ++NumMovedLoads;

 #endif
 
   // Clones of this instruction. Don't create more than one per exit block!
   SmallDenseMap<BasicBlock *, Instruction *, 32> SunkCopies;
 
   // If this instruction is only used outside of the loop, then all users are
   // PHI nodes in exit blocks due to LCSSA form. Just RAUW them with clones of
   // the instruction.
+  // First check if I is worth sinking for all uses. Sink only when it is worth
+  // across all uses.
   SmallSetVector<User*, 8> Users(I.user_begin(), I.user_end());
+  SmallVector<PHINode *, 8> ExitPNs;
   for (auto *UI : Users) {
     auto *User = cast<Instruction>(UI);
 
     if (CurLoop->contains(User))
       continue;
 
     PHINode *PN = cast<PHINode>(User);
     assert(ExitBlockSet.count(PN->getParent()) &&
            "The LCSSA PHI is not in an exit block!");
+    if (!worthSinkOrHoistInst(I, PN->getParent(), ORE, BFI)) {
+      return Changed;
+    }
+
+    ExitPNs.push_back(PN);
+  }
+
+  for (auto *PN : ExitPNs) {
+
     // The PHI must be trivially replaceable.
     Instruction *New = sinkThroughTriviallyReplaceablePHI(
         PN, &I, LI, SunkCopies, SafetyInfo, CurLoop, MSSAU);
     PN->replaceAllUsesWith(New);
     eraseInstruction(*PN, *SafetyInfo, nullptr, nullptr);
     Changed = true;
   }
   return Changed;

llvm/test/Transforms/LICM/Inputs/no-hoist-prof.prof

+_Z3fooii:200:1
+ 0: 1
+ 1: 1 _Z3bari:1
+ 2: 200
+ 3: 200
+ 4: 0
+ 5: 1

llvm/test/Transforms/LICM/no-hoist-prof.ll

+; RUN: opt -enable-new-pm=1 -sample-profile -licm -S -sample-profile-file='%S/Inputs/no-hoist-prof.prof' < %s | FileCheck %s --check-prefix=CHECK-BFI-LICM
+; RUN: opt -passes=licm -S < %s | FileCheck %s --check-prefix=CHECK-LICM
+
+; Original source code:
+;
+; int bar(int);
+; int foo(int iter, int explode) {
+;   int base = bar(explode);
+;   for (int i = 0; i != iter; ++i)
+;     if (i == explode)
+;       iter = (base * base) + bar(iter);
+;   return iter;
+; }
+
+; We need debug information in this .ll in order to leverage the pgo file, so:
+; .ll generated by running `clang++ -O3 -g -S -emit-llvm`, then:
+;   - move hoisted mul back into cold section
+;   - give labels names
+;   - reindex variables
+;   - remove metadata calls, attributes, module header
+;   - remove unnecessary metadata
+
+; CHECK-LICM: .l.check.preheader:{{.*}}
+; CHECK-LICM-NEXT: {{.*}} = mul {{.*}}
+; CHECK-LICM-NEXT: br{{.*}}
+
+; CHECK-BFI-LICM: .l.cold:{{.*}}
+; CHECK-BFI-LICM-NEXT: {{.*}} = mul {{.*}}
+
+define dso_local i32 @_Z3fooii(i32, i32) local_unnamed_addr #0 !dbg !7 {
+  %3 = tail call i32 @_Z3bari(i32 %1), !dbg !19
+  %4 = icmp eq i32 %0, 0, !dbg !22
+  br i1 %4, label %.l.ret, label %.l.check.preheader, !dbg !24
+
+.l.check.preheader:
+  br label %.l.check, !dbg !24
+
+.l.ret:
+  %5 = phi i32 [ 0, %2 ], [ %12, %.l.iterate ]
+  ret i32 %5, !dbg !25
+
+.l.check:
+  %6 = phi i32 [ 0, %.l.check.preheader ], [ %13, %.l.iterate ]
+  %7 = phi i32 [ %0, %.l.check.preheader ], [ %12, %.l.iterate ]
+  %8 = icmp eq i32 %6, %1, !dbg !26
+  br i1 %8, label %.l.cold, label %.l.iterate, !dbg !28
+
+.l.cold:
+  %9 = mul nsw i32 %3, %3
+  %10 = tail call i32 @_Z3bari(i32 %7), !dbg !29
+  %11 = add nsw i32 %10, %9, !dbg !30
+  br label %.l.iterate, !dbg !31
+
+.l.iterate:
+  %12 = phi i32 [ %11, %.l.cold ], [ %7, %.l.check ]
+  %13 = add nuw nsw i32 %6, 1, !dbg !32
+  %14 = icmp eq i32 %13, %12, !dbg !22
+  br i1 %14, label %.l.ret, label %.l.check, !dbg !24, !llvm.loop !33
+}
+
+attributes #0 = { "use-sample-profile" }
+
+declare dso_local i32 @_Z3bari(i32) local_unnamed_addr #1
+
+!llvm.module.flags = !{!4}
+
+!0 = distinct !DICompileUnit(language: DW_LANG_C_plus_plus, file: !1, producer: "clang version 8.0.20181009 ", isOptimized: true, runtimeVersion: 0, emissionKind: FullDebug, nameTableKind: None)
+!1 = !DIFile(filename: "foo.cpp", directory: "/tmp/gather_pgo")
+!4 = !{i32 2, !"Debug Info Version", i32 3}
+!7 = distinct !DISubprogram(name: "foo", linkageName: "_Z3fooii", scope: !1, file: !1, line: 2, type: !8, isLocal: false, isDefinition: true, scopeLine: 2, flags: DIFlagPrototyped, isOptimized: true, unit: !0)
+!8 = !DISubroutineType(types: !9)
+!9 = !{!10, !10, !10}
+!10 = !DIBasicType(name: "int", size: 32, encoding: DW_ATE_signed)
+!16 = distinct !DILexicalBlock(scope: !7, file: !1, line: 4, column: 3)
+!19 = !DILocation(line: 3, column: 14, scope: !7)
+!22 = !DILocation(line: 4, column: 21, scope: !23)
+!23 = distinct !DILexicalBlock(scope: !16, file: !1, line: 4, column: 3)
+!24 = !DILocation(line: 4, column: 3, scope: !16)
+!25 = !DILocation(line: 7, column: 3, scope: !7)
+!26 = !DILocation(line: 5, column: 11, scope: !27)
+!27 = distinct !DILexicalBlock(scope: !23, file: !1, line: 5, column: 9)
+!28 = !DILocation(line: 5, column: 9, scope: !23)
+!29 = !DILocation(line: 6, column: 30, scope: !27)
+!30 = !DILocation(line: 6, column: 28, scope: !27)
+!31 = !DILocation(line: 6, column: 7, scope: !27)
+!32 = !DILocation(line: 4, column: 30, scope: !23)
+!33 = distinct !{!33, !24, !34}
+!34 = !DILocation(line: 6, column: 38, scope: !16)

llvm/test/Transforms/LICM/sink.ll

-; RUN: opt -S -licm < %s | FileCheck %s --check-prefix=CHECK-LICM
+; RUN: opt -S -licm -licm-coldness-threshold=0 < %s | FileCheck %s --check-prefix=CHECK-LICM
+; RUN: opt -S -licm < %s | FileCheck %s --check-prefix=CHECK-BFI-LICM
 ; RUN: opt -S -licm < %s | opt -S -loop-sink | FileCheck %s --check-prefix=CHECK-SINK
 ; RUN: opt -S < %s -passes='require<opt-remark-emit>,loop(licm),loop-sink' \
 ; RUN:     | FileCheck %s --check-prefix=CHECK-SINK
-; RUN: opt -S -licm -enable-mssa-loop-dependency=true -verify-memoryssa < %s | FileCheck %s --check-prefix=CHECK-LICM
+; RUN: opt -S -licm -licm-coldness-threshold=0 -enable-mssa-loop-dependency=true -verify-memoryssa < %s | FileCheck %s --check-prefix=CHECK-LICM
+; RUN: opt -S -licm -enable-mssa-loop-dependency=true -verify-memoryssa < %s | FileCheck %s --check-prefix=CHECK-BFI-LICM
 
 ; Original source code:
 ; int g;
 ; int foo(int p, int x) {
 ;   for (int i = 0; i != x; i++)
 ;     if (__builtin_expect(i == p, 0)) {
 ;       x += g; x *= g;
 ;     }

 
 .lr.ph.preheader:
   br label %.lr.ph
 
 ; CHECK-LICM: .lr.ph.preheader:
 ; CHECK-LICM: load i32, i32* @g
 ; CHECK-LICM: br label %.lr.ph
 
+; CHECK-BFI-LICM: .lr.ph.preheader:
+; CHECK-BFI-LICM-NOT: load i32, i32* @g
+; CHECK-BFI-LICM: br label %.lr.ph
+
 .lr.ph:
   %.03 = phi i32 [ %8, %.combine ], [ 0, %.lr.ph.preheader ]
   %.012 = phi i32 [ %.1, %.combine ], [ %1, %.lr.ph.preheader ]
   %4 = icmp eq i32 %.03, %0
   br i1 %4, label %.then, label %.combine, !prof !1
 
 .then:
   %5 = load i32, i32* @g, align 4