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