PPCBranchCoalescing.cpp revision 360784
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 // For now only consider triangles (i.e, BranchTargetBlock is set, 276 // FalseMBB is null, and BranchTargetBlock is a successor to BranchBlock) 277 if (!Cand.BranchTargetBlock || FalseMBB || 278 !Cand.BranchBlock->isSuccessor(Cand.BranchTargetBlock)) { 279 LLVM_DEBUG(dbgs() << "Does not form a triangle - skip\n"); 280 return false; 281 } 282 283 // Ensure there are only two successors 284 if (Cand.BranchBlock->succ_size() != 2) { 285 LLVM_DEBUG(dbgs() << "Does not have 2 successors - skip\n"); 286 return false; 287 } 288 289 // Sanity check - the block must be able to fall through 290 assert(Cand.BranchBlock->canFallThrough() && 291 "Expecting the block to fall through!"); 292 293 // We have already ensured there are exactly two successors to 294 // BranchBlock and that BranchTargetBlock is a successor to BranchBlock. 295 // Ensure the single fall though block is empty. 296 MachineBasicBlock *Succ = 297 (*Cand.BranchBlock->succ_begin() == Cand.BranchTargetBlock) 298 ? *Cand.BranchBlock->succ_rbegin() 299 : *Cand.BranchBlock->succ_begin(); 300 301 assert(Succ && "Expecting a valid fall-through block\n"); 302 303 if (!Succ->empty()) { 304 LLVM_DEBUG(dbgs() << "Fall-through block contains code -- skip\n"); 305 return false; 306 } 307 308 if (!Succ->isSuccessor(Cand.BranchTargetBlock)) { 309 LLVM_DEBUG( 310 dbgs() 311 << "Successor of fall through block is not branch taken block\n"); 312 return false; 313 } 314 315 Cand.FallThroughBlock = Succ; 316 LLVM_DEBUG(dbgs() << "Valid Candidate\n"); 317 return true; 318} 319 320/// 321/// Determine if the two operand lists are identical 322/// 323/// \param[in] OpList1 operand list 324/// \param[in] OpList2 operand list 325/// \return true if and only if the operands lists are identical 326/// 327bool PPCBranchCoalescing::identicalOperands( 328 ArrayRef<MachineOperand> OpList1, ArrayRef<MachineOperand> OpList2) const { 329 330 if (OpList1.size() != OpList2.size()) { 331 LLVM_DEBUG(dbgs() << "Operand list is different size\n"); 332 return false; 333 } 334 335 for (unsigned i = 0; i < OpList1.size(); ++i) { 336 const MachineOperand &Op1 = OpList1[i]; 337 const MachineOperand &Op2 = OpList2[i]; 338 339 LLVM_DEBUG(dbgs() << "Op1: " << Op1 << "\n" 340 << "Op2: " << Op2 << "\n"); 341 342 if (Op1.isIdenticalTo(Op2)) { 343 // filter out instructions with physical-register uses 344 if (Op1.isReg() && 345 Register::isPhysicalRegister(Op1.getReg()) 346 // If the physical register is constant then we can assume the value 347 // has not changed between uses. 348 && !(Op1.isUse() && MRI->isConstantPhysReg(Op1.getReg()))) { 349 LLVM_DEBUG(dbgs() << "The operands are not provably identical.\n"); 350 return false; 351 } 352 LLVM_DEBUG(dbgs() << "Op1 and Op2 are identical!\n"); 353 continue; 354 } 355 356 // If the operands are not identical, but are registers, check to see if the 357 // definition of the register produces the same value. If they produce the 358 // same value, consider them to be identical. 359 if (Op1.isReg() && Op2.isReg() && 360 Register::isVirtualRegister(Op1.getReg()) && 361 Register::isVirtualRegister(Op2.getReg())) { 362 MachineInstr *Op1Def = MRI->getVRegDef(Op1.getReg()); 363 MachineInstr *Op2Def = MRI->getVRegDef(Op2.getReg()); 364 if (TII->produceSameValue(*Op1Def, *Op2Def, MRI)) { 365 LLVM_DEBUG(dbgs() << "Op1Def: " << *Op1Def << " and " << *Op2Def 366 << " produce the same value!\n"); 367 } else { 368 LLVM_DEBUG(dbgs() << "Operands produce different values\n"); 369 return false; 370 } 371 } else { 372 LLVM_DEBUG(dbgs() << "The operands are not provably identical.\n"); 373 return false; 374 } 375 } 376 377 return true; 378} 379 380/// 381/// Moves ALL PHI instructions in SourceMBB to beginning of TargetMBB 382/// and update them to refer to the new block. PHI node ordering 383/// cannot be assumed so it does not matter where the PHI instructions 384/// are moved to in TargetMBB. 385/// 386/// \param[in] SourceMBB block to move PHI instructions from 387/// \param[in] TargetMBB block to move PHI instructions to 388/// 389void PPCBranchCoalescing::moveAndUpdatePHIs(MachineBasicBlock *SourceMBB, 390 MachineBasicBlock *TargetMBB) { 391 392 MachineBasicBlock::iterator MI = SourceMBB->begin(); 393 MachineBasicBlock::iterator ME = SourceMBB->getFirstNonPHI(); 394 395 if (MI == ME) { 396 LLVM_DEBUG(dbgs() << "SourceMBB contains no PHI instructions.\n"); 397 return; 398 } 399 400 // Update all PHI instructions in SourceMBB and move to top of TargetMBB 401 for (MachineBasicBlock::iterator Iter = MI; Iter != ME; Iter++) { 402 MachineInstr &PHIInst = *Iter; 403 for (unsigned i = 2, e = PHIInst.getNumOperands() + 1; i != e; i += 2) { 404 MachineOperand &MO = PHIInst.getOperand(i); 405 if (MO.getMBB() == SourceMBB) 406 MO.setMBB(TargetMBB); 407 } 408 } 409 TargetMBB->splice(TargetMBB->begin(), SourceMBB, MI, ME); 410} 411 412/// 413/// This function checks if MI can be moved to the beginning of the TargetMBB 414/// following PHI instructions. A MI instruction can be moved to beginning of 415/// the TargetMBB if there are no uses of it within the TargetMBB PHI nodes. 416/// 417/// \param[in] MI the machine instruction to move. 418/// \param[in] TargetMBB the machine basic block to move to 419/// \return true if it is safe to move MI to beginning of TargetMBB, 420/// false otherwise. 421/// 422bool PPCBranchCoalescing::canMoveToBeginning(const MachineInstr &MI, 423 const MachineBasicBlock &TargetMBB 424 ) const { 425 426 LLVM_DEBUG(dbgs() << "Checking if " << MI << " can move to beginning of " 427 << TargetMBB.getNumber() << "\n"); 428 429 for (auto &Def : MI.defs()) { // Looking at Def 430 for (auto &Use : MRI->use_instructions(Def.getReg())) { 431 if (Use.isPHI() && Use.getParent() == &TargetMBB) { 432 LLVM_DEBUG(dbgs() << " *** used in a PHI -- cannot move ***\n"); 433 return false; 434 } 435 } 436 } 437 438 LLVM_DEBUG(dbgs() << " Safe to move to the beginning.\n"); 439 return true; 440} 441 442/// 443/// This function checks if MI can be moved to the end of the TargetMBB, 444/// immediately before the first terminator. A MI instruction can be moved 445/// to then end of the TargetMBB if no PHI node defines what MI uses within 446/// it's own MBB. 447/// 448/// \param[in] MI the machine instruction to move. 449/// \param[in] TargetMBB the machine basic block to move to 450/// \return true if it is safe to move MI to end of TargetMBB, 451/// false otherwise. 452/// 453bool PPCBranchCoalescing::canMoveToEnd(const MachineInstr &MI, 454 const MachineBasicBlock &TargetMBB 455 ) const { 456 457 LLVM_DEBUG(dbgs() << "Checking if " << MI << " can move to end of " 458 << TargetMBB.getNumber() << "\n"); 459 460 for (auto &Use : MI.uses()) { 461 if (Use.isReg() && Register::isVirtualRegister(Use.getReg())) { 462 MachineInstr *DefInst = MRI->getVRegDef(Use.getReg()); 463 if (DefInst->isPHI() && DefInst->getParent() == MI.getParent()) { 464 LLVM_DEBUG(dbgs() << " *** Cannot move this instruction ***\n"); 465 return false; 466 } else { 467 LLVM_DEBUG( 468 dbgs() << " *** def is in another block -- safe to move!\n"); 469 } 470 } 471 } 472 473 LLVM_DEBUG(dbgs() << " Safe to move to the end.\n"); 474 return true; 475} 476 477/// 478/// This method checks to ensure the two coalescing candidates follows the 479/// expected pattern required for coalescing. 480/// 481/// \param[in] SourceRegion The candidate to move statements from 482/// \param[in] TargetRegion The candidate to move statements to 483/// \return true if all instructions in SourceRegion.BranchBlock can be merged 484/// into a block in TargetRegion; false otherwise. 485/// 486bool PPCBranchCoalescing::validateCandidates( 487 CoalescingCandidateInfo &SourceRegion, 488 CoalescingCandidateInfo &TargetRegion) const { 489 490 if (TargetRegion.BranchTargetBlock != SourceRegion.BranchBlock) 491 llvm_unreachable("Expecting SourceRegion to immediately follow TargetRegion"); 492 else if (!MDT->dominates(TargetRegion.BranchBlock, SourceRegion.BranchBlock)) 493 llvm_unreachable("Expecting TargetRegion to dominate SourceRegion"); 494 else if (!MPDT->dominates(SourceRegion.BranchBlock, TargetRegion.BranchBlock)) 495 llvm_unreachable("Expecting SourceRegion to post-dominate TargetRegion"); 496 else if (!TargetRegion.FallThroughBlock->empty() || 497 !SourceRegion.FallThroughBlock->empty()) 498 llvm_unreachable("Expecting fall-through blocks to be empty"); 499 500 return true; 501} 502 503/// 504/// This method determines whether the two coalescing candidates can be merged. 505/// In order to be merged, all instructions must be able to 506/// 1. Move to the beginning of the SourceRegion.BranchTargetBlock; 507/// 2. Move to the end of the TargetRegion.BranchBlock. 508/// Merging involves moving the instructions in the 509/// TargetRegion.BranchTargetBlock (also SourceRegion.BranchBlock). 510/// 511/// This function first try to move instructions from the 512/// TargetRegion.BranchTargetBlock down, to the beginning of the 513/// SourceRegion.BranchTargetBlock. This is not possible if any register defined 514/// in TargetRegion.BranchTargetBlock is used in a PHI node in the 515/// SourceRegion.BranchTargetBlock. In this case, check whether the statement 516/// can be moved up, to the end of the TargetRegion.BranchBlock (immediately 517/// before the branch statement). If it cannot move, then these blocks cannot 518/// be merged. 519/// 520/// Note that there is no analysis for moving instructions past the fall-through 521/// blocks because they are confirmed to be empty. An assert is thrown if they 522/// are not. 523/// 524/// \param[in] SourceRegion The candidate to move statements from 525/// \param[in] TargetRegion The candidate to move statements to 526/// \return true if all instructions in SourceRegion.BranchBlock can be merged 527/// into a block in TargetRegion, false otherwise. 528/// 529bool PPCBranchCoalescing::canMerge(CoalescingCandidateInfo &SourceRegion, 530 CoalescingCandidateInfo &TargetRegion) const { 531 if (!validateCandidates(SourceRegion, TargetRegion)) 532 return false; 533 534 // Walk through PHI nodes first and see if they force the merge into the 535 // SourceRegion.BranchTargetBlock. 536 for (MachineBasicBlock::iterator 537 I = SourceRegion.BranchBlock->instr_begin(), 538 E = SourceRegion.BranchBlock->getFirstNonPHI(); 539 I != E; ++I) { 540 for (auto &Def : I->defs()) 541 for (auto &Use : MRI->use_instructions(Def.getReg())) { 542 if (Use.isPHI() && Use.getParent() == SourceRegion.BranchTargetBlock) { 543 LLVM_DEBUG(dbgs() 544 << "PHI " << *I 545 << " defines register used in another " 546 "PHI within branch target block -- can't merge\n"); 547 NumPHINotMoved++; 548 return false; 549 } 550 if (Use.getParent() == SourceRegion.BranchBlock) { 551 LLVM_DEBUG(dbgs() << "PHI " << *I 552 << " defines register used in this " 553 "block -- all must move down\n"); 554 SourceRegion.MustMoveDown = true; 555 } 556 } 557 } 558 559 // Walk through the MI to see if they should be merged into 560 // TargetRegion.BranchBlock (up) or SourceRegion.BranchTargetBlock (down) 561 for (MachineBasicBlock::iterator 562 I = SourceRegion.BranchBlock->getFirstNonPHI(), 563 E = SourceRegion.BranchBlock->end(); 564 I != E; ++I) { 565 if (!canMoveToBeginning(*I, *SourceRegion.BranchTargetBlock)) { 566 LLVM_DEBUG(dbgs() << "Instruction " << *I 567 << " cannot move down - must move up!\n"); 568 SourceRegion.MustMoveUp = true; 569 } 570 if (!canMoveToEnd(*I, *TargetRegion.BranchBlock)) { 571 LLVM_DEBUG(dbgs() << "Instruction " << *I 572 << " cannot move up - must move down!\n"); 573 SourceRegion.MustMoveDown = true; 574 } 575 } 576 577 return (SourceRegion.MustMoveUp && SourceRegion.MustMoveDown) ? false : true; 578} 579 580/// Merge the instructions from SourceRegion.BranchBlock, 581/// SourceRegion.BranchTargetBlock, and SourceRegion.FallThroughBlock into 582/// TargetRegion.BranchBlock, TargetRegion.BranchTargetBlock and 583/// TargetRegion.FallThroughBlock respectively. 584/// 585/// The successors for blocks in TargetRegion will be updated to use the 586/// successors from blocks in SourceRegion. Finally, the blocks in SourceRegion 587/// will be removed from the function. 588/// 589/// A region consists of a BranchBlock, a FallThroughBlock, and a 590/// BranchTargetBlock. Branch coalesce works on patterns where the 591/// TargetRegion's BranchTargetBlock must also be the SourceRegions's 592/// BranchBlock. 593/// 594/// Before mergeCandidates: 595/// 596/// +---------------------------+ 597/// | TargetRegion.BranchBlock | 598/// +---------------------------+ 599/// / | 600/// / +--------------------------------+ 601/// | | TargetRegion.FallThroughBlock | 602/// \ +--------------------------------+ 603/// \ | 604/// +----------------------------------+ 605/// | TargetRegion.BranchTargetBlock | 606/// | SourceRegion.BranchBlock | 607/// +----------------------------------+ 608/// / | 609/// / +--------------------------------+ 610/// | | SourceRegion.FallThroughBlock | 611/// \ +--------------------------------+ 612/// \ | 613/// +----------------------------------+ 614/// | SourceRegion.BranchTargetBlock | 615/// +----------------------------------+ 616/// 617/// After mergeCandidates: 618/// 619/// +-----------------------------+ 620/// | TargetRegion.BranchBlock | 621/// | SourceRegion.BranchBlock | 622/// +-----------------------------+ 623/// / | 624/// / +---------------------------------+ 625/// | | TargetRegion.FallThroughBlock | 626/// | | SourceRegion.FallThroughBlock | 627/// \ +---------------------------------+ 628/// \ | 629/// +----------------------------------+ 630/// | SourceRegion.BranchTargetBlock | 631/// +----------------------------------+ 632/// 633/// \param[in] SourceRegion The candidate to move blocks from 634/// \param[in] TargetRegion The candidate to move blocks to 635/// 636bool PPCBranchCoalescing::mergeCandidates(CoalescingCandidateInfo &SourceRegion, 637 CoalescingCandidateInfo &TargetRegion) { 638 639 if (SourceRegion.MustMoveUp && SourceRegion.MustMoveDown) { 640 llvm_unreachable("Cannot have both MustMoveDown and MustMoveUp set!"); 641 return false; 642 } 643 644 if (!validateCandidates(SourceRegion, TargetRegion)) 645 return false; 646 647 // Start the merging process by first handling the BranchBlock. 648 // Move any PHIs in SourceRegion.BranchBlock down to the branch-taken block 649 moveAndUpdatePHIs(SourceRegion.BranchBlock, SourceRegion.BranchTargetBlock); 650 651 // Move remaining instructions in SourceRegion.BranchBlock into 652 // TargetRegion.BranchBlock 653 MachineBasicBlock::iterator firstInstr = 654 SourceRegion.BranchBlock->getFirstNonPHI(); 655 MachineBasicBlock::iterator lastInstr = 656 SourceRegion.BranchBlock->getFirstTerminator(); 657 658 MachineBasicBlock *Source = SourceRegion.MustMoveDown 659 ? SourceRegion.BranchTargetBlock 660 : TargetRegion.BranchBlock; 661 662 MachineBasicBlock::iterator Target = 663 SourceRegion.MustMoveDown 664 ? SourceRegion.BranchTargetBlock->getFirstNonPHI() 665 : TargetRegion.BranchBlock->getFirstTerminator(); 666 667 Source->splice(Target, SourceRegion.BranchBlock, firstInstr, lastInstr); 668 669 // Once PHI and instructions have been moved we need to clean up the 670 // control flow. 671 672 // Remove SourceRegion.FallThroughBlock before transferring successors of 673 // SourceRegion.BranchBlock to TargetRegion.BranchBlock. 674 SourceRegion.BranchBlock->removeSuccessor(SourceRegion.FallThroughBlock); 675 TargetRegion.BranchBlock->transferSuccessorsAndUpdatePHIs( 676 SourceRegion.BranchBlock); 677 // Update branch in TargetRegion.BranchBlock to jump to 678 // SourceRegion.BranchTargetBlock 679 // In this case, TargetRegion.BranchTargetBlock == SourceRegion.BranchBlock. 680 TargetRegion.BranchBlock->ReplaceUsesOfBlockWith( 681 SourceRegion.BranchBlock, SourceRegion.BranchTargetBlock); 682 // Remove the branch statement(s) in SourceRegion.BranchBlock 683 MachineBasicBlock::iterator I = 684 SourceRegion.BranchBlock->terminators().begin(); 685 while (I != SourceRegion.BranchBlock->terminators().end()) { 686 MachineInstr &CurrInst = *I; 687 ++I; 688 if (CurrInst.isBranch()) 689 CurrInst.eraseFromParent(); 690 } 691 692 // Fall-through block should be empty since this is part of the condition 693 // to coalesce the branches. 694 assert(TargetRegion.FallThroughBlock->empty() && 695 "FallThroughBlocks should be empty!"); 696 697 // Transfer successor information and move PHIs down to the 698 // branch-taken block. 699 TargetRegion.FallThroughBlock->transferSuccessorsAndUpdatePHIs( 700 SourceRegion.FallThroughBlock); 701 TargetRegion.FallThroughBlock->removeSuccessor(SourceRegion.BranchBlock); 702 703 // Remove the blocks from the function. 704 assert(SourceRegion.BranchBlock->empty() && 705 "Expecting branch block to be empty!"); 706 SourceRegion.BranchBlock->eraseFromParent(); 707 708 assert(SourceRegion.FallThroughBlock->empty() && 709 "Expecting fall-through block to be empty!\n"); 710 SourceRegion.FallThroughBlock->eraseFromParent(); 711 712 NumBlocksCoalesced++; 713 return true; 714} 715 716bool PPCBranchCoalescing::runOnMachineFunction(MachineFunction &MF) { 717 718 if (skipFunction(MF.getFunction()) || MF.empty()) 719 return false; 720 721 bool didSomething = false; 722 723 LLVM_DEBUG(dbgs() << "******** Branch Coalescing ********\n"); 724 initialize(MF); 725 726 LLVM_DEBUG(dbgs() << "Function: "; MF.dump(); dbgs() << "\n"); 727 728 CoalescingCandidateInfo Cand1, Cand2; 729 // Walk over blocks and find candidates to merge 730 // Continue trying to merge with the first candidate found, as long as merging 731 // is successfull. 732 for (MachineBasicBlock &MBB : MF) { 733 bool MergedCandidates = false; 734 do { 735 MergedCandidates = false; 736 Cand1.clear(); 737 Cand2.clear(); 738 739 Cand1.BranchBlock = &MBB; 740 741 // If unable to coalesce the branch, then continue to next block 742 if (!canCoalesceBranch(Cand1)) 743 break; 744 745 Cand2.BranchBlock = Cand1.BranchTargetBlock; 746 if (!canCoalesceBranch(Cand2)) 747 break; 748 749 // Sanity check 750 // The branch-taken block of the second candidate should post-dominate the 751 // first candidate 752 assert(MPDT->dominates(Cand2.BranchTargetBlock, Cand1.BranchBlock) && 753 "Branch-taken block should post-dominate first candidate"); 754 755 if (!identicalOperands(Cand1.Cond, Cand2.Cond)) { 756 LLVM_DEBUG(dbgs() << "Blocks " << Cand1.BranchBlock->getNumber() 757 << " and " << Cand2.BranchBlock->getNumber() 758 << " have different branches\n"); 759 break; 760 } 761 if (!canMerge(Cand2, Cand1)) { 762 LLVM_DEBUG(dbgs() << "Cannot merge blocks " 763 << Cand1.BranchBlock->getNumber() << " and " 764 << Cand2.BranchBlock->getNumber() << "\n"); 765 NumBlocksNotCoalesced++; 766 continue; 767 } 768 LLVM_DEBUG(dbgs() << "Merging blocks " << Cand1.BranchBlock->getNumber() 769 << " and " << Cand1.BranchTargetBlock->getNumber() 770 << "\n"); 771 MergedCandidates = mergeCandidates(Cand2, Cand1); 772 if (MergedCandidates) 773 didSomething = true; 774 775 LLVM_DEBUG(dbgs() << "Function after merging: "; MF.dump(); 776 dbgs() << "\n"); 777 } while (MergedCandidates); 778 } 779 780#ifndef NDEBUG 781 // Verify MF is still valid after branch coalescing 782 if (didSomething) 783 MF.verify(nullptr, "Error in code produced by branch coalescing"); 784#endif // NDEBUG 785 786 LLVM_DEBUG(dbgs() << "Finished Branch Coalescing\n"); 787 return didSomething; 788} 789