diff --git a/llvm/include/llvm/CodeGen/AsmPrinter.h b/llvm/include/llvm/CodeGen/AsmPrinter.h --- a/llvm/include/llvm/CodeGen/AsmPrinter.h +++ b/llvm/include/llvm/CodeGen/AsmPrinter.h @@ -132,6 +132,10 @@ /// default, this is equal to CurrentFnSym. MCSymbol *CurrentFnSymForSize = nullptr; + // The symbol used to represent the start of the current BB section of the + // function. This is used to calculate the size of the BB section. + MCSymbol *CurrentSectionBeginSym = nullptr; + /// Map global GOT equivalent MCSymbols to GlobalVariables and keep track of /// its number of uses by other globals. using GOTEquivUsePair = std::pair; diff --git a/llvm/include/llvm/CodeGen/MachineBasicBlock.h b/llvm/include/llvm/CodeGen/MachineBasicBlock.h --- a/llvm/include/llvm/CodeGen/MachineBasicBlock.h +++ b/llvm/include/llvm/CodeGen/MachineBasicBlock.h @@ -46,19 +46,6 @@ class TargetRegisterClass; class TargetRegisterInfo; -enum MachineBasicBlockSection : unsigned { - /// This is also the order of sections in a function. Basic blocks that are - /// part of the original function section (entry block) come first, followed - /// by exception handling basic blocks, cold basic blocks and finally basic - // blocks that need unique sections. - MBBS_Entry, - MBBS_Exception, - MBBS_Cold, - MBBS_Unique, - /// None implies no sections for any basic block, the default. - MBBS_None, -}; - template <> struct ilist_traits { private: friend class MachineBasicBlock; // Set by the owning MachineBasicBlock. @@ -91,6 +78,10 @@ : PhysReg(PhysReg), LaneMask(LaneMask) {} }; + // Special section IDs for the cold and exception section + const static unsigned ColdSectionID = UINT_MAX; + const static unsigned ExceptionSectionID = UINT_MAX - 1; + private: using Instructions = ilist>; @@ -143,8 +134,8 @@ /// Indicate that this basic block is the entry block of a cleanup funclet. bool IsCleanupFuncletEntry = false; - /// Stores the Section type of the basic block with basic block sections. - MachineBasicBlockSection SectionType = MBBS_None; + /// Stores the Section ID of the basic block with basic block sections. + Optional SectionID; /// Default target of the callbr of a basic block. bool InlineAsmBrDefaultTarget = false; @@ -440,11 +431,11 @@ /// Returns true if this block ends any section. bool isEndSection() const; - /// Returns the type of section this basic block belongs to. - MachineBasicBlockSection getSectionType() const { return SectionType; } + /// Returns the the section id that this basic block belongs to. + Optional getSectionID() const { return SectionID; } /// Indicate that the basic block belongs to a Section Type. - void setSectionType(MachineBasicBlockSection V) { SectionType = V; } + void setSectionID(unsigned V) { SectionID = V; } /// Returns true if this is the indirect dest of an INLINEASM_BR. bool isInlineAsmBrIndirectTarget(const MachineBasicBlock *Tgt) const { diff --git a/llvm/include/llvm/CodeGen/MachineFunction.h b/llvm/include/llvm/CodeGen/MachineFunction.h --- a/llvm/include/llvm/CodeGen/MachineFunction.h +++ b/llvm/include/llvm/CodeGen/MachineFunction.h @@ -346,11 +346,6 @@ /// Section Type for basic blocks, only relevant with basic block sections. BasicBlockSection BBSectionsType = BasicBlockSection::None; - /// With Basic Block Sections, this stores the bb ranges of cold and - /// exception sections. - std::pair ColdSectionRange = {-1, -1}; - std::pair ExceptionSectionRange = {-1, -1}; - /// List of C++ TypeInfo used. std::vector TypeInfos; @@ -505,19 +500,6 @@ void setBBSectionsType(BasicBlockSection V) { BBSectionsType = V; } - void setSectionRange(); - - /// Returns true if this basic block number starts a cold or exception - /// section. - bool isSectionStartMBB(int N) const { - return (N == ColdSectionRange.first || N == ExceptionSectionRange.first); - } - - /// Returns true if this basic block ends a cold or exception section. - bool isSectionEndMBB(int N) const { - return (N == ColdSectionRange.second || N == ExceptionSectionRange.second); - } - /// Creates basic block Labels for this function. void createBBLabels(); diff --git a/llvm/lib/CodeGen/AsmPrinter/AsmPrinter.cpp b/llvm/lib/CodeGen/AsmPrinter/AsmPrinter.cpp --- a/llvm/lib/CodeGen/AsmPrinter/AsmPrinter.cpp +++ b/llvm/lib/CodeGen/AsmPrinter/AsmPrinter.cpp @@ -1097,9 +1097,8 @@ // Print out code for the function. bool HasAnyRealCode = false; int NumInstsInFunction = 0; - bool emitBBSections = MF->hasBBSections(); MachineBasicBlock *EndOfRegularSectionMBB = nullptr; - if (emitBBSections) { + if (MF->hasBBSections()) { EndOfRegularSectionMBB = const_cast(MF->front().getSectionEndMBB()); assert(EndOfRegularSectionMBB->isEndSection() && @@ -1185,8 +1184,7 @@ } } } - if (&MBB != EndOfRegularSectionMBB && - (MF->hasBBLabels() || MBB.isEndSection())) { + if (MF->hasBBLabels()) { // Emit size directive for the size of this basic block. Create a symbol // for the end of the basic block. MCSymbol *CurrentBBEnd = OutContext.createTempSymbol(); @@ -1194,9 +1192,24 @@ MCSymbolRefExpr::create(CurrentBBEnd, OutContext), MCSymbolRefExpr::create(MBB.getSymbol(), OutContext), OutContext); OutStreamer->emitLabel(CurrentBBEnd); - MBB.setEndMCSymbol(CurrentBBEnd); OutStreamer->emitELFSize(MBB.getSymbol(), SizeExp); } + + if (MBB.isEndSection()) { + if (MBB.getSectionID() != MF->front().getSectionID()) { + // Emit size directive for the size of this basic block section. The + // size directive for the regular section will be emitted as the + // function size. + MCSymbol *CurrentSectionEnd = OutContext.createTempSymbol(); + const MCExpr *SizeExp = MCBinaryExpr::createSub( + MCSymbolRefExpr::create(CurrentSectionEnd, OutContext), + MCSymbolRefExpr::create(CurrentSectionBeginSym, OutContext), + OutContext); + OutStreamer->emitLabel(CurrentSectionEnd); + MBB.setEndMCSymbol(CurrentSectionEnd); + OutStreamer->emitELFSize(CurrentSectionBeginSym, SizeExp); + } + } emitBasicBlockEnd(MBB); } @@ -1231,7 +1244,7 @@ } // Switch to the original section if basic block sections was used. - if (emitBBSections) + if (MF->hasBBSections()) OutStreamer->SwitchSection(MF->getSection()); const Function &F = MF->getFunction(); @@ -1249,7 +1262,7 @@ emitFunctionBodyEnd(); if (needFuncLabelsForEHOrDebugInfo(*MF, MMI) || - MAI->hasDotTypeDotSizeDirective() || emitBBSections) { + MAI->hasDotTypeDotSizeDirective() || MF->hasBBSections()) { // Create a symbol for the end of function. CurrentFnEnd = createTempSymbol("func_end"); OutStreamer->emitLabel(CurrentFnEnd); @@ -1272,7 +1285,7 @@ HI.Handler->markFunctionEnd(); } - if (emitBBSections) + if (MF->hasBBSections()) EndOfRegularSectionMBB->setEndMCSymbol(CurrentFnEnd); // Print out jump tables referenced by the function. @@ -1758,6 +1771,7 @@ CurrentFnSymForSize = CurrentFnSym; CurrentFnBegin = nullptr; + CurrentSectionBeginSym = nullptr; CurExceptionSym = nullptr; bool NeedsLocalForSize = MAI->needsLocalForSize(); if (F.hasFnAttribute("patchable-function-entry") || @@ -2995,7 +3009,6 @@ /// MachineBasicBlock, an alignment (if present) and a comment describing /// it if appropriate. void AsmPrinter::emitBasicBlockStart(const MachineBasicBlock &MBB) { - bool BBSections = MF->hasBBSections(); // End the previous funclet and start a new one. if (MBB.isEHFuncletEntry()) { for (const HandlerInfo &HI : Handlers) { @@ -3005,7 +3018,7 @@ } // Emit an alignment directive for this block, if needed. - if (MBB.pred_empty() || !BBSections) { + if (MBB.pred_empty() || !MF->hasBBSections()) { const Align Alignment = MBB.getAlignment(); if (Alignment != Align(1)) emitAlignment(Alignment); @@ -3041,7 +3054,7 @@ emitBasicBlockLoopComments(MBB, MLI, *this); } - bool emitBBLabels = BBSections || MF->hasBBLabels(); + bool emitBBLabels = MF->hasBBSections() || MF->hasBBLabels(); if (MBB.pred_empty() || (!emitBBLabels && isBlockOnlyReachableByFallthrough(&MBB) && !MBB.isEHFuncletEntry() && !MBB.hasLabelMustBeEmitted())) { @@ -3054,23 +3067,23 @@ if (isVerbose() && MBB.hasLabelMustBeEmitted()) { OutStreamer->AddComment("Label of block must be emitted"); } - // With -fbasicblock-sections, a basic block can start a new section. - if (MBB.getSectionType() == MachineBasicBlockSection::MBBS_Exception) { - // Create the exception section for this function. - OutStreamer->SwitchSection( - getObjFileLowering().getNamedSectionForMachineBasicBlock( - MF->getFunction(), MBB, TM, ".eh")); - } else if (MBB.getSectionType() == MachineBasicBlockSection::MBBS_Cold) { - // Create the cold section here. - OutStreamer->SwitchSection( - getObjFileLowering().getNamedSectionForMachineBasicBlock( - MF->getFunction(), MBB, TM, ".unlikely")); - } else if (MBB.isBeginSection() && MBB.isEndSection()) { - OutStreamer->SwitchSection( - getObjFileLowering().getSectionForMachineBasicBlock(MF->getFunction(), - MBB, TM)); - } else if (BBSections) { - OutStreamer->SwitchSection(MF->getSection()); + if (MBB.isBeginSection()) { + // With -fbasicblock-sections, a basic block can start a new section. + if (MBB.getSectionID() == MachineBasicBlock::ExceptionSectionID) { + // Create the exception section for this function. + OutStreamer->SwitchSection( + getObjFileLowering().getNamedSectionForMachineBasicBlock( + MF->getFunction(), MBB, TM, ".eh")); + } else if (MBB.getSectionID() == MachineBasicBlock::ColdSectionID) { + // Create the cold section here. + OutStreamer->SwitchSection( + getObjFileLowering().getNamedSectionForMachineBasicBlock( + MF->getFunction(), MBB, TM, ".unlikely")); + } else + OutStreamer->SwitchSection( + getObjFileLowering().getSectionForMachineBasicBlock( + MF->getFunction(), MBB, TM)); + CurrentSectionBeginSym = MBB.getSymbol(); } OutStreamer->emitLabel(MBB.getSymbol()); } diff --git a/llvm/lib/CodeGen/BBSectionsPrepare.cpp b/llvm/lib/CodeGen/BBSectionsPrepare.cpp --- a/llvm/lib/CodeGen/BBSectionsPrepare.cpp +++ b/llvm/lib/CodeGen/BBSectionsPrepare.cpp @@ -9,47 +9,43 @@ // BBSectionsPrepare implementation. // // The purpose of this pass is to assign sections to basic blocks when -// -fbasicblock-sections= option is used. Exception landing pad blocks are -// specially handled by grouping them in a single section. Further, with +// -fbasicblock-sections= option is used. Further, with // profile information only the subset of basic blocks with profiles are placed -// in a separate section and the rest are grouped in a cold section. +// in separate sections and the rest are grouped in a cold section. The +// exception handling blocks are treated specially to ensure they are all in one +// seciton. // // Basic Block Sections // ==================== // -// With option, -fbasicblock-sections=, each basic block could be placed in a -// unique ELF text section in the object file along with a symbol labelling the -// basic block. The linker can then order the basic block sections in any -// arbitrary sequence which when done correctly can encapsulate block layout, -// function layout and function splitting optimizations. However, there are a -// couple of challenges to be addressed for this to be feasible: +// With option, -fbasicblock-sections=list, every function may be split into +// clusters of basic blocks. Every cluster will be emitted into a separate +// section with its basic blocks sequenced in the given order. +// To get the optimized performance, the clusters must form an optimal BB layout +// for the function. +// Every cluster's section is labeled with a symbol to allow the linker to +// reorder the sections in any arbitrary sequence. +// A global order of these sections would encapsulate the function layout. // -// 1. The compiler must not allow any implicit fall-through between any two -// adjacent basic blocks as they could be reordered at link time to be -// non-adjacent. In other words, the compiler must make a fall-through -// between adjacent basic blocks explicit by retaining the direct jump -// instruction that jumps to the next basic block. +// There are a couple of challenges to be addressed: // -// 2. All inter-basic block branch targets would now need to be resolved by the +// 1. The last basic block of every cluster should not have any implicit +// fallthrough to its next basic block, as it can be reordered by the linker. +// The compiler should make these fallthroughs explicit by adding +// unconditional jumps.. +// +// 2. All inter-cluster branch targets would now need to be resolved by the // linker as they cannot be calculated during compile time. This is done // using static relocations. Further, the compiler tries to use short branch // instructions on some ISAs for small branch offsets. This is not possible -// with basic block sections as the offset is not determined at compile time, -// and long branch instructions have to be used everywhere. -// -// 3. Each additional section bloats object file sizes by tens of bytes. The -// number of basic blocks can be potentially very large compared to the size -// of functions and can bloat object sizes significantly. Option -// fbasicblock-sections= also takes a file path which can be used to specify -// a subset of basic blocks that needs unique sections to keep the bloats -// small. +// for inter-cluster branches as the offset is not determined at compile +// time, and therefore, long branch instructions have to be used for those. // -// 4. Debug Information (DebugInfo) and Call Frame Information (CFI) emission +// 3. Debug Information (DebugInfo) and Call Frame Information (CFI) emission // needs special handling with basic block sections. DebugInfo needs to be // emitted with more relocations as basic block sections can break a // function into potentially several disjoint pieces, and CFI needs to be -// emitted per basic block. This also bloats the object file and binary -// sizes. +// emitted per cluster. This also bloats the object file and binary sizes. // // Basic Block Labels // ================== @@ -83,6 +79,8 @@ #include "llvm/Support/MemoryBuffer.h" #include "llvm/Target/TargetMachine.h" +#include +#include #include using llvm::SmallSet; @@ -92,21 +90,38 @@ namespace { +struct BBClusterInfo { + unsigned ClusterID; + unsigned PositionInCluster; +}; + class BBSectionsPrepare : public MachineFunctionPass { public: static char ID; - StringMap> BBSectionsList; + + // This would hold the basic-block-sections profile. const MemoryBuffer *MBuf = nullptr; - BBSectionsPrepare() : MachineFunctionPass(ID) { - initializeBBSectionsPreparePass(*PassRegistry::getPassRegistry()); - } + // This encapsulates the BB cluster information for every function. + // For every function name, we have a map from (some of) its basic block ids + // to its cluster information. The cluster information for every basic block + // includes its cluster ID along with the position of the basic block in that + // cluster. + StringMap> BBClusterInfoMap; + + // Some functions have alias names. We use this map to find the main alias + // name for which we have mapping in BBClusterInfoMap. + StringMap FuncAliasMap; BBSectionsPrepare(const MemoryBuffer *Buf) : MachineFunctionPass(ID), MBuf(Buf) { initializeBBSectionsPreparePass(*PassRegistry::getPassRegistry()); }; + BBSectionsPrepare() : MachineFunctionPass(ID) { + initializeBBSectionsPreparePass(*PassRegistry::getPassRegistry()); + } + StringRef getPassName() const override { return "Basic Block Sections Analysis"; } @@ -119,30 +134,38 @@ /// Identify basic blocks that need separate sections and prepare to emit them /// accordingly. bool runOnMachineFunction(MachineFunction &MF) override; + + // This function provides the BBCluster information associated with a function + // name. It returns true if mapping is found and false otherwise. + bool getBBClusterInfoForFunction(StringRef s, + DenseMap &m) { + auto r = FuncAliasMap.find(s); + StringRef aliasName = r == FuncAliasMap.end() ? s : r->second; + auto p = BBClusterInfoMap.find(aliasName); + if (p == BBClusterInfoMap.end()) + return false; + m = p->second; + return true; + } }; } // end anonymous namespace char BBSectionsPrepare::ID = 0; INITIALIZE_PASS(BBSectionsPrepare, "bbsections-prepare", - "Determine if a basic block needs a special section", false, - false) + "Prepares for basic block sections, by splitting functions " + "into clusters of basic blocks.", + false, false) // This inserts an unconditional branch at the end of MBB to the next basic // block S if and only if the control-flow implicitly falls through from MBB to -// S and S and MBB belong to different sections. This is necessary with basic -// block sections as MBB and S could be potentially reordered. +// S. This is necessary with basic block sections as they can be reordered by +// clustering or by the linker. static void insertUnconditionalFallthroughBranch(MachineBasicBlock &MBB) { MachineBasicBlock *Fallthrough = MBB.getFallThrough(); - if (Fallthrough == nullptr) return; - // If this basic block and the Fallthrough basic block are in the same - // section then do not insert the jump. - if (MBB.sameSection(Fallthrough)) - return; - const TargetInstrInfo *TII = MBB.getParent()->getSubtarget().getInstrInfo(); SmallVector Cond; MachineBasicBlock *TBB = nullptr, *FBB = nullptr; @@ -158,71 +181,99 @@ TII->insertBranch(MBB, Fallthrough, nullptr, Cond, DL); } -/// This function sorts basic blocks according to the sections in which they are -/// emitted. Basic block sections automatically turn on function sections so -/// the entry block is in the function section. The other sections that are -/// created are: -/// 1) Exception section - basic blocks that are landing pads -/// 2) Cold section - basic blocks that will not have unique sections. -/// 3) Unique section - one per basic block that is emitted in a unique section. -static bool assignSectionsAndSortBasicBlocks( - MachineFunction &MF, - const StringMap> &BBSectionsList) { - SmallSet S = BBSectionsList.lookup(MF.getName()); +// This function optimizes the branching instructions of every +// basic block (except those at the end of the sections) in a given function. +static void optimizeBBJumps(MachineFunction &MF) { + const TargetInstrInfo *TII = MF.getSubtarget().getInstrInfo(); + SmallVector Cond; + for (auto &MBB : MF) + if (!MBB.isEndSection()) { + Cond.clear(); + MachineBasicBlock *TBB = nullptr, *FBB = nullptr; // For analyzeBranch. + if (!TII->analyzeBranch(MBB, TBB, FBB, Cond)) + MBB.updateTerminator(); + } +} - bool HasHotEHPads = false; +// This function sorts basic blocks according to the cluster's information. +// All explicitly specified clusters of basic blocks will be ordered +// accordingly. All non-specified BBs go into a separate "Cold" section. +// Additionally, if exception handling landing pads end up in more than one +// clusters, they are moved into a single "Exception" section. Eventually, +// clusters are ordered in increasing order of their IDs, with the "Exception" +// and "Cold" succeeding all other clusters. +static bool assignSectionsAndSortBasicBlocks( + MachineFunction &MF, DenseMap &FuncBBClusterInfo) { + // This is the set of sections which have EHPads in them. + SmallSet EHPadsSections; for (auto &MBB : MF) { - // Entry basic block cannot start another section because the function - // starts one already. - if (MBB.getNumber() == MF.front().getNumber()) { - MBB.setSectionType(MachineBasicBlockSection::MBBS_Entry); - continue; - } - // Check if this BB is a cold basic block. With the list option, all cold - // basic blocks can be clustered in a single cold section. - // All Exception landing pads must be in a single section. If all the - // landing pads are cold, it can be kept in the cold section. Otherwise, we - // create a separate exception section. - bool isColdBB = ((MF.getTarget().getBBSectionsType() == - llvm::BasicBlockSection::List) && - !S.empty() && !S.count(MBB.getNumber())); - if (isColdBB) { - MBB.setSectionType(MachineBasicBlockSection::MBBS_Cold); - } else if (MBB.isEHPad()) { - // We handle non-cold basic eh blocks later. - HasHotEHPads = true; - } else { - // Place this MBB in a unique section. A unique section begins and ends - // that section by definition. - MBB.setSectionType(MachineBasicBlockSection::MBBS_Unique); + // With the 'all' option, every basic block is placed in a unique section. + // With the 'list' option, every basic block is placed in a section + // associated with its cluster, unless we want sections for every basic + // block in this function (if FuncBBClusterInfo is empty). + if (MF.getTarget().getBBSectionsType() == llvm::BasicBlockSection::All || + FuncBBClusterInfo.empty()) { + // If unique sections are desired for all basic blocks of the function, we + // set every basic block's section ID equal to its number (basic block + // id). This further ensures that basic blocks are ordered canonically. + MBB.setSectionID(MBB.getNumber()); + } else if (FuncBBClusterInfo.count(MBB.getNumber())) + MBB.setSectionID(FuncBBClusterInfo.lookup(MBB.getNumber()).ClusterID); + else { + // BB goes into the special cold section if it is not specified in the + // cluster info map. + MBB.setSectionID(MachineBasicBlock::ColdSectionID); } + + if (MBB.isEHPad()) + EHPadsSections.insert(MBB.getSectionID().getValue()); } - // If some EH Pads are not cold then we move all EH Pads to the exception - // section as we require that all EH Pads be in a single section. - if (HasHotEHPads) { + // If EHPads are in more than one section, we move all of them to a specific + // exception section, as we need all EH Pads to be in a single section. + if (EHPadsSections.size() > 1) { std::for_each(MF.begin(), MF.end(), [&](MachineBasicBlock &MBB) { if (MBB.isEHPad()) - MBB.setSectionType(MachineBasicBlockSection::MBBS_Exception); + MBB.setSectionID(MachineBasicBlock::ExceptionSectionID); }); } for (auto &MBB : MF) { // With -fbasicblock-sections, fall through blocks must be made - // explicitly reachable. Do this after sections is set as - // unnecessary fallthroughs can be avoided. + // explicitly reachable. insertUnconditionalFallthroughBranch(MBB); } - MF.sort(([&](MachineBasicBlock &X, MachineBasicBlock &Y) { - unsigned TypeX = X.getSectionType(); - unsigned TypeY = Y.getSectionType(); + // We make sure that the cluster including the entry basic block precedes all + // other clusters. + auto EntrySectionID = MF.front().getSectionID().getValue(); + + // We sort all basic blocks to make sure the basic blocks of every cluster are + // contiguous and ordered accordingly. Furthermore, clusters are ordered in + // increasing order of their section IDs, with the exception and the + // cold section placed at the end of the function. + MF.sort([&](MachineBasicBlock &X, MachineBasicBlock &Y) { + auto XSectionID = X.getSectionID().getValue(); + auto YSectionID = Y.getSectionID().getValue(); + // If the two basic block are in the same section, the order is decided by + // their position within the section. + if (XSectionID == YSectionID) + return XSectionID < MachineBasicBlock::ExceptionSectionID + ? FuncBBClusterInfo.lookup(X.getNumber()).PositionInCluster < + FuncBBClusterInfo.lookup(Y.getNumber()).PositionInCluster + : X.getNumber() < Y.getNumber(); + // We make sure that the section containing the entry block precedes all the + // other sections. + if (XSectionID == EntrySectionID || YSectionID == EntrySectionID) + return XSectionID == EntrySectionID; + return XSectionID < YSectionID; + }); + + // After ordering basic blocks, we optimize/remove branches which were + // previously added by insertUnconditionalFallthroughBranch. + optimizeBBJumps(MF); - return (TypeX != TypeY) ? TypeX < TypeY : X.getNumber() < Y.getNumber(); - })); - - MF.setSectionRange(); return true; } @@ -243,13 +294,13 @@ return true; } + DenseMap FuncBBClusterInfo; if (BBSectionsType == BasicBlockSection::List && - BBSectionsList.find(MF.getName()) == BBSectionsList.end()) + !getBBClusterInfoForFunction(MF.getName(), FuncBBClusterInfo)) return true; - MF.setBBSectionsType(BBSectionsType); MF.createBBLabels(); - assignSectionsAndSortBasicBlocks(MF, BBSectionsList); + assignSectionsAndSortBasicBlocks(MF, FuncBBClusterInfo); return true; } @@ -257,23 +308,30 @@ // Basic Block Sections can be enabled for a subset of machine basic blocks. // This is done by passing a file containing names of functions for which basic // block sections are desired. Additionally, machine basic block ids of the -// functions can also be specified for a finer granularity. -// A file with basic block sections for all of function main and two blocks for -// function foo looks like this: +// functions can also be specified for a finer granularity. Moreover, a cluster +// of basic blocks could be assigned to the same section. +// A file with basic block sections for all of function main and three blocks +// for function foo (of which 1 and 2 are placed in a cluster) looks like this: // ---------------------------- // list.txt: // !main // !foo -// !!2 +// !!1 2 // !!4 -static bool getBBSectionsList(const MemoryBuffer *MBuf, - StringMap> &bbMap) { +static bool +getBBClusterInfo(const MemoryBuffer *MBuf, + StringMap> &bbClusterInfoMap, + StringMap &funcAliasMap) { if (!MBuf) return false; line_iterator LineIt(*MBuf, /*SkipBlanks=*/true, /*CommentMarker=*/'#'); - StringMap>::iterator fi = bbMap.end(); + StringMap>::iterator fi = + bbClusterInfoMap.end(); + + unsigned CurrentCluster = 0; + unsigned CurrentPosition = 0; for (; !LineIt.is_at_eof(); ++LineIt) { StringRef s(*LineIt); @@ -282,17 +340,53 @@ // Check for the leading "!" if (!s.consume_front("!") || s.empty()) break; - // Check for second "!" which encodes basic block ids. + // Check for second "!" which indicates a cluster of basic blocks. if (s.consume_front("!")) { - if (fi != bbMap.end()) - fi->second.insert(std::stoi(s.str())); - else + if (fi == bbClusterInfoMap.end()) { + errs() << "Could not process profile: " << MBuf->getBufferIdentifier() + << " at line " << Twine(LineIt.line_number()) + << ": Does not follow a function name.\n"; return false; + } + std::istringstream iss(s.str()); + std::vector BBIndexes( + (std::istream_iterator(iss)), + std::istream_iterator()); + // Current position in the current cluster of basic blocks. + CurrentPosition = 0; + for (auto &BBIndexStr : BBIndexes) { + unsigned BBIndex; + if (StringRef(BBIndexStr).getAsInteger(10, BBIndex)) { + errs() << "Could not process profile: " << MBuf->getBufferIdentifier() + << " at line " << Twine(LineIt.line_number()) << ": " + << BBIndexStr << " is not a number!\n"; + return false; + } + if (!BBIndex && CurrentPosition) { + errs() << "Could not process profile " << MBuf->getBufferIdentifier() + << " at line " << Twine(LineIt.line_number()) + << ": Entry BB in the middle of the BB Cluster list!\n"; + return false; + } + fi->second.try_emplace( + BBIndex, BBClusterInfo{CurrentCluster, CurrentPosition++}); + } + CurrentCluster++; } else { + // Function aliases are separated using '/'. We use the first function + // name for the cluster info mapping and delegate all other aliases to + // this one. + auto P = s.split('/'); // Start a new function. - auto R = bbMap.try_emplace(s.split('/').first); - fi = R.first; - assert(R.second); + fi = bbClusterInfoMap.try_emplace(P.first).first; + + auto aliasStr = P.second; + while (aliasStr != "") { + auto Q = aliasStr.split('/'); + funcAliasMap.try_emplace(Q.first, P.first); + aliasStr = Q.second; + } + CurrentCluster = 0; } } return true; @@ -300,7 +394,8 @@ bool BBSectionsPrepare::doInitialization(Module &M) { if (MBuf) - getBBSectionsList(MBuf, BBSectionsList); + if (!getBBClusterInfo(MBuf, BBClusterInfoMap, FuncAliasMap)) + BBClusterInfoMap.clear(); return true; } diff --git a/llvm/lib/CodeGen/MIRParser/MIParser.cpp b/llvm/lib/CodeGen/MIRParser/MIParser.cpp --- a/llvm/lib/CodeGen/MIRParser/MIParser.cpp +++ b/llvm/lib/CodeGen/MIRParser/MIParser.cpp @@ -495,7 +495,7 @@ bool parseOffset(int64_t &Offset); bool parseAlignment(unsigned &Alignment); bool parseAddrspace(unsigned &Addrspace); - bool parseMBBS(MachineBasicBlockSection &T); + bool parseSectionID(Optional &SID); bool parseOperandsOffset(MachineOperand &Op); bool parseIRValue(const Value *&V); bool parseMemoryOperandFlag(MachineMemOperand::Flags &Flags); @@ -620,21 +620,24 @@ return true; } -// Parse Machine Basic Block Section Type. -bool MIParser::parseMBBS(MachineBasicBlockSection &T) { +// Parse Machine Basic Block Section ID. +bool MIParser::parseSectionID(Optional &SID) { assert(Token.is(MIToken::kw_bbsections)); lex(); - const StringRef &S = Token.stringValue(); - if (S == "Entry") - T = MBBS_Entry; - else if (S == "Exception") - T = MBBS_Exception; - else if (S == "Cold") - T = MBBS_Cold; - else if (S == "Unique") - T = MBBS_Unique; - else - return error("Unknown Section Type"); + if (Token.is(MIToken::IntegerLiteral)) { + unsigned Value = 0; + if (getUnsigned(Value)) + return error("Uknown Section ID"); + SID = Value; + } else { + const StringRef &S = Token.stringValue(); + if (S == "Exception") + SID = MachineBasicBlock::ExceptionSectionID; + else if (S == "Cold") + SID = MachineBasicBlock::ColdSectionID; + else + return error("Unknown Section ID"); + } lex(); return false; } @@ -651,7 +654,7 @@ bool HasAddressTaken = false; bool IsLandingPad = false; bool IsEHFuncletEntry = false; - MachineBasicBlockSection SectionType = MBBS_None; + Optional SectionID; unsigned Alignment = 0; BasicBlock *BB = nullptr; if (consumeIfPresent(MIToken::lparen)) { @@ -681,7 +684,7 @@ lex(); break; case MIToken::kw_bbsections: - if (parseMBBS(SectionType)) + if (parseSectionID(SectionID)) return true; break; default: @@ -714,8 +717,8 @@ MBB->setHasAddressTaken(); MBB->setIsEHPad(IsLandingPad); MBB->setIsEHFuncletEntry(IsEHFuncletEntry); - if (SectionType != MBBS_None) { - MBB->setSectionType(SectionType); + if (SectionID.hasValue()) { + MBB->setSectionID(SectionID.getValue()); MF.setBBSectionsType(BasicBlockSection::List); } return false; diff --git a/llvm/lib/CodeGen/MIRParser/MIRParser.cpp b/llvm/lib/CodeGen/MIRParser/MIRParser.cpp --- a/llvm/lib/CodeGen/MIRParser/MIRParser.cpp +++ b/llvm/lib/CodeGen/MIRParser/MIRParser.cpp @@ -442,10 +442,8 @@ if (MF.getTarget().getBBSectionsType() == BasicBlockSection::Labels) { MF.createBBLabels(); MF.setBBSectionsType(BasicBlockSection::Labels); - } else if (MF.hasBBSections()) { - MF.setSectionRange(); + } else if (MF.hasBBSections()) MF.createBBLabels(); - } PFS.SM = &SM; // Initialize the frame information after creating all the MBBs so that the diff --git a/llvm/lib/CodeGen/MIRPrinter.cpp b/llvm/lib/CodeGen/MIRPrinter.cpp --- a/llvm/lib/CodeGen/MIRPrinter.cpp +++ b/llvm/lib/CodeGen/MIRPrinter.cpp @@ -640,24 +640,18 @@ OS << "align " << MBB.getAlignment().value(); HasAttributes = true; } - if (MBB.getSectionType() != MBBS_None) { + if (MBB.getSectionID().hasValue()) { OS << (HasAttributes ? ", " : " ("); OS << "bbsections "; - switch (MBB.getSectionType()) { - case MBBS_Entry: - OS << "Entry"; + switch (MBB.getSectionID().getValue()) { + case MachineBasicBlock::ExceptionSectionID: + OS << "Excetion"; break; - case MBBS_Exception: - OS << "Exception"; - break; - case MBBS_Cold: + case MachineBasicBlock::ColdSectionID: OS << "Cold"; break; - case MBBS_Unique: - OS << "Unique"; - break; default: - llvm_unreachable("No such section type"); + OS << MBB.getSectionID(); } HasAttributes = true; } diff --git a/llvm/lib/CodeGen/MachineBasicBlock.cpp b/llvm/lib/CodeGen/MachineBasicBlock.cpp --- a/llvm/lib/CodeGen/MachineBasicBlock.cpp +++ b/llvm/lib/CodeGen/MachineBasicBlock.cpp @@ -553,12 +553,7 @@ if (this == Other) return true; - if (this->getSectionType() != Other->getSectionType()) - return false; - - // If either is in a unique section, return false. - if (this->getSectionType() == llvm::MachineBasicBlockSection::MBBS_Unique || - Other->getSectionType() == llvm::MachineBasicBlockSection::MBBS_Unique) + if (this->getSectionID() != Other->getSectionID()) return false; return true; @@ -580,14 +575,20 @@ // Returns true if this block begins any section. bool MachineBasicBlock::isBeginSection() const { - return (SectionType == MBBS_Entry || SectionType == MBBS_Unique || - getParent()->isSectionStartMBB(getNumber())); + const MachineFunction *MF = getParent(); + if (!MF->hasBBSections()) + return false; + auto I = std::next(this->getReverseIterator()); + return (I == MF->rend()) || (I->getSectionID() != getSectionID()); } // Returns true if this block begins any section. bool MachineBasicBlock::isEndSection() const { - return (SectionType == MBBS_Entry || SectionType == MBBS_Unique || - getParent()->isSectionEndMBB(getNumber())); + const MachineFunction *MF = getParent(); + if (!MF->hasBBSections()) + return false; + auto I = std::next(this->getIterator()); + return (I == MF->end()) || (I->getSectionID() != getSectionID()); } void MachineBasicBlock::updateTerminator() { @@ -1572,3 +1573,6 @@ "Liveness information is accurate"); return LiveIns.begin(); } + +const unsigned MachineBasicBlock::ColdSectionID; +const unsigned MachineBasicBlock::ExceptionSectionID; diff --git a/llvm/lib/CodeGen/MachineFunction.cpp b/llvm/lib/CodeGen/MachineFunction.cpp --- a/llvm/lib/CodeGen/MachineFunction.cpp +++ b/llvm/lib/CodeGen/MachineFunction.cpp @@ -341,32 +341,6 @@ MBBNumbering.resize(BlockNo); } -/// This sets the section ranges of cold or exception section with basic block -/// sections. -void MachineFunction::setSectionRange() { - // Compute the Section Range of cold and exception basic blocks. Find the - // first and last block of each range. - auto SectionRange = - ([&](llvm::MachineBasicBlockSection S) -> std::pair { - auto MBBP = - std::find_if(begin(), end(), [&](MachineBasicBlock &MBB) -> bool { - return MBB.getSectionType() == S; - }); - if (MBBP == end()) - return std::make_pair(-1, -1); - - auto MBBQ = - std::find_if(rbegin(), rend(), [&](MachineBasicBlock &MBB) -> bool { - return MBB.getSectionType() == S; - }); - assert(MBBQ != rend() && "Section end not found!"); - return std::make_pair(MBBP->getNumber(), MBBQ->getNumber()); - }); - - ExceptionSectionRange = SectionRange(MBBS_Exception); - ColdSectionRange = SectionRange(llvm::MBBS_Cold); -} - /// This is used with -fbasicblock-sections or -fbasicblock-labels option. /// A unary encoding of basic block labels is done to keep ".strtab" sizes /// small. diff --git a/llvm/test/CodeGen/X86/basicblock-sections-eh.ll b/llvm/test/CodeGen/X86/basicblock-sections-eh.ll --- a/llvm/test/CodeGen/X86/basicblock-sections-eh.ll +++ b/llvm/test/CodeGen/X86/basicblock-sections-eh.ll @@ -80,5 +80,5 @@ ;LINUX-SECTIONS: .section .text._Z3foob,"ax",@progbits ;LINUX-SECTIONS: _Z3foob: -;LINUX-SECTIONS: .section .text._Z3foob.eh,"ax",@progbits +;LINUX-SECTIONS: .section .text._Z3foob.laara.BB._Z3foob,"ax",@progbits ;LINUX-SECTIONS: l{{[a|r]*}}.BB._Z3foob: diff --git a/llvm/test/CodeGen/X86/basicblock-sections-listbb.ll b/llvm/test/CodeGen/X86/basicblock-sections-listbb.ll --- a/llvm/test/CodeGen/X86/basicblock-sections-listbb.ll +++ b/llvm/test/CodeGen/X86/basicblock-sections-listbb.ll @@ -35,4 +35,4 @@ ; LINUX-SECTIONS: r.BB._Z3bazb: ; LINUX-SECTIONS: .section .text._Z3bazb.rr.BB._Z3bazb,"ax",@progbits,unique ; LINUX-SECTIONS: rr.BB._Z3bazb: -; LINUX-SECTIONS: .size rr.BB._Z3bazb, .Ltmp1-rr.BB._Z3bazb +; LINUX-SECTIONS: .size rr.BB._Z3bazb, .Ltmp0-rr.BB._Z3bazb diff --git a/llvm/test/CodeGen/X86/basicblock-sections-mir-parse.mir b/llvm/test/CodeGen/X86/basicblock-sections-mir-parse.mir --- a/llvm/test/CodeGen/X86/basicblock-sections-mir-parse.mir +++ b/llvm/test/CodeGen/X86/basicblock-sections-mir-parse.mir @@ -87,7 +87,7 @@ constants: [] machineFunctionInfo: {} body: | - bb.0 (%ir-block.1, bbsections Entry): + bb.0 (%ir-block.1, align 4, bbsections 0): successors: %bb.2(0x40000000), %bb.1(0x40000000) liveins: $edi @@ -102,19 +102,19 @@ JCC_1 %bb.2, 4, implicit killed $eflags JMP_1 %bb.1 - bb.1 (%ir-block.7, bbsections Unique): + bb.1 (%ir-block.7, bbsections 1): successors: %bb.3(0x80000000) MOV32mi $rbp, 1, $noreg, -8, $noreg, 1 :: (store 4 into %ir.2) JMP_1 %bb.3 - bb.2 (%ir-block.8, bbsections Unique): + bb.2 (%ir-block.8, bbsections 2): successors: %bb.3(0x80000000) MOV32mi $rbp, 1, $noreg, -8, $noreg, 0 :: (store 4 into %ir.2) JMP_1 %bb.3 - bb.3 (%ir-block.9, bbsections Unique): + bb.3 (%ir-block.9, bbsections 3): renamable $eax = MOV32rm $rbp, 1, $noreg, -8, $noreg :: (load 4 from %ir.2) $rbp = frame-destroy POP64r implicit-def $rsp, implicit $rsp CFI_INSTRUCTION def_cfa $rsp, 8 diff --git a/llvm/test/CodeGen/X86/basicblock-sections-mir-print.ll b/llvm/test/CodeGen/X86/basicblock-sections-mir-print.ll --- a/llvm/test/CodeGen/X86/basicblock-sections-mir-print.ll +++ b/llvm/test/CodeGen/X86/basicblock-sections-mir-print.ll @@ -26,7 +26,7 @@ ret i32 %10 } -; CHECK: bbsections Entry -; CHECK: bbsections Cold -; CHECK: bbsections Cold -; CHECK: bbsections Unique +; CHECK: bb.0 (%ir-block.1, bbsections Cold): +; CHECK: bb.2 (%ir-block.8, bbsections Cold): +; CHECK: bb.3 (%ir-block.9, bbsections Cold): +; CHECK: bb.1 (%ir-block.7, bbsections 0)