contrib/llvm-project/llvm/lib/Target/PowerPC/PPCBranchCoalescing.cpp

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