contrib/llvm/lib/Target/PowerPC/PPCBranchCoalescing.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 "PPC.h"
  17 #include "llvm/ADT/BitVector.h"
  18 #include "llvm/ADT/Statistic.h"
  19 #include "llvm/CodeGen/MachineDominators.h"
  20 #include "llvm/CodeGen/MachineFunctionPass.h"
  21 #include "llvm/CodeGen/MachinePostDominators.h"
  22 #include "llvm/CodeGen/MachineRegisterInfo.h"
  23 #include "llvm/CodeGen/Passes.h"
  24 #include "llvm/CodeGen/TargetFrameLowering.h"
  25 #include "llvm/CodeGen/TargetInstrInfo.h"
  26 #include "llvm/CodeGen/TargetSubtargetInfo.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 namespace llvm {
  38     void initializePPCBranchCoalescingPass(PassRegistry&);
  39 }
  40
  41 //===----------------------------------------------------------------------===//
  42 //                               PPCBranchCoalescing
  43 //===----------------------------------------------------------------------===//
  44 ///
  45 /// Improve scheduling by coalescing branches that depend on the same condition.
  46 /// This pass looks for blocks that are guarded by the same branch condition
  47 /// and attempts to merge the blocks together. Such opportunities arise from
  48 /// the expansion of select statements in the IR.
  49 ///
  50 /// This pass does not handle implicit operands on branch statements. In order
  51 /// to run on targets that use implicit operands, changes need to be made in the
  52 /// canCoalesceBranch and canMerge methods.
  53 ///
  54 /// Example: the following LLVM IR
  55 ///
  56 ///     %test = icmp eq i32 %x 0
  57 ///     %tmp1 = select i1 %test, double %a, double 2.000000e-03
  58 ///     %tmp2 = select i1 %test, double %b, double 5.000000e-03
  59 ///
  60 /// expands to the following machine code:
  61 ///
  62 /// %bb.0: derived from LLVM BB %entry
  63 ///    liveins: %f1 %f3 %x6
  64 ///        <SNIP1>
  65 ///        %0 = COPY %f1; F8RC:%0
  66 ///        %5 = CMPLWI killed %4, 0; CRRC:%5 GPRC:%4
  67 ///        %8 = LXSDX %zero8, killed %7, implicit %rm;
  68 ///                    mem:LD8[ConstantPool] F8RC:%8 G8RC:%7
  69 ///        BCC 76, %5, <%bb.2>; CRRC:%5
  70 ///    Successors according to CFG: %bb.1(?%) %bb.2(?%)
  71 ///
  72 /// %bb.1: derived from LLVM BB %entry
  73 ///    Predecessors according to CFG: %bb.0
  74 ///    Successors according to CFG: %bb.2(?%)
  75 ///
  76 /// %bb.2: derived from LLVM BB %entry
  77 ///    Predecessors according to CFG: %bb.0 %bb.1
  78 ///        %9 = PHI %8, <%bb.1>, %0, <%bb.0>;
  79 ///                    F8RC:%9,%8,%0
  80 ///        <SNIP2>
  81 ///        BCC 76, %5, <%bb.4>; CRRC:%5
  82 ///    Successors according to CFG: %bb.3(?%) %bb.4(?%)
  83 ///
  84 /// %bb.3: derived from LLVM BB %entry
  85 ///    Predecessors according to CFG: %bb.2
  86 ///    Successors according to CFG: %bb.4(?%)
  87 ///
  88 /// %bb.4: derived from LLVM BB %entry
  89 ///    Predecessors according to CFG: %bb.2 %bb.3
  90 ///        %13 = PHI %12, <%bb.3>, %2, <%bb.2>;
  91 ///                     F8RC:%13,%12,%2
  92 ///        <SNIP3>
  93 ///        BLR8 implicit %lr8, implicit %rm, implicit %f1
  94 ///
  95 /// When this pattern is detected, branch coalescing will try to collapse
  96 /// it by moving code in %bb.2 to %bb.0 and/or %bb.4 and removing %bb.3.
  97 ///
  98 /// If all conditions are meet, IR should collapse to:
  99 ///
 100 /// %bb.0: derived from LLVM BB %entry
 101 ///    liveins: %f1 %f3 %x6
 102 ///        <SNIP1>
 103 ///        %0 = COPY %f1; F8RC:%0
 104 ///        %5 = CMPLWI killed %4, 0; CRRC:%5 GPRC:%4
 105 ///        %8 = LXSDX %zero8, killed %7, implicit %rm;
 106 ///                     mem:LD8[ConstantPool] F8RC:%8 G8RC:%7
 107 ///        <SNIP2>
 108 ///        BCC 76, %5, <%bb.4>; CRRC:%5
 109 ///    Successors according to CFG: %bb.1(0x2aaaaaaa / 0x80000000 = 33.33%)
 110 ///      %bb.4(0x55555554 / 0x80000000 = 66.67%)
 111 ///
 112 /// %bb.1: derived from LLVM BB %entry
 113 ///    Predecessors according to CFG: %bb.0
 114 ///    Successors according to CFG: %bb.4(0x40000000 / 0x80000000 = 50.00%)
 115 ///
 116 /// %bb.4: derived from LLVM BB %entry
 117 ///    Predecessors according to CFG: %bb.0 %bb.1
 118 ///        %9 = PHI %8, <%bb.1>, %0, <%bb.0>;
 119 ///                    F8RC:%9,%8,%0
 120 ///        %13 = PHI %12, <%bb.1>, %2, <%bb.0>;
 121 ///                     F8RC:%13,%12,%2
 122 ///        <SNIP3>
 123 ///        BLR8 implicit %lr8, implicit %rm, implicit %f1
 124 ///
 125 /// Branch Coalescing does not split blocks, it moves everything in the same
 126 /// direction ensuring it does not break use/definition semantics.
 127 ///
 128 /// PHI nodes and its corresponding use instructions are moved to its successor
 129 /// block if there are no uses within the successor block PHI nodes.  PHI
 130 /// node ordering cannot be assumed.
 131 ///
 132 /// Non-PHI can be moved up to the predecessor basic block or down to the
 133 /// successor basic block following any PHI instructions. Whether it moves
 134 /// up or down depends on whether the register(s) defined in the instructions
 135 /// are used in current block or in any PHI instructions at the beginning of
 136 /// the successor block.
 137
 138 namespace {
 139
 140 class PPCBranchCoalescing : public MachineFunctionPass {
 141   struct CoalescingCandidateInfo {
 142     MachineBasicBlock *BranchBlock;       // Block containing the branch
 143     MachineBasicBlock *BranchTargetBlock; // Block branched to
 144     MachineBasicBlock *FallThroughBlock;  // Fall-through if branch not taken
 145     SmallVector<MachineOperand, 4> Cond;
 146     bool MustMoveDown;
 147     bool MustMoveUp;
 148
 149     CoalescingCandidateInfo();
 150     void clear();
 151   };
 152
 153   MachineDominatorTree *MDT;
 154   MachinePostDominatorTree *MPDT;
 155   const TargetInstrInfo *TII;
 156   MachineRegisterInfo *MRI;
 157
 158   void initialize(MachineFunction &F);
 159   bool canCoalesceBranch(CoalescingCandidateInfo &Cand);
 160   bool identicalOperands(ArrayRef<MachineOperand> OperandList1,
 161                          ArrayRef<MachineOperand> OperandList2) const;
 162   bool validateCandidates(CoalescingCandidateInfo &SourceRegion,
 163                           CoalescingCandidateInfo &TargetRegion) const;
 164
 165 public:
 166   static char ID;
 167
 168   PPCBranchCoalescing() : MachineFunctionPass(ID) {
 169     initializePPCBranchCoalescingPass(*PassRegistry::getPassRegistry());
 170   }
 171
 172   void getAnalysisUsage(AnalysisUsage &AU) const override {
 173     AU.addRequired<MachineDominatorTree>();
 174     AU.addRequired<MachinePostDominatorTree>();
 175     MachineFunctionPass::getAnalysisUsage(AU);
 176   }
 177
 178   StringRef getPassName() const override { return "Branch Coalescing"; }
 179
 180   bool mergeCandidates(CoalescingCandidateInfo &SourceRegion,
 181                        CoalescingCandidateInfo &TargetRegion);
 182   bool canMoveToBeginning(const MachineInstr &MI,
 183                           const MachineBasicBlock &MBB) const;
 184   bool canMoveToEnd(const MachineInstr &MI,
 185                     const MachineBasicBlock &MBB) const;
 186   bool canMerge(CoalescingCandidateInfo &SourceRegion,
 187                 CoalescingCandidateInfo &TargetRegion) const;
 188   void moveAndUpdatePHIs(MachineBasicBlock *SourceRegionMBB,
 189                          MachineBasicBlock *TargetRegionMBB);
 190   bool runOnMachineFunction(MachineFunction &MF) override;
 191 };
 192 } // End anonymous namespace.
 193
 194 char PPCBranchCoalescing::ID = 0;
 195 /// createPPCBranchCoalescingPass - returns an instance of the Branch Coalescing
 196 /// Pass
 197 FunctionPass *llvm::createPPCBranchCoalescingPass() {
 198   return new PPCBranchCoalescing();
 199 }
 200
 201 INITIALIZE_PASS_BEGIN(PPCBranchCoalescing, DEBUG_TYPE,
 202                       "Branch Coalescing", false, false)
 203 INITIALIZE_PASS_DEPENDENCY(MachineDominatorTree)
 204 INITIALIZE_PASS_DEPENDENCY(MachinePostDominatorTree)
 205 INITIALIZE_PASS_END(PPCBranchCoalescing, DEBUG_TYPE, "Branch Coalescing",
 206                     false, false)
 207
 208 PPCBranchCoalescing::CoalescingCandidateInfo::CoalescingCandidateInfo()
 209     : BranchBlock(nullptr), BranchTargetBlock(nullptr),
 210       FallThroughBlock(nullptr), MustMoveDown(false), MustMoveUp(false) {}
 211
 212 void PPCBranchCoalescing::CoalescingCandidateInfo::clear() {
 213   BranchBlock = nullptr;
 214   BranchTargetBlock = nullptr;
 215   FallThroughBlock = nullptr;
 216   Cond.clear();
 217   MustMoveDown = false;
 218   MustMoveUp = false;
 219 }
 220
 221 void PPCBranchCoalescing::initialize(MachineFunction &MF) {
 222   MDT = &getAnalysis<MachineDominatorTree>();
 223   MPDT = &getAnalysis<MachinePostDominatorTree>();
 224   TII = MF.getSubtarget().getInstrInfo();
 225   MRI = &MF.getRegInfo();
 226 }
 227
 228 ///
 229 /// Analyze the branch statement to determine if it can be coalesced. This
 230 /// method analyses the branch statement for the given candidate to determine
 231 /// if it can be coalesced. If the branch can be coalesced, then the
 232 /// BranchTargetBlock and the FallThroughBlock are recorded in the specified
 233 /// Candidate.
 234 ///
 235 ///\param[in,out] Cand The coalescing candidate to analyze
 236 ///\return true if and only if the branch can be coalesced, false otherwise
 237 ///
 238 bool PPCBranchCoalescing::canCoalesceBranch(CoalescingCandidateInfo &Cand) {
 239   LLVM_DEBUG(dbgs() << "Determine if branch block "
 240                     << Cand.BranchBlock->getNumber() << " can be coalesced:");
 241   MachineBasicBlock *FalseMBB = nullptr;
 242
 243   if (TII->analyzeBranch(*Cand.BranchBlock, Cand.BranchTargetBlock, FalseMBB,
 244                          Cand.Cond)) {
 245     LLVM_DEBUG(dbgs() << "TII unable to Analyze Branch - skip\n");
 246     return false;
 247   }
 248
 249   for (auto &I : Cand.BranchBlock->terminators()) {
 250     LLVM_DEBUG(dbgs() << "Looking at terminator : " << I << "\n");
 251     if (!I.isBranch())
 252       continue;
 253
 254     // The analyzeBranch method does not include any implicit operands.
 255     // This is not an issue on PPC but must be handled on other targets.
 256     // For this pass to be made target-independent, the analyzeBranch API
 257     // need to be updated to support implicit operands and there would
 258     // need to be a way to verify that any implicit operands would not be
 259     // clobbered by merging blocks.  This would include identifying the
 260     // implicit operands as well as the basic block they are defined in.
 261     // This could be done by changing the analyzeBranch API to have it also
 262     // record and return the implicit operands and the blocks where they are
 263     // defined. Alternatively, the BranchCoalescing code would need to be
 264     // extended to identify the implicit operands.  The analysis in canMerge
 265     // must then be extended to prove that none of the implicit operands are
 266     // changed in the blocks that are combined during coalescing.
 267     if (I.getNumOperands() != I.getNumExplicitOperands()) {
 268       LLVM_DEBUG(dbgs() << "Terminator contains implicit operands - skip : "
 269                         << I << "\n");
 270       return false;
 271     }
 272   }
 273
 274   if (Cand.BranchBlock->isEHPad() || Cand.BranchBlock->hasEHPadSuccessor()) {
 275     LLVM_DEBUG(dbgs() << "EH Pad - skip\n");
 276     return false;
 277   }
 278
 279   // For now only consider triangles (i.e, BranchTargetBlock is set,
 280   // FalseMBB is null, and BranchTargetBlock is a successor to BranchBlock)
 281   if (!Cand.BranchTargetBlock || FalseMBB ||
 282       !Cand.BranchBlock->isSuccessor(Cand.BranchTargetBlock)) {
 283     LLVM_DEBUG(dbgs() << "Does not form a triangle - skip\n");
 284     return false;
 285   }
 286
 287   // Ensure there are only two successors
 288   if (Cand.BranchBlock->succ_size() != 2) {
 289     LLVM_DEBUG(dbgs() << "Does not have 2 successors - skip\n");
 290     return false;
 291   }
 292
 293   // Sanity check - the block must be able to fall through
 294   assert(Cand.BranchBlock->canFallThrough() &&
 295          "Expecting the block to fall through!");
 296
 297   // We have already ensured there are exactly two successors to
 298   // BranchBlock and that BranchTargetBlock is a successor to BranchBlock.
 299   // Ensure the single fall though block is empty.
 300   MachineBasicBlock *Succ =
 301     (*Cand.BranchBlock->succ_begin() == Cand.BranchTargetBlock)
 302     ? *Cand.BranchBlock->succ_rbegin()
 303     : *Cand.BranchBlock->succ_begin();
 304
 305   assert(Succ && "Expecting a valid fall-through block\n");
 306
 307   if (!Succ->empty()) {
 308     LLVM_DEBUG(dbgs() << "Fall-through block contains code -- skip\n");
 309     return false;
 310   }
 311
 312   if (!Succ->isSuccessor(Cand.BranchTargetBlock)) {
 313     LLVM_DEBUG(
 314         dbgs()
 315         << "Successor of fall through block is not branch taken block\n");
 316     return false;
 317   }
 318
 319   Cand.FallThroughBlock = Succ;
 320   LLVM_DEBUG(dbgs() << "Valid Candidate\n");
 321   return true;
 322 }
 323
 324 ///
 325 /// Determine if the two operand lists are identical
 326 ///
 327 /// \param[in] OpList1 operand list
 328 /// \param[in] OpList2 operand list
 329 /// \return true if and only if the operands lists are identical
 330 ///
 331 bool PPCBranchCoalescing::identicalOperands(
 332     ArrayRef<MachineOperand> OpList1, ArrayRef<MachineOperand> OpList2) const {
 333
 334   if (OpList1.size() != OpList2.size()) {
 335     LLVM_DEBUG(dbgs() << "Operand list is different size\n");
 336     return false;
 337   }
 338
 339   for (unsigned i = 0; i < OpList1.size(); ++i) {
 340     const MachineOperand &Op1 = OpList1[i];
 341     const MachineOperand &Op2 = OpList2[i];
 342
 343     LLVM_DEBUG(dbgs() << "Op1: " << Op1 << "\n"
 344                       << "Op2: " << Op2 << "\n");
 345
 346     if (Op1.isIdenticalTo(Op2)) {
 347       // filter out instructions with physical-register uses
 348       if (Op1.isReg() && TargetRegisterInfo::isPhysicalRegister(Op1.getReg())
 349         // If the physical register is constant then we can assume the value
 350         // has not changed between uses.
 351           && !(Op1.isUse() && MRI->isConstantPhysReg(Op1.getReg()))) {
 352         LLVM_DEBUG(dbgs() << "The operands are not provably identical.\n");
 353         return false;
 354       }
 355       LLVM_DEBUG(dbgs() << "Op1 and Op2 are identical!\n");
 356       continue;
 357     }
 358
 359     // If the operands are not identical, but are registers, check to see if the
 360     // definition of the register produces the same value. If they produce the
 361     // same value, consider them to be identical.
 362     if (Op1.isReg() && Op2.isReg() &&
 363         TargetRegisterInfo::isVirtualRegister(Op1.getReg()) &&
 364         TargetRegisterInfo::isVirtualRegister(Op2.getReg())) {
 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 ///
 392 void 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 ///
 425 bool 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 ///
 456 bool 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() && TargetRegisterInfo::isVirtualRegister(Use.getReg())) {
 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 ///
 489 bool 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 ///
 532 bool 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 ///
 639 bool 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
 719 bool 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       // Sanity check
 753       // The branch-taken block of the second candidate should post-dominate the
 754       // first candidate
 755       assert(MPDT->dominates(Cand2.BranchTargetBlock, Cand1.BranchBlock) &&
 756              "Branch-taken block should post-dominate first candidate");
 757
 758       if (!identicalOperands(Cand1.Cond, Cand2.Cond)) {
 759         LLVM_DEBUG(dbgs() << "Blocks " << Cand1.BranchBlock->getNumber()
 760                           << " and " << Cand2.BranchBlock->getNumber()
 761                           << " have different branches\n");
 762         break;
 763       }
 764       if (!canMerge(Cand2, Cand1)) {
 765         LLVM_DEBUG(dbgs() << "Cannot merge blocks "
 766                           << Cand1.BranchBlock->getNumber() << " and "
 767                           << Cand2.BranchBlock->getNumber() << "\n");
 768         NumBlocksNotCoalesced++;
 769         continue;
 770       }
 771       LLVM_DEBUG(dbgs() << "Merging blocks " << Cand1.BranchBlock->getNumber()
 772                         << " and " << Cand1.BranchTargetBlock->getNumber()
 773                         << "\n");
 774       MergedCandidates = mergeCandidates(Cand2, Cand1);
 775       if (MergedCandidates)
 776         didSomething = true;
 777
 778       LLVM_DEBUG(dbgs() << "Function after merging: "; MF.dump();
 779                  dbgs() << "\n");
 780     } while (MergedCandidates);
 781   }
 782
 783 #ifndef NDEBUG
 784   // Verify MF is still valid after branch coalescing
 785   if (didSomething)
 786     MF.verify(nullptr, "Error in code produced by branch coalescing");
 787 #endif // NDEBUG
 788
 789   LLVM_DEBUG(dbgs() << "Finished Branch Coalescing\n");
 790   return didSomething;
 791 }