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