LLVM  10.0.0svn
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/Support/Debug.h"
27 
28 using namespace llvm;
29 
30 #define DEBUG_TYPE "ppc-branch-coalescing"
31 
32 STATISTIC(NumBlocksCoalesced, "Number of blocks coalesced");
33 STATISTIC(NumPHINotMoved, "Number of PHI Nodes that cannot be merged");
34 STATISTIC(NumBlocksNotCoalesced, "Number of blocks not coalesced");
35 
36 //===----------------------------------------------------------------------===//
37 // PPCBranchCoalescing
38 //===----------------------------------------------------------------------===//
39 ///
40 /// Improve scheduling by coalescing branches that depend on the same condition.
41 /// This pass looks for blocks that are guarded by the same branch condition
42 /// and attempts to merge the blocks together. Such opportunities arise from
43 /// the expansion of select statements in the IR.
44 ///
45 /// This pass does not handle implicit operands on branch statements. In order
46 /// to run on targets that use implicit operands, changes need to be made in the
47 /// canCoalesceBranch and canMerge methods.
48 ///
49 /// Example: the following LLVM IR
50 ///
51 /// %test = icmp eq i32 %x 0
52 /// %tmp1 = select i1 %test, double %a, double 2.000000e-03
53 /// %tmp2 = select i1 %test, double %b, double 5.000000e-03
54 ///
55 /// expands to the following machine code:
56 ///
57 /// %bb.0: derived from LLVM BB %entry
58 /// liveins: %f1 %f3 %x6
59 /// <SNIP1>
60 /// %0 = COPY %f1; F8RC:%0
61 /// %5 = CMPLWI killed %4, 0; CRRC:%5 GPRC:%4
62 /// %8 = LXSDX %zero8, killed %7, implicit %rm;
63 /// mem:LD8[ConstantPool] F8RC:%8 G8RC:%7
64 /// BCC 76, %5, <%bb.2>; CRRC:%5
65 /// Successors according to CFG: %bb.1(?%) %bb.2(?%)
66 ///
67 /// %bb.1: derived from LLVM BB %entry
68 /// Predecessors according to CFG: %bb.0
69 /// Successors according to CFG: %bb.2(?%)
70 ///
71 /// %bb.2: derived from LLVM BB %entry
72 /// Predecessors according to CFG: %bb.0 %bb.1
73 /// %9 = PHI %8, <%bb.1>, %0, <%bb.0>;
74 /// F8RC:%9,%8,%0
75 /// <SNIP2>
76 /// BCC 76, %5, <%bb.4>; CRRC:%5
77 /// Successors according to CFG: %bb.3(?%) %bb.4(?%)
78 ///
79 /// %bb.3: derived from LLVM BB %entry
80 /// Predecessors according to CFG: %bb.2
81 /// Successors according to CFG: %bb.4(?%)
82 ///
83 /// %bb.4: derived from LLVM BB %entry
84 /// Predecessors according to CFG: %bb.2 %bb.3
85 /// %13 = PHI %12, <%bb.3>, %2, <%bb.2>;
86 /// F8RC:%13,%12,%2
87 /// <SNIP3>
88 /// BLR8 implicit %lr8, implicit %rm, implicit %f1
89 ///
90 /// When this pattern is detected, branch coalescing will try to collapse
91 /// it by moving code in %bb.2 to %bb.0 and/or %bb.4 and removing %bb.3.
92 ///
93 /// If all conditions are meet, IR should collapse to:
94 ///
95 /// %bb.0: derived from LLVM BB %entry
96 /// liveins: %f1 %f3 %x6
97 /// <SNIP1>
98 /// %0 = COPY %f1; F8RC:%0
99 /// %5 = CMPLWI killed %4, 0; CRRC:%5 GPRC:%4
100 /// %8 = LXSDX %zero8, killed %7, implicit %rm;
101 /// mem:LD8[ConstantPool] F8RC:%8 G8RC:%7
102 /// <SNIP2>
103 /// BCC 76, %5, <%bb.4>; CRRC:%5
104 /// Successors according to CFG: %bb.1(0x2aaaaaaa / 0x80000000 = 33.33%)
105 /// %bb.4(0x55555554 / 0x80000000 = 66.67%)
106 ///
107 /// %bb.1: derived from LLVM BB %entry
108 /// Predecessors according to CFG: %bb.0
109 /// Successors according to CFG: %bb.4(0x40000000 / 0x80000000 = 50.00%)
110 ///
111 /// %bb.4: derived from LLVM BB %entry
112 /// Predecessors according to CFG: %bb.0 %bb.1
113 /// %9 = PHI %8, <%bb.1>, %0, <%bb.0>;
114 /// F8RC:%9,%8,%0
115 /// %13 = PHI %12, <%bb.1>, %2, <%bb.0>;
116 /// F8RC:%13,%12,%2
117 /// <SNIP3>
118 /// BLR8 implicit %lr8, implicit %rm, implicit %f1
119 ///
120 /// Branch Coalescing does not split blocks, it moves everything in the same
121 /// direction ensuring it does not break use/definition semantics.
122 ///
123 /// PHI nodes and its corresponding use instructions are moved to its successor
124 /// block if there are no uses within the successor block PHI nodes. PHI
125 /// node ordering cannot be assumed.
126 ///
127 /// Non-PHI can be moved up to the predecessor basic block or down to the
128 /// successor basic block following any PHI instructions. Whether it moves
129 /// up or down depends on whether the register(s) defined in the instructions
130 /// are used in current block or in any PHI instructions at the beginning of
131 /// the successor block.
132 
133 namespace {
134 
135 class PPCBranchCoalescing : public MachineFunctionPass {
136  struct CoalescingCandidateInfo {
137  MachineBasicBlock *BranchBlock; // Block containing the branch
138  MachineBasicBlock *BranchTargetBlock; // Block branched to
139  MachineBasicBlock *FallThroughBlock; // Fall-through if branch not taken
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 
160 public:
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 
189 char PPCBranchCoalescing::ID = 0;
190 /// createPPCBranchCoalescingPass - returns an instance of the Branch Coalescing
191 /// Pass
193  return new PPCBranchCoalescing();
194 }
195 
196 INITIALIZE_PASS_BEGIN(PPCBranchCoalescing, DEBUG_TYPE,
197  "Branch Coalescing", false, false)
201  false, false)
202 
203 PPCBranchCoalescing::CoalescingCandidateInfo::CoalescingCandidateInfo()
204  : BranchBlock(nullptr), BranchTargetBlock(nullptr),
205  FallThroughBlock(nullptr), MustMoveDown(false), MustMoveUp(false) {}
206 
208  BranchBlock = nullptr;
209  BranchTargetBlock = nullptr;
210  FallThroughBlock = nullptr;
211  Cond.clear();
212  MustMoveDown = false;
213  MustMoveUp = false;
214 }
215 
217  MDT = &getAnalysis<MachineDominatorTree>();
218  MPDT = &getAnalysis<MachinePostDominatorTree>();
219  TII = MF.getSubtarget().getInstrInfo();
220  MRI = &MF.getRegInfo();
221 }
222 
223 ///
224 /// Analyze the branch statement to determine if it can be coalesced. This
225 /// method analyses the branch statement for the given candidate to determine
226 /// if it can be coalesced. If the branch can be coalesced, then the
227 /// BranchTargetBlock and the FallThroughBlock are recorded in the specified
228 /// Candidate.
229 ///
230 ///\param[in,out] Cand The coalescing candidate to analyze
231 ///\return true if and only if the branch can be coalesced, false otherwise
232 ///
233 bool 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  // For now only consider triangles (i.e, BranchTargetBlock is set,
275  // FalseMBB is null, and BranchTargetBlock is a successor to BranchBlock)
276  if (!Cand.BranchTargetBlock || FalseMBB ||
277  !Cand.BranchBlock->isSuccessor(Cand.BranchTargetBlock)) {
278  LLVM_DEBUG(dbgs() << "Does not form a triangle - skip\n");
279  return false;
280  }
281 
282  // Ensure there are only two successors
283  if (Cand.BranchBlock->succ_size() != 2) {
284  LLVM_DEBUG(dbgs() << "Does not have 2 successors - skip\n");
285  return false;
286  }
287 
288  // Sanity check - the block must be able to fall through
289  assert(Cand.BranchBlock->canFallThrough() &&
290  "Expecting the block to fall through!");
291 
292  // We have already ensured there are exactly two successors to
293  // BranchBlock and that BranchTargetBlock is a successor to BranchBlock.
294  // Ensure the single fall though block is empty.
295  MachineBasicBlock *Succ =
296  (*Cand.BranchBlock->succ_begin() == Cand.BranchTargetBlock)
297  ? *Cand.BranchBlock->succ_rbegin()
298  : *Cand.BranchBlock->succ_begin();
299 
300  assert(Succ && "Expecting a valid fall-through block\n");
301 
302  if (!Succ->empty()) {
303  LLVM_DEBUG(dbgs() << "Fall-through block contains code -- skip\n");
304  return false;
305  }
306 
307  if (!Succ->isSuccessor(Cand.BranchTargetBlock)) {
308  LLVM_DEBUG(
309  dbgs()
310  << "Successor of fall through block is not branch taken block\n");
311  return false;
312  }
313 
314  Cand.FallThroughBlock = Succ;
315  LLVM_DEBUG(dbgs() << "Valid Candidate\n");
316  return true;
317 }
318 
319 ///
320 /// Determine if the two operand lists are identical
321 ///
322 /// \param[in] OpList1 operand list
323 /// \param[in] OpList2 operand list
324 /// \return true if and only if the operands lists are identical
325 ///
326 bool PPCBranchCoalescing::identicalOperands(
327  ArrayRef<MachineOperand> OpList1, ArrayRef<MachineOperand> OpList2) const {
328 
329  if (OpList1.size() != OpList2.size()) {
330  LLVM_DEBUG(dbgs() << "Operand list is different size\n");
331  return false;
332  }
333 
334  for (unsigned i = 0; i < OpList1.size(); ++i) {
335  const MachineOperand &Op1 = OpList1[i];
336  const MachineOperand &Op2 = OpList2[i];
337 
338  LLVM_DEBUG(dbgs() << "Op1: " << Op1 << "\n"
339  << "Op2: " << Op2 << "\n");
340 
341  if (Op1.isIdenticalTo(Op2)) {
342  // filter out instructions with physical-register uses
343  if (Op1.isReg() &&
345  // If the physical register is constant then we can assume the value
346  // has not changed between uses.
347  && !(Op1.isUse() && MRI->isConstantPhysReg(Op1.getReg()))) {
348  LLVM_DEBUG(dbgs() << "The operands are not provably identical.\n");
349  return false;
350  }
351  LLVM_DEBUG(dbgs() << "Op1 and Op2 are identical!\n");
352  continue;
353  }
354 
355  // If the operands are not identical, but are registers, check to see if the
356  // definition of the register produces the same value. If they produce the
357  // same value, consider them to be identical.
358  if (Op1.isReg() && Op2.isReg() &&
361  MachineInstr *Op1Def = MRI->getVRegDef(Op1.getReg());
362  MachineInstr *Op2Def = MRI->getVRegDef(Op2.getReg());
363  if (TII->produceSameValue(*Op1Def, *Op2Def, MRI)) {
364  LLVM_DEBUG(dbgs() << "Op1Def: " << *Op1Def << " and " << *Op2Def
365  << " produce the same value!\n");
366  } else {
367  LLVM_DEBUG(dbgs() << "Operands produce different values\n");
368  return false;
369  }
370  } else {
371  LLVM_DEBUG(dbgs() << "The operands are not provably identical.\n");
372  return false;
373  }
374  }
375 
376  return true;
377 }
378 
379 ///
380 /// Moves ALL PHI instructions in SourceMBB to beginning of TargetMBB
381 /// and update them to refer to the new block. PHI node ordering
382 /// cannot be assumed so it does not matter where the PHI instructions
383 /// are moved to in TargetMBB.
384 ///
385 /// \param[in] SourceMBB block to move PHI instructions from
386 /// \param[in] TargetMBB block to move PHI instructions to
387 ///
388 void PPCBranchCoalescing::moveAndUpdatePHIs(MachineBasicBlock *SourceMBB,
389  MachineBasicBlock *TargetMBB) {
390 
391  MachineBasicBlock::iterator MI = SourceMBB->begin();
393 
394  if (MI == ME) {
395  LLVM_DEBUG(dbgs() << "SourceMBB contains no PHI instructions.\n");
396  return;
397  }
398 
399  // Update all PHI instructions in SourceMBB and move to top of TargetMBB
400  for (MachineBasicBlock::iterator Iter = MI; Iter != ME; Iter++) {
401  MachineInstr &PHIInst = *Iter;
402  for (unsigned i = 2, e = PHIInst.getNumOperands() + 1; i != e; i += 2) {
403  MachineOperand &MO = PHIInst.getOperand(i);
404  if (MO.getMBB() == SourceMBB)
405  MO.setMBB(TargetMBB);
406  }
407  }
408  TargetMBB->splice(TargetMBB->begin(), SourceMBB, MI, ME);
409 }
410 
411 ///
412 /// This function checks if MI can be moved to the beginning of the TargetMBB
413 /// following PHI instructions. A MI instruction can be moved to beginning of
414 /// the TargetMBB if there are no uses of it within the TargetMBB PHI nodes.
415 ///
416 /// \param[in] MI the machine instruction to move.
417 /// \param[in] TargetMBB the machine basic block to move to
418 /// \return true if it is safe to move MI to beginning of TargetMBB,
419 /// false otherwise.
420 ///
421 bool PPCBranchCoalescing::canMoveToBeginning(const MachineInstr &MI,
422  const MachineBasicBlock &TargetMBB
423  ) const {
424 
425  LLVM_DEBUG(dbgs() << "Checking if " << MI << " can move to beginning of "
426  << TargetMBB.getNumber() << "\n");
427 
428  for (auto &Def : MI.defs()) { // Looking at Def
429  for (auto &Use : MRI->use_instructions(Def.getReg())) {
430  if (Use.isPHI() && Use.getParent() == &TargetMBB) {
431  LLVM_DEBUG(dbgs() << " *** used in a PHI -- cannot move ***\n");
432  return false;
433  }
434  }
435  }
436 
437  LLVM_DEBUG(dbgs() << " Safe to move to the beginning.\n");
438  return true;
439 }
440 
441 ///
442 /// This function checks if MI can be moved to the end of the TargetMBB,
443 /// immediately before the first terminator. A MI instruction can be moved
444 /// to then end of the TargetMBB if no PHI node defines what MI uses within
445 /// it's own MBB.
446 ///
447 /// \param[in] MI the machine instruction to move.
448 /// \param[in] TargetMBB the machine basic block to move to
449 /// \return true if it is safe to move MI to end of TargetMBB,
450 /// false otherwise.
451 ///
452 bool PPCBranchCoalescing::canMoveToEnd(const MachineInstr &MI,
453  const MachineBasicBlock &TargetMBB
454  ) const {
455 
456  LLVM_DEBUG(dbgs() << "Checking if " << MI << " can move to end of "
457  << TargetMBB.getNumber() << "\n");
458 
459  for (auto &Use : MI.uses()) {
460  if (Use.isReg() && Register::isVirtualRegister(Use.getReg())) {
461  MachineInstr *DefInst = MRI->getVRegDef(Use.getReg());
462  if (DefInst->isPHI() && DefInst->getParent() == MI.getParent()) {
463  LLVM_DEBUG(dbgs() << " *** Cannot move this instruction ***\n");
464  return false;
465  } else {
466  LLVM_DEBUG(
467  dbgs() << " *** def is in another block -- safe to move!\n");
468  }
469  }
470  }
471 
472  LLVM_DEBUG(dbgs() << " Safe to move to the end.\n");
473  return true;
474 }
475 
476 ///
477 /// This method checks to ensure the two coalescing candidates follows the
478 /// expected pattern required for coalescing.
479 ///
480 /// \param[in] SourceRegion The candidate to move statements from
481 /// \param[in] TargetRegion The candidate to move statements to
482 /// \return true if all instructions in SourceRegion.BranchBlock can be merged
483 /// into a block in TargetRegion; false otherwise.
484 ///
485 bool PPCBranchCoalescing::validateCandidates(
486  CoalescingCandidateInfo &SourceRegion,
487  CoalescingCandidateInfo &TargetRegion) const {
488 
489  if (TargetRegion.BranchTargetBlock != SourceRegion.BranchBlock)
490  llvm_unreachable("Expecting SourceRegion to immediately follow TargetRegion");
491  else if (!MDT->dominates(TargetRegion.BranchBlock, SourceRegion.BranchBlock))
492  llvm_unreachable("Expecting TargetRegion to dominate SourceRegion");
493  else if (!MPDT->dominates(SourceRegion.BranchBlock, TargetRegion.BranchBlock))
494  llvm_unreachable("Expecting SourceRegion to post-dominate TargetRegion");
495  else if (!TargetRegion.FallThroughBlock->empty() ||
496  !SourceRegion.FallThroughBlock->empty())
497  llvm_unreachable("Expecting fall-through blocks to be empty");
498 
499  return true;
500 }
501 
502 ///
503 /// This method determines whether the two coalescing candidates can be merged.
504 /// In order to be merged, all instructions must be able to
505 /// 1. Move to the beginning of the SourceRegion.BranchTargetBlock;
506 /// 2. Move to the end of the TargetRegion.BranchBlock.
507 /// Merging involves moving the instructions in the
508 /// TargetRegion.BranchTargetBlock (also SourceRegion.BranchBlock).
509 ///
510 /// This function first try to move instructions from the
511 /// TargetRegion.BranchTargetBlock down, to the beginning of the
512 /// SourceRegion.BranchTargetBlock. This is not possible if any register defined
513 /// in TargetRegion.BranchTargetBlock is used in a PHI node in the
514 /// SourceRegion.BranchTargetBlock. In this case, check whether the statement
515 /// can be moved up, to the end of the TargetRegion.BranchBlock (immediately
516 /// before the branch statement). If it cannot move, then these blocks cannot
517 /// be merged.
518 ///
519 /// Note that there is no analysis for moving instructions past the fall-through
520 /// blocks because they are confirmed to be empty. An assert is thrown if they
521 /// are not.
522 ///
523 /// \param[in] SourceRegion The candidate to move statements from
524 /// \param[in] TargetRegion The candidate to move statements to
525 /// \return true if all instructions in SourceRegion.BranchBlock can be merged
526 /// into a block in TargetRegion, false otherwise.
527 ///
528 bool PPCBranchCoalescing::canMerge(CoalescingCandidateInfo &SourceRegion,
529  CoalescingCandidateInfo &TargetRegion) const {
530  if (!validateCandidates(SourceRegion, TargetRegion))
531  return false;
532 
533  // Walk through PHI nodes first and see if they force the merge into the
534  // SourceRegion.BranchTargetBlock.
536  I = SourceRegion.BranchBlock->instr_begin(),
537  E = SourceRegion.BranchBlock->getFirstNonPHI();
538  I != E; ++I) {
539  for (auto &Def : I->defs())
540  for (auto &Use : MRI->use_instructions(Def.getReg())) {
541  if (Use.isPHI() && Use.getParent() == SourceRegion.BranchTargetBlock) {
542  LLVM_DEBUG(dbgs()
543  << "PHI " << *I
544  << " defines register used in another "
545  "PHI within branch target block -- can't merge\n");
546  NumPHINotMoved++;
547  return false;
548  }
549  if (Use.getParent() == SourceRegion.BranchBlock) {
550  LLVM_DEBUG(dbgs() << "PHI " << *I
551  << " defines register used in this "
552  "block -- all must move down\n");
553  SourceRegion.MustMoveDown = true;
554  }
555  }
556  }
557 
558  // Walk through the MI to see if they should be merged into
559  // TargetRegion.BranchBlock (up) or SourceRegion.BranchTargetBlock (down)
561  I = SourceRegion.BranchBlock->getFirstNonPHI(),
562  E = SourceRegion.BranchBlock->end();
563  I != E; ++I) {
564  if (!canMoveToBeginning(*I, *SourceRegion.BranchTargetBlock)) {
565  LLVM_DEBUG(dbgs() << "Instruction " << *I
566  << " cannot move down - must move up!\n");
567  SourceRegion.MustMoveUp = true;
568  }
569  if (!canMoveToEnd(*I, *TargetRegion.BranchBlock)) {
570  LLVM_DEBUG(dbgs() << "Instruction " << *I
571  << " cannot move up - must move down!\n");
572  SourceRegion.MustMoveDown = true;
573  }
574  }
575 
576  return (SourceRegion.MustMoveUp && SourceRegion.MustMoveDown) ? false : true;
577 }
578 
579 /// Merge the instructions from SourceRegion.BranchBlock,
580 /// SourceRegion.BranchTargetBlock, and SourceRegion.FallThroughBlock into
581 /// TargetRegion.BranchBlock, TargetRegion.BranchTargetBlock and
582 /// TargetRegion.FallThroughBlock respectively.
583 ///
584 /// The successors for blocks in TargetRegion will be updated to use the
585 /// successors from blocks in SourceRegion. Finally, the blocks in SourceRegion
586 /// will be removed from the function.
587 ///
588 /// A region consists of a BranchBlock, a FallThroughBlock, and a
589 /// BranchTargetBlock. Branch coalesce works on patterns where the
590 /// TargetRegion's BranchTargetBlock must also be the SourceRegions's
591 /// BranchBlock.
592 ///
593 /// Before mergeCandidates:
594 ///
595 /// +---------------------------+
596 /// | TargetRegion.BranchBlock |
597 /// +---------------------------+
598 /// / |
599 /// / +--------------------------------+
600 /// | | TargetRegion.FallThroughBlock |
601 /// \ +--------------------------------+
602 /// \ |
603 /// +----------------------------------+
604 /// | TargetRegion.BranchTargetBlock |
605 /// | SourceRegion.BranchBlock |
606 /// +----------------------------------+
607 /// / |
608 /// / +--------------------------------+
609 /// | | SourceRegion.FallThroughBlock |
610 /// \ +--------------------------------+
611 /// \ |
612 /// +----------------------------------+
613 /// | SourceRegion.BranchTargetBlock |
614 /// +----------------------------------+
615 ///
616 /// After mergeCandidates:
617 ///
618 /// +-----------------------------+
619 /// | TargetRegion.BranchBlock |
620 /// | SourceRegion.BranchBlock |
621 /// +-----------------------------+
622 /// / |
623 /// / +---------------------------------+
624 /// | | TargetRegion.FallThroughBlock |
625 /// | | SourceRegion.FallThroughBlock |
626 /// \ +---------------------------------+
627 /// \ |
628 /// +----------------------------------+
629 /// | SourceRegion.BranchTargetBlock |
630 /// +----------------------------------+
631 ///
632 /// \param[in] SourceRegion The candidate to move blocks from
633 /// \param[in] TargetRegion The candidate to move blocks to
634 ///
635 bool PPCBranchCoalescing::mergeCandidates(CoalescingCandidateInfo &SourceRegion,
636  CoalescingCandidateInfo &TargetRegion) {
637 
638  if (SourceRegion.MustMoveUp && SourceRegion.MustMoveDown) {
639  llvm_unreachable("Cannot have both MustMoveDown and MustMoveUp set!");
640  return false;
641  }
642 
643  if (!validateCandidates(SourceRegion, TargetRegion))
644  return false;
645 
646  // Start the merging process by first handling the BranchBlock.
647  // Move any PHIs in SourceRegion.BranchBlock down to the branch-taken block
648  moveAndUpdatePHIs(SourceRegion.BranchBlock, SourceRegion.BranchTargetBlock);
649 
650  // Move remaining instructions in SourceRegion.BranchBlock into
651  // TargetRegion.BranchBlock
652  MachineBasicBlock::iterator firstInstr =
653  SourceRegion.BranchBlock->getFirstNonPHI();
654  MachineBasicBlock::iterator lastInstr =
655  SourceRegion.BranchBlock->getFirstTerminator();
656 
657  MachineBasicBlock *Source = SourceRegion.MustMoveDown
658  ? SourceRegion.BranchTargetBlock
659  : TargetRegion.BranchBlock;
660 
662  SourceRegion.MustMoveDown
663  ? SourceRegion.BranchTargetBlock->getFirstNonPHI()
664  : TargetRegion.BranchBlock->getFirstTerminator();
665 
666  Source->splice(Target, SourceRegion.BranchBlock, firstInstr, lastInstr);
667 
668  // Once PHI and instructions have been moved we need to clean up the
669  // control flow.
670 
671  // Remove SourceRegion.FallThroughBlock before transferring successors of
672  // SourceRegion.BranchBlock to TargetRegion.BranchBlock.
673  SourceRegion.BranchBlock->removeSuccessor(SourceRegion.FallThroughBlock);
674  TargetRegion.BranchBlock->transferSuccessorsAndUpdatePHIs(
675  SourceRegion.BranchBlock);
676  // Update branch in TargetRegion.BranchBlock to jump to
677  // SourceRegion.BranchTargetBlock
678  // In this case, TargetRegion.BranchTargetBlock == SourceRegion.BranchBlock.
679  TargetRegion.BranchBlock->ReplaceUsesOfBlockWith(
680  SourceRegion.BranchBlock, SourceRegion.BranchTargetBlock);
681  // Remove the branch statement(s) in SourceRegion.BranchBlock
683  SourceRegion.BranchBlock->terminators().begin();
684  while (I != SourceRegion.BranchBlock->terminators().end()) {
685  MachineInstr &CurrInst = *I;
686  ++I;
687  if (CurrInst.isBranch())
688  CurrInst.eraseFromParent();
689  }
690 
691  // Fall-through block should be empty since this is part of the condition
692  // to coalesce the branches.
693  assert(TargetRegion.FallThroughBlock->empty() &&
694  "FallThroughBlocks should be empty!");
695 
696  // Transfer successor information and move PHIs down to the
697  // branch-taken block.
698  TargetRegion.FallThroughBlock->transferSuccessorsAndUpdatePHIs(
699  SourceRegion.FallThroughBlock);
700  TargetRegion.FallThroughBlock->removeSuccessor(SourceRegion.BranchBlock);
701 
702  // Remove the blocks from the function.
703  assert(SourceRegion.BranchBlock->empty() &&
704  "Expecting branch block to be empty!");
705  SourceRegion.BranchBlock->eraseFromParent();
706 
707  assert(SourceRegion.FallThroughBlock->empty() &&
708  "Expecting fall-through block to be empty!\n");
709  SourceRegion.FallThroughBlock->eraseFromParent();
710 
711  NumBlocksCoalesced++;
712  return true;
713 }
714 
715 bool PPCBranchCoalescing::runOnMachineFunction(MachineFunction &MF) {
716 
717  if (skipFunction(MF.getFunction()) || MF.empty())
718  return false;
719 
720  bool didSomething = false;
721 
722  LLVM_DEBUG(dbgs() << "******** Branch Coalescing ********\n");
723  initialize(MF);
724 
725  LLVM_DEBUG(dbgs() << "Function: "; MF.dump(); dbgs() << "\n");
726 
727  CoalescingCandidateInfo Cand1, Cand2;
728  // Walk over blocks and find candidates to merge
729  // Continue trying to merge with the first candidate found, as long as merging
730  // is successfull.
731  for (MachineBasicBlock &MBB : MF) {
732  bool MergedCandidates = false;
733  do {
734  MergedCandidates = false;
735  Cand1.clear();
736  Cand2.clear();
737 
738  Cand1.BranchBlock = &MBB;
739 
740  // If unable to coalesce the branch, then continue to next block
741  if (!canCoalesceBranch(Cand1))
742  break;
743 
744  Cand2.BranchBlock = Cand1.BranchTargetBlock;
745  if (!canCoalesceBranch(Cand2))
746  break;
747 
748  // Sanity check
749  // The branch-taken block of the second candidate should post-dominate the
750  // first candidate
751  assert(MPDT->dominates(Cand2.BranchTargetBlock, Cand1.BranchBlock) &&
752  "Branch-taken block should post-dominate first candidate");
753 
754  if (!identicalOperands(Cand1.Cond, Cand2.Cond)) {
755  LLVM_DEBUG(dbgs() << "Blocks " << Cand1.BranchBlock->getNumber()
756  << " and " << Cand2.BranchBlock->getNumber()
757  << " have different branches\n");
758  break;
759  }
760  if (!canMerge(Cand2, Cand1)) {
761  LLVM_DEBUG(dbgs() << "Cannot merge blocks "
762  << Cand1.BranchBlock->getNumber() << " and "
763  << Cand2.BranchBlock->getNumber() << "\n");
764  NumBlocksNotCoalesced++;
765  continue;
766  }
767  LLVM_DEBUG(dbgs() << "Merging blocks " << Cand1.BranchBlock->getNumber()
768  << " and " << Cand1.BranchTargetBlock->getNumber()
769  << "\n");
770  MergedCandidates = mergeCandidates(Cand2, Cand1);
771  if (MergedCandidates)
772  didSomething = true;
773 
774  LLVM_DEBUG(dbgs() << "Function after merging: "; MF.dump();
775  dbgs() << "\n");
776  } while (MergedCandidates);
777  }
778 
779 #ifndef NDEBUG
780  // Verify MF is still valid after branch coalescing
781  if (didSomething)
782  MF.verify(nullptr, "Error in code produced by branch coalescing");
783 #endif // NDEBUG
784 
785  LLVM_DEBUG(dbgs() << "Finished Branch Coalescing\n");
786  return didSomething;
787 }
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
MachineBasicBlock * getMBB() const
This class represents lattice values for constants.
Definition: AllocatorList.h:23
iterator_range< mop_iterator > uses()
Returns a range that includes all operands that are register uses.
Definition: MachineInstr.h:510
static bool isPhysicalRegister(unsigned Reg)
Return true if the specified register number is in the physical register namespace.
Definition: Register.h:63
STATISTIC(NumFunctions, "Total number of functions")
F(f)
bool isPHI() const
void dump() const
dump - Print the current MachineFunction to cerr, useful for debugger use.
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...
AnalysisUsage & addRequired()
#define INITIALIZE_PASS_DEPENDENCY(depName)
Definition: PassSupport.h:50
MachineFunctionPass - This class adapts the FunctionPass interface to allow convenient creation of pa...
const HexagonInstrInfo * TII
unsigned getNumOperands() const
Retuns the total number of operands.
Definition: MachineInstr.h:414
A Use represents the edge between a Value definition and its users.
Definition: Use.h:55
void eraseFromParent()
Unlink &#39;this&#39; from the containing basic block and delete it.
void initializePPCBranchCoalescingPass(PassRegistry &)
Branch false
FunctionPass * createPPCBranchCoalescingPass()
createPPCBranchCoalescingPass - returns an instance of the Branch Coalescing Pass ...
#define DEBUG_TYPE
static void initialize(TargetLibraryInfoImpl &TLI, const Triple &T, ArrayRef< StringLiteral > StandardNames)
Initialize the set of available library functions based on the specified target triple.
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory)...
Definition: APInt.h:32
int getNumber() const
MachineBasicBlocks are uniquely numbered at the function level, unless they&#39;re not in a MachineFuncti...
virtual const TargetInstrInfo * getInstrInfo() const
bool isBranch(QueryType Type=AnyInBundle) const
Returns true if this is a conditional, unconditional, or indirect branch.
Definition: MachineInstr.h:675
TargetInstrInfo - Interface to description of machine instruction set.
bool isIdenticalTo(const MachineOperand &Other) const
Returns true if this operand is identical to the specified operand except for liveness related flags ...
unsigned const MachineRegisterInfo * MRI
const TargetSubtargetInfo & getSubtarget() const
getSubtarget - Return the subtarget for which this machine code is being compiled.
void getAnalysisUsage(AnalysisUsage &AU) const override
getAnalysisUsage - Subclasses that override getAnalysisUsage must call this.
size_t size() const
size - Get the array size.
Definition: ArrayRef.h:148
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
void setMBB(MachineBasicBlock *MBB)
Represent the analysis usage information of a pass.
iterator_range< mop_iterator > defs()
Returns a range over all explicit operands that are register definitions.
Definition: MachineInstr.h:499
FunctionPass class - This class is used to implement most global optimizations.
Definition: Pass.h:284
INITIALIZE_PASS_END(RegBankSelect, DEBUG_TYPE, "Assign register bank of generic virtual registers", false, false) RegBankSelect
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
PostDominatorTree Class - Concrete subclass of DominatorTree that is used to compute the post-dominat...
MachineOperand class - Representation of each machine instruction operand.
This is a &#39;vector&#39; (really, a variable-sized array), optimized for the case when the array is small...
Definition: SmallVector.h:837
const Function & getFunction() const
Return the LLVM function that this machine code represents.
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:132
Target - Wrapper for Target specific information.
static void clear(coro::Shape &Shape)
Definition: Coroutines.cpp:225
const MachineBasicBlock * getParent() const
Definition: MachineInstr.h:256
MachineRegisterInfo - Keep track of information for virtual and physical registers, including vreg register classes, use/def chains for registers, etc.
Representation of each machine instruction.
Definition: MachineInstr.h:64
INITIALIZE_PASS_BEGIN(PPCBranchCoalescing, DEBUG_TYPE, "Branch Coalescing", false, false) INITIALIZE_PASS_END(PPCBranchCoalescing
void splice(iterator Where, MachineBasicBlock *Other, iterator From)
Take an instruction from MBB &#39;Other&#39; at the position From, and insert it into this MBB right before &#39;...
MachineRegisterInfo & getRegInfo()
getRegInfo - Return information about the registers currently in use.
#define I(x, y, z)
Definition: MD5.cpp:58
iterator getFirstNonPHI()
Returns a pointer to the first instruction in this block that is not a PHINode instruction.
bool isReg() const
isReg - Tests if this is a MO_Register operand.
Branch Coalescing
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
static bool isVirtualRegister(unsigned Reg)
Return true if the specified register number is in the virtual register namespace.
Definition: Register.h:69
IRTranslator LLVM IR MI
StringRef - Represent a constant reference to a string, i.e.
Definition: StringRef.h:48
Register getReg() const
getReg - Returns the register number.
#define LLVM_DEBUG(X)
Definition: Debug.h:122
const MachineOperand & getOperand(unsigned i) const
Definition: MachineInstr.h:416
DominatorTree Class - Concrete subclass of DominatorTreeBase that is used to compute a normal dominat...