Restoring authorship annotation for <[email protected]>. Commit 2 of 2.

1 files changed, 484 insertions, 484 deletions

diff --git a/contrib/libs/llvm12/lib/CodeGen/BasicBlockSections.cpp b/contrib/libs/llvm12/lib/CodeGen/BasicBlockSections.cpp
index ba1b0a91cae..7499ea8b42d 100644
--- a/contrib/libs/llvm12/lib/CodeGen/BasicBlockSections.cpp
+++ b/contrib/libs/llvm12/lib/CodeGen/BasicBlockSections.cpp
@@ -1,484 +1,484 @@
-//===-- BasicBlockSections.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 
-// 
-//===----------------------------------------------------------------------===// 
-// 
-// BasicBlockSections implementation. 
-// 
-// The purpose of this pass is to assign sections to basic blocks when 
-// -fbasic-block-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, -fbasic-block-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. 
-// 
-// There are a couple of challenges to be addressed: 
-// 
-// 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 
-//    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. 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 cluster. This also bloats the object file and binary sizes. 
-// 
-// Basic Block Labels 
-// ================== 
-// 
-// With -fbasic-block-sections=labels, we emit the offsets of BB addresses of 
-// every function into the .llvm_bb_addr_map section. Along with the function 
-// symbols, this allows for mapping of virtual addresses in PMU profiles back to 
-// the corresponding basic blocks. This logic is implemented in AsmPrinter. This 
-// pass only assigns the BBSectionType of every function to ``labels``. 
-// 
-//===----------------------------------------------------------------------===// 
- 
-#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/BasicBlockSectionUtils.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/Error.h" 
-#include "llvm/Support/LineIterator.h" 
-#include "llvm/Support/MemoryBuffer.h" 
-#include "llvm/Target/TargetMachine.h" 
- 
-using llvm::SmallSet; 
-using llvm::SmallVector; 
-using llvm::StringMap; 
-using llvm::StringRef; 
-using namespace llvm; 
- 
-// Placing the cold clusters in a separate section mitigates against poor 
-// profiles and allows optimizations such as hugepage mapping to be applied at a 
-// section granularity. Defaults to ".text.split." which is recognized by lld 
-// via the `-z keep-text-section-prefix` flag. 
-cl::opt<std::string> llvm::BBSectionsColdTextPrefix( 
-    "bbsections-cold-text-prefix", 
-    cl::desc("The text prefix to use for cold basic block clusters"), 
-    cl::init(".text.split."), cl::Hidden); 
- 
-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 BasicBlockSections : public MachineFunctionPass { 
-public: 
-  static char ID; 
- 
-  // This contains the basic-block-sections profile. 
-  const MemoryBuffer *MBuf = nullptr; 
- 
-  // 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; 
- 
-  BasicBlockSections(const MemoryBuffer *Buf) 
-      : MachineFunctionPass(ID), MBuf(Buf) { 
-    initializeBasicBlockSectionsPass(*PassRegistry::getPassRegistry()); 
-  }; 
- 
-  BasicBlockSections() : MachineFunctionPass(ID) { 
-    initializeBasicBlockSectionsPass(*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 BasicBlockSections::ID = 0; 
-INITIALIZE_PASS(BasicBlockSections, "bbsections-prepare", 
-                "Prepares for basic block sections, by splitting functions " 
-                "into clusters of basic blocks.", 
-                false, false) 
- 
-// 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; 
-  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()); 
- 
-    // 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(FTMBB); 
-  } 
-} 
- 
-// 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 void 
-assignSections(MachineFunction &MF, 
-               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) { 
-    // 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); 
-    } 
- 
-    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 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.setSectionID(EHPadsSectionID.getValue()); 
-} 
- 
-void llvm::sortBasicBlocksAndUpdateBranches( 
-    MachineFunction &MF, MachineBasicBlockComparator MBBCmp) { 
-  SmallVector<MachineBasicBlock *, 4> PreLayoutFallThroughs( 
-      MF.getNumBlockIDs()); 
-  for (auto &MBB : MF) 
-    PreLayoutFallThroughs[MBB.getNumber()] = MBB.getFallThrough(); 
- 
-  MF.sort(MBBCmp); 
- 
-  // 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); 
-} 
- 
-// If the exception section begins with a landing pad, that landing pad will 
-// assume a zero offset (relative to @LPStart) in the LSDA. However, a value of 
-// zero implies "no landing pad." This function inserts a NOP just before the EH 
-// pad label to ensure a nonzero offset. Returns true if padding is not needed. 
-static bool avoidZeroOffsetLandingPad(MachineFunction &MF) { 
-  for (auto &MBB : MF) { 
-    if (MBB.isBeginSection() && MBB.isEHPad()) { 
-      MachineBasicBlock::iterator MI = MBB.begin(); 
-      while (!MI->isEHLabel()) 
-        ++MI; 
-      MCInst Noop; 
-      MF.getSubtarget().getInstrInfo()->getNoop(Noop); 
-      BuildMI(MBB, MI, DebugLoc(), 
-              MF.getSubtarget().getInstrInfo()->get(Noop.getOpcode())); 
-      return false; 
-    } 
-  } 
-  return true; 
-} 
- 
-bool BasicBlockSections::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); 
-    return true; 
-  } 
- 
-  std::vector<Optional<BBClusterInfo>> FuncBBClusterInfo; 
-  if (BBSectionsType == BasicBlockSection::List && 
-      !getBBClusterInfoForFunction(MF, FuncAliasMap, ProgramBBClusterInfo, 
-                                   FuncBBClusterInfo)) 
-    return true; 
-  MF.setBBSectionsType(BBSectionsType); 
-  assignSections(MF, FuncBBClusterInfo); 
- 
-  // We make sure that the cluster including the entry basic block precedes all 
-  // other clusters. 
-  auto EntryBBSectionID = MF.front().getSectionID(); 
- 
-  // 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; 
-  }; 
- 
-  // 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. 
-  auto Comparator = [&](const MachineBasicBlock &X, 
-                        const 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(); 
-  }; 
- 
-  sortBasicBlocksAndUpdateBranches(MF, Comparator); 
-  avoidZeroOffsetLandingPad(MF); 
-  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. 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 
-// !!1 2 
-// !!4 
-static Error getBBClusterInfo(const MemoryBuffer *MBuf, 
-                              ProgramBBClusterInfoMapTy &ProgramBBClusterInfo, 
-                              StringMap<StringRef> &FuncAliasMap) { 
-  assert(MBuf); 
-  line_iterator LineIt(*MBuf, /*SkipBlanks=*/true, /*CommentMarker=*/'#'); 
- 
-  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] == '@') 
-      continue; 
-    // Check for the leading "!" 
-    if (!S.consume_front("!") || S.empty()) 
-      break; 
-    // 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 Error::success(); 
-} 
- 
-bool BasicBlockSections::doInitialization(Module &M) { 
-  if (!MBuf) 
-    return false; 
-  if (auto Err = getBBClusterInfo(MBuf, ProgramBBClusterInfo, FuncAliasMap)) 
-    report_fatal_error(std::move(Err)); 
-  return false; 
-} 
- 
-void BasicBlockSections::getAnalysisUsage(AnalysisUsage &AU) const { 
-  AU.setPreservesAll(); 
-  MachineFunctionPass::getAnalysisUsage(AU); 
-} 
- 
-MachineFunctionPass * 
-llvm::createBasicBlockSectionsPass(const MemoryBuffer *Buf) { 
-  return new BasicBlockSections(Buf); 
-} 
+//===-- BasicBlockSections.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
+//
+//===----------------------------------------------------------------------===//
+//
+// BasicBlockSections implementation.
+//
+// The purpose of this pass is to assign sections to basic blocks when
+// -fbasic-block-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, -fbasic-block-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.
+//
+// There are a couple of challenges to be addressed:
+//
+// 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
+//    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. 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 cluster. This also bloats the object file and binary sizes.
+//
+// Basic Block Labels
+// ==================
+//
+// With -fbasic-block-sections=labels, we emit the offsets of BB addresses of
+// every function into the .llvm_bb_addr_map section. Along with the function
+// symbols, this allows for mapping of virtual addresses in PMU profiles back to
+// the corresponding basic blocks. This logic is implemented in AsmPrinter. This
+// pass only assigns the BBSectionType of every function to ``labels``.
+//
+//===----------------------------------------------------------------------===//
+
+#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/BasicBlockSectionUtils.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/Error.h"
+#include "llvm/Support/LineIterator.h"
+#include "llvm/Support/MemoryBuffer.h"
+#include "llvm/Target/TargetMachine.h"
+
+using llvm::SmallSet;
+using llvm::SmallVector;
+using llvm::StringMap;
+using llvm::StringRef;
+using namespace llvm;
+
+// Placing the cold clusters in a separate section mitigates against poor
+// profiles and allows optimizations such as hugepage mapping to be applied at a
+// section granularity. Defaults to ".text.split." which is recognized by lld
+// via the `-z keep-text-section-prefix` flag.
+cl::opt<std::string> llvm::BBSectionsColdTextPrefix(
+    "bbsections-cold-text-prefix",
+    cl::desc("The text prefix to use for cold basic block clusters"),
+    cl::init(".text.split."), cl::Hidden);
+
+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 BasicBlockSections : public MachineFunctionPass {
+public:
+  static char ID;
+
+  // This contains the basic-block-sections profile.
+  const MemoryBuffer *MBuf = nullptr;
+
+  // 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;
+
+  BasicBlockSections(const MemoryBuffer *Buf)
+      : MachineFunctionPass(ID), MBuf(Buf) {
+    initializeBasicBlockSectionsPass(*PassRegistry::getPassRegistry());
+  };
+
+  BasicBlockSections() : MachineFunctionPass(ID) {
+    initializeBasicBlockSectionsPass(*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 BasicBlockSections::ID = 0;
+INITIALIZE_PASS(BasicBlockSections, "bbsections-prepare",
+                "Prepares for basic block sections, by splitting functions "
+                "into clusters of basic blocks.",
+                false, false)
+
+// 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;
+  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());
+
+    // 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(FTMBB);
+  }
+}
+
+// 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 void
+assignSections(MachineFunction &MF,
+               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) {
+    // 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);
+    }
+
+    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 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.setSectionID(EHPadsSectionID.getValue());
+}
+
+void llvm::sortBasicBlocksAndUpdateBranches(
+    MachineFunction &MF, MachineBasicBlockComparator MBBCmp) {
+  SmallVector<MachineBasicBlock *, 4> PreLayoutFallThroughs(
+      MF.getNumBlockIDs());
+  for (auto &MBB : MF)
+    PreLayoutFallThroughs[MBB.getNumber()] = MBB.getFallThrough();
+
+  MF.sort(MBBCmp);
+
+  // 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);
+}
+
+// If the exception section begins with a landing pad, that landing pad will
+// assume a zero offset (relative to @LPStart) in the LSDA. However, a value of
+// zero implies "no landing pad." This function inserts a NOP just before the EH
+// pad label to ensure a nonzero offset. Returns true if padding is not needed.
+static bool avoidZeroOffsetLandingPad(MachineFunction &MF) {
+  for (auto &MBB : MF) {
+    if (MBB.isBeginSection() && MBB.isEHPad()) {
+      MachineBasicBlock::iterator MI = MBB.begin();
+      while (!MI->isEHLabel())
+        ++MI;
+      MCInst Noop;
+      MF.getSubtarget().getInstrInfo()->getNoop(Noop);
+      BuildMI(MBB, MI, DebugLoc(),
+              MF.getSubtarget().getInstrInfo()->get(Noop.getOpcode()));
+      return false;
+    }
+  }
+  return true;
+}
+
+bool BasicBlockSections::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);
+    return true;
+  }
+
+  std::vector<Optional<BBClusterInfo>> FuncBBClusterInfo;
+  if (BBSectionsType == BasicBlockSection::List &&
+      !getBBClusterInfoForFunction(MF, FuncAliasMap, ProgramBBClusterInfo,
+                                   FuncBBClusterInfo))
+    return true;
+  MF.setBBSectionsType(BBSectionsType);
+  assignSections(MF, FuncBBClusterInfo);
+
+  // We make sure that the cluster including the entry basic block precedes all
+  // other clusters.
+  auto EntryBBSectionID = MF.front().getSectionID();
+
+  // 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;
+  };
+
+  // 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.
+  auto Comparator = [&](const MachineBasicBlock &X,
+                        const 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();
+  };
+
+  sortBasicBlocksAndUpdateBranches(MF, Comparator);
+  avoidZeroOffsetLandingPad(MF);
+  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. 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
+// !!1 2
+// !!4
+static Error getBBClusterInfo(const MemoryBuffer *MBuf,
+                              ProgramBBClusterInfoMapTy &ProgramBBClusterInfo,
+                              StringMap<StringRef> &FuncAliasMap) {
+  assert(MBuf);
+  line_iterator LineIt(*MBuf, /*SkipBlanks=*/true, /*CommentMarker=*/'#');
+
+  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] == '@')
+      continue;
+    // Check for the leading "!"
+    if (!S.consume_front("!") || S.empty())
+      break;
+    // 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 Error::success();
+}
+
+bool BasicBlockSections::doInitialization(Module &M) {
+  if (!MBuf)
+    return false;
+  if (auto Err = getBBClusterInfo(MBuf, ProgramBBClusterInfo, FuncAliasMap))
+    report_fatal_error(std::move(Err));
+  return false;
+}
+
+void BasicBlockSections::getAnalysisUsage(AnalysisUsage &AU) const {
+  AU.setPreservesAll();
+  MachineFunctionPass::getAnalysisUsage(AU);
+}
+
+MachineFunctionPass *
+llvm::createBasicBlockSectionsPass(const MemoryBuffer *Buf) {
+  return new BasicBlockSections(Buf);
+}