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