LLVM  15.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"
26 #include "llvm/InitializePasses.h"
27 #include "llvm/Support/Debug.h"
28 
29 using namespace llvm;
30 
31 #define DEBUG_TYPE "ppc-branch-coalescing"
32 
33 STATISTIC(NumBlocksCoalesced, "Number of blocks coalesced");
34 STATISTIC(NumPHINotMoved, "Number of PHI Nodes that cannot be merged");
35 STATISTIC(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 
134 namespace {
135 
136 class 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 
161 public:
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 
190 char PPCBranchCoalescing::ID = 0;
191 /// createPPCBranchCoalescingPass - returns an instance of the Branch Coalescing
192 /// Pass
194  return new PPCBranchCoalescing();
195 }
196 
197 INITIALIZE_PASS_BEGIN(PPCBranchCoalescing, DEBUG_TYPE,
198  "Branch Coalescing", false, false)
203 
204 PPCBranchCoalescing::CoalescingCandidateInfo::CoalescingCandidateInfo()
205  : BranchBlock(nullptr), BranchTargetBlock(nullptr),
206  FallThroughBlock(nullptr), MustMoveDown(false), MustMoveUp(false) {}
207 
209  BranchBlock = nullptr;
210  BranchTargetBlock = nullptr;
211  FallThroughBlock = nullptr;
212  Cond.clear();
213  MustMoveDown = false;
214  MustMoveUp = false;
215 }
216 
218  MDT = &getAnalysis<MachineDominatorTree>();
219  MPDT = &getAnalysis<MachinePostDominatorTree>();
220  TII = MF.getSubtarget().getInstrInfo();
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 ///
234 bool 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)) {
314  LLVM_DEBUG(
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 ///
332 bool 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() &&
351  // If the physical register is constant then we can assume the value
352  // has not changed between uses.
353  && !(Op1.isUse() && MRI->isConstantPhysReg(Op1.getReg()))) {
354  LLVM_DEBUG(dbgs() << "The operands are not provably identical.\n");
355  return false;
356  }
357  LLVM_DEBUG(dbgs() << "Op1 and Op2 are identical!\n");
358  continue;
359  }
360 
361  // If the operands are not identical, but are registers, check to see if the
362  // definition of the register produces the same value. If they produce the
363  // same value, consider them to be identical.
364  if (Op1.isReg() && Op2.isReg() &&
367  MachineInstr *Op1Def = MRI->getVRegDef(Op1.getReg());
368  MachineInstr *Op2Def = MRI->getVRegDef(Op2.getReg());
369  if (TII->produceSameValue(*Op1Def, *Op2Def, MRI)) {
370  LLVM_DEBUG(dbgs() << "Op1Def: " << *Op1Def << " and " << *Op2Def
371  << " produce the same value!\n");
372  } else {
373  LLVM_DEBUG(dbgs() << "Operands produce different values\n");
374  return false;
375  }
376  } else {
377  LLVM_DEBUG(dbgs() << "The operands are not provably identical.\n");
378  return false;
379  }
380  }
381 
382  return true;
383 }
384 
385 ///
386 /// Moves ALL PHI instructions in SourceMBB to beginning of TargetMBB
387 /// and update them to refer to the new block. PHI node ordering
388 /// cannot be assumed so it does not matter where the PHI instructions
389 /// are moved to in TargetMBB.
390 ///
391 /// \param[in] SourceMBB block to move PHI instructions from
392 /// \param[in] TargetMBB block to move PHI instructions to
393 ///
394 void PPCBranchCoalescing::moveAndUpdatePHIs(MachineBasicBlock *SourceMBB,
395  MachineBasicBlock *TargetMBB) {
396 
397  MachineBasicBlock::iterator MI = SourceMBB->begin();
399 
400  if (MI == ME) {
401  LLVM_DEBUG(dbgs() << "SourceMBB contains no PHI instructions.\n");
402  return;
403  }
404 
405  // Update all PHI instructions in SourceMBB and move to top of TargetMBB
406  for (MachineBasicBlock::iterator Iter = MI; Iter != ME; Iter++) {
407  MachineInstr &PHIInst = *Iter;
408  for (unsigned i = 2, e = PHIInst.getNumOperands() + 1; i != e; i += 2) {
409  MachineOperand &MO = PHIInst.getOperand(i);
410  if (MO.getMBB() == SourceMBB)
411  MO.setMBB(TargetMBB);
412  }
413  }
414  TargetMBB->splice(TargetMBB->begin(), SourceMBB, MI, ME);
415 }
416 
417 ///
418 /// This function checks if MI can be moved to the beginning of the TargetMBB
419 /// following PHI instructions. A MI instruction can be moved to beginning of
420 /// the TargetMBB if there are no uses of it within the TargetMBB PHI nodes.
421 ///
422 /// \param[in] MI the machine instruction to move.
423 /// \param[in] TargetMBB the machine basic block to move to
424 /// \return true if it is safe to move MI to beginning of TargetMBB,
425 /// false otherwise.
426 ///
427 bool PPCBranchCoalescing::canMoveToBeginning(const MachineInstr &MI,
428  const MachineBasicBlock &TargetMBB
429  ) const {
430 
431  LLVM_DEBUG(dbgs() << "Checking if " << MI << " can move to beginning of "
432  << TargetMBB.getNumber() << "\n");
433 
434  for (auto &Def : MI.defs()) { // Looking at Def
435  for (auto &Use : MRI->use_instructions(Def.getReg())) {
436  if (Use.isPHI() && Use.getParent() == &TargetMBB) {
437  LLVM_DEBUG(dbgs() << " *** used in a PHI -- cannot move ***\n");
438  return false;
439  }
440  }
441  }
442 
443  LLVM_DEBUG(dbgs() << " Safe to move to the beginning.\n");
444  return true;
445 }
446 
447 ///
448 /// This function checks if MI can be moved to the end of the TargetMBB,
449 /// immediately before the first terminator. A MI instruction can be moved
450 /// to then end of the TargetMBB if no PHI node defines what MI uses within
451 /// it's own MBB.
452 ///
453 /// \param[in] MI the machine instruction to move.
454 /// \param[in] TargetMBB the machine basic block to move to
455 /// \return true if it is safe to move MI to end of TargetMBB,
456 /// false otherwise.
457 ///
458 bool PPCBranchCoalescing::canMoveToEnd(const MachineInstr &MI,
459  const MachineBasicBlock &TargetMBB
460  ) const {
461 
462  LLVM_DEBUG(dbgs() << "Checking if " << MI << " can move to end of "
463  << TargetMBB.getNumber() << "\n");
464 
465  for (auto &Use : MI.uses()) {
466  if (Use.isReg() && Register::isVirtualRegister(Use.getReg())) {
467  MachineInstr *DefInst = MRI->getVRegDef(Use.getReg());
468  if (DefInst->isPHI() && DefInst->getParent() == MI.getParent()) {
469  LLVM_DEBUG(dbgs() << " *** Cannot move this instruction ***\n");
470  return false;
471  } else {
472  LLVM_DEBUG(
473  dbgs() << " *** def is in another block -- safe to move!\n");
474  }
475  }
476  }
477 
478  LLVM_DEBUG(dbgs() << " Safe to move to the end.\n");
479  return true;
480 }
481 
482 ///
483 /// This method checks to ensure the two coalescing candidates follows the
484 /// expected pattern required for coalescing.
485 ///
486 /// \param[in] SourceRegion The candidate to move statements from
487 /// \param[in] TargetRegion The candidate to move statements to
488 /// \return true if all instructions in SourceRegion.BranchBlock can be merged
489 /// into a block in TargetRegion; false otherwise.
490 ///
491 bool PPCBranchCoalescing::validateCandidates(
492  CoalescingCandidateInfo &SourceRegion,
493  CoalescingCandidateInfo &TargetRegion) const {
494 
495  if (TargetRegion.BranchTargetBlock != SourceRegion.BranchBlock)
496  llvm_unreachable("Expecting SourceRegion to immediately follow TargetRegion");
497  else if (!MDT->dominates(TargetRegion.BranchBlock, SourceRegion.BranchBlock))
498  llvm_unreachable("Expecting TargetRegion to dominate SourceRegion");
499  else if (!MPDT->dominates(SourceRegion.BranchBlock, TargetRegion.BranchBlock))
500  llvm_unreachable("Expecting SourceRegion to post-dominate TargetRegion");
501  else if (!TargetRegion.FallThroughBlock->empty() ||
502  !SourceRegion.FallThroughBlock->empty())
503  llvm_unreachable("Expecting fall-through blocks to be empty");
504 
505  return true;
506 }
507 
508 ///
509 /// This method determines whether the two coalescing candidates can be merged.
510 /// In order to be merged, all instructions must be able to
511 /// 1. Move to the beginning of the SourceRegion.BranchTargetBlock;
512 /// 2. Move to the end of the TargetRegion.BranchBlock.
513 /// Merging involves moving the instructions in the
514 /// TargetRegion.BranchTargetBlock (also SourceRegion.BranchBlock).
515 ///
516 /// This function first try to move instructions from the
517 /// TargetRegion.BranchTargetBlock down, to the beginning of the
518 /// SourceRegion.BranchTargetBlock. This is not possible if any register defined
519 /// in TargetRegion.BranchTargetBlock is used in a PHI node in the
520 /// SourceRegion.BranchTargetBlock. In this case, check whether the statement
521 /// can be moved up, to the end of the TargetRegion.BranchBlock (immediately
522 /// before the branch statement). If it cannot move, then these blocks cannot
523 /// be merged.
524 ///
525 /// Note that there is no analysis for moving instructions past the fall-through
526 /// blocks because they are confirmed to be empty. An assert is thrown if they
527 /// are not.
528 ///
529 /// \param[in] SourceRegion The candidate to move statements from
530 /// \param[in] TargetRegion The candidate to move statements to
531 /// \return true if all instructions in SourceRegion.BranchBlock can be merged
532 /// into a block in TargetRegion, false otherwise.
533 ///
534 bool PPCBranchCoalescing::canMerge(CoalescingCandidateInfo &SourceRegion,
535  CoalescingCandidateInfo &TargetRegion) const {
536  if (!validateCandidates(SourceRegion, TargetRegion))
537  return false;
538 
539  // Walk through PHI nodes first and see if they force the merge into the
540  // SourceRegion.BranchTargetBlock.
542  I = SourceRegion.BranchBlock->instr_begin(),
543  E = SourceRegion.BranchBlock->getFirstNonPHI();
544  I != E; ++I) {
545  for (auto &Def : I->defs())
546  for (auto &Use : MRI->use_instructions(Def.getReg())) {
547  if (Use.isPHI() && Use.getParent() == SourceRegion.BranchTargetBlock) {
548  LLVM_DEBUG(dbgs()
549  << "PHI " << *I
550  << " defines register used in another "
551  "PHI within branch target block -- can't merge\n");
552  NumPHINotMoved++;
553  return false;
554  }
555  if (Use.getParent() == SourceRegion.BranchBlock) {
556  LLVM_DEBUG(dbgs() << "PHI " << *I
557  << " defines register used in this "
558  "block -- all must move down\n");
559  SourceRegion.MustMoveDown = true;
560  }
561  }
562  }
563 
564  // Walk through the MI to see if they should be merged into
565  // TargetRegion.BranchBlock (up) or SourceRegion.BranchTargetBlock (down)
567  I = SourceRegion.BranchBlock->getFirstNonPHI(),
568  E = SourceRegion.BranchBlock->end();
569  I != E; ++I) {
570  if (!canMoveToBeginning(*I, *SourceRegion.BranchTargetBlock)) {
571  LLVM_DEBUG(dbgs() << "Instruction " << *I
572  << " cannot move down - must move up!\n");
573  SourceRegion.MustMoveUp = true;
574  }
575  if (!canMoveToEnd(*I, *TargetRegion.BranchBlock)) {
576  LLVM_DEBUG(dbgs() << "Instruction " << *I
577  << " cannot move up - must move down!\n");
578  SourceRegion.MustMoveDown = true;
579  }
580  }
581 
582  return (SourceRegion.MustMoveUp && SourceRegion.MustMoveDown) ? false : true;
583 }
584 
585 /// Merge the instructions from SourceRegion.BranchBlock,
586 /// SourceRegion.BranchTargetBlock, and SourceRegion.FallThroughBlock into
587 /// TargetRegion.BranchBlock, TargetRegion.BranchTargetBlock and
588 /// TargetRegion.FallThroughBlock respectively.
589 ///
590 /// The successors for blocks in TargetRegion will be updated to use the
591 /// successors from blocks in SourceRegion. Finally, the blocks in SourceRegion
592 /// will be removed from the function.
593 ///
594 /// A region consists of a BranchBlock, a FallThroughBlock, and a
595 /// BranchTargetBlock. Branch coalesce works on patterns where the
596 /// TargetRegion's BranchTargetBlock must also be the SourceRegions's
597 /// BranchBlock.
598 ///
599 /// Before mergeCandidates:
600 ///
601 /// +---------------------------+
602 /// | TargetRegion.BranchBlock |
603 /// +---------------------------+
604 /// / |
605 /// / +--------------------------------+
606 /// | | TargetRegion.FallThroughBlock |
607 /// \ +--------------------------------+
608 /// \ |
609 /// +----------------------------------+
610 /// | TargetRegion.BranchTargetBlock |
611 /// | SourceRegion.BranchBlock |
612 /// +----------------------------------+
613 /// / |
614 /// / +--------------------------------+
615 /// | | SourceRegion.FallThroughBlock |
616 /// \ +--------------------------------+
617 /// \ |
618 /// +----------------------------------+
619 /// | SourceRegion.BranchTargetBlock |
620 /// +----------------------------------+
621 ///
622 /// After mergeCandidates:
623 ///
624 /// +-----------------------------+
625 /// | TargetRegion.BranchBlock |
626 /// | SourceRegion.BranchBlock |
627 /// +-----------------------------+
628 /// / |
629 /// / +---------------------------------+
630 /// | | TargetRegion.FallThroughBlock |
631 /// | | SourceRegion.FallThroughBlock |
632 /// \ +---------------------------------+
633 /// \ |
634 /// +----------------------------------+
635 /// | SourceRegion.BranchTargetBlock |
636 /// +----------------------------------+
637 ///
638 /// \param[in] SourceRegion The candidate to move blocks from
639 /// \param[in] TargetRegion The candidate to move blocks to
640 ///
641 bool PPCBranchCoalescing::mergeCandidates(CoalescingCandidateInfo &SourceRegion,
642  CoalescingCandidateInfo &TargetRegion) {
643 
644  if (SourceRegion.MustMoveUp && SourceRegion.MustMoveDown) {
645  llvm_unreachable("Cannot have both MustMoveDown and MustMoveUp set!");
646  return false;
647  }
648 
649  if (!validateCandidates(SourceRegion, TargetRegion))
650  return false;
651 
652  // Start the merging process by first handling the BranchBlock.
653  // Move any PHIs in SourceRegion.BranchBlock down to the branch-taken block
654  moveAndUpdatePHIs(SourceRegion.BranchBlock, SourceRegion.BranchTargetBlock);
655 
656  // Move remaining instructions in SourceRegion.BranchBlock into
657  // TargetRegion.BranchBlock
658  MachineBasicBlock::iterator firstInstr =
659  SourceRegion.BranchBlock->getFirstNonPHI();
660  MachineBasicBlock::iterator lastInstr =
661  SourceRegion.BranchBlock->getFirstTerminator();
662 
663  MachineBasicBlock *Source = SourceRegion.MustMoveDown
664  ? SourceRegion.BranchTargetBlock
665  : TargetRegion.BranchBlock;
666 
668  SourceRegion.MustMoveDown
669  ? SourceRegion.BranchTargetBlock->getFirstNonPHI()
670  : TargetRegion.BranchBlock->getFirstTerminator();
671 
672  Source->splice(Target, SourceRegion.BranchBlock, firstInstr, lastInstr);
673 
674  // Once PHI and instructions have been moved we need to clean up the
675  // control flow.
676 
677  // Remove SourceRegion.FallThroughBlock before transferring successors of
678  // SourceRegion.BranchBlock to TargetRegion.BranchBlock.
679  SourceRegion.BranchBlock->removeSuccessor(SourceRegion.FallThroughBlock);
680  TargetRegion.BranchBlock->transferSuccessorsAndUpdatePHIs(
681  SourceRegion.BranchBlock);
682  // Update branch in TargetRegion.BranchBlock to jump to
683  // SourceRegion.BranchTargetBlock
684  // In this case, TargetRegion.BranchTargetBlock == SourceRegion.BranchBlock.
685  TargetRegion.BranchBlock->ReplaceUsesOfBlockWith(
686  SourceRegion.BranchBlock, SourceRegion.BranchTargetBlock);
687  // Remove the branch statement(s) in SourceRegion.BranchBlock
689  SourceRegion.BranchBlock->terminators().begin();
690  while (I != SourceRegion.BranchBlock->terminators().end()) {
691  MachineInstr &CurrInst = *I;
692  ++I;
693  if (CurrInst.isBranch())
694  CurrInst.eraseFromParent();
695  }
696 
697  // Fall-through block should be empty since this is part of the condition
698  // to coalesce the branches.
699  assert(TargetRegion.FallThroughBlock->empty() &&
700  "FallThroughBlocks should be empty!");
701 
702  // Transfer successor information and move PHIs down to the
703  // branch-taken block.
704  TargetRegion.FallThroughBlock->transferSuccessorsAndUpdatePHIs(
705  SourceRegion.FallThroughBlock);
706  TargetRegion.FallThroughBlock->removeSuccessor(SourceRegion.BranchBlock);
707 
708  // Remove the blocks from the function.
709  assert(SourceRegion.BranchBlock->empty() &&
710  "Expecting branch block to be empty!");
711  SourceRegion.BranchBlock->eraseFromParent();
712 
713  assert(SourceRegion.FallThroughBlock->empty() &&
714  "Expecting fall-through block to be empty!\n");
715  SourceRegion.FallThroughBlock->eraseFromParent();
716 
717  NumBlocksCoalesced++;
718  return true;
719 }
720 
721 bool PPCBranchCoalescing::runOnMachineFunction(MachineFunction &MF) {
722 
723  if (skipFunction(MF.getFunction()) || MF.empty())
724  return false;
725 
726  bool didSomething = false;
727 
728  LLVM_DEBUG(dbgs() << "******** Branch Coalescing ********\n");
729  initialize(MF);
730 
731  LLVM_DEBUG(dbgs() << "Function: "; MF.dump(); dbgs() << "\n");
732 
733  CoalescingCandidateInfo Cand1, Cand2;
734  // Walk over blocks and find candidates to merge
735  // Continue trying to merge with the first candidate found, as long as merging
736  // is successfull.
737  for (MachineBasicBlock &MBB : MF) {
738  bool MergedCandidates = false;
739  do {
740  MergedCandidates = false;
741  Cand1.clear();
742  Cand2.clear();
743 
744  Cand1.BranchBlock = &MBB;
745 
746  // If unable to coalesce the branch, then continue to next block
747  if (!canCoalesceBranch(Cand1))
748  break;
749 
750  Cand2.BranchBlock = Cand1.BranchTargetBlock;
751  if (!canCoalesceBranch(Cand2))
752  break;
753 
754  // The branch-taken block of the second candidate should post-dominate the
755  // first candidate.
756  assert(MPDT->dominates(Cand2.BranchTargetBlock, Cand1.BranchBlock) &&
757  "Branch-taken block should post-dominate first candidate");
758 
759  if (!identicalOperands(Cand1.Cond, Cand2.Cond)) {
760  LLVM_DEBUG(dbgs() << "Blocks " << Cand1.BranchBlock->getNumber()
761  << " and " << Cand2.BranchBlock->getNumber()
762  << " have different branches\n");
763  break;
764  }
765  if (!canMerge(Cand2, Cand1)) {
766  LLVM_DEBUG(dbgs() << "Cannot merge blocks "
767  << Cand1.BranchBlock->getNumber() << " and "
768  << Cand2.BranchBlock->getNumber() << "\n");
769  NumBlocksNotCoalesced++;
770  continue;
771  }
772  LLVM_DEBUG(dbgs() << "Merging blocks " << Cand1.BranchBlock->getNumber()
773  << " and " << Cand1.BranchTargetBlock->getNumber()
774  << "\n");
775  MergedCandidates = mergeCandidates(Cand2, Cand1);
776  if (MergedCandidates)
777  didSomething = true;
778 
779  LLVM_DEBUG(dbgs() << "Function after merging: "; MF.dump();
780  dbgs() << "\n");
781  } while (MergedCandidates);
782  }
783 
784 #ifndef NDEBUG
785  // Verify MF is still valid after branch coalescing
786  if (didSomething)
787  MF.verify(nullptr, "Error in code produced by branch coalescing");
788 #endif // NDEBUG
789 
790  LLVM_DEBUG(dbgs() << "Finished Branch Coalescing\n");
791  return didSomething;
792 }
i
i
Definition: README.txt:29
llvm::MachineInstr::isBranch
bool isBranch(QueryType Type=AnyInBundle) const
Returns true if this is a conditional, unconditional, or indirect branch.
Definition: MachineInstr.h:862
MI
IRTranslator LLVM IR MI
Definition: IRTranslator.cpp:104
llvm
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:17
llvm::tgtok::Def
@ Def
Definition: TGLexer.h:50
TargetFrameLowering.h
llvm::MachineRegisterInfo
MachineRegisterInfo - Keep track of information for virtual and physical registers,...
Definition: MachineRegisterInfo.h:50
llvm::TargetSubtargetInfo::getInstrInfo
virtual const TargetInstrInfo * getInstrInfo() const
Definition: TargetSubtargetInfo.h:93
llvm::HexagonInstrInfo::analyzeBranch
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....
Definition: HexagonInstrInfo.cpp:433
llvm::Target
Target - Wrapper for Target specific information.
Definition: TargetRegistry.h:145
llvm::SmallVector
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1185
Statistic.h
llvm::MachineFunctionPass
MachineFunctionPass - This class adapts the FunctionPass interface to allow convenient creation of pa...
Definition: MachineFunctionPass.h:30
llvm::MachineRegisterInfo::use_instructions
iterator_range< use_instr_iterator > use_instructions(Register Reg) const
Definition: MachineRegisterInfo.h:493
TargetInstrInfo.h
initialize
static void initialize(TargetLibraryInfoImpl &TLI, const Triple &T, ArrayRef< StringLiteral > StandardNames)
Initialize the set of available library functions based on the specified target triple.
Definition: TargetLibraryInfo.cpp:116
llvm::MachineFunctionPass::getAnalysisUsage
void getAnalysisUsage(AnalysisUsage &AU) const override
getAnalysisUsage - Subclasses that override getAnalysisUsage must call this.
Definition: MachineFunctionPass.cpp:103
LLVM_DEBUG
#define LLVM_DEBUG(X)
Definition: Debug.h:101
F
#define F(x, y, z)
Definition: MD5.cpp:55
MachineRegisterInfo.h
llvm::dbgs
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:163
clear
static void clear(coro::Shape &Shape)
Definition: Coroutines.cpp:149
Coalescing
Branch Coalescing
Definition: PPCBranchCoalescing.cpp:201
llvm::MachineFunction::getRegInfo
MachineRegisterInfo & getRegInfo()
getRegInfo - Return information about the registers currently in use.
Definition: MachineFunction.h:666
llvm::TargetInstrInfo
TargetInstrInfo - Interface to description of machine instruction set.
Definition: TargetInstrInfo.h:97
llvm::PassRegistry::getPassRegistry
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
Definition: PassRegistry.cpp:31
E
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
llvm::MachineOperand::isUse
bool isUse() const
Definition: MachineOperand.h:369
llvm::MachineInstr::getOperand
const MachineOperand & getOperand(unsigned i) const
Definition: MachineInstr.h:501
llvm::MachineBasicBlock::isSuccessor
bool isSuccessor(const MachineBasicBlock *MBB) const
Return true if the specified MBB is a successor of this block.
Definition: MachineBasicBlock.cpp:909
llvm::Register::isPhysicalRegister
static bool isPhysicalRegister(unsigned Reg)
Return true if the specified register number is in the physical register namespace.
Definition: Register.h:65
llvm::AnalysisUsage
Represent the analysis usage information of a pass.
Definition: PassAnalysisSupport.h:47
false
Definition: StackSlotColoring.cpp:141
TII
const HexagonInstrInfo * TII
Definition: HexagonCopyToCombine.cpp:125
llvm::MachineOperand
MachineOperand class - Representation of each machine instruction operand.
Definition: MachineOperand.h:48
llvm::STATISTIC
STATISTIC(NumFunctions, "Total number of functions")
PPC.h
BitVector.h
llvm::MachineRegisterInfo::getVRegDef
MachineInstr * getVRegDef(Register Reg) const
getVRegDef - Return the machine instr that defines the specified virtual register or null if none is ...
Definition: MachineRegisterInfo.cpp:396
llvm::CallingConv::ID
unsigned ID
LLVM IR allows to use arbitrary numbers as calling convention identifiers.
Definition: CallingConv.h:24
llvm::MachineBasicBlock
Definition: MachineBasicBlock.h:94
INITIALIZE_PASS_END
#define INITIALIZE_PASS_END(passName, arg, name, cfg, analysis)
Definition: PassSupport.h:58
Passes.h
llvm::MachineFunction::getSubtarget
const TargetSubtargetInfo & getSubtarget() const
getSubtarget - Return the subtarget for which this machine code is being compiled.
Definition: MachineFunction.h:656
llvm::MachineOperand::isReg
bool isReg() const
isReg - Tests if this is a MO_Register operand.
Definition: MachineOperand.h:320
llvm::MachineInstr
Representation of each machine instruction.
Definition: MachineInstr.h:66
INITIALIZE_PASS_DEPENDENCY
INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
llvm::numbers::e
constexpr double e
Definition: MathExtras.h:57
llvm::MachineFunction::dump
void dump() const
dump - Print the current MachineFunction to cerr, useful for debugger use.
Definition: MachineFunction.cpp:560
I
#define I(x, y, z)
Definition: MD5.cpp:58
llvm::MachineBasicBlock::getFirstNonPHI
iterator getFirstNonPHI()
Returns a pointer to the first instruction in this block that is not a PHINode instruction.
Definition: MachineBasicBlock.cpp:196
MachineFunctionPass.h
llvm::Register::isVirtualRegister
static bool isVirtualRegister(unsigned Reg)
Return true if the specified register number is in the virtual register namespace.
Definition: Register.h:71
assert
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
llvm::MachineInstr::isPHI
bool isPHI() const
Definition: MachineInstr.h:1256
MachinePostDominators.h
llvm::MachineOperand::getReg
Register getReg() const
getReg - Returns the register number.
Definition: MachineOperand.h:359
llvm::MachineFunction
Definition: MachineFunction.h:257
llvm::Sched::Source
@ Source
Definition: TargetLowering.h:99
llvm::ArrayRef
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...
Definition: APInt.h:32
llvm::MachineOperand::getMBB
MachineBasicBlock * getMBB() const
Definition: MachineOperand.h:561
llvm::MachineBasicBlock::getNumber
int getNumber() const
MachineBasicBlocks are uniquely numbered at the function level, unless they're not in a MachineFuncti...
Definition: MachineBasicBlock.h:1088
Cond
SmallVector< MachineOperand, 4 > Cond
Definition: BasicBlockSections.cpp:137
llvm::StringRef
StringRef - Represent a constant reference to a string, i.e.
Definition: StringRef.h:58
llvm::MachineBasicBlock::splice
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 '...
Definition: MachineBasicBlock.h:982
llvm_unreachable
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
Definition: ErrorHandling.h:143
TargetSubtargetInfo.h
llvm::createPPCBranchCoalescingPass
FunctionPass * createPPCBranchCoalescingPass()
createPPCBranchCoalescingPass - returns an instance of the Branch Coalescing Pass
Definition: PPCBranchCoalescing.cpp:193
llvm::MachineInstr::getParent
const MachineBasicBlock * getParent() const
Definition: MachineInstr.h:288
llvm::MachinePostDominatorTree
MachinePostDominatorTree - an analysis pass wrapper for DominatorTree used to compute the post-domina...
Definition: MachinePostDominators.h:27
MRI
unsigned const MachineRegisterInfo * MRI
Definition: AArch64AdvSIMDScalarPass.cpp:105
llvm::MachineRegisterInfo::isConstantPhysReg
bool isConstantPhysReg(MCRegister PhysReg) const
Returns true if PhysReg is unallocatable and constant throughout the function.
Definition: MachineRegisterInfo.cpp:509
MBB
MachineBasicBlock & MBB
Definition: AArch64SLSHardening.cpp:74
llvm::MachineFunction::getFunction
Function & getFunction()
Return the LLVM function that this machine code represents.
Definition: MachineFunction.h:622
DEBUG_TYPE
#define DEBUG_TYPE
Definition: PPCBranchCoalescing.cpp:31
llvm::MCID::Branch
@ Branch
Definition: MCInstrDesc.h:158
llvm::MachineBasicBlock::begin
iterator begin()
Definition: MachineBasicBlock.h:278
llvm::MachineInstr::getNumOperands
unsigned getNumOperands() const
Retuns the total number of operands.
Definition: MachineInstr.h:494
llvm::ArrayRef::size
size_t size() const
size - Get the array size.
Definition: ArrayRef.h:164
llvm::initializePPCBranchCoalescingPass
void initializePPCBranchCoalescingPass(PassRegistry &)
llvm::MachineOperand::setMBB
void setMBB(MachineBasicBlock *MBB)
Definition: MachineOperand.h:698
llvm::MachineBasicBlock::empty
bool empty() const
Definition: MachineBasicBlock.h:250
llvm::FunctionPass
FunctionPass class - This class is used to implement most global optimizations.
Definition: Pass.h:308
llvm::AnalysisUsage::addRequired
AnalysisUsage & addRequired()
Definition: PassAnalysisSupport.h:75
llvm::MachineDominatorTree
DominatorTree Class - Concrete subclass of DominatorTreeBase that is used to compute a normal dominat...
Definition: MachineDominators.h:51
false
Branch false
Definition: PPCBranchCoalescing.cpp:202
llvm::MachineFunction::empty
bool empty() const
Definition: MachineFunction.h:864
llvm::MachineInstr::eraseFromParent
void eraseFromParent()
Unlink 'this' from the containing basic block and delete it.
Definition: MachineInstr.cpp:650
llvm::MachineInstrBundleIterator< MachineInstr >
InitializePasses.h
Debug.h
llvm::MachineOperand::isIdenticalTo
bool isIdenticalTo(const MachineOperand &Other) const
Returns true if this operand is identical to the specified operand except for liveness related flags ...
Definition: MachineOperand.cpp:285
llvm::Use
A Use represents the edge between a Value definition and its users.
Definition: Use.h:43
MachineDominators.h
llvm::Intrinsic::ID
unsigned ID
Definition: TargetTransformInfo.h:38
INITIALIZE_PASS_BEGIN
INITIALIZE_PASS_BEGIN(PPCBranchCoalescing, DEBUG_TYPE, "Branch Coalescing", false, false) INITIALIZE_PASS_END(PPCBranchCoalescing