1//===-- BasicBlockSections.cpp ---=========--------------------------------===//
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// BasicBlockSections implementation.
10//
11// The purpose of this pass is to assign sections to basic blocks when
12// -fbasic-block-sections= option is used. Further, with profile information
13// only the subset of basic blocks with profiles are placed in separate sections
14// and the rest are grouped in a cold section. The exception handling blocks are
15// treated specially to ensure they are all in one seciton.
16//
17// This pass also implements machine function splitting
18// (-function-splitting=all). Functions without a basic block sections profile
19// are split using PGO/AutoFDO profiles: cold blocks are moved into a separate
20// section with the symbol `foo.cold`.
21//
22// Basic Block Sections
23// ====================
24//
25// With option, -fbasic-block-sections=list, every function may be split into
26// clusters of basic blocks. Every cluster will be emitted into a separate
27// section with its basic blocks sequenced in the given order. To get the
28// optimized performance, the clusters must form an optimal BB layout for the
29// function. We insert a symbol at the beginning of every cluster's section to
30// allow the linker to reorder the sections in any arbitrary sequence. A global
31// order of these sections would encapsulate the function layout.
32// For example, consider the following clusters for a function foo (consisting
33// of 6 basic blocks 0, 1, ..., 5).
34//
35// 0 2
36// 1 3 5
37//
38// * Basic blocks 0 and 2 are placed in one section with symbol `foo`
39// referencing the beginning of this section.
40// * Basic blocks 1, 3, 5 are placed in a separate section. A new symbol
41// `foo.__part.1` will reference the beginning of this section.
42// * Basic block 4 (note that it is not referenced in the list) is placed in
43// one section, and a new symbol `foo.cold` will point to it.
44//
45// There are a couple of challenges to be addressed:
46//
47// 1. The last basic block of every cluster should not have any implicit
48// fallthrough to its next basic block, as it can be reordered by the linker.
49// The compiler should make these fallthroughs explicit by adding
50// unconditional jumps..
51//
52// 2. All inter-cluster branch targets would now need to be resolved by the
53// linker as they cannot be calculated during compile time. This is done
54// using static relocations. Further, the compiler tries to use short branch
55// instructions on some ISAs for small branch offsets. This is not possible
56// for inter-cluster branches as the offset is not determined at compile
57// time, and therefore, long branch instructions have to be used for those.
58//
59// 3. Debug Information (DebugInfo) and Call Frame Information (CFI) emission
60// needs special handling with basic block sections. DebugInfo needs to be
61// emitted with more relocations as basic block sections can break a
62// function into potentially several disjoint pieces, and CFI needs to be
63// emitted per cluster. This also bloats the object file and binary sizes.
64//
65// Basic Block Address Map
66// ==================
67//
68// With -fbasic-block-address-map, we emit the offsets of BB addresses of
69// every function into the .llvm_bb_addr_map section. Along with the function
70// symbols, this allows for mapping of virtual addresses in PMU profiles back to
71// the corresponding basic blocks. This logic is implemented in AsmPrinter. This
72// pass only assigns the BBSectionType of every function to ``labels``.
73//
74// Machine Function Splitting
75// ==========================
76//
77// With -function-splitting=all, functions without a basic block sections
78// profile are split using PGO/AutoFDO profiles. Blocks deemed cold are placed
79// in a separate section prefixed with ".text.split." (see
80// -bbsections-cold-text-prefix), referenced by the symbol `foo.cold`. Grouping
81// cold blocks across functions decreases fragmentation and improves icache and
82// iTLB utilization. Such functions get the BBSectionType ``Preset``.
83//
84// For the original RFC of machine function splitting please see
85// https://groups.google.com/d/msg/llvm-dev/RUegaMg-iqc/wFAVxa6fCgAJ
86//
87//===----------------------------------------------------------------------===//
88
89#include "llvm/ADT/SmallVector.h"
90#include "llvm/ADT/StringRef.h"
91#include "llvm/Analysis/EHUtils.h"
92#include "llvm/Analysis/ProfileSummaryInfo.h"
93#include "llvm/CodeGen/BasicBlockMatchingAndInference.h"
94#include "llvm/CodeGen/BasicBlockSectionUtils.h"
95#include "llvm/CodeGen/BasicBlockSectionsProfileReader.h"
96#include "llvm/CodeGen/MachineBlockFrequencyInfo.h"
97#include "llvm/CodeGen/MachineDominators.h"
98#include "llvm/CodeGen/MachineFunction.h"
99#include "llvm/CodeGen/MachineFunctionPass.h"
100#include "llvm/CodeGen/MachinePostDominators.h"
101#include "llvm/CodeGen/Passes.h"
102#include "llvm/CodeGen/TargetInstrInfo.h"
103#include "llvm/IR/Function.h"
104#include "llvm/InitializePasses.h"
105#include "llvm/Support/CommandLine.h"
106#include "llvm/Support/UniqueBBID.h"
107#include "llvm/Target/TargetMachine.h"
108#include "llvm/Transforms/Utils/CodeLayout.h"
109#include <optional>
110
111using namespace llvm;
112
113// Placing the cold clusters in a separate section mitigates against poor
114// profiles and allows optimizations such as hugepage mapping to be applied at a
115// section granularity. Defaults to ".text.split." which is recognized by lld
116// via the `-z keep-text-section-prefix` flag.
117cl::opt<std::string> llvm::BBSectionsColdTextPrefix(
118 "bbsections-cold-text-prefix",
119 cl::desc("The text prefix to use for cold basic block clusters"),
120 cl::init(Val: ".text.split."), cl::Hidden);
121
122static cl::opt<bool> BBSectionsDetectSourceDrift(
123 "bbsections-detect-source-drift",
124 cl::desc("This checks if there is a fdo instr. profile hash "
125 "mismatch for this function"),
126 cl::init(Val: true), cl::Hidden);
127
128// FIXME: This cutoff value is CPU dependent and should be moved to
129// TargetTransformInfo once we consider enabling this on other platforms.
130// The value is expressed as a ProfileSummaryInfo integer percentile cutoff.
131// Defaults to 999950, i.e. all blocks colder than 99.995 percentile are split.
132// The default was empirically determined to be optimal when considering cutoff
133// values between 99%-ile to 100%-ile with respect to iTLB and icache metrics on
134// Intel CPUs.
135static cl::opt<unsigned>
136 PercentileCutoff("mfs-psi-cutoff",
137 cl::desc("Percentile profile summary cutoff used to "
138 "determine cold blocks. Unused if set to zero."),
139 cl::init(Val: 999950), cl::Hidden);
140
141static cl::opt<unsigned> ColdCountThreshold(
142 "mfs-count-threshold",
143 cl::desc(
144 "Minimum number of times a block must be executed to be retained."),
145 cl::init(Val: 1), cl::Hidden);
146
147static cl::opt<bool> SplitAllEHCode(
148 "mfs-split-ehcode",
149 cl::desc("Splits all EH code and it's descendants by default."),
150 cl::init(Val: false), cl::Hidden);
151
152namespace {
153
154class BasicBlockSections : public MachineFunctionPass {
155public:
156 static char ID;
157
158 explicit BasicBlockSections(bool SplitWithPGO = false)
159 : MachineFunctionPass(ID), SplitWithPGO(SplitWithPGO) {
160 initializeBasicBlockSectionsPass(*PassRegistry::getPassRegistry());
161 }
162
163 StringRef getPassName() const override {
164 return "Basic Block Sections Transformation";
165 }
166
167 void getAnalysisUsage(AnalysisUsage &AU) const override;
168
169 /// Identify basic blocks that need separate sections and prepare to emit them
170 /// accordingly.
171 bool runOnMachineFunction(MachineFunction &MF) override;
172
173private:
174 bool handleBBSections(MachineFunction &MF);
175 bool handleBBAddrMap(MachineFunction &MF);
176 bool shouldSplitWithPGO(MachineFunction &MF);
177 void assignColdSectionWithPGO(MachineFunction &MF);
178
179 // Whether functions without a basic block sections profile are split using
180 // PGO/AutoFDO profiles (-function-splitting=all).
181 const bool SplitWithPGO;
182};
183
184} // end anonymous namespace
185
186char BasicBlockSections::ID = 0;
187INITIALIZE_PASS_BEGIN(
188 BasicBlockSections, "bbsections-prepare",
189 "Prepares for basic block sections, by splitting functions "
190 "into clusters of basic blocks.",
191 false, false)
192INITIALIZE_PASS_DEPENDENCY(BasicBlockSectionsProfileReaderWrapperPass)
193INITIALIZE_PASS_DEPENDENCY(MachineBlockFrequencyInfoWrapperPass)
194INITIALIZE_PASS_DEPENDENCY(ProfileSummaryInfoWrapperPass)
195INITIALIZE_PASS_END(BasicBlockSections, "bbsections-prepare",
196 "Prepares for basic block sections, by splitting functions "
197 "into clusters of basic blocks.",
198 false, false)
199
200// This function updates and optimizes the branching instructions of every basic
201// block in a given function to account for changes in the layout.
202static void
203updateBranches(MachineFunction &MF,
204 const SmallVector<MachineBasicBlock *> &PreLayoutFallThroughs) {
205 const TargetInstrInfo *TII = MF.getSubtarget().getInstrInfo();
206 SmallVector<MachineOperand, 4> Cond;
207 for (auto &MBB : MF) {
208 auto NextMBBI = std::next(x: MBB.getIterator());
209 auto *FTMBB = PreLayoutFallThroughs[MBB.getNumber()];
210 // If this block had a fallthrough before we need an explicit unconditional
211 // branch to that block if either
212 // 1- the block ends a section, which means its next block may be
213 // reorderd by the linker, or
214 // 2- the fallthrough block is not adjacent to the block in the new
215 // order.
216 if (FTMBB && (MBB.isEndSection() || &*NextMBBI != FTMBB))
217 TII->insertUnconditionalBranch(MBB, DestBB: FTMBB, DL: MBB.findBranchDebugLoc());
218
219 // We do not optimize branches for machine basic blocks ending sections, as
220 // their adjacent block might be reordered by the linker.
221 if (MBB.isEndSection())
222 continue;
223
224 // It might be possible to optimize branches by flipping the branch
225 // condition.
226 Cond.clear();
227 MachineBasicBlock *TBB = nullptr, *FBB = nullptr; // For analyzeBranch.
228 if (TII->analyzeBranch(MBB, TBB, FBB, Cond))
229 continue;
230 MBB.updateTerminator(PreviousLayoutSuccessor: FTMBB);
231 }
232}
233
234// This function generates the machine basic block clusters of "hot" blocks.
235// Currently, only support one cluster creation.
236// TODO: Support multi-cluster creation.
237static SmallVector<BBClusterInfo>
238createBBClusterInfoForFunction(MachineFunction &MF,
239 const BasicBlockMatchingAndInference &BMI) {
240 SmallVector<BBClusterInfo> BBClusterInfos;
241 auto OptWeightInfo = BMI.getWeightInfo(FuncName: MF.getName());
242 if (!OptWeightInfo)
243 return BBClusterInfos;
244 auto BlockWeights = OptWeightInfo->BlockWeights;
245 auto EdgeWeights = OptWeightInfo->EdgeWeights;
246
247 SmallVector<const MachineBasicBlock *, 4> HotMBBs;
248 if (MF.size() <= 2) {
249 for (auto &MBB : MF) {
250 if (MBB.isEntryBlock() || BlockWeights[&MBB] > 0) {
251 HotMBBs.push_back(Elt: &MBB);
252 }
253 }
254 } else {
255 SmallVector<uint64_t, 0> BlockSizes(MF.size());
256 SmallVector<uint64_t, 0> BlockCounts(MF.size());
257 std::vector<const MachineBasicBlock *> OrigOrder;
258 OrigOrder.reserve(n: MF.size());
259 SmallVector<codelayout::EdgeCount, 0> JumpCounts;
260
261 // Renumber blocks for running the layout algorithm.
262 MF.RenumberBlocks();
263
264 // Init the MBB size and count.
265 for (auto &MBB : MF) {
266 auto NonDbgInsts =
267 instructionsWithoutDebug(It: MBB.instr_begin(), End: MBB.instr_end());
268 int NumInsts = std::distance(first: NonDbgInsts.begin(), last: NonDbgInsts.end());
269 BlockSizes[MBB.getNumber()] = 4 * NumInsts;
270 BlockCounts[MBB.getNumber()] = BlockWeights[&MBB];
271 OrigOrder.push_back(x: &MBB);
272 }
273
274 // Init the edge count.
275 for (auto &MBB : MF) {
276 for (auto *Succ : MBB.successors()) {
277 auto EdgeWeight = EdgeWeights[std::make_pair(x: &MBB, y&: Succ)];
278 JumpCounts.push_back(Elt: {.src: static_cast<uint64_t>(MBB.getNumber()),
279 .dst: static_cast<uint64_t>(Succ->getNumber()),
280 .count: EdgeWeight});
281 }
282 }
283
284 // Run the layout algorithm.
285 auto Result = computeExtTspLayout(NodeSizes: BlockSizes, NodeCounts: BlockCounts, EdgeCounts: JumpCounts);
286 for (uint64_t R : Result) {
287 auto Block = OrigOrder[R];
288 if (Block->isEntryBlock() || BlockWeights[Block] > 0)
289 HotMBBs.push_back(Elt: Block);
290 }
291 }
292
293 // Generate the "hot" basic block cluster.
294 if (!HotMBBs.empty()) {
295 unsigned CurrentPosition = 0;
296 for (auto &MBB : HotMBBs)
297 BBClusterInfos.push_back(Elt: {.BBID: *MBB->getBBID(), .ClusterID: 0, .PositionInCluster: CurrentPosition++});
298 }
299 return BBClusterInfos;
300}
301
302// This function sorts basic blocks according to the cluster's information.
303// All explicitly specified clusters of basic blocks will be ordered
304// accordingly. All non-specified BBs go into a separate "Cold" section.
305// Additionally, if exception handling landing pads end up in more than one
306// clusters, they are moved into a single "Exception" section. Eventually,
307// clusters are ordered in increasing order of their IDs, with the "Exception"
308// and "Cold" succeeding all other clusters. With -function-splitting=none, all
309// basic blocks stay in the default section instead.
310// FuncClusterInfo represents the cluster information for basic blocks. It
311// maps from BBID of basic blocks to their cluster information.
312static void
313assignSections(MachineFunction &MF,
314 const DenseMap<UniqueBBID, BBClusterInfo> &FuncClusterInfo) {
315 assert(MF.hasBBSections() && "BB Sections is not set for function.");
316 // With function splitting disabled, the profile only decides the layout and
317 // the function is emitted as a single section.
318 if (MF.getTarget().getBBSectionsType() == BasicBlockSection::List &&
319 MF.getTarget().Options.FunctionSplitting == FunctionSplittingMode::None)
320 return;
321 // This variable stores the section ID of the cluster containing eh_pads (if
322 // all eh_pads are one cluster). If more than one cluster contain eh_pads, we
323 // set it equal to ExceptionSectionID.
324 std::optional<MBBSectionID> EHPadsSectionID;
325
326 for (auto &MBB : MF) {
327 // With the 'all' option, every basic block is placed in a unique section.
328 // With the 'list' option, every basic block is placed in a section
329 // associated with its cluster.
330 if (MF.getTarget().getBBSectionsType() == llvm::BasicBlockSection::All) {
331 // If unique sections are desired for all basic blocks of the function, we
332 // set every basic block's section ID equal to its original position in
333 // the layout (which is equal to its number). This ensures that basic
334 // blocks are ordered canonically.
335 MBB.setSectionID(MBB.getNumber());
336 } else {
337 auto I = FuncClusterInfo.find(Val: *MBB.getBBID());
338 if (I != FuncClusterInfo.end()) {
339 MBB.setSectionID(I->second.ClusterID);
340 } else {
341 const TargetInstrInfo &TII =
342 *MBB.getParent()->getSubtarget().getInstrInfo();
343
344 if (TII.isMBBSafeToSplitToCold(MBB)) {
345 // BB goes into the special cold section if it is not specified in the
346 // cluster info map. If it is not safe to split, it is kept in the
347 // default section.
348 MBB.setSectionID(MBBSectionID::ColdSectionID);
349 }
350 }
351 }
352
353 if (MBB.isEHPad() && EHPadsSectionID != MBB.getSectionID() &&
354 EHPadsSectionID != MBBSectionID::ExceptionSectionID) {
355 // If we already have one cluster containing eh_pads, this must be updated
356 // to ExceptionSectionID. Otherwise, we set it equal to the current
357 // section ID.
358 EHPadsSectionID = EHPadsSectionID ? MBBSectionID::ExceptionSectionID
359 : MBB.getSectionID();
360 }
361 }
362
363 // If EHPads are in more than one section, this places all of them in the
364 // special exception section.
365 if (EHPadsSectionID == MBBSectionID::ExceptionSectionID)
366 for (auto &MBB : MF)
367 if (MBB.isEHPad())
368 MBB.setSectionID(*EHPadsSectionID);
369}
370
371void llvm::sortBasicBlocksAndUpdateBranches(
372 MachineFunction &MF, MachineBasicBlockComparator MBBCmp) {
373 [[maybe_unused]] const MachineBasicBlock *EntryBlock = &MF.front();
374 SmallVector<MachineBasicBlock *> PreLayoutFallThroughs(MF.getNumBlockIDs());
375 for (auto &MBB : MF)
376 PreLayoutFallThroughs[MBB.getNumber()] =
377 MBB.getFallThrough(/*JumpToFallThrough=*/false);
378
379 MF.sort(comp: MBBCmp);
380 assert(&MF.front() == EntryBlock &&
381 "Entry block should not be displaced by basic block sections");
382
383 // Set IsBeginSection and IsEndSection according to the assigned section IDs.
384 MF.assignBeginEndSections();
385
386 // After reordering basic blocks, we must update basic block branches to
387 // insert explicit fallthrough branches when required and optimize branches
388 // when possible.
389 updateBranches(MF, PreLayoutFallThroughs);
390}
391
392// If the exception section begins with a landing pad, that landing pad will
393// assume a zero offset (relative to @LPStart) in the LSDA. However, a value of
394// zero implies "no landing pad." This function inserts a NOP just before the EH
395// pad label to ensure a nonzero offset.
396void llvm::avoidZeroOffsetLandingPad(MachineFunction &MF) {
397 std::optional<MBBSectionID> CurrentSection;
398 auto IsFirstNonEmptyBBInSection = [&](const MachineBasicBlock &MBB) {
399 if (MBB.getFirstNonDebugInstr() == MBB.end() ||
400 MBB.getSectionID() == CurrentSection)
401 return false;
402 CurrentSection = MBB.getSectionID();
403 return true;
404 };
405
406 for (auto &MBB : MF) {
407 if (IsFirstNonEmptyBBInSection(MBB) && MBB.isEHPad()) {
408 MachineBasicBlock::iterator MI = MBB.begin();
409 while (!MI->isEHLabel())
410 ++MI;
411 MF.getSubtarget().getInstrInfo()->insertNoop(MBB, MI);
412 }
413 }
414}
415
416bool llvm::hasInstrProfHashMismatch(MachineFunction &MF) {
417 if (!BBSectionsDetectSourceDrift)
418 return false;
419
420 const char MetadataName[] = "instr_prof_hash_mismatch";
421 auto *Existing = MF.getFunction().getMetadata(KindID: LLVMContext::MD_annotation);
422 if (Existing) {
423 MDTuple *Tuple = cast<MDTuple>(Val: Existing);
424 for (const auto &N : Tuple->operands())
425 if (N.equalsStr(Str: MetadataName))
426 return true;
427 }
428
429 return false;
430}
431
432/// setDescendantEHBlocksCold - This splits all EH pads and blocks reachable
433/// only by EH pad as cold. This will help mark EH pads statically cold
434/// instead of relying on profile data.
435static void setDescendantEHBlocksCold(MachineFunction &MF) {
436 DenseSet<MachineBasicBlock *> EHBlocks;
437 computeEHOnlyBlocks(F&: MF, EHBlocks);
438 for (auto Block : EHBlocks) {
439 Block->setSectionID(MBBSectionID::ColdSectionID);
440 }
441}
442
443static bool isColdBlock(const MachineBasicBlock &MBB,
444 const MachineBlockFrequencyInfo *MBFI,
445 ProfileSummaryInfo *PSI) {
446 std::optional<uint64_t> Count = MBFI->getBlockProfileCount(MBB: &MBB);
447 // For instrumentation profiles and sample profiles, we use different ways
448 // to judge whether a block is cold and should be split.
449 if (PSI->hasInstrumentationProfile() || PSI->hasCSInstrumentationProfile()) {
450 // If using instrument profile, which is deemed "accurate", no count means
451 // cold.
452 if (!Count)
453 return true;
454 if (PercentileCutoff > 0)
455 return PSI->isColdCountNthPercentile(PercentileCutoff, C: *Count);
456 // Fallthrough to end of function.
457 } else if (PSI->hasSampleProfile()) {
458 // For sample profile, no count means "do not judege coldness".
459 if (!Count)
460 return false;
461 }
462
463 return (*Count < ColdCountThreshold);
464}
465
466// Returns whether a function which does not have a basic block sections profile
467// should be split using its PGO/AutoFDO profile.
468bool BasicBlockSections::shouldSplitWithPGO(MachineFunction &MF) {
469 if (!SplitWithPGO || skipFunction(F: MF.getFunction()))
470 return false;
471
472 // We target functions with profile data. Static information in the form
473 // of exception handling code may be split to cold if user passes the
474 // mfs-split-ehcode flag.
475 if (!MF.getFunction().hasProfileData() && !SplitAllEHCode)
476 return false;
477
478 const TargetInstrInfo &TII = *MF.getSubtarget().getInstrInfo();
479 if (!TII.isFunctionSafeToSplit(MF))
480 return false;
481
482 // Do not split functions which are in the basic block sections profile, even
483 // if their profile is not used due to source drift.
484 if (MF.getTarget().getBBSectionsType() == BasicBlockSection::List &&
485 getAnalysis<BasicBlockSectionsProfileReaderWrapperPass>()
486 .getBBSPR()
487 .isFunctionHot(FuncName: MF.getName()))
488 return false;
489
490 return true;
491}
492
493// Splits a function using its PGO/AutoFDO profile: assigns the cold section to
494// cold blocks, and the default section to all the other blocks.
495void BasicBlockSections::assignColdSectionWithPGO(MachineFunction &MF) {
496 MF.setBBSectionsType(BasicBlockSection::Preset);
497
498 const TargetInstrInfo &TII = *MF.getSubtarget().getInstrInfo();
499 bool UseProfileData = MF.getFunction().hasProfileData();
500 MachineBlockFrequencyInfo *MBFI = nullptr;
501 ProfileSummaryInfo *PSI = nullptr;
502 if (UseProfileData) {
503 MBFI = &getAnalysis<MachineBlockFrequencyInfoWrapperPass>().getMBFI();
504 PSI = &getAnalysis<ProfileSummaryInfoWrapperPass>().getPSI();
505 // If we don't have a good profile (sample profile is not deemed
506 // as a "good profile") and the function is not hot, then early
507 // return. (Because we can only trust hot functions when profile
508 // quality is not good.)
509 if (PSI->hasSampleProfile() && !PSI->isFunctionHotInCallGraph(F: &MF, BFI&: *MBFI)) {
510 // Split all EH code and it's descendant statically by default.
511 if (SplitAllEHCode)
512 setDescendantEHBlocksCold(MF);
513 return;
514 }
515 }
516
517 SmallVector<MachineBasicBlock *, 2> LandingPads;
518 for (auto &MBB : MF) {
519 if (MBB.isEntryBlock())
520 continue;
521
522 if (MBB.isEHPad())
523 LandingPads.push_back(Elt: &MBB);
524 else if (UseProfileData && isColdBlock(MBB, MBFI, PSI) &&
525 TII.isMBBSafeToSplitToCold(MBB) && !SplitAllEHCode)
526 MBB.setSectionID(MBBSectionID::ColdSectionID);
527 }
528
529 // Split all EH code and it's descendant statically by default.
530 if (SplitAllEHCode)
531 setDescendantEHBlocksCold(MF);
532 // We only split out eh pads if all of them are cold.
533 else {
534 // Here we have UseProfileData == true.
535 bool HasHotLandingPads = false;
536 for (const MachineBasicBlock *LP : LandingPads) {
537 if (!isColdBlock(MBB: *LP, MBFI, PSI) || !TII.isMBBSafeToSplitToCold(MBB: *LP))
538 HasHotLandingPads = true;
539 }
540 if (!HasHotLandingPads) {
541 for (MachineBasicBlock *LP : LandingPads)
542 LP->setSectionID(MBBSectionID::ColdSectionID);
543 }
544 }
545}
546
547// Identify, arrange, and modify basic blocks which need separate sections
548// according to the specification provided by the -fbasic-block-sections flag,
549// or according to the PGO/AutoFDO profile with -function-splitting=all.
550bool BasicBlockSections::handleBBSections(MachineFunction &MF) {
551 auto BBSectionsType = MF.getTarget().getBBSectionsType();
552
553 DenseMap<UniqueBBID, BBClusterInfo> FuncClusterInfo;
554 // Check for source drift. If the source has changed since the profiles
555 // were obtained, optimizing basic blocks might be sub-optimal.
556 // This only applies to BasicBlockSection::List as it creates
557 // clusters of basic blocks using basic block ids. Source drift can
558 // invalidate these groupings leading to sub-optimal code generation with
559 // regards to performance.
560 if (BBSectionsType == BasicBlockSection::List &&
561 !hasInstrProfHashMismatch(MF)) {
562 SmallVector<BBClusterInfo> ClusterInfo;
563 if (auto *BMI = getAnalysisIfAvailable<BasicBlockMatchingAndInference>()) {
564 ClusterInfo = createBBClusterInfoForFunction(MF, BMI: *BMI);
565 } else {
566 ClusterInfo = getAnalysis<BasicBlockSectionsProfileReaderWrapperPass>()
567 .getClusterInfoForFunction(FuncName: MF.getName());
568 }
569 for (auto &BBClusterInfo : ClusterInfo) {
570 FuncClusterInfo.try_emplace(Key: BBClusterInfo.BBID, Args&: BBClusterInfo);
571 }
572 }
573
574 // A function without a basic block sections profile is split using its
575 // PGO/AutoFDO profile, if enabled.
576 const bool UsePGO =
577 BBSectionsType == BasicBlockSection::None ||
578 (BBSectionsType == BasicBlockSection::List && FuncClusterInfo.empty());
579 if (UsePGO && !shouldSplitWithPGO(MF))
580 return false;
581
582 // Renumber blocks before assigning sections and sorting them. This is useful
583 // for accessing the original layout positions and finding the original
584 // fallthroughs. Blocks which are not in any cluster keep their original
585 // order, which retains decisions made by prior passes such as
586 // MachineBlockPlacement.
587 MF.RenumberBlocks();
588
589 if (UsePGO) {
590 assignColdSectionWithPGO(MF);
591 } else {
592 MF.setBBSectionsType(BBSectionsType);
593 assignSections(MF, FuncClusterInfo);
594 }
595
596 const MachineBasicBlock &EntryBB = MF.front();
597 auto EntryBBSectionID = EntryBB.getSectionID();
598
599 // Helper function for ordering BB sections as follows:
600 // * Entry section (section including the entry block).
601 // * Regular sections (in increasing order of their Number).
602 // ...
603 // * Exception section
604 // * Cold section
605 auto MBBSectionOrder = [EntryBBSectionID](const MBBSectionID &LHS,
606 const MBBSectionID &RHS) {
607 // We make sure that the section containing the entry block precedes all the
608 // other sections.
609 if (LHS == EntryBBSectionID || RHS == EntryBBSectionID)
610 return LHS == EntryBBSectionID;
611 return LHS.Type == RHS.Type ? LHS.Number < RHS.Number : LHS.Type < RHS.Type;
612 };
613
614 // We sort all basic blocks to make sure the basic blocks of every cluster are
615 // contiguous and ordered accordingly. Furthermore, clusters are ordered in
616 // increasing order of their section IDs, with the exception and the
617 // cold section placed at the end of the function.
618 // Also, we force the entry block of the function to be placed at the
619 // beginning of the function, regardless of the requested order.
620 auto Comparator = [&](const MachineBasicBlock &X,
621 const MachineBasicBlock &Y) {
622 auto XSectionID = X.getSectionID();
623 auto YSectionID = Y.getSectionID();
624 if (XSectionID != YSectionID)
625 return MBBSectionOrder(XSectionID, YSectionID);
626 // Make sure that the entry block is placed at the beginning.
627 if (&X == &EntryBB || &Y == &EntryBB)
628 return &X == &EntryBB;
629 // If the two basic blocks are in the same section, the order is decided by
630 // their cluster and their position within the cluster. A section holds more
631 // than one cluster only with -function-splitting=none. Basic blocks which
632 // are not in any cluster come after all the profiled basic blocks of the
633 // section, in their original order. Without a basic block sections profile,
634 // all basic blocks keep their original order (they might not have BBIDs).
635 if (XSectionID.Type == MBBSectionID::SectionType::Default &&
636 !FuncClusterInfo.empty()) {
637 auto XI = FuncClusterInfo.find(Val: *X.getBBID());
638 auto YI = FuncClusterInfo.find(Val: *Y.getBBID());
639 bool XInCluster = XI != FuncClusterInfo.end();
640 bool YInCluster = YI != FuncClusterInfo.end();
641 if (XInCluster != YInCluster)
642 return XInCluster;
643 if (XInCluster)
644 return std::tie(args&: XI->second.ClusterID, args&: XI->second.PositionInCluster) <
645 std::tie(args&: YI->second.ClusterID, args&: YI->second.PositionInCluster);
646 }
647 return X.getNumber() < Y.getNumber();
648 };
649
650 sortBasicBlocksAndUpdateBranches(MF, MBBCmp: Comparator);
651 avoidZeroOffsetLandingPad(MF);
652 return true;
653}
654
655// When the BB address map needs to be generated, this renumbers basic blocks to
656// make them appear in increasing order of their IDs in the function. This
657// avoids the need to store basic block IDs in the BB address map section, since
658// they can be determined implicitly.
659bool BasicBlockSections::handleBBAddrMap(MachineFunction &MF) {
660 if (!MF.getTarget().Options.BBAddrMap)
661 return false;
662 MF.RenumberBlocks();
663 return true;
664}
665
666bool BasicBlockSections::runOnMachineFunction(MachineFunction &MF) {
667 // First handle the basic block sections.
668 auto R1 = handleBBSections(MF);
669 // Handle basic block address map after basic block sections are finalized.
670 auto R2 = handleBBAddrMap(MF);
671 return R1 || R2;
672}
673
674void BasicBlockSections::getAnalysisUsage(AnalysisUsage &AU) const {
675 AU.setPreservesAll();
676 AU.addRequired<BasicBlockSectionsProfileReaderWrapperPass>();
677 if (SplitWithPGO) {
678 AU.addRequired<MachineBlockFrequencyInfoWrapperPass>();
679 AU.addRequired<ProfileSummaryInfoWrapperPass>();
680 }
681 AU.addUsedIfAvailable<BasicBlockMatchingAndInference>();
682 AU.addUsedIfAvailable<MachineDominatorTreeWrapperPass>();
683 AU.addUsedIfAvailable<MachinePostDominatorTreeWrapperPass>();
684 MachineFunctionPass::getAnalysisUsage(AU);
685}
686
687MachineFunctionPass *llvm::createBasicBlockSectionsPass(bool SplitWithPGO) {
688 return new BasicBlockSections(SplitWithPGO);
689}
690