1//===-- BasicBlockPathCloning.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/// \file
10/// BasicBlockPathCloning implementation.
11///
12/// The purpose of this pass is to clone basic block paths based on information
13/// provided by the -fbasic-block-sections=list option.
14/// Please refer to BasicBlockSectionsProfileReader.cpp to see a path cloning
15/// example.
16//===----------------------------------------------------------------------===//
17// This pass clones the machine basic blocks alongs the given paths and sets up
18// the CFG. It assigns BBIDs to the cloned blocks so that the
19// `BasicBlockSections` pass can correctly map the cluster information to the
20// blocks. The cloned block's BBID will have the same BaseID as the original
21// block, but will get a unique non-zero CloneID (original blocks all have zero
22// CloneIDs). This pass applies a path cloning if it satisfies the following
23// conditions:
24// 1. All BBIDs in the path should be mapped to existing blocks.
25// 2. Each two consecutive BBIDs in the path must have a successor
26// relationship in the CFG.
27// 3. The path should not include a block with indirect branches, except for
28// the last block.
29// If a path does not satisfy all three conditions, it will be rejected, but the
30// CloneIDs for its (supposed to be cloned) blocks will be bypassed to make sure
31// that the `BasicBlockSections` pass can map cluster info correctly to the
32// actually-cloned blocks.
33//===----------------------------------------------------------------------===//
34
35#include "llvm/ADT/SmallVector.h"
36#include "llvm/ADT/StringRef.h"
37#include "llvm/CodeGen/BasicBlockSectionUtils.h"
38#include "llvm/CodeGen/BasicBlockSectionsProfileReader.h"
39#include "llvm/CodeGen/MachineBlockHashInfo.h"
40#include "llvm/CodeGen/MachineFunction.h"
41#include "llvm/CodeGen/MachineFunctionPass.h"
42#include "llvm/CodeGen/Passes.h"
43#include "llvm/CodeGen/TargetInstrInfo.h"
44#include "llvm/InitializePasses.h"
45#include "llvm/Support/UniqueBBID.h"
46#include "llvm/Support/WithColor.h"
47#include "llvm/Target/TargetMachine.h"
48
49using namespace llvm;
50
51namespace {
52
53// Clones the given block and assigns the given `CloneID` to its BBID. Copies
54// the instructions into the new block and sets up its successors.
55MachineBasicBlock *CloneMachineBasicBlock(MachineBasicBlock &OrigBB,
56 unsigned CloneID) {
57 auto &MF = *OrigBB.getParent();
58 auto TII = MF.getSubtarget().getInstrInfo();
59 // Create the clone block and set its BBID based on the original block.
60 MachineBasicBlock *CloneBB = MF.CreateMachineBasicBlock(
61 BB: OrigBB.getBasicBlock(), BBID: UniqueBBID{.BaseID: OrigBB.getBBID()->BaseID, .CloneID: CloneID});
62 MF.push_back(MBB: CloneBB);
63
64 // Copy the instructions.
65 for (auto &I : OrigBB.instrs()) {
66 // Bundled instructions are duplicated together.
67 if (I.isBundledWithPred())
68 continue;
69 TII->duplicate(MBB&: *CloneBB, InsertBefore: CloneBB->end(), Orig: I);
70 }
71
72 // Add the successors of the original block as the new block's successors.
73 // We set the predecessor after returning from this call.
74 for (auto SI = OrigBB.succ_begin(), SE = OrigBB.succ_end(); SI != SE; ++SI)
75 CloneBB->copySuccessor(Orig: &OrigBB, I: SI);
76
77 if (auto FT = OrigBB.getFallThrough(/*JumpToFallThrough=*/false)) {
78 // The original block has an implicit fall through.
79 // Insert an explicit unconditional jump from the cloned block to the
80 // fallthrough block. Technically, this is only needed for the last block
81 // of the path, but we do it for all clones for consistency.
82 TII->insertUnconditionalBranch(MBB&: *CloneBB, DestBB: FT, DL: CloneBB->findBranchDebugLoc());
83 }
84 return CloneBB;
85}
86
87// Returns if we can legally apply the cloning represented by `ClonePath`.
88// `BBIDToBlock` contains the original basic blocks in function `MF` keyed by
89// their `BBID::BaseID`.
90bool IsValidCloning(const MachineFunction &MF,
91 const DenseMap<unsigned, MachineBasicBlock *> &BBIDToBlock,
92 const SmallVector<unsigned> &ClonePath) {
93 const MachineBasicBlock *PrevBB = nullptr;
94 for (size_t I = 0; I < ClonePath.size(); ++I) {
95 unsigned BBID = ClonePath[I];
96 const MachineBasicBlock *PathBB = BBIDToBlock.lookup(Val: BBID);
97 if (!PathBB) {
98 WithColor::warning() << "no block with id " << BBID << " in function "
99 << MF.getName() << "\n";
100 return false;
101 }
102
103 if (PrevBB) {
104 if (!PrevBB->isSuccessor(MBB: PathBB)) {
105 WithColor::warning()
106 << "block #" << BBID << " is not a successor of block #"
107 << PrevBB->getBBID()->BaseID << " in function " << MF.getName()
108 << "\n";
109 return false;
110 }
111
112 for (auto &MI : *PathBB) {
113 // Avoid cloning when the block contains non-duplicable instructions.
114 // CFI instructions are marked as non-duplicable only because of Darwin,
115 // so we exclude them from this check.
116 if (MI.isNotDuplicable() && !MI.isCFIInstruction()) {
117 WithColor::warning()
118 << "block #" << BBID
119 << " has non-duplicable instructions in function " << MF.getName()
120 << "\n";
121 return false;
122 }
123 }
124 if (PathBB->isMachineBlockAddressTaken()) {
125 // Avoid cloning blocks which have their address taken since we can't
126 // rewire branches to those blocks as easily.
127 WithColor::warning()
128 << "block #" << BBID
129 << " has its machine block address taken in function "
130 << MF.getName() << "\n";
131 return false;
132 }
133 if (PathBB->isInlineAsmBrIndirectTarget()) {
134 // Similarly for branches to the block within an asm goto.
135 WithColor::warning()
136 << "block #" << BBID
137 << " is a branch target of an 'asm goto' in function "
138 << MF.getName() << "\n";
139 return false;
140 }
141 }
142
143 if (I != ClonePath.size() - 1 && !PathBB->empty() &&
144 PathBB->back().isIndirectBranch()) {
145 WithColor::warning()
146 << "block #" << BBID
147 << " has indirect branch and appears as the non-tail block of a "
148 "path in function "
149 << MF.getName() << "\n";
150 return false;
151 }
152 PrevBB = PathBB;
153 }
154 return true;
155}
156
157// Applies all clonings specified in `ClonePaths` to `MF`. Returns true
158// if any clonings have been applied.
159bool ApplyCloning(MachineFunction &MF,
160 const SmallVector<SmallVector<unsigned>> &ClonePaths) {
161 if (ClonePaths.empty())
162 return false;
163 bool AnyPathsCloned = false;
164 // Map from the final BB IDs to the `MachineBasicBlock`s.
165 DenseMap<unsigned, MachineBasicBlock *> BBIDToBlock;
166 for (auto &BB : MF)
167 BBIDToBlock.try_emplace(Key: BB.getBBID()->BaseID, Args: &BB);
168
169 DenseMap<unsigned, unsigned> NClonesForBBID;
170 auto TII = MF.getSubtarget().getInstrInfo();
171 for (const auto &ClonePath : ClonePaths) {
172 if (!IsValidCloning(MF, BBIDToBlock, ClonePath)) {
173 // We still need to increment the number of clones so we can map
174 // to the cluster info correctly.
175 for (unsigned BBID : ClonePath)
176 ++NClonesForBBID[BBID];
177 continue;
178 }
179 MachineBasicBlock *PrevBB = nullptr;
180 for (unsigned BBID : ClonePath) {
181 MachineBasicBlock *OrigBB = BBIDToBlock.at(Val: BBID);
182 if (PrevBB == nullptr) {
183 // The first block in the path is not cloned. We only need to make it
184 // branch to the next cloned block in the path. Here, we make its
185 // fallthrough explicit so we can change it later.
186 if (auto FT = OrigBB->getFallThrough(/*JumpToFallThrough=*/false)) {
187 TII->insertUnconditionalBranch(MBB&: *OrigBB, DestBB: FT,
188 DL: OrigBB->findBranchDebugLoc());
189 }
190 PrevBB = OrigBB;
191 continue;
192 }
193 MachineBasicBlock *CloneBB =
194 CloneMachineBasicBlock(OrigBB&: *OrigBB, CloneID: ++NClonesForBBID[BBID]);
195
196 // Set up the previous block in the path to jump to the clone. This also
197 // transfers the successor/predecessor relationship of PrevBB and OrigBB
198 // to that of PrevBB and CloneBB.
199 PrevBB->ReplaceUsesOfBlockWith(Old: OrigBB, New: CloneBB);
200
201 // Copy the livein set.
202 for (auto &LiveIn : OrigBB->liveins())
203 CloneBB->addLiveIn(RegMaskPair: LiveIn);
204
205 PrevBB = CloneBB;
206 }
207 AnyPathsCloned = true;
208 }
209 return AnyPathsCloned;
210}
211
212class BasicBlockPathCloning : public MachineFunctionPass {
213public:
214 static char ID;
215
216 BasicBlockSectionsProfileReaderWrapperPass *BBSectionsProfileReader = nullptr;
217
218 BasicBlockPathCloning() : MachineFunctionPass(ID) {}
219
220 StringRef getPassName() const override { return "Basic Block Path Cloning"; }
221
222 void getAnalysisUsage(AnalysisUsage &AU) const override;
223
224 /// Identify basic blocks that need separate sections and prepare to emit them
225 /// accordingly.
226 bool runOnMachineFunction(MachineFunction &MF) override;
227};
228
229} // namespace
230
231char BasicBlockPathCloning::ID = 0;
232INITIALIZE_PASS_BEGIN(
233 BasicBlockPathCloning, "bb-path-cloning",
234 "Applies path clonings for the -basic-block-sections=list option", false,
235 false)
236INITIALIZE_PASS_DEPENDENCY(BasicBlockSectionsProfileReaderWrapperPass)
237INITIALIZE_PASS_END(
238 BasicBlockPathCloning, "bb-path-cloning",
239 "Applies path clonings for the -basic-block-sections=list option", false,
240 false)
241
242bool BasicBlockPathCloning::runOnMachineFunction(MachineFunction &MF) {
243 assert(MF.getTarget().getBBSectionsType() == BasicBlockSection::List &&
244 "BB Sections list not enabled!");
245 if (hasInstrProfHashMismatch(MF))
246 return false;
247
248 return ApplyCloning(MF,
249 ClonePaths: getAnalysis<BasicBlockSectionsProfileReaderWrapperPass>()
250 .getClonePathsForFunction(FuncName: MF.getName()));
251}
252
253void BasicBlockPathCloning::getAnalysisUsage(AnalysisUsage &AU) const {
254 AU.addRequired<BasicBlockSectionsProfileReaderWrapperPass>();
255 AU.addPreserved<MachineBlockHashInfo>();
256 MachineFunctionPass::getAnalysisUsage(AU);
257}
258
259MachineFunctionPass *llvm::createBasicBlockPathCloningPass() {
260 return new BasicBlockPathCloning();
261}
262