/Users/buildslave/jenkins/workspace/clang-stage2-coverage-R/llvm/lib/Target/PowerPC/PPCBranchCoalescing.cpp
Line | Count | Source (jump to first uncovered line) |
1 | | //===-- CoalesceBranches.cpp - Coalesce blocks with the same condition ---===// |
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 | | /// Coalesce basic blocks guarded by the same branch condition into a single |
11 | | /// basic block. |
12 | | /// |
13 | | //===----------------------------------------------------------------------===// |
14 | | |
15 | | #include "PPC.h" |
16 | | #include "llvm/ADT/BitVector.h" |
17 | | #include "llvm/ADT/Statistic.h" |
18 | | #include "llvm/CodeGen/MachineDominators.h" |
19 | | #include "llvm/CodeGen/MachineFunctionPass.h" |
20 | | #include "llvm/CodeGen/MachinePostDominators.h" |
21 | | #include "llvm/CodeGen/MachineRegisterInfo.h" |
22 | | #include "llvm/CodeGen/Passes.h" |
23 | | #include "llvm/CodeGen/TargetFrameLowering.h" |
24 | | #include "llvm/CodeGen/TargetInstrInfo.h" |
25 | | #include "llvm/CodeGen/TargetSubtargetInfo.h" |
26 | | #include "llvm/Support/Debug.h" |
27 | | |
28 | | using namespace llvm; |
29 | | |
30 | | #define DEBUG_TYPE "ppc-branch-coalescing" |
31 | | |
32 | | STATISTIC(NumBlocksCoalesced, "Number of blocks coalesced"); |
33 | | STATISTIC(NumPHINotMoved, "Number of PHI Nodes that cannot be merged"); |
34 | | STATISTIC(NumBlocksNotCoalesced, "Number of blocks not coalesced"); |
35 | | |
36 | | //===----------------------------------------------------------------------===// |
37 | | // PPCBranchCoalescing |
38 | | //===----------------------------------------------------------------------===// |
39 | | /// |
40 | | /// Improve scheduling by coalescing branches that depend on the same condition. |
41 | | /// This pass looks for blocks that are guarded by the same branch condition |
42 | | /// and attempts to merge the blocks together. Such opportunities arise from |
43 | | /// the expansion of select statements in the IR. |
44 | | /// |
45 | | /// This pass does not handle implicit operands on branch statements. In order |
46 | | /// to run on targets that use implicit operands, changes need to be made in the |
47 | | /// canCoalesceBranch and canMerge methods. |
48 | | /// |
49 | | /// Example: the following LLVM IR |
50 | | /// |
51 | | /// %test = icmp eq i32 %x 0 |
52 | | /// %tmp1 = select i1 %test, double %a, double 2.000000e-03 |
53 | | /// %tmp2 = select i1 %test, double %b, double 5.000000e-03 |
54 | | /// |
55 | | /// expands to the following machine code: |
56 | | /// |
57 | | /// %bb.0: derived from LLVM BB %entry |
58 | | /// liveins: %f1 %f3 %x6 |
59 | | /// <SNIP1> |
60 | | /// %0 = COPY %f1; F8RC:%0 |
61 | | /// %5 = CMPLWI killed %4, 0; CRRC:%5 GPRC:%4 |
62 | | /// %8 = LXSDX %zero8, killed %7, implicit %rm; |
63 | | /// mem:LD8[ConstantPool] F8RC:%8 G8RC:%7 |
64 | | /// BCC 76, %5, <%bb.2>; CRRC:%5 |
65 | | /// Successors according to CFG: %bb.1(?%) %bb.2(?%) |
66 | | /// |
67 | | /// %bb.1: derived from LLVM BB %entry |
68 | | /// Predecessors according to CFG: %bb.0 |
69 | | /// Successors according to CFG: %bb.2(?%) |
70 | | /// |
71 | | /// %bb.2: derived from LLVM BB %entry |
72 | | /// Predecessors according to CFG: %bb.0 %bb.1 |
73 | | /// %9 = PHI %8, <%bb.1>, %0, <%bb.0>; |
74 | | /// F8RC:%9,%8,%0 |
75 | | /// <SNIP2> |
76 | | /// BCC 76, %5, <%bb.4>; CRRC:%5 |
77 | | /// Successors according to CFG: %bb.3(?%) %bb.4(?%) |
78 | | /// |
79 | | /// %bb.3: derived from LLVM BB %entry |
80 | | /// Predecessors according to CFG: %bb.2 |
81 | | /// Successors according to CFG: %bb.4(?%) |
82 | | /// |
83 | | /// %bb.4: derived from LLVM BB %entry |
84 | | /// Predecessors according to CFG: %bb.2 %bb.3 |
85 | | /// %13 = PHI %12, <%bb.3>, %2, <%bb.2>; |
86 | | /// F8RC:%13,%12,%2 |
87 | | /// <SNIP3> |
88 | | /// BLR8 implicit %lr8, implicit %rm, implicit %f1 |
89 | | /// |
90 | | /// When this pattern is detected, branch coalescing will try to collapse |
91 | | /// it by moving code in %bb.2 to %bb.0 and/or %bb.4 and removing %bb.3. |
92 | | /// |
93 | | /// If all conditions are meet, IR should collapse to: |
94 | | /// |
95 | | /// %bb.0: derived from LLVM BB %entry |
96 | | /// liveins: %f1 %f3 %x6 |
97 | | /// <SNIP1> |
98 | | /// %0 = COPY %f1; F8RC:%0 |
99 | | /// %5 = CMPLWI killed %4, 0; CRRC:%5 GPRC:%4 |
100 | | /// %8 = LXSDX %zero8, killed %7, implicit %rm; |
101 | | /// mem:LD8[ConstantPool] F8RC:%8 G8RC:%7 |
102 | | /// <SNIP2> |
103 | | /// BCC 76, %5, <%bb.4>; CRRC:%5 |
104 | | /// Successors according to CFG: %bb.1(0x2aaaaaaa / 0x80000000 = 33.33%) |
105 | | /// %bb.4(0x55555554 / 0x80000000 = 66.67%) |
106 | | /// |
107 | | /// %bb.1: derived from LLVM BB %entry |
108 | | /// Predecessors according to CFG: %bb.0 |
109 | | /// Successors according to CFG: %bb.4(0x40000000 / 0x80000000 = 50.00%) |
110 | | /// |
111 | | /// %bb.4: derived from LLVM BB %entry |
112 | | /// Predecessors according to CFG: %bb.0 %bb.1 |
113 | | /// %9 = PHI %8, <%bb.1>, %0, <%bb.0>; |
114 | | /// F8RC:%9,%8,%0 |
115 | | /// %13 = PHI %12, <%bb.1>, %2, <%bb.0>; |
116 | | /// F8RC:%13,%12,%2 |
117 | | /// <SNIP3> |
118 | | /// BLR8 implicit %lr8, implicit %rm, implicit %f1 |
119 | | /// |
120 | | /// Branch Coalescing does not split blocks, it moves everything in the same |
121 | | /// direction ensuring it does not break use/definition semantics. |
122 | | /// |
123 | | /// PHI nodes and its corresponding use instructions are moved to its successor |
124 | | /// block if there are no uses within the successor block PHI nodes. PHI |
125 | | /// node ordering cannot be assumed. |
126 | | /// |
127 | | /// Non-PHI can be moved up to the predecessor basic block or down to the |
128 | | /// successor basic block following any PHI instructions. Whether it moves |
129 | | /// up or down depends on whether the register(s) defined in the instructions |
130 | | /// are used in current block or in any PHI instructions at the beginning of |
131 | | /// the successor block. |
132 | | |
133 | | namespace { |
134 | | |
135 | | class PPCBranchCoalescing : public MachineFunctionPass { |
136 | | struct CoalescingCandidateInfo { |
137 | | MachineBasicBlock *BranchBlock; // Block containing the branch |
138 | | MachineBasicBlock *BranchTargetBlock; // Block branched to |
139 | | MachineBasicBlock *FallThroughBlock; // Fall-through if branch not taken |
140 | | SmallVector<MachineOperand, 4> Cond; |
141 | | bool MustMoveDown; |
142 | | bool MustMoveUp; |
143 | | |
144 | | CoalescingCandidateInfo(); |
145 | | void clear(); |
146 | | }; |
147 | | |
148 | | MachineDominatorTree *MDT; |
149 | | MachinePostDominatorTree *MPDT; |
150 | | const TargetInstrInfo *TII; |
151 | | MachineRegisterInfo *MRI; |
152 | | |
153 | | void initialize(MachineFunction &F); |
154 | | bool canCoalesceBranch(CoalescingCandidateInfo &Cand); |
155 | | bool identicalOperands(ArrayRef<MachineOperand> OperandList1, |
156 | | ArrayRef<MachineOperand> OperandList2) const; |
157 | | bool validateCandidates(CoalescingCandidateInfo &SourceRegion, |
158 | | CoalescingCandidateInfo &TargetRegion) const; |
159 | | |
160 | | public: |
161 | | static char ID; |
162 | | |
163 | 4 | PPCBranchCoalescing() : MachineFunctionPass(ID) { |
164 | 4 | initializePPCBranchCoalescingPass(*PassRegistry::getPassRegistry()); |
165 | 4 | } |
166 | | |
167 | 3 | void getAnalysisUsage(AnalysisUsage &AU) const override { |
168 | 3 | AU.addRequired<MachineDominatorTree>(); |
169 | 3 | AU.addRequired<MachinePostDominatorTree>(); |
170 | 3 | MachineFunctionPass::getAnalysisUsage(AU); |
171 | 3 | } |
172 | | |
173 | 6 | StringRef getPassName() const override { return "Branch Coalescing"; } |
174 | | |
175 | | bool mergeCandidates(CoalescingCandidateInfo &SourceRegion, |
176 | | CoalescingCandidateInfo &TargetRegion); |
177 | | bool canMoveToBeginning(const MachineInstr &MI, |
178 | | const MachineBasicBlock &MBB) const; |
179 | | bool canMoveToEnd(const MachineInstr &MI, |
180 | | const MachineBasicBlock &MBB) const; |
181 | | bool canMerge(CoalescingCandidateInfo &SourceRegion, |
182 | | CoalescingCandidateInfo &TargetRegion) const; |
183 | | void moveAndUpdatePHIs(MachineBasicBlock *SourceRegionMBB, |
184 | | MachineBasicBlock *TargetRegionMBB); |
185 | | bool runOnMachineFunction(MachineFunction &MF) override; |
186 | | }; |
187 | | } // End anonymous namespace. |
188 | | |
189 | | char PPCBranchCoalescing::ID = 0; |
190 | | /// createPPCBranchCoalescingPass - returns an instance of the Branch Coalescing |
191 | | /// Pass |
192 | 4 | FunctionPass *llvm::createPPCBranchCoalescingPass() { |
193 | 4 | return new PPCBranchCoalescing(); |
194 | 4 | } |
195 | | |
196 | 101k | INITIALIZE_PASS_BEGIN(PPCBranchCoalescing, DEBUG_TYPE, |
197 | 101k | "Branch Coalescing", false, false) |
198 | 101k | INITIALIZE_PASS_DEPENDENCY(MachineDominatorTree) |
199 | 101k | INITIALIZE_PASS_DEPENDENCY(MachinePostDominatorTree) |
200 | 101k | INITIALIZE_PASS_END(PPCBranchCoalescing, DEBUG_TYPE, "Branch Coalescing", |
201 | | false, false) |
202 | | |
203 | | PPCBranchCoalescing::CoalescingCandidateInfo::CoalescingCandidateInfo() |
204 | | : BranchBlock(nullptr), BranchTargetBlock(nullptr), |
205 | 4 | FallThroughBlock(nullptr), MustMoveDown(false), MustMoveUp(false) {} |
206 | | |
207 | 20 | void PPCBranchCoalescing::CoalescingCandidateInfo::clear() { |
208 | 20 | BranchBlock = nullptr; |
209 | 20 | BranchTargetBlock = nullptr; |
210 | 20 | FallThroughBlock = nullptr; |
211 | 20 | Cond.clear(); |
212 | 20 | MustMoveDown = false; |
213 | 20 | MustMoveUp = false; |
214 | 20 | } |
215 | | |
216 | 2 | void PPCBranchCoalescing::initialize(MachineFunction &MF) { |
217 | 2 | MDT = &getAnalysis<MachineDominatorTree>(); |
218 | 2 | MPDT = &getAnalysis<MachinePostDominatorTree>(); |
219 | 2 | TII = MF.getSubtarget().getInstrInfo(); |
220 | 2 | MRI = &MF.getRegInfo(); |
221 | 2 | } |
222 | | |
223 | | /// |
224 | | /// Analyze the branch statement to determine if it can be coalesced. This |
225 | | /// method analyses the branch statement for the given candidate to determine |
226 | | /// if it can be coalesced. If the branch can be coalesced, then the |
227 | | /// BranchTargetBlock and the FallThroughBlock are recorded in the specified |
228 | | /// Candidate. |
229 | | /// |
230 | | ///\param[in,out] Cand The coalescing candidate to analyze |
231 | | ///\return true if and only if the branch can be coalesced, false otherwise |
232 | | /// |
233 | 16 | bool PPCBranchCoalescing::canCoalesceBranch(CoalescingCandidateInfo &Cand) { |
234 | 16 | LLVM_DEBUG(dbgs() << "Determine if branch block " |
235 | 16 | << Cand.BranchBlock->getNumber() << " can be coalesced:"); |
236 | 16 | MachineBasicBlock *FalseMBB = nullptr; |
237 | 16 | |
238 | 16 | if (TII->analyzeBranch(*Cand.BranchBlock, Cand.BranchTargetBlock, FalseMBB, |
239 | 16 | Cand.Cond)) { |
240 | 4 | LLVM_DEBUG(dbgs() << "TII unable to Analyze Branch - skip\n"); |
241 | 4 | return false; |
242 | 4 | } |
243 | 12 | |
244 | 12 | for (auto &I : Cand.BranchBlock->terminators()) { |
245 | 10 | LLVM_DEBUG(dbgs() << "Looking at terminator : " << I << "\n"); |
246 | 10 | if (!I.isBranch()) |
247 | 0 | continue; |
248 | 10 | |
249 | 10 | // The analyzeBranch method does not include any implicit operands. |
250 | 10 | // This is not an issue on PPC but must be handled on other targets. |
251 | 10 | // For this pass to be made target-independent, the analyzeBranch API |
252 | 10 | // need to be updated to support implicit operands and there would |
253 | 10 | // need to be a way to verify that any implicit operands would not be |
254 | 10 | // clobbered by merging blocks. This would include identifying the |
255 | 10 | // implicit operands as well as the basic block they are defined in. |
256 | 10 | // This could be done by changing the analyzeBranch API to have it also |
257 | 10 | // record and return the implicit operands and the blocks where they are |
258 | 10 | // defined. Alternatively, the BranchCoalescing code would need to be |
259 | 10 | // extended to identify the implicit operands. The analysis in canMerge |
260 | 10 | // must then be extended to prove that none of the implicit operands are |
261 | 10 | // changed in the blocks that are combined during coalescing. |
262 | 10 | if (I.getNumOperands() != I.getNumExplicitOperands()) { |
263 | 0 | LLVM_DEBUG(dbgs() << "Terminator contains implicit operands - skip : " |
264 | 0 | << I << "\n"); |
265 | 0 | return false; |
266 | 0 | } |
267 | 10 | } |
268 | 12 | |
269 | 12 | if (Cand.BranchBlock->isEHPad() || Cand.BranchBlock->hasEHPadSuccessor()) { |
270 | 0 | LLVM_DEBUG(dbgs() << "EH Pad - skip\n"); |
271 | 0 | return false; |
272 | 0 | } |
273 | 12 | |
274 | 12 | // For now only consider triangles (i.e, BranchTargetBlock is set, |
275 | 12 | // FalseMBB is null, and BranchTargetBlock is a successor to BranchBlock) |
276 | 12 | if (!Cand.BranchTargetBlock || FalseMBB10 || |
277 | 12 | !Cand.BranchBlock->isSuccessor(Cand.BranchTargetBlock)10 ) { |
278 | 2 | LLVM_DEBUG(dbgs() << "Does not form a triangle - skip\n"); |
279 | 2 | return false; |
280 | 2 | } |
281 | 10 | |
282 | 10 | // Ensure there are only two successors |
283 | 10 | if (Cand.BranchBlock->succ_size() != 2) { |
284 | 0 | LLVM_DEBUG(dbgs() << "Does not have 2 successors - skip\n"); |
285 | 0 | return false; |
286 | 0 | } |
287 | 10 | |
288 | 10 | // Sanity check - the block must be able to fall through |
289 | 10 | assert(Cand.BranchBlock->canFallThrough() && |
290 | 10 | "Expecting the block to fall through!"); |
291 | 10 | |
292 | 10 | // We have already ensured there are exactly two successors to |
293 | 10 | // BranchBlock and that BranchTargetBlock is a successor to BranchBlock. |
294 | 10 | // Ensure the single fall though block is empty. |
295 | 10 | MachineBasicBlock *Succ = |
296 | 10 | (*Cand.BranchBlock->succ_begin() == Cand.BranchTargetBlock) |
297 | 10 | ? *Cand.BranchBlock->succ_rbegin()0 |
298 | 10 | : *Cand.BranchBlock->succ_begin(); |
299 | 10 | |
300 | 10 | assert(Succ && "Expecting a valid fall-through block\n"); |
301 | 10 | |
302 | 10 | if (!Succ->empty()) { |
303 | 0 | LLVM_DEBUG(dbgs() << "Fall-through block contains code -- skip\n"); |
304 | 0 | return false; |
305 | 0 | } |
306 | 10 | |
307 | 10 | if (!Succ->isSuccessor(Cand.BranchTargetBlock)) { |
308 | 0 | LLVM_DEBUG( |
309 | 0 | dbgs() |
310 | 0 | << "Successor of fall through block is not branch taken block\n"); |
311 | 0 | return false; |
312 | 0 | } |
313 | 10 | |
314 | 10 | Cand.FallThroughBlock = Succ; |
315 | 10 | LLVM_DEBUG(dbgs() << "Valid Candidate\n"); |
316 | 10 | return true; |
317 | 10 | } |
318 | | |
319 | | /// |
320 | | /// Determine if the two operand lists are identical |
321 | | /// |
322 | | /// \param[in] OpList1 operand list |
323 | | /// \param[in] OpList2 operand list |
324 | | /// \return true if and only if the operands lists are identical |
325 | | /// |
326 | | bool PPCBranchCoalescing::identicalOperands( |
327 | 4 | ArrayRef<MachineOperand> OpList1, ArrayRef<MachineOperand> OpList2) const { |
328 | 4 | |
329 | 4 | if (OpList1.size() != OpList2.size()) { |
330 | 0 | LLVM_DEBUG(dbgs() << "Operand list is different size\n"); |
331 | 0 | return false; |
332 | 0 | } |
333 | 4 | |
334 | 12 | for (unsigned i = 0; 4 i < OpList1.size(); ++i8 ) { |
335 | 8 | const MachineOperand &Op1 = OpList1[i]; |
336 | 8 | const MachineOperand &Op2 = OpList2[i]; |
337 | 8 | |
338 | 8 | LLVM_DEBUG(dbgs() << "Op1: " << Op1 << "\n" |
339 | 8 | << "Op2: " << Op2 << "\n"); |
340 | 8 | |
341 | 8 | if (Op1.isIdenticalTo(Op2)) { |
342 | 8 | // filter out instructions with physical-register uses |
343 | 8 | if (Op1.isReg() && TargetRegisterInfo::isPhysicalRegister(Op1.getReg())4 |
344 | 8 | // If the physical register is constant then we can assume the value |
345 | 8 | // has not changed between uses. |
346 | 8 | && !(0 Op1.isUse()0 && MRI->isConstantPhysReg(Op1.getReg())0 )) { |
347 | 0 | LLVM_DEBUG(dbgs() << "The operands are not provably identical.\n"); |
348 | 0 | return false; |
349 | 0 | } |
350 | 8 | LLVM_DEBUG(dbgs() << "Op1 and Op2 are identical!\n"); |
351 | 8 | continue; |
352 | 8 | } |
353 | 0 | |
354 | 0 | // If the operands are not identical, but are registers, check to see if the |
355 | 0 | // definition of the register produces the same value. If they produce the |
356 | 0 | // same value, consider them to be identical. |
357 | 0 | if (Op1.isReg() && Op2.isReg() && |
358 | 0 | TargetRegisterInfo::isVirtualRegister(Op1.getReg()) && |
359 | 0 | TargetRegisterInfo::isVirtualRegister(Op2.getReg())) { |
360 | 0 | MachineInstr *Op1Def = MRI->getVRegDef(Op1.getReg()); |
361 | 0 | MachineInstr *Op2Def = MRI->getVRegDef(Op2.getReg()); |
362 | 0 | if (TII->produceSameValue(*Op1Def, *Op2Def, MRI)) { |
363 | 0 | LLVM_DEBUG(dbgs() << "Op1Def: " << *Op1Def << " and " << *Op2Def |
364 | 0 | << " produce the same value!\n"); |
365 | 0 | } else { |
366 | 0 | LLVM_DEBUG(dbgs() << "Operands produce different values\n"); |
367 | 0 | return false; |
368 | 0 | } |
369 | 0 | } else { |
370 | 0 | LLVM_DEBUG(dbgs() << "The operands are not provably identical.\n"); |
371 | 0 | return false; |
372 | 0 | } |
373 | 0 | } |
374 | 4 | |
375 | 4 | return true; |
376 | 4 | } |
377 | | |
378 | | /// |
379 | | /// Moves ALL PHI instructions in SourceMBB to beginning of TargetMBB |
380 | | /// and update them to refer to the new block. PHI node ordering |
381 | | /// cannot be assumed so it does not matter where the PHI instructions |
382 | | /// are moved to in TargetMBB. |
383 | | /// |
384 | | /// \param[in] SourceMBB block to move PHI instructions from |
385 | | /// \param[in] TargetMBB block to move PHI instructions to |
386 | | /// |
387 | | void PPCBranchCoalescing::moveAndUpdatePHIs(MachineBasicBlock *SourceMBB, |
388 | 4 | MachineBasicBlock *TargetMBB) { |
389 | 4 | |
390 | 4 | MachineBasicBlock::iterator MI = SourceMBB->begin(); |
391 | 4 | MachineBasicBlock::iterator ME = SourceMBB->getFirstNonPHI(); |
392 | 4 | |
393 | 4 | if (MI == ME) { |
394 | 0 | LLVM_DEBUG(dbgs() << "SourceMBB contains no PHI instructions.\n"); |
395 | 0 | return; |
396 | 0 | } |
397 | 4 | |
398 | 4 | // Update all PHI instructions in SourceMBB and move to top of TargetMBB |
399 | 10 | for (MachineBasicBlock::iterator Iter = MI; 4 Iter != ME; Iter++6 ) { |
400 | 6 | MachineInstr &PHIInst = *Iter; |
401 | 18 | for (unsigned i = 2, e = PHIInst.getNumOperands() + 1; i != e; i += 212 ) { |
402 | 12 | MachineOperand &MO = PHIInst.getOperand(i); |
403 | 12 | if (MO.getMBB() == SourceMBB) |
404 | 0 | MO.setMBB(TargetMBB); |
405 | 12 | } |
406 | 6 | } |
407 | 4 | TargetMBB->splice(TargetMBB->begin(), SourceMBB, MI, ME); |
408 | 4 | } |
409 | | |
410 | | /// |
411 | | /// This function checks if MI can be moved to the beginning of the TargetMBB |
412 | | /// following PHI instructions. A MI instruction can be moved to beginning of |
413 | | /// the TargetMBB if there are no uses of it within the TargetMBB PHI nodes. |
414 | | /// |
415 | | /// \param[in] MI the machine instruction to move. |
416 | | /// \param[in] TargetMBB the machine basic block to move to |
417 | | /// \return true if it is safe to move MI to beginning of TargetMBB, |
418 | | /// false otherwise. |
419 | | /// |
420 | | bool PPCBranchCoalescing::canMoveToBeginning(const MachineInstr &MI, |
421 | | const MachineBasicBlock &TargetMBB |
422 | 12 | ) const { |
423 | 12 | |
424 | 12 | LLVM_DEBUG(dbgs() << "Checking if " << MI << " can move to beginning of " |
425 | 12 | << TargetMBB.getNumber() << "\n"); |
426 | 12 | |
427 | 12 | for (auto &Def : MI.defs()) { // Looking at Def |
428 | 8 | for (auto &Use : MRI->use_instructions(Def.getReg())) { |
429 | 8 | if (Use.isPHI() && Use.getParent() == &TargetMBB4 ) { |
430 | 4 | LLVM_DEBUG(dbgs() << " *** used in a PHI -- cannot move ***\n"); |
431 | 4 | return false; |
432 | 4 | } |
433 | 8 | } |
434 | 8 | } |
435 | 12 | |
436 | 12 | LLVM_DEBUG8 (dbgs() << " Safe to move to the beginning.\n"); |
437 | 8 | return true; |
438 | 12 | } |
439 | | |
440 | | /// |
441 | | /// This function checks if MI can be moved to the end of the TargetMBB, |
442 | | /// immediately before the first terminator. A MI instruction can be moved |
443 | | /// to then end of the TargetMBB if no PHI node defines what MI uses within |
444 | | /// it's own MBB. |
445 | | /// |
446 | | /// \param[in] MI the machine instruction to move. |
447 | | /// \param[in] TargetMBB the machine basic block to move to |
448 | | /// \return true if it is safe to move MI to end of TargetMBB, |
449 | | /// false otherwise. |
450 | | /// |
451 | | bool PPCBranchCoalescing::canMoveToEnd(const MachineInstr &MI, |
452 | | const MachineBasicBlock &TargetMBB |
453 | 12 | ) const { |
454 | 12 | |
455 | 12 | LLVM_DEBUG(dbgs() << "Checking if " << MI << " can move to end of " |
456 | 12 | << TargetMBB.getNumber() << "\n"); |
457 | 12 | |
458 | 26 | for (auto &Use : MI.uses()) { |
459 | 26 | if (Use.isReg() && TargetRegisterInfo::isVirtualRegister(Use.getReg())14 ) { |
460 | 8 | MachineInstr *DefInst = MRI->getVRegDef(Use.getReg()); |
461 | 8 | if (DefInst->isPHI() && DefInst->getParent() == MI.getParent()0 ) { |
462 | 0 | LLVM_DEBUG(dbgs() << " *** Cannot move this instruction ***\n"); |
463 | 0 | return false; |
464 | 8 | } else { |
465 | 8 | LLVM_DEBUG( |
466 | 8 | dbgs() << " *** def is in another block -- safe to move!\n"); |
467 | 8 | } |
468 | 8 | } |
469 | 26 | } |
470 | 12 | |
471 | 12 | LLVM_DEBUG(dbgs() << " Safe to move to the end.\n"); |
472 | 12 | return true; |
473 | 12 | } |
474 | | |
475 | | /// |
476 | | /// This method checks to ensure the two coalescing candidates follows the |
477 | | /// expected pattern required for coalescing. |
478 | | /// |
479 | | /// \param[in] SourceRegion The candidate to move statements from |
480 | | /// \param[in] TargetRegion The candidate to move statements to |
481 | | /// \return true if all instructions in SourceRegion.BranchBlock can be merged |
482 | | /// into a block in TargetRegion; false otherwise. |
483 | | /// |
484 | | bool PPCBranchCoalescing::validateCandidates( |
485 | | CoalescingCandidateInfo &SourceRegion, |
486 | 8 | CoalescingCandidateInfo &TargetRegion) const { |
487 | 8 | |
488 | 8 | if (TargetRegion.BranchTargetBlock != SourceRegion.BranchBlock) |
489 | 8 | llvm_unreachable0 ("Expecting SourceRegion to immediately follow TargetRegion"); |
490 | 8 | else if (!MDT->dominates(TargetRegion.BranchBlock, SourceRegion.BranchBlock)) |
491 | 8 | llvm_unreachable0 ("Expecting TargetRegion to dominate SourceRegion"); |
492 | 8 | else if (!MPDT->dominates(SourceRegion.BranchBlock, TargetRegion.BranchBlock)) |
493 | 8 | llvm_unreachable0 ("Expecting SourceRegion to post-dominate TargetRegion"); |
494 | 8 | else if (!TargetRegion.FallThroughBlock->empty() || |
495 | 8 | !SourceRegion.FallThroughBlock->empty()) |
496 | 8 | llvm_unreachable0 ("Expecting fall-through blocks to be empty"); |
497 | 8 | |
498 | 8 | return true; |
499 | 8 | } |
500 | | |
501 | | /// |
502 | | /// This method determines whether the two coalescing candidates can be merged. |
503 | | /// In order to be merged, all instructions must be able to |
504 | | /// 1. Move to the beginning of the SourceRegion.BranchTargetBlock; |
505 | | /// 2. Move to the end of the TargetRegion.BranchBlock. |
506 | | /// Merging involves moving the instructions in the |
507 | | /// TargetRegion.BranchTargetBlock (also SourceRegion.BranchBlock). |
508 | | /// |
509 | | /// This function first try to move instructions from the |
510 | | /// TargetRegion.BranchTargetBlock down, to the beginning of the |
511 | | /// SourceRegion.BranchTargetBlock. This is not possible if any register defined |
512 | | /// in TargetRegion.BranchTargetBlock is used in a PHI node in the |
513 | | /// SourceRegion.BranchTargetBlock. In this case, check whether the statement |
514 | | /// can be moved up, to the end of the TargetRegion.BranchBlock (immediately |
515 | | /// before the branch statement). If it cannot move, then these blocks cannot |
516 | | /// be merged. |
517 | | /// |
518 | | /// Note that there is no analysis for moving instructions past the fall-through |
519 | | /// blocks because they are confirmed to be empty. An assert is thrown if they |
520 | | /// are not. |
521 | | /// |
522 | | /// \param[in] SourceRegion The candidate to move statements from |
523 | | /// \param[in] TargetRegion The candidate to move statements to |
524 | | /// \return true if all instructions in SourceRegion.BranchBlock can be merged |
525 | | /// into a block in TargetRegion, false otherwise. |
526 | | /// |
527 | | bool PPCBranchCoalescing::canMerge(CoalescingCandidateInfo &SourceRegion, |
528 | 4 | CoalescingCandidateInfo &TargetRegion) const { |
529 | 4 | if (!validateCandidates(SourceRegion, TargetRegion)) |
530 | 0 | return false; |
531 | 4 | |
532 | 4 | // Walk through PHI nodes first and see if they force the merge into the |
533 | 4 | // SourceRegion.BranchTargetBlock. |
534 | 4 | for (MachineBasicBlock::iterator |
535 | 4 | I = SourceRegion.BranchBlock->instr_begin(), |
536 | 4 | E = SourceRegion.BranchBlock->getFirstNonPHI(); |
537 | 10 | I != E; ++I6 ) { |
538 | 6 | for (auto &Def : I->defs()) |
539 | 6 | for (auto &Use : MRI->use_instructions(Def.getReg())) { |
540 | 6 | if (Use.isPHI() && Use.getParent() == SourceRegion.BranchTargetBlock0 ) { |
541 | 0 | LLVM_DEBUG(dbgs() |
542 | 0 | << "PHI " << *I |
543 | 0 | << " defines register used in another " |
544 | 0 | "PHI within branch target block -- can't merge\n"); |
545 | 0 | NumPHINotMoved++; |
546 | 0 | return false; |
547 | 0 | } |
548 | 6 | if (Use.getParent() == SourceRegion.BranchBlock) { |
549 | 0 | LLVM_DEBUG(dbgs() << "PHI " << *I |
550 | 0 | << " defines register used in this " |
551 | 0 | "block -- all must move down\n"); |
552 | 0 | SourceRegion.MustMoveDown = true; |
553 | 0 | } |
554 | 6 | } |
555 | 6 | } |
556 | 4 | |
557 | 4 | // Walk through the MI to see if they should be merged into |
558 | 4 | // TargetRegion.BranchBlock (up) or SourceRegion.BranchTargetBlock (down) |
559 | 4 | for (MachineBasicBlock::iterator |
560 | 4 | I = SourceRegion.BranchBlock->getFirstNonPHI(), |
561 | 4 | E = SourceRegion.BranchBlock->end(); |
562 | 16 | I != E; ++I12 ) { |
563 | 12 | if (!canMoveToBeginning(*I, *SourceRegion.BranchTargetBlock)) { |
564 | 4 | LLVM_DEBUG(dbgs() << "Instruction " << *I |
565 | 4 | << " cannot move down - must move up!\n"); |
566 | 4 | SourceRegion.MustMoveUp = true; |
567 | 4 | } |
568 | 12 | if (!canMoveToEnd(*I, *TargetRegion.BranchBlock)) { |
569 | 0 | LLVM_DEBUG(dbgs() << "Instruction " << *I |
570 | 0 | << " cannot move up - must move down!\n"); |
571 | 0 | SourceRegion.MustMoveDown = true; |
572 | 0 | } |
573 | 12 | } |
574 | 4 | |
575 | 4 | return (SourceRegion.MustMoveUp && SourceRegion.MustMoveDown) ? false0 : true; |
576 | 4 | } |
577 | | |
578 | | /// Merge the instructions from SourceRegion.BranchBlock, |
579 | | /// SourceRegion.BranchTargetBlock, and SourceRegion.FallThroughBlock into |
580 | | /// TargetRegion.BranchBlock, TargetRegion.BranchTargetBlock and |
581 | | /// TargetRegion.FallThroughBlock respectively. |
582 | | /// |
583 | | /// The successors for blocks in TargetRegion will be updated to use the |
584 | | /// successors from blocks in SourceRegion. Finally, the blocks in SourceRegion |
585 | | /// will be removed from the function. |
586 | | /// |
587 | | /// A region consists of a BranchBlock, a FallThroughBlock, and a |
588 | | /// BranchTargetBlock. Branch coalesce works on patterns where the |
589 | | /// TargetRegion's BranchTargetBlock must also be the SourceRegions's |
590 | | /// BranchBlock. |
591 | | /// |
592 | | /// Before mergeCandidates: |
593 | | /// |
594 | | /// +---------------------------+ |
595 | | /// | TargetRegion.BranchBlock | |
596 | | /// +---------------------------+ |
597 | | /// / | |
598 | | /// / +--------------------------------+ |
599 | | /// | | TargetRegion.FallThroughBlock | |
600 | | /// \ +--------------------------------+ |
601 | | /// \ | |
602 | | /// +----------------------------------+ |
603 | | /// | TargetRegion.BranchTargetBlock | |
604 | | /// | SourceRegion.BranchBlock | |
605 | | /// +----------------------------------+ |
606 | | /// / | |
607 | | /// / +--------------------------------+ |
608 | | /// | | SourceRegion.FallThroughBlock | |
609 | | /// \ +--------------------------------+ |
610 | | /// \ | |
611 | | /// +----------------------------------+ |
612 | | /// | SourceRegion.BranchTargetBlock | |
613 | | /// +----------------------------------+ |
614 | | /// |
615 | | /// After mergeCandidates: |
616 | | /// |
617 | | /// +-----------------------------+ |
618 | | /// | TargetRegion.BranchBlock | |
619 | | /// | SourceRegion.BranchBlock | |
620 | | /// +-----------------------------+ |
621 | | /// / | |
622 | | /// / +---------------------------------+ |
623 | | /// | | TargetRegion.FallThroughBlock | |
624 | | /// | | SourceRegion.FallThroughBlock | |
625 | | /// \ +---------------------------------+ |
626 | | /// \ | |
627 | | /// +----------------------------------+ |
628 | | /// | SourceRegion.BranchTargetBlock | |
629 | | /// +----------------------------------+ |
630 | | /// |
631 | | /// \param[in] SourceRegion The candidate to move blocks from |
632 | | /// \param[in] TargetRegion The candidate to move blocks to |
633 | | /// |
634 | | bool PPCBranchCoalescing::mergeCandidates(CoalescingCandidateInfo &SourceRegion, |
635 | 4 | CoalescingCandidateInfo &TargetRegion) { |
636 | 4 | |
637 | 4 | if (SourceRegion.MustMoveUp && SourceRegion.MustMoveDown) { |
638 | 0 | llvm_unreachable("Cannot have both MustMoveDown and MustMoveUp set!"); |
639 | 0 | return false; |
640 | 4 | } |
641 | 4 | |
642 | 4 | if (!validateCandidates(SourceRegion, TargetRegion)) |
643 | 0 | return false; |
644 | 4 | |
645 | 4 | // Start the merging process by first handling the BranchBlock. |
646 | 4 | // Move any PHIs in SourceRegion.BranchBlock down to the branch-taken block |
647 | 4 | moveAndUpdatePHIs(SourceRegion.BranchBlock, SourceRegion.BranchTargetBlock); |
648 | 4 | |
649 | 4 | // Move remaining instructions in SourceRegion.BranchBlock into |
650 | 4 | // TargetRegion.BranchBlock |
651 | 4 | MachineBasicBlock::iterator firstInstr = |
652 | 4 | SourceRegion.BranchBlock->getFirstNonPHI(); |
653 | 4 | MachineBasicBlock::iterator lastInstr = |
654 | 4 | SourceRegion.BranchBlock->getFirstTerminator(); |
655 | 4 | |
656 | 4 | MachineBasicBlock *Source = SourceRegion.MustMoveDown |
657 | 4 | ? SourceRegion.BranchTargetBlock0 |
658 | 4 | : TargetRegion.BranchBlock; |
659 | 4 | |
660 | 4 | MachineBasicBlock::iterator Target = |
661 | 4 | SourceRegion.MustMoveDown |
662 | 4 | ? SourceRegion.BranchTargetBlock->getFirstNonPHI()0 |
663 | 4 | : TargetRegion.BranchBlock->getFirstTerminator(); |
664 | 4 | |
665 | 4 | Source->splice(Target, SourceRegion.BranchBlock, firstInstr, lastInstr); |
666 | 4 | |
667 | 4 | // Once PHI and instructions have been moved we need to clean up the |
668 | 4 | // control flow. |
669 | 4 | |
670 | 4 | // Remove SourceRegion.FallThroughBlock before transferring successors of |
671 | 4 | // SourceRegion.BranchBlock to TargetRegion.BranchBlock. |
672 | 4 | SourceRegion.BranchBlock->removeSuccessor(SourceRegion.FallThroughBlock); |
673 | 4 | TargetRegion.BranchBlock->transferSuccessorsAndUpdatePHIs( |
674 | 4 | SourceRegion.BranchBlock); |
675 | 4 | // Update branch in TargetRegion.BranchBlock to jump to |
676 | 4 | // SourceRegion.BranchTargetBlock |
677 | 4 | // In this case, TargetRegion.BranchTargetBlock == SourceRegion.BranchBlock. |
678 | 4 | TargetRegion.BranchBlock->ReplaceUsesOfBlockWith( |
679 | 4 | SourceRegion.BranchBlock, SourceRegion.BranchTargetBlock); |
680 | 4 | // Remove the branch statement(s) in SourceRegion.BranchBlock |
681 | 4 | MachineBasicBlock::iterator I = |
682 | 4 | SourceRegion.BranchBlock->terminators().begin(); |
683 | 8 | while (I != SourceRegion.BranchBlock->terminators().end()) { |
684 | 4 | MachineInstr &CurrInst = *I; |
685 | 4 | ++I; |
686 | 4 | if (CurrInst.isBranch()) |
687 | 4 | CurrInst.eraseFromParent(); |
688 | 4 | } |
689 | 4 | |
690 | 4 | // Fall-through block should be empty since this is part of the condition |
691 | 4 | // to coalesce the branches. |
692 | 4 | assert(TargetRegion.FallThroughBlock->empty() && |
693 | 4 | "FallThroughBlocks should be empty!"); |
694 | 4 | |
695 | 4 | // Transfer successor information and move PHIs down to the |
696 | 4 | // branch-taken block. |
697 | 4 | TargetRegion.FallThroughBlock->transferSuccessorsAndUpdatePHIs( |
698 | 4 | SourceRegion.FallThroughBlock); |
699 | 4 | TargetRegion.FallThroughBlock->removeSuccessor(SourceRegion.BranchBlock); |
700 | 4 | |
701 | 4 | // Remove the blocks from the function. |
702 | 4 | assert(SourceRegion.BranchBlock->empty() && |
703 | 4 | "Expecting branch block to be empty!"); |
704 | 4 | SourceRegion.BranchBlock->eraseFromParent(); |
705 | 4 | |
706 | 4 | assert(SourceRegion.FallThroughBlock->empty() && |
707 | 4 | "Expecting fall-through block to be empty!\n"); |
708 | 4 | SourceRegion.FallThroughBlock->eraseFromParent(); |
709 | 4 | |
710 | 4 | NumBlocksCoalesced++; |
711 | 4 | return true; |
712 | 4 | } |
713 | | |
714 | 2 | bool PPCBranchCoalescing::runOnMachineFunction(MachineFunction &MF) { |
715 | 2 | |
716 | 2 | if (skipFunction(MF.getFunction()) || MF.empty()) |
717 | 0 | return false; |
718 | 2 | |
719 | 2 | bool didSomething = false; |
720 | 2 | |
721 | 2 | LLVM_DEBUG(dbgs() << "******** Branch Coalescing ********\n"); |
722 | 2 | initialize(MF); |
723 | 2 | |
724 | 2 | LLVM_DEBUG(dbgs() << "Function: "; MF.dump(); dbgs() << "\n"); |
725 | 2 | |
726 | 2 | CoalescingCandidateInfo Cand1, Cand2; |
727 | 2 | // Walk over blocks and find candidates to merge |
728 | 2 | // Continue trying to merge with the first candidate found, as long as merging |
729 | 2 | // is successfull. |
730 | 6 | for (MachineBasicBlock &MBB : MF) { |
731 | 6 | bool MergedCandidates = false; |
732 | 10 | do { |
733 | 10 | MergedCandidates = false; |
734 | 10 | Cand1.clear(); |
735 | 10 | Cand2.clear(); |
736 | 10 | |
737 | 10 | Cand1.BranchBlock = &MBB; |
738 | 10 | |
739 | 10 | // If unable to coalesce the branch, then continue to next block |
740 | 10 | if (!canCoalesceBranch(Cand1)) |
741 | 4 | break; |
742 | 6 | |
743 | 6 | Cand2.BranchBlock = Cand1.BranchTargetBlock; |
744 | 6 | if (!canCoalesceBranch(Cand2)) |
745 | 2 | break; |
746 | 4 | |
747 | 4 | // Sanity check |
748 | 4 | // The branch-taken block of the second candidate should post-dominate the |
749 | 4 | // first candidate |
750 | 4 | assert(MPDT->dominates(Cand2.BranchTargetBlock, Cand1.BranchBlock) && |
751 | 4 | "Branch-taken block should post-dominate first candidate"); |
752 | 4 | |
753 | 4 | if (!identicalOperands(Cand1.Cond, Cand2.Cond)) { |
754 | 0 | LLVM_DEBUG(dbgs() << "Blocks " << Cand1.BranchBlock->getNumber() |
755 | 0 | << " and " << Cand2.BranchBlock->getNumber() |
756 | 0 | << " have different branches\n"); |
757 | 0 | break; |
758 | 0 | } |
759 | 4 | if (!canMerge(Cand2, Cand1)) { |
760 | 0 | LLVM_DEBUG(dbgs() << "Cannot merge blocks " |
761 | 0 | << Cand1.BranchBlock->getNumber() << " and " |
762 | 0 | << Cand2.BranchBlock->getNumber() << "\n"); |
763 | 0 | NumBlocksNotCoalesced++; |
764 | 0 | continue; |
765 | 0 | } |
766 | 4 | LLVM_DEBUG(dbgs() << "Merging blocks " << Cand1.BranchBlock->getNumber() |
767 | 4 | << " and " << Cand1.BranchTargetBlock->getNumber() |
768 | 4 | << "\n"); |
769 | 4 | MergedCandidates = mergeCandidates(Cand2, Cand1); |
770 | 4 | if (MergedCandidates) |
771 | 4 | didSomething = true; |
772 | 4 | |
773 | 4 | LLVM_DEBUG(dbgs() << "Function after merging: "; MF.dump(); |
774 | 4 | dbgs() << "\n"); |
775 | 4 | } while (MergedCandidates); |
776 | 6 | } |
777 | 2 | |
778 | | #ifndef NDEBUG |
779 | | // Verify MF is still valid after branch coalescing |
780 | | if (didSomething) |
781 | | MF.verify(nullptr, "Error in code produced by branch coalescing"); |
782 | | #endif // NDEBUG |
783 | | |
784 | 2 | LLVM_DEBUG(dbgs() << "Finished Branch Coalescing\n"); |
785 | 2 | return didSomething; |
786 | 2 | } |