Basic Block Sections support in LLVM.
This is the second patch in a series of patches to enable basic block
sections support.
This patch adds support for:
* Creating direct jumps at the end of basic blocks that have fall
through instructions.
* New pass, bbsections-prepare, that analyzes placement of basic blocks
in sections.
* Actual placing of a basic block in a unique section with special
handling of exception handling blocks.
* Supports placing a subset of basic blocks in a unique section.
* Support for MIR serialization and deserialization with basic block
sections.
Parent patch : D68063
Differential Revision: https://reviews.llvm.org/D73674
diff --git a/llvm/lib/CodeGen/AsmPrinter/AsmPrinter.cpp b/llvm/lib/CodeGen/AsmPrinter/AsmPrinter.cpp
index 31b53d7..7d0050f 100644
--- a/llvm/lib/CodeGen/AsmPrinter/AsmPrinter.cpp
+++ b/llvm/lib/CodeGen/AsmPrinter/AsmPrinter.cpp
@@ -682,7 +682,9 @@
emitConstantPool();
// Print the 'header' of function.
- OutStreamer->SwitchSection(getObjFileLowering().SectionForGlobal(&F, TM));
+ MF->setSection(getObjFileLowering().SectionForGlobal(&F, TM));
+ OutStreamer->SwitchSection(MF->getSection());
+
emitVisibility(CurrentFnSym, F.getVisibility());
if (MAI->needsFunctionDescriptors() &&
@@ -1095,6 +1097,15 @@
// 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.
emitBasicBlockStart(MBB);
@@ -1174,7 +1185,18 @@
}
}
}
-
+ 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();
+ 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);
+ }
emitBasicBlockEnd(MBB);
}
@@ -1208,6 +1230,10 @@
}
}
+ // Switch to the original section if basic block sections was used.
+ if (emitBBSections)
+ OutStreamer->SwitchSection(MF->getSection());
+
const Function &F = MF->getFunction();
for (const auto &BB : F) {
if (!BB.hasAddressTaken())
@@ -1223,7 +1249,7 @@
emitFunctionBodyEnd();
if (needFuncLabelsForEHOrDebugInfo(*MF, MMI) ||
- MAI->hasDotTypeDotSizeDirective()) {
+ MAI->hasDotTypeDotSizeDirective() || emitBBSections) {
// Create a symbol for the end of function.
CurrentFnEnd = createTempSymbol("func_end");
OutStreamer->emitLabel(CurrentFnEnd);
@@ -1246,6 +1272,9 @@
HI.Handler->markFunctionEnd();
}
+ if (emitBBSections)
+ EndOfRegularSectionMBB->setEndMCSymbol(CurrentFnEnd);
+
// Print out jump tables referenced by the function.
emitJumpTableInfo();
@@ -2973,10 +3002,11 @@
PrintChildLoopComment(OS, Loop, AP.getFunctionNumber());
}
-/// EmitBasicBlockStart - This method prints the label for the specified
+/// emitBasicBlockStart - This method prints the label for the specified
/// 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) {
@@ -2986,9 +3016,11 @@
}
// Emit an alignment directive for this block, if needed.
- const Align Alignment = MBB.getAlignment();
- if (Alignment != Align(1))
- emitAlignment(Alignment);
+ if (MBB.pred_empty() || !BBSections) {
+ 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
@@ -3020,18 +3052,37 @@
emitBasicBlockLoopComments(MBB, MLI, *this);
}
- // Print the main label for the block.
+ bool emitBBLabels = BBSections || MF->hasBBLabels();
if (MBB.pred_empty() ||
- (isBlockOnlyReachableByFallthrough(&MBB) && !MBB.isEHFuncletEntry() &&
- !MBB.hasLabelMustBeEmitted())) {
+ (!emitBBLabels && isBlockOnlyReachableByFallthrough(&MBB) &&
+ !MBB.isEHFuncletEntry() && !MBB.hasLabelMustBeEmitted())) {
if (isVerbose()) {
// NOTE: Want this comment at start of line, don't emit with AddComment.
OutStreamer->emitRawComment(" %bb." + Twine(MBB.getNumber()) + ":",
false);
}
} else {
- if (isVerbose() && MBB.hasLabelMustBeEmitted())
+ 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());
+ }
OutStreamer->emitLabel(MBB.getSymbol());
}
}
@@ -3064,6 +3115,10 @@
/// 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.
+ if (MBB->isBeginSection())
+ return false;
+
// If this is a landing pad, it isn't a fall through. If it has no preds,
// then nothing falls through to it.
if (MBB->isEHPad() || MBB->pred_empty())
diff --git a/llvm/lib/CodeGen/BBSectionsPrepare.cpp b/llvm/lib/CodeGen/BBSectionsPrepare.cpp
new file mode 100644
index 0000000..3c1f122
--- /dev/null
+++ b/llvm/lib/CodeGen/BBSectionsPrepare.cpp
@@ -0,0 +1,315 @@
+//===-- BBSectionsPrepare.cpp ---=========---------------------------------===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+//
+// 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.
+//
+// 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:
+//
+// 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.
+//
+// 2. All inter-basic block 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.
+//
+// 4. 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.
+//
+// Basic Block Labels
+// ==================
+//
+// With -fbasicblock-sections=labels, or when a basic block is placed in a
+// unique section, it is labelled with a symbol. This allows easy mapping of
+// virtual addresses from PMU profiles back to the corresponding basic blocks.
+// Since the number of basic blocks is large, the labeling bloats the symbol
+// table sizes and the string table sizes significantly. While the binary size
+// does increase, it does not affect performance as the symbol table is not
+// loaded in memory during run-time. The string table size bloat is kept very
+// minimal using a unary naming scheme that uses string suffix compression. The
+// basic blocks for function foo are named "a.BB.foo", "aa.BB.foo", ... This
+// turns out to be very good for string table sizes and the bloat in the string
+// table size for a very large binary is ~8 %. The naming also allows using
+// the --symbol-ordering-file option in LLD to arbitrarily reorder the
+// sections.
+//
+//===----------------------------------------------------------------------===//
+
+#include "llvm/ADT/SmallSet.h"
+#include "llvm/ADT/StringMap.h"
+#include "llvm/ADT/StringRef.h"
+#include "llvm/CodeGen/MachineFunction.h"
+#include "llvm/CodeGen/MachineFunctionPass.h"
+#include "llvm/CodeGen/MachineModuleInfo.h"
+#include "llvm/CodeGen/Passes.h"
+#include "llvm/CodeGen/TargetInstrInfo.h"
+#include "llvm/InitializePasses.h"
+#include "llvm/Support/LineIterator.h"
+#include "llvm/Support/MemoryBuffer.h"
+#include "llvm/Target/TargetMachine.h"
+
+#include <string>
+
+using llvm::SmallSet;
+using llvm::StringMap;
+using llvm::StringRef;
+using namespace llvm;
+
+namespace {
+
+class BBSectionsPrepare : public MachineFunctionPass {
+public:
+ static char ID;
+ StringMap<SmallSet<unsigned, 4>> BBSectionsList;
+ const MemoryBuffer *MBuf = nullptr;
+
+ BBSectionsPrepare() : MachineFunctionPass(ID) {
+ initializeBBSectionsPreparePass(*PassRegistry::getPassRegistry());
+ }
+
+ BBSectionsPrepare(const MemoryBuffer *Buf)
+ : MachineFunctionPass(ID), MBuf(Buf) {
+ initializeBBSectionsPreparePass(*PassRegistry::getPassRegistry());
+ };
+
+ StringRef getPassName() const override {
+ return "Basic Block Sections Analysis";
+ }
+
+ void getAnalysisUsage(AnalysisUsage &AU) const override;
+
+ /// Read profiles of basic blocks if available here.
+ bool doInitialization(Module &M) override;
+
+ /// Identify basic blocks that need separate sections and prepare to emit them
+ /// accordingly.
+ bool runOnMachineFunction(MachineFunction &MF) override;
+};
+
+} // end anonymous namespace
+
+char BBSectionsPrepare::ID = 0;
+INITIALIZE_PASS(BBSectionsPrepare, "bbsections-prepare",
+ "Determine if a basic block needs a special section", 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();
+ SmallVector<MachineOperand, 4> Cond;
+ MachineBasicBlock *TBB = nullptr, *FBB = nullptr;
+
+ // If a branch to the fall through block already exists, return.
+ if (!TII->analyzeBranch(MBB, TBB, FBB, Cond) &&
+ (TBB == Fallthrough || FBB == Fallthrough)) {
+ return;
+ }
+
+ 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.
+static bool assignSectionsAndSortBasicBlocks(
+ MachineFunction &MF,
+ const StringMap<SmallSet<unsigned, 4>> &BBSectionsList) {
+ SmallSet<unsigned, 4> S = BBSectionsList.lookup(MF.getName());
+
+ bool HasHotEHPads = false;
+
+ 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);
+ }
+ }
+
+ // 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 (MBB.isEHPad())
+ MBB.setSectionType(MachineBasicBlockSection::MBBS_Exception);
+ });
+ }
+
+ 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);
+ }
+
+ MF.sort(([&](MachineBasicBlock &X, MachineBasicBlock &Y) {
+ unsigned TypeX = X.getSectionType();
+ unsigned TypeY = Y.getSectionType();
+
+ return (TypeX != TypeY) ? TypeX < TypeY : X.getNumber() < Y.getNumber();
+ }));
+
+ MF.setSectionRange();
+ return true;
+}
+
+bool BBSectionsPrepare::runOnMachineFunction(MachineFunction &MF) {
+ 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
+ // labels to match the profiles with the correct blocks.
+ MF.RenumberBlocks();
+
+ if (BBSectionsType == BasicBlockSection::Labels) {
+ MF.setBBSectionsType(BBSectionsType);
+ MF.createBBLabels();
+ return true;
+ }
+
+ if (BBSectionsType == BasicBlockSection::List &&
+ BBSectionsList.find(MF.getName()) == BBSectionsList.end())
+ return true;
+
+ MF.setBBSectionsType(BBSectionsType);
+ MF.createBBLabels();
+ assignSectionsAndSortBasicBlocks(MF, BBSectionsList);
+
+ 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:
+// ----------------------------
+// list.txt:
+// !main
+// !foo
+// !!2
+// !!4
+static bool getBBSectionsList(const MemoryBuffer *MBuf,
+ StringMap<SmallSet<unsigned, 4>> &bbMap) {
+ if (!MBuf)
+ return false;
+
+ line_iterator LineIt(*MBuf, /*SkipBlanks=*/true, /*CommentMarker=*/'#');
+
+ StringMap<SmallSet<unsigned, 4>>::iterator fi = bbMap.end();
+
+ for (; !LineIt.is_at_eof(); ++LineIt) {
+ StringRef s(*LineIt);
+ if (s[0] == '@')
+ continue;
+ // Check for the leading "!"
+ 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);
+ }
+ }
+ return true;
+}
+
+bool BBSectionsPrepare::doInitialization(Module &M) {
+ if (MBuf)
+ getBBSectionsList(MBuf, BBSectionsList);
+ return true;
+}
+
+void BBSectionsPrepare::getAnalysisUsage(AnalysisUsage &AU) const {
+ AU.setPreservesAll();
+ AU.addRequired<MachineModuleInfoWrapperPass>();
+}
+
+MachineFunctionPass *
+llvm::createBBSectionsPreparePass(const MemoryBuffer *Buf) {
+ return new BBSectionsPrepare(Buf);
+}
diff --git a/llvm/lib/CodeGen/CMakeLists.txt b/llvm/lib/CodeGen/CMakeLists.txt
index 0a299da..0d3ecc1 100644
--- a/llvm/lib/CodeGen/CMakeLists.txt
+++ b/llvm/lib/CodeGen/CMakeLists.txt
@@ -8,6 +8,7 @@
BranchRelaxation.cpp
BreakFalseDeps.cpp
BuiltinGCs.cpp
+ BBSectionsPrepare.cpp
CalcSpillWeights.cpp
CallingConvLower.cpp
CFGuardLongjmp.cpp
diff --git a/llvm/lib/CodeGen/CodeGen.cpp b/llvm/lib/CodeGen/CodeGen.cpp
index c74ba71..eefb328 100644
--- a/llvm/lib/CodeGen/CodeGen.cpp
+++ b/llvm/lib/CodeGen/CodeGen.cpp
@@ -20,6 +20,7 @@
/// initializeCodeGen - Initialize all passes linked into the CodeGen library.
void llvm::initializeCodeGen(PassRegistry &Registry) {
initializeAtomicExpandPass(Registry);
+ initializeBBSectionsPreparePass(Registry);
initializeBranchFolderPassPass(Registry);
initializeBranchRelaxationPass(Registry);
initializeCFGuardLongjmpPass(Registry);
diff --git a/llvm/lib/CodeGen/MIRParser/MILexer.cpp b/llvm/lib/CodeGen/MIRParser/MILexer.cpp
index 827f53a..36a027c9 100644
--- a/llvm/lib/CodeGen/MIRParser/MILexer.cpp
+++ b/llvm/lib/CodeGen/MIRParser/MILexer.cpp
@@ -268,6 +268,7 @@
.Case("pre-instr-symbol", MIToken::kw_pre_instr_symbol)
.Case("post-instr-symbol", MIToken::kw_post_instr_symbol)
.Case("heap-alloc-marker", MIToken::kw_heap_alloc_marker)
+ .Case("bbsections", MIToken::kw_bbsections)
.Case("unknown-size", MIToken::kw_unknown_size)
.Default(MIToken::Identifier);
}
diff --git a/llvm/lib/CodeGen/MIRParser/MILexer.h b/llvm/lib/CodeGen/MIRParser/MILexer.h
index aaffe4a..e76f6a7 100644
--- a/llvm/lib/CodeGen/MIRParser/MILexer.h
+++ b/llvm/lib/CodeGen/MIRParser/MILexer.h
@@ -122,6 +122,7 @@
kw_pre_instr_symbol,
kw_post_instr_symbol,
kw_heap_alloc_marker,
+ kw_bbsections,
kw_unknown_size,
// Named metadata keywords
diff --git a/llvm/lib/CodeGen/MIRParser/MIParser.cpp b/llvm/lib/CodeGen/MIRParser/MIParser.cpp
index c20c155..93af409 100644
--- a/llvm/lib/CodeGen/MIRParser/MIParser.cpp
+++ b/llvm/lib/CodeGen/MIRParser/MIParser.cpp
@@ -495,6 +495,7 @@
bool parseOffset(int64_t &Offset);
bool parseAlignment(unsigned &Alignment);
bool parseAddrspace(unsigned &Addrspace);
+ bool parseMBBS(MachineBasicBlockSection &T);
bool parseOperandsOffset(MachineOperand &Op);
bool parseIRValue(const Value *&V);
bool parseMemoryOperandFlag(MachineMemOperand::Flags &Flags);
@@ -619,6 +620,25 @@
return true;
}
+// Parse Machine Basic Block Section Type.
+bool MIParser::parseMBBS(MachineBasicBlockSection &T) {
+ 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");
+ lex();
+ return false;
+}
+
bool MIParser::parseBasicBlockDefinition(
DenseMap<unsigned, MachineBasicBlock *> &MBBSlots) {
assert(Token.is(MIToken::MachineBasicBlockLabel));
@@ -630,6 +650,7 @@
lex();
bool HasAddressTaken = false;
bool IsLandingPad = false;
+ MachineBasicBlockSection SectionType = MBBS_None;
unsigned Alignment = 0;
BasicBlock *BB = nullptr;
if (consumeIfPresent(MIToken::lparen)) {
@@ -654,6 +675,10 @@
return true;
lex();
break;
+ case MIToken::kw_bbsections:
+ if (parseMBBS(SectionType))
+ return true;
+ break;
default:
break;
}
@@ -683,6 +708,10 @@
if (HasAddressTaken)
MBB->setHasAddressTaken();
MBB->setIsEHPad(IsLandingPad);
+ if (SectionType != MBBS_None) {
+ MBB->setSectionType(SectionType);
+ MF.setBBSectionsType(BasicBlockSection::List);
+ }
return false;
}
diff --git a/llvm/lib/CodeGen/MIRParser/MIRParser.cpp b/llvm/lib/CodeGen/MIRParser/MIRParser.cpp
index f955bdc..199d077 100644
--- a/llvm/lib/CodeGen/MIRParser/MIRParser.cpp
+++ b/llvm/lib/CodeGen/MIRParser/MIRParser.cpp
@@ -438,6 +438,14 @@
diagFromBlockStringDiag(Error, YamlMF.Body.Value.SourceRange));
return true;
}
+ // Check Basic Block Section Flags.
+ if (MF.getTarget().getBBSectionsType() == BasicBlockSection::Labels) {
+ MF.createBBLabels();
+ MF.setBBSectionsType(BasicBlockSection::Labels);
+ } else if (MF.hasBBSections()) {
+ MF.setSectionRange();
+ 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
index ece4f96..1fb557e 100644
--- a/llvm/lib/CodeGen/MIRPrinter.cpp
+++ b/llvm/lib/CodeGen/MIRPrinter.cpp
@@ -635,6 +635,27 @@
OS << "align " << MBB.getAlignment().value();
HasAttributes = true;
}
+ if (MBB.getSectionType() != MBBS_None) {
+ OS << (HasAttributes ? ", " : " (");
+ OS << "bbsections ";
+ switch (MBB.getSectionType()) {
+ case MBBS_Entry:
+ OS << "Entry";
+ break;
+ case MBBS_Exception:
+ OS << "Exception";
+ break;
+ case MBBS_Cold:
+ OS << "Cold";
+ break;
+ case MBBS_Unique:
+ OS << "Unique";
+ break;
+ default:
+ llvm_unreachable("No such section type");
+ }
+ HasAttributes = true;
+ }
if (HasAttributes)
OS << ")";
OS << ":\n";
diff --git a/llvm/lib/CodeGen/MachineBasicBlock.cpp b/llvm/lib/CodeGen/MachineBasicBlock.cpp
index c2f459e..b273da8 100644
--- a/llvm/lib/CodeGen/MachineBasicBlock.cpp
+++ b/llvm/lib/CodeGen/MachineBasicBlock.cpp
@@ -61,12 +61,31 @@
const MachineFunction *MF = getParent();
MCContext &Ctx = MF->getContext();
auto Prefix = Ctx.getAsmInfo()->getPrivateLabelPrefix();
- assert(getNumber() >= 0 && "cannot get label for unreachable MBB");
- CachedMCSymbol = Ctx.getOrCreateSymbol(Twine(Prefix) + "BB" +
- Twine(MF->getFunctionNumber()) +
- "_" + Twine(getNumber()));
- }
+ bool BasicBlockSymbols = MF->hasBBSections() || MF->hasBBLabels();
+ auto Delimiter = BasicBlockSymbols ? "." : "_";
+ assert(getNumber() >= 0 && "cannot get label for unreachable MBB");
+
+ // With Basic Block Sections, we emit a symbol for every basic block. To
+ // keep the size of strtab small, we choose a unary encoding which can
+ // compress the symbol names significantly. The basic blocks for function
+ // foo are named a.BB.foo, aa.BB.foo, and so on.
+ if (BasicBlockSymbols) {
+ auto Iter = MF->getBBSectionsSymbolPrefix().begin();
+ if (getNumber() < 0 ||
+ getNumber() >= (int)MF->getBBSectionsSymbolPrefix().size())
+ report_fatal_error("Unreachable MBB: " + Twine(getNumber()));
+ std::string Prefix(Iter + 1, Iter + getNumber() + 1);
+ std::reverse(Prefix.begin(), Prefix.end());
+ CachedMCSymbol =
+ Ctx.getOrCreateSymbol(Prefix + Twine(Delimiter) + "BB" +
+ Twine(Delimiter) + Twine(MF->getName()));
+ } else {
+ CachedMCSymbol = Ctx.getOrCreateSymbol(
+ Twine(Prefix) + "BB" + Twine(MF->getFunctionNumber()) +
+ Twine(Delimiter) + Twine(getNumber()));
+ }
+ }
return CachedMCSymbol;
}
@@ -529,6 +548,48 @@
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.
diff --git a/llvm/lib/CodeGen/MachineFunction.cpp b/llvm/lib/CodeGen/MachineFunction.cpp
index b00907f..76a1bd9 100644
--- a/llvm/lib/CodeGen/MachineFunction.cpp
+++ b/llvm/lib/CodeGen/MachineFunction.cpp
@@ -33,6 +33,7 @@
#include "llvm/CodeGen/MachineRegisterInfo.h"
#include "llvm/CodeGen/PseudoSourceValue.h"
#include "llvm/CodeGen/TargetFrameLowering.h"
+#include "llvm/CodeGen/TargetInstrInfo.h"
#include "llvm/CodeGen/TargetLowering.h"
#include "llvm/CodeGen/TargetRegisterInfo.h"
#include "llvm/CodeGen/TargetSubtargetInfo.h"
@@ -71,6 +72,7 @@
#include <cstdint>
#include <iterator>
#include <string>
+#include <type_traits>
#include <utility>
#include <vector>
@@ -339,6 +341,59 @@
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.
+void MachineFunction::createBBLabels() {
+ const TargetInstrInfo *TII = getSubtarget().getInstrInfo();
+ this->BBSectionsSymbolPrefix.resize(getNumBlockIDs(), 'a');
+ for (auto MBBI = begin(), E = end(); MBBI != E; ++MBBI) {
+ assert(
+ (MBBI->getNumber() >= 0 && MBBI->getNumber() < (int)getNumBlockIDs()) &&
+ "BasicBlock number was out of range!");
+ // 'a' - Normal block.
+ // 'r' - Return block.
+ // 'l' - Landing Pad.
+ // 'L' - Return and landing pad.
+ bool isEHPad = MBBI->isEHPad();
+ bool isRetBlock = MBBI->isReturnBlock() && !TII->isTailCall(MBBI->back());
+ char type = 'a';
+ if (isEHPad && isRetBlock)
+ type = 'L';
+ else if (isEHPad)
+ type = 'l';
+ else if (isRetBlock)
+ type = 'r';
+ BBSectionsSymbolPrefix[MBBI->getNumber()] = type;
+ }
+}
+
/// 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 2ce285c..8f1c342 100644
--- a/llvm/lib/CodeGen/TargetLoweringObjectFileImpl.cpp
+++ b/llvm/lib/CodeGen/TargetLoweringObjectFileImpl.cpp
@@ -21,6 +21,8 @@
#include "llvm/BinaryFormat/Dwarf.h"
#include "llvm/BinaryFormat/ELF.h"
#include "llvm/BinaryFormat/MachO.h"
+#include "llvm/CodeGen/MachineBasicBlock.h"
+#include "llvm/CodeGen/MachineFunction.h"
#include "llvm/CodeGen/MachineModuleInfo.h"
#include "llvm/CodeGen/MachineModuleInfoImpls.h"
#include "llvm/IR/Comdat.h"
@@ -52,8 +54,8 @@
#include "llvm/ProfileData/InstrProf.h"
#include "llvm/Support/Casting.h"
#include "llvm/Support/CodeGen.h"
-#include "llvm/Support/Format.h"
#include "llvm/Support/ErrorHandling.h"
+#include "llvm/Support/Format.h"
#include "llvm/Support/raw_ostream.h"
#include "llvm/Target/TargetMachine.h"
#include <cassert>
@@ -762,6 +764,56 @@
return DataRelROSection;
}
+/// Returns a unique section for the given machine basic block.
+MCSection *TargetLoweringObjectFileELF::getSectionForMachineBasicBlock(
+ const Function &F, const MachineBasicBlock &MBB,
+ const TargetMachine &TM) const {
+ SmallString<128> Name;
+ Name = (static_cast<MCSectionELF *>(MBB.getParent()->getSection()))
+ ->getSectionName();
+ if (TM.getUniqueBBSectionNames()) {
+ Name += ".";
+ Name += MBB.getSymbol()->getName();
+ }
+ unsigned UniqueID = NextUniqueID++;
+ 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, UniqueID,
+ 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) {
diff --git a/llvm/lib/CodeGen/TargetPassConfig.cpp b/llvm/lib/CodeGen/TargetPassConfig.cpp
index 4485d5e..a351efc 100644
--- a/llvm/lib/CodeGen/TargetPassConfig.cpp
+++ b/llvm/lib/CodeGen/TargetPassConfig.cpp
@@ -983,6 +983,9 @@
addPass(createMachineOutlinerPass(RunOnAllFunctions));
}
+ if (TM->getBBSectionsType() != llvm::BasicBlockSection::None)
+ addPass(llvm::createBBSectionsPreparePass(TM->getBBSectionsFuncListBuf()));
+
// Add passes that directly emit MI after all other MI passes.
addPreEmitPass2();