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