789 lines · cpp
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-exception6//7//===----------------------------------------------------------------------===//8///9/// \file10/// Coalesce basic blocks guarded by the same branch condition into a single11/// basic block.12///13//===----------------------------------------------------------------------===//14 15#include "PPC.h"16#include "llvm/ADT/Statistic.h"17#include "llvm/CodeGen/MachineDominators.h"18#include "llvm/CodeGen/MachineFunctionPass.h"19#include "llvm/CodeGen/MachinePostDominators.h"20#include "llvm/CodeGen/MachineRegisterInfo.h"21#include "llvm/CodeGen/Passes.h"22#include "llvm/CodeGen/TargetFrameLowering.h"23#include "llvm/CodeGen/TargetInstrInfo.h"24#include "llvm/CodeGen/TargetSubtargetInfo.h"25#include "llvm/InitializePasses.h"26#include "llvm/Support/Debug.h"27 28using namespace llvm;29 30#define DEBUG_TYPE "ppc-branch-coalescing"31 32STATISTIC(NumBlocksCoalesced, "Number of blocks coalesced");33STATISTIC(NumPHINotMoved, "Number of PHI Nodes that cannot be merged");34STATISTIC(NumBlocksNotCoalesced, "Number of blocks not coalesced");35 36//===----------------------------------------------------------------------===//37// PPCBranchCoalescing38//===----------------------------------------------------------------------===//39///40/// Improve scheduling by coalescing branches that depend on the same condition.41/// This pass looks for blocks that are guarded by the same branch condition42/// and attempts to merge the blocks together. Such opportunities arise from43/// the expansion of select statements in the IR.44///45/// This pass does not handle implicit operands on branch statements. In order46/// to run on targets that use implicit operands, changes need to be made in the47/// canCoalesceBranch and canMerge methods.48///49/// Example: the following LLVM IR50///51/// %test = icmp eq i32 %x 052/// %tmp1 = select i1 %test, double %a, double 2.000000e-0353/// %tmp2 = select i1 %test, double %b, double 5.000000e-0354///55/// expands to the following machine code:56///57/// %bb.0: derived from LLVM BB %entry58/// liveins: %f1 %f3 %x659/// <SNIP1>60/// %0 = COPY %f1; F8RC:%061/// %5 = CMPLWI killed %4, 0; CRRC:%5 GPRC:%462/// %8 = LXSDX %zero8, killed %7, implicit %rm;63/// mem:LD8[ConstantPool] F8RC:%8 G8RC:%764/// BCC 76, %5, <%bb.2>; CRRC:%565/// Successors according to CFG: %bb.1(?%) %bb.2(?%)66///67/// %bb.1: derived from LLVM BB %entry68/// Predecessors according to CFG: %bb.069/// Successors according to CFG: %bb.2(?%)70///71/// %bb.2: derived from LLVM BB %entry72/// Predecessors according to CFG: %bb.0 %bb.173/// %9 = PHI %8, <%bb.1>, %0, <%bb.0>;74/// F8RC:%9,%8,%075/// <SNIP2>76/// BCC 76, %5, <%bb.4>; CRRC:%577/// Successors according to CFG: %bb.3(?%) %bb.4(?%)78///79/// %bb.3: derived from LLVM BB %entry80/// Predecessors according to CFG: %bb.281/// Successors according to CFG: %bb.4(?%)82///83/// %bb.4: derived from LLVM BB %entry84/// Predecessors according to CFG: %bb.2 %bb.385/// %13 = PHI %12, <%bb.3>, %2, <%bb.2>;86/// F8RC:%13,%12,%287/// <SNIP3>88/// BLR8 implicit %lr8, implicit %rm, implicit %f189///90/// When this pattern is detected, branch coalescing will try to collapse91/// it by moving code in %bb.2 to %bb.0 and/or %bb.4 and removing %bb.3.92///93/// If all conditions are meet, IR should collapse to:94///95/// %bb.0: derived from LLVM BB %entry96/// liveins: %f1 %f3 %x697/// <SNIP1>98/// %0 = COPY %f1; F8RC:%099/// %5 = CMPLWI killed %4, 0; CRRC:%5 GPRC:%4100/// %8 = LXSDX %zero8, killed %7, implicit %rm;101/// mem:LD8[ConstantPool] F8RC:%8 G8RC:%7102/// <SNIP2>103/// BCC 76, %5, <%bb.4>; CRRC:%5104/// Successors according to CFG: %bb.1(0x2aaaaaaa / 0x80000000 = 33.33%)105/// %bb.4(0x55555554 / 0x80000000 = 66.67%)106///107/// %bb.1: derived from LLVM BB %entry108/// Predecessors according to CFG: %bb.0109/// Successors according to CFG: %bb.4(0x40000000 / 0x80000000 = 50.00%)110///111/// %bb.4: derived from LLVM BB %entry112/// Predecessors according to CFG: %bb.0 %bb.1113/// %9 = PHI %8, <%bb.1>, %0, <%bb.0>;114/// F8RC:%9,%8,%0115/// %13 = PHI %12, <%bb.1>, %2, <%bb.0>;116/// F8RC:%13,%12,%2117/// <SNIP3>118/// BLR8 implicit %lr8, implicit %rm, implicit %f1119///120/// Branch Coalescing does not split blocks, it moves everything in the same121/// direction ensuring it does not break use/definition semantics.122///123/// PHI nodes and its corresponding use instructions are moved to its successor124/// block if there are no uses within the successor block PHI nodes. PHI125/// node ordering cannot be assumed.126///127/// Non-PHI can be moved up to the predecessor basic block or down to the128/// successor basic block following any PHI instructions. Whether it moves129/// up or down depends on whether the register(s) defined in the instructions130/// are used in current block or in any PHI instructions at the beginning of131/// the successor block.132 133namespace {134 135class PPCBranchCoalescing : public MachineFunctionPass {136 struct CoalescingCandidateInfo {137 MachineBasicBlock *BranchBlock; // Block containing the branch138 MachineBasicBlock *BranchTargetBlock; // Block branched to139 MachineBasicBlock *FallThroughBlock; // Fall-through if branch not taken140 SmallVector<MachineOperand, 4> Cond;141 bool MustMoveDown;142 bool MustMoveUp;143 144 CoalescingCandidateInfo();145 void clear();146 };147 148 MachineDominatorTree *MDT;149 MachinePostDominatorTree *MPDT;150 const TargetInstrInfo *TII;151 MachineRegisterInfo *MRI;152 153 void initialize(MachineFunction &F);154 bool canCoalesceBranch(CoalescingCandidateInfo &Cand);155 bool identicalOperands(ArrayRef<MachineOperand> OperandList1,156 ArrayRef<MachineOperand> OperandList2) const;157 bool validateCandidates(CoalescingCandidateInfo &SourceRegion,158 CoalescingCandidateInfo &TargetRegion) const;159 160public:161 static char ID;162 163 PPCBranchCoalescing() : MachineFunctionPass(ID) {}164 165 void getAnalysisUsage(AnalysisUsage &AU) const override {166 AU.addRequired<MachineDominatorTreeWrapperPass>();167 AU.addRequired<MachinePostDominatorTreeWrapperPass>();168 MachineFunctionPass::getAnalysisUsage(AU);169 }170 171 StringRef getPassName() const override { return "Branch Coalescing"; }172 173 bool mergeCandidates(CoalescingCandidateInfo &SourceRegion,174 CoalescingCandidateInfo &TargetRegion);175 bool canMoveToBeginning(const MachineInstr &MI,176 const MachineBasicBlock &MBB) const;177 bool canMoveToEnd(const MachineInstr &MI,178 const MachineBasicBlock &MBB) const;179 bool canMerge(CoalescingCandidateInfo &SourceRegion,180 CoalescingCandidateInfo &TargetRegion) const;181 void moveAndUpdatePHIs(MachineBasicBlock *SourceRegionMBB,182 MachineBasicBlock *TargetRegionMBB);183 bool runOnMachineFunction(MachineFunction &MF) override;184};185} // End anonymous namespace.186 187char PPCBranchCoalescing::ID = 0;188/// createPPCBranchCoalescingPass - returns an instance of the Branch Coalescing189/// Pass190FunctionPass *llvm::createPPCBranchCoalescingPass() {191 return new PPCBranchCoalescing();192}193 194INITIALIZE_PASS_BEGIN(PPCBranchCoalescing, DEBUG_TYPE,195 "Branch Coalescing", false, false)196INITIALIZE_PASS_DEPENDENCY(MachineDominatorTreeWrapperPass)197INITIALIZE_PASS_DEPENDENCY(MachinePostDominatorTreeWrapperPass)198INITIALIZE_PASS_END(PPCBranchCoalescing, DEBUG_TYPE, "Branch Coalescing",199 false, false)200 201PPCBranchCoalescing::CoalescingCandidateInfo::CoalescingCandidateInfo()202 : BranchBlock(nullptr), BranchTargetBlock(nullptr),203 FallThroughBlock(nullptr), MustMoveDown(false), MustMoveUp(false) {}204 205void PPCBranchCoalescing::CoalescingCandidateInfo::clear() {206 BranchBlock = nullptr;207 BranchTargetBlock = nullptr;208 FallThroughBlock = nullptr;209 Cond.clear();210 MustMoveDown = false;211 MustMoveUp = false;212}213 214void PPCBranchCoalescing::initialize(MachineFunction &MF) {215 MDT = &getAnalysis<MachineDominatorTreeWrapperPass>().getDomTree();216 MPDT = &getAnalysis<MachinePostDominatorTreeWrapperPass>().getPostDomTree();217 TII = MF.getSubtarget().getInstrInfo();218 MRI = &MF.getRegInfo();219}220 221///222/// Analyze the branch statement to determine if it can be coalesced. This223/// method analyses the branch statement for the given candidate to determine224/// if it can be coalesced. If the branch can be coalesced, then the225/// BranchTargetBlock and the FallThroughBlock are recorded in the specified226/// Candidate.227///228///\param[in,out] Cand The coalescing candidate to analyze229///\return true if and only if the branch can be coalesced, false otherwise230///231bool PPCBranchCoalescing::canCoalesceBranch(CoalescingCandidateInfo &Cand) {232 LLVM_DEBUG(dbgs() << "Determine if branch block "233 << Cand.BranchBlock->getNumber() << " can be coalesced:");234 MachineBasicBlock *FalseMBB = nullptr;235 236 if (TII->analyzeBranch(*Cand.BranchBlock, Cand.BranchTargetBlock, FalseMBB,237 Cand.Cond)) {238 LLVM_DEBUG(dbgs() << "TII unable to Analyze Branch - skip\n");239 return false;240 }241 242 for (auto &I : Cand.BranchBlock->terminators()) {243 LLVM_DEBUG(dbgs() << "Looking at terminator : " << I << "\n");244 if (!I.isBranch())245 continue;246 247 // The analyzeBranch method does not include any implicit operands.248 // This is not an issue on PPC but must be handled on other targets.249 // For this pass to be made target-independent, the analyzeBranch API250 // need to be updated to support implicit operands and there would251 // need to be a way to verify that any implicit operands would not be252 // clobbered by merging blocks. This would include identifying the253 // implicit operands as well as the basic block they are defined in.254 // This could be done by changing the analyzeBranch API to have it also255 // record and return the implicit operands and the blocks where they are256 // defined. Alternatively, the BranchCoalescing code would need to be257 // extended to identify the implicit operands. The analysis in canMerge258 // must then be extended to prove that none of the implicit operands are259 // changed in the blocks that are combined during coalescing.260 if (I.getNumOperands() != I.getNumExplicitOperands()) {261 LLVM_DEBUG(dbgs() << "Terminator contains implicit operands - skip : "262 << I << "\n");263 return false;264 }265 }266 267 if (Cand.BranchBlock->isEHPad() || Cand.BranchBlock->hasEHPadSuccessor()) {268 LLVM_DEBUG(dbgs() << "EH Pad - skip\n");269 return false;270 }271 272 if (Cand.BranchBlock->mayHaveInlineAsmBr()) {273 LLVM_DEBUG(dbgs() << "Inline Asm Br - skip\n");274 return false;275 }276 277 // For now only consider triangles (i.e, BranchTargetBlock is set,278 // FalseMBB is null, and BranchTargetBlock is a successor to BranchBlock)279 if (!Cand.BranchTargetBlock || FalseMBB ||280 !Cand.BranchBlock->isSuccessor(Cand.BranchTargetBlock)) {281 LLVM_DEBUG(dbgs() << "Does not form a triangle - skip\n");282 return false;283 }284 285 // Ensure there are only two successors286 if (Cand.BranchBlock->succ_size() != 2) {287 LLVM_DEBUG(dbgs() << "Does not have 2 successors - skip\n");288 return false;289 }290 291 // The block must be able to fall through.292 assert(Cand.BranchBlock->canFallThrough() &&293 "Expecting the block to fall through!");294 295 // We have already ensured there are exactly two successors to296 // BranchBlock and that BranchTargetBlock is a successor to BranchBlock.297 // Ensure the single fall though block is empty.298 MachineBasicBlock *Succ =299 (*Cand.BranchBlock->succ_begin() == Cand.BranchTargetBlock)300 ? *Cand.BranchBlock->succ_rbegin()301 : *Cand.BranchBlock->succ_begin();302 303 assert(Succ && "Expecting a valid fall-through block\n");304 305 if (!Succ->empty()) {306 LLVM_DEBUG(dbgs() << "Fall-through block contains code -- skip\n");307 return false;308 }309 310 if (!Succ->isSuccessor(Cand.BranchTargetBlock)) {311 LLVM_DEBUG(312 dbgs()313 << "Successor of fall through block is not branch taken block\n");314 return false;315 }316 317 Cand.FallThroughBlock = Succ;318 LLVM_DEBUG(dbgs() << "Valid Candidate\n");319 return true;320}321 322///323/// Determine if the two operand lists are identical324///325/// \param[in] OpList1 operand list326/// \param[in] OpList2 operand list327/// \return true if and only if the operands lists are identical328///329bool PPCBranchCoalescing::identicalOperands(330 ArrayRef<MachineOperand> OpList1, ArrayRef<MachineOperand> OpList2) const {331 332 if (OpList1.size() != OpList2.size()) {333 LLVM_DEBUG(dbgs() << "Operand list is different size\n");334 return false;335 }336 337 for (unsigned i = 0; i < OpList1.size(); ++i) {338 const MachineOperand &Op1 = OpList1[i];339 const MachineOperand &Op2 = OpList2[i];340 341 LLVM_DEBUG(dbgs() << "Op1: " << Op1 << "\n"342 << "Op2: " << Op2 << "\n");343 344 if (Op1.isIdenticalTo(Op2)) {345 // filter out instructions with physical-register uses346 if (Op1.isReg() && Op1.getReg().isPhysical()347 // If the physical register is constant then we can assume the value348 // has not changed between uses.349 && !(Op1.isUse() && MRI->isConstantPhysReg(Op1.getReg()))) {350 LLVM_DEBUG(dbgs() << "The operands are not provably identical.\n");351 return false;352 }353 LLVM_DEBUG(dbgs() << "Op1 and Op2 are identical!\n");354 continue;355 }356 357 // If the operands are not identical, but are registers, check to see if the358 // definition of the register produces the same value. If they produce the359 // same value, consider them to be identical.360 if (Op1.isReg() && Op2.isReg() && Op1.getReg().isVirtual() &&361 Op2.getReg().isVirtual()) {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 " << *Op2Def366 << " 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 TargetMBB382/// and update them to refer to the new block. PHI node ordering383/// cannot be assumed so it does not matter where the PHI instructions384/// are moved to in TargetMBB.385///386/// \param[in] SourceMBB block to move PHI instructions from387/// \param[in] TargetMBB block to move PHI instructions to388///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 TargetMBB401 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 TargetMBB414/// following PHI instructions. A MI instruction can be moved to beginning of415/// 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 to419/// \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 &TargetMBB424 ) 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 Def430 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 moved445/// to then end of the TargetMBB if no PHI node defines what MI uses within446/// it's own MBB.447///448/// \param[in] MI the machine instruction to move.449/// \param[in] TargetMBB the machine basic block to move to450/// \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 &TargetMBB455 ) 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() && Use.getReg().isVirtual()) {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 the479/// expected pattern required for coalescing.480///481/// \param[in] SourceRegion The candidate to move statements from482/// \param[in] TargetRegion The candidate to move statements to483/// \return true if all instructions in SourceRegion.BranchBlock can be merged484/// 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 to506/// 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 the509/// TargetRegion.BranchTargetBlock (also SourceRegion.BranchBlock).510///511/// This function first try to move instructions from the512/// TargetRegion.BranchTargetBlock down, to the beginning of the513/// SourceRegion.BranchTargetBlock. This is not possible if any register defined514/// in TargetRegion.BranchTargetBlock is used in a PHI node in the515/// SourceRegion.BranchTargetBlock. In this case, check whether the statement516/// can be moved up, to the end of the TargetRegion.BranchBlock (immediately517/// before the branch statement). If it cannot move, then these blocks cannot518/// be merged.519///520/// Note that there is no analysis for moving instructions past the fall-through521/// blocks because they are confirmed to be empty. An assert is thrown if they522/// are not.523///524/// \param[in] SourceRegion The candidate to move statements from525/// \param[in] TargetRegion The candidate to move statements to526/// \return true if all instructions in SourceRegion.BranchBlock can be merged527/// 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 the535 // SourceRegion.BranchTargetBlock.536 for (MachineBasicBlock::iterator537 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 " << *I545 << " 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 " << *I552 << " 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 into560 // TargetRegion.BranchBlock (up) or SourceRegion.BranchTargetBlock (down)561 for (MachineBasicBlock::iterator562 I = SourceRegion.BranchBlock->getFirstNonPHI(),563 E = SourceRegion.BranchBlock->end();564 I != E; ++I) {565 if (!canMoveToBeginning(*I, *SourceRegion.BranchTargetBlock)) {566 LLVM_DEBUG(dbgs() << "Instruction " << *I567 << " cannot move down - must move up!\n");568 SourceRegion.MustMoveUp = true;569 }570 if (!canMoveToEnd(*I, *TargetRegion.BranchBlock)) {571 LLVM_DEBUG(dbgs() << "Instruction " << *I572 << " 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 into582/// TargetRegion.BranchBlock, TargetRegion.BranchTargetBlock and583/// TargetRegion.FallThroughBlock respectively.584///585/// The successors for blocks in TargetRegion will be updated to use the586/// successors from blocks in SourceRegion. Finally, the blocks in SourceRegion587/// will be removed from the function.588///589/// A region consists of a BranchBlock, a FallThroughBlock, and a590/// BranchTargetBlock. Branch coalesce works on patterns where the591/// TargetRegion's BranchTargetBlock must also be the SourceRegions's592/// 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 from634/// \param[in] TargetRegion The candidate to move blocks to635///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 block649 moveAndUpdatePHIs(SourceRegion.BranchBlock, SourceRegion.BranchTargetBlock);650 651 // Move remaining instructions in SourceRegion.BranchBlock into652 // TargetRegion.BranchBlock653 MachineBasicBlock::iterator firstInstr =654 SourceRegion.BranchBlock->getFirstNonPHI();655 MachineBasicBlock::iterator lastInstr =656 SourceRegion.BranchBlock->getFirstTerminator();657 658 MachineBasicBlock *Source = SourceRegion.MustMoveDown659 ? SourceRegion.BranchTargetBlock660 : TargetRegion.BranchBlock;661 662 MachineBasicBlock::iterator Target =663 SourceRegion.MustMoveDown664 ? 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 the670 // control flow.671 672 // Remove SourceRegion.FallThroughBlock before transferring successors of673 // 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 to678 // SourceRegion.BranchTargetBlock679 // In this case, TargetRegion.BranchTargetBlock == SourceRegion.BranchBlock.680 TargetRegion.BranchBlock->ReplaceUsesOfBlockWith(681 SourceRegion.BranchBlock, SourceRegion.BranchTargetBlock);682 // Remove the branch statement(s) in SourceRegion.BranchBlock683 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 condition693 // to coalesce the branches.694 assert(TargetRegion.FallThroughBlock->empty() &&695 "FallThroughBlocks should be empty!");696 697 // Transfer successor information and move PHIs down to the698 // branch-taken block.699 TargetRegion.FallThroughBlock->transferSuccessorsAndUpdatePHIs(700 SourceRegion.FallThroughBlock);701 TargetRegion.FallThroughBlock->removeSuccessor(SourceRegion.BranchBlock);702 TargetRegion.FallThroughBlock->normalizeSuccProbs();703 704 // Remove the blocks from the function.705 assert(SourceRegion.BranchBlock->empty() &&706 "Expecting branch block to be empty!");707 SourceRegion.BranchBlock->eraseFromParent();708 709 assert(SourceRegion.FallThroughBlock->empty() &&710 "Expecting fall-through block to be empty!\n");711 SourceRegion.FallThroughBlock->eraseFromParent();712 713 NumBlocksCoalesced++;714 return true;715}716 717bool PPCBranchCoalescing::runOnMachineFunction(MachineFunction &MF) {718 719 if (skipFunction(MF.getFunction()) || MF.empty())720 return false;721 722 bool didSomething = false;723 724 LLVM_DEBUG(dbgs() << "******** Branch Coalescing ********\n");725 initialize(MF);726 727 LLVM_DEBUG(dbgs() << "Function: "; MF.dump(); dbgs() << "\n");728 729 CoalescingCandidateInfo Cand1, Cand2;730 // Walk over blocks and find candidates to merge731 // Continue trying to merge with the first candidate found, as long as merging732 // is successfull.733 for (MachineBasicBlock &MBB : MF) {734 bool MergedCandidates = false;735 do {736 MergedCandidates = false;737 Cand1.clear();738 Cand2.clear();739 740 Cand1.BranchBlock = &MBB;741 742 // If unable to coalesce the branch, then continue to next block743 if (!canCoalesceBranch(Cand1))744 break;745 746 Cand2.BranchBlock = Cand1.BranchTargetBlock;747 if (!canCoalesceBranch(Cand2))748 break;749 750 // The branch-taken block of the second candidate should post-dominate the751 // 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 NDEBUG781 // Verify MF is still valid after branch coalescing782 if (didSomething)783 MF.verify(nullptr, "Error in code produced by branch coalescing");784#endif // NDEBUG785 786 LLVM_DEBUG(dbgs() << "Finished Branch Coalescing\n");787 return didSomething;788}789