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