1*e8d8bef9SDimitry Andric //===-- BasicBlockSections.cpp ---=========--------------------------------===// 2*e8d8bef9SDimitry Andric // 3*e8d8bef9SDimitry Andric // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4*e8d8bef9SDimitry Andric // See https://llvm.org/LICENSE.txt for license information. 5*e8d8bef9SDimitry Andric // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 6*e8d8bef9SDimitry Andric // 7*e8d8bef9SDimitry Andric //===----------------------------------------------------------------------===// 8*e8d8bef9SDimitry Andric // 9*e8d8bef9SDimitry Andric // BasicBlockSections implementation. 10*e8d8bef9SDimitry Andric // 11*e8d8bef9SDimitry Andric // The purpose of this pass is to assign sections to basic blocks when 12*e8d8bef9SDimitry Andric // -fbasic-block-sections= option is used. Further, with profile information 13*e8d8bef9SDimitry Andric // only the subset of basic blocks with profiles are placed in separate sections 14*e8d8bef9SDimitry Andric // and the rest are grouped in a cold section. The exception handling blocks are 15*e8d8bef9SDimitry Andric // treated specially to ensure they are all in one seciton. 16*e8d8bef9SDimitry Andric // 17*e8d8bef9SDimitry Andric // Basic Block Sections 18*e8d8bef9SDimitry Andric // ==================== 19*e8d8bef9SDimitry Andric // 20*e8d8bef9SDimitry Andric // With option, -fbasic-block-sections=list, every function may be split into 21*e8d8bef9SDimitry Andric // clusters of basic blocks. Every cluster will be emitted into a separate 22*e8d8bef9SDimitry Andric // section with its basic blocks sequenced in the given order. To get the 23*e8d8bef9SDimitry Andric // optimized performance, the clusters must form an optimal BB layout for the 24*e8d8bef9SDimitry Andric // function. Every cluster's section is labeled with a symbol to allow the 25*e8d8bef9SDimitry Andric // linker to reorder the sections in any arbitrary sequence. A global order of 26*e8d8bef9SDimitry Andric // these sections would encapsulate the function layout. 27*e8d8bef9SDimitry Andric // 28*e8d8bef9SDimitry Andric // There are a couple of challenges to be addressed: 29*e8d8bef9SDimitry Andric // 30*e8d8bef9SDimitry Andric // 1. The last basic block of every cluster should not have any implicit 31*e8d8bef9SDimitry Andric // fallthrough to its next basic block, as it can be reordered by the linker. 32*e8d8bef9SDimitry Andric // The compiler should make these fallthroughs explicit by adding 33*e8d8bef9SDimitry Andric // unconditional jumps.. 34*e8d8bef9SDimitry Andric // 35*e8d8bef9SDimitry Andric // 2. All inter-cluster branch targets would now need to be resolved by the 36*e8d8bef9SDimitry Andric // linker as they cannot be calculated during compile time. This is done 37*e8d8bef9SDimitry Andric // using static relocations. Further, the compiler tries to use short branch 38*e8d8bef9SDimitry Andric // instructions on some ISAs for small branch offsets. This is not possible 39*e8d8bef9SDimitry Andric // for inter-cluster branches as the offset is not determined at compile 40*e8d8bef9SDimitry Andric // time, and therefore, long branch instructions have to be used for those. 41*e8d8bef9SDimitry Andric // 42*e8d8bef9SDimitry Andric // 3. Debug Information (DebugInfo) and Call Frame Information (CFI) emission 43*e8d8bef9SDimitry Andric // needs special handling with basic block sections. DebugInfo needs to be 44*e8d8bef9SDimitry Andric // emitted with more relocations as basic block sections can break a 45*e8d8bef9SDimitry Andric // function into potentially several disjoint pieces, and CFI needs to be 46*e8d8bef9SDimitry Andric // emitted per cluster. This also bloats the object file and binary sizes. 47*e8d8bef9SDimitry Andric // 48*e8d8bef9SDimitry Andric // Basic Block Labels 49*e8d8bef9SDimitry Andric // ================== 50*e8d8bef9SDimitry Andric // 51*e8d8bef9SDimitry Andric // With -fbasic-block-sections=labels, we emit the offsets of BB addresses of 52*e8d8bef9SDimitry Andric // every function into the .llvm_bb_addr_map section. Along with the function 53*e8d8bef9SDimitry Andric // symbols, this allows for mapping of virtual addresses in PMU profiles back to 54*e8d8bef9SDimitry Andric // the corresponding basic blocks. This logic is implemented in AsmPrinter. This 55*e8d8bef9SDimitry Andric // pass only assigns the BBSectionType of every function to ``labels``. 56*e8d8bef9SDimitry Andric // 57*e8d8bef9SDimitry Andric //===----------------------------------------------------------------------===// 58*e8d8bef9SDimitry Andric 59*e8d8bef9SDimitry Andric #include "llvm/ADT/Optional.h" 60*e8d8bef9SDimitry Andric #include "llvm/ADT/SmallSet.h" 61*e8d8bef9SDimitry Andric #include "llvm/ADT/SmallVector.h" 62*e8d8bef9SDimitry Andric #include "llvm/ADT/StringMap.h" 63*e8d8bef9SDimitry Andric #include "llvm/ADT/StringRef.h" 64*e8d8bef9SDimitry Andric #include "llvm/CodeGen/BasicBlockSectionUtils.h" 65*e8d8bef9SDimitry Andric #include "llvm/CodeGen/MachineFunction.h" 66*e8d8bef9SDimitry Andric #include "llvm/CodeGen/MachineFunctionPass.h" 67*e8d8bef9SDimitry Andric #include "llvm/CodeGen/MachineModuleInfo.h" 68*e8d8bef9SDimitry Andric #include "llvm/CodeGen/Passes.h" 69*e8d8bef9SDimitry Andric #include "llvm/CodeGen/TargetInstrInfo.h" 70*e8d8bef9SDimitry Andric #include "llvm/InitializePasses.h" 71*e8d8bef9SDimitry Andric #include "llvm/Support/Error.h" 72*e8d8bef9SDimitry Andric #include "llvm/Support/LineIterator.h" 73*e8d8bef9SDimitry Andric #include "llvm/Support/MemoryBuffer.h" 74*e8d8bef9SDimitry Andric #include "llvm/Target/TargetMachine.h" 75*e8d8bef9SDimitry Andric 76*e8d8bef9SDimitry Andric using llvm::SmallSet; 77*e8d8bef9SDimitry Andric using llvm::SmallVector; 78*e8d8bef9SDimitry Andric using llvm::StringMap; 79*e8d8bef9SDimitry Andric using llvm::StringRef; 80*e8d8bef9SDimitry Andric using namespace llvm; 81*e8d8bef9SDimitry Andric 82*e8d8bef9SDimitry Andric // Placing the cold clusters in a separate section mitigates against poor 83*e8d8bef9SDimitry Andric // profiles and allows optimizations such as hugepage mapping to be applied at a 84*e8d8bef9SDimitry Andric // section granularity. Defaults to ".text.split." which is recognized by lld 85*e8d8bef9SDimitry Andric // via the `-z keep-text-section-prefix` flag. 86*e8d8bef9SDimitry Andric cl::opt<std::string> llvm::BBSectionsColdTextPrefix( 87*e8d8bef9SDimitry Andric "bbsections-cold-text-prefix", 88*e8d8bef9SDimitry Andric cl::desc("The text prefix to use for cold basic block clusters"), 89*e8d8bef9SDimitry Andric cl::init(".text.split."), cl::Hidden); 90*e8d8bef9SDimitry Andric 91*e8d8bef9SDimitry Andric namespace { 92*e8d8bef9SDimitry Andric 93*e8d8bef9SDimitry Andric // This struct represents the cluster information for a machine basic block. 94*e8d8bef9SDimitry Andric struct BBClusterInfo { 95*e8d8bef9SDimitry Andric // MachineBasicBlock ID. 96*e8d8bef9SDimitry Andric unsigned MBBNumber; 97*e8d8bef9SDimitry Andric // Cluster ID this basic block belongs to. 98*e8d8bef9SDimitry Andric unsigned ClusterID; 99*e8d8bef9SDimitry Andric // Position of basic block within the cluster. 100*e8d8bef9SDimitry Andric unsigned PositionInCluster; 101*e8d8bef9SDimitry Andric }; 102*e8d8bef9SDimitry Andric 103*e8d8bef9SDimitry Andric using ProgramBBClusterInfoMapTy = StringMap<SmallVector<BBClusterInfo, 4>>; 104*e8d8bef9SDimitry Andric 105*e8d8bef9SDimitry Andric class BasicBlockSections : public MachineFunctionPass { 106*e8d8bef9SDimitry Andric public: 107*e8d8bef9SDimitry Andric static char ID; 108*e8d8bef9SDimitry Andric 109*e8d8bef9SDimitry Andric // This contains the basic-block-sections profile. 110*e8d8bef9SDimitry Andric const MemoryBuffer *MBuf = nullptr; 111*e8d8bef9SDimitry Andric 112*e8d8bef9SDimitry Andric // This encapsulates the BB cluster information for the whole program. 113*e8d8bef9SDimitry Andric // 114*e8d8bef9SDimitry Andric // For every function name, it contains the cluster information for (all or 115*e8d8bef9SDimitry Andric // some of) its basic blocks. The cluster information for every basic block 116*e8d8bef9SDimitry Andric // includes its cluster ID along with the position of the basic block in that 117*e8d8bef9SDimitry Andric // cluster. 118*e8d8bef9SDimitry Andric ProgramBBClusterInfoMapTy ProgramBBClusterInfo; 119*e8d8bef9SDimitry Andric 120*e8d8bef9SDimitry Andric // Some functions have alias names. We use this map to find the main alias 121*e8d8bef9SDimitry Andric // name for which we have mapping in ProgramBBClusterInfo. 122*e8d8bef9SDimitry Andric StringMap<StringRef> FuncAliasMap; 123*e8d8bef9SDimitry Andric 124*e8d8bef9SDimitry Andric BasicBlockSections(const MemoryBuffer *Buf) 125*e8d8bef9SDimitry Andric : MachineFunctionPass(ID), MBuf(Buf) { 126*e8d8bef9SDimitry Andric initializeBasicBlockSectionsPass(*PassRegistry::getPassRegistry()); 127*e8d8bef9SDimitry Andric }; 128*e8d8bef9SDimitry Andric 129*e8d8bef9SDimitry Andric BasicBlockSections() : MachineFunctionPass(ID) { 130*e8d8bef9SDimitry Andric initializeBasicBlockSectionsPass(*PassRegistry::getPassRegistry()); 131*e8d8bef9SDimitry Andric } 132*e8d8bef9SDimitry Andric 133*e8d8bef9SDimitry Andric StringRef getPassName() const override { 134*e8d8bef9SDimitry Andric return "Basic Block Sections Analysis"; 135*e8d8bef9SDimitry Andric } 136*e8d8bef9SDimitry Andric 137*e8d8bef9SDimitry Andric void getAnalysisUsage(AnalysisUsage &AU) const override; 138*e8d8bef9SDimitry Andric 139*e8d8bef9SDimitry Andric /// Read profiles of basic blocks if available here. 140*e8d8bef9SDimitry Andric bool doInitialization(Module &M) override; 141*e8d8bef9SDimitry Andric 142*e8d8bef9SDimitry Andric /// Identify basic blocks that need separate sections and prepare to emit them 143*e8d8bef9SDimitry Andric /// accordingly. 144*e8d8bef9SDimitry Andric bool runOnMachineFunction(MachineFunction &MF) override; 145*e8d8bef9SDimitry Andric }; 146*e8d8bef9SDimitry Andric 147*e8d8bef9SDimitry Andric } // end anonymous namespace 148*e8d8bef9SDimitry Andric 149*e8d8bef9SDimitry Andric char BasicBlockSections::ID = 0; 150*e8d8bef9SDimitry Andric INITIALIZE_PASS(BasicBlockSections, "bbsections-prepare", 151*e8d8bef9SDimitry Andric "Prepares for basic block sections, by splitting functions " 152*e8d8bef9SDimitry Andric "into clusters of basic blocks.", 153*e8d8bef9SDimitry Andric false, false) 154*e8d8bef9SDimitry Andric 155*e8d8bef9SDimitry Andric // This function updates and optimizes the branching instructions of every basic 156*e8d8bef9SDimitry Andric // block in a given function to account for changes in the layout. 157*e8d8bef9SDimitry Andric static void updateBranches( 158*e8d8bef9SDimitry Andric MachineFunction &MF, 159*e8d8bef9SDimitry Andric const SmallVector<MachineBasicBlock *, 4> &PreLayoutFallThroughs) { 160*e8d8bef9SDimitry Andric const TargetInstrInfo *TII = MF.getSubtarget().getInstrInfo(); 161*e8d8bef9SDimitry Andric SmallVector<MachineOperand, 4> Cond; 162*e8d8bef9SDimitry Andric for (auto &MBB : MF) { 163*e8d8bef9SDimitry Andric auto NextMBBI = std::next(MBB.getIterator()); 164*e8d8bef9SDimitry Andric auto *FTMBB = PreLayoutFallThroughs[MBB.getNumber()]; 165*e8d8bef9SDimitry Andric // If this block had a fallthrough before we need an explicit unconditional 166*e8d8bef9SDimitry Andric // branch to that block if either 167*e8d8bef9SDimitry Andric // 1- the block ends a section, which means its next block may be 168*e8d8bef9SDimitry Andric // reorderd by the linker, or 169*e8d8bef9SDimitry Andric // 2- the fallthrough block is not adjacent to the block in the new 170*e8d8bef9SDimitry Andric // order. 171*e8d8bef9SDimitry Andric if (FTMBB && (MBB.isEndSection() || &*NextMBBI != FTMBB)) 172*e8d8bef9SDimitry Andric TII->insertUnconditionalBranch(MBB, FTMBB, MBB.findBranchDebugLoc()); 173*e8d8bef9SDimitry Andric 174*e8d8bef9SDimitry Andric // We do not optimize branches for machine basic blocks ending sections, as 175*e8d8bef9SDimitry Andric // their adjacent block might be reordered by the linker. 176*e8d8bef9SDimitry Andric if (MBB.isEndSection()) 177*e8d8bef9SDimitry Andric continue; 178*e8d8bef9SDimitry Andric 179*e8d8bef9SDimitry Andric // It might be possible to optimize branches by flipping the branch 180*e8d8bef9SDimitry Andric // condition. 181*e8d8bef9SDimitry Andric Cond.clear(); 182*e8d8bef9SDimitry Andric MachineBasicBlock *TBB = nullptr, *FBB = nullptr; // For analyzeBranch. 183*e8d8bef9SDimitry Andric if (TII->analyzeBranch(MBB, TBB, FBB, Cond)) 184*e8d8bef9SDimitry Andric continue; 185*e8d8bef9SDimitry Andric MBB.updateTerminator(FTMBB); 186*e8d8bef9SDimitry Andric } 187*e8d8bef9SDimitry Andric } 188*e8d8bef9SDimitry Andric 189*e8d8bef9SDimitry Andric // This function provides the BBCluster information associated with a function. 190*e8d8bef9SDimitry Andric // Returns true if a valid association exists and false otherwise. 191*e8d8bef9SDimitry Andric static bool getBBClusterInfoForFunction( 192*e8d8bef9SDimitry Andric const MachineFunction &MF, const StringMap<StringRef> FuncAliasMap, 193*e8d8bef9SDimitry Andric const ProgramBBClusterInfoMapTy &ProgramBBClusterInfo, 194*e8d8bef9SDimitry Andric std::vector<Optional<BBClusterInfo>> &V) { 195*e8d8bef9SDimitry Andric // Get the main alias name for the function. 196*e8d8bef9SDimitry Andric auto FuncName = MF.getName(); 197*e8d8bef9SDimitry Andric auto R = FuncAliasMap.find(FuncName); 198*e8d8bef9SDimitry Andric StringRef AliasName = R == FuncAliasMap.end() ? FuncName : R->second; 199*e8d8bef9SDimitry Andric 200*e8d8bef9SDimitry Andric // Find the assoicated cluster information. 201*e8d8bef9SDimitry Andric auto P = ProgramBBClusterInfo.find(AliasName); 202*e8d8bef9SDimitry Andric if (P == ProgramBBClusterInfo.end()) 203*e8d8bef9SDimitry Andric return false; 204*e8d8bef9SDimitry Andric 205*e8d8bef9SDimitry Andric if (P->second.empty()) { 206*e8d8bef9SDimitry Andric // This indicates that sections are desired for all basic blocks of this 207*e8d8bef9SDimitry Andric // function. We clear the BBClusterInfo vector to denote this. 208*e8d8bef9SDimitry Andric V.clear(); 209*e8d8bef9SDimitry Andric return true; 210*e8d8bef9SDimitry Andric } 211*e8d8bef9SDimitry Andric 212*e8d8bef9SDimitry Andric V.resize(MF.getNumBlockIDs()); 213*e8d8bef9SDimitry Andric for (auto bbClusterInfo : P->second) { 214*e8d8bef9SDimitry Andric // Bail out if the cluster information contains invalid MBB numbers. 215*e8d8bef9SDimitry Andric if (bbClusterInfo.MBBNumber >= MF.getNumBlockIDs()) 216*e8d8bef9SDimitry Andric return false; 217*e8d8bef9SDimitry Andric V[bbClusterInfo.MBBNumber] = bbClusterInfo; 218*e8d8bef9SDimitry Andric } 219*e8d8bef9SDimitry Andric return true; 220*e8d8bef9SDimitry Andric } 221*e8d8bef9SDimitry Andric 222*e8d8bef9SDimitry Andric // This function sorts basic blocks according to the cluster's information. 223*e8d8bef9SDimitry Andric // All explicitly specified clusters of basic blocks will be ordered 224*e8d8bef9SDimitry Andric // accordingly. All non-specified BBs go into a separate "Cold" section. 225*e8d8bef9SDimitry Andric // Additionally, if exception handling landing pads end up in more than one 226*e8d8bef9SDimitry Andric // clusters, they are moved into a single "Exception" section. Eventually, 227*e8d8bef9SDimitry Andric // clusters are ordered in increasing order of their IDs, with the "Exception" 228*e8d8bef9SDimitry Andric // and "Cold" succeeding all other clusters. 229*e8d8bef9SDimitry Andric // FuncBBClusterInfo represent the cluster information for basic blocks. If this 230*e8d8bef9SDimitry Andric // is empty, it means unique sections for all basic blocks in the function. 231*e8d8bef9SDimitry Andric static void 232*e8d8bef9SDimitry Andric assignSections(MachineFunction &MF, 233*e8d8bef9SDimitry Andric const std::vector<Optional<BBClusterInfo>> &FuncBBClusterInfo) { 234*e8d8bef9SDimitry Andric assert(MF.hasBBSections() && "BB Sections is not set for function."); 235*e8d8bef9SDimitry Andric // This variable stores the section ID of the cluster containing eh_pads (if 236*e8d8bef9SDimitry Andric // all eh_pads are one cluster). If more than one cluster contain eh_pads, we 237*e8d8bef9SDimitry Andric // set it equal to ExceptionSectionID. 238*e8d8bef9SDimitry Andric Optional<MBBSectionID> EHPadsSectionID; 239*e8d8bef9SDimitry Andric 240*e8d8bef9SDimitry Andric for (auto &MBB : MF) { 241*e8d8bef9SDimitry Andric // With the 'all' option, every basic block is placed in a unique section. 242*e8d8bef9SDimitry Andric // With the 'list' option, every basic block is placed in a section 243*e8d8bef9SDimitry Andric // associated with its cluster, unless we want individual unique sections 244*e8d8bef9SDimitry Andric // for every basic block in this function (if FuncBBClusterInfo is empty). 245*e8d8bef9SDimitry Andric if (MF.getTarget().getBBSectionsType() == llvm::BasicBlockSection::All || 246*e8d8bef9SDimitry Andric FuncBBClusterInfo.empty()) { 247*e8d8bef9SDimitry Andric // If unique sections are desired for all basic blocks of the function, we 248*e8d8bef9SDimitry Andric // set every basic block's section ID equal to its number (basic block 249*e8d8bef9SDimitry Andric // id). This further ensures that basic blocks are ordered canonically. 250*e8d8bef9SDimitry Andric MBB.setSectionID({static_cast<unsigned int>(MBB.getNumber())}); 251*e8d8bef9SDimitry Andric } else if (FuncBBClusterInfo[MBB.getNumber()].hasValue()) 252*e8d8bef9SDimitry Andric MBB.setSectionID(FuncBBClusterInfo[MBB.getNumber()]->ClusterID); 253*e8d8bef9SDimitry Andric else { 254*e8d8bef9SDimitry Andric // BB goes into the special cold section if it is not specified in the 255*e8d8bef9SDimitry Andric // cluster info map. 256*e8d8bef9SDimitry Andric MBB.setSectionID(MBBSectionID::ColdSectionID); 257*e8d8bef9SDimitry Andric } 258*e8d8bef9SDimitry Andric 259*e8d8bef9SDimitry Andric if (MBB.isEHPad() && EHPadsSectionID != MBB.getSectionID() && 260*e8d8bef9SDimitry Andric EHPadsSectionID != MBBSectionID::ExceptionSectionID) { 261*e8d8bef9SDimitry Andric // If we already have one cluster containing eh_pads, this must be updated 262*e8d8bef9SDimitry Andric // to ExceptionSectionID. Otherwise, we set it equal to the current 263*e8d8bef9SDimitry Andric // section ID. 264*e8d8bef9SDimitry Andric EHPadsSectionID = EHPadsSectionID.hasValue() 265*e8d8bef9SDimitry Andric ? MBBSectionID::ExceptionSectionID 266*e8d8bef9SDimitry Andric : MBB.getSectionID(); 267*e8d8bef9SDimitry Andric } 268*e8d8bef9SDimitry Andric } 269*e8d8bef9SDimitry Andric 270*e8d8bef9SDimitry Andric // If EHPads are in more than one section, this places all of them in the 271*e8d8bef9SDimitry Andric // special exception section. 272*e8d8bef9SDimitry Andric if (EHPadsSectionID == MBBSectionID::ExceptionSectionID) 273*e8d8bef9SDimitry Andric for (auto &MBB : MF) 274*e8d8bef9SDimitry Andric if (MBB.isEHPad()) 275*e8d8bef9SDimitry Andric MBB.setSectionID(EHPadsSectionID.getValue()); 276*e8d8bef9SDimitry Andric } 277*e8d8bef9SDimitry Andric 278*e8d8bef9SDimitry Andric void llvm::sortBasicBlocksAndUpdateBranches( 279*e8d8bef9SDimitry Andric MachineFunction &MF, MachineBasicBlockComparator MBBCmp) { 280*e8d8bef9SDimitry Andric SmallVector<MachineBasicBlock *, 4> PreLayoutFallThroughs( 281*e8d8bef9SDimitry Andric MF.getNumBlockIDs()); 282*e8d8bef9SDimitry Andric for (auto &MBB : MF) 283*e8d8bef9SDimitry Andric PreLayoutFallThroughs[MBB.getNumber()] = MBB.getFallThrough(); 284*e8d8bef9SDimitry Andric 285*e8d8bef9SDimitry Andric MF.sort(MBBCmp); 286*e8d8bef9SDimitry Andric 287*e8d8bef9SDimitry Andric // Set IsBeginSection and IsEndSection according to the assigned section IDs. 288*e8d8bef9SDimitry Andric MF.assignBeginEndSections(); 289*e8d8bef9SDimitry Andric 290*e8d8bef9SDimitry Andric // After reordering basic blocks, we must update basic block branches to 291*e8d8bef9SDimitry Andric // insert explicit fallthrough branches when required and optimize branches 292*e8d8bef9SDimitry Andric // when possible. 293*e8d8bef9SDimitry Andric updateBranches(MF, PreLayoutFallThroughs); 294*e8d8bef9SDimitry Andric } 295*e8d8bef9SDimitry Andric 296*e8d8bef9SDimitry Andric // If the exception section begins with a landing pad, that landing pad will 297*e8d8bef9SDimitry Andric // assume a zero offset (relative to @LPStart) in the LSDA. However, a value of 298*e8d8bef9SDimitry Andric // zero implies "no landing pad." This function inserts a NOP just before the EH 299*e8d8bef9SDimitry Andric // pad label to ensure a nonzero offset. Returns true if padding is not needed. 300*e8d8bef9SDimitry Andric static bool avoidZeroOffsetLandingPad(MachineFunction &MF) { 301*e8d8bef9SDimitry Andric for (auto &MBB : MF) { 302*e8d8bef9SDimitry Andric if (MBB.isBeginSection() && MBB.isEHPad()) { 303*e8d8bef9SDimitry Andric MachineBasicBlock::iterator MI = MBB.begin(); 304*e8d8bef9SDimitry Andric while (!MI->isEHLabel()) 305*e8d8bef9SDimitry Andric ++MI; 306*e8d8bef9SDimitry Andric MCInst Noop; 307*e8d8bef9SDimitry Andric MF.getSubtarget().getInstrInfo()->getNoop(Noop); 308*e8d8bef9SDimitry Andric BuildMI(MBB, MI, DebugLoc(), 309*e8d8bef9SDimitry Andric MF.getSubtarget().getInstrInfo()->get(Noop.getOpcode())); 310*e8d8bef9SDimitry Andric return false; 311*e8d8bef9SDimitry Andric } 312*e8d8bef9SDimitry Andric } 313*e8d8bef9SDimitry Andric return true; 314*e8d8bef9SDimitry Andric } 315*e8d8bef9SDimitry Andric 316*e8d8bef9SDimitry Andric bool BasicBlockSections::runOnMachineFunction(MachineFunction &MF) { 317*e8d8bef9SDimitry Andric auto BBSectionsType = MF.getTarget().getBBSectionsType(); 318*e8d8bef9SDimitry Andric assert(BBSectionsType != BasicBlockSection::None && 319*e8d8bef9SDimitry Andric "BB Sections not enabled!"); 320*e8d8bef9SDimitry Andric // Renumber blocks before sorting them for basic block sections. This is 321*e8d8bef9SDimitry Andric // useful during sorting, basic blocks in the same section will retain the 322*e8d8bef9SDimitry Andric // default order. This renumbering should also be done for basic block 323*e8d8bef9SDimitry Andric // labels to match the profiles with the correct blocks. 324*e8d8bef9SDimitry Andric MF.RenumberBlocks(); 325*e8d8bef9SDimitry Andric 326*e8d8bef9SDimitry Andric if (BBSectionsType == BasicBlockSection::Labels) { 327*e8d8bef9SDimitry Andric MF.setBBSectionsType(BBSectionsType); 328*e8d8bef9SDimitry Andric return true; 329*e8d8bef9SDimitry Andric } 330*e8d8bef9SDimitry Andric 331*e8d8bef9SDimitry Andric std::vector<Optional<BBClusterInfo>> FuncBBClusterInfo; 332*e8d8bef9SDimitry Andric if (BBSectionsType == BasicBlockSection::List && 333*e8d8bef9SDimitry Andric !getBBClusterInfoForFunction(MF, FuncAliasMap, ProgramBBClusterInfo, 334*e8d8bef9SDimitry Andric FuncBBClusterInfo)) 335*e8d8bef9SDimitry Andric return true; 336*e8d8bef9SDimitry Andric MF.setBBSectionsType(BBSectionsType); 337*e8d8bef9SDimitry Andric assignSections(MF, FuncBBClusterInfo); 338*e8d8bef9SDimitry Andric 339*e8d8bef9SDimitry Andric // We make sure that the cluster including the entry basic block precedes all 340*e8d8bef9SDimitry Andric // other clusters. 341*e8d8bef9SDimitry Andric auto EntryBBSectionID = MF.front().getSectionID(); 342*e8d8bef9SDimitry Andric 343*e8d8bef9SDimitry Andric // Helper function for ordering BB sections as follows: 344*e8d8bef9SDimitry Andric // * Entry section (section including the entry block). 345*e8d8bef9SDimitry Andric // * Regular sections (in increasing order of their Number). 346*e8d8bef9SDimitry Andric // ... 347*e8d8bef9SDimitry Andric // * Exception section 348*e8d8bef9SDimitry Andric // * Cold section 349*e8d8bef9SDimitry Andric auto MBBSectionOrder = [EntryBBSectionID](const MBBSectionID &LHS, 350*e8d8bef9SDimitry Andric const MBBSectionID &RHS) { 351*e8d8bef9SDimitry Andric // We make sure that the section containing the entry block precedes all the 352*e8d8bef9SDimitry Andric // other sections. 353*e8d8bef9SDimitry Andric if (LHS == EntryBBSectionID || RHS == EntryBBSectionID) 354*e8d8bef9SDimitry Andric return LHS == EntryBBSectionID; 355*e8d8bef9SDimitry Andric return LHS.Type == RHS.Type ? LHS.Number < RHS.Number : LHS.Type < RHS.Type; 356*e8d8bef9SDimitry Andric }; 357*e8d8bef9SDimitry Andric 358*e8d8bef9SDimitry Andric // We sort all basic blocks to make sure the basic blocks of every cluster are 359*e8d8bef9SDimitry Andric // contiguous and ordered accordingly. Furthermore, clusters are ordered in 360*e8d8bef9SDimitry Andric // increasing order of their section IDs, with the exception and the 361*e8d8bef9SDimitry Andric // cold section placed at the end of the function. 362*e8d8bef9SDimitry Andric auto Comparator = [&](const MachineBasicBlock &X, 363*e8d8bef9SDimitry Andric const MachineBasicBlock &Y) { 364*e8d8bef9SDimitry Andric auto XSectionID = X.getSectionID(); 365*e8d8bef9SDimitry Andric auto YSectionID = Y.getSectionID(); 366*e8d8bef9SDimitry Andric if (XSectionID != YSectionID) 367*e8d8bef9SDimitry Andric return MBBSectionOrder(XSectionID, YSectionID); 368*e8d8bef9SDimitry Andric // If the two basic block are in the same section, the order is decided by 369*e8d8bef9SDimitry Andric // their position within the section. 370*e8d8bef9SDimitry Andric if (XSectionID.Type == MBBSectionID::SectionType::Default) 371*e8d8bef9SDimitry Andric return FuncBBClusterInfo[X.getNumber()]->PositionInCluster < 372*e8d8bef9SDimitry Andric FuncBBClusterInfo[Y.getNumber()]->PositionInCluster; 373*e8d8bef9SDimitry Andric return X.getNumber() < Y.getNumber(); 374*e8d8bef9SDimitry Andric }; 375*e8d8bef9SDimitry Andric 376*e8d8bef9SDimitry Andric sortBasicBlocksAndUpdateBranches(MF, Comparator); 377*e8d8bef9SDimitry Andric avoidZeroOffsetLandingPad(MF); 378*e8d8bef9SDimitry Andric return true; 379*e8d8bef9SDimitry Andric } 380*e8d8bef9SDimitry Andric 381*e8d8bef9SDimitry Andric // Basic Block Sections can be enabled for a subset of machine basic blocks. 382*e8d8bef9SDimitry Andric // This is done by passing a file containing names of functions for which basic 383*e8d8bef9SDimitry Andric // block sections are desired. Additionally, machine basic block ids of the 384*e8d8bef9SDimitry Andric // functions can also be specified for a finer granularity. Moreover, a cluster 385*e8d8bef9SDimitry Andric // of basic blocks could be assigned to the same section. 386*e8d8bef9SDimitry Andric // A file with basic block sections for all of function main and three blocks 387*e8d8bef9SDimitry Andric // for function foo (of which 1 and 2 are placed in a cluster) looks like this: 388*e8d8bef9SDimitry Andric // ---------------------------- 389*e8d8bef9SDimitry Andric // list.txt: 390*e8d8bef9SDimitry Andric // !main 391*e8d8bef9SDimitry Andric // !foo 392*e8d8bef9SDimitry Andric // !!1 2 393*e8d8bef9SDimitry Andric // !!4 394*e8d8bef9SDimitry Andric static Error getBBClusterInfo(const MemoryBuffer *MBuf, 395*e8d8bef9SDimitry Andric ProgramBBClusterInfoMapTy &ProgramBBClusterInfo, 396*e8d8bef9SDimitry Andric StringMap<StringRef> &FuncAliasMap) { 397*e8d8bef9SDimitry Andric assert(MBuf); 398*e8d8bef9SDimitry Andric line_iterator LineIt(*MBuf, /*SkipBlanks=*/true, /*CommentMarker=*/'#'); 399*e8d8bef9SDimitry Andric 400*e8d8bef9SDimitry Andric auto invalidProfileError = [&](auto Message) { 401*e8d8bef9SDimitry Andric return make_error<StringError>( 402*e8d8bef9SDimitry Andric Twine("Invalid profile " + MBuf->getBufferIdentifier() + " at line " + 403*e8d8bef9SDimitry Andric Twine(LineIt.line_number()) + ": " + Message), 404*e8d8bef9SDimitry Andric inconvertibleErrorCode()); 405*e8d8bef9SDimitry Andric }; 406*e8d8bef9SDimitry Andric 407*e8d8bef9SDimitry Andric auto FI = ProgramBBClusterInfo.end(); 408*e8d8bef9SDimitry Andric 409*e8d8bef9SDimitry Andric // Current cluster ID corresponding to this function. 410*e8d8bef9SDimitry Andric unsigned CurrentCluster = 0; 411*e8d8bef9SDimitry Andric // Current position in the current cluster. 412*e8d8bef9SDimitry Andric unsigned CurrentPosition = 0; 413*e8d8bef9SDimitry Andric 414*e8d8bef9SDimitry Andric // Temporary set to ensure every basic block ID appears once in the clusters 415*e8d8bef9SDimitry Andric // of a function. 416*e8d8bef9SDimitry Andric SmallSet<unsigned, 4> FuncBBIDs; 417*e8d8bef9SDimitry Andric 418*e8d8bef9SDimitry Andric for (; !LineIt.is_at_eof(); ++LineIt) { 419*e8d8bef9SDimitry Andric StringRef S(*LineIt); 420*e8d8bef9SDimitry Andric if (S[0] == '@') 421*e8d8bef9SDimitry Andric continue; 422*e8d8bef9SDimitry Andric // Check for the leading "!" 423*e8d8bef9SDimitry Andric if (!S.consume_front("!") || S.empty()) 424*e8d8bef9SDimitry Andric break; 425*e8d8bef9SDimitry Andric // Check for second "!" which indicates a cluster of basic blocks. 426*e8d8bef9SDimitry Andric if (S.consume_front("!")) { 427*e8d8bef9SDimitry Andric if (FI == ProgramBBClusterInfo.end()) 428*e8d8bef9SDimitry Andric return invalidProfileError( 429*e8d8bef9SDimitry Andric "Cluster list does not follow a function name specifier."); 430*e8d8bef9SDimitry Andric SmallVector<StringRef, 4> BBIndexes; 431*e8d8bef9SDimitry Andric S.split(BBIndexes, ' '); 432*e8d8bef9SDimitry Andric // Reset current cluster position. 433*e8d8bef9SDimitry Andric CurrentPosition = 0; 434*e8d8bef9SDimitry Andric for (auto BBIndexStr : BBIndexes) { 435*e8d8bef9SDimitry Andric unsigned long long BBIndex; 436*e8d8bef9SDimitry Andric if (getAsUnsignedInteger(BBIndexStr, 10, BBIndex)) 437*e8d8bef9SDimitry Andric return invalidProfileError(Twine("Unsigned integer expected: '") + 438*e8d8bef9SDimitry Andric BBIndexStr + "'."); 439*e8d8bef9SDimitry Andric if (!FuncBBIDs.insert(BBIndex).second) 440*e8d8bef9SDimitry Andric return invalidProfileError(Twine("Duplicate basic block id found '") + 441*e8d8bef9SDimitry Andric BBIndexStr + "'."); 442*e8d8bef9SDimitry Andric if (!BBIndex && CurrentPosition) 443*e8d8bef9SDimitry Andric return invalidProfileError("Entry BB (0) does not begin a cluster."); 444*e8d8bef9SDimitry Andric 445*e8d8bef9SDimitry Andric FI->second.emplace_back(BBClusterInfo{ 446*e8d8bef9SDimitry Andric ((unsigned)BBIndex), CurrentCluster, CurrentPosition++}); 447*e8d8bef9SDimitry Andric } 448*e8d8bef9SDimitry Andric CurrentCluster++; 449*e8d8bef9SDimitry Andric } else { // This is a function name specifier. 450*e8d8bef9SDimitry Andric // Function aliases are separated using '/'. We use the first function 451*e8d8bef9SDimitry Andric // name for the cluster info mapping and delegate all other aliases to 452*e8d8bef9SDimitry Andric // this one. 453*e8d8bef9SDimitry Andric SmallVector<StringRef, 4> Aliases; 454*e8d8bef9SDimitry Andric S.split(Aliases, '/'); 455*e8d8bef9SDimitry Andric for (size_t i = 1; i < Aliases.size(); ++i) 456*e8d8bef9SDimitry Andric FuncAliasMap.try_emplace(Aliases[i], Aliases.front()); 457*e8d8bef9SDimitry Andric 458*e8d8bef9SDimitry Andric // Prepare for parsing clusters of this function name. 459*e8d8bef9SDimitry Andric // Start a new cluster map for this function name. 460*e8d8bef9SDimitry Andric FI = ProgramBBClusterInfo.try_emplace(Aliases.front()).first; 461*e8d8bef9SDimitry Andric CurrentCluster = 0; 462*e8d8bef9SDimitry Andric FuncBBIDs.clear(); 463*e8d8bef9SDimitry Andric } 464*e8d8bef9SDimitry Andric } 465*e8d8bef9SDimitry Andric return Error::success(); 466*e8d8bef9SDimitry Andric } 467*e8d8bef9SDimitry Andric 468*e8d8bef9SDimitry Andric bool BasicBlockSections::doInitialization(Module &M) { 469*e8d8bef9SDimitry Andric if (!MBuf) 470*e8d8bef9SDimitry Andric return false; 471*e8d8bef9SDimitry Andric if (auto Err = getBBClusterInfo(MBuf, ProgramBBClusterInfo, FuncAliasMap)) 472*e8d8bef9SDimitry Andric report_fatal_error(std::move(Err)); 473*e8d8bef9SDimitry Andric return false; 474*e8d8bef9SDimitry Andric } 475*e8d8bef9SDimitry Andric 476*e8d8bef9SDimitry Andric void BasicBlockSections::getAnalysisUsage(AnalysisUsage &AU) const { 477*e8d8bef9SDimitry Andric AU.setPreservesAll(); 478*e8d8bef9SDimitry Andric MachineFunctionPass::getAnalysisUsage(AU); 479*e8d8bef9SDimitry Andric } 480*e8d8bef9SDimitry Andric 481*e8d8bef9SDimitry Andric MachineFunctionPass * 482*e8d8bef9SDimitry Andric llvm::createBasicBlockSectionsPass(const MemoryBuffer *Buf) { 483*e8d8bef9SDimitry Andric return new BasicBlockSections(Buf); 484*e8d8bef9SDimitry Andric } 485