LLVM 20.0.0git
PPCBranchCoalescing.cpp
Go to the documentation of this file.
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"
21#include "llvm/CodeGen/Passes.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
141 bool MustMoveDown;
142 bool MustMoveUp;
143
144 CoalescingCandidateInfo();
145 void clear();
146 };
147
150 const TargetInstrInfo *TII;
152
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) {
165 }
166
167 void getAnalysisUsage(AnalysisUsage &AU) const override {
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
193 return new PPCBranchCoalescing();
194}
195
197 "Branch Coalescing", false, false)
200INITIALIZE_PASS_END(PPCBranchCoalescing, DEBUG_TYPE, "Branch Coalescing",
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();
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(*Cand.BranchBlock, Cand.BranchTargetBlock, FalseMBB,
239 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(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(Cand.BranchTargetBlock)) {
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(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(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(Op1.getReg());
365 MachineInstr *Op2Def = MRI->getVRegDef(Op2.getReg());
366 if (TII->produceSameValue(*Op1Def, *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();
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(TargetMBB->begin(), SourceMBB, MI, 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(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(Use.getReg());
465 if (DefInst->isPHI() && DefInst->getParent() == MI.getParent()) {
466 LLVM_DEBUG(dbgs() << " *** Cannot move this instruction ***\n");
467 return false;
468 } else {
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(TargetRegion.BranchBlock, SourceRegion.BranchBlock))
495 llvm_unreachable("Expecting TargetRegion to dominate SourceRegion");
496 else if (!MPDT->dominates(SourceRegion.BranchBlock, 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.
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(Def.getReg())) {
544 if (Use.isPHI() && Use.getParent() == SourceRegion.BranchTargetBlock) {
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)
564 I = SourceRegion.BranchBlock->getFirstNonPHI(),
565 E = SourceRegion.BranchBlock->end();
566 I != E; ++I) {
567 if (!canMoveToBeginning(*I, *SourceRegion.BranchTargetBlock)) {
568 LLVM_DEBUG(dbgs() << "Instruction " << *I
569 << " cannot move down - must move up!\n");
570 SourceRegion.MustMoveUp = true;
571 }
572 if (!canMoveToEnd(*I, *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(SourceRegion.BranchBlock, SourceRegion.BranchTargetBlock);
652
653 // Move remaining instructions in SourceRegion.BranchBlock into
654 // TargetRegion.BranchBlock
655 MachineBasicBlock::iterator firstInstr =
656 SourceRegion.BranchBlock->getFirstNonPHI();
658 SourceRegion.BranchBlock->getFirstTerminator();
659
660 MachineBasicBlock *Source = SourceRegion.MustMoveDown
661 ? SourceRegion.BranchTargetBlock
662 : TargetRegion.BranchBlock;
663
665 SourceRegion.MustMoveDown
666 ? SourceRegion.BranchTargetBlock->getFirstNonPHI()
667 : TargetRegion.BranchBlock->getFirstTerminator();
668
669 Source->splice(Target, SourceRegion.BranchBlock, firstInstr, 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(SourceRegion.FallThroughBlock);
677 TargetRegion.BranchBlock->transferSuccessorsAndUpdatePHIs(
678 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 SourceRegion.BranchBlock, SourceRegion.BranchTargetBlock);
684 // Remove the branch statement(s) in SourceRegion.BranchBlock
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 SourceRegion.FallThroughBlock);
703 TargetRegion.FallThroughBlock->removeSuccessor(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(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(Cand1))
746 break;
747
748 Cand2.BranchBlock = Cand1.BranchTargetBlock;
749 if (!canCoalesceBranch(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(Cand1.Cond, 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(Cand2, 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(Cand2, 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}
unsigned const MachineRegisterInfo * MRI
MachineBasicBlock & MBB
static void clear(coro::Shape &Shape)
Definition: Coroutines.cpp:148
#define LLVM_DEBUG(X)
Definition: Debug.h:101
const HexagonInstrInfo * TII
IRTranslator LLVM IR MI
#define F(x, y, z)
Definition: MD5.cpp:55
#define I(x, y, z)
Definition: MD5.cpp:58
Branch Coalescing
Branch false
#define DEBUG_TYPE
#define INITIALIZE_PASS_DEPENDENCY(depName)
Definition: PassSupport.h:55
#define INITIALIZE_PASS_END(passName, arg, name, cfg, analysis)
Definition: PassSupport.h:57
#define INITIALIZE_PASS_BEGIN(passName, arg, name, cfg, analysis)
Definition: PassSupport.h:52
const SmallVectorImpl< MachineOperand > & Cond
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
This file defines the 'Statistic' class, which is designed to be an easy way to expose various metric...
#define STATISTIC(VARNAME, DESC)
Definition: Statistic.h:166
static void initialize(TargetLibraryInfoImpl &TLI, const Triple &T, ArrayRef< StringLiteral > StandardNames)
Initialize the set of available library functions based on the specified target triple.
Represent the analysis usage information of a pass.
AnalysisUsage & addRequired()
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...
Definition: ArrayRef.h:41
size_t size() const
size - Get the array size.
Definition: ArrayRef.h:165
FunctionPass class - This class is used to implement most global optimizations.
Definition: Pass.h:310
bool analyzeBranch(MachineBasicBlock &MBB, MachineBasicBlock *&TBB, MachineBasicBlock *&FBB, SmallVectorImpl< MachineOperand > &Cond, bool AllowModify) const override
Analyze the branching code at the end of MBB, returning true if it cannot be understood (e....
int getNumber() const
MachineBasicBlocks are uniquely numbered at the function level, unless they're not in a MachineFuncti...
iterator getFirstNonPHI()
Returns a pointer to the first instruction in this block that is not a PHINode instruction.
succ_reverse_iterator succ_rbegin()
bool isSuccessor(const MachineBasicBlock *MBB) const
Return true if the specified MBB is a successor of this block.
void splice(iterator Where, MachineBasicBlock *Other, iterator From)
Take an instruction from MBB 'Other' at the position From, and insert it into this MBB right before '...
Analysis pass which computes a MachineDominatorTree.
DominatorTree Class - Concrete subclass of DominatorTreeBase that is used to compute a normal dominat...
MachineFunctionPass - This class adapts the FunctionPass interface to allow convenient creation of pa...
void getAnalysisUsage(AnalysisUsage &AU) const override
getAnalysisUsage - Subclasses that override getAnalysisUsage must call this.
virtual bool runOnMachineFunction(MachineFunction &MF)=0
runOnMachineFunction - This method must be overloaded to perform the desired machine code transformat...
const TargetSubtargetInfo & getSubtarget() const
getSubtarget - Return the subtarget for which this machine code is being compiled.
void dump() const
dump - Print the current MachineFunction to cerr, useful for debugger use.
MachineRegisterInfo & getRegInfo()
getRegInfo - Return information about the registers currently in use.
Function & getFunction()
Return the LLVM function that this machine code represents.
Representation of each machine instruction.
Definition: MachineInstr.h:69
const MachineBasicBlock * getParent() const
Definition: MachineInstr.h:346
unsigned getNumOperands() const
Retuns the total number of operands.
Definition: MachineInstr.h:572
bool isBranch(QueryType Type=AnyInBundle) const
Returns true if this is a conditional, unconditional, or indirect branch.
Definition: MachineInstr.h:982
void eraseFromParent()
Unlink 'this' from the containing basic block and delete it.
bool isPHI() const
const MachineOperand & getOperand(unsigned i) const
Definition: MachineInstr.h:579
MachineOperand class - Representation of each machine instruction operand.
bool isReg() const
isReg - Tests if this is a MO_Register operand.
MachineBasicBlock * getMBB() const
void setMBB(MachineBasicBlock *MBB)
Register getReg() const
getReg - Returns the register number.
bool isIdenticalTo(const MachineOperand &Other) const
Returns true if this operand is identical to the specified operand except for liveness related flags ...
MachinePostDominatorTree - an analysis pass wrapper for DominatorTree used to compute the post-domina...
MachineRegisterInfo - Keep track of information for virtual and physical registers,...
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
virtual StringRef getPassName() const
getPassName - Return a nice clean name for a pass.
Definition: Pass.cpp:81
constexpr bool isVirtual() const
Return true if the specified register number is in the virtual register namespace.
Definition: Register.h:91
constexpr bool isPhysical() const
Return true if the specified register number is in the physical register namespace.
Definition: Register.h:95
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1209
StringRef - Represent a constant reference to a string, i.e.
Definition: StringRef.h:50
TargetInstrInfo - Interface to description of machine instruction set.
virtual const TargetInstrInfo * getInstrInfo() const
Target - Wrapper for Target specific information.
A Use represents the edge between a Value definition and its users.
Definition: Use.h:43
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
unsigned ID
LLVM IR allows to use arbitrary numbers as calling convention identifiers.
Definition: CallingConv.h:24
NodeAddr< DefNode * > Def
Definition: RDFGraph.h:384
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:163
FunctionPass * createPPCBranchCoalescingPass()
createPPCBranchCoalescingPass - returns an instance of the Branch Coalescing Pass
void initializePPCBranchCoalescingPass(PassRegistry &)