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 and path cloning.
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 if (MBB->getBBID()) {
298 BBClusterInfos.push_back(Elt: {.BBID: *(MBB->getBBID()), .ClusterID: 0, .PositionInCluster: CurrentPosition++});
299 }
300 }
301 }
302 return BBClusterInfos;
303}
304
305// This function sorts basic blocks according to the cluster's information.
306// All explicitly specified clusters of basic blocks will be ordered
307// accordingly. All non-specified BBs go into a separate "Cold" section.
308// Additionally, if exception handling landing pads end up in more than one
309// clusters, they are moved into a single "Exception" section. Eventually,
310// clusters are ordered in increasing order of their IDs, with the "Exception"
311// and "Cold" succeeding all other clusters. With -function-splitting=none, all
312// basic blocks stay in the default section instead.
313// FuncClusterInfo represents the cluster information for basic blocks. It
314// maps from BBID of basic blocks to their cluster information.
315static void
316assignSections(MachineFunction &MF,
317 const DenseMap<UniqueBBID, BBClusterInfo> &FuncClusterInfo) {
318 assert(MF.hasBBSections() && "BB Sections is not set for function.");
319 // With function splitting disabled, the profile only decides the layout and
320 // the function is emitted as a single section.
321 if (MF.getTarget().getBBSectionsType() == BasicBlockSection::List &&
322 MF.getTarget().Options.FunctionSplitting == FunctionSplittingMode::None)
323 return;
324 // This variable stores the section ID of the cluster containing eh_pads (if
325 // all eh_pads are one cluster). If more than one cluster contain eh_pads, we
326 // set it equal to ExceptionSectionID.
327 std::optional<MBBSectionID> EHPadsSectionID;
328
329 for (auto &MBB : MF) {
330 // With the 'all' option, every basic block is placed in a unique section.
331 // With the 'list' option, every basic block is placed in a section
332 // associated with its cluster.
333 if (MF.getTarget().getBBSectionsType() == llvm::BasicBlockSection::All) {
334 // If unique sections are desired for all basic blocks of the function, we
335 // set every basic block's section ID equal to its original position in
336 // the layout (which is equal to its number). This ensures that basic
337 // blocks are ordered canonically.
338 MBB.setSectionID(MBB.getNumber());
339 } else {
340 auto I = FuncClusterInfo.find(Val: *MBB.getBBID());
341 if (I != FuncClusterInfo.end()) {
342 MBB.setSectionID(I->second.ClusterID);
343 } else {
344 const TargetInstrInfo &TII =
345 *MBB.getParent()->getSubtarget().getInstrInfo();
346
347 if (TII.isMBBSafeToSplitToCold(MBB)) {
348 // BB goes into the special cold section if it is not specified in the
349 // cluster info map. If it is not safe to split, it is kept in the
350 // default section.
351 MBB.setSectionID(MBBSectionID::ColdSectionID);
352 }
353 }
354 }
355
356 if (MBB.isEHPad() && EHPadsSectionID != MBB.getSectionID() &&
357 EHPadsSectionID != MBBSectionID::ExceptionSectionID) {
358 // If we already have one cluster containing eh_pads, this must be updated
359 // to ExceptionSectionID. Otherwise, we set it equal to the current
360 // section ID.
361 EHPadsSectionID = EHPadsSectionID ? MBBSectionID::ExceptionSectionID
362 : MBB.getSectionID();
363 }
364 }
365
366 // If EHPads are in more than one section, this places all of them in the
367 // special exception section.
368 if (EHPadsSectionID == MBBSectionID::ExceptionSectionID)
369 for (auto &MBB : MF)
370 if (MBB.isEHPad())
371 MBB.setSectionID(*EHPadsSectionID);
372}
373
374void llvm::sortBasicBlocksAndUpdateBranches(
375 MachineFunction &MF, MachineBasicBlockComparator MBBCmp) {
376 [[maybe_unused]] const MachineBasicBlock *EntryBlock = &MF.front();
377 SmallVector<MachineBasicBlock *> PreLayoutFallThroughs(MF.getNumBlockIDs());
378 for (auto &MBB : MF)
379 PreLayoutFallThroughs[MBB.getNumber()] =
380 MBB.getFallThrough(/*JumpToFallThrough=*/false);
381
382 MF.sort(comp: MBBCmp);
383 assert(&MF.front() == EntryBlock &&
384 "Entry block should not be displaced by basic block sections");
385
386 // Set IsBeginSection and IsEndSection according to the assigned section IDs.
387 MF.assignBeginEndSections();
388
389 // After reordering basic blocks, we must update basic block branches to
390 // insert explicit fallthrough branches when required and optimize branches
391 // when possible.
392 updateBranches(MF, PreLayoutFallThroughs);
393}
394
395// If the exception section begins with a landing pad, that landing pad will
396// assume a zero offset (relative to @LPStart) in the LSDA. However, a value of
397// zero implies "no landing pad." This function inserts a NOP just before the EH
398// pad label to ensure a nonzero offset.
399void llvm::avoidZeroOffsetLandingPad(MachineFunction &MF) {
400 std::optional<MBBSectionID> CurrentSection;
401 auto IsFirstNonEmptyBBInSection = [&](const MachineBasicBlock &MBB) {
402 if (MBB.empty() || MBB.getSectionID() == CurrentSection)
403 return false;
404 CurrentSection = MBB.getSectionID();
405 return true;
406 };
407
408 for (auto &MBB : MF) {
409 if (IsFirstNonEmptyBBInSection(MBB) && MBB.isEHPad()) {
410 MachineBasicBlock::iterator MI = MBB.begin();
411 while (!MI->isEHLabel())
412 ++MI;
413 MF.getSubtarget().getInstrInfo()->insertNoop(MBB, MI);
414 }
415 }
416}
417
418bool llvm::hasInstrProfHashMismatch(MachineFunction &MF) {
419 if (!BBSectionsDetectSourceDrift)
420 return false;
421
422 const char MetadataName[] = "instr_prof_hash_mismatch";
423 auto *Existing = MF.getFunction().getMetadata(KindID: LLVMContext::MD_annotation);
424 if (Existing) {
425 MDTuple *Tuple = cast<MDTuple>(Val: Existing);
426 for (const auto &N : Tuple->operands())
427 if (N.equalsStr(Str: MetadataName))
428 return true;
429 }
430
431 return false;
432}
433
434/// setDescendantEHBlocksCold - This splits all EH pads and blocks reachable
435/// only by EH pad as cold. This will help mark EH pads statically cold
436/// instead of relying on profile data.
437static void setDescendantEHBlocksCold(MachineFunction &MF) {
438 DenseSet<MachineBasicBlock *> EHBlocks;
439 computeEHOnlyBlocks(F&: MF, EHBlocks);
440 for (auto Block : EHBlocks) {
441 Block->setSectionID(MBBSectionID::ColdSectionID);
442 }
443}
444
445static bool isColdBlock(const MachineBasicBlock &MBB,
446 const MachineBlockFrequencyInfo *MBFI,
447 ProfileSummaryInfo *PSI) {
448 std::optional<uint64_t> Count = MBFI->getBlockProfileCount(MBB: &MBB);
449 // For instrumentation profiles and sample profiles, we use different ways
450 // to judge whether a block is cold and should be split.
451 if (PSI->hasInstrumentationProfile() || PSI->hasCSInstrumentationProfile()) {
452 // If using instrument profile, which is deemed "accurate", no count means
453 // cold.
454 if (!Count)
455 return true;
456 if (PercentileCutoff > 0)
457 return PSI->isColdCountNthPercentile(PercentileCutoff, C: *Count);
458 // Fallthrough to end of function.
459 } else if (PSI->hasSampleProfile()) {
460 // For sample profile, no count means "do not judege coldness".
461 if (!Count)
462 return false;
463 }
464
465 return (*Count < ColdCountThreshold);
466}
467
468// Returns whether a function which does not have a basic block sections profile
469// should be split using its PGO/AutoFDO profile.
470bool BasicBlockSections::shouldSplitWithPGO(MachineFunction &MF) {
471 if (!SplitWithPGO || skipFunction(F: MF.getFunction()))
472 return false;
473
474 // We target functions with profile data. Static information in the form
475 // of exception handling code may be split to cold if user passes the
476 // mfs-split-ehcode flag.
477 if (!MF.getFunction().hasProfileData() && !SplitAllEHCode)
478 return false;
479
480 const TargetInstrInfo &TII = *MF.getSubtarget().getInstrInfo();
481 if (!TII.isFunctionSafeToSplit(MF))
482 return false;
483
484 // Do not split functions which are in the basic block sections profile, even
485 // if their profile is not used due to source drift.
486 if (MF.getTarget().getBBSectionsType() == BasicBlockSection::List &&
487 getAnalysis<BasicBlockSectionsProfileReaderWrapperPass>()
488 .getBBSPR()
489 .isFunctionHot(FuncName: MF.getName()))
490 return false;
491
492 return true;
493}
494
495// Splits a function using its PGO/AutoFDO profile: assigns the cold section to
496// cold blocks, and the default section to all the other blocks.
497void BasicBlockSections::assignColdSectionWithPGO(MachineFunction &MF) {
498 MF.setBBSectionsType(BasicBlockSection::Preset);
499
500 const TargetInstrInfo &TII = *MF.getSubtarget().getInstrInfo();
501 bool UseProfileData = MF.getFunction().hasProfileData();
502 MachineBlockFrequencyInfo *MBFI = nullptr;
503 ProfileSummaryInfo *PSI = nullptr;
504 if (UseProfileData) {
505 MBFI = &getAnalysis<MachineBlockFrequencyInfoWrapperPass>().getMBFI();
506 PSI = &getAnalysis<ProfileSummaryInfoWrapperPass>().getPSI();
507 // If we don't have a good profile (sample profile is not deemed
508 // as a "good profile") and the function is not hot, then early
509 // return. (Because we can only trust hot functions when profile
510 // quality is not good.)
511 if (PSI->hasSampleProfile() && !PSI->isFunctionHotInCallGraph(F: &MF, BFI&: *MBFI)) {
512 // Split all EH code and it's descendant statically by default.
513 if (SplitAllEHCode)
514 setDescendantEHBlocksCold(MF);
515 return;
516 }
517 }
518
519 SmallVector<MachineBasicBlock *, 2> LandingPads;
520 for (auto &MBB : MF) {
521 if (MBB.isEntryBlock())
522 continue;
523
524 if (MBB.isEHPad())
525 LandingPads.push_back(Elt: &MBB);
526 else if (UseProfileData && isColdBlock(MBB, MBFI, PSI) &&
527 TII.isMBBSafeToSplitToCold(MBB) && !SplitAllEHCode)
528 MBB.setSectionID(MBBSectionID::ColdSectionID);
529 }
530
531 // Split all EH code and it's descendant statically by default.
532 if (SplitAllEHCode)
533 setDescendantEHBlocksCold(MF);
534 // We only split out eh pads if all of them are cold.
535 else {
536 // Here we have UseProfileData == true.
537 bool HasHotLandingPads = false;
538 for (const MachineBasicBlock *LP : LandingPads) {
539 if (!isColdBlock(MBB: *LP, MBFI, PSI) || !TII.isMBBSafeToSplitToCold(MBB: *LP))
540 HasHotLandingPads = true;
541 }
542 if (!HasHotLandingPads) {
543 for (MachineBasicBlock *LP : LandingPads)
544 LP->setSectionID(MBBSectionID::ColdSectionID);
545 }
546 }
547}
548
549// Identify, arrange, and modify basic blocks which need separate sections
550// according to the specification provided by the -fbasic-block-sections flag,
551// or according to the PGO/AutoFDO profile with -function-splitting=all.
552bool BasicBlockSections::handleBBSections(MachineFunction &MF) {
553 auto BBSectionsType = MF.getTarget().getBBSectionsType();
554
555 DenseMap<UniqueBBID, BBClusterInfo> FuncClusterInfo;
556 // Check for source drift. If the source has changed since the profiles
557 // were obtained, optimizing basic blocks might be sub-optimal.
558 // This only applies to BasicBlockSection::List as it creates
559 // clusters of basic blocks using basic block ids. Source drift can
560 // invalidate these groupings leading to sub-optimal code generation with
561 // regards to performance.
562 if (BBSectionsType == BasicBlockSection::List &&
563 !hasInstrProfHashMismatch(MF)) {
564 SmallVector<BBClusterInfo> ClusterInfo;
565 if (auto *BMI = getAnalysisIfAvailable<BasicBlockMatchingAndInference>()) {
566 ClusterInfo = createBBClusterInfoForFunction(MF, BMI: *BMI);
567 } else {
568 ClusterInfo = getAnalysis<BasicBlockSectionsProfileReaderWrapperPass>()
569 .getClusterInfoForFunction(FuncName: MF.getName());
570 }
571 for (auto &BBClusterInfo : ClusterInfo) {
572 FuncClusterInfo.try_emplace(Key: BBClusterInfo.BBID, Args&: BBClusterInfo);
573 }
574 }
575
576 // A function without a basic block sections profile is split using its
577 // PGO/AutoFDO profile, if enabled.
578 const bool UsePGO =
579 BBSectionsType == BasicBlockSection::None ||
580 (BBSectionsType == BasicBlockSection::List && FuncClusterInfo.empty());
581 if (UsePGO && !shouldSplitWithPGO(MF))
582 return false;
583
584 // Renumber blocks before assigning sections and sorting them. This is useful
585 // for accessing the original layout positions and finding the original
586 // fallthroughs. Blocks which are not in any cluster keep their original
587 // order, which retains decisions made by prior passes such as
588 // MachineBlockPlacement.
589 MF.RenumberBlocks();
590
591 if (UsePGO) {
592 assignColdSectionWithPGO(MF);
593 } else {
594 MF.setBBSectionsType(BBSectionsType);
595 assignSections(MF, FuncClusterInfo);
596 }
597
598 const MachineBasicBlock &EntryBB = MF.front();
599 auto EntryBBSectionID = EntryBB.getSectionID();
600
601 // Helper function for ordering BB sections as follows:
602 // * Entry section (section including the entry block).
603 // * Regular sections (in increasing order of their Number).
604 // ...
605 // * Exception section
606 // * Cold section
607 auto MBBSectionOrder = [EntryBBSectionID](const MBBSectionID &LHS,
608 const MBBSectionID &RHS) {
609 // We make sure that the section containing the entry block precedes all the
610 // other sections.
611 if (LHS == EntryBBSectionID || RHS == EntryBBSectionID)
612 return LHS == EntryBBSectionID;
613 return LHS.Type == RHS.Type ? LHS.Number < RHS.Number : LHS.Type < RHS.Type;
614 };
615
616 // We sort all basic blocks to make sure the basic blocks of every cluster are
617 // contiguous and ordered accordingly. Furthermore, clusters are ordered in
618 // increasing order of their section IDs, with the exception and the
619 // cold section placed at the end of the function.
620 // Also, we force the entry block of the function to be placed at the
621 // beginning of the function, regardless of the requested order.
622 auto Comparator = [&](const MachineBasicBlock &X,
623 const MachineBasicBlock &Y) {
624 auto XSectionID = X.getSectionID();
625 auto YSectionID = Y.getSectionID();
626 if (XSectionID != YSectionID)
627 return MBBSectionOrder(XSectionID, YSectionID);
628 // Make sure that the entry block is placed at the beginning.
629 if (&X == &EntryBB || &Y == &EntryBB)
630 return &X == &EntryBB;
631 // If the two basic blocks are in the same section, the order is decided by
632 // their cluster and their position within the cluster. A section holds more
633 // than one cluster only with -function-splitting=none. Basic blocks which
634 // are not in any cluster come after all the profiled basic blocks of the
635 // section, in their original order. Without a basic block sections profile,
636 // all basic blocks keep their original order (they might not have BBIDs).
637 if (XSectionID.Type == MBBSectionID::SectionType::Default &&
638 !FuncClusterInfo.empty()) {
639 auto XI = FuncClusterInfo.find(Val: *X.getBBID());
640 auto YI = FuncClusterInfo.find(Val: *Y.getBBID());
641 bool XInCluster = XI != FuncClusterInfo.end();
642 bool YInCluster = YI != FuncClusterInfo.end();
643 if (XInCluster != YInCluster)
644 return XInCluster;
645 if (XInCluster)
646 return std::tie(args&: XI->second.ClusterID, args&: XI->second.PositionInCluster) <
647 std::tie(args&: YI->second.ClusterID, args&: YI->second.PositionInCluster);
648 }
649 return X.getNumber() < Y.getNumber();
650 };
651
652 sortBasicBlocksAndUpdateBranches(MF, MBBCmp: Comparator);
653 avoidZeroOffsetLandingPad(MF);
654 return true;
655}
656
657// When the BB address map needs to be generated, this renumbers basic blocks to
658// make them appear in increasing order of their IDs in the function. This
659// avoids the need to store basic block IDs in the BB address map section, since
660// they can be determined implicitly.
661bool BasicBlockSections::handleBBAddrMap(MachineFunction &MF) {
662 if (!MF.getTarget().Options.BBAddrMap)
663 return false;
664 MF.RenumberBlocks();
665 return true;
666}
667
668bool BasicBlockSections::runOnMachineFunction(MachineFunction &MF) {
669 // First handle the basic block sections.
670 auto R1 = handleBBSections(MF);
671 // Handle basic block address map after basic block sections are finalized.
672 auto R2 = handleBBAddrMap(MF);
673 return R1 || R2;
674}
675
676void BasicBlockSections::getAnalysisUsage(AnalysisUsage &AU) const {
677 AU.setPreservesAll();
678 AU.addRequired<BasicBlockSectionsProfileReaderWrapperPass>();
679 if (SplitWithPGO) {
680 AU.addRequired<MachineBlockFrequencyInfoWrapperPass>();
681 AU.addRequired<ProfileSummaryInfoWrapperPass>();
682 }
683 AU.addUsedIfAvailable<BasicBlockMatchingAndInference>();
684 AU.addUsedIfAvailable<MachineDominatorTreeWrapperPass>();
685 AU.addUsedIfAvailable<MachinePostDominatorTreeWrapperPass>();
686 MachineFunctionPass::getAnalysisUsage(AU);
687}
688
689MachineFunctionPass *llvm::createBasicBlockSectionsPass(bool SplitWithPGO) {
690 return new BasicBlockSections(SplitWithPGO);
691}
692