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/BranchProbabilityInfo.h"
28#include "llvm/Analysis/EHUtils.h"
29#include "llvm/Analysis/ProfileSummaryInfo.h"
30#include "llvm/CodeGen/BasicBlockSectionUtils.h"
31#include "llvm/CodeGen/BasicBlockSectionsProfileReader.h"
32#include "llvm/CodeGen/MachineBasicBlock.h"
33#include "llvm/CodeGen/MachineBlockFrequencyInfo.h"
34#include "llvm/CodeGen/MachineFunction.h"
35#include "llvm/CodeGen/MachineFunctionPass.h"
36#include "llvm/CodeGen/MachineModuleInfo.h"
37#include "llvm/CodeGen/Passes.h"
38#include "llvm/CodeGen/TargetInstrInfo.h"
39#include "llvm/IR/Function.h"
40#include "llvm/InitializePasses.h"
41#include "llvm/Support/CommandLine.h"
42#include <optional>
43
44using namespace llvm;
45
46// FIXME: This cutoff value is CPU dependent and should be moved to
47// TargetTransformInfo once we consider enabling this on other platforms.
48// The value is expressed as a ProfileSummaryInfo integer percentile cutoff.
49// Defaults to 999950, i.e. all blocks colder than 99.995 percentile are split.
50// The default was empirically determined to be optimal when considering cutoff
51// values between 99%-ile to 100%-ile with respect to iTLB and icache metrics on
52// Intel CPUs.
53static cl::opt<unsigned>
54 PercentileCutoff("mfs-psi-cutoff",
55 cl::desc("Percentile profile summary cutoff used to "
56 "determine cold blocks. Unused if set to zero."),
57 cl::init(Val: 999950), cl::Hidden);
58
59static cl::opt<unsigned> ColdCountThreshold(
60 "mfs-count-threshold",
61 cl::desc(
62 "Minimum number of times a block must be executed to be retained."),
63 cl::init(Val: 1), cl::Hidden);
64
65static cl::opt<bool> SplitAllEHCode(
66 "mfs-split-ehcode",
67 cl::desc("Splits all EH code and it's descendants by default."),
68 cl::init(Val: false), cl::Hidden);
69
70namespace {
71
72class MachineFunctionSplitter : public MachineFunctionPass {
73public:
74 static char ID;
75 MachineFunctionSplitter() : MachineFunctionPass(ID) {}
76
77 StringRef getPassName() const override {
78 return "Machine Function Splitter Transformation";
79 }
80
81 void getAnalysisUsage(AnalysisUsage &AU) const override;
82
83 bool runOnMachineFunction(MachineFunction &F) override;
84};
85} // end anonymous namespace
86
87/// setDescendantEHBlocksCold - This splits all EH pads and blocks reachable
88/// only by EH pad as cold. This will help mark EH pads statically cold
89/// instead of relying on profile data.
90static void setDescendantEHBlocksCold(MachineFunction &MF) {
91 DenseSet<MachineBasicBlock *> EHBlocks;
92 computeEHOnlyBlocks(F&: MF, EHBlocks);
93 for (auto Block : EHBlocks) {
94 Block->setSectionID(MBBSectionID::ColdSectionID);
95 }
96}
97
98static void finishAdjustingBasicBlocksAndLandingPads(MachineFunction &MF) {
99 auto Comparator = [](const MachineBasicBlock &X, const MachineBasicBlock &Y) {
100 return X.getSectionID().Type < Y.getSectionID().Type;
101 };
102 llvm::sortBasicBlocksAndUpdateBranches(MF, MBBCmp: Comparator);
103 llvm::avoidZeroOffsetLandingPad(MF);
104}
105
106static bool isColdBlock(const MachineBasicBlock &MBB,
107 const MachineBlockFrequencyInfo *MBFI,
108 ProfileSummaryInfo *PSI) {
109 std::optional<uint64_t> Count = MBFI->getBlockProfileCount(MBB: &MBB);
110 // For instrumentation profiles and sample profiles, we use different ways
111 // to judge whether a block is cold and should be split.
112 if (PSI->hasInstrumentationProfile() || PSI->hasCSInstrumentationProfile()) {
113 // If using instrument profile, which is deemed "accurate", no count means
114 // cold.
115 if (!Count)
116 return true;
117 if (PercentileCutoff > 0)
118 return PSI->isColdCountNthPercentile(PercentileCutoff, C: *Count);
119 // Fallthrough to end of function.
120 } else if (PSI->hasSampleProfile()) {
121 // For sample profile, no count means "do not judege coldness".
122 if (!Count)
123 return false;
124 }
125
126 return (*Count < ColdCountThreshold);
127}
128
129bool MachineFunctionSplitter::runOnMachineFunction(MachineFunction &MF) {
130 if (skipFunction(F: MF.getFunction()))
131 return false;
132
133 // Do not split functions when -basic-block-sections=all is specified.
134 if (MF.getTarget().getBBSectionsType() == llvm::BasicBlockSection::All)
135 return false;
136 // We target functions with profile data. Static information in the form
137 // of exception handling code may be split to cold if user passes the
138 // mfs-split-ehcode flag.
139 bool UseProfileData = MF.getFunction().hasProfileData();
140 if (!UseProfileData && !SplitAllEHCode)
141 return false;
142
143 const TargetInstrInfo &TII = *MF.getSubtarget().getInstrInfo();
144 if (!TII.isFunctionSafeToSplit(MF))
145 return false;
146
147 // Do not split functions with BasicBlockSections profiles as they will
148 // be split by the BasicBlockSections pass.
149 auto BBSectionsProfile =
150 getAnalysisIfAvailable<BasicBlockSectionsProfileReaderWrapperPass>();
151 if (BBSectionsProfile != nullptr &&
152 BBSectionsProfile->getBBSPR().isFunctionHot(FuncName: MF.getName()))
153 return false;
154
155 // Renumbering blocks here preserves the order of the blocks as
156 // sortBasicBlocksAndUpdateBranches uses the numeric identifier to sort
157 // blocks. Preserving the order of blocks is essential to retaining decisions
158 // made by prior passes such as MachineBlockPlacement.
159 MF.RenumberBlocks();
160 MF.setBBSectionsType(BasicBlockSection::Preset);
161
162 MachineBlockFrequencyInfo *MBFI = nullptr;
163 ProfileSummaryInfo *PSI = nullptr;
164 if (UseProfileData) {
165 MBFI = &getAnalysis<MachineBlockFrequencyInfoWrapperPass>().getMBFI();
166 PSI = &getAnalysis<ProfileSummaryInfoWrapperPass>().getPSI();
167 // If we don't have a good profile (sample profile is not deemed
168 // as a "good profile") and the function is not hot, then early
169 // return. (Because we can only trust hot functions when profile
170 // quality is not good.)
171 if (PSI->hasSampleProfile() && !PSI->isFunctionHotInCallGraph(F: &MF, BFI&: *MBFI)) {
172 // Split all EH code and it's descendant statically by default.
173 if (SplitAllEHCode)
174 setDescendantEHBlocksCold(MF);
175 finishAdjustingBasicBlocksAndLandingPads(MF);
176 return true;
177 }
178 }
179
180 SmallVector<MachineBasicBlock *, 2> LandingPads;
181 for (auto &MBB : MF) {
182 if (MBB.isEntryBlock())
183 continue;
184
185 if (MBB.isEHPad())
186 LandingPads.push_back(Elt: &MBB);
187 else if (UseProfileData && isColdBlock(MBB, MBFI, PSI) &&
188 TII.isMBBSafeToSplitToCold(MBB) && !SplitAllEHCode)
189 MBB.setSectionID(MBBSectionID::ColdSectionID);
190 }
191
192 // Split all EH code and it's descendant statically by default.
193 if (SplitAllEHCode)
194 setDescendantEHBlocksCold(MF);
195 // We only split out eh pads if all of them are cold.
196 else {
197 // Here we have UseProfileData == true.
198 bool HasHotLandingPads = false;
199 for (const MachineBasicBlock *LP : LandingPads) {
200 if (!isColdBlock(MBB: *LP, MBFI, PSI) || !TII.isMBBSafeToSplitToCold(MBB: *LP))
201 HasHotLandingPads = true;
202 }
203 if (!HasHotLandingPads) {
204 for (MachineBasicBlock *LP : LandingPads)
205 LP->setSectionID(MBBSectionID::ColdSectionID);
206 }
207 }
208
209 finishAdjustingBasicBlocksAndLandingPads(MF);
210 return true;
211}
212
213void MachineFunctionSplitter::getAnalysisUsage(AnalysisUsage &AU) const {
214 AU.addRequired<MachineModuleInfoWrapperPass>();
215 AU.addRequired<MachineBlockFrequencyInfoWrapperPass>();
216 AU.addRequired<ProfileSummaryInfoWrapperPass>();
217 AU.addUsedIfAvailable<BasicBlockSectionsProfileReaderWrapperPass>();
218}
219
220char MachineFunctionSplitter::ID = 0;
221INITIALIZE_PASS(MachineFunctionSplitter, "machine-function-splitter",
222 "Split machine functions using profile information", false,
223 false)
224
225MachineFunctionPass *llvm::createMachineFunctionSplitterPass() {
226 return new MachineFunctionSplitter();
227}
228