/Users/buildslave/jenkins/sharedspace/clang-stage2-coverage-R@2/llvm/lib/Target/PowerPC/PPCBranchSelector.cpp
Line | Count | Source (jump to first uncovered line) |
1 | | //===-- PPCBranchSelector.cpp - Emit long conditional branches ------------===// |
2 | | // |
3 | | // The LLVM Compiler Infrastructure |
4 | | // |
5 | | // This file is distributed under the University of Illinois Open Source |
6 | | // License. See LICENSE.TXT for details. |
7 | | // |
8 | | //===----------------------------------------------------------------------===// |
9 | | // |
10 | | // This file contains a pass that scans a machine function to determine which |
11 | | // conditional branches need more than 16 bits of displacement to reach their |
12 | | // target basic block. It does this in two passes; a calculation of basic block |
13 | | // positions pass, and a branch pseudo op to machine branch opcode pass. This |
14 | | // pass should be run last, just before the assembly printer. |
15 | | // |
16 | | //===----------------------------------------------------------------------===// |
17 | | |
18 | | #include "MCTargetDesc/PPCPredicates.h" |
19 | | #include "PPC.h" |
20 | | #include "PPCInstrBuilder.h" |
21 | | #include "PPCInstrInfo.h" |
22 | | #include "PPCSubtarget.h" |
23 | | #include "llvm/ADT/Statistic.h" |
24 | | #include "llvm/CodeGen/MachineFunctionPass.h" |
25 | | #include "llvm/CodeGen/MachineRegisterInfo.h" |
26 | | #include "llvm/Support/MathExtras.h" |
27 | | #include "llvm/Target/TargetMachine.h" |
28 | | #include "llvm/Target/TargetSubtargetInfo.h" |
29 | | using namespace llvm; |
30 | | |
31 | | #define DEBUG_TYPE "ppc-branch-select" |
32 | | |
33 | | STATISTIC(NumExpanded, "Number of branches expanded to long format"); |
34 | | |
35 | | namespace llvm { |
36 | | void initializePPCBSelPass(PassRegistry&); |
37 | | } |
38 | | |
39 | | namespace { |
40 | | struct PPCBSel : public MachineFunctionPass { |
41 | | static char ID; |
42 | 1.36k | PPCBSel() : MachineFunctionPass(ID) { |
43 | 1.36k | initializePPCBSelPass(*PassRegistry::getPassRegistry()); |
44 | 1.36k | } |
45 | | |
46 | | // The sizes of the basic blocks in the function (the first |
47 | | // element of the pair); the second element of the pair is the amount of the |
48 | | // size that is due to potential padding. |
49 | | std::vector<std::pair<unsigned, unsigned>> BlockSizes; |
50 | | |
51 | | bool runOnMachineFunction(MachineFunction &Fn) override; |
52 | | |
53 | 1.36k | MachineFunctionProperties getRequiredProperties() const override { |
54 | 1.36k | return MachineFunctionProperties().set( |
55 | 1.36k | MachineFunctionProperties::Property::NoVRegs); |
56 | 1.36k | } |
57 | | |
58 | 1.36k | StringRef getPassName() const override { return "PowerPC Branch Selector"; } |
59 | | }; |
60 | | char PPCBSel::ID = 0; |
61 | | } |
62 | | |
63 | | INITIALIZE_PASS(PPCBSel, "ppc-branch-select", "PowerPC Branch Selector", |
64 | | false, false) |
65 | | |
66 | | /// createPPCBranchSelectionPass - returns an instance of the Branch Selection |
67 | | /// Pass |
68 | | /// |
69 | 1.36k | FunctionPass *llvm::createPPCBranchSelectionPass() { |
70 | 1.36k | return new PPCBSel(); |
71 | 1.36k | } |
72 | | |
73 | 7.48k | bool PPCBSel::runOnMachineFunction(MachineFunction &Fn) { |
74 | 7.48k | const PPCInstrInfo *TII = |
75 | 7.48k | static_cast<const PPCInstrInfo *>(Fn.getSubtarget().getInstrInfo()); |
76 | 7.48k | // Give the blocks of the function a dense, in-order, numbering. |
77 | 7.48k | Fn.RenumberBlocks(); |
78 | 7.48k | BlockSizes.resize(Fn.getNumBlockIDs()); |
79 | 7.48k | |
80 | 7.48k | auto GetAlignmentAdjustment = |
81 | 4.51k | [](MachineBasicBlock &MBB, unsigned Offset) -> unsigned { |
82 | 4.51k | unsigned Align = MBB.getAlignment(); |
83 | 4.51k | if (!Align) |
84 | 4.30k | return 0; |
85 | 206 | |
86 | 206 | unsigned AlignAmt = 1 << Align; |
87 | 206 | unsigned ParentAlign = MBB.getParent()->getAlignment(); |
88 | 206 | |
89 | 206 | if (Align <= ParentAlign) |
90 | 148 | return OffsetToAlignment(Offset, AlignAmt); |
91 | 58 | |
92 | 58 | // The alignment of this MBB is larger than the function's alignment, so we |
93 | 58 | // can't tell whether or not it will insert nops. Assume that it will. |
94 | 58 | return AlignAmt + OffsetToAlignment(Offset, AlignAmt); |
95 | 58 | }; |
96 | 7.48k | |
97 | 7.48k | // We need to be careful about the offset of the first block in the function |
98 | 7.48k | // because it might not have the function's alignment. This happens because, |
99 | 7.48k | // under the ELFv2 ABI, for functions which require a TOC pointer, we add a |
100 | 7.48k | // two-instruction sequence to the start of the function. |
101 | 7.48k | // Note: This needs to be synchronized with the check in |
102 | 7.48k | // PPCLinuxAsmPrinter::EmitFunctionBodyStart. |
103 | 7.48k | unsigned InitialOffset = 0; |
104 | 7.48k | if (Fn.getSubtarget<PPCSubtarget>().isELFv2ABI() && |
105 | 2.52k | !Fn.getRegInfo().use_empty(PPC::X2)) |
106 | 563 | InitialOffset = 8; |
107 | 7.48k | |
108 | 7.48k | // Measure each MBB and compute a size for the entire function. |
109 | 7.48k | unsigned FuncSize = InitialOffset; |
110 | 19.4k | for (MachineFunction::iterator MFI = Fn.begin(), E = Fn.end(); MFI != E; |
111 | 11.9k | ++MFI11.9k ) { |
112 | 11.9k | MachineBasicBlock *MBB = &*MFI; |
113 | 11.9k | |
114 | 11.9k | // The end of the previous block may have extra nops if this block has an |
115 | 11.9k | // alignment requirement. |
116 | 11.9k | if (MBB->getNumber() > 011.9k ) { |
117 | 4.51k | unsigned AlignExtra = GetAlignmentAdjustment(*MBB, FuncSize); |
118 | 4.51k | |
119 | 4.51k | auto &BS = BlockSizes[MBB->getNumber()-1]; |
120 | 4.51k | BS.first += AlignExtra; |
121 | 4.51k | BS.second = AlignExtra; |
122 | 4.51k | |
123 | 4.51k | FuncSize += AlignExtra; |
124 | 4.51k | } |
125 | 11.9k | |
126 | 11.9k | unsigned BlockSize = 0; |
127 | 11.9k | for (MachineInstr &MI : *MBB) |
128 | 68.1k | BlockSize += TII->getInstSizeInBytes(MI); |
129 | 11.9k | |
130 | 11.9k | BlockSizes[MBB->getNumber()].first = BlockSize; |
131 | 11.9k | FuncSize += BlockSize; |
132 | 11.9k | } |
133 | 7.48k | |
134 | 7.48k | // If the entire function is smaller than the displacement of a branch field, |
135 | 7.48k | // we know we don't need to shrink any branches in this function. This is a |
136 | 7.48k | // common case. |
137 | 7.48k | if (FuncSize < (1 << 15)7.48k ) { |
138 | 7.48k | BlockSizes.clear(); |
139 | 7.48k | return false; |
140 | 7.48k | } |
141 | 0 | |
142 | 0 | // For each conditional branch, if the offset to its destination is larger |
143 | 0 | // than the offset field allows, transform it into a long branch sequence |
144 | 0 | // like this: |
145 | 0 | // short branch: |
146 | 0 | // bCC MBB |
147 | 0 | // long branch: |
148 | 0 | // b!CC $PC+8 |
149 | 0 | // b MBB |
150 | 0 | // |
151 | 0 | bool MadeChange = true; |
152 | 0 | bool EverMadeChange = false; |
153 | 0 | while (MadeChange0 ) { |
154 | 0 | // Iteratively expand branches until we reach a fixed point. |
155 | 0 | MadeChange = false; |
156 | 0 | |
157 | 0 | for (MachineFunction::iterator MFI = Fn.begin(), E = Fn.end(); MFI != E; |
158 | 0 | ++MFI0 ) { |
159 | 0 | MachineBasicBlock &MBB = *MFI; |
160 | 0 | unsigned MBBStartOffset = 0; |
161 | 0 | for (MachineBasicBlock::iterator I = MBB.begin(), E = MBB.end(); |
162 | 0 | I != E0 ; ++I0 ) { |
163 | 0 | MachineBasicBlock *Dest = nullptr; |
164 | 0 | if (I->getOpcode() == PPC::BCC && 0 !I->getOperand(2).isImm()0 ) |
165 | 0 | Dest = I->getOperand(2).getMBB(); |
166 | 0 | else if (0 (I->getOpcode() == PPC::BC || 0 I->getOpcode() == PPC::BCn0 ) && |
167 | 0 | !I->getOperand(1).isImm()) |
168 | 0 | Dest = I->getOperand(1).getMBB(); |
169 | 0 | else if (0 (I->getOpcode() == PPC::BDNZ8 || 0 I->getOpcode() == PPC::BDNZ0 || |
170 | 0 | I->getOpcode() == PPC::BDZ80 || I->getOpcode() == PPC::BDZ0 ) && |
171 | 0 | !I->getOperand(0).isImm()) |
172 | 0 | Dest = I->getOperand(0).getMBB(); |
173 | 0 |
|
174 | 0 | if (!Dest0 ) { |
175 | 0 | MBBStartOffset += TII->getInstSizeInBytes(*I); |
176 | 0 | continue; |
177 | 0 | } |
178 | 0 | |
179 | 0 | // Determine the offset from the current branch to the destination |
180 | 0 | // block. |
181 | 0 | int BranchSize; |
182 | 0 | if (Dest->getNumber() <= MBB.getNumber()0 ) { |
183 | 0 | // If this is a backwards branch, the delta is the offset from the |
184 | 0 | // start of this block to this branch, plus the sizes of all blocks |
185 | 0 | // from this block to the dest. |
186 | 0 | BranchSize = MBBStartOffset; |
187 | 0 | |
188 | 0 | for (unsigned i = Dest->getNumber(), e = MBB.getNumber(); i != e0 ; ++i0 ) |
189 | 0 | BranchSize += BlockSizes[i].first; |
190 | 0 | } else { |
191 | 0 | // Otherwise, add the size of the blocks between this block and the |
192 | 0 | // dest to the number of bytes left in this block. |
193 | 0 | BranchSize = -MBBStartOffset; |
194 | 0 |
|
195 | 0 | for (unsigned i = MBB.getNumber(), e = Dest->getNumber(); i != e0 ; ++i0 ) |
196 | 0 | BranchSize += BlockSizes[i].first; |
197 | 0 | } |
198 | 0 |
|
199 | 0 | // If this branch is in range, ignore it. |
200 | 0 | if (isInt<16>(BranchSize)0 ) { |
201 | 0 | MBBStartOffset += 4; |
202 | 0 | continue; |
203 | 0 | } |
204 | 0 |
|
205 | 0 | // Otherwise, we have to expand it to a long branch. |
206 | 0 | MachineInstr &OldBranch = *I; |
207 | 0 | DebugLoc dl = OldBranch.getDebugLoc(); |
208 | 0 |
|
209 | 0 | if (I->getOpcode() == PPC::BCC0 ) { |
210 | 0 | // The BCC operands are: |
211 | 0 | // 0. PPC branch predicate |
212 | 0 | // 1. CR register |
213 | 0 | // 2. Target MBB |
214 | 0 | PPC::Predicate Pred = (PPC::Predicate)I->getOperand(0).getImm(); |
215 | 0 | unsigned CRReg = I->getOperand(1).getReg(); |
216 | 0 | |
217 | 0 | // Jump over the uncond branch inst (i.e. $PC+8) on opposite condition. |
218 | 0 | BuildMI(MBB, I, dl, TII->get(PPC::BCC)) |
219 | 0 | .addImm(PPC::InvertPredicate(Pred)).addReg(CRReg).addImm(2); |
220 | 0 | } else if (0 I->getOpcode() == PPC::BC0 ) { |
221 | 0 | unsigned CRBit = I->getOperand(0).getReg(); |
222 | 0 | BuildMI(MBB, I, dl, TII->get(PPC::BCn)).addReg(CRBit).addImm(2); |
223 | 0 | } else if (0 I->getOpcode() == PPC::BCn0 ) { |
224 | 0 | unsigned CRBit = I->getOperand(0).getReg(); |
225 | 0 | BuildMI(MBB, I, dl, TII->get(PPC::BC)).addReg(CRBit).addImm(2); |
226 | 0 | } else if (0 I->getOpcode() == PPC::BDNZ0 ) { |
227 | 0 | BuildMI(MBB, I, dl, TII->get(PPC::BDZ)).addImm(2); |
228 | 0 | } else if (0 I->getOpcode() == PPC::BDNZ80 ) { |
229 | 0 | BuildMI(MBB, I, dl, TII->get(PPC::BDZ8)).addImm(2); |
230 | 0 | } else if (0 I->getOpcode() == PPC::BDZ0 ) { |
231 | 0 | BuildMI(MBB, I, dl, TII->get(PPC::BDNZ)).addImm(2); |
232 | 0 | } else if (0 I->getOpcode() == PPC::BDZ80 ) { |
233 | 0 | BuildMI(MBB, I, dl, TII->get(PPC::BDNZ8)).addImm(2); |
234 | 0 | } else { |
235 | 0 | llvm_unreachable("Unhandled branch type!"); |
236 | 0 | } |
237 | 0 | |
238 | 0 | // Uncond branch to the real destination. |
239 | 0 | I = BuildMI(MBB, I, dl, TII->get(PPC::B)).addMBB(Dest); |
240 | 0 |
|
241 | 0 | // Remove the old branch from the function. |
242 | 0 | OldBranch.eraseFromParent(); |
243 | 0 |
|
244 | 0 | // Remember that this instruction is 8-bytes, increase the size of the |
245 | 0 | // block by 4, remember to iterate. |
246 | 0 | BlockSizes[MBB.getNumber()].first += 4; |
247 | 0 | MBBStartOffset += 8; |
248 | 0 | ++NumExpanded; |
249 | 0 | MadeChange = true; |
250 | 0 | } |
251 | 0 | } |
252 | 0 |
|
253 | 0 | if (0 MadeChange0 ) { |
254 | 0 | // If we're going to iterate again, make sure we've updated our |
255 | 0 | // padding-based contributions to the block sizes. |
256 | 0 | unsigned Offset = InitialOffset; |
257 | 0 | for (MachineFunction::iterator MFI = Fn.begin(), E = Fn.end(); MFI != E; |
258 | 0 | ++MFI0 ) { |
259 | 0 | MachineBasicBlock *MBB = &*MFI; |
260 | 0 |
|
261 | 0 | if (MBB->getNumber() > 00 ) { |
262 | 0 | auto &BS = BlockSizes[MBB->getNumber()-1]; |
263 | 0 | BS.first -= BS.second; |
264 | 0 | Offset -= BS.second; |
265 | 0 |
|
266 | 0 | unsigned AlignExtra = GetAlignmentAdjustment(*MBB, Offset); |
267 | 0 |
|
268 | 0 | BS.first += AlignExtra; |
269 | 0 | BS.second = AlignExtra; |
270 | 0 |
|
271 | 0 | Offset += AlignExtra; |
272 | 0 | } |
273 | 0 |
|
274 | 0 | Offset += BlockSizes[MBB->getNumber()].first; |
275 | 0 | } |
276 | 0 | } |
277 | 0 |
|
278 | 0 | EverMadeChange |= MadeChange; |
279 | 0 | } |
280 | 0 | |
281 | 0 | BlockSizes.clear(); |
282 | 0 | return true; |
283 | 7.48k | } |