1 //===-- MachineFunctionSplitter.cpp - Split machine functions //-----------===//
2 //
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6 //
7 //===----------------------------------------------------------------------===//
8 //
9 // \file
10 // Uses profile information to split out cold blocks.
11 //
12 // This pass splits out cold machine basic blocks from the parent function. This
13 // implementation leverages the basic block section framework. Blocks marked
14 // cold by this pass are grouped together in a separate section prefixed with
15 // ".text.unlikely.*". The linker can then group these together as a cold
16 // section. The split part of the function is a contiguous region identified by
17 // the symbol "foo.cold". Grouping all cold blocks across functions together
18 // decreases fragmentation and improves icache and itlb utilization. Note that
19 // the overall changes to the binary size are negligible; only a small number of
20 // additional jump instructions may be introduced.
21 //
22 // For the original RFC of this pass please see
23 // https://groups.google.com/d/msg/llvm-dev/RUegaMg-iqc/wFAVxa6fCgAJ
24 //===----------------------------------------------------------------------===//
25 
26 #include "llvm/ADT/SmallVector.h"
27 #include "llvm/Analysis/ProfileSummaryInfo.h"
28 #include "llvm/CodeGen/BasicBlockSectionUtils.h"
29 #include "llvm/CodeGen/MachineBasicBlock.h"
30 #include "llvm/CodeGen/MachineBlockFrequencyInfo.h"
31 #include "llvm/CodeGen/MachineFunction.h"
32 #include "llvm/CodeGen/MachineFunctionPass.h"
33 #include "llvm/CodeGen/MachineModuleInfo.h"
34 #include "llvm/CodeGen/Passes.h"
35 #include "llvm/IR/Function.h"
36 #include "llvm/InitializePasses.h"
37 #include "llvm/Support/CommandLine.h"
38 
39 using namespace llvm;
40 
41 // FIXME: This cutoff value is CPU dependent and should be moved to
42 // TargetTransformInfo once we consider enabling this on other platforms.
43 // The value is expressed as a ProfileSummaryInfo integer percentile cutoff.
44 // Defaults to 999950, i.e. all blocks colder than 99.995 percentile are split.
45 // The default was empirically determined to be optimal when considering cutoff
46 // values between 99%-ile to 100%-ile with respect to iTLB and icache metrics on
47 // Intel CPUs.
48 static cl::opt<unsigned>
49     PercentileCutoff("mfs-psi-cutoff",
50                      cl::desc("Percentile profile summary cutoff used to "
51                               "determine cold blocks. Unused if set to zero."),
52                      cl::init(999950), cl::Hidden);
53 
54 static cl::opt<unsigned> ColdCountThreshold(
55     "mfs-count-threshold",
56     cl::desc(
57         "Minimum number of times a block must be executed to be retained."),
58     cl::init(1), cl::Hidden);
59 
60 namespace {
61 
62 class MachineFunctionSplitter : public MachineFunctionPass {
63 public:
64   static char ID;
65   MachineFunctionSplitter() : MachineFunctionPass(ID) {
66     initializeMachineFunctionSplitterPass(*PassRegistry::getPassRegistry());
67   }
68 
69   StringRef getPassName() const override {
70     return "Machine Function Splitter Transformation";
71   }
72 
73   void getAnalysisUsage(AnalysisUsage &AU) const override;
74 
75   bool runOnMachineFunction(MachineFunction &F) override;
76 };
77 } // end anonymous namespace
78 
79 static bool isColdBlock(const MachineBasicBlock &MBB,
80                         const MachineBlockFrequencyInfo *MBFI,
81                         ProfileSummaryInfo *PSI) {
82   Optional<uint64_t> Count = MBFI->getBlockProfileCount(&MBB);
83   if (!Count)
84     return true;
85 
86   if (PercentileCutoff > 0) {
87     return PSI->isColdCountNthPercentile(PercentileCutoff, *Count);
88   }
89   return (*Count < ColdCountThreshold);
90 }
91 
92 bool MachineFunctionSplitter::runOnMachineFunction(MachineFunction &MF) {
93   // TODO: We only target functions with profile data. Static information may
94   // also be considered but we don't see performance improvements yet.
95   if (!MF.getFunction().hasProfileData())
96     return false;
97 
98   // TODO: We don't split functions where a section attribute has been set
99   // since the split part may not be placed in a contiguous region. It may also
100   // be more beneficial to augment the linker to ensure contiguous layout of
101   // split functions within the same section as specified by the attribute.
102   if (MF.getFunction().hasSection() ||
103       MF.getFunction().hasFnAttribute("implicit-section-name"))
104     return false;
105 
106   // We don't want to proceed further for cold functions
107   // or functions of unknown hotness. Lukewarm functions have no prefix.
108   Optional<StringRef> SectionPrefix = MF.getFunction().getSectionPrefix();
109   if (SectionPrefix && (SectionPrefix.value().equals("unlikely") ||
110                         SectionPrefix.value().equals("unknown"))) {
111     return false;
112   }
113 
114   // Renumbering blocks here preserves the order of the blocks as
115   // sortBasicBlocksAndUpdateBranches uses the numeric identifier to sort
116   // blocks. Preserving the order of blocks is essential to retaining decisions
117   // made by prior passes such as MachineBlockPlacement.
118   MF.RenumberBlocks();
119   MF.setBBSectionsType(BasicBlockSection::Preset);
120   auto *MBFI = &getAnalysis<MachineBlockFrequencyInfo>();
121   auto *PSI = &getAnalysis<ProfileSummaryInfoWrapperPass>().getPSI();
122 
123   SmallVector<MachineBasicBlock *, 2> LandingPads;
124   for (auto &MBB : MF) {
125     if (MBB.isEntryBlock())
126       continue;
127 
128     if (MBB.isEHPad())
129       LandingPads.push_back(&MBB);
130     else if (isColdBlock(MBB, MBFI, PSI))
131       MBB.setSectionID(MBBSectionID::ColdSectionID);
132   }
133 
134   // We only split out eh pads if all of them are cold.
135   bool HasHotLandingPads = false;
136   for (const MachineBasicBlock *LP : LandingPads) {
137     if (!isColdBlock(*LP, MBFI, PSI))
138       HasHotLandingPads = true;
139   }
140   if (!HasHotLandingPads) {
141     for (MachineBasicBlock *LP : LandingPads)
142       LP->setSectionID(MBBSectionID::ColdSectionID);
143   }
144 
145   auto Comparator = [](const MachineBasicBlock &X, const MachineBasicBlock &Y) {
146     return X.getSectionID().Type < Y.getSectionID().Type;
147   };
148   llvm::sortBasicBlocksAndUpdateBranches(MF, Comparator);
149   llvm::avoidZeroOffsetLandingPad(MF);
150   return true;
151 }
152 
153 void MachineFunctionSplitter::getAnalysisUsage(AnalysisUsage &AU) const {
154   AU.addRequired<MachineModuleInfoWrapperPass>();
155   AU.addRequired<MachineBlockFrequencyInfo>();
156   AU.addRequired<ProfileSummaryInfoWrapperPass>();
157 }
158 
159 char MachineFunctionSplitter::ID = 0;
160 INITIALIZE_PASS(MachineFunctionSplitter, "machine-function-splitter",
161                 "Split machine functions using profile information", false,
162                 false)
163 
164 MachineFunctionPass *llvm::createMachineFunctionSplitterPass() {
165   return new MachineFunctionSplitter();
166 }
167