Hot cold splitting pass

[hiraditya]

Summary

Find cold blocks based on profile information (or optionally with static analysis).
Forward propagate profile information to all cold-blocks.
Outline a cold region.
Set calling conv and prof hint for the callsite of the outlined function.

[kparzysz]

This looks good. Do you have a testcase that demonstrates what this pass does?

lib/Transforms/IPO/HotColdSplitting.cpp

209 ↗

(On Diff #160423)

Another thing for the future development would be to find the largest cold section of the code: for example, if there are two adjacent loops that are both in a cold side of an if-statement, both of them could be outlined into the same function.

[hiraditya]

In D50658#1200708, @kparzysz wrote:

This looks good. Do you have a testcase that demonstrates what this pass does?

Working on it.

lib/Transforms/IPO/HotColdSplitting.cpp

209 ↗

(On Diff #160423)

That's a good idea! Thanks. I'll work on that. Another improvement I'm thinking of is to outline multiple regions from a function.

[sebpop]

lib/Transforms/IPO/HotColdSplitting.cpp

209 ↗

(On Diff #160423)

find cold blocks like this:

+ bool unlikelyExecuted(BasicBlock &BB) {
+    if (blockEndsInUnreachable(&BB))
+      return true;
+    // Exception handling blocks are unlikely executed.
+    if (BB.isEHPad())
+      return true;
+    for (const Instruction &I : BB)
+      if (const CallInst *CI = dyn_cast<CallInst>(&I)) {
+        // The block is cold if it calls functions tagged as cold or noreturn.
+        if (CI->hasFnAttr(Attribute::Cold) ||
+            CI->hasFnAttr(Attribute::NoReturn))
+          return true;
+
+        // Assume that inline assembly is hot code.
+        if (isa<InlineAsm>(CI->getCalledValue()))
+          return false;
+      }

and then propagate the cold block property to all the blocks only reachable from the cold blocks:

+  DenseMap<const BasicBlock *, bool> ColdBlock;
+  // First mark all function basic blocks as hot or cold.
+  for (BasicBlock &BB : *F)
+    ColdBlock[&BB] = unlikelyExecuted(BB);
+
+  // Then adjust the hot/cold partitions by adding to the cold partition all the
+  // blocks that are only reachable from cold blocks.
+  forwardPropagation(ColdBlock, F);
+

+static void
+forwardPropagation(DenseMap<const BasicBlock *, bool> &ColdBlock,
+                   Function *F) {
+  SmallVector<BasicBlock *, 8> WL;
+  DenseMap<const BasicBlock *, bool> Visited;
+  for (BasicBlock &BB : *F)
+    Visited[&BB] = false;
+
+  BasicBlock *It = &F->front();
+  if (!ColdBlock[It]) {
+    Visited[It] = true;
+    WL.push_back(It);
+    while (WL.size() > 0) {
+      It = WL.pop_back_val();
+      for (BasicBlock *Succ : It->successors())
+        // Do not visit blocks that are cold.
+        if (!ColdBlock[Succ] && !Visited[Succ]) {
+          Visited[Succ] = true;
+          WL.push_back(Succ);
+        }
+    }
+  }
+
+  // Mark all the blocks that were not visited as cold.
+  for (MachineBasicBlock &BB : *F)
+    if (!Visited[&BB])
+      ColdBlock[&BB] = true;
+}

[hiraditya]

Thanks @sebpop for the patches. I'll update them. Having a static analysis to split the blocks will definitely help when we don;t have profile.

[hiraditya]

Updated with patches from @sebpop

[sebpop]

lib/Transforms/IPO/HotColdSplitting.cpp

275 ↗

(On Diff #161380)

or ColdBlock[BB]

277 ↗

(On Diff #161380)

As Krzysztof mentioned, you need a different code here to get the largest cold region that could contain sequential loops.

You can extend the region as long as SingleExit is cold: then you ask for another exit block that post-dominates Exit, etc. recursively.

304 ↗

(On Diff #161380)

you need to pass ColdBlock map to outlineColdBlocks().

[hiraditya]

Forward propagate profile information to all cold-blocks.

[sebpop]

lib/Transforms/IPO/HotColdSplitting.cpp

166 ↗

(On Diff #161418)

As AllColdBlocks is the complement of Visited, you could return Visited and avoid this loop.
Then you would ask the negative: a block is cold if it is not in Visited.

168 ↗

(On Diff #161418)

I think this TODO should be done in the code generation where you outline cold basic blocks: see below in outlineColdBlocks ...

300 ↗

(On Diff #161418)

... implement the expansion to larger cold regions here.
Again, you can extend the region as long as SingleExit is cold: then you ask for another exit block that post-dominates Exit, etc. recursively.
Like so:

 if (PSI->isColdBB(BB, BFI) || ColdBlock.count(BB)) {
   SmallVector<BasicBlock *, 4> Region;
   BasicBlock *ExitColdRegion = nullptr;
   BasicBlock *Exit = (*PDT)[BB]->getIDom()->getBlock();
   // Estimate cold region between a BB and its dom-frontier.
   while (isSingleEntrySingleExit(BB, Exit, DT, PDT, Region) &&
              isOutlineCandidate(Region, Exit)) {
     ExitColdRegion = Exit;
     // Update Exit recursively to its dom-frontier.
     Exit = (*PDT)[Exit]->getIDom()->getBlock();
     Region.clear();
   }
   if (ExitColdRegion) {
     ++NumColdSESEFound;
     Region.clear();
     isSingleEntrySingleExit(BB, ExitColdRegion, DT, PDT, Region);
     return extractColdRegion(Region, DT, BFI, ORE);
   }
}

[hiraditya]

Suggestions from Sebastian:

Only populate hot-regions and find cold as complement of hot-region (compile time optimization)

[sebpop]

lib/Transforms/IPO/HotColdSplitting.cpp

294 ↗

(On Diff #162560)

In the patch that I posted this if condition was outside the while loop.

Please move this check outside the while loop body, otherwise you won't iterate the while loop to discover a larger cold region than the first one that we discover with (*PDT)[BB]->getIDom()->getBlock().

[hiraditya]

Fixed copy-paste error.

[hiraditya]

Added testcase and disable recursive outlining of cold-functions.

[hiraditya]

Check calling convention of outlined function to discard it form hot-cold split optimization

[dmgreen]

Hello. What version of llvm is this based on? It's still using DEBUG macros. It will need rebasing onto trunk.

[hiraditya]

I'll rebase onto top of trunk.

[hiraditya]

Rebase onto top of trunk

[hiraditya]

If there are no-more suggestions for this first draft I'd like to get this in (disabled by default) such that people can try and give feedback. Thanks!

[sebpop]

lgtm, thanks!

[thakis]

The new test fails like so on my mac laptop:

********************
FAIL: LLVM :: Transforms/HotColdSplit/split-cold-1.ll (22545 of 27683)
******************** TEST 'LLVM :: Transforms/HotColdSplit/split-cold-1.ll' FAILED ********************
Script:
--
: 'RUN: at line 1';   /Users/thakis/src/llvm-build-goma/bin/opt -hotcoldsplit -S < /Users/thakis/src/llvm-rw/test/Transforms/HotColdSplit/split-cold-1.ll | /Users/thakis/src/llvm-build-goma/bin/FileCheck /Users/thakis/src/llvm-rw/test/Transforms/HotColdSplit/split-cold-1.ll
--
Exit Code: 1

Command Output (stderr):
--
/Users/thakis/src/llvm-rw/test/Transforms/HotColdSplit/split-cold-1.ll:10:15: error: CHECK-NEXT: expected string not found in input
; CHECK-NEXT: call coldcc void @foo
              ^
<stdin>:18:11: note: scanning from here
codeRepl: ; preds = %if.end
          ^
<stdin>:26:5: note: possible intended match here
define internal void @foo_if.then12() personality i8* bitcast (i32 (...)* @__gxx_personality_v0 to i8*) {
    ^

--

Output of the pass is at http://codepad.org/R7iwxBeR

[sebpop]

I broke the check in https://reviews.llvm.org/rL341838 and fixed it in https://reviews.llvm.org/rL341839

[tejohnson]

I see that there is a new Pass Manager version of your new pass, but I don't see that it is ever being enabled in the new pass manager pipeline (or tested). Are you planning to add that?

[tejohnson]

In D50658#1240509, @tejohnson wrote:

I see that there is a new Pass Manager version of your new pass, but I don't see that it is ever being enabled in the new pass manager pipeline (or tested). Are you planning to add that?

Pinging question. It should be straightforward to add to the new PM, is that something you plan to do soon as a follow-on?

[sebpop]

In D50658#1247050, @tejohnson wrote:

In D50658#1240509, @tejohnson wrote:

I see that there is a new Pass Manager version of your new pass, but I don't see that it is ever being enabled in the new pass manager pipeline (or tested). Are you planning to add that?

Pinging question. It should be straightforward to add to the new PM, is that something you plan to do soon as a follow-on?

Sure, we will add the pass to the newPM together with a flag.
The pass will be disabled by default until we get all the bugs fixed.

[hiraditya]

Added support for new PM: https://reviews.llvm.org/D52708

[gyiu]

@hiraditya This is very similar to the PartialInlining pass based on PSI that can outline multiple cold regions in a function, something I implemented a couple of years ago. Is there a chance we can merge these two passes into one?

https://reviews.llvm.org/rL319398

llvm/trunk/include/llvm/InitializePasses.h

 void initializeGVNLegacyPassPass(PassRegistry&);
 void initializeGVNSinkLegacyPassPass(PassRegistry&);
 void initializeGlobalDCELegacyPassPass(PassRegistry&);
 void initializeGlobalMergePass(PassRegistry&);
 void initializeGlobalOptLegacyPassPass(PassRegistry&);
 void initializeGlobalSplitPass(PassRegistry&);
 void initializeGlobalsAAWrapperPassPass(PassRegistry&);
 void initializeGuardWideningLegacyPassPass(PassRegistry&);
+void initializeHotColdSplittingLegacyPassPass(PassRegistry&);
 void initializeHWAddressSanitizerPass(PassRegistry&);
 void initializeIPCPPass(PassRegistry&);
 void initializeIPSCCPLegacyPassPass(PassRegistry&);
 void initializeIRCELegacyPassPass(PassRegistry&);
 void initializeIRTranslatorPass(PassRegistry&);
 void initializeIVUsersWrapperPassPass(PassRegistry&);
 void initializeIfConverterPass(PassRegistry&);
 void initializeImplicitNullChecksPass(PassRegistry&);

llvm/trunk/include/llvm/Transforms/IPO.h

 
 //===----------------------------------------------------------------------===//
 /// createMergeFunctionsPass - This pass discovers identical functions and
 /// collapses them.
 ///
 ModulePass *createMergeFunctionsPass();
 
 //===----------------------------------------------------------------------===//
+/// createHotColdSplittingPass - This pass outlines cold blocks into a separate
+/// function(s).
+ModulePass *createHotColdSplittingPass();
+
+//===----------------------------------------------------------------------===//
 /// createPartialInliningPass - This pass inlines parts of functions.
 ///
 ModulePass *createPartialInliningPass();
 
 //===----------------------------------------------------------------------===//
 /// createBarrierNoopPass - This pass is purely a module pass barrier in a pass
 /// manager.
 ModulePass *createBarrierNoopPass();

llvm/trunk/lib/Transforms/IPO/CMakeLists.txt

add_llvm_library(LLVMipo
   ElimAvailExtern.cpp
   ExtractGV.cpp
   ForceFunctionAttrs.cpp
   FunctionAttrs.cpp
   FunctionImport.cpp
   GlobalDCE.cpp
   GlobalOpt.cpp
   GlobalSplit.cpp
+  HotColdSplitting.cpp
   IPConstantPropagation.cpp
   IPO.cpp
   InferFunctionAttrs.cpp
   InlineSimple.cpp
   Inliner.cpp
   Internalize.cpp
   LoopExtractor.cpp
   LowerTypeTests.cpp

llvm/trunk/lib/Transforms/IPO/HotColdSplitting.cpp

+//===- HotColdSplitting.cpp -- Outline Cold Regions -------------*- C++ -*-===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// Outline cold regions to a separate function.
+// TODO: Update BFI and BPI
+// TODO: Add all the outlined functions to a separate section.
+//
+//===----------------------------------------------------------------------===//
+
+#include "llvm/ADT/SmallVector.h"
+#include "llvm/ADT/Statistic.h"
+#include "llvm/Analysis/AliasAnalysis.h"
+#include "llvm/Analysis/BlockFrequencyInfo.h"
+#include "llvm/Analysis/BranchProbabilityInfo.h"
+#include "llvm/Analysis/CFG.h"
+#include "llvm/Analysis/OptimizationRemarkEmitter.h"
+#include "llvm/Analysis/PostDominators.h"
+#include "llvm/Analysis/ProfileSummaryInfo.h"
+#include "llvm/IR/BasicBlock.h"
+#include "llvm/IR/CFG.h"
+#include "llvm/IR/DataLayout.h"
+#include "llvm/IR/DiagnosticInfo.h"
+#include "llvm/IR/Dominators.h"
+#include "llvm/IR/Function.h"
+#include "llvm/IR/Instruction.h"
+#include "llvm/IR/Instructions.h"
+#include "llvm/IR/Metadata.h"
+#include "llvm/IR/Module.h"
+#include "llvm/IR/PassManager.h"
+#include "llvm/IR/Type.h"
+#include "llvm/IR/Use.h"
+#include "llvm/IR/User.h"
+#include "llvm/IR/Value.h"
+#include "llvm/Pass.h"
+#include "llvm/Support/BlockFrequency.h"
+#include "llvm/Support/BranchProbability.h"
+#include "llvm/Support/Debug.h"
+#include "llvm/Support/raw_ostream.h"
+#include "llvm/Transforms/IPO.h"
+#include "llvm/Transforms/Scalar.h"
+#include "llvm/Transforms/Utils/BasicBlockUtils.h"
+#include "llvm/Transforms/Utils/Cloning.h"
+#include "llvm/Transforms/Utils/CodeExtractor.h"
+#include "llvm/Transforms/Utils/Local.h"
+#include "llvm/Transforms/Utils/SSAUpdater.h"
+#include "llvm/Transforms/Utils/ValueMapper.h"
+#include <algorithm>
+#include <cassert>
+
+#define DEBUG_TYPE "hotcoldsplit"
+
+STATISTIC(NumColdSESEFound,
+          "Number of cold single entry single exit (SESE) regions found.");
+STATISTIC(NumColdSESEOutlined,
+          "Number of cold single entry single exit (SESE) regions outlined.");
+
+using namespace llvm;
+
+static cl::opt<bool> EnableStaticAnalyis("hot-cold-static-analysis",
+                              cl::init(true), cl::Hidden);
+
+
+namespace {
+
+struct PostDomTree : PostDomTreeBase<BasicBlock> {
+  PostDomTree(Function &F) { recalculate(F); }
+};
+
+typedef DenseSet<const BasicBlock *> DenseSetBB;
+
+// From: https://reviews.llvm.org/D22558
+// Exit is not part of the region.
+static bool isSingleEntrySingleExit(BasicBlock *Entry, const BasicBlock *Exit,
+                                    DominatorTree *DT, PostDomTree *PDT,
+                                    SmallVectorImpl<BasicBlock *> &Region) {
+  if (!DT->dominates(Entry, Exit))
+    return false;
+
+  if (!PDT->dominates(Exit, Entry))
+    return false;
+
+  Region.push_back(Entry);
+  for (auto I = df_begin(Entry), E = df_end(Entry); I != E;) {
+    if (*I == Exit) {
+      I.skipChildren();
+      continue;
+    }
+    if (!DT->dominates(Entry, *I))
+      return false;
+    Region.push_back(*I);
+    ++I;
+  }
+  return true;
+}
+
+bool blockEndsInUnreachable(const BasicBlock &BB) {
+  if (BB.empty())
+    return true;
+  const TerminatorInst *I = BB.getTerminator();
+  if (isa<ReturnInst>(I) || isa<IndirectBrInst>(I))
+    return true;
+  // Unreachable blocks do not have any successor.
+  return succ_empty(&BB);
+}
+
+static
+bool unlikelyExecuted(const BasicBlock &BB) {
+  if (blockEndsInUnreachable(BB))
+    return true;
+  // Exception handling blocks are unlikely executed.
+  if (BB.isEHPad())
+    return true;
+  for (const Instruction &I : BB)
+    if (const CallInst *CI = dyn_cast<CallInst>(&I)) {
+      // The block is cold if it calls functions tagged as cold or noreturn.
+      if (CI->hasFnAttr(Attribute::Cold) ||
+          CI->hasFnAttr(Attribute::NoReturn))
+        return true;
+
+      // Assume that inline assembly is hot code.
+      if (isa<InlineAsm>(CI->getCalledValue()))
+        return false;
+    }
+  return false;
+}
+
+static DenseSetBB getHotBlocks(Function &F) {
+  // First mark all function basic blocks as hot or cold.
+  DenseSet<const BasicBlock *> ColdBlocks;
+  for (BasicBlock &BB : F)
+    if (unlikelyExecuted(BB))
+      ColdBlocks.insert(&BB);
+  // Forward propagation.
+  DenseSetBB AllColdBlocks;
+  SmallVector<const BasicBlock *, 8> WL;
+  DenseSetBB Visited; // Track hot blocks.
+
+  const BasicBlock *It = &F.front();
+  const TerminatorInst *TI = It->getTerminator();
+  if (!ColdBlocks.count(It)) {
+    Visited.insert(It);
+    // Breadth First Search to mark edges not reachable from cold.
+    WL.push_back(It);
+    while (WL.size() > 0) {
+      It = WL.pop_back_val();
+      for (const BasicBlock *Succ : successors(TI)) {
+        // Do not visit blocks that are cold.
+        if (!ColdBlocks.count(Succ) && !Visited.count(Succ)) {
+          Visited.insert(Succ);
+          WL.push_back(Succ);
+        }
+      }
+    }
+  }
+
+  return Visited;
+}
+
+class HotColdSplitting {
+public:
+  HotColdSplitting(ProfileSummaryInfo *ProfSI,
+                   function_ref<BlockFrequencyInfo *(Function &)> GBFI,
+                   std::function<OptimizationRemarkEmitter &(Function &)> *GORE)
+      : PSI(ProfSI), GetBFI(GBFI), GetORE(GORE) {}
+  bool run(Module &M);
+
+private:
+  bool shouldOutlineFrom(const Function &F) const;
+  Function *outlineColdBlocks(Function &F,
+                              const DenseSet<const BasicBlock *> &ColdBlock,
+                              DominatorTree *DT, PostDomTree *PDT);
+  Function *extractColdRegion(const SmallVectorImpl<BasicBlock *> &Region,
+                              DominatorTree *DT, BlockFrequencyInfo *BFI,
+                              OptimizationRemarkEmitter &ORE);
+  bool isOutlineCandidate(const SmallVectorImpl<BasicBlock *> &Region,
+                          const BasicBlock *Exit) const {
+    if (!Exit)
+      return false;
+    // TODO: Find a better metric to compute the size of region being outlined.
+    if (Region.size() == 1)
+      return false;
+    // Regions with landing pads etc.
+    for (const BasicBlock *BB : Region) {
+      if (BB->isEHPad() || BB->hasAddressTaken())
+        return false;
+    }
+    return true;
+  }
+  SmallPtrSet<const Function *, 2> OutlinedFunctions;
+  ProfileSummaryInfo *PSI;
+  function_ref<BlockFrequencyInfo *(Function &)> GetBFI;
+  std::function<OptimizationRemarkEmitter &(Function &)> *GetORE;
+};
+
+class HotColdSplittingLegacyPass : public ModulePass {
+public:
+  static char ID;
+  HotColdSplittingLegacyPass() : ModulePass(ID) {
+    initializeHotColdSplittingLegacyPassPass(*PassRegistry::getPassRegistry());
+  }
+
+  void getAnalysisUsage(AnalysisUsage &AU) const override {
+    AU.addRequired<AssumptionCacheTracker>();
+    AU.addRequired<BlockFrequencyInfoWrapperPass>();
+    AU.addRequired<ProfileSummaryInfoWrapperPass>();
+  }
+
+  bool runOnModule(Module &M) override;
+};
+
+} // end anonymous namespace
+
+// Returns false if the function should not be considered for hot-cold split
+// optimization. Already outlined functions have coldcc so no need to check
+// for them here.
+bool HotColdSplitting::shouldOutlineFrom(const Function &F) const {
+  if (F.size() <= 2)
+    return false;
+
+  if (F.hasAddressTaken())
+    return false;
+
+  if (F.hasFnAttribute(Attribute::AlwaysInline))
+    return false;
+
+  if (F.hasFnAttribute(Attribute::NoInline))
+    return false;
+
+  if (F.getCallingConv() == CallingConv::Cold)
+    return false;
+
+  if (PSI->isFunctionEntryCold(&F))
+    return false;
+  return true;
+}
+
+Function *
+HotColdSplitting::extractColdRegion(const SmallVectorImpl<BasicBlock *> &Region,
+                                    DominatorTree *DT, BlockFrequencyInfo *BFI,
+                                    OptimizationRemarkEmitter &ORE) {
+  LLVM_DEBUG(for (auto *BB : Region)
+          llvm::dbgs() << "\nExtracting: " << *BB;);
+  // TODO: Pass BFI and BPI to update profile information.
+  CodeExtractor CE(Region, DT, /*AggregateArgs*/ false, nullptr, nullptr,
+                   /* AllowVarargs */ false);
+
+  SetVector<Value *> Inputs, Outputs, Sinks;
+  CE.findInputsOutputs(Inputs, Outputs, Sinks);
+
+  // Do not extract regions that have live exit variables.
+  if (Outputs.size() > 0)
+    return nullptr;
+
+  if (Function *OutF = CE.extractCodeRegion()) {
+    User *U = *OutF->user_begin();
+    CallInst *CI = cast<CallInst>(U);
+    CallSite CS(CI);
+    NumColdSESEOutlined++;
+    OutF->setCallingConv(CallingConv::Cold);
+    CS.setCallingConv(CallingConv::Cold);
+    CI->setIsNoInline();
+    LLVM_DEBUG(llvm::dbgs() << "Outlined Region at block: " << Region.front());
+    return OutF;
+  }
+
+  ORE.emit([&]() {
+    return OptimizationRemarkMissed(DEBUG_TYPE, "ExtractFailed",
+                                    &*Region[0]->begin())
+           << "Failed to extract region at block "
+           << ore::NV("Block", Region.front());
+  });
+  return nullptr;
+}
+
+// Return the function created after outlining, nullptr otherwise.
+Function *HotColdSplitting::outlineColdBlocks(Function &F,
+                                              const  DenseSetBB &HotBlock,
+                                              DominatorTree *DT,
+                                              PostDomTree *PDT) {
+  auto BFI = GetBFI(F);
+  auto &ORE = (*GetORE)(F);
+  // Walking the dominator tree allows us to find the largest
+  // cold region.
+  BasicBlock *Begin = DT->getRootNode()->getBlock();
+  for (auto I = df_begin(Begin), E = df_end(Begin); I != E; ++I) {
+    BasicBlock *BB = *I;
+    if (PSI->isColdBB(BB, BFI) || !HotBlock.count(BB)) {
+      SmallVector<BasicBlock *, 4> ValidColdRegion, Region;
+      auto *BBNode = (*PDT)[BB];
+      auto Exit = BBNode->getIDom()->getBlock();
+      // We might need a virtual exit which post-dominates all basic blocks.
+      if (!Exit)
+        continue;
+      BasicBlock *ExitColdRegion = nullptr;
+      // Estimated cold region between a BB and its dom-frontier.
+      while (isSingleEntrySingleExit(BB, Exit, DT, PDT, Region) &&
+             isOutlineCandidate(Region, Exit)) {
+        ExitColdRegion = Exit;
+        ValidColdRegion = Region;
+        Region.clear();
+        // Update Exit recursively to its dom-frontier.
+        Exit = (*PDT)[Exit]->getIDom()->getBlock();
+      }
+      if (ExitColdRegion) {
+        ++NumColdSESEFound;
+        // Candidate for outlining. FIXME: Continue outlining.
+        // FIXME: Shouldn't need uniquing, debug isSingleEntrySingleExit
+        //std::sort(ValidColdRegion.begin(), ValidColdRegion.end());
+        auto last = std::unique(ValidColdRegion.begin(), ValidColdRegion.end());
+        ValidColdRegion.erase(last, ValidColdRegion.end());
+        return extractColdRegion(ValidColdRegion, DT, BFI, ORE);
+      }
+    }
+  }
+  return nullptr;
+}
+
+bool HotColdSplitting::run(Module &M) {
+  for (auto &F : M) {
+    if (!shouldOutlineFrom(F))
+      continue;
+    DominatorTree DT(F);
+    PostDomTree PDT(F);
+    PDT.recalculate(F);
+    DenseSetBB HotBlocks;
+    if (EnableStaticAnalyis) // Static analysis of cold blocks.
+      HotBlocks = getHotBlocks(F);
+
+    auto Outlined = outlineColdBlocks(F, HotBlocks, &DT, &PDT);
+    if (Outlined)
+      OutlinedFunctions.insert(Outlined);
+  }
+  return true;
+}
+
+bool HotColdSplittingLegacyPass::runOnModule(Module &M) {
+  if (skipModule(M))
+    return false;
+  ProfileSummaryInfo *PSI =
+      getAnalysis<ProfileSummaryInfoWrapperPass>().getPSI();
+  auto GBFI = [this](Function &F) {
+    return &this->getAnalysis<BlockFrequencyInfoWrapperPass>(F).getBFI();
+  };
+  std::unique_ptr<OptimizationRemarkEmitter> ORE;
+  std::function<OptimizationRemarkEmitter &(Function &)> GetORE =
+      [&ORE](Function &F) -> OptimizationRemarkEmitter & {
+    ORE.reset(new OptimizationRemarkEmitter(&F));
+    return *ORE.get();
+  };
+
+  return HotColdSplitting(PSI, GBFI, &GetORE).run(M);
+}
+
+char HotColdSplittingLegacyPass::ID = 0;
+INITIALIZE_PASS_BEGIN(HotColdSplittingLegacyPass, "hotcoldsplit",
+                      "Hot Cold Splitting", false, false)
+INITIALIZE_PASS_DEPENDENCY(ProfileSummaryInfoWrapperPass)
+INITIALIZE_PASS_DEPENDENCY(BlockFrequencyInfoWrapperPass)
+INITIALIZE_PASS_END(HotColdSplittingLegacyPass, "hotcoldsplit",
+                    "Hot Cold Splitting", false, false)
+
+ModulePass *llvm::createHotColdSplittingPass() {
+  return new HotColdSplittingLegacyPass();
+}

llvm/trunk/lib/Transforms/IPO/IPO.cpp

void llvm::initializeIPO(PassRegistry &Registry) {
   initializeConstantMergeLegacyPassPass(Registry);
   initializeCrossDSOCFIPass(Registry);
   initializeDAEPass(Registry);
   initializeDAHPass(Registry);
   initializeForceFunctionAttrsLegacyPassPass(Registry);
   initializeGlobalDCELegacyPassPass(Registry);
   initializeGlobalOptLegacyPassPass(Registry);
   initializeGlobalSplitPass(Registry);
+  initializeHotColdSplittingLegacyPassPass(Registry);
   initializeIPCPPass(Registry);
   initializeAlwaysInlinerLegacyPassPass(Registry);
   initializeSimpleInlinerPass(Registry);
   initializeInferFunctionAttrsLegacyPassPass(Registry);
   initializeInternalizeLegacyPassPass(Registry);
   initializeLoopExtractorPass(Registry);
   initializeBlockExtractorPass(Registry);
   initializeSingleLoopExtractorPass(Registry);

llvm/trunk/lib/Transforms/IPO/PassManagerBuilder.cpp

 static cl::opt<bool> EnableUnrollAndJam("enable-unroll-and-jam",
                                         cl::init(false), cl::Hidden,
                                         cl::desc("Enable Unroll And Jam Pass"));
 
 static cl::opt<bool>
     EnablePrepareForThinLTO("prepare-for-thinlto", cl::init(false), cl::Hidden,
                             cl::desc("Enable preparation for ThinLTO."));
 
+cl::opt<bool> EnableHotColdSplit("hot-cold-split", cl::init(false), cl::Hidden,
+    cl::desc("Enable hot-cold splitting pass"));
+
+
 static cl::opt<bool> RunPGOInstrGen(
     "profile-generate", cl::init(false), cl::Hidden,
     cl::desc("Enable PGO instrumentation."));
 
 static cl::opt<std::string>
     PGOOutputFile("profile-generate-file", cl::init(""), cl::Hidden,
                       cl::desc("Specify the path of profile data file."));
 
void PassManagerBuilder::populateModulePassManager(
   bool PrepareForThinLTOUsingPGOSampleProfile =
       PrepareForThinLTO && !PGOSampleUse.empty();
   if (PrepareForThinLTOUsingPGOSampleProfile)
     DisableUnrollLoops = true;
 
   // Infer attributes about declarations if possible.
   MPM.add(createInferFunctionAttrsLegacyPass());
 
+  if (EnableHotColdSplit)
+    MPM.add(createHotColdSplittingPass());
+
   addExtensionsToPM(EP_ModuleOptimizerEarly, MPM);
 
   if (OptLevel > 2)
     MPM.add(createCallSiteSplittingPass());
 
   MPM.add(createIPSCCPPass());          // IP SCCP
   MPM.add(createCalledValuePropagationPass());
   MPM.add(createGlobalOptimizerPass()); // Optimize out global vars

llvm/trunk/test/Transforms/HotColdSplit/split-cold-1.ll

+; RUN: opt -hotcoldsplit -S < %s | FileCheck %s
+source_filename = "bugpoint-output-054409e.bc"
+target datalayout = "e-m:o-i64:64-f80:128-n8:16:32:64-S128"
+target triple = "x86_64-apple-macosx10.13.0"
+
+declare i32 @__gxx_personality_v0(...)
+
+; Outlined function is called from a basic block named codeRepl
+; CHECK: codeRepl:
+; CHECK-NEXT: call coldcc void @foo
+; Check that no recursive outlining is done.
+; CHECK-NOT: codeRepl:
+; Function Attrs: ssp uwtable
+define hidden void @foo() personality i8* bitcast (i32 (...)* @__gxx_personality_v0 to i8*) {
+entry:
+  br i1 undef, label %if.then, label %if.end
+
+if.then:                                          ; preds = %entry
+  unreachable
+
+if.end:                                           ; preds = %entry
+  br label %if.then12
+
+if.then12:                                        ; preds = %if.end
+  br label %cleanup40
+
+cleanup40:                                        ; preds = %if.then12
+  br label %return
+
+return:                                           ; preds = %cleanup40
+  ret void
+}
+
+