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/Statistic.h"
17#include "llvm/CodeGen/MachineDominators.h"
18#include "llvm/CodeGen/MachineFunctionPass.h"
19#include "llvm/CodeGen/MachinePostDominators.h"
20#include "llvm/CodeGen/MachineRegisterInfo.h"
21#include "llvm/CodeGen/Passes.h"
22#include "llvm/CodeGen/TargetFrameLowering.h"
23#include "llvm/CodeGen/TargetInstrInfo.h"
24#include "llvm/CodeGen/TargetSubtargetInfo.h"
25#include "llvm/InitializePasses.h"
26#include "llvm/Support/Debug.h"
27
28using namespace llvm;
29
30#define DEBUG_TYPE "ppc-branch-coalescing"
31
32STATISTIC(NumBlocksCoalesced, "Number of blocks coalesced");
33STATISTIC(NumPHINotMoved, "Number of PHI Nodes that cannot be merged");
34STATISTIC(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
133namespace {
134
135class 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
160public:
161 static char ID;
162
163 PPCBranchCoalescing() : MachineFunctionPass(ID) {
164 initializePPCBranchCoalescingPass(*PassRegistry::getPassRegistry());
165 }
166
167 void getAnalysisUsage(AnalysisUsage &AU) const override {
168 AU.addRequired<MachineDominatorTreeWrapperPass>();
169 AU.addRequired<MachinePostDominatorTreeWrapperPass>();
170 MachineFunctionPass::getAnalysisUsage(AU);
171 }
172
173 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
189char PPCBranchCoalescing::ID = 0;
190/// createPPCBranchCoalescingPass - returns an instance of the Branch Coalescing
191/// Pass
192FunctionPass *llvm::createPPCBranchCoalescingPass() {
193 return new PPCBranchCoalescing();
194}
195
196INITIALIZE_PASS_BEGIN(PPCBranchCoalescing, DEBUG_TYPE,
197 "Branch Coalescing", false, false)
198INITIALIZE_PASS_DEPENDENCY(MachineDominatorTreeWrapperPass)
199INITIALIZE_PASS_DEPENDENCY(MachinePostDominatorTreeWrapperPass)
200INITIALIZE_PASS_END(PPCBranchCoalescing, DEBUG_TYPE, "Branch Coalescing",
201 false, false)
202
203PPCBranchCoalescing::CoalescingCandidateInfo::CoalescingCandidateInfo()
204 : BranchBlock(nullptr), BranchTargetBlock(nullptr),
205 FallThroughBlock(nullptr), MustMoveDown(false), MustMoveUp(false) {}
206
207void PPCBranchCoalescing::CoalescingCandidateInfo::clear() {
208 BranchBlock = nullptr;
209 BranchTargetBlock = nullptr;
210 FallThroughBlock = nullptr;
211 Cond.clear();
212 MustMoveDown = false;
213 MustMoveUp = false;
214}
215
216void PPCBranchCoalescing::initialize(MachineFunction &MF) {
217 MDT = &getAnalysis<MachineDominatorTreeWrapperPass>().getDomTree();
218 MPDT = &getAnalysis<MachinePostDominatorTreeWrapperPass>().getPostDomTree();
219 TII = MF.getSubtarget().getInstrInfo();
220 MRI = &MF.getRegInfo();
221}
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///
233bool PPCBranchCoalescing::canCoalesceBranch(CoalescingCandidateInfo &Cand) {
234 LLVM_DEBUG(dbgs() << "Determine if branch block "
235 << Cand.BranchBlock->getNumber() << " can be coalesced:");
236 MachineBasicBlock *FalseMBB = nullptr;
237
238 if (TII->analyzeBranch(MBB&: *Cand.BranchBlock, TBB&: Cand.BranchTargetBlock, FBB&: FalseMBB,
239 Cond&: Cand.Cond)) {
240 LLVM_DEBUG(dbgs() << "TII unable to Analyze Branch - skip\n");
241 return false;
242 }
243
244 for (auto &I : Cand.BranchBlock->terminators()) {
245 LLVM_DEBUG(dbgs() << "Looking at terminator : " << I << "\n");
246 if (!I.isBranch())
247 continue;
248
249 // The analyzeBranch method does not include any implicit operands.
250 // This is not an issue on PPC but must be handled on other targets.
251 // For this pass to be made target-independent, the analyzeBranch API
252 // need to be updated to support implicit operands and there would
253 // need to be a way to verify that any implicit operands would not be
254 // clobbered by merging blocks. This would include identifying the
255 // implicit operands as well as the basic block they are defined in.
256 // This could be done by changing the analyzeBranch API to have it also
257 // record and return the implicit operands and the blocks where they are
258 // defined. Alternatively, the BranchCoalescing code would need to be
259 // extended to identify the implicit operands. The analysis in canMerge
260 // must then be extended to prove that none of the implicit operands are
261 // changed in the blocks that are combined during coalescing.
262 if (I.getNumOperands() != I.getNumExplicitOperands()) {
263 LLVM_DEBUG(dbgs() << "Terminator contains implicit operands - skip : "
264 << I << "\n");
265 return false;
266 }
267 }
268
269 if (Cand.BranchBlock->isEHPad() || Cand.BranchBlock->hasEHPadSuccessor()) {
270 LLVM_DEBUG(dbgs() << "EH Pad - skip\n");
271 return false;
272 }
273
274 if (Cand.BranchBlock->mayHaveInlineAsmBr()) {
275 LLVM_DEBUG(dbgs() << "Inline Asm Br - skip\n");
276 return false;
277 }
278
279 // For now only consider triangles (i.e, BranchTargetBlock is set,
280 // FalseMBB is null, and BranchTargetBlock is a successor to BranchBlock)
281 if (!Cand.BranchTargetBlock || FalseMBB ||
282 !Cand.BranchBlock->isSuccessor(MBB: Cand.BranchTargetBlock)) {
283 LLVM_DEBUG(dbgs() << "Does not form a triangle - skip\n");
284 return false;
285 }
286
287 // Ensure there are only two successors
288 if (Cand.BranchBlock->succ_size() != 2) {
289 LLVM_DEBUG(dbgs() << "Does not have 2 successors - skip\n");
290 return false;
291 }
292
293 // The block must be able to fall through.
294 assert(Cand.BranchBlock->canFallThrough() &&
295 "Expecting the block to fall through!");
296
297 // We have already ensured there are exactly two successors to
298 // BranchBlock and that BranchTargetBlock is a successor to BranchBlock.
299 // Ensure the single fall though block is empty.
300 MachineBasicBlock *Succ =
301 (*Cand.BranchBlock->succ_begin() == Cand.BranchTargetBlock)
302 ? *Cand.BranchBlock->succ_rbegin()
303 : *Cand.BranchBlock->succ_begin();
304
305 assert(Succ && "Expecting a valid fall-through block\n");
306
307 if (!Succ->empty()) {
308 LLVM_DEBUG(dbgs() << "Fall-through block contains code -- skip\n");
309 return false;
310 }
311
312 if (!Succ->isSuccessor(MBB: Cand.BranchTargetBlock)) {
313 LLVM_DEBUG(
314 dbgs()
315 << "Successor of fall through block is not branch taken block\n");
316 return false;
317 }
318
319 Cand.FallThroughBlock = Succ;
320 LLVM_DEBUG(dbgs() << "Valid Candidate\n");
321 return true;
322}
323
324///
325/// Determine if the two operand lists are identical
326///
327/// \param[in] OpList1 operand list
328/// \param[in] OpList2 operand list
329/// \return true if and only if the operands lists are identical
330///
331bool PPCBranchCoalescing::identicalOperands(
332 ArrayRef<MachineOperand> OpList1, ArrayRef<MachineOperand> OpList2) const {
333
334 if (OpList1.size() != OpList2.size()) {
335 LLVM_DEBUG(dbgs() << "Operand list is different size\n");
336 return false;
337 }
338
339 for (unsigned i = 0; i < OpList1.size(); ++i) {
340 const MachineOperand &Op1 = OpList1[i];
341 const MachineOperand &Op2 = OpList2[i];
342
343 LLVM_DEBUG(dbgs() << "Op1: " << Op1 << "\n"
344 << "Op2: " << Op2 << "\n");
345
346 if (Op1.isIdenticalTo(Other: Op2)) {
347 // filter out instructions with physical-register uses
348 if (Op1.isReg() && Op1.getReg().isPhysical()
349 // If the physical register is constant then we can assume the value
350 // has not changed between uses.
351 && !(Op1.isUse() && MRI->isConstantPhysReg(PhysReg: Op1.getReg()))) {
352 LLVM_DEBUG(dbgs() << "The operands are not provably identical.\n");
353 return false;
354 }
355 LLVM_DEBUG(dbgs() << "Op1 and Op2 are identical!\n");
356 continue;
357 }
358
359 // If the operands are not identical, but are registers, check to see if the
360 // definition of the register produces the same value. If they produce the
361 // same value, consider them to be identical.
362 if (Op1.isReg() && Op2.isReg() && Op1.getReg().isVirtual() &&
363 Op2.getReg().isVirtual()) {
364 MachineInstr *Op1Def = MRI->getVRegDef(Reg: Op1.getReg());
365 MachineInstr *Op2Def = MRI->getVRegDef(Reg: Op2.getReg());
366 if (TII->produceSameValue(MI0: *Op1Def, MI1: *Op2Def, MRI)) {
367 LLVM_DEBUG(dbgs() << "Op1Def: " << *Op1Def << " and " << *Op2Def
368 << " produce the same value!\n");
369 } else {
370 LLVM_DEBUG(dbgs() << "Operands produce different values\n");
371 return false;
372 }
373 } else {
374 LLVM_DEBUG(dbgs() << "The operands are not provably identical.\n");
375 return false;
376 }
377 }
378
379 return true;
380}
381
382///
383/// Moves ALL PHI instructions in SourceMBB to beginning of TargetMBB
384/// and update them to refer to the new block. PHI node ordering
385/// cannot be assumed so it does not matter where the PHI instructions
386/// are moved to in TargetMBB.
387///
388/// \param[in] SourceMBB block to move PHI instructions from
389/// \param[in] TargetMBB block to move PHI instructions to
390///
391void PPCBranchCoalescing::moveAndUpdatePHIs(MachineBasicBlock *SourceMBB,
392 MachineBasicBlock *TargetMBB) {
393
394 MachineBasicBlock::iterator MI = SourceMBB->begin();
395 MachineBasicBlock::iterator ME = SourceMBB->getFirstNonPHI();
396
397 if (MI == ME) {
398 LLVM_DEBUG(dbgs() << "SourceMBB contains no PHI instructions.\n");
399 return;
400 }
401
402 // Update all PHI instructions in SourceMBB and move to top of TargetMBB
403 for (MachineBasicBlock::iterator Iter = MI; Iter != ME; Iter++) {
404 MachineInstr &PHIInst = *Iter;
405 for (unsigned i = 2, e = PHIInst.getNumOperands() + 1; i != e; i += 2) {
406 MachineOperand &MO = PHIInst.getOperand(i);
407 if (MO.getMBB() == SourceMBB)
408 MO.setMBB(TargetMBB);
409 }
410 }
411 TargetMBB->splice(Where: TargetMBB->begin(), Other: SourceMBB, From: MI, To: ME);
412}
413
414///
415/// This function checks if MI can be moved to the beginning of the TargetMBB
416/// following PHI instructions. A MI instruction can be moved to beginning of
417/// the TargetMBB if there are no uses of it within the TargetMBB PHI nodes.
418///
419/// \param[in] MI the machine instruction to move.
420/// \param[in] TargetMBB the machine basic block to move to
421/// \return true if it is safe to move MI to beginning of TargetMBB,
422/// false otherwise.
423///
424bool PPCBranchCoalescing::canMoveToBeginning(const MachineInstr &MI,
425 const MachineBasicBlock &TargetMBB
426 ) const {
427
428 LLVM_DEBUG(dbgs() << "Checking if " << MI << " can move to beginning of "
429 << TargetMBB.getNumber() << "\n");
430
431 for (auto &Def : MI.defs()) { // Looking at Def
432 for (auto &Use : MRI->use_instructions(Reg: Def.getReg())) {
433 if (Use.isPHI() && Use.getParent() == &TargetMBB) {
434 LLVM_DEBUG(dbgs() << " *** used in a PHI -- cannot move ***\n");
435 return false;
436 }
437 }
438 }
439
440 LLVM_DEBUG(dbgs() << " Safe to move to the beginning.\n");
441 return true;
442}
443
444///
445/// This function checks if MI can be moved to the end of the TargetMBB,
446/// immediately before the first terminator. A MI instruction can be moved
447/// to then end of the TargetMBB if no PHI node defines what MI uses within
448/// it's own MBB.
449///
450/// \param[in] MI the machine instruction to move.
451/// \param[in] TargetMBB the machine basic block to move to
452/// \return true if it is safe to move MI to end of TargetMBB,
453/// false otherwise.
454///
455bool PPCBranchCoalescing::canMoveToEnd(const MachineInstr &MI,
456 const MachineBasicBlock &TargetMBB
457 ) const {
458
459 LLVM_DEBUG(dbgs() << "Checking if " << MI << " can move to end of "
460 << TargetMBB.getNumber() << "\n");
461
462 for (auto &Use : MI.uses()) {
463 if (Use.isReg() && Use.getReg().isVirtual()) {
464 MachineInstr *DefInst = MRI->getVRegDef(Reg: Use.getReg());
465 if (DefInst->isPHI() && DefInst->getParent() == MI.getParent()) {
466 LLVM_DEBUG(dbgs() << " *** Cannot move this instruction ***\n");
467 return false;
468 } else {
469 LLVM_DEBUG(
470 dbgs() << " *** def is in another block -- safe to move!\n");
471 }
472 }
473 }
474
475 LLVM_DEBUG(dbgs() << " Safe to move to the end.\n");
476 return true;
477}
478
479///
480/// This method checks to ensure the two coalescing candidates follows the
481/// expected pattern required for coalescing.
482///
483/// \param[in] SourceRegion The candidate to move statements from
484/// \param[in] TargetRegion The candidate to move statements to
485/// \return true if all instructions in SourceRegion.BranchBlock can be merged
486/// into a block in TargetRegion; false otherwise.
487///
488bool PPCBranchCoalescing::validateCandidates(
489 CoalescingCandidateInfo &SourceRegion,
490 CoalescingCandidateInfo &TargetRegion) const {
491
492 if (TargetRegion.BranchTargetBlock != SourceRegion.BranchBlock)
493 llvm_unreachable("Expecting SourceRegion to immediately follow TargetRegion");
494 else if (!MDT->dominates(A: TargetRegion.BranchBlock, B: SourceRegion.BranchBlock))
495 llvm_unreachable("Expecting TargetRegion to dominate SourceRegion");
496 else if (!MPDT->dominates(A: SourceRegion.BranchBlock, B: TargetRegion.BranchBlock))
497 llvm_unreachable("Expecting SourceRegion to post-dominate TargetRegion");
498 else if (!TargetRegion.FallThroughBlock->empty() ||
499 !SourceRegion.FallThroughBlock->empty())
500 llvm_unreachable("Expecting fall-through blocks to be empty");
501
502 return true;
503}
504
505///
506/// This method determines whether the two coalescing candidates can be merged.
507/// In order to be merged, all instructions must be able to
508/// 1. Move to the beginning of the SourceRegion.BranchTargetBlock;
509/// 2. Move to the end of the TargetRegion.BranchBlock.
510/// Merging involves moving the instructions in the
511/// TargetRegion.BranchTargetBlock (also SourceRegion.BranchBlock).
512///
513/// This function first try to move instructions from the
514/// TargetRegion.BranchTargetBlock down, to the beginning of the
515/// SourceRegion.BranchTargetBlock. This is not possible if any register defined
516/// in TargetRegion.BranchTargetBlock is used in a PHI node in the
517/// SourceRegion.BranchTargetBlock. In this case, check whether the statement
518/// can be moved up, to the end of the TargetRegion.BranchBlock (immediately
519/// before the branch statement). If it cannot move, then these blocks cannot
520/// be merged.
521///
522/// Note that there is no analysis for moving instructions past the fall-through
523/// blocks because they are confirmed to be empty. An assert is thrown if they
524/// are not.
525///
526/// \param[in] SourceRegion The candidate to move statements from
527/// \param[in] TargetRegion The candidate to move statements to
528/// \return true if all instructions in SourceRegion.BranchBlock can be merged
529/// into a block in TargetRegion, false otherwise.
530///
531bool PPCBranchCoalescing::canMerge(CoalescingCandidateInfo &SourceRegion,
532 CoalescingCandidateInfo &TargetRegion) const {
533 if (!validateCandidates(SourceRegion, TargetRegion))
534 return false;
535
536 // Walk through PHI nodes first and see if they force the merge into the
537 // SourceRegion.BranchTargetBlock.
538 for (MachineBasicBlock::iterator
539 I = SourceRegion.BranchBlock->instr_begin(),
540 E = SourceRegion.BranchBlock->getFirstNonPHI();
541 I != E; ++I) {
542 for (auto &Def : I->defs())
543 for (auto &Use : MRI->use_instructions(Reg: Def.getReg())) {
544 if (Use.isPHI() && Use.getParent() == SourceRegion.BranchTargetBlock) {
545 LLVM_DEBUG(dbgs()
546 << "PHI " << *I
547 << " defines register used in another "
548 "PHI within branch target block -- can't merge\n");
549 NumPHINotMoved++;
550 return false;
551 }
552 if (Use.getParent() == SourceRegion.BranchBlock) {
553 LLVM_DEBUG(dbgs() << "PHI " << *I
554 << " defines register used in this "
555 "block -- all must move down\n");
556 SourceRegion.MustMoveDown = true;
557 }
558 }
559 }
560
561 // Walk through the MI to see if they should be merged into
562 // TargetRegion.BranchBlock (up) or SourceRegion.BranchTargetBlock (down)
563 for (MachineBasicBlock::iterator
564 I = SourceRegion.BranchBlock->getFirstNonPHI(),
565 E = SourceRegion.BranchBlock->end();
566 I != E; ++I) {
567 if (!canMoveToBeginning(MI: *I, TargetMBB: *SourceRegion.BranchTargetBlock)) {
568 LLVM_DEBUG(dbgs() << "Instruction " << *I
569 << " cannot move down - must move up!\n");
570 SourceRegion.MustMoveUp = true;
571 }
572 if (!canMoveToEnd(MI: *I, TargetMBB: *TargetRegion.BranchBlock)) {
573 LLVM_DEBUG(dbgs() << "Instruction " << *I
574 << " cannot move up - must move down!\n");
575 SourceRegion.MustMoveDown = true;
576 }
577 }
578
579 return (SourceRegion.MustMoveUp && SourceRegion.MustMoveDown) ? false : true;
580}
581
582/// Merge the instructions from SourceRegion.BranchBlock,
583/// SourceRegion.BranchTargetBlock, and SourceRegion.FallThroughBlock into
584/// TargetRegion.BranchBlock, TargetRegion.BranchTargetBlock and
585/// TargetRegion.FallThroughBlock respectively.
586///
587/// The successors for blocks in TargetRegion will be updated to use the
588/// successors from blocks in SourceRegion. Finally, the blocks in SourceRegion
589/// will be removed from the function.
590///
591/// A region consists of a BranchBlock, a FallThroughBlock, and a
592/// BranchTargetBlock. Branch coalesce works on patterns where the
593/// TargetRegion's BranchTargetBlock must also be the SourceRegions's
594/// BranchBlock.
595///
596/// Before mergeCandidates:
597///
598/// +---------------------------+
599/// | TargetRegion.BranchBlock |
600/// +---------------------------+
601/// / |
602/// / +--------------------------------+
603/// | | TargetRegion.FallThroughBlock |
604/// \ +--------------------------------+
605/// \ |
606/// +----------------------------------+
607/// | TargetRegion.BranchTargetBlock |
608/// | SourceRegion.BranchBlock |
609/// +----------------------------------+
610/// / |
611/// / +--------------------------------+
612/// | | SourceRegion.FallThroughBlock |
613/// \ +--------------------------------+
614/// \ |
615/// +----------------------------------+
616/// | SourceRegion.BranchTargetBlock |
617/// +----------------------------------+
618///
619/// After mergeCandidates:
620///
621/// +-----------------------------+
622/// | TargetRegion.BranchBlock |
623/// | SourceRegion.BranchBlock |
624/// +-----------------------------+
625/// / |
626/// / +---------------------------------+
627/// | | TargetRegion.FallThroughBlock |
628/// | | SourceRegion.FallThroughBlock |
629/// \ +---------------------------------+
630/// \ |
631/// +----------------------------------+
632/// | SourceRegion.BranchTargetBlock |
633/// +----------------------------------+
634///
635/// \param[in] SourceRegion The candidate to move blocks from
636/// \param[in] TargetRegion The candidate to move blocks to
637///
638bool PPCBranchCoalescing::mergeCandidates(CoalescingCandidateInfo &SourceRegion,
639 CoalescingCandidateInfo &TargetRegion) {
640
641 if (SourceRegion.MustMoveUp && SourceRegion.MustMoveDown) {
642 llvm_unreachable("Cannot have both MustMoveDown and MustMoveUp set!");
643 return false;
644 }
645
646 if (!validateCandidates(SourceRegion, TargetRegion))
647 return false;
648
649 // Start the merging process by first handling the BranchBlock.
650 // Move any PHIs in SourceRegion.BranchBlock down to the branch-taken block
651 moveAndUpdatePHIs(SourceMBB: SourceRegion.BranchBlock, TargetMBB: SourceRegion.BranchTargetBlock);
652
653 // Move remaining instructions in SourceRegion.BranchBlock into
654 // TargetRegion.BranchBlock
655 MachineBasicBlock::iterator firstInstr =
656 SourceRegion.BranchBlock->getFirstNonPHI();
657 MachineBasicBlock::iterator lastInstr =
658 SourceRegion.BranchBlock->getFirstTerminator();
659
660 MachineBasicBlock *Source = SourceRegion.MustMoveDown
661 ? SourceRegion.BranchTargetBlock
662 : TargetRegion.BranchBlock;
663
664 MachineBasicBlock::iterator Target =
665 SourceRegion.MustMoveDown
666 ? SourceRegion.BranchTargetBlock->getFirstNonPHI()
667 : TargetRegion.BranchBlock->getFirstTerminator();
668
669 Source->splice(Where: Target, Other: SourceRegion.BranchBlock, From: firstInstr, To: lastInstr);
670
671 // Once PHI and instructions have been moved we need to clean up the
672 // control flow.
673
674 // Remove SourceRegion.FallThroughBlock before transferring successors of
675 // SourceRegion.BranchBlock to TargetRegion.BranchBlock.
676 SourceRegion.BranchBlock->removeSuccessor(Succ: SourceRegion.FallThroughBlock);
677 TargetRegion.BranchBlock->transferSuccessorsAndUpdatePHIs(
678 FromMBB: SourceRegion.BranchBlock);
679 // Update branch in TargetRegion.BranchBlock to jump to
680 // SourceRegion.BranchTargetBlock
681 // In this case, TargetRegion.BranchTargetBlock == SourceRegion.BranchBlock.
682 TargetRegion.BranchBlock->ReplaceUsesOfBlockWith(
683 Old: SourceRegion.BranchBlock, New: SourceRegion.BranchTargetBlock);
684 // Remove the branch statement(s) in SourceRegion.BranchBlock
685 MachineBasicBlock::iterator I =
686 SourceRegion.BranchBlock->terminators().begin();
687 while (I != SourceRegion.BranchBlock->terminators().end()) {
688 MachineInstr &CurrInst = *I;
689 ++I;
690 if (CurrInst.isBranch())
691 CurrInst.eraseFromParent();
692 }
693
694 // Fall-through block should be empty since this is part of the condition
695 // to coalesce the branches.
696 assert(TargetRegion.FallThroughBlock->empty() &&
697 "FallThroughBlocks should be empty!");
698
699 // Transfer successor information and move PHIs down to the
700 // branch-taken block.
701 TargetRegion.FallThroughBlock->transferSuccessorsAndUpdatePHIs(
702 FromMBB: SourceRegion.FallThroughBlock);
703 TargetRegion.FallThroughBlock->removeSuccessor(Succ: SourceRegion.BranchBlock);
704 TargetRegion.FallThroughBlock->normalizeSuccProbs();
705
706 // Remove the blocks from the function.
707 assert(SourceRegion.BranchBlock->empty() &&
708 "Expecting branch block to be empty!");
709 SourceRegion.BranchBlock->eraseFromParent();
710
711 assert(SourceRegion.FallThroughBlock->empty() &&
712 "Expecting fall-through block to be empty!\n");
713 SourceRegion.FallThroughBlock->eraseFromParent();
714
715 NumBlocksCoalesced++;
716 return true;
717}
718
719bool PPCBranchCoalescing::runOnMachineFunction(MachineFunction &MF) {
720
721 if (skipFunction(F: MF.getFunction()) || MF.empty())
722 return false;
723
724 bool didSomething = false;
725
726 LLVM_DEBUG(dbgs() << "******** Branch Coalescing ********\n");
727 initialize(MF);
728
729 LLVM_DEBUG(dbgs() << "Function: "; MF.dump(); dbgs() << "\n");
730
731 CoalescingCandidateInfo Cand1, Cand2;
732 // Walk over blocks and find candidates to merge
733 // Continue trying to merge with the first candidate found, as long as merging
734 // is successfull.
735 for (MachineBasicBlock &MBB : MF) {
736 bool MergedCandidates = false;
737 do {
738 MergedCandidates = false;
739 Cand1.clear();
740 Cand2.clear();
741
742 Cand1.BranchBlock = &MBB;
743
744 // If unable to coalesce the branch, then continue to next block
745 if (!canCoalesceBranch(Cand&: Cand1))
746 break;
747
748 Cand2.BranchBlock = Cand1.BranchTargetBlock;
749 if (!canCoalesceBranch(Cand&: Cand2))
750 break;
751
752 // The branch-taken block of the second candidate should post-dominate the
753 // first candidate.
754 assert(MPDT->dominates(Cand2.BranchTargetBlock, Cand1.BranchBlock) &&
755 "Branch-taken block should post-dominate first candidate");
756
757 if (!identicalOperands(OpList1: Cand1.Cond, OpList2: Cand2.Cond)) {
758 LLVM_DEBUG(dbgs() << "Blocks " << Cand1.BranchBlock->getNumber()
759 << " and " << Cand2.BranchBlock->getNumber()
760 << " have different branches\n");
761 break;
762 }
763 if (!canMerge(SourceRegion&: Cand2, TargetRegion&: Cand1)) {
764 LLVM_DEBUG(dbgs() << "Cannot merge blocks "
765 << Cand1.BranchBlock->getNumber() << " and "
766 << Cand2.BranchBlock->getNumber() << "\n");
767 NumBlocksNotCoalesced++;
768 continue;
769 }
770 LLVM_DEBUG(dbgs() << "Merging blocks " << Cand1.BranchBlock->getNumber()
771 << " and " << Cand1.BranchTargetBlock->getNumber()
772 << "\n");
773 MergedCandidates = mergeCandidates(SourceRegion&: Cand2, TargetRegion&: Cand1);
774 if (MergedCandidates)
775 didSomething = true;
776
777 LLVM_DEBUG(dbgs() << "Function after merging: "; MF.dump();
778 dbgs() << "\n");
779 } while (MergedCandidates);
780 }
781
782#ifndef NDEBUG
783 // Verify MF is still valid after branch coalescing
784 if (didSomething)
785 MF.verify(nullptr, "Error in code produced by branch coalescing");
786#endif // NDEBUG
787
788 LLVM_DEBUG(dbgs() << "Finished Branch Coalescing\n");
789 return didSomething;
790}
791