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