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