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