1 | //===-- MSP430BranchSelector.cpp - Emit long conditional branches ---------===// |
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 | // This file contains a pass that scans a machine function to determine which |
10 | // conditional branches need more than 10 bits of displacement to reach their |
11 | // target basic block. It does this in two passes; a calculation of basic block |
12 | // positions pass, and a branch pseudo op to machine branch opcode pass. This |
13 | // pass should be run last, just before the assembly printer. |
14 | // |
15 | //===----------------------------------------------------------------------===// |
16 | |
17 | #include "MSP430.h" |
18 | #include "MSP430InstrInfo.h" |
19 | #include "MSP430Subtarget.h" |
20 | #include "llvm/ADT/Statistic.h" |
21 | #include "llvm/CodeGen/MachineFunctionPass.h" |
22 | #include "llvm/CodeGen/MachineInstrBuilder.h" |
23 | #include "llvm/Support/Debug.h" |
24 | #include "llvm/Support/MathExtras.h" |
25 | #include "llvm/Target/TargetMachine.h" |
26 | using namespace llvm; |
27 | |
28 | #define DEBUG_TYPE "msp430-branch-select" |
29 | |
30 | static cl::opt<bool> |
31 | BranchSelectEnabled("msp430-branch-select" , cl::Hidden, cl::init(Val: true), |
32 | cl::desc("Expand out of range branches" )); |
33 | |
34 | STATISTIC(NumSplit, "Number of machine basic blocks split" ); |
35 | STATISTIC(NumExpanded, "Number of branches expanded to long format" ); |
36 | |
37 | namespace { |
38 | class MSP430BSel : public MachineFunctionPass { |
39 | |
40 | typedef SmallVector<int, 16> OffsetVector; |
41 | |
42 | MachineFunction *MF; |
43 | const MSP430InstrInfo *TII; |
44 | |
45 | unsigned measureFunction(OffsetVector &BlockOffsets, |
46 | MachineBasicBlock *FromBB = nullptr); |
47 | bool expandBranches(OffsetVector &BlockOffsets); |
48 | |
49 | public: |
50 | static char ID; |
51 | MSP430BSel() : MachineFunctionPass(ID) {} |
52 | |
53 | bool runOnMachineFunction(MachineFunction &MF) override; |
54 | |
55 | MachineFunctionProperties getRequiredProperties() const override { |
56 | return MachineFunctionProperties().set( |
57 | MachineFunctionProperties::Property::NoVRegs); |
58 | } |
59 | |
60 | StringRef getPassName() const override { return "MSP430 Branch Selector" ; } |
61 | }; |
62 | char MSP430BSel::ID = 0; |
63 | } |
64 | |
65 | static bool isInRage(int DistanceInBytes) { |
66 | // According to CC430 Family User's Guide, Section 4.5.1.3, branch |
67 | // instructions have the signed 10-bit word offset field, so first we need to |
68 | // convert the distance from bytes to words, then check if it fits in 10-bit |
69 | // signed integer. |
70 | const int WordSize = 2; |
71 | |
72 | assert((DistanceInBytes % WordSize == 0) && |
73 | "Branch offset should be word aligned!" ); |
74 | |
75 | int Words = DistanceInBytes / WordSize; |
76 | return isInt<10>(x: Words); |
77 | } |
78 | |
79 | /// Measure each basic block, fill the BlockOffsets, and return the size of |
80 | /// the function, starting with BB |
81 | unsigned MSP430BSel::measureFunction(OffsetVector &BlockOffsets, |
82 | MachineBasicBlock *FromBB) { |
83 | // Give the blocks of the function a dense, in-order, numbering. |
84 | MF->RenumberBlocks(MBBFrom: FromBB); |
85 | |
86 | MachineFunction::iterator Begin; |
87 | if (FromBB == nullptr) { |
88 | Begin = MF->begin(); |
89 | } else { |
90 | Begin = FromBB->getIterator(); |
91 | } |
92 | |
93 | BlockOffsets.resize(N: MF->getNumBlockIDs()); |
94 | |
95 | unsigned TotalSize = BlockOffsets[Begin->getNumber()]; |
96 | for (auto &MBB : make_range(x: Begin, y: MF->end())) { |
97 | BlockOffsets[MBB.getNumber()] = TotalSize; |
98 | for (MachineInstr &MI : MBB) { |
99 | TotalSize += TII->getInstSizeInBytes(MI); |
100 | } |
101 | } |
102 | return TotalSize; |
103 | } |
104 | |
105 | /// Do expand branches and split the basic blocks if necessary. |
106 | /// Returns true if made any change. |
107 | bool MSP430BSel::expandBranches(OffsetVector &BlockOffsets) { |
108 | // For each conditional branch, if the offset to its destination is larger |
109 | // than the offset field allows, transform it into a long branch sequence |
110 | // like this: |
111 | // short branch: |
112 | // bCC MBB |
113 | // long branch: |
114 | // b!CC $PC+6 |
115 | // b MBB |
116 | // |
117 | bool MadeChange = false; |
118 | for (auto MBB = MF->begin(), E = MF->end(); MBB != E; ++MBB) { |
119 | unsigned MBBStartOffset = 0; |
120 | for (auto MI = MBB->begin(), EE = MBB->end(); MI != EE; ++MI) { |
121 | MBBStartOffset += TII->getInstSizeInBytes(MI: *MI); |
122 | |
123 | // If this instruction is not a short branch then skip it. |
124 | if (MI->getOpcode() != MSP430::JCC && MI->getOpcode() != MSP430::JMP) { |
125 | continue; |
126 | } |
127 | |
128 | MachineBasicBlock *DestBB = MI->getOperand(i: 0).getMBB(); |
129 | // Determine the distance from the current branch to the destination |
130 | // block. MBBStartOffset already includes the size of the current branch |
131 | // instruction. |
132 | int BlockDistance = |
133 | BlockOffsets[DestBB->getNumber()] - BlockOffsets[MBB->getNumber()]; |
134 | int BranchDistance = BlockDistance - MBBStartOffset; |
135 | |
136 | // If this branch is in range, ignore it. |
137 | if (isInRage(DistanceInBytes: BranchDistance)) { |
138 | continue; |
139 | } |
140 | |
141 | LLVM_DEBUG(dbgs() << " Found a branch that needs expanding, " |
142 | << printMBBReference(*DestBB) << ", Distance " |
143 | << BranchDistance << "\n" ); |
144 | |
145 | // If JCC is not the last instruction we need to split the MBB. |
146 | if (MI->getOpcode() == MSP430::JCC && std::next(x: MI) != EE) { |
147 | |
148 | LLVM_DEBUG(dbgs() << " Found a basic block that needs to be split, " |
149 | << printMBBReference(*MBB) << "\n" ); |
150 | |
151 | // Create a new basic block. |
152 | MachineBasicBlock *NewBB = |
153 | MF->CreateMachineBasicBlock(BB: MBB->getBasicBlock()); |
154 | MF->insert(MBBI: std::next(x: MBB), MBB: NewBB); |
155 | |
156 | // Splice the instructions following MI over to the NewBB. |
157 | NewBB->splice(Where: NewBB->end(), Other: &*MBB, From: std::next(x: MI), To: MBB->end()); |
158 | |
159 | // Update the successor lists. |
160 | for (MachineBasicBlock *Succ : MBB->successors()) { |
161 | if (Succ == DestBB) { |
162 | continue; |
163 | } |
164 | MBB->replaceSuccessor(Old: Succ, New: NewBB); |
165 | NewBB->addSuccessor(Succ); |
166 | } |
167 | |
168 | // We introduced a new MBB so all following blocks should be numbered |
169 | // and measured again. |
170 | measureFunction(BlockOffsets, FromBB: &*MBB); |
171 | |
172 | ++NumSplit; |
173 | |
174 | // It may be not necessary to start all over at this point, but it's |
175 | // safer do this anyway. |
176 | return true; |
177 | } |
178 | |
179 | MachineInstr &OldBranch = *MI; |
180 | DebugLoc dl = OldBranch.getDebugLoc(); |
181 | int InstrSizeDiff = -TII->getInstSizeInBytes(MI: OldBranch); |
182 | |
183 | if (MI->getOpcode() == MSP430::JCC) { |
184 | MachineBasicBlock *NextMBB = &*std::next(x: MBB); |
185 | assert(MBB->isSuccessor(NextMBB) && |
186 | "This block must have a layout successor!" ); |
187 | |
188 | // The BCC operands are: |
189 | // 0. Target MBB |
190 | // 1. MSP430 branch predicate |
191 | SmallVector<MachineOperand, 1> Cond; |
192 | Cond.push_back(Elt: MI->getOperand(i: 1)); |
193 | |
194 | // Jump over the long branch on the opposite condition |
195 | TII->reverseBranchCondition(Cond); |
196 | MI = BuildMI(BB&: *MBB, I: MI, MIMD: dl, MCID: TII->get(Opcode: MSP430::JCC)) |
197 | .addMBB(MBB: NextMBB) |
198 | .add(MO: Cond[0]); |
199 | InstrSizeDiff += TII->getInstSizeInBytes(MI: *MI); |
200 | ++MI; |
201 | } |
202 | |
203 | // Unconditional branch to the real destination. |
204 | MI = BuildMI(BB&: *MBB, I: MI, MIMD: dl, MCID: TII->get(Opcode: MSP430::Bi)).addMBB(MBB: DestBB); |
205 | InstrSizeDiff += TII->getInstSizeInBytes(MI: *MI); |
206 | |
207 | // Remove the old branch from the function. |
208 | OldBranch.eraseFromParent(); |
209 | |
210 | // The size of a new instruction is different from the old one, so we need |
211 | // to correct all block offsets. |
212 | for (int i = MBB->getNumber() + 1, e = BlockOffsets.size(); i < e; ++i) { |
213 | BlockOffsets[i] += InstrSizeDiff; |
214 | } |
215 | MBBStartOffset += InstrSizeDiff; |
216 | |
217 | ++NumExpanded; |
218 | MadeChange = true; |
219 | } |
220 | } |
221 | return MadeChange; |
222 | } |
223 | |
224 | bool MSP430BSel::runOnMachineFunction(MachineFunction &mf) { |
225 | MF = &mf; |
226 | TII = static_cast<const MSP430InstrInfo *>(MF->getSubtarget().getInstrInfo()); |
227 | |
228 | // If the pass is disabled, just bail early. |
229 | if (!BranchSelectEnabled) |
230 | return false; |
231 | |
232 | LLVM_DEBUG(dbgs() << "\n********** " << getPassName() << " **********\n" ); |
233 | |
234 | // BlockOffsets - Contains the distance from the beginning of the function to |
235 | // the beginning of each basic block. |
236 | OffsetVector BlockOffsets; |
237 | |
238 | unsigned FunctionSize = measureFunction(BlockOffsets); |
239 | // If the entire function is smaller than the displacement of a branch field, |
240 | // we know we don't need to expand any branches in this |
241 | // function. This is a common case. |
242 | if (isInRage(DistanceInBytes: FunctionSize)) { |
243 | return false; |
244 | } |
245 | |
246 | // Iteratively expand branches until we reach a fixed point. |
247 | bool MadeChange = false; |
248 | while (expandBranches(BlockOffsets)) |
249 | MadeChange = true; |
250 | |
251 | return MadeChange; |
252 | } |
253 | |
254 | /// Returns an instance of the Branch Selection Pass |
255 | FunctionPass *llvm::createMSP430BranchSelectionPass() { |
256 | return new MSP430BSel(); |
257 | } |
258 | |