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

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

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

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

276

or ColdBlock[BB]

278

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.

305

you need to pass ColdBlock map to outlineColdBlocks().

[hiraditya]

Forward propagate profile information to all cold-blocks.

[sebpop]

lib/Transforms/IPO/HotColdSplitting.cpp

167

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.

169

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

301

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

295

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

include/llvm/InitializePasses.h

 void initializeGlobalSplitPass(PassRegistry&);
 void initializeGlobalsAAWrapperPassPass(PassRegistry&);
 void initializeGuardWideningLegacyPassPass(PassRegistry&);
+void initializeHotColdSplittingLegacyPassPass(PassRegistry&);
 void initializeIPCPPass(PassRegistry&);
 void initializeIPSCCPLegacyPassPass(PassRegistry&);
 void initializeIRTranslatorPass(PassRegistry&);

include/llvm/Transforms/IPO.h

 createMergeSimilarFunctionsPass(const ModuleSummaryIndex *S = nullptr);
 
 //===----------------------------------------------------------------------===//
+/// createHotColdSplittingPass - This pass outlines cold blocks into a separate
+/// function(s).
+ModulePass *createHotColdSplittingPass();
+
+//===----------------------------------------------------------------------===//
 /// createPartialInliningPass - This pass inlines parts of functions.
 ///
 ModulePass *createPartialInliningPass();

lib/Transforms/IPO/CMakeLists.txt

   GlobalDCE.cpp
   GlobalOpt.cpp
   GlobalSplit.cpp
+  HotColdSplitting.cpp
   IPConstantPropagation.cpp
   IPO.cpp
   InferFunctionAttrs.cpp

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.
+//
+//===----------------------------------------------------------------------===//
+
+#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;
+
+namespace {
+
+struct PostDomTree : PostDomTreeBase<BasicBlock> {
+  PostDomTree(Function &F) { recalculate(F); }
+};
+
+// From: https://reviews.llvm.org/D22558
+// Exit is not part of the region.
+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;
+}
+
+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);
+  Function *extractColdRegion(const SmallVectorImpl<BasicBlock *> &Region,
+                              DominatorTree *DT, BlockFrequencyInfo *BFI,
+                              OptimizationRemarkEmitter &ORE);
+  bool isOutlineCandidate(const SmallVectorImpl<BasicBlock *> &Region,
+                          const BasicBlock *Exit) const {
+    // 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;
+  }
+  SmallVector<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
+
+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 (PSI->isFunctionEntryCold(&F))
+    return false;
+  return true;
+}
+
+Function *
+HotColdSplitting::extractColdRegion(const SmallVectorImpl<BasicBlock *> &Region,
+                                    DominatorTree *DT, BlockFrequencyInfo *BFI,
+                                    OptimizationRemarkEmitter &ORE) {
+  CodeExtractor CE(Region, DT, /*AggregateArgs*/ false, BFI, 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);
+    OutlinedFunctions.push_back(OutF);
+    NumColdSESEOutlined++;
+    OutF->setCallingConv(CallingConv::Cold);
+    CS.setCallingConv(CallingConv::Cold);
+    CI->setIsNoInline();
+    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) {
+  auto BFI = GetBFI(F);
+  auto &ORE = (*GetORE)(F);
+  DominatorTree DT(F);
+  PostDomTree PDT(F);
+  PDT.recalculate(F);
+  BasicBlock *Begin = &*F.begin();
+  for (auto I = df_begin(Begin), E = df_end(Begin); I != E; ++I) {
+    BasicBlock *BB = *I;
+    if (PSI->isColdBB(BB, BFI)) {
+      // Get cold region
+      BasicBlock *Exit = PDT[BB]->getIDom()->getBlock();
+      SmallVector<BasicBlock *, 4> Region;
+      if (isSingleEntrySingleExit(BB, Exit, &DT, &PDT, Region) &&
+          isOutlineCandidate(Region, Exit)) {
+        ++NumColdSESEFound;
+        // Candidate for outlining. FIXME: Continue outlining.
+        return extractColdRegion(Region, &DT, BFI, ORE);
+      }
+    }
+  }
+  return nullptr;
+}
+
+bool HotColdSplitting::run(Module &M) {
+  for (auto &F : M) {
+    if (shouldOutlineFrom(F))
+      outlineColdBlocks(F);
+  }
+  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();
+}

lib/Transforms/IPO/IPO.cpp

   initializeGlobalDCELegacyPassPass(Registry);
   initializeGlobalOptLegacyPassPass(Registry);
   initializeGlobalSplitPass(Registry);
+  initializeHotColdSplittingLegacyPassPass(Registry);
   initializeIPCPPass(Registry);
   initializeAlwaysInlinerLegacyPassPass(Registry);
   initializeSimpleInlinerPass(Registry);