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// Basic Block Sections
18// ====================
19//
20// With option, -fbasic-block-sections=list, every function may be split into
21// clusters of basic blocks. Every cluster will be emitted into a separate
22// section with its basic blocks sequenced in the given order. To get the
23// optimized performance, the clusters must form an optimal BB layout for the
24// function. We insert a symbol at the beginning of every cluster's section to
25// allow the linker to reorder the sections in any arbitrary sequence. A global
26// order of these sections would encapsulate the function layout.
27// For example, consider the following clusters for a function foo (consisting
28// of 6 basic blocks 0, 1, ..., 5).
29//
30// 0 2
31// 1 3 5
32//
33// * Basic blocks 0 and 2 are placed in one section with symbol `foo`
34// referencing the beginning of this section.
35// * Basic blocks 1, 3, 5 are placed in a separate section. A new symbol
36// `foo.__part.1` will reference the beginning of this section.
37// * Basic block 4 (note that it is not referenced in the list) is placed in
38// one section, and a new symbol `foo.cold` will point to it.
39//
40// There are a couple of challenges to be addressed:
41//
42// 1. The last basic block of every cluster should not have any implicit
43// fallthrough to its next basic block, as it can be reordered by the linker.
44// The compiler should make these fallthroughs explicit by adding
45// unconditional jumps..
46//
47// 2. All inter-cluster branch targets would now need to be resolved by the
48// linker as they cannot be calculated during compile time. This is done
49// using static relocations. Further, the compiler tries to use short branch
50// instructions on some ISAs for small branch offsets. This is not possible
51// for inter-cluster branches as the offset is not determined at compile
52// time, and therefore, long branch instructions have to be used for those.
53//
54// 3. Debug Information (DebugInfo) and Call Frame Information (CFI) emission
55// needs special handling with basic block sections. DebugInfo needs to be
56// emitted with more relocations as basic block sections can break a
57// function into potentially several disjoint pieces, and CFI needs to be
58// emitted per cluster. This also bloats the object file and binary sizes.
59//
60// Basic Block Address Map
61// ==================
62//
63// With -fbasic-block-address-map, we emit the offsets of BB addresses of
64// every function into the .llvm_bb_addr_map section. Along with the function
65// symbols, this allows for mapping of virtual addresses in PMU profiles back to
66// the corresponding basic blocks. This logic is implemented in AsmPrinter. This
67// pass only assigns the BBSectionType of every function to ``labels``.
68//
69//===----------------------------------------------------------------------===//
70
71#include "llvm/ADT/SmallVector.h"
72#include "llvm/ADT/StringRef.h"
73#include "llvm/CodeGen/BasicBlockMatchingAndInference.h"
74#include "llvm/CodeGen/BasicBlockSectionUtils.h"
75#include "llvm/CodeGen/BasicBlockSectionsProfileReader.h"
76#include "llvm/CodeGen/MachineDominators.h"
77#include "llvm/CodeGen/MachineFunction.h"
78#include "llvm/CodeGen/MachineFunctionPass.h"
79#include "llvm/CodeGen/MachinePostDominators.h"
80#include "llvm/CodeGen/Passes.h"
81#include "llvm/CodeGen/TargetInstrInfo.h"
82#include "llvm/InitializePasses.h"
83#include "llvm/Support/UniqueBBID.h"
84#include "llvm/Target/TargetMachine.h"
85#include "llvm/Transforms/Utils/CodeLayout.h"
86#include <optional>
87
88using namespace llvm;
89
90// Placing the cold clusters in a separate section mitigates against poor
91// profiles and allows optimizations such as hugepage mapping to be applied at a
92// section granularity. Defaults to ".text.split." which is recognized by lld
93// via the `-z keep-text-section-prefix` flag.
94cl::opt<std::string> llvm::BBSectionsColdTextPrefix(
95 "bbsections-cold-text-prefix",
96 cl::desc("The text prefix to use for cold basic block clusters"),
97 cl::init(Val: ".text.split."), cl::Hidden);
98
99static cl::opt<bool> BBSectionsDetectSourceDrift(
100 "bbsections-detect-source-drift",
101 cl::desc("This checks if there is a fdo instr. profile hash "
102 "mismatch for this function"),
103 cl::init(Val: true), cl::Hidden);
104
105namespace {
106
107class BasicBlockSections : public MachineFunctionPass {
108public:
109 static char ID;
110
111 BasicBlockSectionsProfileReaderWrapperPass *BBSectionsProfileReader = nullptr;
112
113 BasicBlockSections() : MachineFunctionPass(ID) {}
114
115 StringRef getPassName() const override {
116 return "Basic Block Sections Analysis";
117 }
118
119 void getAnalysisUsage(AnalysisUsage &AU) const override;
120
121 /// Identify basic blocks that need separate sections and prepare to emit them
122 /// accordingly.
123 bool runOnMachineFunction(MachineFunction &MF) override;
124
125private:
126 bool handleBBSections(MachineFunction &MF);
127 bool handleBBAddrMap(MachineFunction &MF);
128};
129
130} // end anonymous namespace
131
132char BasicBlockSections::ID = 0;
133INITIALIZE_PASS_BEGIN(
134 BasicBlockSections, "bbsections-prepare",
135 "Prepares for basic block sections, by splitting functions "
136 "into clusters of basic blocks.",
137 false, false)
138INITIALIZE_PASS_DEPENDENCY(BasicBlockSectionsProfileReaderWrapperPass)
139INITIALIZE_PASS_END(BasicBlockSections, "bbsections-prepare",
140 "Prepares for basic block sections, by splitting functions "
141 "into clusters of basic blocks.",
142 false, false)
143
144// This function updates and optimizes the branching instructions of every basic
145// block in a given function to account for changes in the layout.
146static void
147updateBranches(MachineFunction &MF,
148 const SmallVector<MachineBasicBlock *> &PreLayoutFallThroughs) {
149 const TargetInstrInfo *TII = MF.getSubtarget().getInstrInfo();
150 SmallVector<MachineOperand, 4> Cond;
151 for (auto &MBB : MF) {
152 auto NextMBBI = std::next(x: MBB.getIterator());
153 auto *FTMBB = PreLayoutFallThroughs[MBB.getNumber()];
154 // If this block had a fallthrough before we need an explicit unconditional
155 // branch to that block if either
156 // 1- the block ends a section, which means its next block may be
157 // reorderd by the linker, or
158 // 2- the fallthrough block is not adjacent to the block in the new
159 // order.
160 if (FTMBB && (MBB.isEndSection() || &*NextMBBI != FTMBB))
161 TII->insertUnconditionalBranch(MBB, DestBB: FTMBB, DL: MBB.findBranchDebugLoc());
162
163 // We do not optimize branches for machine basic blocks ending sections, as
164 // their adjacent block might be reordered by the linker.
165 if (MBB.isEndSection())
166 continue;
167
168 // It might be possible to optimize branches by flipping the branch
169 // condition.
170 Cond.clear();
171 MachineBasicBlock *TBB = nullptr, *FBB = nullptr; // For analyzeBranch.
172 if (TII->analyzeBranch(MBB, TBB, FBB, Cond))
173 continue;
174 MBB.updateTerminator(PreviousLayoutSuccessor: FTMBB);
175 }
176}
177
178// This function generates the machine basic block clusters of "hot" blocks.
179// Currently, only support one cluster creation.
180// TODO: Support multi-cluster creation and path cloning.
181static SmallVector<BBClusterInfo>
182createBBClusterInfoForFunction(MachineFunction &MF,
183 const BasicBlockMatchingAndInference &BMI) {
184 SmallVector<BBClusterInfo> BBClusterInfos;
185 auto OptWeightInfo = BMI.getWeightInfo(FuncName: MF.getName());
186 if (!OptWeightInfo)
187 return BBClusterInfos;
188 auto BlockWeights = OptWeightInfo->BlockWeights;
189 auto EdgeWeights = OptWeightInfo->EdgeWeights;
190
191 SmallVector<const MachineBasicBlock *, 4> HotMBBs;
192 if (MF.size() <= 2) {
193 for (auto &MBB : MF) {
194 if (MBB.isEntryBlock() || BlockWeights[&MBB] > 0) {
195 HotMBBs.push_back(Elt: &MBB);
196 }
197 }
198 } else {
199 SmallVector<uint64_t, 0> BlockSizes(MF.size());
200 SmallVector<uint64_t, 0> BlockCounts(MF.size());
201 std::vector<const MachineBasicBlock *> OrigOrder;
202 OrigOrder.reserve(n: MF.size());
203 SmallVector<codelayout::EdgeCount, 0> JumpCounts;
204
205 // Renumber blocks for running the layout algorithm.
206 MF.RenumberBlocks();
207
208 // Init the MBB size and count.
209 for (auto &MBB : MF) {
210 auto NonDbgInsts =
211 instructionsWithoutDebug(It: MBB.instr_begin(), End: MBB.instr_end());
212 int NumInsts = std::distance(first: NonDbgInsts.begin(), last: NonDbgInsts.end());
213 BlockSizes[MBB.getNumber()] = 4 * NumInsts;
214 BlockCounts[MBB.getNumber()] = BlockWeights[&MBB];
215 OrigOrder.push_back(x: &MBB);
216 }
217
218 // Init the edge count.
219 for (auto &MBB : MF) {
220 for (auto *Succ : MBB.successors()) {
221 auto EdgeWeight = EdgeWeights[std::make_pair(x: &MBB, y&: Succ)];
222 JumpCounts.push_back(Elt: {.src: static_cast<uint64_t>(MBB.getNumber()),
223 .dst: static_cast<uint64_t>(Succ->getNumber()),
224 .count: EdgeWeight});
225 }
226 }
227
228 // Run the layout algorithm.
229 auto Result = computeExtTspLayout(NodeSizes: BlockSizes, NodeCounts: BlockCounts, EdgeCounts: JumpCounts);
230 for (uint64_t R : Result) {
231 auto Block = OrigOrder[R];
232 if (Block->isEntryBlock() || BlockWeights[Block] > 0)
233 HotMBBs.push_back(Elt: Block);
234 }
235 }
236
237 // Generate the "hot" basic block cluster.
238 if (!HotMBBs.empty()) {
239 unsigned CurrentPosition = 0;
240 for (auto &MBB : HotMBBs) {
241 if (MBB->getBBID()) {
242 BBClusterInfos.push_back(Elt: {.BBID: *(MBB->getBBID()), .ClusterID: 0, .PositionInCluster: CurrentPosition++});
243 }
244 }
245 }
246 return BBClusterInfos;
247}
248
249// This function sorts basic blocks according to the cluster's information.
250// All explicitly specified clusters of basic blocks will be ordered
251// accordingly. All non-specified BBs go into a separate "Cold" section.
252// Additionally, if exception handling landing pads end up in more than one
253// clusters, they are moved into a single "Exception" section. Eventually,
254// clusters are ordered in increasing order of their IDs, with the "Exception"
255// and "Cold" succeeding all other clusters.
256// FuncClusterInfo represents the cluster information for basic blocks. It
257// maps from BBID of basic blocks to their cluster information.
258static void
259assignSections(MachineFunction &MF,
260 const DenseMap<UniqueBBID, BBClusterInfo> &FuncClusterInfo) {
261 assert(MF.hasBBSections() && "BB Sections is not set for function.");
262 // This variable stores the section ID of the cluster containing eh_pads (if
263 // all eh_pads are one cluster). If more than one cluster contain eh_pads, we
264 // set it equal to ExceptionSectionID.
265 std::optional<MBBSectionID> EHPadsSectionID;
266
267 for (auto &MBB : MF) {
268 // With the 'all' option, every basic block is placed in a unique section.
269 // With the 'list' option, every basic block is placed in a section
270 // associated with its cluster.
271 if (MF.getTarget().getBBSectionsType() == llvm::BasicBlockSection::All) {
272 // If unique sections are desired for all basic blocks of the function, we
273 // set every basic block's section ID equal to its original position in
274 // the layout (which is equal to its number). This ensures that basic
275 // blocks are ordered canonically.
276 MBB.setSectionID(MBB.getNumber());
277 } else {
278 auto I = FuncClusterInfo.find(Val: *MBB.getBBID());
279 if (I != FuncClusterInfo.end()) {
280 MBB.setSectionID(I->second.ClusterID);
281 } else {
282 const TargetInstrInfo &TII =
283 *MBB.getParent()->getSubtarget().getInstrInfo();
284
285 if (TII.isMBBSafeToSplitToCold(MBB)) {
286 // BB goes into the special cold section if it is not specified in the
287 // cluster info map.
288 MBB.setSectionID(MBBSectionID::ColdSectionID);
289 }
290 }
291 }
292
293 if (MBB.isEHPad() && EHPadsSectionID != MBB.getSectionID() &&
294 EHPadsSectionID != MBBSectionID::ExceptionSectionID) {
295 // If we already have one cluster containing eh_pads, this must be updated
296 // to ExceptionSectionID. Otherwise, we set it equal to the current
297 // section ID.
298 EHPadsSectionID = EHPadsSectionID ? MBBSectionID::ExceptionSectionID
299 : MBB.getSectionID();
300 }
301 }
302
303 // If EHPads are in more than one section, this places all of them in the
304 // special exception section.
305 if (EHPadsSectionID == MBBSectionID::ExceptionSectionID)
306 for (auto &MBB : MF)
307 if (MBB.isEHPad())
308 MBB.setSectionID(*EHPadsSectionID);
309}
310
311void llvm::sortBasicBlocksAndUpdateBranches(
312 MachineFunction &MF, MachineBasicBlockComparator MBBCmp) {
313 [[maybe_unused]] const MachineBasicBlock *EntryBlock = &MF.front();
314 SmallVector<MachineBasicBlock *> PreLayoutFallThroughs(MF.getNumBlockIDs());
315 for (auto &MBB : MF)
316 PreLayoutFallThroughs[MBB.getNumber()] =
317 MBB.getFallThrough(/*JumpToFallThrough=*/false);
318
319 MF.sort(comp: MBBCmp);
320 assert(&MF.front() == EntryBlock &&
321 "Entry block should not be displaced by basic block sections");
322
323 // Set IsBeginSection and IsEndSection according to the assigned section IDs.
324 MF.assignBeginEndSections();
325
326 // After reordering basic blocks, we must update basic block branches to
327 // insert explicit fallthrough branches when required and optimize branches
328 // when possible.
329 updateBranches(MF, PreLayoutFallThroughs);
330}
331
332// If the exception section begins with a landing pad, that landing pad will
333// assume a zero offset (relative to @LPStart) in the LSDA. However, a value of
334// zero implies "no landing pad." This function inserts a NOP just before the EH
335// pad label to ensure a nonzero offset.
336void llvm::avoidZeroOffsetLandingPad(MachineFunction &MF) {
337 std::optional<MBBSectionID> CurrentSection;
338 auto IsFirstNonEmptyBBInSection = [&](const MachineBasicBlock &MBB) {
339 if (MBB.empty() || MBB.getSectionID() == CurrentSection)
340 return false;
341 CurrentSection = MBB.getSectionID();
342 return true;
343 };
344
345 for (auto &MBB : MF) {
346 if (IsFirstNonEmptyBBInSection(MBB) && MBB.isEHPad()) {
347 MachineBasicBlock::iterator MI = MBB.begin();
348 while (!MI->isEHLabel())
349 ++MI;
350 MF.getSubtarget().getInstrInfo()->insertNoop(MBB, MI);
351 }
352 }
353}
354
355bool llvm::hasInstrProfHashMismatch(MachineFunction &MF) {
356 if (!BBSectionsDetectSourceDrift)
357 return false;
358
359 const char MetadataName[] = "instr_prof_hash_mismatch";
360 auto *Existing = MF.getFunction().getMetadata(KindID: LLVMContext::MD_annotation);
361 if (Existing) {
362 MDTuple *Tuple = cast<MDTuple>(Val: Existing);
363 for (const auto &N : Tuple->operands())
364 if (N.equalsStr(Str: MetadataName))
365 return true;
366 }
367
368 return false;
369}
370
371// Identify, arrange, and modify basic blocks which need separate sections
372// according to the specification provided by the -fbasic-block-sections flag.
373bool BasicBlockSections::handleBBSections(MachineFunction &MF) {
374 auto BBSectionsType = MF.getTarget().getBBSectionsType();
375 if (BBSectionsType == BasicBlockSection::None)
376 return false;
377
378 // Check for source drift. If the source has changed since the profiles
379 // were obtained, optimizing basic blocks might be sub-optimal.
380 // This only applies to BasicBlockSection::List as it creates
381 // clusters of basic blocks using basic block ids. Source drift can
382 // invalidate these groupings leading to sub-optimal code generation with
383 // regards to performance.
384 if (BBSectionsType == BasicBlockSection::List &&
385 hasInstrProfHashMismatch(MF))
386 return false;
387
388 DenseMap<UniqueBBID, BBClusterInfo> FuncClusterInfo;
389 if (BBSectionsType == BasicBlockSection::List) {
390 SmallVector<BBClusterInfo> ClusterInfo;
391 if (auto *BMI = getAnalysisIfAvailable<BasicBlockMatchingAndInference>()) {
392 ClusterInfo = createBBClusterInfoForFunction(MF, BMI: *BMI);
393 } else {
394 ClusterInfo = getAnalysis<BasicBlockSectionsProfileReaderWrapperPass>()
395 .getClusterInfoForFunction(FuncName: MF.getName());
396 }
397 if (ClusterInfo.empty())
398 return false;
399 for (auto &BBClusterInfo : ClusterInfo) {
400 FuncClusterInfo.try_emplace(Key: BBClusterInfo.BBID, Args&: BBClusterInfo);
401 }
402 }
403
404 // Renumber blocks before sorting them. This is useful for accessing the
405 // original layout positions and finding the original fallthroughs.
406 MF.RenumberBlocks();
407
408 MF.setBBSectionsType(BBSectionsType);
409 assignSections(MF, FuncClusterInfo);
410
411 const MachineBasicBlock &EntryBB = MF.front();
412 auto EntryBBSectionID = EntryBB.getSectionID();
413
414 // Helper function for ordering BB sections as follows:
415 // * Entry section (section including the entry block).
416 // * Regular sections (in increasing order of their Number).
417 // ...
418 // * Exception section
419 // * Cold section
420 auto MBBSectionOrder = [EntryBBSectionID](const MBBSectionID &LHS,
421 const MBBSectionID &RHS) {
422 // We make sure that the section containing the entry block precedes all the
423 // other sections.
424 if (LHS == EntryBBSectionID || RHS == EntryBBSectionID)
425 return LHS == EntryBBSectionID;
426 return LHS.Type == RHS.Type ? LHS.Number < RHS.Number : LHS.Type < RHS.Type;
427 };
428
429 // We sort all basic blocks to make sure the basic blocks of every cluster are
430 // contiguous and ordered accordingly. Furthermore, clusters are ordered in
431 // increasing order of their section IDs, with the exception and the
432 // cold section placed at the end of the function.
433 // Also, we force the entry block of the function to be placed at the
434 // beginning of the function, regardless of the requested order.
435 auto Comparator = [&](const MachineBasicBlock &X,
436 const MachineBasicBlock &Y) {
437 auto XSectionID = X.getSectionID();
438 auto YSectionID = Y.getSectionID();
439 if (XSectionID != YSectionID)
440 return MBBSectionOrder(XSectionID, YSectionID);
441 // Make sure that the entry block is placed at the beginning.
442 if (&X == &EntryBB || &Y == &EntryBB)
443 return &X == &EntryBB;
444 // If the two basic block are in the same section, the order is decided by
445 // their position within the section.
446 if (XSectionID.Type == MBBSectionID::SectionType::Default)
447 return FuncClusterInfo.lookup(Val: *X.getBBID()).PositionInCluster <
448 FuncClusterInfo.lookup(Val: *Y.getBBID()).PositionInCluster;
449 return X.getNumber() < Y.getNumber();
450 };
451
452 sortBasicBlocksAndUpdateBranches(MF, MBBCmp: Comparator);
453 avoidZeroOffsetLandingPad(MF);
454 return true;
455}
456
457// When the BB address map needs to be generated, this renumbers basic blocks to
458// make them appear in increasing order of their IDs in the function. This
459// avoids the need to store basic block IDs in the BB address map section, since
460// they can be determined implicitly.
461bool BasicBlockSections::handleBBAddrMap(MachineFunction &MF) {
462 if (!MF.getTarget().Options.BBAddrMap)
463 return false;
464 MF.RenumberBlocks();
465 return true;
466}
467
468bool BasicBlockSections::runOnMachineFunction(MachineFunction &MF) {
469 // First handle the basic block sections.
470 auto R1 = handleBBSections(MF);
471 // Handle basic block address map after basic block sections are finalized.
472 auto R2 = handleBBAddrMap(MF);
473
474 // We renumber blocks, so update the dominator tree we want to preserve.
475 if (auto *WP = getAnalysisIfAvailable<MachineDominatorTreeWrapperPass>())
476 WP->getDomTree().updateBlockNumbers();
477 if (auto *WP = getAnalysisIfAvailable<MachinePostDominatorTreeWrapperPass>())
478 WP->getPostDomTree().updateBlockNumbers();
479
480 return R1 || R2;
481}
482
483void BasicBlockSections::getAnalysisUsage(AnalysisUsage &AU) const {
484 AU.setPreservesAll();
485 AU.addRequired<BasicBlockSectionsProfileReaderWrapperPass>();
486 AU.addUsedIfAvailable<BasicBlockMatchingAndInference>();
487 AU.addUsedIfAvailable<MachineDominatorTreeWrapperPass>();
488 AU.addUsedIfAvailable<MachinePostDominatorTreeWrapperPass>();
489 MachineFunctionPass::getAnalysisUsage(AU);
490}
491
492MachineFunctionPass *llvm::createBasicBlockSectionsPass() {
493 return new BasicBlockSections();
494}
495