contrib/llvm/lib/CodeGen/BranchCoalescing.cpp

   1 //===-- CoalesceBranches.cpp - Coalesce blocks with the same condition ---===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file is distributed under the University of Illinois Open Source
   6 // License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 ///
  10 /// \file
  11 /// Coalesce basic blocks guarded by the same branch condition into a single
  12 /// basic block.
  13 ///
  14 //===----------------------------------------------------------------------===//
  15
  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/Support/Debug.h"
  24 #include "llvm/Target/TargetFrameLowering.h"
  25 #include "llvm/Target/TargetInstrInfo.h"
  26 #include "llvm/Target/TargetSubtargetInfo.h"
  27
  28 using namespace llvm;
  29
  30 #define DEBUG_TYPE "branch-coalescing"
  31
  32 static cl::opt<cl::boolOrDefault>
  33     EnableBranchCoalescing("enable-branch-coalesce", cl::Hidden,
  34                            cl::desc("enable coalescing of duplicate branches"));
  35
  36 STATISTIC(NumBlocksCoalesced, "Number of blocks coalesced");
  37 STATISTIC(NumPHINotMoved, "Number of PHI Nodes that cannot be merged");
  38 STATISTIC(NumBlocksNotCoalesced, "Number of blocks not coalesced");
  39
  40 //===----------------------------------------------------------------------===//
  41 //                               BranchCoalescing
  42 //===----------------------------------------------------------------------===//
  43 ///
  44 /// Improve scheduling by coalescing branches that depend on the same condition.
  45 /// This pass looks for blocks that are guarded by the same branch condition
  46 /// and attempts to merge the blocks together. Such opportunities arise from
  47 /// the expansion of select statements in the IR.
  48 ///
  49 /// For example, consider 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 /// This IR expands to the following machine code on PowerPC:
  56 ///
  57 /// BB#0: derived from LLVM BB %entry
  58 ///    Live Ins: %F1 %F3 %X6
  59 ///        <SNIP1>
  60 ///        %vreg0<def> = COPY %F1; F8RC:%vreg0
  61 ///        %vreg5<def> = CMPLWI %vreg4<kill>, 0; CRRC:%vreg5 GPRC:%vreg4
  62 ///        %vreg8<def> = LXSDX %ZERO8, %vreg7<kill>, %RM<imp-use>;
  63 ///                    mem:LD8[ConstantPool] F8RC:%vreg8 G8RC:%vreg7
  64 ///        BCC 76, %vreg5, <BB#2>; CRRC:%vreg5
  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 ///        %vreg9<def> = PHI %vreg8, <BB#1>, %vreg0, <BB#0>;
  74 ///                    F8RC:%vreg9,%vreg8,%vreg0
  75 ///        <SNIP2>
  76 ///        BCC 76, %vreg5, <BB#4>; CRRC:%vreg5
  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 ///        %vreg13<def> = PHI %vreg12, <BB#3>, %vreg2, <BB#2>;
  86 ///                     F8RC:%vreg13,%vreg12,%vreg2
  87 ///        <SNIP3>
  88 ///        BLR8 %LR8<imp-use>, %RM<imp-use>, %F1<imp-use>
  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 ///    Live Ins: %F1 %F3 %X6
  97 ///        <SNIP1>
  98 ///        %vreg0<def> = COPY %F1; F8RC:%vreg0
  99 ///        %vreg5<def> = CMPLWI %vreg4<kill>, 0; CRRC:%vreg5 GPRC:%vreg4
 100 ///        %vreg8<def> = LXSDX %ZERO8, %vreg7<kill>, %RM<imp-use>;
 101 ///                     mem:LD8[ConstantPool] F8RC:%vreg8 G8RC:%vreg7
 102 ///        <SNIP2>
 103 ///        BCC 76, %vreg5, <BB#4>; CRRC:%vreg5
 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 ///        %vreg9<def> = PHI %vreg8, <BB#1>, %vreg0, <BB#0>;
 114 ///                    F8RC:%vreg9,%vreg8,%vreg0
 115 ///        %vreg13<def> = PHI %vreg12, <BB#1>, %vreg2, <BB#0>;
 116 ///                     F8RC:%vreg13,%vreg12,%vreg2
 117 ///        <SNIP3>
 118 ///        BLR8 %LR8<imp-use>, %RM<imp-use>, %F1<imp-use>
 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 BranchCoalescing : 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
 140     SmallVector<MachineOperand, 4> Cond;
 141     bool MustMoveDown;
 142     bool MustMoveUp;
 143
 144     CoalescingCandidateInfo();
 145     void clear();
 146   };
 147
 148   MachineDominatorTree *MDT;
 149   MachinePostDominatorTree *MPDT;
 150   const TargetInstrInfo *TII;
 151   MachineRegisterInfo *MRI;
 152
 153   void initialize(MachineFunction &F);
 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   static bool isBranchCoalescingEnabled() {
 161     return EnableBranchCoalescing == cl::BOU_TRUE;
 162   }
 163
 164 public:
 165   static char ID;
 166
 167   BranchCoalescing() : MachineFunctionPass(ID) {
 168     initializeBranchCoalescingPass(*PassRegistry::getPassRegistry());
 169   }
 170
 171   void getAnalysisUsage(AnalysisUsage &AU) const override {
 172     AU.addRequired<MachineDominatorTree>();
 173     AU.addRequired<MachinePostDominatorTree>();
 174     MachineFunctionPass::getAnalysisUsage(AU);
 175   }
 176
 177   StringRef getPassName() const override { return "Branch Coalescing"; }
 178
 179   bool mergeCandidates(CoalescingCandidateInfo &SourceRegion,
 180                        CoalescingCandidateInfo &TargetRegion);
 181   bool canMoveToBeginning(const MachineInstr &MI,
 182                           const MachineBasicBlock &MBB) const;
 183   bool canMoveToEnd(const MachineInstr &MI,
 184                     const MachineBasicBlock &MBB) const;
 185   bool canMerge(CoalescingCandidateInfo &SourceRegion,
 186                 CoalescingCandidateInfo &TargetRegion) const;
 187   void moveAndUpdatePHIs(MachineBasicBlock *SourceRegionMBB,
 188                          MachineBasicBlock *TargetRegionMBB);
 189   bool runOnMachineFunction(MachineFunction &MF) override;
 190 };
 191 } // End anonymous namespace.
 192
 193 char BranchCoalescing::ID = 0;
 194 char &llvm::BranchCoalescingID = BranchCoalescing::ID;
 195
 196 INITIALIZE_PASS_BEGIN(BranchCoalescing, DEBUG_TYPE,
 197                       "Branch Coalescing", false, false)
 198 INITIALIZE_PASS_DEPENDENCY(MachineDominatorTree)
 199 INITIALIZE_PASS_DEPENDENCY(MachinePostDominatorTree)
 200 INITIALIZE_PASS_END(BranchCoalescing, DEBUG_TYPE, "Branch Coalescing",
 201                     false, false)
 202
 203 BranchCoalescing::CoalescingCandidateInfo::CoalescingCandidateInfo()
 204     : BranchBlock(nullptr), BranchTargetBlock(nullptr),
 205       FallThroughBlock(nullptr), MustMoveDown(false), MustMoveUp(false) {}
 206
 207 void BranchCoalescing::CoalescingCandidateInfo::clear() {
 208   BranchBlock = nullptr;
 209   BranchTargetBlock = nullptr;
 210   FallThroughBlock = nullptr;
 211   Cond.clear();
 212   MustMoveDown = false;
 213   MustMoveUp = false;
 214 }
 215
 216 void BranchCoalescing::initialize(MachineFunction &MF) {
 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 BranchCoalescing::canCoalesceBranch(CoalescingCandidateInfo &Cand) {
 234   DEBUG(dbgs() << "Determine if branch block " << Cand.BranchBlock->getNumber()
 235                << " can be coalesced:");
 236   MachineBasicBlock *FalseMBB = nullptr;
 237
 238   if (TII->analyzeBranch(*Cand.BranchBlock, Cand.BranchTargetBlock, FalseMBB,
 239                          Cand.Cond)) {
 240     DEBUG(dbgs() << "TII unable to Analyze Branch - skip\n");
 241     return false;
 242   }
 243
 244   for (auto &I : Cand.BranchBlock->terminators()) {
 245     DEBUG(dbgs() << "Looking at terminator : " << I << "\n");
 246     if (!I.isBranch())
 247       continue;
 248
 249     if (I.getNumOperands() != I.getNumExplicitOperands()) {
 250       DEBUG(dbgs() << "Terminator contains implicit operands - skip : " << I
 251                    << "\n");
 252       return false;
 253     }
 254   }
 255
 256   if (Cand.BranchBlock->isEHPad() || Cand.BranchBlock->hasEHPadSuccessor()) {
 257     DEBUG(dbgs() << "EH Pad - skip\n");
 258     return false;
 259   }
 260
 261   // For now only consider triangles (i.e, BranchTargetBlock is set,
 262   // FalseMBB is null, and BranchTargetBlock is a successor to BranchBlock)
 263   if (!Cand.BranchTargetBlock || FalseMBB ||
 264       !Cand.BranchBlock->isSuccessor(Cand.BranchTargetBlock)) {
 265     DEBUG(dbgs() << "Does not form a triangle - skip\n");
 266     return false;
 267   }
 268
 269   // Ensure there are only two successors
 270   if (Cand.BranchBlock->succ_size() != 2) {
 271     DEBUG(dbgs() << "Does not have 2 successors - skip\n");
 272     return false;
 273   }
 274
 275   // Sanity check - the block must be able to fall through
 276   assert(Cand.BranchBlock->canFallThrough() &&
 277          "Expecting the block to fall through!");
 278
 279   // We have already ensured there are exactly two successors to
 280   // BranchBlock and that BranchTargetBlock is a successor to BranchBlock.
 281   // Ensure the single fall though block is empty.
 282   MachineBasicBlock *Succ =
 283     (*Cand.BranchBlock->succ_begin() == Cand.BranchTargetBlock)
 284     ? *Cand.BranchBlock->succ_rbegin()
 285     : *Cand.BranchBlock->succ_begin();
 286
 287   assert(Succ && "Expecting a valid fall-through block\n");
 288
 289   if (!Succ->empty()) {
 290       DEBUG(dbgs() << "Fall-through block contains code -- skip\n");
 291       return false;
 292   }
 293
 294   if (!Succ->isSuccessor(Cand.BranchTargetBlock)) {
 295       DEBUG(dbgs()
 296             << "Successor of fall through block is not branch taken block\n");
 297       return false;
 298   }
 299
 300   Cand.FallThroughBlock = Succ;
 301   DEBUG(dbgs() << "Valid Candidate\n");
 302   return true;
 303 }
 304
 305 ///
 306 /// Determine if the two operand lists are identical
 307 ///
 308 /// \param[in] OpList1 operand list
 309 /// \param[in] OpList2 operand list
 310 /// \return true if and only if the operands lists are identical
 311 ///
 312 bool BranchCoalescing::identicalOperands(
 313     ArrayRef<MachineOperand> OpList1, ArrayRef<MachineOperand> OpList2) const {
 314
 315   if (OpList1.size() != OpList2.size()) {
 316     DEBUG(dbgs() << "Operand list is different size\n");
 317     return false;
 318   }
 319
 320   for (unsigned i = 0; i < OpList1.size(); ++i) {
 321     const MachineOperand &Op1 = OpList1[i];
 322     const MachineOperand &Op2 = OpList2[i];
 323
 324     DEBUG(dbgs() << "Op1: " << Op1 << "\n"
 325                  << "Op2: " << Op2 << "\n");
 326
 327     if (Op1.isIdenticalTo(Op2)) {
 328       DEBUG(dbgs() << "Op1 and Op2 are identical!\n");
 329       continue;
 330     }
 331
 332     // If the operands are not identical, but are registers, check to see if the
 333     // definition of the register produces the same value. If they produce the
 334     // same value, consider them to be identical.
 335     if (Op1.isReg() && Op2.isReg() &&
 336         TargetRegisterInfo::isVirtualRegister(Op1.getReg()) &&
 337         TargetRegisterInfo::isVirtualRegister(Op2.getReg())) {
 338       MachineInstr *Op1Def = MRI->getVRegDef(Op1.getReg());
 339       MachineInstr *Op2Def = MRI->getVRegDef(Op2.getReg());
 340       if (TII->produceSameValue(*Op1Def, *Op2Def, MRI)) {
 341         DEBUG(dbgs() << "Op1Def: " << *Op1Def << " and " << *Op2Def
 342                      << " produce the same value!\n");
 343       } else {
 344         DEBUG(dbgs() << "Operands produce different values\n");
 345         return false;
 346       }
 347     } else {
 348       DEBUG(dbgs() << "The operands are not provably identical.\n");
 349       return false;
 350     }
 351   }
 352   return true;
 353 }
 354
 355 ///
 356 /// Moves ALL PHI instructions in SourceMBB to beginning of TargetMBB
 357 /// and update them to refer to the new block.  PHI node ordering
 358 /// cannot be assumed so it does not matter where the PHI instructions
 359 /// are moved to in TargetMBB.
 360 ///
 361 /// \param[in] SourceMBB block to move PHI instructions from
 362 /// \param[in] TargetMBB block to move PHI instructions to
 363 ///
 364 void BranchCoalescing::moveAndUpdatePHIs(MachineBasicBlock *SourceMBB,
 365                                          MachineBasicBlock *TargetMBB) {
 366
 367   MachineBasicBlock::iterator MI = SourceMBB->begin();
 368   MachineBasicBlock::iterator ME = SourceMBB->getFirstNonPHI();
 369
 370   if (MI == ME) {
 371     DEBUG(dbgs() << "SourceMBB contains no PHI instructions.\n");
 372     return;
 373   }
 374
 375   // Update all PHI instructions in SourceMBB and move to top of TargetMBB
 376   for (MachineBasicBlock::iterator Iter = MI; Iter != ME; Iter++) {
 377     MachineInstr &PHIInst = *Iter;
 378     for (unsigned i = 2, e = PHIInst.getNumOperands() + 1; i != e; i += 2) {
 379       MachineOperand &MO = PHIInst.getOperand(i);
 380       if (MO.getMBB() == SourceMBB)
 381         MO.setMBB(TargetMBB);
 382     }
 383   }
 384   TargetMBB->splice(TargetMBB->begin(), SourceMBB, MI, ME);
 385 }
 386
 387 ///
 388 /// This function checks if MI can be moved to the beginning of the TargetMBB
 389 /// following PHI instructions. A MI instruction can be moved to beginning of
 390 /// the TargetMBB if there are no uses of it within the TargetMBB PHI nodes.
 391 ///
 392 /// \param[in] MI the machine instruction to move.
 393 /// \param[in] TargetMBB the machine basic block to move to
 394 /// \return true if it is safe to move MI to beginning of TargetMBB,
 395 ///         false otherwise.
 396 ///
 397 bool BranchCoalescing::canMoveToBeginning(const MachineInstr &MI,
 398                                           const MachineBasicBlock &TargetMBB
 399                                           ) const {
 400
 401   DEBUG(dbgs() << "Checking if " << MI << " can move to beginning of "
 402         << TargetMBB.getNumber() << "\n");
 403
 404   for (auto &Def : MI.defs()) { // Looking at Def
 405     for (auto &Use : MRI->use_instructions(Def.getReg())) {
 406       if (Use.isPHI() && Use.getParent() == &TargetMBB) {
 407         DEBUG(dbgs() << "    *** used in a PHI -- cannot move ***\n");
 408        return false;
 409       }
 410     }
 411   }
 412
 413   DEBUG(dbgs() << "  Safe to move to the beginning.\n");
 414   return true;
 415 }
 416
 417 ///
 418 /// This function checks if MI can be moved to the end of the TargetMBB,
 419 /// immediately before the first terminator.  A MI instruction can be moved
 420 /// to then end of the TargetMBB if no PHI node defines what MI uses within
 421 /// it's own MBB.
 422 ///
 423 /// \param[in] MI the machine instruction to move.
 424 /// \param[in] TargetMBB the machine basic block to move to
 425 /// \return true if it is safe to move MI to end of TargetMBB,
 426 ///         false otherwise.
 427 ///
 428 bool BranchCoalescing::canMoveToEnd(const MachineInstr &MI,
 429                                     const MachineBasicBlock &TargetMBB
 430                                     ) const {
 431
 432   DEBUG(dbgs() << "Checking if " << MI << " can move to end of "
 433         << TargetMBB.getNumber() << "\n");
 434
 435   for (auto &Use : MI.uses()) {
 436     if (Use.isReg() && TargetRegisterInfo::isVirtualRegister(Use.getReg())) {
 437       MachineInstr *DefInst = MRI->getVRegDef(Use.getReg());
 438       if (DefInst->isPHI() && DefInst->getParent() == MI.getParent()) {
 439         DEBUG(dbgs() << "    *** Cannot move this instruction ***\n");
 440         return false;
 441       } else {
 442         DEBUG(dbgs() << "    *** def is in another block -- safe to move!\n");
 443       }
 444     }
 445   }
 446
 447   DEBUG(dbgs() << "  Safe to move to the end.\n");
 448   return true;
 449 }
 450
 451 ///
 452 /// This method checks to ensure the two coalescing candidates follows the
 453 /// expected pattern required for coalescing.
 454 ///
 455 /// \param[in] SourceRegion The candidate to move statements from
 456 /// \param[in] TargetRegion The candidate to move statements to
 457 /// \return true if all instructions in SourceRegion.BranchBlock can be merged
 458 /// into a block in TargetRegion; false otherwise.
 459 ///
 460 bool BranchCoalescing::validateCandidates(
 461     CoalescingCandidateInfo &SourceRegion,
 462     CoalescingCandidateInfo &TargetRegion) const {
 463
 464   if (TargetRegion.BranchTargetBlock != SourceRegion.BranchBlock)
 465     llvm_unreachable("Expecting SourceRegion to immediately follow TargetRegion");
 466   else if (!MDT->dominates(TargetRegion.BranchBlock, SourceRegion.BranchBlock))
 467     llvm_unreachable("Expecting TargetRegion to dominate SourceRegion");
 468   else if (!MPDT->dominates(SourceRegion.BranchBlock, TargetRegion.BranchBlock))
 469     llvm_unreachable("Expecting SourceRegion to post-dominate TargetRegion");
 470   else if (!TargetRegion.FallThroughBlock->empty() ||
 471            !SourceRegion.FallThroughBlock->empty())
 472     llvm_unreachable("Expecting fall-through blocks to be empty");
 473
 474   return true;
 475 }
 476
 477 ///
 478 /// This method determines whether the two coalescing candidates can be merged.
 479 /// In order to be merged, all instructions must be able to
 480 ///   1. Move to the beginning of the SourceRegion.BranchTargetBlock;
 481 ///   2. Move to the end of the TargetRegion.BranchBlock.
 482 /// Merging involves moving the instructions in the
 483 /// TargetRegion.BranchTargetBlock (also SourceRegion.BranchBlock).
 484 ///
 485 /// This function first try to move instructions from the
 486 /// TargetRegion.BranchTargetBlock down, to the beginning of the
 487 /// SourceRegion.BranchTargetBlock. This is not possible if any register defined
 488 /// in TargetRegion.BranchTargetBlock is used in a PHI node in the
 489 /// SourceRegion.BranchTargetBlock. In this case, check whether the statement
 490 /// can be moved up, to the end of the TargetRegion.BranchBlock (immediately
 491 /// before the branch statement). If it cannot move, then these blocks cannot
 492 /// be merged.
 493 ///
 494 /// Note that there is no analysis for moving instructions past the fall-through
 495 /// blocks because they are confirmed to be empty. An assert is thrown if they
 496 /// are not.
 497 ///
 498 /// \param[in] SourceRegion The candidate to move statements from
 499 /// \param[in] TargetRegion The candidate to move statements to
 500 /// \return true if all instructions in SourceRegion.BranchBlock can be merged
 501 ///         into a block in TargetRegion, false otherwise.
 502 ///
 503 bool BranchCoalescing::canMerge(CoalescingCandidateInfo &SourceRegion,
 504                                 CoalescingCandidateInfo &TargetRegion) const {
 505   if (!validateCandidates(SourceRegion, TargetRegion))
 506     return false;
 507
 508   // Walk through PHI nodes first and see if they force the merge into the
 509   // SourceRegion.BranchTargetBlock.
 510   for (MachineBasicBlock::iterator
 511            I = SourceRegion.BranchBlock->instr_begin(),
 512            E = SourceRegion.BranchBlock->getFirstNonPHI();
 513        I != E; ++I) {
 514     for (auto &Def : I->defs())
 515       for (auto &Use : MRI->use_instructions(Def.getReg())) {
 516         if (Use.isPHI() && Use.getParent() == SourceRegion.BranchTargetBlock) {
 517           DEBUG(dbgs() << "PHI " << *I << " defines register used in another "
 518                           "PHI within branch target block -- can't merge\n");
 519           NumPHINotMoved++;
 520           return false;
 521         }
 522         if (Use.getParent() == SourceRegion.BranchBlock) {
 523           DEBUG(dbgs() << "PHI " << *I
 524                        << " defines register used in this "
 525                           "block -- all must move down\n");
 526           SourceRegion.MustMoveDown = true;
 527         }
 528       }
 529   }
 530
 531   // Walk through the MI to see if they should be merged into
 532   // TargetRegion.BranchBlock (up) or SourceRegion.BranchTargetBlock (down)
 533   for (MachineBasicBlock::iterator
 534            I = SourceRegion.BranchBlock->getFirstNonPHI(),
 535            E = SourceRegion.BranchBlock->end();
 536        I != E; ++I) {
 537     if (!canMoveToBeginning(*I, *SourceRegion.BranchTargetBlock)) {
 538       DEBUG(dbgs() << "Instruction " << *I
 539                    << " cannot move down - must move up!\n");
 540       SourceRegion.MustMoveUp = true;
 541     }
 542     if (!canMoveToEnd(*I, *TargetRegion.BranchBlock)) {
 543       DEBUG(dbgs() << "Instruction " << *I
 544                    << " cannot move up - must move down!\n");
 545       SourceRegion.MustMoveDown = true;
 546     }
 547   }
 548
 549   return (SourceRegion.MustMoveUp && SourceRegion.MustMoveDown) ? false : true;
 550 }
 551
 552 /// Merge the instructions from SourceRegion.BranchBlock,
 553 /// SourceRegion.BranchTargetBlock, and SourceRegion.FallThroughBlock into
 554 /// TargetRegion.BranchBlock, TargetRegion.BranchTargetBlock and
 555 /// TargetRegion.FallThroughBlock respectively.
 556 ///
 557 /// The successors for blocks in TargetRegion will be updated to use the
 558 /// successors from blocks in SourceRegion. Finally, the blocks in SourceRegion
 559 /// will be removed from the function.
 560 ///
 561 /// A region consists of a BranchBlock, a FallThroughBlock, and a
 562 /// BranchTargetBlock. Branch coalesce works on patterns where the
 563 /// TargetRegion's BranchTargetBlock must also be the SourceRegions's
 564 /// BranchBlock.
 565 ///
 566 ///  Before mergeCandidates:
 567 ///
 568 ///  +---------------------------+
 569 ///  |  TargetRegion.BranchBlock |
 570 ///  +---------------------------+
 571 ///     /        |
 572 ///    /   +--------------------------------+
 573 ///   |    |  TargetRegion.FallThroughBlock |
 574 ///    \   +--------------------------------+
 575 ///     \        |
 576 ///  +----------------------------------+
 577 ///  |  TargetRegion.BranchTargetBlock  |
 578 ///  |  SourceRegion.BranchBlock        |
 579 ///  +----------------------------------+
 580 ///     /        |
 581 ///    /   +--------------------------------+
 582 ///   |    |  SourceRegion.FallThroughBlock |
 583 ///    \   +--------------------------------+
 584 ///     \        |
 585 ///  +----------------------------------+
 586 ///  |  SourceRegion.BranchTargetBlock  |
 587 ///  +----------------------------------+
 588 ///
 589 ///  After mergeCandidates:
 590 ///
 591 ///  +-----------------------------+
 592 ///  |  TargetRegion.BranchBlock   |
 593 ///  |  SourceRegion.BranchBlock   |
 594 ///  +-----------------------------+
 595 ///     /        |
 596 ///    /   +---------------------------------+
 597 ///   |    |  TargetRegion.FallThroughBlock  |
 598 ///   |    |  SourceRegion.FallThroughBlock  |
 599 ///    \   +---------------------------------+
 600 ///     \        |
 601 ///  +----------------------------------+
 602 ///  |  SourceRegion.BranchTargetBlock  |
 603 ///  +----------------------------------+
 604 ///
 605 /// \param[in] SourceRegion The candidate to move blocks from
 606 /// \param[in] TargetRegion The candidate to move blocks to
 607 ///
 608 bool BranchCoalescing::mergeCandidates(CoalescingCandidateInfo &SourceRegion,
 609                                        CoalescingCandidateInfo &TargetRegion) {
 610
 611   if (SourceRegion.MustMoveUp && SourceRegion.MustMoveDown) {
 612     llvm_unreachable("Cannot have both MustMoveDown and MustMoveUp set!");
 613     return false;
 614   }
 615
 616   if (!validateCandidates(SourceRegion, TargetRegion))
 617     return false;
 618
 619   // Start the merging process by first handling the BranchBlock.
 620   // Move any PHIs in SourceRegion.BranchBlock down to the branch-taken block
 621   moveAndUpdatePHIs(SourceRegion.BranchBlock, SourceRegion.BranchTargetBlock);
 622
 623   // Move remaining instructions in SourceRegion.BranchBlock into
 624   // TargetRegion.BranchBlock
 625   MachineBasicBlock::iterator firstInstr =
 626       SourceRegion.BranchBlock->getFirstNonPHI();
 627   MachineBasicBlock::iterator lastInstr =
 628       SourceRegion.BranchBlock->getFirstTerminator();
 629
 630   MachineBasicBlock *Source = SourceRegion.MustMoveDown
 631                                   ? SourceRegion.BranchTargetBlock
 632                                   : TargetRegion.BranchBlock;
 633
 634   MachineBasicBlock::iterator Target =
 635       SourceRegion.MustMoveDown
 636           ? SourceRegion.BranchTargetBlock->getFirstNonPHI()
 637           : TargetRegion.BranchBlock->getFirstTerminator();
 638
 639   Source->splice(Target, SourceRegion.BranchBlock, firstInstr, lastInstr);
 640
 641   // Once PHI and instructions have been moved we need to clean up the
 642   // control flow.
 643
 644   // Remove SourceRegion.FallThroughBlock before transferring successors of
 645   // SourceRegion.BranchBlock to TargetRegion.BranchBlock.
 646   SourceRegion.BranchBlock->removeSuccessor(SourceRegion.FallThroughBlock);
 647   TargetRegion.BranchBlock->transferSuccessorsAndUpdatePHIs(
 648       SourceRegion.BranchBlock);
 649   // Update branch in TargetRegion.BranchBlock to jump to
 650   // SourceRegion.BranchTargetBlock
 651   // In this case, TargetRegion.BranchTargetBlock == SourceRegion.BranchBlock.
 652   TargetRegion.BranchBlock->ReplaceUsesOfBlockWith(
 653       SourceRegion.BranchBlock, SourceRegion.BranchTargetBlock);
 654   // Remove the branch statement(s) in SourceRegion.BranchBlock
 655   MachineBasicBlock::iterator I =
 656       SourceRegion.BranchBlock->terminators().begin();
 657   while (I != SourceRegion.BranchBlock->terminators().end()) {
 658     MachineInstr &CurrInst = *I;
 659     ++I;
 660     if (CurrInst.isBranch())
 661       CurrInst.eraseFromParent();
 662   }
 663
 664   // Fall-through block should be empty since this is part of the condition
 665   // to coalesce the branches.
 666   assert(TargetRegion.FallThroughBlock->empty() &&
 667          "FallThroughBlocks should be empty!");
 668
 669   // Transfer successor information and move PHIs down to the
 670   // branch-taken block.
 671   TargetRegion.FallThroughBlock->transferSuccessorsAndUpdatePHIs(
 672       SourceRegion.FallThroughBlock);
 673   TargetRegion.FallThroughBlock->removeSuccessor(SourceRegion.BranchBlock);
 674
 675   // Remove the blocks from the function.
 676   assert(SourceRegion.BranchBlock->empty() &&
 677          "Expecting branch block to be empty!");
 678   SourceRegion.BranchBlock->eraseFromParent();
 679
 680   assert(SourceRegion.FallThroughBlock->empty() &&
 681          "Expecting fall-through block to be empty!\n");
 682   SourceRegion.FallThroughBlock->eraseFromParent();
 683
 684   NumBlocksCoalesced++;
 685   return true;
 686 }
 687
 688 bool BranchCoalescing::runOnMachineFunction(MachineFunction &MF) {
 689
 690   if (skipFunction(*MF.getFunction()) || MF.empty() ||
 691       !isBranchCoalescingEnabled())
 692     return false;
 693
 694   bool didSomething = false;
 695
 696   DEBUG(dbgs() << "******** Branch Coalescing ********\n");
 697   initialize(MF);
 698
 699   DEBUG(dbgs() << "Function: "; MF.dump(); dbgs() << "\n");
 700
 701   CoalescingCandidateInfo Cand1, Cand2;
 702   // Walk over blocks and find candidates to merge
 703   // Continue trying to merge with the first candidate found, as long as merging
 704   // is successfull.
 705   for (MachineBasicBlock &MBB : MF) {
 706     bool MergedCandidates = false;
 707     do {
 708       MergedCandidates = false;
 709       Cand1.clear();
 710       Cand2.clear();
 711
 712       Cand1.BranchBlock = &MBB;
 713
 714       // If unable to coalesce the branch, then continue to next block
 715       if (!canCoalesceBranch(Cand1))
 716         break;
 717
 718       Cand2.BranchBlock = Cand1.BranchTargetBlock;
 719       if (!canCoalesceBranch(Cand2))
 720         break;
 721
 722       // Sanity check
 723       // The branch-taken block of the second candidate should post-dominate the
 724       // first candidate
 725       assert(MPDT->dominates(Cand2.BranchTargetBlock, Cand1.BranchBlock) &&
 726              "Branch-taken block should post-dominate first candidate");
 727
 728       if (!identicalOperands(Cand1.Cond, Cand2.Cond)) {
 729         DEBUG(dbgs() << "Blocks " << Cand1.BranchBlock->getNumber() << " and "
 730                      << Cand2.BranchBlock->getNumber()
 731                      << " have different branches\n");
 732         break;
 733       }
 734       if (!canMerge(Cand2, Cand1)) {
 735         DEBUG(dbgs() << "Cannot merge blocks " << Cand1.BranchBlock->getNumber()
 736                      << " and " << Cand2.BranchBlock->getNumber() << "\n");
 737         NumBlocksNotCoalesced++;
 738         continue;
 739       }
 740       DEBUG(dbgs() << "Merging blocks " << Cand1.BranchBlock->getNumber()
 741                    << " and " << Cand1.BranchTargetBlock->getNumber() << "\n");
 742       MergedCandidates = mergeCandidates(Cand2, Cand1);
 743       if (MergedCandidates)
 744         didSomething = true;
 745
 746       DEBUG(dbgs() << "Function after merging: "; MF.dump(); dbgs() << "\n");
 747     } while (MergedCandidates);
 748   }
 749
 750 #ifndef NDEBUG
 751   // Verify MF is still valid after branch coalescing
 752   if (didSomething)
 753     MF.verify(nullptr, "Error in code produced by branch coalescing");
 754 #endif // NDEBUG
 755
 756   DEBUG(dbgs() << "Finished Branch Coalescing\n");
 757   return didSomething;
 758 }