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
344  // If the physical register is constant then we can assume the value
345  // has not changed between uses.
346  && !(Op1.isUse() && MRI->isConstantPhysReg(Op1.getReg()))) {
347  LLVM_DEBUG(dbgs() << "The operands are not provably identical.\n");
348  return false;
349  }
350  LLVM_DEBUG(dbgs() << "Op1 and Op2 are identical!\n");
351  continue;
352  }
353 
354  // If the operands are not identical, but are registers, check to see if the
355  // definition of the register produces the same value. If they produce the
356  // same value, consider them to be identical.
357  if (Op1.isReg() && Op2.isReg() &&
360  MachineInstr *Op1Def = MRI->getVRegDef(Op1.getReg());
361  MachineInstr *Op2Def = MRI->getVRegDef(Op2.getReg());
362  if (TII->produceSameValue(*Op1Def, *Op2Def, MRI)) {
363  LLVM_DEBUG(dbgs() << "Op1Def: " << *Op1Def << " and " << *Op2Def
364  << " produce the same value!\n");
365  } else {
366  LLVM_DEBUG(dbgs() << "Operands produce different values\n");
367  return false;
368  }
369  } else {
370  LLVM_DEBUG(dbgs() << "The operands are not provably identical.\n");
371  return false;
372  }
373  }
374 
375  return true;
376 }
377 
378 ///
379 /// Moves ALL PHI instructions in SourceMBB to beginning of TargetMBB
380 /// and update them to refer to the new block. PHI node ordering
381 /// cannot be assumed so it does not matter where the PHI instructions
382 /// are moved to in TargetMBB.
383 ///
384 /// \param[in] SourceMBB block to move PHI instructions from
385 /// \param[in] TargetMBB block to move PHI instructions to
386 ///
387 void PPCBranchCoalescing::moveAndUpdatePHIs(MachineBasicBlock *SourceMBB,
388  MachineBasicBlock *TargetMBB) {
389 
390  MachineBasicBlock::iterator MI = SourceMBB->begin();
392 
393  if (MI == ME) {
394  LLVM_DEBUG(dbgs() << "SourceMBB contains no PHI instructions.\n");
395  return;
396  }
397 
398  // Update all PHI instructions in SourceMBB and move to top of TargetMBB
399  for (MachineBasicBlock::iterator Iter = MI; Iter != ME; Iter++) {
400  MachineInstr &PHIInst = *Iter;
401  for (unsigned i = 2, e = PHIInst.getNumOperands() + 1; i != e; i += 2) {
402  MachineOperand &MO = PHIInst.getOperand(i);
403  if (MO.getMBB() == SourceMBB)
404  MO.setMBB(TargetMBB);
405  }
406  }
407  TargetMBB->splice(TargetMBB->begin(), SourceMBB, MI, ME);
408 }
409 
410 ///
411 /// This function checks if MI can be moved to the beginning of the TargetMBB
412 /// following PHI instructions. A MI instruction can be moved to beginning of
413 /// the TargetMBB if there are no uses of it within the TargetMBB PHI nodes.
414 ///
415 /// \param[in] MI the machine instruction to move.
416 /// \param[in] TargetMBB the machine basic block to move to
417 /// \return true if it is safe to move MI to beginning of TargetMBB,
418 /// false otherwise.
419 ///
420 bool PPCBranchCoalescing::canMoveToBeginning(const MachineInstr &MI,
421  const MachineBasicBlock &TargetMBB
422  ) const {
423 
424  LLVM_DEBUG(dbgs() << "Checking if " << MI << " can move to beginning of "
425  << TargetMBB.getNumber() << "\n");
426 
427  for (auto &Def : MI.defs()) { // Looking at Def
428  for (auto &Use : MRI->use_instructions(Def.getReg())) {
429  if (Use.isPHI() && Use.getParent() == &TargetMBB) {
430  LLVM_DEBUG(dbgs() << " *** used in a PHI -- cannot move ***\n");
431  return false;
432  }
433  }
434  }
435 
436  LLVM_DEBUG(dbgs() << " Safe to move to the beginning.\n");
437  return true;
438 }
439 
440 ///
441 /// This function checks if MI can be moved to the end of the TargetMBB,
442 /// immediately before the first terminator. A MI instruction can be moved
443 /// to then end of the TargetMBB if no PHI node defines what MI uses within
444 /// it's own MBB.
445 ///
446 /// \param[in] MI the machine instruction to move.
447 /// \param[in] TargetMBB the machine basic block to move to
448 /// \return true if it is safe to move MI to end of TargetMBB,
449 /// false otherwise.
450 ///
451 bool PPCBranchCoalescing::canMoveToEnd(const MachineInstr &MI,
452  const MachineBasicBlock &TargetMBB
453  ) const {
454 
455  LLVM_DEBUG(dbgs() << "Checking if " << MI << " can move to end of "
456  << TargetMBB.getNumber() << "\n");
457 
458  for (auto &Use : MI.uses()) {
459  if (Use.isReg() && TargetRegisterInfo::isVirtualRegister(Use.getReg())) {
460  MachineInstr *DefInst = MRI->getVRegDef(Use.getReg());
461  if (DefInst->isPHI() && DefInst->getParent() == MI.getParent()) {
462  LLVM_DEBUG(dbgs() << " *** Cannot move this instruction ***\n");
463  return false;
464  } else {
465  LLVM_DEBUG(
466  dbgs() << " *** def is in another block -- safe to move!\n");
467  }
468  }
469  }
470 
471  LLVM_DEBUG(dbgs() << " Safe to move to the end.\n");
472  return true;
473 }
474 
475 ///
476 /// This method checks to ensure the two coalescing candidates follows the
477 /// expected pattern required for coalescing.
478 ///
479 /// \param[in] SourceRegion The candidate to move statements from
480 /// \param[in] TargetRegion The candidate to move statements to
481 /// \return true if all instructions in SourceRegion.BranchBlock can be merged
482 /// into a block in TargetRegion; false otherwise.
483 ///
484 bool PPCBranchCoalescing::validateCandidates(
485  CoalescingCandidateInfo &SourceRegion,
486  CoalescingCandidateInfo &TargetRegion) const {
487 
488  if (TargetRegion.BranchTargetBlock != SourceRegion.BranchBlock)
489  llvm_unreachable("Expecting SourceRegion to immediately follow TargetRegion");
490  else if (!MDT->dominates(TargetRegion.BranchBlock, SourceRegion.BranchBlock))
491  llvm_unreachable("Expecting TargetRegion to dominate SourceRegion");
492  else if (!MPDT->dominates(SourceRegion.BranchBlock, TargetRegion.BranchBlock))
493  llvm_unreachable("Expecting SourceRegion to post-dominate TargetRegion");
494  else if (!TargetRegion.FallThroughBlock->empty() ||
495  !SourceRegion.FallThroughBlock->empty())
496  llvm_unreachable("Expecting fall-through blocks to be empty");
497 
498  return true;
499 }
500 
501 ///
502 /// This method determines whether the two coalescing candidates can be merged.
503 /// In order to be merged, all instructions must be able to
504 /// 1. Move to the beginning of the SourceRegion.BranchTargetBlock;
505 /// 2. Move to the end of the TargetRegion.BranchBlock.
506 /// Merging involves moving the instructions in the
507 /// TargetRegion.BranchTargetBlock (also SourceRegion.BranchBlock).
508 ///
509 /// This function first try to move instructions from the
510 /// TargetRegion.BranchTargetBlock down, to the beginning of the
511 /// SourceRegion.BranchTargetBlock. This is not possible if any register defined
512 /// in TargetRegion.BranchTargetBlock is used in a PHI node in the
513 /// SourceRegion.BranchTargetBlock. In this case, check whether the statement
514 /// can be moved up, to the end of the TargetRegion.BranchBlock (immediately
515 /// before the branch statement). If it cannot move, then these blocks cannot
516 /// be merged.
517 ///
518 /// Note that there is no analysis for moving instructions past the fall-through
519 /// blocks because they are confirmed to be empty. An assert is thrown if they
520 /// are not.
521 ///
522 /// \param[in] SourceRegion The candidate to move statements from
523 /// \param[in] TargetRegion The candidate to move statements to
524 /// \return true if all instructions in SourceRegion.BranchBlock can be merged
525 /// into a block in TargetRegion, false otherwise.
526 ///
527 bool PPCBranchCoalescing::canMerge(CoalescingCandidateInfo &SourceRegion,
528  CoalescingCandidateInfo &TargetRegion) const {
529  if (!validateCandidates(SourceRegion, TargetRegion))
530  return false;
531 
532  // Walk through PHI nodes first and see if they force the merge into the
533  // SourceRegion.BranchTargetBlock.
535  I = SourceRegion.BranchBlock->instr_begin(),
536  E = SourceRegion.BranchBlock->getFirstNonPHI();
537  I != E; ++I) {
538  for (auto &Def : I->defs())
539  for (auto &Use : MRI->use_instructions(Def.getReg())) {
540  if (Use.isPHI() && Use.getParent() == SourceRegion.BranchTargetBlock) {
541  LLVM_DEBUG(dbgs()
542  << "PHI " << *I
543  << " defines register used in another "
544  "PHI within branch target block -- can't merge\n");
545  NumPHINotMoved++;
546  return false;
547  }
548  if (Use.getParent() == SourceRegion.BranchBlock) {
549  LLVM_DEBUG(dbgs() << "PHI " << *I
550  << " defines register used in this "
551  "block -- all must move down\n");
552  SourceRegion.MustMoveDown = true;
553  }
554  }
555  }
556 
557  // Walk through the MI to see if they should be merged into
558  // TargetRegion.BranchBlock (up) or SourceRegion.BranchTargetBlock (down)
560  I = SourceRegion.BranchBlock->getFirstNonPHI(),
561  E = SourceRegion.BranchBlock->end();
562  I != E; ++I) {
563  if (!canMoveToBeginning(*I, *SourceRegion.BranchTargetBlock)) {
564  LLVM_DEBUG(dbgs() << "Instruction " << *I
565  << " cannot move down - must move up!\n");
566  SourceRegion.MustMoveUp = true;
567  }
568  if (!canMoveToEnd(*I, *TargetRegion.BranchBlock)) {
569  LLVM_DEBUG(dbgs() << "Instruction " << *I
570  << " cannot move up - must move down!\n");
571  SourceRegion.MustMoveDown = true;
572  }
573  }
574 
575  return (SourceRegion.MustMoveUp && SourceRegion.MustMoveDown) ? false : true;
576 }
577 
578 /// Merge the instructions from SourceRegion.BranchBlock,
579 /// SourceRegion.BranchTargetBlock, and SourceRegion.FallThroughBlock into
580 /// TargetRegion.BranchBlock, TargetRegion.BranchTargetBlock and
581 /// TargetRegion.FallThroughBlock respectively.
582 ///
583 /// The successors for blocks in TargetRegion will be updated to use the
584 /// successors from blocks in SourceRegion. Finally, the blocks in SourceRegion
585 /// will be removed from the function.
586 ///
587 /// A region consists of a BranchBlock, a FallThroughBlock, and a
588 /// BranchTargetBlock. Branch coalesce works on patterns where the
589 /// TargetRegion's BranchTargetBlock must also be the SourceRegions's
590 /// BranchBlock.
591 ///
592 /// Before mergeCandidates:
593 ///
594 /// +---------------------------+
595 /// | TargetRegion.BranchBlock |
596 /// +---------------------------+
597 /// / |
598 /// / +--------------------------------+
599 /// | | TargetRegion.FallThroughBlock |
600 /// \ +--------------------------------+
601 /// \ |
602 /// +----------------------------------+
603 /// | TargetRegion.BranchTargetBlock |
604 /// | SourceRegion.BranchBlock |
605 /// +----------------------------------+
606 /// / |
607 /// / +--------------------------------+
608 /// | | SourceRegion.FallThroughBlock |
609 /// \ +--------------------------------+
610 /// \ |
611 /// +----------------------------------+
612 /// | SourceRegion.BranchTargetBlock |
613 /// +----------------------------------+
614 ///
615 /// After mergeCandidates:
616 ///
617 /// +-----------------------------+
618 /// | TargetRegion.BranchBlock |
619 /// | SourceRegion.BranchBlock |
620 /// +-----------------------------+
621 /// / |
622 /// / +---------------------------------+
623 /// | | TargetRegion.FallThroughBlock |
624 /// | | SourceRegion.FallThroughBlock |
625 /// \ +---------------------------------+
626 /// \ |
627 /// +----------------------------------+
628 /// | SourceRegion.BranchTargetBlock |
629 /// +----------------------------------+
630 ///
631 /// \param[in] SourceRegion The candidate to move blocks from
632 /// \param[in] TargetRegion The candidate to move blocks to
633 ///
634 bool PPCBranchCoalescing::mergeCandidates(CoalescingCandidateInfo &SourceRegion,
635  CoalescingCandidateInfo &TargetRegion) {
636 
637  if (SourceRegion.MustMoveUp && SourceRegion.MustMoveDown) {
638  llvm_unreachable("Cannot have both MustMoveDown and MustMoveUp set!");
639  return false;
640  }
641 
642  if (!validateCandidates(SourceRegion, TargetRegion))
643  return false;
644 
645  // Start the merging process by first handling the BranchBlock.
646  // Move any PHIs in SourceRegion.BranchBlock down to the branch-taken block
647  moveAndUpdatePHIs(SourceRegion.BranchBlock, SourceRegion.BranchTargetBlock);
648 
649  // Move remaining instructions in SourceRegion.BranchBlock into
650  // TargetRegion.BranchBlock
651  MachineBasicBlock::iterator firstInstr =
652  SourceRegion.BranchBlock->getFirstNonPHI();
653  MachineBasicBlock::iterator lastInstr =
654  SourceRegion.BranchBlock->getFirstTerminator();
655 
656  MachineBasicBlock *Source = SourceRegion.MustMoveDown
657  ? SourceRegion.BranchTargetBlock
658  : TargetRegion.BranchBlock;
659 
661  SourceRegion.MustMoveDown
662  ? SourceRegion.BranchTargetBlock->getFirstNonPHI()
663  : TargetRegion.BranchBlock->getFirstTerminator();
664 
665  Source->splice(Target, SourceRegion.BranchBlock, firstInstr, lastInstr);
666 
667  // Once PHI and instructions have been moved we need to clean up the
668  // control flow.
669 
670  // Remove SourceRegion.FallThroughBlock before transferring successors of
671  // SourceRegion.BranchBlock to TargetRegion.BranchBlock.
672  SourceRegion.BranchBlock->removeSuccessor(SourceRegion.FallThroughBlock);
673  TargetRegion.BranchBlock->transferSuccessorsAndUpdatePHIs(
674  SourceRegion.BranchBlock);
675  // Update branch in TargetRegion.BranchBlock to jump to
676  // SourceRegion.BranchTargetBlock
677  // In this case, TargetRegion.BranchTargetBlock == SourceRegion.BranchBlock.
678  TargetRegion.BranchBlock->ReplaceUsesOfBlockWith(
679  SourceRegion.BranchBlock, SourceRegion.BranchTargetBlock);
680  // Remove the branch statement(s) in SourceRegion.BranchBlock
682  SourceRegion.BranchBlock->terminators().begin();
683  while (I != SourceRegion.BranchBlock->terminators().end()) {
684  MachineInstr &CurrInst = *I;
685  ++I;
686  if (CurrInst.isBranch())
687  CurrInst.eraseFromParent();
688  }
689 
690  // Fall-through block should be empty since this is part of the condition
691  // to coalesce the branches.
692  assert(TargetRegion.FallThroughBlock->empty() &&
693  "FallThroughBlocks should be empty!");
694 
695  // Transfer successor information and move PHIs down to the
696  // branch-taken block.
697  TargetRegion.FallThroughBlock->transferSuccessorsAndUpdatePHIs(
698  SourceRegion.FallThroughBlock);
699  TargetRegion.FallThroughBlock->removeSuccessor(SourceRegion.BranchBlock);
700 
701  // Remove the blocks from the function.
702  assert(SourceRegion.BranchBlock->empty() &&
703  "Expecting branch block to be empty!");
704  SourceRegion.BranchBlock->eraseFromParent();
705 
706  assert(SourceRegion.FallThroughBlock->empty() &&
707  "Expecting fall-through block to be empty!\n");
708  SourceRegion.FallThroughBlock->eraseFromParent();
709 
710  NumBlocksCoalesced++;
711  return true;
712 }
713 
714 bool PPCBranchCoalescing::runOnMachineFunction(MachineFunction &MF) {
715 
716  if (skipFunction(MF.getFunction()) || MF.empty())
717  return false;
718 
719  bool didSomething = false;
720 
721  LLVM_DEBUG(dbgs() << "******** Branch Coalescing ********\n");
722  initialize(MF);
723 
724  LLVM_DEBUG(dbgs() << "Function: "; MF.dump(); dbgs() << "\n");
725 
726  CoalescingCandidateInfo Cand1, Cand2;
727  // Walk over blocks and find candidates to merge
728  // Continue trying to merge with the first candidate found, as long as merging
729  // is successfull.
730  for (MachineBasicBlock &MBB : MF) {
731  bool MergedCandidates = false;
732  do {
733  MergedCandidates = false;
734  Cand1.clear();
735  Cand2.clear();
736 
737  Cand1.BranchBlock = &MBB;
738 
739  // If unable to coalesce the branch, then continue to next block
740  if (!canCoalesceBranch(Cand1))
741  break;
742 
743  Cand2.BranchBlock = Cand1.BranchTargetBlock;
744  if (!canCoalesceBranch(Cand2))
745  break;
746 
747  // Sanity check
748  // The branch-taken block of the second candidate should post-dominate the
749  // first candidate
750  assert(MPDT->dominates(Cand2.BranchTargetBlock, Cand1.BranchBlock) &&
751  "Branch-taken block should post-dominate first candidate");
752 
753  if (!identicalOperands(Cand1.Cond, Cand2.Cond)) {
754  LLVM_DEBUG(dbgs() << "Blocks " << Cand1.BranchBlock->getNumber()
755  << " and " << Cand2.BranchBlock->getNumber()
756  << " have different branches\n");
757  break;
758  }
759  if (!canMerge(Cand2, Cand1)) {
760  LLVM_DEBUG(dbgs() << "Cannot merge blocks "
761  << Cand1.BranchBlock->getNumber() << " and "
762  << Cand2.BranchBlock->getNumber() << "\n");
763  NumBlocksNotCoalesced++;
764  continue;
765  }
766  LLVM_DEBUG(dbgs() << "Merging blocks " << Cand1.BranchBlock->getNumber()
767  << " and " << Cand1.BranchTargetBlock->getNumber()
768  << "\n");
769  MergedCandidates = mergeCandidates(Cand2, Cand1);
770  if (MergedCandidates)
771  didSomething = true;
772 
773  LLVM_DEBUG(dbgs() << "Function after merging: "; MF.dump();
774  dbgs() << "\n");
775  } while (MergedCandidates);
776  }
777 
778 #ifndef NDEBUG
779  // Verify MF is still valid after branch coalescing
780  if (didSomething)
781  MF.verify(nullptr, "Error in code produced by branch coalescing");
782 #endif // NDEBUG
783 
784  LLVM_DEBUG(dbgs() << "Finished Branch Coalescing\n");
785  return didSomething;
786 }
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:494
static bool isVirtualRegister(unsigned Reg)
Return true if the specified register number is in the virtual register namespace.
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
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:659
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:483
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 initialize(TargetLibraryInfoImpl &TLI, const Triple &T, ArrayRef< StringRef > StandardNames)
Initialize the set of available library functions based on the specified target triple.
static void clear(coro::Shape &Shape)
Definition: Coroutines.cpp:211
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
static bool isPhysicalRegister(unsigned Reg)
Return true if the specified register number is in the physical register namespace.
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())
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...