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