Extend BasicBlock sections to allow specifying clusters of basic blocks in the same section.
Differential Revision: https://reviews.llvm.org/D76954
diff --git a/llvm/lib/CodeGen/AsmPrinter/AsmPrinter.cpp b/llvm/lib/CodeGen/AsmPrinter/AsmPrinter.cpp
index b7bd6c9..8583760 100644
--- a/llvm/lib/CodeGen/AsmPrinter/AsmPrinter.cpp
+++ b/llvm/lib/CodeGen/AsmPrinter/AsmPrinter.cpp
@@ -1097,14 +1097,6 @@
// Print out code for the function.
bool HasAnyRealCode = false;
int NumInstsInFunction = 0;
- bool emitBBSections = MF->hasBBSections();
- MachineBasicBlock *EndOfRegularSectionMBB = nullptr;
- if (emitBBSections) {
- EndOfRegularSectionMBB =
- const_cast<MachineBasicBlock *>(MF->front().getSectionEndMBB());
- assert(EndOfRegularSectionMBB->isEndSection() &&
- "The MBB at the end of the regular section must end a section");
- }
for (auto &MBB : *MF) {
// Print a label for the basic block.
@@ -1185,17 +1177,41 @@
}
}
}
- if (&MBB != EndOfRegularSectionMBB &&
- (MF->hasBBLabels() || MBB.isEndSection())) {
- // Emit size directive for the size of this basic block. Create a symbol
- // for the end of the basic block.
- MCSymbol *CurrentBBEnd = OutContext.createTempSymbol();
+
+ // We need a temporary symbol for the end of this basic block, if either we
+ // have BBLabels enabled and we want to emit size directive for the BBs, or
+ // if this basic blocks marks the end of a section (except the section
+ // containing the entry basic block as the end symbol for that section is
+ // CurrentFnEnd).
+ MCSymbol *CurrentBBEnd = nullptr;
+ if ((MAI->hasDotTypeDotSizeDirective() && MF->hasBBLabels()) ||
+ (MBB.isEndSection() && !MBB.sameSection(&MF->front()))) {
+ CurrentBBEnd = OutContext.createTempSymbol();
+ OutStreamer->emitLabel(CurrentBBEnd);
+ }
+
+ // Helper for emitting the size directive associated with a basic block
+ // symbol.
+ auto emitELFSizeDirective = [&](MCSymbol *SymForSize) {
+ assert(CurrentBBEnd && "Basicblock end symbol not set!");
const MCExpr *SizeExp = MCBinaryExpr::createSub(
MCSymbolRefExpr::create(CurrentBBEnd, OutContext),
- MCSymbolRefExpr::create(MBB.getSymbol(), OutContext), OutContext);
- OutStreamer->emitLabel(CurrentBBEnd);
- MBB.setEndMCSymbol(CurrentBBEnd);
- OutStreamer->emitELFSize(MBB.getSymbol(), SizeExp);
+ MCSymbolRefExpr::create(SymForSize, OutContext), OutContext);
+ OutStreamer->emitELFSize(SymForSize, SizeExp);
+ };
+
+ // Emit size directive for the size of each basic block, if BBLabels is
+ // enabled.
+ if (MAI->hasDotTypeDotSizeDirective() && MF->hasBBLabels())
+ emitELFSizeDirective(MBB.getSymbol());
+
+ // Emit size directive for the size of each basic block section once we
+ // get to the end of that section.
+ if (MBB.isEndSection()) {
+ if (!MBB.sameSection(&MF->front())) {
+ if (MAI->hasDotTypeDotSizeDirective())
+ emitELFSizeDirective(CurrentSectionBeginSym);
+ }
}
emitBasicBlockEnd(MBB);
}
@@ -1230,9 +1246,8 @@
}
}
- // Switch to the original section if basic block sections was used.
- if (emitBBSections)
- OutStreamer->SwitchSection(MF->getSection());
+ // Switch to the original section in case basic block sections was used.
+ OutStreamer->SwitchSection(MF->getSection());
const Function &F = MF->getFunction();
for (const auto &BB : F) {
@@ -1249,7 +1264,7 @@
emitFunctionBodyEnd();
if (needFuncLabelsForEHOrDebugInfo(*MF, MMI) ||
- MAI->hasDotTypeDotSizeDirective() || emitBBSections) {
+ MAI->hasDotTypeDotSizeDirective()) {
// Create a symbol for the end of function.
CurrentFnEnd = createTempSymbol("func_end");
OutStreamer->emitLabel(CurrentFnEnd);
@@ -1272,8 +1287,6 @@
HI.Handler->markFunctionEnd();
}
- if (emitBBSections)
- EndOfRegularSectionMBB->setEndMCSymbol(CurrentFnEnd);
// Print out jump tables referenced by the function.
emitJumpTableInfo();
@@ -1753,6 +1766,7 @@
CurrentFnSymForSize = CurrentFnSym;
CurrentFnBegin = nullptr;
+ CurrentSectionBeginSym = nullptr;
CurExceptionSym = nullptr;
bool NeedsLocalForSize = MAI->needsLocalForSize();
if (F.hasFnAttribute("patchable-function-entry") ||
@@ -2981,7 +2995,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) {
@@ -2991,11 +3004,9 @@
}
// Emit an alignment directive for this block, if needed.
- if (MBB.pred_empty() || !BBSections) {
- const Align Alignment = MBB.getAlignment();
- if (Alignment != Align(1))
- emitAlignment(Alignment);
- }
+ const Align Alignment = MBB.getAlignment();
+ if (Alignment != Align(1))
+ emitAlignment(Alignment);
// If the block has its address taken, emit any labels that were used to
// reference the block. It is possible that there is more than one label
@@ -3027,9 +3038,8 @@
emitBasicBlockLoopComments(MBB, MLI, *this);
}
- bool emitBBLabels = BBSections || MF->hasBBLabels();
if (MBB.pred_empty() ||
- (!emitBBLabels && isBlockOnlyReachableByFallthrough(&MBB) &&
+ (!MF->hasBBLabels() && isBlockOnlyReachableByFallthrough(&MBB) &&
!MBB.isEHFuncletEntry() && !MBB.hasLabelMustBeEmitted())) {
if (isVerbose()) {
// NOTE: Want this comment at start of line, don't emit with AddComment.
@@ -3040,23 +3050,12 @@
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()) {
+ // Switch to a new section if this basic block must begin a section.
+ if (MBB.isBeginSection()) {
OutStreamer->SwitchSection(
getObjFileLowering().getSectionForMachineBasicBlock(MF->getFunction(),
MBB, TM));
- } else if (BBSections) {
- OutStreamer->SwitchSection(MF->getSection());
+ CurrentSectionBeginSym = MBB.getSymbol();
}
OutStreamer->emitLabel(MBB.getSymbol());
}
@@ -3090,7 +3089,7 @@
/// the predecessor and this block is a fall-through.
bool AsmPrinter::
isBlockOnlyReachableByFallthrough(const MachineBasicBlock *MBB) const {
- // With BasicBlock Sections, no block is a fall through.
+ // With BasicBlock Sections, beginning of the section is not a fallthrough.
if (MBB->isBeginSection())
return false;
diff --git a/llvm/lib/CodeGen/BBSectionsPrepare.cpp b/llvm/lib/CodeGen/BBSectionsPrepare.cpp
index 6e81801a..eb71a38 100644
--- a/llvm/lib/CodeGen/BBSectionsPrepare.cpp
+++ b/llvm/lib/CodeGen/BBSectionsPrepare.cpp
@@ -9,47 +9,41 @@
// 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
-// 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.
+// -fbasicblock-sections= option is used. Further, with profile information only
+// the subset of basic blocks with profiles are placed 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.
+// for inter-cluster branches as the offset is not determined at compile
+// time, and therefore, long branch instructions have to be used for those.
//
-// 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.
-//
-// 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
// ==================
@@ -70,7 +64,9 @@
//
//===----------------------------------------------------------------------===//
+#include "llvm/ADT/Optional.h"
#include "llvm/ADT/SmallSet.h"
+#include "llvm/ADT/SmallVector.h"
#include "llvm/ADT/StringMap.h"
#include "llvm/ADT/StringRef.h"
#include "llvm/CodeGen/MachineFunction.h"
@@ -79,34 +75,59 @@
#include "llvm/CodeGen/Passes.h"
#include "llvm/CodeGen/TargetInstrInfo.h"
#include "llvm/InitializePasses.h"
+#include "llvm/Support/Error.h"
#include "llvm/Support/LineIterator.h"
#include "llvm/Support/MemoryBuffer.h"
#include "llvm/Target/TargetMachine.h"
-#include <string>
-
using llvm::SmallSet;
+using llvm::SmallVector;
using llvm::StringMap;
using llvm::StringRef;
using namespace llvm;
namespace {
+// This struct represents the cluster information for a machine basic block.
+struct BBClusterInfo {
+ // MachineBasicBlock ID.
+ unsigned MBBNumber;
+ // Cluster ID this basic block belongs to.
+ unsigned ClusterID;
+ // Position of basic block within the cluster.
+ unsigned PositionInCluster;
+};
+
+using ProgramBBClusterInfoMapTy = StringMap<SmallVector<BBClusterInfo, 4>>;
+
class BBSectionsPrepare : public MachineFunctionPass {
public:
static char ID;
- StringMap<SmallSet<unsigned, 4>> BBSectionsList;
+
+ // This contains the basic-block-sections profile.
const MemoryBuffer *MBuf = nullptr;
- BBSectionsPrepare() : MachineFunctionPass(ID) {
- initializeBBSectionsPreparePass(*PassRegistry::getPassRegistry());
- }
+ // This encapsulates the BB cluster information for the whole program.
+ //
+ // For every function name, it contains the cluster information for (all or
+ // some of) its basic blocks. The cluster information for every basic block
+ // includes its cluster ID along with the position of the basic block in that
+ // cluster.
+ ProgramBBClusterInfoMapTy ProgramBBClusterInfo;
+
+ // Some functions have alias names. We use this map to find the main alias
+ // name for which we have mapping in ProgramBBClusterInfo.
+ StringMap<StringRef> 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";
}
@@ -125,104 +146,181 @@
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.
-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();
+// This function updates and optimizes the branching instructions of every basic
+// block in a given function to account for changes in the layout.
+static void updateBranches(
+ MachineFunction &MF,
+ const SmallVector<MachineBasicBlock *, 4> &PreLayoutFallThroughs) {
+ const TargetInstrInfo *TII = MF.getSubtarget().getInstrInfo();
SmallVector<MachineOperand, 4> Cond;
- MachineBasicBlock *TBB = nullptr, *FBB = nullptr;
+ for (auto &MBB : MF) {
+ auto NextMBBI = std::next(MBB.getIterator());
+ auto *FTMBB = PreLayoutFallThroughs[MBB.getNumber()];
+ // If this block had a fallthrough before we need an explicit unconditional
+ // branch to that block if either
+ // 1- the block ends a section, which means its next block may be
+ // reorderd by the linker, or
+ // 2- the fallthrough block is not adjacent to the block in the new
+ // order.
+ if (FTMBB && (MBB.isEndSection() || &*NextMBBI != FTMBB))
+ TII->insertUnconditionalBranch(MBB, FTMBB, MBB.findBranchDebugLoc());
- // If a branch to the fall through block already exists, return.
- if (!TII->analyzeBranch(MBB, TBB, FBB, Cond) &&
- (TBB == Fallthrough || FBB == Fallthrough)) {
- return;
+ // We do not optimize branches for machine basic blocks ending sections, as
+ // their adjacent block might be reordered by the linker.
+ if (MBB.isEndSection())
+ continue;
+
+ // It might be possible to optimize branches by flipping the branch
+ // condition.
+ Cond.clear();
+ MachineBasicBlock *TBB = nullptr, *FBB = nullptr; // For analyzeBranch.
+ if (TII->analyzeBranch(MBB, TBB, FBB, Cond))
+ continue;
+ MBB.updateTerminator();
}
-
- Cond.clear();
- DebugLoc DL = MBB.findBranchDebugLoc();
- 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.
+// This function provides the BBCluster information associated with a function.
+// Returns true if a valid association exists and false otherwise.
+static bool getBBClusterInfoForFunction(
+ const MachineFunction &MF, const StringMap<StringRef> FuncAliasMap,
+ const ProgramBBClusterInfoMapTy &ProgramBBClusterInfo,
+ std::vector<Optional<BBClusterInfo>> &V) {
+ // Get the main alias name for the function.
+ auto FuncName = MF.getName();
+ auto R = FuncAliasMap.find(FuncName);
+ StringRef AliasName = R == FuncAliasMap.end() ? FuncName : R->second;
+
+ // Find the assoicated cluster information.
+ auto P = ProgramBBClusterInfo.find(AliasName);
+ if (P == ProgramBBClusterInfo.end())
+ return false;
+
+ if (P->second.empty()) {
+ // This indicates that sections are desired for all basic blocks of this
+ // function. We clear the BBClusterInfo vector to denote this.
+ V.clear();
+ return true;
+ }
+
+ V.resize(MF.getNumBlockIDs());
+ for (auto bbClusterInfo : P->second) {
+ // Bail out if the cluster information contains invalid MBB numbers.
+ if (bbClusterInfo.MBBNumber >= MF.getNumBlockIDs())
+ return false;
+ V[bbClusterInfo.MBBNumber] = bbClusterInfo;
+ }
+ return true;
+}
+
+// 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.
+// FuncBBClusterInfo represent the cluster information for basic blocks. If this
+// is empty, it means unique sections for all basic blocks in the function.
static bool assignSectionsAndSortBasicBlocks(
MachineFunction &MF,
- const StringMap<SmallSet<unsigned, 4>> &BBSectionsList) {
- SmallSet<unsigned, 4> S = BBSectionsList.lookup(MF.getName());
-
- bool HasHotEHPads = false;
+ const std::vector<Optional<BBClusterInfo>> &FuncBBClusterInfo) {
+ assert(MF.hasBBSections() && "BB Sections is not set for function.");
+ // This variable stores the section ID of the cluster containing eh_pads (if
+ // all eh_pads are one cluster). If more than one cluster contain eh_pads, we
+ // set it equal to ExceptionSectionID.
+ Optional<MBBSectionID> EHPadsSectionID;
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;
+ // 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 individual unique 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({static_cast<unsigned int>(MBB.getNumber())});
+ } else if (FuncBBClusterInfo[MBB.getNumber()].hasValue())
+ MBB.setSectionID(FuncBBClusterInfo[MBB.getNumber()]->ClusterID);
+ else {
+ // BB goes into the special cold section if it is not specified in the
+ // cluster info map.
+ MBB.setSectionID(MBBSectionID::ColdSectionID);
}
- // 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);
+
+ if (MBB.isEHPad() && EHPadsSectionID != MBB.getSectionID() &&
+ EHPadsSectionID != MBBSectionID::ExceptionSectionID) {
+ // If we already have one cluster containing eh_pads, this must be updated
+ // to ExceptionSectionID. Otherwise, we set it equal to the current
+ // section ID.
+ EHPadsSectionID = EHPadsSectionID.hasValue()
+ ? MBBSectionID::ExceptionSectionID
+ : MBB.getSectionID();
}
}
- // 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) {
- std::for_each(MF.begin(), MF.end(), [&](MachineBasicBlock &MBB) {
+ // If EHPads are in more than one section, this places all of them in the
+ // special exception section.
+ if (EHPadsSectionID == MBBSectionID::ExceptionSectionID)
+ for (auto &MBB : MF)
if (MBB.isEHPad())
- MBB.setSectionType(MachineBasicBlockSection::MBBS_Exception);
- });
- }
+ MBB.setSectionID(EHPadsSectionID.getValue());
- 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.
- insertUnconditionalFallthroughBranch(MBB);
- }
+ SmallVector<MachineBasicBlock *, 4> PreLayoutFallThroughs(
+ MF.getNumBlockIDs());
+ for (auto &MBB : MF)
+ PreLayoutFallThroughs[MBB.getNumber()] = MBB.getFallThrough();
- 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 EntryBBSectionID = MF.front().getSectionID();
- return (TypeX != TypeY) ? TypeX < TypeY : X.getNumber() < Y.getNumber();
- }));
+ // Helper function for ordering BB sections as follows:
+ // * Entry section (section including the entry block).
+ // * Regular sections (in increasing order of their Number).
+ // ...
+ // * Exception section
+ // * Cold section
+ auto MBBSectionOrder = [EntryBBSectionID](const MBBSectionID &LHS,
+ const MBBSectionID &RHS) {
+ // We make sure that the section containing the entry block precedes all the
+ // other sections.
+ if (LHS == EntryBBSectionID || RHS == EntryBBSectionID)
+ return LHS == EntryBBSectionID;
+ return LHS.Type == RHS.Type ? LHS.Number < RHS.Number : LHS.Type < RHS.Type;
+ };
- MF.setSectionRange();
+ // 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();
+ auto YSectionID = Y.getSectionID();
+ if (XSectionID != YSectionID)
+ return MBBSectionOrder(XSectionID, YSectionID);
+ // If the two basic block are in the same section, the order is decided by
+ // their position within the section.
+ if (XSectionID.Type == MBBSectionID::SectionType::Default)
+ return FuncBBClusterInfo[X.getNumber()]->PositionInCluster <
+ FuncBBClusterInfo[Y.getNumber()]->PositionInCluster;
+ return X.getNumber() < Y.getNumber();
+ });
+
+ // Set IsBeginSection and IsEndSection according to the assigned section IDs.
+ MF.assignBeginEndSections();
+
+ // After reordering basic blocks, we must update basic block branches to
+ // insert explicit fallthrough branches when required and optimize branches
+ // when possible.
+ updateBranches(MF, PreLayoutFallThroughs);
+
return true;
}
@@ -230,7 +328,6 @@
auto BBSectionsType = MF.getTarget().getBBSectionsType();
assert(BBSectionsType != BasicBlockSection::None &&
"BB Sections not enabled!");
-
// Renumber blocks before sorting them for basic block sections. This is
// useful during sorting, basic blocks in the same section will retain the
// default order. This renumbering should also be done for basic block
@@ -243,65 +340,110 @@
return true;
}
+ std::vector<Optional<BBClusterInfo>> FuncBBClusterInfo;
if (BBSectionsType == BasicBlockSection::List &&
- BBSectionsList.find(MF.getName()) == BBSectionsList.end())
+ !getBBClusterInfoForFunction(MF, FuncAliasMap, ProgramBBClusterInfo,
+ FuncBBClusterInfo))
return true;
-
MF.setBBSectionsType(BBSectionsType);
MF.createBBLabels();
- assignSectionsAndSortBasicBlocks(MF, BBSectionsList);
-
+ assignSectionsAndSortBasicBlocks(MF, FuncBBClusterInfo);
return true;
}
// 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<SmallSet<unsigned, 4>> &bbMap) {
- if (!MBuf)
- return false;
-
+static Error getBBClusterInfo(const MemoryBuffer *MBuf,
+ ProgramBBClusterInfoMapTy &ProgramBBClusterInfo,
+ StringMap<StringRef> &FuncAliasMap) {
+ assert(MBuf);
line_iterator LineIt(*MBuf, /*SkipBlanks=*/true, /*CommentMarker=*/'#');
- StringMap<SmallSet<unsigned, 4>>::iterator fi = bbMap.end();
+ auto invalidProfileError = [&](auto Message) {
+ return make_error<StringError>(
+ Twine("Invalid profile " + MBuf->getBufferIdentifier() + " at line " +
+ Twine(LineIt.line_number()) + ": " + Message),
+ inconvertibleErrorCode());
+ };
+
+ auto FI = ProgramBBClusterInfo.end();
+
+ // Current cluster ID corresponding to this function.
+ unsigned CurrentCluster = 0;
+ // Current position in the current cluster.
+ unsigned CurrentPosition = 0;
+
+ // Temporary set to ensure every basic block ID appears once in the clusters
+ // of a function.
+ SmallSet<unsigned, 4> FuncBBIDs;
for (; !LineIt.is_at_eof(); ++LineIt) {
- StringRef s(*LineIt);
- if (s[0] == '@')
+ StringRef S(*LineIt);
+ if (S[0] == '@')
continue;
// Check for the leading "!"
- if (!s.consume_front("!") || s.empty())
+ if (!S.consume_front("!") || S.empty())
break;
- // Check for second "!" which encodes basic block ids.
- if (s.consume_front("!")) {
- if (fi != bbMap.end())
- fi->second.insert(std::stoi(s.str()));
- else
- return false;
- } else {
- // Start a new function.
- auto R = bbMap.try_emplace(s.split('/').first);
- fi = R.first;
- assert(R.second);
+ // Check for second "!" which indicates a cluster of basic blocks.
+ if (S.consume_front("!")) {
+ if (FI == ProgramBBClusterInfo.end())
+ return invalidProfileError(
+ "Cluster list does not follow a function name specifier.");
+ SmallVector<StringRef, 4> BBIndexes;
+ S.split(BBIndexes, ' ');
+ // Reset current cluster position.
+ CurrentPosition = 0;
+ for (auto BBIndexStr : BBIndexes) {
+ unsigned long long BBIndex;
+ if (getAsUnsignedInteger(BBIndexStr, 10, BBIndex))
+ return invalidProfileError(Twine("Unsigned integer expected: '") +
+ BBIndexStr + "'.");
+ if (!FuncBBIDs.insert(BBIndex).second)
+ return invalidProfileError(Twine("Duplicate basic block id found '") +
+ BBIndexStr + "'.");
+ if (!BBIndex && CurrentPosition)
+ return invalidProfileError("Entry BB (0) does not begin a cluster.");
+
+ FI->second.emplace_back(BBClusterInfo{
+ ((unsigned)BBIndex), CurrentCluster, CurrentPosition++});
+ }
+ CurrentCluster++;
+ } else { // This is a function name specifier.
+ // Function aliases are separated using '/'. We use the first function
+ // name for the cluster info mapping and delegate all other aliases to
+ // this one.
+ SmallVector<StringRef, 4> Aliases;
+ S.split(Aliases, '/');
+ for (size_t i = 1; i < Aliases.size(); ++i)
+ FuncAliasMap.try_emplace(Aliases[i], Aliases.front());
+
+ // Prepare for parsing clusters of this function name.
+ // Start a new cluster map for this function name.
+ FI = ProgramBBClusterInfo.try_emplace(Aliases.front()).first;
+ CurrentCluster = 0;
+ FuncBBIDs.clear();
}
}
- return true;
+ return Error::success();
}
bool BBSectionsPrepare::doInitialization(Module &M) {
- if (MBuf)
- getBBSectionsList(MBuf, BBSectionsList);
- return true;
+ if (!MBuf)
+ return false;
+ if (auto Err = getBBClusterInfo(MBuf, ProgramBBClusterInfo, FuncAliasMap))
+ report_fatal_error(std::move(Err));
+ return false;
}
void BBSectionsPrepare::getAnalysisUsage(AnalysisUsage &AU) const {
diff --git a/llvm/lib/CodeGen/MIRParser/MIParser.cpp b/llvm/lib/CodeGen/MIRParser/MIParser.cpp
index 68de9f4..0107e5e 100644
--- 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<MBBSectionID> &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<MBBSectionID> &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("Unknown Section ID");
+ SID = MBBSectionID{Value};
+ } else {
+ const StringRef &S = Token.stringValue();
+ if (S == "Exception")
+ SID = MBBSectionID::ExceptionSectionID;
+ else if (S == "Cold")
+ SID = MBBSectionID::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<MBBSectionID> 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
index 5b6f71a..eb17434 100644
--- a/llvm/lib/CodeGen/MIRParser/MIRParser.cpp
+++ b/llvm/lib/CodeGen/MIRParser/MIRParser.cpp
@@ -442,8 +442,8 @@
MF.createBBLabels();
MF.setBBSectionsType(BasicBlockSection::Labels);
} else if (MF.hasBBSections()) {
- MF.setSectionRange();
MF.createBBLabels();
+ MF.assignBeginEndSections();
}
PFS.SM = &SM;
diff --git a/llvm/lib/CodeGen/MIRPrinter.cpp b/llvm/lib/CodeGen/MIRPrinter.cpp
index 0853181..5504480 100644
--- a/llvm/lib/CodeGen/MIRPrinter.cpp
+++ b/llvm/lib/CodeGen/MIRPrinter.cpp
@@ -643,24 +643,18 @@
OS << "align " << MBB.getAlignment().value();
HasAttributes = true;
}
- if (MBB.getSectionType() != MBBS_None) {
+ if (MBB.getSectionID() != MBBSectionID(0)) {
OS << (HasAttributes ? ", " : " (");
OS << "bbsections ";
- switch (MBB.getSectionType()) {
- case MBBS_Entry:
- OS << "Entry";
- break;
- case MBBS_Exception:
+ switch (MBB.getSectionID().Type) {
+ case MBBSectionID::SectionType::Exception:
OS << "Exception";
break;
- case MBBS_Cold:
+ case MBBSectionID::SectionType::Cold:
OS << "Cold";
break;
- case MBBS_Unique:
- OS << "Unique";
- break;
default:
- llvm_unreachable("No such section type");
+ OS << MBB.getSectionID().Number;
}
HasAttributes = true;
}
diff --git a/llvm/lib/CodeGen/MachineBasicBlock.cpp b/llvm/lib/CodeGen/MachineBasicBlock.cpp
index 3fa60dd..5f46086 100644
--- a/llvm/lib/CodeGen/MachineBasicBlock.cpp
+++ b/llvm/lib/CodeGen/MachineBasicBlock.cpp
@@ -62,7 +62,9 @@
MCContext &Ctx = MF->getContext();
auto Prefix = Ctx.getAsmInfo()->getPrivateLabelPrefix();
- bool BasicBlockSymbols = MF->hasBBSections() || MF->hasBBLabels();
+ // We emit a non-temporary symbol for every basic block if we have BBLabels
+ // or -- with basic block sections -- when a basic block begins a section.
+ bool BasicBlockSymbols = isBeginSection() || MF->hasBBLabels();
auto Delimiter = BasicBlockSymbols ? "." : "_";
assert(getNumber() >= 0 && "cannot get label for unreachable MBB");
@@ -548,48 +550,6 @@
getParent()->splice(++NewBefore->getIterator(), getIterator());
}
-// Returns true if this basic block and the Other are in the same section.
-bool MachineBasicBlock::sameSection(const MachineBasicBlock *Other) const {
- 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)
- return false;
-
- return true;
-}
-
-const MachineBasicBlock *MachineBasicBlock::getSectionEndMBB() const {
- if (this->isEndSection())
- return this;
- auto I = std::next(this->getIterator());
- const MachineFunction *MF = getParent();
- while (I != MF->end()) {
- const MachineBasicBlock &MBB = *I;
- if (MBB.isEndSection())
- return &MBB;
- I = std::next(I);
- }
- llvm_unreachable("No End Basic Block for this section.");
-}
-
-// Returns true if this block begins any section.
-bool MachineBasicBlock::isBeginSection() const {
- return (SectionType == MBBS_Entry || SectionType == MBBS_Unique ||
- getParent()->isSectionStartMBB(getNumber()));
-}
-
-// Returns true if this block begins any section.
-bool MachineBasicBlock::isEndSection() const {
- return (SectionType == MBBS_Entry || SectionType == MBBS_Unique ||
- getParent()->isSectionEndMBB(getNumber()));
-}
-
void MachineBasicBlock::updateTerminator() {
const TargetInstrInfo *TII = getParent()->getSubtarget().getInstrInfo();
// A block with no successors has no concerns with fall-through edges.
@@ -1572,3 +1532,7 @@
"Liveness information is accurate");
return LiveIns.begin();
}
+
+const MBBSectionID MBBSectionID::ColdSectionID(MBBSectionID::SectionType::Cold);
+const MBBSectionID
+ MBBSectionID::ExceptionSectionID(MBBSectionID::SectionType::Exception);
diff --git a/llvm/lib/CodeGen/MachineFunction.cpp b/llvm/lib/CodeGen/MachineFunction.cpp
index 1b89333..464f389 100644
--- a/llvm/lib/CodeGen/MachineFunction.cpp
+++ b/llvm/lib/CodeGen/MachineFunction.cpp
@@ -340,32 +340,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<int, int> {
- 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.
@@ -393,6 +367,22 @@
}
}
+/// This method iterates over the basic blocks and assigns their IsBeginSection
+/// and IsEndSection fields. This must be called after MBB layout is finalized
+/// and the SectionID's are assigned to MBBs.
+void MachineFunction::assignBeginEndSections() {
+ front().setIsBeginSection();
+ auto CurrentSectionID = front().getSectionID();
+ for (auto MBBI = std::next(begin()), E = end(); MBBI != E; ++MBBI) {
+ if (MBBI->getSectionID() == CurrentSectionID)
+ continue;
+ MBBI->setIsBeginSection();
+ std::prev(MBBI)->setIsEndSection();
+ CurrentSectionID = MBBI->getSectionID();
+ }
+ back().setIsEndSection();
+}
+
/// Allocate a new MachineInstr. Use this instead of `new MachineInstr'.
MachineInstr *MachineFunction::CreateMachineInstr(const MCInstrDesc &MCID,
const DebugLoc &DL,
diff --git a/llvm/lib/CodeGen/TargetLoweringObjectFileImpl.cpp b/llvm/lib/CodeGen/TargetLoweringObjectFileImpl.cpp
index b96cba4..1794669 100644
--- a/llvm/lib/CodeGen/TargetLoweringObjectFileImpl.cpp
+++ b/llvm/lib/CodeGen/TargetLoweringObjectFileImpl.cpp
@@ -769,14 +769,31 @@
MCSection *TargetLoweringObjectFileELF::getSectionForMachineBasicBlock(
const Function &F, const MachineBasicBlock &MBB,
const TargetMachine &TM) const {
+ assert(MBB.isBeginSection() && "Basic block does not start a section!");
SmallString<128> Name;
Name = (static_cast<MCSectionELF *>(MBB.getParent()->getSection()))
->getSectionName();
- if (TM.getUniqueBBSectionNames()) {
- Name += ".";
- Name += MBB.getSymbol()->getName();
+ unsigned UniqueID = MCContext::GenericSectionID;
+
+ switch (MBB.getSectionID().Type) {
+ // Append suffixes to represent special cold and exception sections.
+ case MBBSectionID::SectionType::Exception:
+ Name += ".eh";
+ break;
+ case MBBSectionID::SectionType::Cold:
+ Name += ".unlikely";
+ break;
+ // For regular sections, either use a unique name, or a unique ID for the
+ // section.
+ default:
+ if (TM.getUniqueBBSectionNames()) {
+ Name += ".";
+ Name += MBB.getSymbol()->getName();
+ } else
+ UniqueID = NextUniqueID++;
+ break;
}
- unsigned UniqueID = NextUniqueID++;
+
unsigned Flags = ELF::SHF_ALLOC | ELF::SHF_EXECINSTR;
std::string GroupName = "";
if (F.hasComdat()) {
@@ -788,33 +805,6 @@
nullptr);
}
-MCSection *TargetLoweringObjectFileELF::getNamedSectionForMachineBasicBlock(
- const Function &F, const MachineBasicBlock &MBB, const TargetMachine &TM,
- const char *Suffix) const {
- SmallString<128> Name;
- Name = (static_cast<MCSectionELF *>(MBB.getParent()->getSection()))
- ->getSectionName();
-
- // If unique section names is off, explicity add the function name to the
- // section name to make sure named sections for functions are unique
- // across the module.
- if (!TM.getUniqueSectionNames()) {
- Name += ".";
- Name += MBB.getParent()->getName();
- }
-
- Name += Suffix;
-
- unsigned Flags = ELF::SHF_ALLOC | ELF::SHF_EXECINSTR;
- std::string GroupName = "";
- if (F.hasComdat()) {
- Flags |= ELF::SHF_GROUP;
- GroupName = F.getComdat()->getName().str();
- }
- return getContext().getELFSection(Name, ELF::SHT_PROGBITS, Flags,
- 0 /* Entry Size */, GroupName);
-}
-
static MCSectionELF *getStaticStructorSection(MCContext &Ctx, bool UseInitArray,
bool IsCtor, unsigned Priority,
const MCSymbol *KeySym) {