[HotColdSplitting] Use TTI to inform outlining threshold

[vsk]

Summary

Using TargetTransformInfo allows the splitting pass to factor in the
code size cost of instructions as it decides whether or not outlining is
profitable.

This did not regress the overall amount of outlining seen on the handful
of internal frameworks I tested.

Thanks to Jun Bum Lim for suggesting this!

[vsk]

• Move a test that's particularly X86-specific into an X86 directory.

[sebpop]

Looks good to me.

llvm/lib/Transforms/IPO/HotColdSplitting.cpp

70

You may want to tune the magic constant 3 for the new way of computing code size.

llvm/lib/Transforms/IPO/HotColdSplitting.cpp

 STATISTIC(NumColdRegionsFound, "Number of cold regions found.");
 STATISTIC(NumColdRegionsOutlined, "Number of cold regions outlined.");
 
 using namespace llvm;
 
 static cl::opt<bool> EnableStaticAnalyis("hot-cold-static-analysis",
                               cl::init(true), cl::Hidden);
 
-static cl::opt<unsigned> MinOutliningInstCount(
-    "min-outlining-inst-count", cl::init(3), cl::Hidden,
-    cl::desc("Minimum number of instructions needed for a single-block region "
-             "to be an outlining candidate"));
+static cl::opt<int>
+    MinOutliningThreshold("min-outlining-thresh", cl::init(3), cl::Hidden,
+                          cl::desc("Code size threshold for outlining within a "
+                                   "single BB (as a multiple of TCC_Basic)"));
 
 namespace {
 
 struct PostDomTree : PostDomTreeBase<BasicBlock> {
   PostDomTree(Function &F) { recalculate(F); }
 };
 
 /// A sequence of basic blocks.
static bool unlikelyExecuted(const BasicBlock &BB) {
   return false;
 }
 
 /// Check whether it's safe to outline \p BB.
 static bool mayExtractBlock(const BasicBlock &BB) {
   return !BB.hasAddressTaken();
 }
 
-/// Check whether \p BB has at least \p Min non-debug, non-terminator
-/// instructions.
-static bool hasMinimumInstCount(const BasicBlock &BB, unsigned Min) {
-  unsigned Count = 0;
+/// Check whether \p BB is profitable to outline (i.e. its code size cost meets
+/// the threshold set in \p MinOutliningThreshold).
+static bool isProfitableToOutline(const BasicBlock &BB,
+                                  TargetTransformInfo &TTI) {
+  int Cost = 0;
   for (const Instruction &I : BB) {
     if (isa<DbgInfoIntrinsic>(&I) || &I == BB.getTerminator())
       continue;
-    if (++Count >= Min)
+
+    Cost += TTI.getInstructionCost(&I, TargetTransformInfo::TCK_CodeSize);
+
+    if (Cost >= (MinOutliningThreshold * TargetTransformInfo::TCC_Basic))
       return true;
   }
   return false;
 }
 
 /// Identify the maximal region of cold blocks which includes \p SinkBB.
 ///
 /// Include all blocks post-dominated by \p SinkBB, \p SinkBB itself, and all
 /// blocks dominated by \p SinkBB. Exclude all other blocks, and blocks which
 /// cannot be outlined.
 ///
 /// Return an empty sequence if the cold region is too small to outline, or if
 /// the cold region has no warm predecessors.
-static BlockSequence
-findMaximalColdRegion(BasicBlock &SinkBB, DominatorTree &DT, PostDomTree &PDT) {
+static BlockSequence findMaximalColdRegion(BasicBlock &SinkBB,
+                                           TargetTransformInfo &TTI,
+                                           DominatorTree &DT,
+                                           PostDomTree &PDT) {
   // The maximal cold region.
   BlockSequence ColdRegion = {};
 
   // The ancestor farthest-away from SinkBB, and also post-dominated by it.
   BasicBlock *MaxAncestor = &SinkBB;
   unsigned MaxAncestorHeight = 0;
 
   // Visit SinkBB's ancestors using inverse DFS.
if (!SinkDom || !mayExtractBlock(SuccBB)) {
       SuccIt.skipChildren();
       continue;
     }
 
     ColdRegion.push_back(&SuccBB);
     ++SuccIt;
   }
 
-  if (ColdRegion.size() == 1 &&
-      !hasMinimumInstCount(*ColdRegion[0], MinOutliningInstCount))
+  if (ColdRegion.size() == 1 && !isProfitableToOutline(*ColdRegion[0], TTI))
     return {};
 
   return ColdRegion;
 }
 
 /// Get the largest cold region in \p F.
 static BlockSequence getLargestColdRegion(Function &F, ProfileSummaryInfo &PSI,
                                           BlockFrequencyInfo *BFI,
+                                          TargetTransformInfo &TTI,
                                           DominatorTree &DT, PostDomTree &PDT) {
   // Keep track of the largest cold region.
   BlockSequence LargestColdRegion = {};
 
   for (BasicBlock &BB : F) {
     // Identify cold blocks.
     if (!mayExtractBlock(BB))
       continue;
     bool Cold =
         PSI.isColdBB(&BB, BFI) || (EnableStaticAnalyis && unlikelyExecuted(BB));
     if (!Cold)
       continue;
 
     LLVM_DEBUG({
       dbgs() << "Found cold block:\n";
       BB.dump();
     });
 
     // Find a maximal cold region we can outline.
-    BlockSequence ColdRegion = findMaximalColdRegion(BB, DT, PDT);
+    BlockSequence ColdRegion = findMaximalColdRegion(BB, TTI, DT, PDT);
     if (ColdRegion.empty()) {
       LLVM_DEBUG(dbgs() << "  Skipping (block not profitable to extract)\n");
       continue;
     }
 
     ++NumColdRegionsFound;
 
     LLVM_DEBUG({
HotColdSplitting(ProfileSummaryInfo *ProfSI,
                    function_ref<TargetTransformInfo &(Function &)> GTTI,
                    std::function<OptimizationRemarkEmitter &(Function &)> *GORE)
       : PSI(ProfSI), GetBFI(GBFI), GetTTI(GTTI), GetORE(GORE) {}
   bool run(Module &M);
 
 private:
   bool shouldOutlineFrom(const Function &F) const;
   Function *extractColdRegion(const BlockSequence &Region, DominatorTree &DT,
-                              BlockFrequencyInfo *BFI,
+                              BlockFrequencyInfo *BFI, TargetTransformInfo &TTI,
                               OptimizationRemarkEmitter &ORE, unsigned Count);
   SmallPtrSet<const Function *, 2> OutlinedFunctions;
   ProfileSummaryInfo *PSI;
   function_ref<BlockFrequencyInfo *(Function &)> GetBFI;
   function_ref<TargetTransformInfo &(Function &)> GetTTI;
   std::function<OptimizationRemarkEmitter &(Function &)> *GetORE;
 };
 
bool HotColdSplitting::shouldOutlineFrom(const Function &F) const {
   if (PSI->isFunctionEntryCold(&F))
     return false;
   return true;
 }
 
 Function *HotColdSplitting::extractColdRegion(const BlockSequence &Region,
                                               DominatorTree &DT,
                                               BlockFrequencyInfo *BFI,
+                                              TargetTransformInfo &TTI,
                                               OptimizationRemarkEmitter &ORE,
                                               unsigned Count) {
   assert(!Region.empty());
   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, /* BFI */ nullptr,
Function *HotColdSplitting::extractColdRegion(const BlockSequence &Region,
 
   // TODO: Run MergeBasicBlockIntoOnlyPred on the outlined function.
   Function *OrigF = Region[0]->getParent();
   if (Function *OutF = CE.extractCodeRegion()) {
     User *U = *OutF->user_begin();
     CallInst *CI = cast<CallInst>(U);
     CallSite CS(CI);
     NumColdRegionsOutlined++;
-    if (GetTTI(*OutF).useColdCCForColdCall(*OutF)) {
+    if (TTI.useColdCCForColdCall(*OutF)) {
       OutF->setCallingConv(CallingConv::Cold);
       CS.setCallingConv(CallingConv::Cold);
     }
     CI->setIsNoInline();
 
     // Try to make the outlined code as small as possible on the assumption
     // that it's cold.
     assert(!OutF->hasFnAttribute(Attribute::OptimizeNone) &&
if (!shouldOutlineFrom(F)) {
       continue;
     }
 
     LLVM_DEBUG(llvm::dbgs() << "Outlining in " << F.getName() << "\n");
     DominatorTree DT(F);
     PostDomTree PDT(F);
     PDT.recalculate(F);
     BlockFrequencyInfo *BFI = GetBFI(F);
+    TargetTransformInfo &TTI = GetTTI(F);
 
-    BlockSequence ColdRegion = getLargestColdRegion(F, *PSI, BFI, DT, PDT);
+    BlockSequence ColdRegion = getLargestColdRegion(F, *PSI, BFI, TTI, DT, PDT);
     if (ColdRegion.empty())
       continue;
 
     OptimizationRemarkEmitter &ORE = (*GetORE)(F);
     Function *Outlined =
-        extractColdRegion(ColdRegion, DT, BFI, ORE, /*Count=*/1);
+        extractColdRegion(ColdRegion, DT, BFI, TTI, ORE, /*Count=*/1);
     if (Outlined) {
       OutlinedFunctions.insert(Outlined);
       Changed = true;
     }
   }
   return Changed;
 }
 

llvm/test/Transforms/HotColdSplit/outline-expensive.ll

+; The magic number 6 comes from (1 * TCC_Expensive) + (1 * CostOfCallX86).
+; RUN: opt -hotcoldsplit -min-outlining-thresh=6 -S < %s | FileCheck %s
+
+; Test that we outline even though there are only two cold instructions. TTI
+; should determine that they are expensive in terms of code size.
+
+target datalayout = "e-m:o-i64:64-f80:128-n8:16:32:64-S128"
+target triple = "x86_64-apple-macosx10.14.0"
+
+; CHECK-LABEL: @fun
+; CHECK: call void @fun.cold.1
+define void @fun(i32 %x) {
+entry:
+  br i1 undef, label %if.then, label %if.else
+
+if.then:
+  ret void
+
+if.else:
+  %y = sdiv i32 %x, 111
+  call void @sink(i32 %y)
+  ret void
+}
+
+declare void @sink(i32 %x) cold