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 29using namespace llvm; 30 31#define DEBUG_TYPE "ppc-branch-coalescing" 32 33STATISTIC(NumBlocksCoalesced, "Number of blocks coalesced"); 34STATISTIC(NumPHINotMoved, "Number of PHI Nodes that cannot be merged"); 35STATISTIC(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 134namespace { 135 136class 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 161public: 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 190char PPCBranchCoalescing::ID = 0; 191/// createPPCBranchCoalescingPass - returns an instance of the Branch Coalescing 192/// Pass 193FunctionPass *llvm::createPPCBranchCoalescingPass() { 194 return new PPCBranchCoalescing(); 195} 196 197INITIALIZE_PASS_BEGIN(PPCBranchCoalescing, DEBUG_TYPE, 198 "Branch Coalescing", false, false) 199INITIALIZE_PASS_DEPENDENCY(MachineDominatorTree) 200INITIALIZE_PASS_DEPENDENCY(MachinePostDominatorTree) 201INITIALIZE_PASS_END(PPCBranchCoalescing, DEBUG_TYPE, "Branch Coalescing", 202 false, false) 203 204PPCBranchCoalescing::CoalescingCandidateInfo::CoalescingCandidateInfo() 205 : BranchBlock(nullptr), BranchTargetBlock(nullptr), 206 FallThroughBlock(nullptr), MustMoveDown(false), MustMoveUp(false) {} 207 208void PPCBranchCoalescing::CoalescingCandidateInfo::clear() { 209 BranchBlock = nullptr; 210 BranchTargetBlock = nullptr; 211 FallThroughBlock = nullptr; 212 Cond.clear(); 213 MustMoveDown = false; 214 MustMoveUp = false; 215} 216 217void 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/// 234bool 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/// 332bool 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() && Op1.getReg().isPhysical() 350 // If the physical register is constant then we can assume the value 351 // has not changed between uses. 352 && !(Op1.isUse() && MRI->isConstantPhysReg(Op1.getReg()))) { 353 LLVM_DEBUG(dbgs() << "The operands are not provably identical.\n"); 354 return false; 355 } 356 LLVM_DEBUG(dbgs() << "Op1 and Op2 are identical!\n"); 357 continue; 358 } 359 360 // If the operands are not identical, but are registers, check to see if the 361 // definition of the register produces the same value. If they produce the 362 // same value, consider them to be identical. 363 if (Op1.isReg() && Op2.isReg() && Op1.getReg().isVirtual() && 364 Op2.getReg().isVirtual()) { 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/// 392void 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/// 425bool 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/// 456bool 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() && Use.getReg().isVirtual()) { 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/// 489bool 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/// 532bool 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/// 639bool 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 719bool 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 // 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