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 } 792
