1 //===-- BasicBlockSections.cpp ---=========--------------------------------===//
2 //
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6 //
7 //===----------------------------------------------------------------------===//
8 //
9 // BasicBlockSections implementation.
10 //
11 // The purpose of this pass is to assign sections to basic blocks when
12 // -fbasic-block-sections= option is used. Further, with profile information
13 // only the subset of basic blocks with profiles are placed in separate sections
14 // and the rest are grouped in a cold section. The exception handling blocks are
15 // treated specially to ensure they are all in one seciton.
16 //
17 // Basic Block Sections
18 // ====================
19 //
20 // With option, -fbasic-block-sections=list, every function may be split into
21 // clusters of basic blocks. Every cluster will be emitted into a separate
22 // section with its basic blocks sequenced in the given order. To get the
23 // optimized performance, the clusters must form an optimal BB layout for the
24 // function. We insert a symbol at the beginning of every cluster's section to
25 // allow the linker to reorder the sections in any arbitrary sequence. A global
26 // order of these sections would encapsulate the function layout.
27 // For example, consider the following clusters for a function foo (consisting
28 // of 6 basic blocks 0, 1, ..., 5).
29 //
30 // 0 2
31 // 1 3 5
32 //
33 // * Basic blocks 0 and 2 are placed in one section with symbol `foo`
34 //   referencing the beginning of this section.
35 // * Basic blocks 1, 3, 5 are placed in a separate section. A new symbol
36 //   `foo.__part.1` will reference the beginning of this section.
37 // * Basic block 4 (note that it is not referenced in the list) is placed in
38 //   one section, and a new symbol `foo.cold` will point to it.
39 //
40 // There are a couple of challenges to be addressed:
41 //
42 // 1. The last basic block of every cluster should not have any implicit
43 //    fallthrough to its next basic block, as it can be reordered by the linker.
44 //    The compiler should make these fallthroughs explicit by adding
45 //    unconditional jumps..
46 //
47 // 2. All inter-cluster branch targets would now need to be resolved by the
48 //    linker as they cannot be calculated during compile time. This is done
49 //    using static relocations. Further, the compiler tries to use short branch
50 //    instructions on some ISAs for small branch offsets. This is not possible
51 //    for inter-cluster branches as the offset is not determined at compile
52 //    time, and therefore, long branch instructions have to be used for those.
53 //
54 // 3. Debug Information (DebugInfo) and Call Frame Information (CFI) emission
55 //    needs special handling with basic block sections. DebugInfo needs to be
56 //    emitted with more relocations as basic block sections can break a
57 //    function into potentially several disjoint pieces, and CFI needs to be
58 //    emitted per cluster. This also bloats the object file and binary sizes.
59 //
60 // Basic Block Labels
61 // ==================
62 //
63 // With -fbasic-block-sections=labels, we encode the offsets of BB addresses of
64 // every function into the .llvm_bb_addr_map section. Along with the function
65 // symbols, this allows for mapping of virtual addresses in PMU profiles back to
66 // the corresponding basic blocks. This logic is implemented in AsmPrinter. This
67 // pass only assigns the BBSectionType of every function to ``labels``.
68 //
69 //===----------------------------------------------------------------------===//
70 
71 #include "llvm/ADT/Optional.h"
72 #include "llvm/ADT/SmallVector.h"
73 #include "llvm/ADT/StringRef.h"
74 #include "llvm/CodeGen/BasicBlockSectionsProfileReader.h"
75 #include "llvm/CodeGen/BasicBlockSectionUtils.h"
76 #include "llvm/CodeGen/MachineFunction.h"
77 #include "llvm/CodeGen/MachineFunctionPass.h"
78 #include "llvm/CodeGen/Passes.h"
79 #include "llvm/CodeGen/TargetInstrInfo.h"
80 #include "llvm/InitializePasses.h"
81 #include "llvm/Target/TargetMachine.h"
82 
83 using namespace llvm;
84 
85 // Placing the cold clusters in a separate section mitigates against poor
86 // profiles and allows optimizations such as hugepage mapping to be applied at a
87 // section granularity. Defaults to ".text.split." which is recognized by lld
88 // via the `-z keep-text-section-prefix` flag.
89 cl::opt<std::string> llvm::BBSectionsColdTextPrefix(
90     "bbsections-cold-text-prefix",
91     cl::desc("The text prefix to use for cold basic block clusters"),
92     cl::init(".text.split."), cl::Hidden);
93 
94 cl::opt<bool> BBSectionsDetectSourceDrift(
95     "bbsections-detect-source-drift",
96     cl::desc("This checks if there is a fdo instr. profile hash "
97              "mismatch for this function"),
98     cl::init(true), cl::Hidden);
99 
100 namespace {
101 
102 class BasicBlockSections : public MachineFunctionPass {
103 public:
104   static char ID;
105 
106   BasicBlockSectionsProfileReader *BBSectionsProfileReader = nullptr;
107 
108   BasicBlockSections() : MachineFunctionPass(ID) {
109     initializeBasicBlockSectionsPass(*PassRegistry::getPassRegistry());
110   }
111 
112   StringRef getPassName() const override {
113     return "Basic Block Sections Analysis";
114   }
115 
116   void getAnalysisUsage(AnalysisUsage &AU) const override;
117 
118   /// Identify basic blocks that need separate sections and prepare to emit them
119   /// accordingly.
120   bool runOnMachineFunction(MachineFunction &MF) override;
121 };
122 
123 } // end anonymous namespace
124 
125 char BasicBlockSections::ID = 0;
126 INITIALIZE_PASS(BasicBlockSections, "bbsections-prepare",
127                 "Prepares for basic block sections, by splitting functions "
128                 "into clusters of basic blocks.",
129                 false, false)
130 
131 // This function updates and optimizes the branching instructions of every basic
132 // block in a given function to account for changes in the layout.
133 static void updateBranches(
134     MachineFunction &MF,
135     const SmallVector<MachineBasicBlock *, 4> &PreLayoutFallThroughs) {
136   const TargetInstrInfo *TII = MF.getSubtarget().getInstrInfo();
137   SmallVector<MachineOperand, 4> Cond;
138   for (auto &MBB : MF) {
139     auto NextMBBI = std::next(MBB.getIterator());
140     auto *FTMBB = PreLayoutFallThroughs[MBB.getNumber()];
141     // If this block had a fallthrough before we need an explicit unconditional
142     // branch to that block if either
143     //     1- the block ends a section, which means its next block may be
144     //        reorderd by the linker, or
145     //     2- the fallthrough block is not adjacent to the block in the new
146     //        order.
147     if (FTMBB && (MBB.isEndSection() || &*NextMBBI != FTMBB))
148       TII->insertUnconditionalBranch(MBB, FTMBB, MBB.findBranchDebugLoc());
149 
150     // We do not optimize branches for machine basic blocks ending sections, as
151     // their adjacent block might be reordered by the linker.
152     if (MBB.isEndSection())
153       continue;
154 
155     // It might be possible to optimize branches by flipping the branch
156     // condition.
157     Cond.clear();
158     MachineBasicBlock *TBB = nullptr, *FBB = nullptr; // For analyzeBranch.
159     if (TII->analyzeBranch(MBB, TBB, FBB, Cond))
160       continue;
161     MBB.updateTerminator(FTMBB);
162   }
163 }
164 
165 // This function provides the BBCluster information associated with a function.
166 // Returns true if a valid association exists and false otherwise.
167 bool getBBClusterInfoForFunction(
168     const MachineFunction &MF,
169     BasicBlockSectionsProfileReader *BBSectionsProfileReader,
170     std::vector<Optional<BBClusterInfo>> &V) {
171 
172   // Find the assoicated cluster information.
173   std::pair<bool, SmallVector<BBClusterInfo, 4>> P =
174       BBSectionsProfileReader->getBBClusterInfoForFunction(MF.getName());
175   if (!P.first)
176     return false;
177 
178   if (P.second.empty()) {
179     // This indicates that sections are desired for all basic blocks of this
180     // function. We clear the BBClusterInfo vector to denote this.
181     V.clear();
182     return true;
183   }
184 
185   V.resize(MF.getNumBlockIDs());
186   for (auto bbClusterInfo : P.second) {
187     // Bail out if the cluster information contains invalid MBB numbers.
188     if (bbClusterInfo.MBBNumber >= MF.getNumBlockIDs())
189       return false;
190     V[bbClusterInfo.MBBNumber] = bbClusterInfo;
191   }
192   return true;
193 }
194 
195 // This function sorts basic blocks according to the cluster's information.
196 // All explicitly specified clusters of basic blocks will be ordered
197 // accordingly. All non-specified BBs go into a separate "Cold" section.
198 // Additionally, if exception handling landing pads end up in more than one
199 // clusters, they are moved into a single "Exception" section. Eventually,
200 // clusters are ordered in increasing order of their IDs, with the "Exception"
201 // and "Cold" succeeding all other clusters.
202 // FuncBBClusterInfo represent the cluster information for basic blocks. If this
203 // is empty, it means unique sections for all basic blocks in the function.
204 static void
205 assignSections(MachineFunction &MF,
206                const std::vector<Optional<BBClusterInfo>> &FuncBBClusterInfo) {
207   assert(MF.hasBBSections() && "BB Sections is not set for function.");
208   // This variable stores the section ID of the cluster containing eh_pads (if
209   // all eh_pads are one cluster). If more than one cluster contain eh_pads, we
210   // set it equal to ExceptionSectionID.
211   Optional<MBBSectionID> EHPadsSectionID;
212 
213   for (auto &MBB : MF) {
214     // With the 'all' option, every basic block is placed in a unique section.
215     // With the 'list' option, every basic block is placed in a section
216     // associated with its cluster, unless we want individual unique sections
217     // for every basic block in this function (if FuncBBClusterInfo is empty).
218     if (MF.getTarget().getBBSectionsType() == llvm::BasicBlockSection::All ||
219         FuncBBClusterInfo.empty()) {
220       // If unique sections are desired for all basic blocks of the function, we
221       // set every basic block's section ID equal to its number (basic block
222       // id). This further ensures that basic blocks are ordered canonically.
223       MBB.setSectionID({static_cast<unsigned int>(MBB.getNumber())});
224     } else if (FuncBBClusterInfo[MBB.getNumber()])
225       MBB.setSectionID(FuncBBClusterInfo[MBB.getNumber()]->ClusterID);
226     else {
227       // BB goes into the special cold section if it is not specified in the
228       // cluster info map.
229       MBB.setSectionID(MBBSectionID::ColdSectionID);
230     }
231 
232     if (MBB.isEHPad() && EHPadsSectionID != MBB.getSectionID() &&
233         EHPadsSectionID != MBBSectionID::ExceptionSectionID) {
234       // If we already have one cluster containing eh_pads, this must be updated
235       // to ExceptionSectionID. Otherwise, we set it equal to the current
236       // section ID.
237       EHPadsSectionID = EHPadsSectionID ? MBBSectionID::ExceptionSectionID
238                                         : MBB.getSectionID();
239     }
240   }
241 
242   // If EHPads are in more than one section, this places all of them in the
243   // special exception section.
244   if (EHPadsSectionID == MBBSectionID::ExceptionSectionID)
245     for (auto &MBB : MF)
246       if (MBB.isEHPad())
247         MBB.setSectionID(*EHPadsSectionID);
248 }
249 
250 void llvm::sortBasicBlocksAndUpdateBranches(
251     MachineFunction &MF, MachineBasicBlockComparator MBBCmp) {
252   SmallVector<MachineBasicBlock *, 4> PreLayoutFallThroughs(
253       MF.getNumBlockIDs());
254   for (auto &MBB : MF)
255     PreLayoutFallThroughs[MBB.getNumber()] = MBB.getFallThrough();
256 
257   MF.sort(MBBCmp);
258 
259   // Set IsBeginSection and IsEndSection according to the assigned section IDs.
260   MF.assignBeginEndSections();
261 
262   // After reordering basic blocks, we must update basic block branches to
263   // insert explicit fallthrough branches when required and optimize branches
264   // when possible.
265   updateBranches(MF, PreLayoutFallThroughs);
266 }
267 
268 // If the exception section begins with a landing pad, that landing pad will
269 // assume a zero offset (relative to @LPStart) in the LSDA. However, a value of
270 // zero implies "no landing pad." This function inserts a NOP just before the EH
271 // pad label to ensure a nonzero offset.
272 void llvm::avoidZeroOffsetLandingPad(MachineFunction &MF) {
273   for (auto &MBB : MF) {
274     if (MBB.isBeginSection() && MBB.isEHPad()) {
275       MachineBasicBlock::iterator MI = MBB.begin();
276       while (!MI->isEHLabel())
277         ++MI;
278       MCInst Nop = MF.getSubtarget().getInstrInfo()->getNop();
279       BuildMI(MBB, MI, DebugLoc(),
280               MF.getSubtarget().getInstrInfo()->get(Nop.getOpcode()));
281     }
282   }
283 }
284 
285 // This checks if the source of this function has drifted since this binary was
286 // profiled previously.  For now, we are piggy backing on what PGO does to
287 // detect this with instrumented profiles.  PGO emits an hash of the IR and
288 // checks if the hash has changed.  Advanced basic block layout is usually done
289 // on top of PGO optimized binaries and hence this check works well in practice.
290 static bool hasInstrProfHashMismatch(MachineFunction &MF) {
291   if (!BBSectionsDetectSourceDrift)
292     return false;
293 
294   const char MetadataName[] = "instr_prof_hash_mismatch";
295   auto *Existing = MF.getFunction().getMetadata(LLVMContext::MD_annotation);
296   if (Existing) {
297     MDTuple *Tuple = cast<MDTuple>(Existing);
298     for (const auto &N : Tuple->operands())
299       if (cast<MDString>(N.get())->getString() == MetadataName)
300         return true;
301   }
302 
303   return false;
304 }
305 
306 bool BasicBlockSections::runOnMachineFunction(MachineFunction &MF) {
307   auto BBSectionsType = MF.getTarget().getBBSectionsType();
308   assert(BBSectionsType != BasicBlockSection::None &&
309          "BB Sections not enabled!");
310 
311   // Check for source drift.  If the source has changed since the profiles
312   // were obtained, optimizing basic blocks might be sub-optimal.
313   // This only applies to BasicBlockSection::List as it creates
314   // clusters of basic blocks using basic block ids. Source drift can
315   // invalidate these groupings leading to sub-optimal code generation with
316   // regards to performance.
317   if (BBSectionsType == BasicBlockSection::List &&
318       hasInstrProfHashMismatch(MF))
319     return true;
320 
321   // Renumber blocks before sorting them for basic block sections.  This is
322   // useful during sorting, basic blocks in the same section will retain the
323   // default order.  This renumbering should also be done for basic block
324   // labels to match the profiles with the correct blocks.
325   MF.RenumberBlocks();
326 
327   if (BBSectionsType == BasicBlockSection::Labels) {
328     MF.setBBSectionsType(BBSectionsType);
329     return true;
330   }
331 
332   BBSectionsProfileReader = &getAnalysis<BasicBlockSectionsProfileReader>();
333 
334   std::vector<Optional<BBClusterInfo>> FuncBBClusterInfo;
335   if (BBSectionsType == BasicBlockSection::List &&
336       !getBBClusterInfoForFunction(MF, BBSectionsProfileReader,
337                                    FuncBBClusterInfo))
338     return true;
339   MF.setBBSectionsType(BBSectionsType);
340   assignSections(MF, FuncBBClusterInfo);
341 
342   // We make sure that the cluster including the entry basic block precedes all
343   // other clusters.
344   auto EntryBBSectionID = MF.front().getSectionID();
345 
346   // Helper function for ordering BB sections as follows:
347   //   * Entry section (section including the entry block).
348   //   * Regular sections (in increasing order of their Number).
349   //     ...
350   //   * Exception section
351   //   * Cold section
352   auto MBBSectionOrder = [EntryBBSectionID](const MBBSectionID &LHS,
353                                             const MBBSectionID &RHS) {
354     // We make sure that the section containing the entry block precedes all the
355     // other sections.
356     if (LHS == EntryBBSectionID || RHS == EntryBBSectionID)
357       return LHS == EntryBBSectionID;
358     return LHS.Type == RHS.Type ? LHS.Number < RHS.Number : LHS.Type < RHS.Type;
359   };
360 
361   // We sort all basic blocks to make sure the basic blocks of every cluster are
362   // contiguous and ordered accordingly. Furthermore, clusters are ordered in
363   // increasing order of their section IDs, with the exception and the
364   // cold section placed at the end of the function.
365   auto Comparator = [&](const MachineBasicBlock &X,
366                         const MachineBasicBlock &Y) {
367     auto XSectionID = X.getSectionID();
368     auto YSectionID = Y.getSectionID();
369     if (XSectionID != YSectionID)
370       return MBBSectionOrder(XSectionID, YSectionID);
371     // If the two basic block are in the same section, the order is decided by
372     // their position within the section.
373     if (XSectionID.Type == MBBSectionID::SectionType::Default)
374       return FuncBBClusterInfo[X.getNumber()]->PositionInCluster <
375              FuncBBClusterInfo[Y.getNumber()]->PositionInCluster;
376     return X.getNumber() < Y.getNumber();
377   };
378 
379   sortBasicBlocksAndUpdateBranches(MF, Comparator);
380   avoidZeroOffsetLandingPad(MF);
381   return true;
382 }
383 
384 void BasicBlockSections::getAnalysisUsage(AnalysisUsage &AU) const {
385   AU.setPreservesAll();
386   AU.addRequired<BasicBlockSectionsProfileReader>();
387   MachineFunctionPass::getAnalysisUsage(AU);
388 }
389 
390 MachineFunctionPass *llvm::createBasicBlockSectionsPass() {
391   return new BasicBlockSections();
392 }
393