410 lines · cpp
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-exception6//7//===----------------------------------------------------------------------===//8//9// BasicBlockSections implementation.10//11// The purpose of this pass is to assign sections to basic blocks when12// -fbasic-block-sections= option is used. Further, with profile information13// only the subset of basic blocks with profiles are placed in separate sections14// and the rest are grouped in a cold section. The exception handling blocks are15// treated specially to ensure they are all in one seciton.16//17// Basic Block Sections18// ====================19//20// With option, -fbasic-block-sections=list, every function may be split into21// clusters of basic blocks. Every cluster will be emitted into a separate22// section with its basic blocks sequenced in the given order. To get the23// optimized performance, the clusters must form an optimal BB layout for the24// function. We insert a symbol at the beginning of every cluster's section to25// allow the linker to reorder the sections in any arbitrary sequence. A global26// order of these sections would encapsulate the function layout.27// For example, consider the following clusters for a function foo (consisting28// of 6 basic blocks 0, 1, ..., 5).29//30// 0 231// 1 3 532//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 symbol36// `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 in38// 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 implicit43// fallthrough to its next basic block, as it can be reordered by the linker.44// The compiler should make these fallthroughs explicit by adding45// unconditional jumps..46//47// 2. All inter-cluster branch targets would now need to be resolved by the48// linker as they cannot be calculated during compile time. This is done49// using static relocations. Further, the compiler tries to use short branch50// instructions on some ISAs for small branch offsets. This is not possible51// for inter-cluster branches as the offset is not determined at compile52// time, and therefore, long branch instructions have to be used for those.53//54// 3. Debug Information (DebugInfo) and Call Frame Information (CFI) emission55// needs special handling with basic block sections. DebugInfo needs to be56// emitted with more relocations as basic block sections can break a57// function into potentially several disjoint pieces, and CFI needs to be58// emitted per cluster. This also bloats the object file and binary sizes.59//60// Basic Block Address Map61// ==================62//63// With -fbasic-block-address-map, we emit the offsets of BB addresses of64// every function into the .llvm_bb_addr_map section. Along with the function65// symbols, this allows for mapping of virtual addresses in PMU profiles back to66// the corresponding basic blocks. This logic is implemented in AsmPrinter. This67// 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/BasicBlockSectionUtils.h"74#include "llvm/CodeGen/BasicBlockSectionsProfileReader.h"75#include "llvm/CodeGen/MachineDominators.h"76#include "llvm/CodeGen/MachineFunction.h"77#include "llvm/CodeGen/MachineFunctionPass.h"78#include "llvm/CodeGen/MachinePostDominators.h"79#include "llvm/CodeGen/Passes.h"80#include "llvm/CodeGen/TargetInstrInfo.h"81#include "llvm/InitializePasses.h"82#include "llvm/Support/UniqueBBID.h"83#include "llvm/Target/TargetMachine.h"84#include <optional>85 86using namespace llvm;87 88// Placing the cold clusters in a separate section mitigates against poor89// profiles and allows optimizations such as hugepage mapping to be applied at a90// section granularity. Defaults to ".text.split." which is recognized by lld91// via the `-z keep-text-section-prefix` flag.92cl::opt<std::string> llvm::BBSectionsColdTextPrefix(93 "bbsections-cold-text-prefix",94 cl::desc("The text prefix to use for cold basic block clusters"),95 cl::init(".text.split."), cl::Hidden);96 97static cl::opt<bool> BBSectionsDetectSourceDrift(98 "bbsections-detect-source-drift",99 cl::desc("This checks if there is a fdo instr. profile hash "100 "mismatch for this function"),101 cl::init(true), cl::Hidden);102 103namespace {104 105class BasicBlockSections : public MachineFunctionPass {106public:107 static char ID;108 109 BasicBlockSectionsProfileReaderWrapperPass *BBSectionsProfileReader = nullptr;110 111 BasicBlockSections() : MachineFunctionPass(ID) {112 initializeBasicBlockSectionsPass(*PassRegistry::getPassRegistry());113 }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 them122 /// accordingly.123 bool runOnMachineFunction(MachineFunction &MF) override;124 125private:126 bool handleBBSections(MachineFunction &MF);127 bool handleBBAddrMap(MachineFunction &MF);128};129 130} // end anonymous namespace131 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 basic145// block in a given function to account for changes in the layout.146static void147updateBranches(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(MBB.getIterator());153 auto *FTMBB = PreLayoutFallThroughs[MBB.getNumber()];154 // If this block had a fallthrough before we need an explicit unconditional155 // branch to that block if either156 // 1- the block ends a section, which means its next block may be157 // reorderd by the linker, or158 // 2- the fallthrough block is not adjacent to the block in the new159 // order.160 if (FTMBB && (MBB.isEndSection() || &*NextMBBI != FTMBB))161 TII->insertUnconditionalBranch(MBB, FTMBB, MBB.findBranchDebugLoc());162 163 // We do not optimize branches for machine basic blocks ending sections, as164 // 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 branch169 // 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(FTMBB);175 }176}177 178// This function sorts basic blocks according to the cluster's information.179// All explicitly specified clusters of basic blocks will be ordered180// accordingly. All non-specified BBs go into a separate "Cold" section.181// Additionally, if exception handling landing pads end up in more than one182// clusters, they are moved into a single "Exception" section. Eventually,183// clusters are ordered in increasing order of their IDs, with the "Exception"184// and "Cold" succeeding all other clusters.185// FuncClusterInfo represents the cluster information for basic blocks. It186// maps from BBID of basic blocks to their cluster information.187static void188assignSections(MachineFunction &MF,189 const DenseMap<UniqueBBID, BBClusterInfo> &FuncClusterInfo) {190 assert(MF.hasBBSections() && "BB Sections is not set for function.");191 // This variable stores the section ID of the cluster containing eh_pads (if192 // all eh_pads are one cluster). If more than one cluster contain eh_pads, we193 // set it equal to ExceptionSectionID.194 std::optional<MBBSectionID> EHPadsSectionID;195 196 for (auto &MBB : MF) {197 // With the 'all' option, every basic block is placed in a unique section.198 // With the 'list' option, every basic block is placed in a section199 // associated with its cluster.200 if (MF.getTarget().getBBSectionsType() == llvm::BasicBlockSection::All) {201 // If unique sections are desired for all basic blocks of the function, we202 // set every basic block's section ID equal to its original position in203 // the layout (which is equal to its number). This ensures that basic204 // blocks are ordered canonically.205 MBB.setSectionID(MBB.getNumber());206 } else {207 auto I = FuncClusterInfo.find(*MBB.getBBID());208 if (I != FuncClusterInfo.end()) {209 MBB.setSectionID(I->second.ClusterID);210 } else {211 const TargetInstrInfo &TII =212 *MBB.getParent()->getSubtarget().getInstrInfo();213 214 if (TII.isMBBSafeToSplitToCold(MBB)) {215 // BB goes into the special cold section if it is not specified in the216 // cluster info map.217 MBB.setSectionID(MBBSectionID::ColdSectionID);218 }219 }220 }221 222 if (MBB.isEHPad() && EHPadsSectionID != MBB.getSectionID() &&223 EHPadsSectionID != MBBSectionID::ExceptionSectionID) {224 // If we already have one cluster containing eh_pads, this must be updated225 // to ExceptionSectionID. Otherwise, we set it equal to the current226 // section ID.227 EHPadsSectionID = EHPadsSectionID ? MBBSectionID::ExceptionSectionID228 : MBB.getSectionID();229 }230 }231 232 // If EHPads are in more than one section, this places all of them in the233 // special exception section.234 if (EHPadsSectionID == MBBSectionID::ExceptionSectionID)235 for (auto &MBB : MF)236 if (MBB.isEHPad())237 MBB.setSectionID(*EHPadsSectionID);238}239 240void llvm::sortBasicBlocksAndUpdateBranches(241 MachineFunction &MF, MachineBasicBlockComparator MBBCmp) {242 [[maybe_unused]] const MachineBasicBlock *EntryBlock = &MF.front();243 SmallVector<MachineBasicBlock *> PreLayoutFallThroughs(MF.getNumBlockIDs());244 for (auto &MBB : MF)245 PreLayoutFallThroughs[MBB.getNumber()] =246 MBB.getFallThrough(/*JumpToFallThrough=*/false);247 248 MF.sort(MBBCmp);249 assert(&MF.front() == EntryBlock &&250 "Entry block should not be displaced by basic block sections");251 252 // Set IsBeginSection and IsEndSection according to the assigned section IDs.253 MF.assignBeginEndSections();254 255 // After reordering basic blocks, we must update basic block branches to256 // insert explicit fallthrough branches when required and optimize branches257 // when possible.258 updateBranches(MF, PreLayoutFallThroughs);259}260 261// If the exception section begins with a landing pad, that landing pad will262// assume a zero offset (relative to @LPStart) in the LSDA. However, a value of263// zero implies "no landing pad." This function inserts a NOP just before the EH264// pad label to ensure a nonzero offset.265void llvm::avoidZeroOffsetLandingPad(MachineFunction &MF) {266 for (auto &MBB : MF) {267 if (MBB.isBeginSection() && MBB.isEHPad()) {268 MachineBasicBlock::iterator MI = MBB.begin();269 while (!MI->isEHLabel())270 ++MI;271 MF.getSubtarget().getInstrInfo()->insertNoop(MBB, MI);272 }273 }274}275 276bool llvm::hasInstrProfHashMismatch(MachineFunction &MF) {277 if (!BBSectionsDetectSourceDrift)278 return false;279 280 const char MetadataName[] = "instr_prof_hash_mismatch";281 auto *Existing = MF.getFunction().getMetadata(LLVMContext::MD_annotation);282 if (Existing) {283 MDTuple *Tuple = cast<MDTuple>(Existing);284 for (const auto &N : Tuple->operands())285 if (N.equalsStr(MetadataName))286 return true;287 }288 289 return false;290}291 292// Identify, arrange, and modify basic blocks which need separate sections293// according to the specification provided by the -fbasic-block-sections flag.294bool BasicBlockSections::handleBBSections(MachineFunction &MF) {295 auto BBSectionsType = MF.getTarget().getBBSectionsType();296 if (BBSectionsType == BasicBlockSection::None)297 return false;298 299 // Check for source drift. If the source has changed since the profiles300 // were obtained, optimizing basic blocks might be sub-optimal.301 // This only applies to BasicBlockSection::List as it creates302 // clusters of basic blocks using basic block ids. Source drift can303 // invalidate these groupings leading to sub-optimal code generation with304 // regards to performance.305 if (BBSectionsType == BasicBlockSection::List &&306 hasInstrProfHashMismatch(MF))307 return false;308 309 DenseMap<UniqueBBID, BBClusterInfo> FuncClusterInfo;310 if (BBSectionsType == BasicBlockSection::List) {311 auto ClusterInfo = getAnalysis<BasicBlockSectionsProfileReaderWrapperPass>()312 .getClusterInfoForFunction(MF.getName());313 if (ClusterInfo.empty())314 return false;315 for (auto &BBClusterInfo : ClusterInfo) {316 FuncClusterInfo.try_emplace(BBClusterInfo.BBID, BBClusterInfo);317 }318 }319 320 // Renumber blocks before sorting them. This is useful for accessing the321 // original layout positions and finding the original fallthroughs.322 MF.RenumberBlocks();323 324 MF.setBBSectionsType(BBSectionsType);325 assignSections(MF, FuncClusterInfo);326 327 const MachineBasicBlock &EntryBB = MF.front();328 auto EntryBBSectionID = EntryBB.getSectionID();329 330 // Helper function for ordering BB sections as follows:331 // * Entry section (section including the entry block).332 // * Regular sections (in increasing order of their Number).333 // ...334 // * Exception section335 // * Cold section336 auto MBBSectionOrder = [EntryBBSectionID](const MBBSectionID &LHS,337 const MBBSectionID &RHS) {338 // We make sure that the section containing the entry block precedes all the339 // other sections.340 if (LHS == EntryBBSectionID || RHS == EntryBBSectionID)341 return LHS == EntryBBSectionID;342 return LHS.Type == RHS.Type ? LHS.Number < RHS.Number : LHS.Type < RHS.Type;343 };344 345 // We sort all basic blocks to make sure the basic blocks of every cluster are346 // contiguous and ordered accordingly. Furthermore, clusters are ordered in347 // increasing order of their section IDs, with the exception and the348 // cold section placed at the end of the function.349 // Also, we force the entry block of the function to be placed at the350 // beginning of the function, regardless of the requested order.351 auto Comparator = [&](const MachineBasicBlock &X,352 const MachineBasicBlock &Y) {353 auto XSectionID = X.getSectionID();354 auto YSectionID = Y.getSectionID();355 if (XSectionID != YSectionID)356 return MBBSectionOrder(XSectionID, YSectionID);357 // Make sure that the entry block is placed at the beginning.358 if (&X == &EntryBB || &Y == &EntryBB)359 return &X == &EntryBB;360 // If the two basic block are in the same section, the order is decided by361 // their position within the section.362 if (XSectionID.Type == MBBSectionID::SectionType::Default)363 return FuncClusterInfo.lookup(*X.getBBID()).PositionInCluster <364 FuncClusterInfo.lookup(*Y.getBBID()).PositionInCluster;365 return X.getNumber() < Y.getNumber();366 };367 368 sortBasicBlocksAndUpdateBranches(MF, Comparator);369 avoidZeroOffsetLandingPad(MF);370 return true;371}372 373// When the BB address map needs to be generated, this renumbers basic blocks to374// make them appear in increasing order of their IDs in the function. This375// avoids the need to store basic block IDs in the BB address map section, since376// they can be determined implicitly.377bool BasicBlockSections::handleBBAddrMap(MachineFunction &MF) {378 if (!MF.getTarget().Options.BBAddrMap)379 return false;380 MF.RenumberBlocks();381 return true;382}383 384bool BasicBlockSections::runOnMachineFunction(MachineFunction &MF) {385 // First handle the basic block sections.386 auto R1 = handleBBSections(MF);387 // Handle basic block address map after basic block sections are finalized.388 auto R2 = handleBBAddrMap(MF);389 390 // We renumber blocks, so update the dominator tree we want to preserve.391 if (auto *WP = getAnalysisIfAvailable<MachineDominatorTreeWrapperPass>())392 WP->getDomTree().updateBlockNumbers();393 if (auto *WP = getAnalysisIfAvailable<MachinePostDominatorTreeWrapperPass>())394 WP->getPostDomTree().updateBlockNumbers();395 396 return R1 || R2;397}398 399void BasicBlockSections::getAnalysisUsage(AnalysisUsage &AU) const {400 AU.setPreservesAll();401 AU.addRequired<BasicBlockSectionsProfileReaderWrapperPass>();402 AU.addUsedIfAvailable<MachineDominatorTreeWrapperPass>();403 AU.addUsedIfAvailable<MachinePostDominatorTreeWrapperPass>();404 MachineFunctionPass::getAnalysisUsage(AU);405}406 407MachineFunctionPass *llvm::createBasicBlockSectionsPass() {408 return new BasicBlockSections();409}410