BranchFolding.cpp revision 2210c0bea83aa8a8585d793a1f63e8c01b65be38
121ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner//===-- BranchFolding.cpp - Fold machine code branch instructions ---------===// 2edf128a7fa90f2b0b7ee24741a04a7ae1ecd6f7eMisha Brukman// 321ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner// The LLVM Compiler Infrastructure 421ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner// 54ee451de366474b9c228b4e5fa573795a715216dChris Lattner// This file is distributed under the University of Illinois Open Source 64ee451de366474b9c228b4e5fa573795a715216dChris Lattner// License. See LICENSE.TXT for details. 7edf128a7fa90f2b0b7ee24741a04a7ae1ecd6f7eMisha Brukman// 821ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner//===----------------------------------------------------------------------===// 921ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner// 1021ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner// This pass forwards branches to unconditional branches to make them branch 1121ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner// directly to the target block. This pass often results in dead MBB's, which 1221ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner// it then removes. 1321ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner// 1421ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner// Note that this pass must be run after register allocation, it cannot handle 1521ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner// SSA form. 1621ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner// 1721ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner//===----------------------------------------------------------------------===// 1821ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner 19f10a56a86f8ae32d0493c7de770493d55519b073Chris Lattner#define DEBUG_TYPE "branchfolding" 20030a0a0cdb38924e55773a8e0b5fe7347aa664aaEvan Cheng#include "BranchFolding.h" 212c04dae715b05017d7d2c19ab4f8cb37c1e650aeBob Wilson#include "llvm/Function.h" 2221ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner#include "llvm/CodeGen/Passes.h" 2344c3b9fdd416c79f4b67cde1aecfced5921efd81Jim Laskey#include "llvm/CodeGen/MachineModuleInfo.h" 2421ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner#include "llvm/CodeGen/MachineFunctionPass.h" 25c50ffcb7fcb7c1109fee2406e8f74d096f755f47Chris Lattner#include "llvm/CodeGen/MachineJumpTableInfo.h" 2669cb9b78f11d505f4351a269fc90e7b77fcda437Dale Johannesen#include "llvm/CodeGen/RegisterScavenging.h" 2721ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner#include "llvm/Target/TargetInstrInfo.h" 2821ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner#include "llvm/Target/TargetMachine.h" 296f0d024a534af18d9e60b3ea757376cd8a3a980eDan Gohman#include "llvm/Target/TargetRegisterInfo.h" 3012143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner#include "llvm/Support/CommandLine.h" 31f10a56a86f8ae32d0493c7de770493d55519b073Chris Lattner#include "llvm/Support/Debug.h" 32c25e7581b9b8088910da31702d4ca21c4734c6d7Torok Edwin#include "llvm/Support/ErrorHandling.h" 333403bcd8f943cb053a7d9bbf8eb8135407699afaBill Wendling#include "llvm/Support/raw_ostream.h" 3480b09fe8bc1d2755ef9a6b03b8862a657db42f06Evan Cheng#include "llvm/ADT/SmallSet.h" 352210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman#include "llvm/ADT/SetVector.h" 3612143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner#include "llvm/ADT/Statistic.h" 37551ccae044b0ff658fe629dd67edd5ffe75d10e8Reid Spencer#include "llvm/ADT/STLExtras.h" 38d41b30def3181bce4bf87e8bde664d15663165d0Jeff Cohen#include <algorithm> 3921ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattnerusing namespace llvm; 4021ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner 41cd3245ac45c595da96bb768a55cddc356dff55feChris LattnerSTATISTIC(NumDeadBlocks, "Number of dead blocks removed"); 42cd3245ac45c595da96bb768a55cddc356dff55feChris LattnerSTATISTIC(NumBranchOpts, "Number of branches optimized"); 43cd3245ac45c595da96bb768a55cddc356dff55feChris LattnerSTATISTIC(NumTailMerge , "Number of block tails merged"); 444e3f125e184f96ae72f2c44d16cafe0d44158283Dan Gohmanstatic cl::opt<cl::boolOrDefault> FlagEnableTailMerge("enable-tail-merge", 4581da02b553b86868637f27b89c6e919c31ed5b51Dale Johannesen cl::init(cl::BOU_UNSET), cl::Hidden); 46844731a7f1909f55935e3514c9e713a62d67662eDan Gohman// Throttle for huge numbers of predecessors (compile speed problems) 47844731a7f1909f55935e3514c9e713a62d67662eDan Gohmanstatic cl::opt<unsigned> 484e3f125e184f96ae72f2c44d16cafe0d44158283Dan GohmanTailMergeThreshold("tail-merge-threshold", 49844731a7f1909f55935e3514c9e713a62d67662eDan Gohman cl::desc("Max number of predecessors to consider tail merging"), 50622addbe49ffdc611adb315fb22756e23fe7b222Dale Johannesen cl::init(150), cl::Hidden); 511a90a5aebe3488dc3feaab60ba16bed1659ba27bDale Johannesen 522210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman// Heuristic for tail merging (and, inversely, tail duplication). 532210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman// TODO: This should be replaced with a target query. 542210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohmanstatic cl::opt<unsigned> 552210c0bea83aa8a8585d793a1f63e8c01b65be38Dan GohmanTailMergeSize("tail-merge-size", 562210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman cl::desc("Min number of instructions to consider tail merging"), 572210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman cl::init(3), cl::Hidden); 58794fd75c67a2cdc128d67342c6d88a504d186896Devang Patel 59030a0a0cdb38924e55773a8e0b5fe7347aa664aaEvan Chengchar BranchFolderPass::ID = 0; 6021ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner 612210c0bea83aa8a8585d793a1f63e8c01b65be38Dan GohmanPass *llvm::createBranchFoldingPass(bool DefaultEnableTailMerge) { 62a597103c328e29fb763e7a4864bd7c29a588fc9dBob Wilson return new BranchFolderPass(DefaultEnableTailMerge); 63030a0a0cdb38924e55773a8e0b5fe7347aa664aaEvan Cheng} 64030a0a0cdb38924e55773a8e0b5fe7347aa664aaEvan Cheng 65030a0a0cdb38924e55773a8e0b5fe7347aa664aaEvan Chengbool BranchFolderPass::runOnMachineFunction(MachineFunction &MF) { 66030a0a0cdb38924e55773a8e0b5fe7347aa664aaEvan Cheng return OptimizeFunction(MF, 67030a0a0cdb38924e55773a8e0b5fe7347aa664aaEvan Cheng MF.getTarget().getInstrInfo(), 68030a0a0cdb38924e55773a8e0b5fe7347aa664aaEvan Cheng MF.getTarget().getRegisterInfo(), 69030a0a0cdb38924e55773a8e0b5fe7347aa664aaEvan Cheng getAnalysisIfAvailable<MachineModuleInfo>()); 70030a0a0cdb38924e55773a8e0b5fe7347aa664aaEvan Cheng} 71030a0a0cdb38924e55773a8e0b5fe7347aa664aaEvan Cheng 72030a0a0cdb38924e55773a8e0b5fe7347aa664aaEvan Cheng 73a597103c328e29fb763e7a4864bd7c29a588fc9dBob WilsonBranchFolder::BranchFolder(bool defaultEnableTailMerge) { 74030a0a0cdb38924e55773a8e0b5fe7347aa664aaEvan Cheng switch (FlagEnableTailMerge) { 75030a0a0cdb38924e55773a8e0b5fe7347aa664aaEvan Cheng case cl::BOU_UNSET: EnableTailMerge = defaultEnableTailMerge; break; 76030a0a0cdb38924e55773a8e0b5fe7347aa664aaEvan Cheng case cl::BOU_TRUE: EnableTailMerge = true; break; 77030a0a0cdb38924e55773a8e0b5fe7347aa664aaEvan Cheng case cl::BOU_FALSE: EnableTailMerge = false; break; 78030a0a0cdb38924e55773a8e0b5fe7347aa664aaEvan Cheng } 79b3c27428969b3cc52ab8493e91b5dd1465325fedEvan Cheng} 8021ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner 81c50ffcb7fcb7c1109fee2406e8f74d096f755f47Chris Lattner/// RemoveDeadBlock - Remove the specified dead machine basic block from the 82c50ffcb7fcb7c1109fee2406e8f74d096f755f47Chris Lattner/// function, updating the CFG. 83683747abb81a7b7711ad6cb5abf5a4227f7ab691Chris Lattnervoid BranchFolder::RemoveDeadBlock(MachineBasicBlock *MBB) { 84033c9715d9bf7ce59ad2e466bf0720811b34da08Jim Laskey assert(MBB->pred_empty() && "MBB must be dead!"); 853403bcd8f943cb053a7d9bbf8eb8135407699afaBill Wendling DEBUG(errs() << "\nRemoving MBB: " << *MBB); 864e3f125e184f96ae72f2c44d16cafe0d44158283Dan Gohman 87c50ffcb7fcb7c1109fee2406e8f74d096f755f47Chris Lattner MachineFunction *MF = MBB->getParent(); 88c50ffcb7fcb7c1109fee2406e8f74d096f755f47Chris Lattner // drop all successors. 89c50ffcb7fcb7c1109fee2406e8f74d096f755f47Chris Lattner while (!MBB->succ_empty()) 90c50ffcb7fcb7c1109fee2406e8f74d096f755f47Chris Lattner MBB->removeSuccessor(MBB->succ_end()-1); 914e3f125e184f96ae72f2c44d16cafe0d44158283Dan Gohman 9268d4d1d49c813d10047ad116e897a17d67112c10Duncan Sands // If there are any labels in the basic block, unregister them from 9368d4d1d49c813d10047ad116e897a17d67112c10Duncan Sands // MachineModuleInfo. 9444c3b9fdd416c79f4b67cde1aecfced5921efd81Jim Laskey if (MMI && !MBB->empty()) { 95683747abb81a7b7711ad6cb5abf5a4227f7ab691Chris Lattner for (MachineBasicBlock::iterator I = MBB->begin(), E = MBB->end(); 96683747abb81a7b7711ad6cb5abf5a4227f7ab691Chris Lattner I != E; ++I) { 9768d4d1d49c813d10047ad116e897a17d67112c10Duncan Sands if (I->isLabel()) 98683747abb81a7b7711ad6cb5abf5a4227f7ab691Chris Lattner // The label ID # is always operand #0, an immediate. 9944c3b9fdd416c79f4b67cde1aecfced5921efd81Jim Laskey MMI->InvalidateLabel(I->getOperand(0).getImm()); 100683747abb81a7b7711ad6cb5abf5a4227f7ab691Chris Lattner } 101683747abb81a7b7711ad6cb5abf5a4227f7ab691Chris Lattner } 1024e3f125e184f96ae72f2c44d16cafe0d44158283Dan Gohman 103c50ffcb7fcb7c1109fee2406e8f74d096f755f47Chris Lattner // Remove the block. 1048e5f2c6f65841542e2a7092553fe42a00048e4c7Dan Gohman MF->erase(MBB); 105c50ffcb7fcb7c1109fee2406e8f74d096f755f47Chris Lattner} 106c50ffcb7fcb7c1109fee2406e8f74d096f755f47Chris Lattner 10780b09fe8bc1d2755ef9a6b03b8862a657db42f06Evan Cheng/// OptimizeImpDefsBlock - If a basic block is just a bunch of implicit_def 10880b09fe8bc1d2755ef9a6b03b8862a657db42f06Evan Cheng/// followed by terminators, and if the implicitly defined registers are not 10980b09fe8bc1d2755ef9a6b03b8862a657db42f06Evan Cheng/// used by the terminators, remove those implicit_def's. e.g. 11080b09fe8bc1d2755ef9a6b03b8862a657db42f06Evan Cheng/// BB1: 11180b09fe8bc1d2755ef9a6b03b8862a657db42f06Evan Cheng/// r0 = implicit_def 11280b09fe8bc1d2755ef9a6b03b8862a657db42f06Evan Cheng/// r1 = implicit_def 11380b09fe8bc1d2755ef9a6b03b8862a657db42f06Evan Cheng/// br 11480b09fe8bc1d2755ef9a6b03b8862a657db42f06Evan Cheng/// This block can be optimized away later if the implicit instructions are 11580b09fe8bc1d2755ef9a6b03b8862a657db42f06Evan Cheng/// removed. 11680b09fe8bc1d2755ef9a6b03b8862a657db42f06Evan Chengbool BranchFolder::OptimizeImpDefsBlock(MachineBasicBlock *MBB) { 11780b09fe8bc1d2755ef9a6b03b8862a657db42f06Evan Cheng SmallSet<unsigned, 4> ImpDefRegs; 11880b09fe8bc1d2755ef9a6b03b8862a657db42f06Evan Cheng MachineBasicBlock::iterator I = MBB->begin(); 11980b09fe8bc1d2755ef9a6b03b8862a657db42f06Evan Cheng while (I != MBB->end()) { 12080b09fe8bc1d2755ef9a6b03b8862a657db42f06Evan Cheng if (I->getOpcode() != TargetInstrInfo::IMPLICIT_DEF) 12180b09fe8bc1d2755ef9a6b03b8862a657db42f06Evan Cheng break; 12280b09fe8bc1d2755ef9a6b03b8862a657db42f06Evan Cheng unsigned Reg = I->getOperand(0).getReg(); 12380b09fe8bc1d2755ef9a6b03b8862a657db42f06Evan Cheng ImpDefRegs.insert(Reg); 124030a0a0cdb38924e55773a8e0b5fe7347aa664aaEvan Cheng for (const unsigned *SubRegs = TRI->getSubRegisters(Reg); 12580b09fe8bc1d2755ef9a6b03b8862a657db42f06Evan Cheng unsigned SubReg = *SubRegs; ++SubRegs) 12680b09fe8bc1d2755ef9a6b03b8862a657db42f06Evan Cheng ImpDefRegs.insert(SubReg); 12780b09fe8bc1d2755ef9a6b03b8862a657db42f06Evan Cheng ++I; 12880b09fe8bc1d2755ef9a6b03b8862a657db42f06Evan Cheng } 12980b09fe8bc1d2755ef9a6b03b8862a657db42f06Evan Cheng if (ImpDefRegs.empty()) 13080b09fe8bc1d2755ef9a6b03b8862a657db42f06Evan Cheng return false; 13180b09fe8bc1d2755ef9a6b03b8862a657db42f06Evan Cheng 13280b09fe8bc1d2755ef9a6b03b8862a657db42f06Evan Cheng MachineBasicBlock::iterator FirstTerm = I; 13380b09fe8bc1d2755ef9a6b03b8862a657db42f06Evan Cheng while (I != MBB->end()) { 13480b09fe8bc1d2755ef9a6b03b8862a657db42f06Evan Cheng if (!TII->isUnpredicatedTerminator(I)) 13580b09fe8bc1d2755ef9a6b03b8862a657db42f06Evan Cheng return false; 13680b09fe8bc1d2755ef9a6b03b8862a657db42f06Evan Cheng // See if it uses any of the implicitly defined registers. 13780b09fe8bc1d2755ef9a6b03b8862a657db42f06Evan Cheng for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i) { 13880b09fe8bc1d2755ef9a6b03b8862a657db42f06Evan Cheng MachineOperand &MO = I->getOperand(i); 139d735b8019b0f297d7c14b55adcd887af24d8e602Dan Gohman if (!MO.isReg() || !MO.isUse()) 14080b09fe8bc1d2755ef9a6b03b8862a657db42f06Evan Cheng continue; 14180b09fe8bc1d2755ef9a6b03b8862a657db42f06Evan Cheng unsigned Reg = MO.getReg(); 14280b09fe8bc1d2755ef9a6b03b8862a657db42f06Evan Cheng if (ImpDefRegs.count(Reg)) 14380b09fe8bc1d2755ef9a6b03b8862a657db42f06Evan Cheng return false; 14480b09fe8bc1d2755ef9a6b03b8862a657db42f06Evan Cheng } 14580b09fe8bc1d2755ef9a6b03b8862a657db42f06Evan Cheng ++I; 14680b09fe8bc1d2755ef9a6b03b8862a657db42f06Evan Cheng } 14780b09fe8bc1d2755ef9a6b03b8862a657db42f06Evan Cheng 14880b09fe8bc1d2755ef9a6b03b8862a657db42f06Evan Cheng I = MBB->begin(); 14980b09fe8bc1d2755ef9a6b03b8862a657db42f06Evan Cheng while (I != FirstTerm) { 15080b09fe8bc1d2755ef9a6b03b8862a657db42f06Evan Cheng MachineInstr *ImpDefMI = &*I; 15180b09fe8bc1d2755ef9a6b03b8862a657db42f06Evan Cheng ++I; 15280b09fe8bc1d2755ef9a6b03b8862a657db42f06Evan Cheng MBB->erase(ImpDefMI); 15380b09fe8bc1d2755ef9a6b03b8862a657db42f06Evan Cheng } 15480b09fe8bc1d2755ef9a6b03b8862a657db42f06Evan Cheng 15580b09fe8bc1d2755ef9a6b03b8862a657db42f06Evan Cheng return true; 15680b09fe8bc1d2755ef9a6b03b8862a657db42f06Evan Cheng} 15780b09fe8bc1d2755ef9a6b03b8862a657db42f06Evan Cheng 158030a0a0cdb38924e55773a8e0b5fe7347aa664aaEvan Cheng/// OptimizeFunction - Perhaps branch folding, tail merging and other 159030a0a0cdb38924e55773a8e0b5fe7347aa664aaEvan Cheng/// CFG optimizations on the given function. 160030a0a0cdb38924e55773a8e0b5fe7347aa664aaEvan Chengbool BranchFolder::OptimizeFunction(MachineFunction &MF, 161030a0a0cdb38924e55773a8e0b5fe7347aa664aaEvan Cheng const TargetInstrInfo *tii, 162030a0a0cdb38924e55773a8e0b5fe7347aa664aaEvan Cheng const TargetRegisterInfo *tri, 163030a0a0cdb38924e55773a8e0b5fe7347aa664aaEvan Cheng MachineModuleInfo *mmi) { 164030a0a0cdb38924e55773a8e0b5fe7347aa664aaEvan Cheng if (!tii) return false; 165030a0a0cdb38924e55773a8e0b5fe7347aa664aaEvan Cheng 166030a0a0cdb38924e55773a8e0b5fe7347aa664aaEvan Cheng TII = tii; 167030a0a0cdb38924e55773a8e0b5fe7347aa664aaEvan Cheng TRI = tri; 168030a0a0cdb38924e55773a8e0b5fe7347aa664aaEvan Cheng MMI = mmi; 1697821a8afd3009c3c2760592e61de9e2c31c73e18Chris Lattner 170030a0a0cdb38924e55773a8e0b5fe7347aa664aaEvan Cheng RS = TRI->requiresRegisterScavenging(MF) ? new RegScavenger() : NULL; 17180b09fe8bc1d2755ef9a6b03b8862a657db42f06Evan Cheng 17214ba0cc42959a3fcc9b6781aea614b01877fb55fDale Johannesen // Fix CFG. The later algorithms expect it to be right. 173030a0a0cdb38924e55773a8e0b5fe7347aa664aaEvan Cheng bool MadeChange = false; 17414ba0cc42959a3fcc9b6781aea614b01877fb55fDale Johannesen for (MachineFunction::iterator I = MF.begin(), E = MF.end(); I != E; I++) { 17514ba0cc42959a3fcc9b6781aea614b01877fb55fDale Johannesen MachineBasicBlock *MBB = I, *TBB = 0, *FBB = 0; 17644eb65cf58e3ab9b5621ce72256d1621a18aeed7Owen Anderson SmallVector<MachineOperand, 4> Cond; 177dc54d317e7a381ef8e4aca80d54ad1466bb85ddaEvan Cheng if (!TII->AnalyzeBranch(*MBB, TBB, FBB, Cond, true)) 178030a0a0cdb38924e55773a8e0b5fe7347aa664aaEvan Cheng MadeChange |= MBB->CorrectExtraCFGEdges(TBB, FBB, !Cond.empty()); 179030a0a0cdb38924e55773a8e0b5fe7347aa664aaEvan Cheng MadeChange |= OptimizeImpDefsBlock(MBB); 18014ba0cc42959a3fcc9b6781aea614b01877fb55fDale Johannesen } 18114ba0cc42959a3fcc9b6781aea614b01877fb55fDale Johannesen 18276b38fcabeba725e166a2ff72c56fe31d784b229Dale Johannesen 18312143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner bool MadeChangeThisIteration = true; 18412143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner while (MadeChangeThisIteration) { 18512143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner MadeChangeThisIteration = false; 18612143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner MadeChangeThisIteration |= TailMergeBlocks(MF); 18712143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner MadeChangeThisIteration |= OptimizeBranches(MF); 188030a0a0cdb38924e55773a8e0b5fe7347aa664aaEvan Cheng MadeChange |= MadeChangeThisIteration; 18912143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner } 19012143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner 1916acfe12dd6d52c801f78c240528b7cb42fa91159Chris Lattner // See if any jump tables have become mergable or dead as the code generator 1926acfe12dd6d52c801f78c240528b7cb42fa91159Chris Lattner // did its thing. 1936acfe12dd6d52c801f78c240528b7cb42fa91159Chris Lattner MachineJumpTableInfo *JTI = MF.getJumpTableInfo(); 1946acfe12dd6d52c801f78c240528b7cb42fa91159Chris Lattner const std::vector<MachineJumpTableEntry> &JTs = JTI->getJumpTables(); 1956acfe12dd6d52c801f78c240528b7cb42fa91159Chris Lattner if (!JTs.empty()) { 1966acfe12dd6d52c801f78c240528b7cb42fa91159Chris Lattner // Figure out how these jump tables should be merged. 1976acfe12dd6d52c801f78c240528b7cb42fa91159Chris Lattner std::vector<unsigned> JTMapping; 1986acfe12dd6d52c801f78c240528b7cb42fa91159Chris Lattner JTMapping.reserve(JTs.size()); 1994e3f125e184f96ae72f2c44d16cafe0d44158283Dan Gohman 2006acfe12dd6d52c801f78c240528b7cb42fa91159Chris Lattner // We always keep the 0th jump table. 2016acfe12dd6d52c801f78c240528b7cb42fa91159Chris Lattner JTMapping.push_back(0); 2026acfe12dd6d52c801f78c240528b7cb42fa91159Chris Lattner 2036acfe12dd6d52c801f78c240528b7cb42fa91159Chris Lattner // Scan the jump tables, seeing if there are any duplicates. Note that this 2046acfe12dd6d52c801f78c240528b7cb42fa91159Chris Lattner // is N^2, which should be fixed someday. 205030a0a0cdb38924e55773a8e0b5fe7347aa664aaEvan Cheng for (unsigned i = 1, e = JTs.size(); i != e; ++i) { 206030a0a0cdb38924e55773a8e0b5fe7347aa664aaEvan Cheng if (JTs[i].MBBs.empty()) 207030a0a0cdb38924e55773a8e0b5fe7347aa664aaEvan Cheng JTMapping.push_back(i); 208030a0a0cdb38924e55773a8e0b5fe7347aa664aaEvan Cheng else 209030a0a0cdb38924e55773a8e0b5fe7347aa664aaEvan Cheng JTMapping.push_back(JTI->getJumpTableIndex(JTs[i].MBBs)); 210030a0a0cdb38924e55773a8e0b5fe7347aa664aaEvan Cheng } 2114e3f125e184f96ae72f2c44d16cafe0d44158283Dan Gohman 2126acfe12dd6d52c801f78c240528b7cb42fa91159Chris Lattner // If a jump table was merge with another one, walk the function rewriting 2136acfe12dd6d52c801f78c240528b7cb42fa91159Chris Lattner // references to jump tables to reference the new JT ID's. Keep track of 2146acfe12dd6d52c801f78c240528b7cb42fa91159Chris Lattner // whether we see a jump table idx, if not, we can delete the JT. 2156b8583cbf1f8a3df5ae859d3da2ca690ff57f91cDale Johannesen BitVector JTIsLive(JTs.size()); 2166acfe12dd6d52c801f78c240528b7cb42fa91159Chris Lattner for (MachineFunction::iterator BB = MF.begin(), E = MF.end(); 2176acfe12dd6d52c801f78c240528b7cb42fa91159Chris Lattner BB != E; ++BB) { 2186acfe12dd6d52c801f78c240528b7cb42fa91159Chris Lattner for (MachineBasicBlock::iterator I = BB->begin(), E = BB->end(); 2196acfe12dd6d52c801f78c240528b7cb42fa91159Chris Lattner I != E; ++I) 2206acfe12dd6d52c801f78c240528b7cb42fa91159Chris Lattner for (unsigned op = 0, e = I->getNumOperands(); op != e; ++op) { 2216acfe12dd6d52c801f78c240528b7cb42fa91159Chris Lattner MachineOperand &Op = I->getOperand(op); 222d735b8019b0f297d7c14b55adcd887af24d8e602Dan Gohman if (!Op.isJTI()) continue; 2238aa797aa51cd4ea1ec6f46f4891a6897944b75b2Chris Lattner unsigned NewIdx = JTMapping[Op.getIndex()]; 2248aa797aa51cd4ea1ec6f46f4891a6897944b75b2Chris Lattner Op.setIndex(NewIdx); 2256acfe12dd6d52c801f78c240528b7cb42fa91159Chris Lattner 2266acfe12dd6d52c801f78c240528b7cb42fa91159Chris Lattner // Remember that this JT is live. 2276b8583cbf1f8a3df5ae859d3da2ca690ff57f91cDale Johannesen JTIsLive.set(NewIdx); 2286acfe12dd6d52c801f78c240528b7cb42fa91159Chris Lattner } 2296acfe12dd6d52c801f78c240528b7cb42fa91159Chris Lattner } 2304e3f125e184f96ae72f2c44d16cafe0d44158283Dan Gohman 2316acfe12dd6d52c801f78c240528b7cb42fa91159Chris Lattner // Finally, remove dead jump tables. This happens either because the 2326acfe12dd6d52c801f78c240528b7cb42fa91159Chris Lattner // indirect jump was unreachable (and thus deleted) or because the jump 2336acfe12dd6d52c801f78c240528b7cb42fa91159Chris Lattner // table was merged with some other one. 2346acfe12dd6d52c801f78c240528b7cb42fa91159Chris Lattner for (unsigned i = 0, e = JTIsLive.size(); i != e; ++i) 2356b8583cbf1f8a3df5ae859d3da2ca690ff57f91cDale Johannesen if (!JTIsLive.test(i)) { 2366acfe12dd6d52c801f78c240528b7cb42fa91159Chris Lattner JTI->RemoveJumpTable(i); 237030a0a0cdb38924e55773a8e0b5fe7347aa664aaEvan Cheng MadeChange = true; 2386acfe12dd6d52c801f78c240528b7cb42fa91159Chris Lattner } 2396acfe12dd6d52c801f78c240528b7cb42fa91159Chris Lattner } 240030a0a0cdb38924e55773a8e0b5fe7347aa664aaEvan Cheng 24169cb9b78f11d505f4351a269fc90e7b77fcda437Dale Johannesen delete RS; 242030a0a0cdb38924e55773a8e0b5fe7347aa664aaEvan Cheng return MadeChange; 24312143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner} 24412143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner 24512143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner//===----------------------------------------------------------------------===// 24612143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner// Tail Merging of Blocks 24712143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner//===----------------------------------------------------------------------===// 24812143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner 24912143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner/// HashMachineInstr - Compute a hash value for MI and its operands. 25012143054aa6d120f029d268a5154bf2ecd0f707fChris Lattnerstatic unsigned HashMachineInstr(const MachineInstr *MI) { 25112143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner unsigned Hash = MI->getOpcode(); 25212143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 25312143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner const MachineOperand &Op = MI->getOperand(i); 2544e3f125e184f96ae72f2c44d16cafe0d44158283Dan Gohman 25512143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner // Merge in bits from the operand if easy. 25612143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner unsigned OperandHash = 0; 25712143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner switch (Op.getType()) { 25812143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner case MachineOperand::MO_Register: OperandHash = Op.getReg(); break; 25912143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner case MachineOperand::MO_Immediate: OperandHash = Op.getImm(); break; 26012143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner case MachineOperand::MO_MachineBasicBlock: 2618aa797aa51cd4ea1ec6f46f4891a6897944b75b2Chris Lattner OperandHash = Op.getMBB()->getNumber(); 26212143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner break; 2638aa797aa51cd4ea1ec6f46f4891a6897944b75b2Chris Lattner case MachineOperand::MO_FrameIndex: 26412143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner case MachineOperand::MO_ConstantPoolIndex: 26512143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner case MachineOperand::MO_JumpTableIndex: 2668aa797aa51cd4ea1ec6f46f4891a6897944b75b2Chris Lattner OperandHash = Op.getIndex(); 26712143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner break; 26812143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner case MachineOperand::MO_GlobalAddress: 26912143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner case MachineOperand::MO_ExternalSymbol: 27012143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner // Global address / external symbol are too hard, don't bother, but do 27112143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner // pull in the offset. 27212143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner OperandHash = Op.getOffset(); 27312143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner break; 27412143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner default: break; 27512143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner } 2764e3f125e184f96ae72f2c44d16cafe0d44158283Dan Gohman 27712143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner Hash += ((OperandHash << 3) | Op.getType()) << (i&31); 27812143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner } 27912143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner return Hash; 28012143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner} 28112143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner 2827aea8320340ce867eb4328aeec52cb02c88ef0b3Dale Johannesen/// HashEndOfMBB - Hash the last few instructions in the MBB. For blocks 2834e3f125e184f96ae72f2c44d16cafe0d44158283Dan Gohman/// with no successors, we hash two instructions, because cross-jumping 2844e3f125e184f96ae72f2c44d16cafe0d44158283Dan Gohman/// only saves code when at least two instructions are removed (since a 2857aea8320340ce867eb4328aeec52cb02c88ef0b3Dale Johannesen/// branch must be inserted). For blocks with a successor, one of the 2867aea8320340ce867eb4328aeec52cb02c88ef0b3Dale Johannesen/// two blocks to be tail-merged will end with a branch already, so 2877aea8320340ce867eb4328aeec52cb02c88ef0b3Dale Johannesen/// it gains to cross-jump even for one instruction. 2887aea8320340ce867eb4328aeec52cb02c88ef0b3Dale Johannesenstatic unsigned HashEndOfMBB(const MachineBasicBlock *MBB, 2897aea8320340ce867eb4328aeec52cb02c88ef0b3Dale Johannesen unsigned minCommonTailLength) { 29012143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner MachineBasicBlock::const_iterator I = MBB->end(); 29112143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner if (I == MBB->begin()) 29212143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner return 0; // Empty MBB. 2934e3f125e184f96ae72f2c44d16cafe0d44158283Dan Gohman 29412143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner --I; 29512143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner unsigned Hash = HashMachineInstr(I); 2964e3f125e184f96ae72f2c44d16cafe0d44158283Dan Gohman 2977aea8320340ce867eb4328aeec52cb02c88ef0b3Dale Johannesen if (I == MBB->begin() || minCommonTailLength == 1) 29812143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner return Hash; // Single instr MBB. 2994e3f125e184f96ae72f2c44d16cafe0d44158283Dan Gohman 30012143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner --I; 30112143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner // Hash in the second-to-last instruction. 30212143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner Hash ^= HashMachineInstr(I) << 2; 30312143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner return Hash; 30412143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner} 30512143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner 30612143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner/// ComputeCommonTailLength - Given two machine basic blocks, compute the number 30712143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner/// of instructions they actually have in common together at their end. Return 30812143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner/// iterators for the first shared instruction in each block. 30912143054aa6d120f029d268a5154bf2ecd0f707fChris Lattnerstatic unsigned ComputeCommonTailLength(MachineBasicBlock *MBB1, 31012143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner MachineBasicBlock *MBB2, 31112143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner MachineBasicBlock::iterator &I1, 31212143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner MachineBasicBlock::iterator &I2) { 31312143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner I1 = MBB1->end(); 31412143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner I2 = MBB2->end(); 3154e3f125e184f96ae72f2c44d16cafe0d44158283Dan Gohman 31612143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner unsigned TailLen = 0; 31712143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner while (I1 != MBB1->begin() && I2 != MBB2->begin()) { 31812143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner --I1; --I2; 3194e3f125e184f96ae72f2c44d16cafe0d44158283Dan Gohman if (!I1->isIdenticalTo(I2) || 320da6efc5268958a0668806e989c1c5a1f788543e5Bill Wendling // FIXME: This check is dubious. It's used to get around a problem where 3210713a224234b4596709c7582ebf17a1ccb95c872Bill Wendling // people incorrectly expect inline asm directives to remain in the same 3220713a224234b4596709c7582ebf17a1ccb95c872Bill Wendling // relative order. This is untenable because normal compiler 3230713a224234b4596709c7582ebf17a1ccb95c872Bill Wendling // optimizations (like this one) may reorder and/or merge these 3240713a224234b4596709c7582ebf17a1ccb95c872Bill Wendling // directives. 32580629c85f1041df41b5158ebb03a4725af6ecd90Bill Wendling I1->getOpcode() == TargetInstrInfo::INLINEASM) { 32612143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner ++I1; ++I2; 32712143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner break; 32812143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner } 32912143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner ++TailLen; 33012143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner } 33112143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner return TailLen; 33212143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner} 33312143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner 33412143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner/// ReplaceTailWithBranchTo - Delete the instruction OldInst and everything 335386e29065db5b05b57440f6b2a6dfa1e7f29a00dChris Lattner/// after it, replacing it with an unconditional branch to NewDest. This 336386e29065db5b05b57440f6b2a6dfa1e7f29a00dChris Lattner/// returns true if OldInst's block is modified, false if NewDest is modified. 33712143054aa6d120f029d268a5154bf2ecd0f707fChris Lattnervoid BranchFolder::ReplaceTailWithBranchTo(MachineBasicBlock::iterator OldInst, 33812143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner MachineBasicBlock *NewDest) { 33912143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner MachineBasicBlock *OldBB = OldInst->getParent(); 3404e3f125e184f96ae72f2c44d16cafe0d44158283Dan Gohman 34112143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner // Remove all the old successors of OldBB from the CFG. 34212143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner while (!OldBB->succ_empty()) 34312143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner OldBB->removeSuccessor(OldBB->succ_begin()); 3444e3f125e184f96ae72f2c44d16cafe0d44158283Dan Gohman 34512143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner // Remove all the dead instructions from the end of OldBB. 34612143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner OldBB->erase(OldInst, OldBB->end()); 34712143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner 348386e29065db5b05b57440f6b2a6dfa1e7f29a00dChris Lattner // If OldBB isn't immediately before OldBB, insert a branch to it. 349386e29065db5b05b57440f6b2a6dfa1e7f29a00dChris Lattner if (++MachineFunction::iterator(OldBB) != MachineFunction::iterator(NewDest)) 3501501cdbf63cff3afd92df6cd249096770334b268Dan Gohman TII->InsertBranch(*OldBB, NewDest, 0, SmallVector<MachineOperand, 0>()); 35112143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner OldBB->addSuccessor(NewDest); 35212143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner ++NumTailMerge; 35312143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner} 35412143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner 3551d08d83230338ca5969ff6ae6737a978336538bfChris Lattner/// SplitMBBAt - Given a machine basic block and an iterator into it, split the 3561d08d83230338ca5969ff6ae6737a978336538bfChris Lattner/// MBB so that the part before the iterator falls into the part starting at the 3571d08d83230338ca5969ff6ae6737a978336538bfChris Lattner/// iterator. This returns the new MBB. 3581d08d83230338ca5969ff6ae6737a978336538bfChris LattnerMachineBasicBlock *BranchFolder::SplitMBBAt(MachineBasicBlock &CurMBB, 3591d08d83230338ca5969ff6ae6737a978336538bfChris Lattner MachineBasicBlock::iterator BBI1) { 3608e5f2c6f65841542e2a7092553fe42a00048e4c7Dan Gohman MachineFunction &MF = *CurMBB.getParent(); 3618e5f2c6f65841542e2a7092553fe42a00048e4c7Dan Gohman 3621d08d83230338ca5969ff6ae6737a978336538bfChris Lattner // Create the fall-through block. 3631d08d83230338ca5969ff6ae6737a978336538bfChris Lattner MachineFunction::iterator MBBI = &CurMBB; 3648e5f2c6f65841542e2a7092553fe42a00048e4c7Dan Gohman MachineBasicBlock *NewMBB =MF.CreateMachineBasicBlock(CurMBB.getBasicBlock()); 3658e5f2c6f65841542e2a7092553fe42a00048e4c7Dan Gohman CurMBB.getParent()->insert(++MBBI, NewMBB); 3661d08d83230338ca5969ff6ae6737a978336538bfChris Lattner 3671d08d83230338ca5969ff6ae6737a978336538bfChris Lattner // Move all the successors of this block to the specified block. 36804478e56f736325d3567e7c0efe2bb5c2766c63bDan Gohman NewMBB->transferSuccessors(&CurMBB); 3694e3f125e184f96ae72f2c44d16cafe0d44158283Dan Gohman 3701d08d83230338ca5969ff6ae6737a978336538bfChris Lattner // Add an edge from CurMBB to NewMBB for the fall-through. 3711d08d83230338ca5969ff6ae6737a978336538bfChris Lattner CurMBB.addSuccessor(NewMBB); 3724e3f125e184f96ae72f2c44d16cafe0d44158283Dan Gohman 3731d08d83230338ca5969ff6ae6737a978336538bfChris Lattner // Splice the code over. 3741d08d83230338ca5969ff6ae6737a978336538bfChris Lattner NewMBB->splice(NewMBB->end(), &CurMBB, BBI1, CurMBB.end()); 37569cb9b78f11d505f4351a269fc90e7b77fcda437Dale Johannesen 37669cb9b78f11d505f4351a269fc90e7b77fcda437Dale Johannesen // For targets that use the register scavenger, we must maintain LiveIns. 37769cb9b78f11d505f4351a269fc90e7b77fcda437Dale Johannesen if (RS) { 37869cb9b78f11d505f4351a269fc90e7b77fcda437Dale Johannesen RS->enterBasicBlock(&CurMBB); 37969cb9b78f11d505f4351a269fc90e7b77fcda437Dale Johannesen if (!CurMBB.empty()) 38069cb9b78f11d505f4351a269fc90e7b77fcda437Dale Johannesen RS->forward(prior(CurMBB.end())); 381030a0a0cdb38924e55773a8e0b5fe7347aa664aaEvan Cheng BitVector RegsLiveAtExit(TRI->getNumRegs()); 38269cb9b78f11d505f4351a269fc90e7b77fcda437Dale Johannesen RS->getRegsUsed(RegsLiveAtExit, false); 383030a0a0cdb38924e55773a8e0b5fe7347aa664aaEvan Cheng for (unsigned int i=0, e=TRI->getNumRegs(); i!=e; i++) 38469cb9b78f11d505f4351a269fc90e7b77fcda437Dale Johannesen if (RegsLiveAtExit[i]) 38569cb9b78f11d505f4351a269fc90e7b77fcda437Dale Johannesen NewMBB->addLiveIn(i); 38669cb9b78f11d505f4351a269fc90e7b77fcda437Dale Johannesen } 38769cb9b78f11d505f4351a269fc90e7b77fcda437Dale Johannesen 3881d08d83230338ca5969ff6ae6737a978336538bfChris Lattner return NewMBB; 3891d08d83230338ca5969ff6ae6737a978336538bfChris Lattner} 3901d08d83230338ca5969ff6ae6737a978336538bfChris Lattner 391d4bf3c2fd60975b30cd067b59f743a3ea45e45b5Chris Lattner/// EstimateRuntime - Make a rough estimate for how long it will take to run 392d4bf3c2fd60975b30cd067b59f743a3ea45e45b5Chris Lattner/// the specified code. 393d4bf3c2fd60975b30cd067b59f743a3ea45e45b5Chris Lattnerstatic unsigned EstimateRuntime(MachineBasicBlock::iterator I, 39469244300b8a0112efb44b6273ecea4ca6264b8cfChris Lattner MachineBasicBlock::iterator E) { 395d4bf3c2fd60975b30cd067b59f743a3ea45e45b5Chris Lattner unsigned Time = 0; 396d4bf3c2fd60975b30cd067b59f743a3ea45e45b5Chris Lattner for (; I != E; ++I) { 397749c6f6b5ed301c84aac562e414486549d7b98ebChris Lattner const TargetInstrDesc &TID = I->getDesc(); 398749c6f6b5ed301c84aac562e414486549d7b98ebChris Lattner if (TID.isCall()) 399d4bf3c2fd60975b30cd067b59f743a3ea45e45b5Chris Lattner Time += 10; 40041474baac839da410302950305722cb0e026a094Dan Gohman else if (TID.mayLoad() || TID.mayStore()) 401d4bf3c2fd60975b30cd067b59f743a3ea45e45b5Chris Lattner Time += 2; 402d4bf3c2fd60975b30cd067b59f743a3ea45e45b5Chris Lattner else 403d4bf3c2fd60975b30cd067b59f743a3ea45e45b5Chris Lattner ++Time; 404d4bf3c2fd60975b30cd067b59f743a3ea45e45b5Chris Lattner } 405d4bf3c2fd60975b30cd067b59f743a3ea45e45b5Chris Lattner return Time; 406d4bf3c2fd60975b30cd067b59f743a3ea45e45b5Chris Lattner} 407d4bf3c2fd60975b30cd067b59f743a3ea45e45b5Chris Lattner 40876b38fcabeba725e166a2ff72c56fe31d784b229Dale Johannesen// CurMBB needs to add an unconditional branch to SuccMBB (we removed these 40976b38fcabeba725e166a2ff72c56fe31d784b229Dale Johannesen// branches temporarily for tail merging). In the case where CurMBB ends 41076b38fcabeba725e166a2ff72c56fe31d784b229Dale Johannesen// with a conditional branch to the next block, optimize by reversing the 41176b38fcabeba725e166a2ff72c56fe31d784b229Dale Johannesen// test and conditionally branching to SuccMBB instead. 41276b38fcabeba725e166a2ff72c56fe31d784b229Dale Johannesenstatic void FixTail(MachineBasicBlock* CurMBB, MachineBasicBlock *SuccBB, 41376b38fcabeba725e166a2ff72c56fe31d784b229Dale Johannesen const TargetInstrInfo *TII) { 41476b38fcabeba725e166a2ff72c56fe31d784b229Dale Johannesen MachineFunction *MF = CurMBB->getParent(); 41576b38fcabeba725e166a2ff72c56fe31d784b229Dale Johannesen MachineFunction::iterator I = next(MachineFunction::iterator(CurMBB)); 41676b38fcabeba725e166a2ff72c56fe31d784b229Dale Johannesen MachineBasicBlock *TBB = 0, *FBB = 0; 41744eb65cf58e3ab9b5621ce72256d1621a18aeed7Owen Anderson SmallVector<MachineOperand, 4> Cond; 41876b38fcabeba725e166a2ff72c56fe31d784b229Dale Johannesen if (I != MF->end() && 419dc54d317e7a381ef8e4aca80d54ad1466bb85ddaEvan Cheng !TII->AnalyzeBranch(*CurMBB, TBB, FBB, Cond, true)) { 42076b38fcabeba725e166a2ff72c56fe31d784b229Dale Johannesen MachineBasicBlock *NextBB = I; 4216b8583cbf1f8a3df5ae859d3da2ca690ff57f91cDale Johannesen if (TBB == NextBB && !Cond.empty() && !FBB) { 42276b38fcabeba725e166a2ff72c56fe31d784b229Dale Johannesen if (!TII->ReverseBranchCondition(Cond)) { 42376b38fcabeba725e166a2ff72c56fe31d784b229Dale Johannesen TII->RemoveBranch(*CurMBB); 42476b38fcabeba725e166a2ff72c56fe31d784b229Dale Johannesen TII->InsertBranch(*CurMBB, SuccBB, NULL, Cond); 42576b38fcabeba725e166a2ff72c56fe31d784b229Dale Johannesen return; 42676b38fcabeba725e166a2ff72c56fe31d784b229Dale Johannesen } 42776b38fcabeba725e166a2ff72c56fe31d784b229Dale Johannesen } 42876b38fcabeba725e166a2ff72c56fe31d784b229Dale Johannesen } 4291501cdbf63cff3afd92df6cd249096770334b268Dan Gohman TII->InsertBranch(*CurMBB, SuccBB, NULL, SmallVector<MachineOperand, 0>()); 43076b38fcabeba725e166a2ff72c56fe31d784b229Dale Johannesen} 43176b38fcabeba725e166a2ff72c56fe31d784b229Dale Johannesen 43244008c59188ba61aeacfd8be049e3be548ffcea4Dale Johannesenstatic bool MergeCompare(const std::pair<unsigned,MachineBasicBlock*> &p, 43344008c59188ba61aeacfd8be049e3be548ffcea4Dale Johannesen const std::pair<unsigned,MachineBasicBlock*> &q) { 43495ef406e0f2da0197f8b46849319c07e9bea1e55Dale Johannesen if (p.first < q.first) 43595ef406e0f2da0197f8b46849319c07e9bea1e55Dale Johannesen return true; 43695ef406e0f2da0197f8b46849319c07e9bea1e55Dale Johannesen else if (p.first > q.first) 43795ef406e0f2da0197f8b46849319c07e9bea1e55Dale Johannesen return false; 43895ef406e0f2da0197f8b46849319c07e9bea1e55Dale Johannesen else if (p.second->getNumber() < q.second->getNumber()) 43995ef406e0f2da0197f8b46849319c07e9bea1e55Dale Johannesen return true; 44095ef406e0f2da0197f8b46849319c07e9bea1e55Dale Johannesen else if (p.second->getNumber() > q.second->getNumber()) 44195ef406e0f2da0197f8b46849319c07e9bea1e55Dale Johannesen return false; 44267fcdf7f6579fcc070f019096cedf80d5a834554David Greene else { 44397b4ac8c844e08ce1c4f4a73b85ba56775a2a6c5Duncan Sands // _GLIBCXX_DEBUG checks strict weak ordering, which involves comparing 44497b4ac8c844e08ce1c4f4a73b85ba56775a2a6c5Duncan Sands // an object with itself. 44597b4ac8c844e08ce1c4f4a73b85ba56775a2a6c5Duncan Sands#ifndef _GLIBCXX_DEBUG 446c23197a26f34f559ea9797de51e187087c039c42Torok Edwin llvm_unreachable("Predecessor appears twice"); 44767fcdf7f6579fcc070f019096cedf80d5a834554David Greene#endif 4485d5ee80ea8bf300d1ee8ccbd7174466d98a1e99eDan Gohman return false; 44967fcdf7f6579fcc070f019096cedf80d5a834554David Greene } 45095ef406e0f2da0197f8b46849319c07e9bea1e55Dale Johannesen} 45195ef406e0f2da0197f8b46849319c07e9bea1e55Dale Johannesen 4522210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman/// CountTerminators - Count the number of terminators in the given 4532210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman/// block and set I to the position of the first non-terminator, if there 4542210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman/// is one, or MBB->end() otherwise. 4552210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohmanstatic unsigned CountTerminators(MachineBasicBlock *MBB, 4562210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman MachineBasicBlock::iterator &I) { 4572210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman I = MBB->end(); 4582210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman unsigned NumTerms = 0; 4592210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman for (;;) { 4602210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman if (I == MBB->begin()) { 4612210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman I = MBB->end(); 4622210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman break; 4632210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman } 4642210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman --I; 4652210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman if (!I->getDesc().isTerminator()) break; 4662210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman ++NumTerms; 4672210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman } 4682210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman return NumTerms; 4692210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman} 4702210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman 4717b888b8ad07cccec099634bc838eed5da3f336b1Bob Wilson/// ProfitableToMerge - Check if two machine basic blocks have a common tail 4727b888b8ad07cccec099634bc838eed5da3f336b1Bob Wilson/// and decide if it would be profitable to merge those tails. Return the 4737b888b8ad07cccec099634bc838eed5da3f336b1Bob Wilson/// length of the common tail and iterators to the first common instruction 4747b888b8ad07cccec099634bc838eed5da3f336b1Bob Wilson/// in each block. 4757b888b8ad07cccec099634bc838eed5da3f336b1Bob Wilsonstatic bool ProfitableToMerge(MachineBasicBlock *MBB1, 4767b888b8ad07cccec099634bc838eed5da3f336b1Bob Wilson MachineBasicBlock *MBB2, 4777b888b8ad07cccec099634bc838eed5da3f336b1Bob Wilson unsigned minCommonTailLength, 4787b888b8ad07cccec099634bc838eed5da3f336b1Bob Wilson unsigned &CommonTailLen, 4797b888b8ad07cccec099634bc838eed5da3f336b1Bob Wilson MachineBasicBlock::iterator &I1, 4802210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman MachineBasicBlock::iterator &I2, 4812210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman MachineBasicBlock *SuccBB, 4822210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman MachineBasicBlock *PredBB) { 4837b888b8ad07cccec099634bc838eed5da3f336b1Bob Wilson CommonTailLen = ComputeCommonTailLength(MBB1, MBB2, I1, I2); 4847b888b8ad07cccec099634bc838eed5da3f336b1Bob Wilson MachineFunction *MF = MBB1->getParent(); 4857b888b8ad07cccec099634bc838eed5da3f336b1Bob Wilson 4867b888b8ad07cccec099634bc838eed5da3f336b1Bob Wilson if (CommonTailLen == 0) 4877b888b8ad07cccec099634bc838eed5da3f336b1Bob Wilson return false; 4887b888b8ad07cccec099634bc838eed5da3f336b1Bob Wilson 4892210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman // It's almost always profitable to merge any number of non-terminator 4902210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman // instructions with the block that falls through into the common successor. 4912210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman if (MBB1 == PredBB || MBB2 == PredBB) { 4922210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman MachineBasicBlock::iterator I; 4932210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman unsigned NumTerms = CountTerminators(MBB1 == PredBB ? MBB2 : MBB1, I); 4942210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman if (CommonTailLen > NumTerms) 4952210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman return true; 4962210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman } 4972210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman 4982210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman // If both blocks have an unconditional branch temporarily stripped out, 4992210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman // treat that as an additional common instruction. 5002210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman if (MBB1 != PredBB && MBB2 != PredBB && 5012210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman !MBB1->back().getDesc().isBarrier() && 5022210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman !MBB2->back().getDesc().isBarrier()) 5032210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman --minCommonTailLength; 5042210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman 5052210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman // Check if the common tail is long enough to be worthwhile. 5062210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman if (CommonTailLen >= minCommonTailLength) 5072210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman return true; 5082210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman 5097b888b8ad07cccec099634bc838eed5da3f336b1Bob Wilson // If we are optimizing for code size, 1 instruction in common is enough if 5107b888b8ad07cccec099634bc838eed5da3f336b1Bob Wilson // we don't have to split a block. At worst we will be replacing a 5117b888b8ad07cccec099634bc838eed5da3f336b1Bob Wilson // fallthrough into the common tail with a branch, which at worst breaks 5127b888b8ad07cccec099634bc838eed5da3f336b1Bob Wilson // even with falling through into the duplicated common tail. 5137b888b8ad07cccec099634bc838eed5da3f336b1Bob Wilson if (MF->getFunction()->hasFnAttr(Attribute::OptimizeForSize) && 5147b888b8ad07cccec099634bc838eed5da3f336b1Bob Wilson (I1 == MBB1->begin() || I2 == MBB2->begin())) 5157b888b8ad07cccec099634bc838eed5da3f336b1Bob Wilson return true; 5167b888b8ad07cccec099634bc838eed5da3f336b1Bob Wilson 5177b888b8ad07cccec099634bc838eed5da3f336b1Bob Wilson return false; 5187b888b8ad07cccec099634bc838eed5da3f336b1Bob Wilson} 5197b888b8ad07cccec099634bc838eed5da3f336b1Bob Wilson 5206b8583cbf1f8a3df5ae859d3da2ca690ff57f91cDale Johannesen/// ComputeSameTails - Look through all the blocks in MergePotentials that have 5214e3f125e184f96ae72f2c44d16cafe0d44158283Dan Gohman/// hash CurHash (guaranteed to match the last element). Build the vector 5226b8583cbf1f8a3df5ae859d3da2ca690ff57f91cDale Johannesen/// SameTails of all those that have the (same) largest number of instructions 5236b8583cbf1f8a3df5ae859d3da2ca690ff57f91cDale Johannesen/// in common of any pair of these blocks. SameTails entries contain an 5244e3f125e184f96ae72f2c44d16cafe0d44158283Dan Gohman/// iterator into MergePotentials (from which the MachineBasicBlock can be 5254e3f125e184f96ae72f2c44d16cafe0d44158283Dan Gohman/// found) and a MachineBasicBlock::iterator into that MBB indicating the 5266b8583cbf1f8a3df5ae859d3da2ca690ff57f91cDale Johannesen/// instruction where the matching code sequence begins. 5276b8583cbf1f8a3df5ae859d3da2ca690ff57f91cDale Johannesen/// Order of elements in SameTails is the reverse of the order in which 5286b8583cbf1f8a3df5ae859d3da2ca690ff57f91cDale Johannesen/// those blocks appear in MergePotentials (where they are not necessarily 5296b8583cbf1f8a3df5ae859d3da2ca690ff57f91cDale Johannesen/// consecutive). 5304e3f125e184f96ae72f2c44d16cafe0d44158283Dan Gohmanunsigned BranchFolder::ComputeSameTails(unsigned CurHash, 5312210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman unsigned minCommonTailLength, 5322210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman MachineBasicBlock *SuccBB, 5332210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman MachineBasicBlock *PredBB) { 5346b8583cbf1f8a3df5ae859d3da2ca690ff57f91cDale Johannesen unsigned maxCommonTailLength = 0U; 5356b8583cbf1f8a3df5ae859d3da2ca690ff57f91cDale Johannesen SameTails.clear(); 5366b8583cbf1f8a3df5ae859d3da2ca690ff57f91cDale Johannesen MachineBasicBlock::iterator TrialBBI1, TrialBBI2; 5376b8583cbf1f8a3df5ae859d3da2ca690ff57f91cDale Johannesen MPIterator HighestMPIter = prior(MergePotentials.end()); 5386b8583cbf1f8a3df5ae859d3da2ca690ff57f91cDale Johannesen for (MPIterator CurMPIter = prior(MergePotentials.end()), 5394e3f125e184f96ae72f2c44d16cafe0d44158283Dan Gohman B = MergePotentials.begin(); 5404e3f125e184f96ae72f2c44d16cafe0d44158283Dan Gohman CurMPIter!=B && CurMPIter->first == CurHash; 5416b8583cbf1f8a3df5ae859d3da2ca690ff57f91cDale Johannesen --CurMPIter) { 5424e3f125e184f96ae72f2c44d16cafe0d44158283Dan Gohman for (MPIterator I = prior(CurMPIter); I->first == CurHash ; --I) { 5437b888b8ad07cccec099634bc838eed5da3f336b1Bob Wilson unsigned CommonTailLen; 5447b888b8ad07cccec099634bc838eed5da3f336b1Bob Wilson if (ProfitableToMerge(CurMPIter->second, I->second, minCommonTailLength, 5452210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman CommonTailLen, TrialBBI1, TrialBBI2, 5462210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman SuccBB, PredBB)) { 5476b8583cbf1f8a3df5ae859d3da2ca690ff57f91cDale Johannesen if (CommonTailLen > maxCommonTailLength) { 5486b8583cbf1f8a3df5ae859d3da2ca690ff57f91cDale Johannesen SameTails.clear(); 5496b8583cbf1f8a3df5ae859d3da2ca690ff57f91cDale Johannesen maxCommonTailLength = CommonTailLen; 5506b8583cbf1f8a3df5ae859d3da2ca690ff57f91cDale Johannesen HighestMPIter = CurMPIter; 5516b8583cbf1f8a3df5ae859d3da2ca690ff57f91cDale Johannesen SameTails.push_back(std::make_pair(CurMPIter, TrialBBI1)); 5526b8583cbf1f8a3df5ae859d3da2ca690ff57f91cDale Johannesen } 5536b8583cbf1f8a3df5ae859d3da2ca690ff57f91cDale Johannesen if (HighestMPIter == CurMPIter && 5546b8583cbf1f8a3df5ae859d3da2ca690ff57f91cDale Johannesen CommonTailLen == maxCommonTailLength) 5556b8583cbf1f8a3df5ae859d3da2ca690ff57f91cDale Johannesen SameTails.push_back(std::make_pair(I, TrialBBI2)); 5566b8583cbf1f8a3df5ae859d3da2ca690ff57f91cDale Johannesen } 5574e3f125e184f96ae72f2c44d16cafe0d44158283Dan Gohman if (I == B) 5586b8583cbf1f8a3df5ae859d3da2ca690ff57f91cDale Johannesen break; 5596b8583cbf1f8a3df5ae859d3da2ca690ff57f91cDale Johannesen } 5606b8583cbf1f8a3df5ae859d3da2ca690ff57f91cDale Johannesen } 5616b8583cbf1f8a3df5ae859d3da2ca690ff57f91cDale Johannesen return maxCommonTailLength; 5626b8583cbf1f8a3df5ae859d3da2ca690ff57f91cDale Johannesen} 5636b8583cbf1f8a3df5ae859d3da2ca690ff57f91cDale Johannesen 5646b8583cbf1f8a3df5ae859d3da2ca690ff57f91cDale Johannesen/// RemoveBlocksWithHash - Remove all blocks with hash CurHash from 5656b8583cbf1f8a3df5ae859d3da2ca690ff57f91cDale Johannesen/// MergePotentials, restoring branches at ends of blocks as appropriate. 5664e3f125e184f96ae72f2c44d16cafe0d44158283Dan Gohmanvoid BranchFolder::RemoveBlocksWithHash(unsigned CurHash, 5676b8583cbf1f8a3df5ae859d3da2ca690ff57f91cDale Johannesen MachineBasicBlock* SuccBB, 5686b8583cbf1f8a3df5ae859d3da2ca690ff57f91cDale Johannesen MachineBasicBlock* PredBB) { 569679860e31bd7b8f043ba1ccdc5990cb9bafd9055Dale Johannesen MPIterator CurMPIter, B; 5704e3f125e184f96ae72f2c44d16cafe0d44158283Dan Gohman for (CurMPIter = prior(MergePotentials.end()), B = MergePotentials.begin(); 5714e3f125e184f96ae72f2c44d16cafe0d44158283Dan Gohman CurMPIter->first == CurHash; 5726b8583cbf1f8a3df5ae859d3da2ca690ff57f91cDale Johannesen --CurMPIter) { 5736b8583cbf1f8a3df5ae859d3da2ca690ff57f91cDale Johannesen // Put the unconditional branch back, if we need one. 5746b8583cbf1f8a3df5ae859d3da2ca690ff57f91cDale Johannesen MachineBasicBlock *CurMBB = CurMPIter->second; 5756b8583cbf1f8a3df5ae859d3da2ca690ff57f91cDale Johannesen if (SuccBB && CurMBB != PredBB) 5766b8583cbf1f8a3df5ae859d3da2ca690ff57f91cDale Johannesen FixTail(CurMBB, SuccBB, TII); 5774e3f125e184f96ae72f2c44d16cafe0d44158283Dan Gohman if (CurMPIter == B) 5786b8583cbf1f8a3df5ae859d3da2ca690ff57f91cDale Johannesen break; 5796b8583cbf1f8a3df5ae859d3da2ca690ff57f91cDale Johannesen } 580679860e31bd7b8f043ba1ccdc5990cb9bafd9055Dale Johannesen if (CurMPIter->first!=CurHash) 581679860e31bd7b8f043ba1ccdc5990cb9bafd9055Dale Johannesen CurMPIter++; 582679860e31bd7b8f043ba1ccdc5990cb9bafd9055Dale Johannesen MergePotentials.erase(CurMPIter, MergePotentials.end()); 5836b8583cbf1f8a3df5ae859d3da2ca690ff57f91cDale Johannesen} 5846b8583cbf1f8a3df5ae859d3da2ca690ff57f91cDale Johannesen 58551b2b9e29e4fa828ffd83d36f548bc44a4007822Dale Johannesen/// CreateCommonTailOnlyBlock - None of the blocks to be tail-merged consist 58651b2b9e29e4fa828ffd83d36f548bc44a4007822Dale Johannesen/// only of the common tail. Create a block that does by splitting one. 58751b2b9e29e4fa828ffd83d36f548bc44a4007822Dale Johannesenunsigned BranchFolder::CreateCommonTailOnlyBlock(MachineBasicBlock *&PredBB, 58851b2b9e29e4fa828ffd83d36f548bc44a4007822Dale Johannesen unsigned maxCommonTailLength) { 58951b2b9e29e4fa828ffd83d36f548bc44a4007822Dale Johannesen unsigned i, commonTailIndex; 59051b2b9e29e4fa828ffd83d36f548bc44a4007822Dale Johannesen unsigned TimeEstimate = ~0U; 59151b2b9e29e4fa828ffd83d36f548bc44a4007822Dale Johannesen for (i=0, commonTailIndex=0; i<SameTails.size(); i++) { 59251b2b9e29e4fa828ffd83d36f548bc44a4007822Dale Johannesen // Use PredBB if possible; that doesn't require a new branch. 5934e3f125e184f96ae72f2c44d16cafe0d44158283Dan Gohman if (SameTails[i].first->second == PredBB) { 59451b2b9e29e4fa828ffd83d36f548bc44a4007822Dale Johannesen commonTailIndex = i; 59551b2b9e29e4fa828ffd83d36f548bc44a4007822Dale Johannesen break; 59651b2b9e29e4fa828ffd83d36f548bc44a4007822Dale Johannesen } 59751b2b9e29e4fa828ffd83d36f548bc44a4007822Dale Johannesen // Otherwise, make a (fairly bogus) choice based on estimate of 59851b2b9e29e4fa828ffd83d36f548bc44a4007822Dale Johannesen // how long it will take the various blocks to execute. 5994e3f125e184f96ae72f2c44d16cafe0d44158283Dan Gohman unsigned t = EstimateRuntime(SameTails[i].first->second->begin(), 60051b2b9e29e4fa828ffd83d36f548bc44a4007822Dale Johannesen SameTails[i].second); 6014e3f125e184f96ae72f2c44d16cafe0d44158283Dan Gohman if (t <= TimeEstimate) { 60251b2b9e29e4fa828ffd83d36f548bc44a4007822Dale Johannesen TimeEstimate = t; 60351b2b9e29e4fa828ffd83d36f548bc44a4007822Dale Johannesen commonTailIndex = i; 60451b2b9e29e4fa828ffd83d36f548bc44a4007822Dale Johannesen } 60551b2b9e29e4fa828ffd83d36f548bc44a4007822Dale Johannesen } 60651b2b9e29e4fa828ffd83d36f548bc44a4007822Dale Johannesen 60751b2b9e29e4fa828ffd83d36f548bc44a4007822Dale Johannesen MachineBasicBlock::iterator BBI = SameTails[commonTailIndex].second; 60851b2b9e29e4fa828ffd83d36f548bc44a4007822Dale Johannesen MachineBasicBlock *MBB = SameTails[commonTailIndex].first->second; 60951b2b9e29e4fa828ffd83d36f548bc44a4007822Dale Johannesen 610a127edceae2a0097133e9f032e759f9d15f92b7eDan Gohman DEBUG(errs() << "\nSplitting BB#" << MBB->getNumber() << ", size " 6113403bcd8f943cb053a7d9bbf8eb8135407699afaBill Wendling << maxCommonTailLength); 61251b2b9e29e4fa828ffd83d36f548bc44a4007822Dale Johannesen 61351b2b9e29e4fa828ffd83d36f548bc44a4007822Dale Johannesen MachineBasicBlock *newMBB = SplitMBBAt(*MBB, BBI); 61451b2b9e29e4fa828ffd83d36f548bc44a4007822Dale Johannesen SameTails[commonTailIndex].first->second = newMBB; 61551b2b9e29e4fa828ffd83d36f548bc44a4007822Dale Johannesen SameTails[commonTailIndex].second = newMBB->begin(); 6164e3f125e184f96ae72f2c44d16cafe0d44158283Dan Gohman 61751b2b9e29e4fa828ffd83d36f548bc44a4007822Dale Johannesen // If we split PredBB, newMBB is the new predecessor. 6184e3f125e184f96ae72f2c44d16cafe0d44158283Dan Gohman if (PredBB == MBB) 61951b2b9e29e4fa828ffd83d36f548bc44a4007822Dale Johannesen PredBB = newMBB; 62051b2b9e29e4fa828ffd83d36f548bc44a4007822Dale Johannesen 62151b2b9e29e4fa828ffd83d36f548bc44a4007822Dale Johannesen return commonTailIndex; 62251b2b9e29e4fa828ffd83d36f548bc44a4007822Dale Johannesen} 62351b2b9e29e4fa828ffd83d36f548bc44a4007822Dale Johannesen 6247d33b4c59b56afb96feea71073c1d9e70c457e28Dale Johannesen// See if any of the blocks in MergePotentials (which all have a common single 6257d33b4c59b56afb96feea71073c1d9e70c457e28Dale Johannesen// successor, or all have no successor) can be tail-merged. If there is a 6267d33b4c59b56afb96feea71073c1d9e70c457e28Dale Johannesen// successor, any blocks in MergePotentials that are not tail-merged and 6277d33b4c59b56afb96feea71073c1d9e70c457e28Dale Johannesen// are not immediately before Succ must have an unconditional branch to 6284e3f125e184f96ae72f2c44d16cafe0d44158283Dan Gohman// Succ added (but the predecessor/successor lists need no adjustment). 6297d33b4c59b56afb96feea71073c1d9e70c457e28Dale Johannesen// The lone predecessor of Succ that falls through into Succ, 6307d33b4c59b56afb96feea71073c1d9e70c457e28Dale Johannesen// if any, is given in PredBB. 6317d33b4c59b56afb96feea71073c1d9e70c457e28Dale Johannesen 6322210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohmanbool BranchFolder::TryTailMergeBlocks(MachineBasicBlock *SuccBB, 6332210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman MachineBasicBlock* PredBB) { 634030a0a0cdb38924e55773a8e0b5fe7347aa664aaEvan Cheng bool MadeChange = false; 635030a0a0cdb38924e55773a8e0b5fe7347aa664aaEvan Cheng 6362210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman // Except for the special cases below, tail-merge if there are at least 6372210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman // this many instructions in common. 6382210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman unsigned minCommonTailLength = TailMergeSize; 6392210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman 6402210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman // If there's a successor block, there are some cases which don't require 6412210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman // new branching and as such are very likely to be profitable. 6422210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman if (SuccBB) { 6432210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman if (SuccBB->pred_size() == MergePotentials.size() && 6442210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman !MergePotentials[0].second->empty()) { 6452210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman // If all the predecessors have at least one tail instruction in common, 6462210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman // merging is very likely to be a win since it won't require an increase 6472210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman // in static branches, and it will decrease the static instruction count. 6482210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman bool AllPredsMatch = true; 6492210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman MachineBasicBlock::iterator FirstNonTerm; 6502210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman unsigned MinNumTerms = CountTerminators(MergePotentials[0].second, 6512210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman FirstNonTerm); 6522210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman if (FirstNonTerm != MergePotentials[0].second->end()) { 6532210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman for (unsigned i = 1, e = MergePotentials.size(); i != e; ++i) { 6542210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman MachineBasicBlock::iterator OtherFirstNonTerm; 6552210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman unsigned NumTerms = CountTerminators(MergePotentials[0].second, 6562210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman OtherFirstNonTerm); 6572210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman if (NumTerms < MinNumTerms) 6582210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman MinNumTerms = NumTerms; 6592210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman if (OtherFirstNonTerm == MergePotentials[i].second->end() || 6602210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman OtherFirstNonTerm->isIdenticalTo(FirstNonTerm)) { 6612210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman AllPredsMatch = false; 6622210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman break; 6632210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman } 6642210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman } 6652210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman 6662210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman // If they all have an instruction in common, do any amount of merging. 6672210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman if (AllPredsMatch) 6682210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman minCommonTailLength = MinNumTerms + 1; 6692210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman } 6702210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman } 6712210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman } 6724e3f125e184f96ae72f2c44d16cafe0d44158283Dan Gohman 6732210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman DEBUG(errs() << "\nTryTailMergeBlocks: "; 6742210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman for (unsigned i = 0, e = MergePotentials.size(); i != e; ++i) 6752210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman errs() << "BB#" << MergePotentials[i].second->getNumber() 6762210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman << (i == e-1 ? "" : ", "); 6772210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman errs() << "\n"; 6782210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman if (SuccBB) { 6792210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman errs() << " with successor BB#" << SuccBB->getNumber() << '\n'; 6802210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman if (PredBB) 6812210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman errs() << " which has fall-through from BB#" 6822210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman << PredBB->getNumber() << "\n"; 6832210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman } 6842210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman errs() << "Looking for common tails of at least " 6852210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman << minCommonTailLength << " instruction" 6862210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman << (minCommonTailLength == 1 ? "" : "s") << '\n'; 6872210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman ); 6886b8583cbf1f8a3df5ae859d3da2ca690ff57f91cDale Johannesen 68912143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner // Sort by hash value so that blocks with identical end sequences sort 69012143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner // together. 6916b8583cbf1f8a3df5ae859d3da2ca690ff57f91cDale Johannesen std::stable_sort(MergePotentials.begin(), MergePotentials.end(),MergeCompare); 69212143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner 69312143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner // Walk through equivalence sets looking for actual exact matches. 69412143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner while (MergePotentials.size() > 1) { 695b2e40990c40999804f0f28650685c4af18e4c261Dan Gohman unsigned CurHash = MergePotentials.back().first; 6964e3f125e184f96ae72f2c44d16cafe0d44158283Dan Gohman 6976b8583cbf1f8a3df5ae859d3da2ca690ff57f91cDale Johannesen // Build SameTails, identifying the set of blocks with this hash code 6986b8583cbf1f8a3df5ae859d3da2ca690ff57f91cDale Johannesen // and with the maximum number of instructions in common. 6994e3f125e184f96ae72f2c44d16cafe0d44158283Dan Gohman unsigned maxCommonTailLength = ComputeSameTails(CurHash, 7002210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman minCommonTailLength, 7012210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman SuccBB, PredBB); 7027aea8320340ce867eb4328aeec52cb02c88ef0b3Dale Johannesen 7034e3f125e184f96ae72f2c44d16cafe0d44158283Dan Gohman // If we didn't find any pair that has at least minCommonTailLength 7046ae83faadf715c398e637424a764f6b02f0b6df2Dale Johannesen // instructions in common, remove all blocks with this hash code and retry. 7056ae83faadf715c398e637424a764f6b02f0b6df2Dale Johannesen if (SameTails.empty()) { 7066b8583cbf1f8a3df5ae859d3da2ca690ff57f91cDale Johannesen RemoveBlocksWithHash(CurHash, SuccBB, PredBB); 7077aea8320340ce867eb4328aeec52cb02c88ef0b3Dale Johannesen continue; 7087aea8320340ce867eb4328aeec52cb02c88ef0b3Dale Johannesen } 7091d08d83230338ca5969ff6ae6737a978336538bfChris Lattner 7106ae83faadf715c398e637424a764f6b02f0b6df2Dale Johannesen // If one of the blocks is the entire common tail (and not the entry 71151b2b9e29e4fa828ffd83d36f548bc44a4007822Dale Johannesen // block, which we can't jump to), we can treat all blocks with this same 71251b2b9e29e4fa828ffd83d36f548bc44a4007822Dale Johannesen // tail at once. Use PredBB if that is one of the possibilities, as that 71351b2b9e29e4fa828ffd83d36f548bc44a4007822Dale Johannesen // will not introduce any extra branches. 71451b2b9e29e4fa828ffd83d36f548bc44a4007822Dale Johannesen MachineBasicBlock *EntryBB = MergePotentials.begin()->second-> 71551b2b9e29e4fa828ffd83d36f548bc44a4007822Dale Johannesen getParent()->begin(); 71651b2b9e29e4fa828ffd83d36f548bc44a4007822Dale Johannesen unsigned int commonTailIndex, i; 71751b2b9e29e4fa828ffd83d36f548bc44a4007822Dale Johannesen for (commonTailIndex=SameTails.size(), i=0; i<SameTails.size(); i++) { 7186ae83faadf715c398e637424a764f6b02f0b6df2Dale Johannesen MachineBasicBlock *MBB = SameTails[i].first->second; 7192210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman if (MBB == EntryBB) 7202210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman continue; 7212210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman if (MBB == PredBB) { 72251b2b9e29e4fa828ffd83d36f548bc44a4007822Dale Johannesen commonTailIndex = i; 7232210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman break; 7246ae83faadf715c398e637424a764f6b02f0b6df2Dale Johannesen } 7252210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman if (MBB->begin() == SameTails[i].second) 7262210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman commonTailIndex = i; 7276ae83faadf715c398e637424a764f6b02f0b6df2Dale Johannesen } 7286ae83faadf715c398e637424a764f6b02f0b6df2Dale Johannesen 7292210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman if (commonTailIndex == SameTails.size() || 7302210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman (SameTails[commonTailIndex].first->second == PredBB && 7312210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman SameTails[commonTailIndex].first->second->begin() != 7322210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman SameTails[i].second)) { 73351b2b9e29e4fa828ffd83d36f548bc44a4007822Dale Johannesen // None of the blocks consist entirely of the common tail. 73451b2b9e29e4fa828ffd83d36f548bc44a4007822Dale Johannesen // Split a block so that one does. 7352210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman commonTailIndex = CreateCommonTailOnlyBlock(PredBB, maxCommonTailLength); 7361d08d83230338ca5969ff6ae6737a978336538bfChris Lattner } 73751b2b9e29e4fa828ffd83d36f548bc44a4007822Dale Johannesen 73851b2b9e29e4fa828ffd83d36f548bc44a4007822Dale Johannesen MachineBasicBlock *MBB = SameTails[commonTailIndex].first->second; 73951b2b9e29e4fa828ffd83d36f548bc44a4007822Dale Johannesen // MBB is common tail. Adjust all other BB's to jump to this one. 74051b2b9e29e4fa828ffd83d36f548bc44a4007822Dale Johannesen // Traversal must be forwards so erases work. 7412210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman DEBUG(errs() << "\nUsing common tail in BB#" << MBB->getNumber() 7422210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman << " for "); 7432210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman for (unsigned int i=0, e = SameTails.size(); i != e; ++i) { 7444e3f125e184f96ae72f2c44d16cafe0d44158283Dan Gohman if (commonTailIndex == i) 74551b2b9e29e4fa828ffd83d36f548bc44a4007822Dale Johannesen continue; 7462210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman DEBUG(errs() << "BB#" << SameTails[i].first->second->getNumber() 7472210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman << (i == e-1 ? "" : ", ")); 74851b2b9e29e4fa828ffd83d36f548bc44a4007822Dale Johannesen // Hack the end off BB i, making it jump to BB commonTailIndex instead. 74951b2b9e29e4fa828ffd83d36f548bc44a4007822Dale Johannesen ReplaceTailWithBranchTo(SameTails[i].second, MBB); 75051b2b9e29e4fa828ffd83d36f548bc44a4007822Dale Johannesen // BB i is no longer a predecessor of SuccBB; remove it from the worklist. 75151b2b9e29e4fa828ffd83d36f548bc44a4007822Dale Johannesen MergePotentials.erase(SameTails[i].first); 75212143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner } 7533403bcd8f943cb053a7d9bbf8eb8135407699afaBill Wendling DEBUG(errs() << "\n"); 75451b2b9e29e4fa828ffd83d36f548bc44a4007822Dale Johannesen // We leave commonTailIndex in the worklist in case there are other blocks 75551b2b9e29e4fa828ffd83d36f548bc44a4007822Dale Johannesen // that match it with a smaller number of instructions. 7561d08d83230338ca5969ff6ae6737a978336538bfChris Lattner MadeChange = true; 75721ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner } 75812143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner return MadeChange; 75912143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner} 76021ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner 7617d33b4c59b56afb96feea71073c1d9e70c457e28Dale Johannesenbool BranchFolder::TailMergeBlocks(MachineFunction &MF) { 76276b38fcabeba725e166a2ff72c56fe31d784b229Dale Johannesen 7637d33b4c59b56afb96feea71073c1d9e70c457e28Dale Johannesen if (!EnableTailMerge) return false; 7644e3f125e184f96ae72f2c44d16cafe0d44158283Dan Gohman 765030a0a0cdb38924e55773a8e0b5fe7347aa664aaEvan Cheng bool MadeChange = false; 76676b38fcabeba725e166a2ff72c56fe31d784b229Dale Johannesen 7677d33b4c59b56afb96feea71073c1d9e70c457e28Dale Johannesen // First find blocks with no successors. 76876b38fcabeba725e166a2ff72c56fe31d784b229Dale Johannesen MergePotentials.clear(); 7697d33b4c59b56afb96feea71073c1d9e70c457e28Dale Johannesen for (MachineFunction::iterator I = MF.begin(), E = MF.end(); I != E; ++I) { 7707d33b4c59b56afb96feea71073c1d9e70c457e28Dale Johannesen if (I->succ_empty()) 7717aea8320340ce867eb4328aeec52cb02c88ef0b3Dale Johannesen MergePotentials.push_back(std::make_pair(HashEndOfMBB(I, 2U), I)); 7727d33b4c59b56afb96feea71073c1d9e70c457e28Dale Johannesen } 7734e3f125e184f96ae72f2c44d16cafe0d44158283Dan Gohman 77476b38fcabeba725e166a2ff72c56fe31d784b229Dale Johannesen // See if we can do any tail merging on those. 7756ae83faadf715c398e637424a764f6b02f0b6df2Dale Johannesen if (MergePotentials.size() < TailMergeThreshold && 7766ae83faadf715c398e637424a764f6b02f0b6df2Dale Johannesen MergePotentials.size() >= 2) 7772210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman MadeChange |= TryTailMergeBlocks(NULL, NULL); 7787d33b4c59b56afb96feea71073c1d9e70c457e28Dale Johannesen 77976b38fcabeba725e166a2ff72c56fe31d784b229Dale Johannesen // Look at blocks (IBB) with multiple predecessors (PBB). 78076b38fcabeba725e166a2ff72c56fe31d784b229Dale Johannesen // We change each predecessor to a canonical form, by 78176b38fcabeba725e166a2ff72c56fe31d784b229Dale Johannesen // (1) temporarily removing any unconditional branch from the predecessor 78276b38fcabeba725e166a2ff72c56fe31d784b229Dale Johannesen // to IBB, and 78376b38fcabeba725e166a2ff72c56fe31d784b229Dale Johannesen // (2) alter conditional branches so they branch to the other block 7844e3f125e184f96ae72f2c44d16cafe0d44158283Dan Gohman // not IBB; this may require adding back an unconditional branch to IBB 78576b38fcabeba725e166a2ff72c56fe31d784b229Dale Johannesen // later, where there wasn't one coming in. E.g. 78676b38fcabeba725e166a2ff72c56fe31d784b229Dale Johannesen // Bcc IBB 78776b38fcabeba725e166a2ff72c56fe31d784b229Dale Johannesen // fallthrough to QBB 78876b38fcabeba725e166a2ff72c56fe31d784b229Dale Johannesen // here becomes 78976b38fcabeba725e166a2ff72c56fe31d784b229Dale Johannesen // Bncc QBB 79076b38fcabeba725e166a2ff72c56fe31d784b229Dale Johannesen // with a conceptual B to IBB after that, which never actually exists. 79176b38fcabeba725e166a2ff72c56fe31d784b229Dale Johannesen // With those changes, we see whether the predecessors' tails match, 79276b38fcabeba725e166a2ff72c56fe31d784b229Dale Johannesen // and merge them if so. We change things out of canonical form and 79376b38fcabeba725e166a2ff72c56fe31d784b229Dale Johannesen // back to the way they were later in the process. (OptimizeBranches 79476b38fcabeba725e166a2ff72c56fe31d784b229Dale Johannesen // would undo some of this, but we can't use it, because we'd get into 79576b38fcabeba725e166a2ff72c56fe31d784b229Dale Johannesen // a compile-time infinite loop repeatedly doing and undoing the same 79676b38fcabeba725e166a2ff72c56fe31d784b229Dale Johannesen // transformations.) 7977d33b4c59b56afb96feea71073c1d9e70c457e28Dale Johannesen 7982210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman for (MachineFunction::iterator I = next(MF.begin()), E = MF.end(); 7992210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman I != E; ++I) { 80062bc8a44868bd86e96bdbd2f0d66dda690cc66adDale Johannesen if (I->pred_size() >= 2 && I->pred_size() < TailMergeThreshold) { 801da65822cfc938594f8fb7840947c1eb77e057a48Dan Gohman SmallPtrSet<MachineBasicBlock *, 8> UniquePreds; 8027d33b4c59b56afb96feea71073c1d9e70c457e28Dale Johannesen MachineBasicBlock *IBB = I; 8037d33b4c59b56afb96feea71073c1d9e70c457e28Dale Johannesen MachineBasicBlock *PredBB = prior(I); 80476b38fcabeba725e166a2ff72c56fe31d784b229Dale Johannesen MergePotentials.clear(); 8054e3f125e184f96ae72f2c44d16cafe0d44158283Dan Gohman for (MachineBasicBlock::pred_iterator P = I->pred_begin(), 8061a90a5aebe3488dc3feaab60ba16bed1659ba27bDale Johannesen E2 = I->pred_end(); 8077d33b4c59b56afb96feea71073c1d9e70c457e28Dale Johannesen P != E2; ++P) { 8087d33b4c59b56afb96feea71073c1d9e70c457e28Dale Johannesen MachineBasicBlock* PBB = *P; 80976b38fcabeba725e166a2ff72c56fe31d784b229Dale Johannesen // Skip blocks that loop to themselves, can't tail merge these. 8104e3f125e184f96ae72f2c44d16cafe0d44158283Dan Gohman if (PBB == IBB) 81176b38fcabeba725e166a2ff72c56fe31d784b229Dale Johannesen continue; 812da65822cfc938594f8fb7840947c1eb77e057a48Dan Gohman // Visit each predecessor only once. 813da65822cfc938594f8fb7840947c1eb77e057a48Dan Gohman if (!UniquePreds.insert(PBB)) 814da65822cfc938594f8fb7840947c1eb77e057a48Dan Gohman continue; 8157d33b4c59b56afb96feea71073c1d9e70c457e28Dale Johannesen MachineBasicBlock *TBB = 0, *FBB = 0; 81644eb65cf58e3ab9b5621ce72256d1621a18aeed7Owen Anderson SmallVector<MachineOperand, 4> Cond; 817dc54d317e7a381ef8e4aca80d54ad1466bb85ddaEvan Cheng if (!TII->AnalyzeBranch(*PBB, TBB, FBB, Cond, true)) { 81876b38fcabeba725e166a2ff72c56fe31d784b229Dale Johannesen // Failing case: IBB is the target of a cbr, and 81976b38fcabeba725e166a2ff72c56fe31d784b229Dale Johannesen // we cannot reverse the branch. 82044eb65cf58e3ab9b5621ce72256d1621a18aeed7Owen Anderson SmallVector<MachineOperand, 4> NewCond(Cond); 8214e3f125e184f96ae72f2c44d16cafe0d44158283Dan Gohman if (!Cond.empty() && TBB == IBB) { 82276b38fcabeba725e166a2ff72c56fe31d784b229Dale Johannesen if (TII->ReverseBranchCondition(NewCond)) 82376b38fcabeba725e166a2ff72c56fe31d784b229Dale Johannesen continue; 82476b38fcabeba725e166a2ff72c56fe31d784b229Dale Johannesen // This is the QBB case described above 82576b38fcabeba725e166a2ff72c56fe31d784b229Dale Johannesen if (!FBB) 82676b38fcabeba725e166a2ff72c56fe31d784b229Dale Johannesen FBB = next(MachineFunction::iterator(PBB)); 82776b38fcabeba725e166a2ff72c56fe31d784b229Dale Johannesen } 828fe7e397100edd4f2d618a1ff938dfa8624670ec1Dale Johannesen // Failing case: the only way IBB can be reached from PBB is via 829fe7e397100edd4f2d618a1ff938dfa8624670ec1Dale Johannesen // exception handling. Happens for landing pads. Would be nice 830fe7e397100edd4f2d618a1ff938dfa8624670ec1Dale Johannesen // to have a bit in the edge so we didn't have to do all this. 831fe7e397100edd4f2d618a1ff938dfa8624670ec1Dale Johannesen if (IBB->isLandingPad()) { 832fe7e397100edd4f2d618a1ff938dfa8624670ec1Dale Johannesen MachineFunction::iterator IP = PBB; IP++; 833fe7e397100edd4f2d618a1ff938dfa8624670ec1Dale Johannesen MachineBasicBlock* PredNextBB = NULL; 834fe7e397100edd4f2d618a1ff938dfa8624670ec1Dale Johannesen if (IP!=MF.end()) 835fe7e397100edd4f2d618a1ff938dfa8624670ec1Dale Johannesen PredNextBB = IP; 8364e3f125e184f96ae72f2c44d16cafe0d44158283Dan Gohman if (TBB == NULL) { 837fe7e397100edd4f2d618a1ff938dfa8624670ec1Dale Johannesen if (IBB!=PredNextBB) // fallthrough 838fe7e397100edd4f2d618a1ff938dfa8624670ec1Dale Johannesen continue; 839fe7e397100edd4f2d618a1ff938dfa8624670ec1Dale Johannesen } else if (FBB) { 840fe7e397100edd4f2d618a1ff938dfa8624670ec1Dale Johannesen if (TBB!=IBB && FBB!=IBB) // cbr then ubr 841fe7e397100edd4f2d618a1ff938dfa8624670ec1Dale Johannesen continue; 842303595942502f17c087fa28874c2b89117148c45Dan Gohman } else if (Cond.empty()) { 843fe7e397100edd4f2d618a1ff938dfa8624670ec1Dale Johannesen if (TBB!=IBB) // ubr 844fe7e397100edd4f2d618a1ff938dfa8624670ec1Dale Johannesen continue; 845fe7e397100edd4f2d618a1ff938dfa8624670ec1Dale Johannesen } else { 846fe7e397100edd4f2d618a1ff938dfa8624670ec1Dale Johannesen if (TBB!=IBB && IBB!=PredNextBB) // cbr 847fe7e397100edd4f2d618a1ff938dfa8624670ec1Dale Johannesen continue; 848fe7e397100edd4f2d618a1ff938dfa8624670ec1Dale Johannesen } 849fe7e397100edd4f2d618a1ff938dfa8624670ec1Dale Johannesen } 85076b38fcabeba725e166a2ff72c56fe31d784b229Dale Johannesen // Remove the unconditional branch at the end, if any. 8516b8583cbf1f8a3df5ae859d3da2ca690ff57f91cDale Johannesen if (TBB && (Cond.empty() || FBB)) { 8527d33b4c59b56afb96feea71073c1d9e70c457e28Dale Johannesen TII->RemoveBranch(*PBB); 8536b8583cbf1f8a3df5ae859d3da2ca690ff57f91cDale Johannesen if (!Cond.empty()) 8547d33b4c59b56afb96feea71073c1d9e70c457e28Dale Johannesen // reinsert conditional branch only, for now 8554e3f125e184f96ae72f2c44d16cafe0d44158283Dan Gohman TII->InsertBranch(*PBB, (TBB == IBB) ? FBB : TBB, 0, NewCond); 8567d33b4c59b56afb96feea71073c1d9e70c457e28Dale Johannesen } 8577aea8320340ce867eb4328aeec52cb02c88ef0b3Dale Johannesen MergePotentials.push_back(std::make_pair(HashEndOfMBB(PBB, 1U), *P)); 8587d33b4c59b56afb96feea71073c1d9e70c457e28Dale Johannesen } 8597d33b4c59b56afb96feea71073c1d9e70c457e28Dale Johannesen } 860cdc06ba5dfdded6cdc48061d36b63b807962ab31Dan Gohman if (MergePotentials.size() >= 2) 8612210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman MadeChange |= TryTailMergeBlocks(IBB, PredBB); 862cdc06ba5dfdded6cdc48061d36b63b807962ab31Dan Gohman // Reinsert an unconditional branch if needed. 8632210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman // The 1 below can occur as a result of removing blocks in TryTailMergeBlocks. 8642210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman PredBB = prior(I); // this may have been changed in TryTailMergeBlocks 865cdc06ba5dfdded6cdc48061d36b63b807962ab31Dan Gohman if (MergePotentials.size() == 1 && 866cdc06ba5dfdded6cdc48061d36b63b807962ab31Dan Gohman MergePotentials.begin()->second != PredBB) 8672210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman FixTail(MergePotentials.begin()->second, IBB, TII); 8687d33b4c59b56afb96feea71073c1d9e70c457e28Dale Johannesen } 8697d33b4c59b56afb96feea71073c1d9e70c457e28Dale Johannesen } 8707d33b4c59b56afb96feea71073c1d9e70c457e28Dale Johannesen return MadeChange; 8717d33b4c59b56afb96feea71073c1d9e70c457e28Dale Johannesen} 87212143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner 87312143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner//===----------------------------------------------------------------------===// 87412143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner// Branch Optimization 87512143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner//===----------------------------------------------------------------------===// 87612143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner 87712143054aa6d120f029d268a5154bf2ecd0f707fChris Lattnerbool BranchFolder::OptimizeBranches(MachineFunction &MF) { 878030a0a0cdb38924e55773a8e0b5fe7347aa664aaEvan Cheng bool MadeChange = false; 8794e3f125e184f96ae72f2c44d16cafe0d44158283Dan Gohman 8806b896cec8b703e08e5f3d809e086a39b6ebe6589Dale Johannesen // Make sure blocks are numbered in order 8816b896cec8b703e08e5f3d809e086a39b6ebe6589Dale Johannesen MF.RenumberBlocks(); 8826b896cec8b703e08e5f3d809e086a39b6ebe6589Dale Johannesen 88312143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner for (MachineFunction::iterator I = ++MF.begin(), E = MF.end(); I != E; ) { 88412143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner MachineBasicBlock *MBB = I++; 885030a0a0cdb38924e55773a8e0b5fe7347aa664aaEvan Cheng MadeChange |= OptimizeBlock(MBB); 8864e3f125e184f96ae72f2c44d16cafe0d44158283Dan Gohman 88712143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner // If it is dead, remove it. 888033c9715d9bf7ce59ad2e466bf0720811b34da08Jim Laskey if (MBB->pred_empty()) { 88912143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner RemoveDeadBlock(MBB); 89012143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner MadeChange = true; 89112143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner ++NumDeadBlocks; 89212143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner } 89312143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner } 89412143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner return MadeChange; 89521ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner} 89621ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner 89712143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner 8986b0e3f890779b7fc912bec8d40a9590e44742737Chris Lattner/// CanFallThrough - Return true if the specified block (with the specified 8996b0e3f890779b7fc912bec8d40a9590e44742737Chris Lattner/// branch condition) can implicitly transfer control to the block after it by 9006b0e3f890779b7fc912bec8d40a9590e44742737Chris Lattner/// falling off the end of it. This should return false if it can reach the 9016b0e3f890779b7fc912bec8d40a9590e44742737Chris Lattner/// block after it, but it uses an explicit branch to do so (e.g. a table jump). 9026b0e3f890779b7fc912bec8d40a9590e44742737Chris Lattner/// 9036b0e3f890779b7fc912bec8d40a9590e44742737Chris Lattner/// True is a conservative answer. 9046b0e3f890779b7fc912bec8d40a9590e44742737Chris Lattner/// 9056b0e3f890779b7fc912bec8d40a9590e44742737Chris Lattnerbool BranchFolder::CanFallThrough(MachineBasicBlock *CurBB, 9066b0e3f890779b7fc912bec8d40a9590e44742737Chris Lattner bool BranchUnAnalyzable, 9074e3f125e184f96ae72f2c44d16cafe0d44158283Dan Gohman MachineBasicBlock *TBB, 90851b2b9e29e4fa828ffd83d36f548bc44a4007822Dale Johannesen MachineBasicBlock *FBB, 90944eb65cf58e3ab9b5621ce72256d1621a18aeed7Owen Anderson const SmallVectorImpl<MachineOperand> &Cond) { 9106b0e3f890779b7fc912bec8d40a9590e44742737Chris Lattner MachineFunction::iterator Fallthrough = CurBB; 9116b0e3f890779b7fc912bec8d40a9590e44742737Chris Lattner ++Fallthrough; 9126b0e3f890779b7fc912bec8d40a9590e44742737Chris Lattner // If FallthroughBlock is off the end of the function, it can't fall through. 9136b0e3f890779b7fc912bec8d40a9590e44742737Chris Lattner if (Fallthrough == CurBB->getParent()->end()) 9146b0e3f890779b7fc912bec8d40a9590e44742737Chris Lattner return false; 9154e3f125e184f96ae72f2c44d16cafe0d44158283Dan Gohman 9166b0e3f890779b7fc912bec8d40a9590e44742737Chris Lattner // If FallthroughBlock isn't a successor of CurBB, no fallthrough is possible. 9176b0e3f890779b7fc912bec8d40a9590e44742737Chris Lattner if (!CurBB->isSuccessor(Fallthrough)) 9186b0e3f890779b7fc912bec8d40a9590e44742737Chris Lattner return false; 9194e3f125e184f96ae72f2c44d16cafe0d44158283Dan Gohman 9202210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman // If we couldn't analyze the branch, examine the last instruction. 9212210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman // If the block doesn't end in a known control barrier, assume fallthrough 9222210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman // is possible. The isPredicable check is needed because this code can be 9232210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman // called during IfConversion, where an instruction which is normally a 9242210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman // Barrier is predicated and thus no longer an actual control barrier. This 9252210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman // is over-conservative though, because if an instruction isn't actually 9262210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman // predicated we could still treat it like a barrier. 9272210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman if (BranchUnAnalyzable) 9282210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman return CurBB->empty() || !CurBB->back().getDesc().isBarrier() || 9292210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman CurBB->back().getDesc().isPredicable(); 9302210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman 9317d09784d3fc652131a2afbf06a0f2ed893837fb9Chris Lattner // If there is no branch, control always falls through. 9327d09784d3fc652131a2afbf06a0f2ed893837fb9Chris Lattner if (TBB == 0) return true; 9337d09784d3fc652131a2afbf06a0f2ed893837fb9Chris Lattner 9347d09784d3fc652131a2afbf06a0f2ed893837fb9Chris Lattner // If there is some explicit branch to the fallthrough block, it can obviously 9357d09784d3fc652131a2afbf06a0f2ed893837fb9Chris Lattner // reach, even though the branch should get folded to fall through implicitly. 9366b0e3f890779b7fc912bec8d40a9590e44742737Chris Lattner if (MachineFunction::iterator(TBB) == Fallthrough || 9376b0e3f890779b7fc912bec8d40a9590e44742737Chris Lattner MachineFunction::iterator(FBB) == Fallthrough) 9387d09784d3fc652131a2afbf06a0f2ed893837fb9Chris Lattner return true; 9394e3f125e184f96ae72f2c44d16cafe0d44158283Dan Gohman 9404e3f125e184f96ae72f2c44d16cafe0d44158283Dan Gohman // If it's an unconditional branch to some block not the fall through, it 9417d09784d3fc652131a2afbf06a0f2ed893837fb9Chris Lattner // doesn't fall through. 9427d09784d3fc652131a2afbf06a0f2ed893837fb9Chris Lattner if (Cond.empty()) return false; 9434e3f125e184f96ae72f2c44d16cafe0d44158283Dan Gohman 9447d09784d3fc652131a2afbf06a0f2ed893837fb9Chris Lattner // Otherwise, if it is conditional and has no explicit false block, it falls 9457d09784d3fc652131a2afbf06a0f2ed893837fb9Chris Lattner // through. 946c2e91e34dc18d794435db86713c06400ea60e930Chris Lattner return FBB == 0; 9477d09784d3fc652131a2afbf06a0f2ed893837fb9Chris Lattner} 9487d09784d3fc652131a2afbf06a0f2ed893837fb9Chris Lattner 9496b0e3f890779b7fc912bec8d40a9590e44742737Chris Lattner/// CanFallThrough - Return true if the specified can implicitly transfer 9506b0e3f890779b7fc912bec8d40a9590e44742737Chris Lattner/// control to the block after it by falling off the end of it. This should 9516b0e3f890779b7fc912bec8d40a9590e44742737Chris Lattner/// return false if it can reach the block after it, but it uses an explicit 9526b0e3f890779b7fc912bec8d40a9590e44742737Chris Lattner/// branch to do so (e.g. a table jump). 9536b0e3f890779b7fc912bec8d40a9590e44742737Chris Lattner/// 9546b0e3f890779b7fc912bec8d40a9590e44742737Chris Lattner/// True is a conservative answer. 9556b0e3f890779b7fc912bec8d40a9590e44742737Chris Lattner/// 9566b0e3f890779b7fc912bec8d40a9590e44742737Chris Lattnerbool BranchFolder::CanFallThrough(MachineBasicBlock *CurBB) { 9576b0e3f890779b7fc912bec8d40a9590e44742737Chris Lattner MachineBasicBlock *TBB = 0, *FBB = 0; 95844eb65cf58e3ab9b5621ce72256d1621a18aeed7Owen Anderson SmallVector<MachineOperand, 4> Cond; 959dc54d317e7a381ef8e4aca80d54ad1466bb85ddaEvan Cheng bool CurUnAnalyzable = TII->AnalyzeBranch(*CurBB, TBB, FBB, Cond, true); 9606b0e3f890779b7fc912bec8d40a9590e44742737Chris Lattner return CanFallThrough(CurBB, CurUnAnalyzable, TBB, FBB, Cond); 9616b0e3f890779b7fc912bec8d40a9590e44742737Chris Lattner} 9626b0e3f890779b7fc912bec8d40a9590e44742737Chris Lattner 963a7bef4a4e49f461984c04ef6be6eef3f1c023558Chris Lattner/// IsBetterFallthrough - Return true if it would be clearly better to 964a7bef4a4e49f461984c04ef6be6eef3f1c023558Chris Lattner/// fall-through to MBB1 than to fall through into MBB2. This has to return 965a7bef4a4e49f461984c04ef6be6eef3f1c023558Chris Lattner/// a strict ordering, returning true for both (MBB1,MBB2) and (MBB2,MBB1) will 966a7bef4a4e49f461984c04ef6be6eef3f1c023558Chris Lattner/// result in infinite loops. 9674e3f125e184f96ae72f2c44d16cafe0d44158283Dan Gohmanstatic bool IsBetterFallthrough(MachineBasicBlock *MBB1, 96869244300b8a0112efb44b6273ecea4ca6264b8cfChris Lattner MachineBasicBlock *MBB2) { 969154e1047184384afd0a701a9f8816459cf0b3490Chris Lattner // Right now, we use a simple heuristic. If MBB2 ends with a call, and 970154e1047184384afd0a701a9f8816459cf0b3490Chris Lattner // MBB1 doesn't, we prefer to fall through into MBB1. This allows us to 971a7bef4a4e49f461984c04ef6be6eef3f1c023558Chris Lattner // optimize branches that branch to either a return block or an assert block 972a7bef4a4e49f461984c04ef6be6eef3f1c023558Chris Lattner // into a fallthrough to the return. 973a7bef4a4e49f461984c04ef6be6eef3f1c023558Chris Lattner if (MBB1->empty() || MBB2->empty()) return false; 9744e3f125e184f96ae72f2c44d16cafe0d44158283Dan Gohman 97511a4f64bd4cb6d438dd4b5882ee1b7404832f27fChristopher Lamb // If there is a clear successor ordering we make sure that one block 97611a4f64bd4cb6d438dd4b5882ee1b7404832f27fChristopher Lamb // will fall through to the next 97711a4f64bd4cb6d438dd4b5882ee1b7404832f27fChristopher Lamb if (MBB1->isSuccessor(MBB2)) return true; 97811a4f64bd4cb6d438dd4b5882ee1b7404832f27fChristopher Lamb if (MBB2->isSuccessor(MBB1)) return false; 979a7bef4a4e49f461984c04ef6be6eef3f1c023558Chris Lattner 980a7bef4a4e49f461984c04ef6be6eef3f1c023558Chris Lattner MachineInstr *MBB1I = --MBB1->end(); 981a7bef4a4e49f461984c04ef6be6eef3f1c023558Chris Lattner MachineInstr *MBB2I = --MBB2->end(); 982749c6f6b5ed301c84aac562e414486549d7b98ebChris Lattner return MBB2I->getDesc().isCall() && !MBB1I->getDesc().isCall(); 983a7bef4a4e49f461984c04ef6be6eef3f1c023558Chris Lattner} 984a7bef4a4e49f461984c04ef6be6eef3f1c023558Chris Lattner 9852210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman/// TailDuplicate - MBB unconditionally branches to SuccBB. If it is profitable, 9862210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman/// duplicate SuccBB's contents in MBB to eliminate the branch. 9872210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohmanbool BranchFolder::TailDuplicate(MachineBasicBlock *TailBB, 9882210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman bool PrevFallsThrough, 9892210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman MachineFunction &MF) { 9902210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman // Don't try to tail-duplicate single-block loops. 9912210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman if (TailBB->isSuccessor(TailBB)) 9922210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman return false; 9932210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman 9942210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman // Don't tail-duplicate a block which will soon be folded into its successor. 9952210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman if (TailBB->succ_size() == 1 && 9962210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman TailBB->succ_begin()[0]->pred_size() == 1) 9972210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman return false; 9982210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman 9992210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman // Duplicate up to one less that the tail-merge threshold, so that we don't 10002210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman // get into an infinite loop between duplicating and merging. When optimizing 10012210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman // for size, duplicate only one, because one branch instruction can be 10022210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman // eliminated to compensate for the duplication. 10032210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman unsigned MaxDuplicateCount = 10042210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman MF.getFunction()->hasFnAttr(Attribute::OptimizeForSize) ? 10052210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman 1 : (TailMergeSize - 1); 10062210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman 10072210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman // Check the instructions in the block to determine whether tail-duplication 10082210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman // is invalid or unlikely to be unprofitable. 10092210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman unsigned i = 0; 10102210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman bool HasCall = false; 10112210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman for (MachineBasicBlock::iterator I = TailBB->begin(); 10122210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman I != TailBB->end(); ++I, ++i) { 10132210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman // Non-duplicable things shouldn't be tail-duplicated. 10142210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman if (I->getDesc().isNotDuplicable()) return false; 10152210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman // Don't duplicate more than the threshold. 10162210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman if (i == MaxDuplicateCount) return false; 10172210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman // Remember if we saw a call. 10182210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman if (I->getDesc().isCall()) HasCall = true; 10192210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman } 10202210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman // Heuristically, don't tail-duplicate calls if it would expand code size, 10212210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman // as it's less likely to be worth the extra cost. 10222210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman if (i > 1 && HasCall) 10232210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman return false; 10242210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman 10252210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman // Iterate through all the unique predecessors and tail-duplicate this 10262210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman // block into them, if possible. Copying the list ahead of time also 10272210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman // avoids trouble with the predecessor list reallocating. 10282210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman bool Changed = false; 10292210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman SmallSetVector<MachineBasicBlock *, 8> Preds(TailBB->pred_begin(), 10302210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman TailBB->pred_end()); 10312210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman for (SmallSetVector<MachineBasicBlock *, 8>::iterator PI = Preds.begin(), 10322210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman PE = Preds.end(); PI != PE; ++PI) { 10332210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman MachineBasicBlock *PredBB = *PI; 10342210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman 10352210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman assert(TailBB != PredBB && 10362210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman "Single-block loop should have been rejected earlier!"); 10372210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman if (PredBB->succ_size() > 1) continue; 10382210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman 10392210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman MachineBasicBlock *PredTBB, *PredFBB; 10402210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman SmallVector<MachineOperand, 4> PredCond; 10412210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman if (TII->AnalyzeBranch(*PredBB, PredTBB, PredFBB, PredCond, true)) 10422210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman continue; 10432210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman if (!PredCond.empty()) 10442210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman continue; 10452210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman // EH edges are ignored by AnalyzeBranch. 10462210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman if (PredBB->succ_size() != 1) 10472210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman continue; 10482210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman // Don't duplicate into a fall-through predecessor unless its the 10492210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman // only predecessor. 10502210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman if (&*next(MachineFunction::iterator(PredBB)) == TailBB && 10512210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman PrevFallsThrough && 10522210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman TailBB->pred_size() != 1) 10532210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman continue; 10542210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman 10552210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman DEBUG(errs() << "\nTail-duplicating into PredBB: " << *PredBB 10562210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman << "From Succ: " << *TailBB); 10572210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman 10582210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman // Remove PredBB's unconditional branch. 10592210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman TII->RemoveBranch(*PredBB); 10602210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman // Clone the contents of TailBB into PredBB. 10612210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman for (MachineBasicBlock::iterator I = TailBB->begin(), E = TailBB->end(); 10622210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman I != E; ++I) { 10632210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman MachineInstr *NewMI = MF.CloneMachineInstr(I); 10642210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman PredBB->insert(PredBB->end(), NewMI); 10652210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman } 10662210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman 10672210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman // Update the CFG. 10682210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman PredBB->removeSuccessor(PredBB->succ_begin()); 10692210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman assert(PredBB->succ_empty() && 10702210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman "TailDuplicate called on block with multiple successors!"); 10712210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman for (MachineBasicBlock::succ_iterator I = TailBB->succ_begin(), 10722210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman E = TailBB->succ_end(); I != E; ++I) 10732210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman PredBB->addSuccessor(*I); 10742210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman 10752210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman Changed = true; 10762210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman } 10772210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman 10782210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman return Changed; 10792210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman} 10802210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman 10817821a8afd3009c3c2760592e61de9e2c31c73e18Chris Lattner/// OptimizeBlock - Analyze and optimize control flow related to the specified 10827821a8afd3009c3c2760592e61de9e2c31c73e18Chris Lattner/// block. This is never called on the entry block. 1083030a0a0cdb38924e55773a8e0b5fe7347aa664aaEvan Chengbool BranchFolder::OptimizeBlock(MachineBasicBlock *MBB) { 1084030a0a0cdb38924e55773a8e0b5fe7347aa664aaEvan Cheng bool MadeChange = false; 1085d194498d2669e28cd8e85b0ceb7c69a7ec66da13Dan Gohman MachineFunction &MF = *MBB->getParent(); 10862210c0bea83aa8a8585d793a1f63e8c01b65be38Dan GohmanReoptimizeBlock: 1087030a0a0cdb38924e55773a8e0b5fe7347aa664aaEvan Cheng 10887d09784d3fc652131a2afbf06a0f2ed893837fb9Chris Lattner MachineFunction::iterator FallThrough = MBB; 10897d09784d3fc652131a2afbf06a0f2ed893837fb9Chris Lattner ++FallThrough; 10904e3f125e184f96ae72f2c44d16cafe0d44158283Dan Gohman 1091eb15eeec396145b6f5028d07bd2c4a5e903fdec5Chris Lattner // If this block is empty, make everyone use its fall-through, not the block 1092a52dd151378eeaad1369829b1dc3164874774e04Dale Johannesen // explicitly. Landing pads should not do this since the landing-pad table 1093ab918103d284b91105831c6b198ad2ab760b907dDan Gohman // points to this block. Blocks with their addresses taken shouldn't be 1094ab918103d284b91105831c6b198ad2ab760b907dDan Gohman // optimized away. 1095ab918103d284b91105831c6b198ad2ab760b907dDan Gohman if (MBB->empty() && !MBB->isLandingPad() && !MBB->hasAddressTaken()) { 1096386e29065db5b05b57440f6b2a6dfa1e7f29a00dChris Lattner // Dead block? Leave for cleanup later. 1097030a0a0cdb38924e55773a8e0b5fe7347aa664aaEvan Cheng if (MBB->pred_empty()) return MadeChange; 10984e3f125e184f96ae72f2c44d16cafe0d44158283Dan Gohman 1099d194498d2669e28cd8e85b0ceb7c69a7ec66da13Dan Gohman if (FallThrough == MF.end()) { 1100c50ffcb7fcb7c1109fee2406e8f74d096f755f47Chris Lattner // TODO: Simplify preds to not branch here if possible! 1101c50ffcb7fcb7c1109fee2406e8f74d096f755f47Chris Lattner } else { 1102c50ffcb7fcb7c1109fee2406e8f74d096f755f47Chris Lattner // Rewrite all predecessors of the old block to go to the fallthrough 1103c50ffcb7fcb7c1109fee2406e8f74d096f755f47Chris Lattner // instead. 1104033c9715d9bf7ce59ad2e466bf0720811b34da08Jim Laskey while (!MBB->pred_empty()) { 11057821a8afd3009c3c2760592e61de9e2c31c73e18Chris Lattner MachineBasicBlock *Pred = *(MBB->pred_end()-1); 11060370fad74b48388412c52d1325512f2c218487faEvan Cheng Pred->ReplaceUsesOfBlockWith(MBB, FallThrough); 11077821a8afd3009c3c2760592e61de9e2c31c73e18Chris Lattner } 1108c50ffcb7fcb7c1109fee2406e8f74d096f755f47Chris Lattner // If MBB was the target of a jump table, update jump tables to go to the 1109c50ffcb7fcb7c1109fee2406e8f74d096f755f47Chris Lattner // fallthrough instead. 1110d194498d2669e28cd8e85b0ceb7c69a7ec66da13Dan Gohman MF.getJumpTableInfo()->ReplaceMBBInJumpTables(MBB, FallThrough); 11117821a8afd3009c3c2760592e61de9e2c31c73e18Chris Lattner MadeChange = true; 111221ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner } 1113030a0a0cdb38924e55773a8e0b5fe7347aa664aaEvan Cheng return MadeChange; 111421ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner } 111521ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner 11167821a8afd3009c3c2760592e61de9e2c31c73e18Chris Lattner // Check to see if we can simplify the terminator of the block before this 11177821a8afd3009c3c2760592e61de9e2c31c73e18Chris Lattner // one. 11187d09784d3fc652131a2afbf06a0f2ed893837fb9Chris Lattner MachineBasicBlock &PrevBB = *prior(MachineFunction::iterator(MBB)); 1119ffddf6ba1c58b42dcfd071972754649c3ca5dff7Chris Lattner 11207821a8afd3009c3c2760592e61de9e2c31c73e18Chris Lattner MachineBasicBlock *PriorTBB = 0, *PriorFBB = 0; 112144eb65cf58e3ab9b5621ce72256d1621a18aeed7Owen Anderson SmallVector<MachineOperand, 4> PriorCond; 11226b0e3f890779b7fc912bec8d40a9590e44742737Chris Lattner bool PriorUnAnalyzable = 1123dc54d317e7a381ef8e4aca80d54ad1466bb85ddaEvan Cheng TII->AnalyzeBranch(PrevBB, PriorTBB, PriorFBB, PriorCond, true); 1124386e29065db5b05b57440f6b2a6dfa1e7f29a00dChris Lattner if (!PriorUnAnalyzable) { 1125386e29065db5b05b57440f6b2a6dfa1e7f29a00dChris Lattner // If the CFG for the prior block has extra edges, remove them. 11262bdb7d0cc88881857073b36f4a09ebe2f2008c24Evan Cheng MadeChange |= PrevBB.CorrectExtraCFGEdges(PriorTBB, PriorFBB, 11272bdb7d0cc88881857073b36f4a09ebe2f2008c24Evan Cheng !PriorCond.empty()); 11284e3f125e184f96ae72f2c44d16cafe0d44158283Dan Gohman 11297821a8afd3009c3c2760592e61de9e2c31c73e18Chris Lattner // If the previous branch is conditional and both conditions go to the same 11302d47bd937c13556ace07b2b2daf4dfe75f4e1e90Chris Lattner // destination, remove the branch, replacing it with an unconditional one or 11312d47bd937c13556ace07b2b2daf4dfe75f4e1e90Chris Lattner // a fall-through. 11327821a8afd3009c3c2760592e61de9e2c31c73e18Chris Lattner if (PriorTBB && PriorTBB == PriorFBB) { 1133386e29065db5b05b57440f6b2a6dfa1e7f29a00dChris Lattner TII->RemoveBranch(PrevBB); 11344e3f125e184f96ae72f2c44d16cafe0d44158283Dan Gohman PriorCond.clear(); 11357d09784d3fc652131a2afbf06a0f2ed893837fb9Chris Lattner if (PriorTBB != MBB) 1136386e29065db5b05b57440f6b2a6dfa1e7f29a00dChris Lattner TII->InsertBranch(PrevBB, PriorTBB, 0, PriorCond); 11377821a8afd3009c3c2760592e61de9e2c31c73e18Chris Lattner MadeChange = true; 113812143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner ++NumBranchOpts; 11392210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman goto ReoptimizeBlock; 11407821a8afd3009c3c2760592e61de9e2c31c73e18Chris Lattner } 11414e3f125e184f96ae72f2c44d16cafe0d44158283Dan Gohman 11422210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman // If the previous block unconditionally falls through to this block and 11432210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman // this block has no other predecessors, move the contents of this block 11442210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman // into the prior block. This doesn't usually happen when SimplifyCFG 11452210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman // has been used, but it can happen tail duplication eliminates all the 11462210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman // non-branch predecessors of a block leaving only the fall-through edge. 11472210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman // This has to check PrevBB->succ_size() because EH edges are ignored by 11482210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman // AnalyzeBranch. 11492210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman if (PriorCond.empty() && !PriorTBB && MBB->pred_size() == 1 && 11502210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman PrevBB.succ_size() == 1 && 11512210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman !MBB->hasAddressTaken()) { 11522210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman DEBUG(errs() << "\nMerging into block: " << PrevBB 11532210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman << "From MBB: " << *MBB); 11542210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman PrevBB.splice(PrevBB.end(), MBB, MBB->begin(), MBB->end()); 11552210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman PrevBB.removeSuccessor(PrevBB.succ_begin());; 11562210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman assert(PrevBB.succ_empty()); 11572210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman PrevBB.transferSuccessors(MBB); 11582210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman MadeChange = true; 11592210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman return MadeChange; 11602210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman } 11612210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman 11627821a8afd3009c3c2760592e61de9e2c31c73e18Chris Lattner // If the previous branch *only* branches to *this* block (conditional or 11637821a8afd3009c3c2760592e61de9e2c31c73e18Chris Lattner // not) remove the branch. 11647d09784d3fc652131a2afbf06a0f2ed893837fb9Chris Lattner if (PriorTBB == MBB && PriorFBB == 0) { 1165386e29065db5b05b57440f6b2a6dfa1e7f29a00dChris Lattner TII->RemoveBranch(PrevBB); 11667821a8afd3009c3c2760592e61de9e2c31c73e18Chris Lattner MadeChange = true; 116712143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner ++NumBranchOpts; 11682210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman goto ReoptimizeBlock; 11697821a8afd3009c3c2760592e61de9e2c31c73e18Chris Lattner } 11704e3f125e184f96ae72f2c44d16cafe0d44158283Dan Gohman 11712d47bd937c13556ace07b2b2daf4dfe75f4e1e90Chris Lattner // If the prior block branches somewhere else on the condition and here if 11722d47bd937c13556ace07b2b2daf4dfe75f4e1e90Chris Lattner // the condition is false, remove the uncond second branch. 11737d09784d3fc652131a2afbf06a0f2ed893837fb9Chris Lattner if (PriorFBB == MBB) { 11742d47bd937c13556ace07b2b2daf4dfe75f4e1e90Chris Lattner TII->RemoveBranch(PrevBB); 11752d47bd937c13556ace07b2b2daf4dfe75f4e1e90Chris Lattner TII->InsertBranch(PrevBB, PriorTBB, 0, PriorCond); 11762d47bd937c13556ace07b2b2daf4dfe75f4e1e90Chris Lattner MadeChange = true; 11772d47bd937c13556ace07b2b2daf4dfe75f4e1e90Chris Lattner ++NumBranchOpts; 11782210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman goto ReoptimizeBlock; 11792d47bd937c13556ace07b2b2daf4dfe75f4e1e90Chris Lattner } 11804e3f125e184f96ae72f2c44d16cafe0d44158283Dan Gohman 1181a2d799531a748a349b9a458dbbc580b134074c49Chris Lattner // If the prior block branches here on true and somewhere else on false, and 1182a2d799531a748a349b9a458dbbc580b134074c49Chris Lattner // if the branch condition is reversible, reverse the branch to create a 1183a2d799531a748a349b9a458dbbc580b134074c49Chris Lattner // fall-through. 11847d09784d3fc652131a2afbf06a0f2ed893837fb9Chris Lattner if (PriorTBB == MBB) { 118544eb65cf58e3ab9b5621ce72256d1621a18aeed7Owen Anderson SmallVector<MachineOperand, 4> NewPriorCond(PriorCond); 1186a2d799531a748a349b9a458dbbc580b134074c49Chris Lattner if (!TII->ReverseBranchCondition(NewPriorCond)) { 1187a2d799531a748a349b9a458dbbc580b134074c49Chris Lattner TII->RemoveBranch(PrevBB); 1188a2d799531a748a349b9a458dbbc580b134074c49Chris Lattner TII->InsertBranch(PrevBB, PriorFBB, 0, NewPriorCond); 1189a2d799531a748a349b9a458dbbc580b134074c49Chris Lattner MadeChange = true; 1190a2d799531a748a349b9a458dbbc580b134074c49Chris Lattner ++NumBranchOpts; 11912210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman goto ReoptimizeBlock; 1192a2d799531a748a349b9a458dbbc580b134074c49Chris Lattner } 1193a2d799531a748a349b9a458dbbc580b134074c49Chris Lattner } 11944e3f125e184f96ae72f2c44d16cafe0d44158283Dan Gohman 11956d31268a7dc9854fa5a5cb9227ba9a15c5898414Dan Gohman // If this block has no successors (e.g. it is a return block or ends with 11966d31268a7dc9854fa5a5cb9227ba9a15c5898414Dan Gohman // a call to a no-return function like abort or __cxa_throw) and if the pred 11976d31268a7dc9854fa5a5cb9227ba9a15c5898414Dan Gohman // falls through into this block, and if it would otherwise fall through 11986d31268a7dc9854fa5a5cb9227ba9a15c5898414Dan Gohman // into the block after this, move this block to the end of the function. 1199154e1047184384afd0a701a9f8816459cf0b3490Chris Lattner // 1200a7bef4a4e49f461984c04ef6be6eef3f1c023558Chris Lattner // We consider it more likely that execution will stay in the function (e.g. 1201a7bef4a4e49f461984c04ef6be6eef3f1c023558Chris Lattner // due to loops) than it is to exit it. This asserts in loops etc, moving 1202a7bef4a4e49f461984c04ef6be6eef3f1c023558Chris Lattner // the assert condition out of the loop body. 12036d31268a7dc9854fa5a5cb9227ba9a15c5898414Dan Gohman if (MBB->succ_empty() && !PriorCond.empty() && PriorFBB == 0 && 1204154e1047184384afd0a701a9f8816459cf0b3490Chris Lattner MachineFunction::iterator(PriorTBB) == FallThrough && 1205154e1047184384afd0a701a9f8816459cf0b3490Chris Lattner !CanFallThrough(MBB)) { 1206f10a56a86f8ae32d0493c7de770493d55519b073Chris Lattner bool DoTransform = true; 12074e3f125e184f96ae72f2c44d16cafe0d44158283Dan Gohman 1208a7bef4a4e49f461984c04ef6be6eef3f1c023558Chris Lattner // We have to be careful that the succs of PredBB aren't both no-successor 1209a7bef4a4e49f461984c04ef6be6eef3f1c023558Chris Lattner // blocks. If neither have successors and if PredBB is the second from 1210a7bef4a4e49f461984c04ef6be6eef3f1c023558Chris Lattner // last block in the function, we'd just keep swapping the two blocks for 1211a7bef4a4e49f461984c04ef6be6eef3f1c023558Chris Lattner // last. Only do the swap if one is clearly better to fall through than 1212a7bef4a4e49f461984c04ef6be6eef3f1c023558Chris Lattner // the other. 1213d194498d2669e28cd8e85b0ceb7c69a7ec66da13Dan Gohman if (FallThrough == --MF.end() && 121469244300b8a0112efb44b6273ecea4ca6264b8cfChris Lattner !IsBetterFallthrough(PriorTBB, MBB)) 1215f10a56a86f8ae32d0493c7de770493d55519b073Chris Lattner DoTransform = false; 1216f10a56a86f8ae32d0493c7de770493d55519b073Chris Lattner 1217f10a56a86f8ae32d0493c7de770493d55519b073Chris Lattner // We don't want to do this transformation if we have control flow like: 1218f10a56a86f8ae32d0493c7de770493d55519b073Chris Lattner // br cond BB2 1219f10a56a86f8ae32d0493c7de770493d55519b073Chris Lattner // BB1: 1220f10a56a86f8ae32d0493c7de770493d55519b073Chris Lattner // .. 1221f10a56a86f8ae32d0493c7de770493d55519b073Chris Lattner // jmp BBX 1222f10a56a86f8ae32d0493c7de770493d55519b073Chris Lattner // BB2: 1223f10a56a86f8ae32d0493c7de770493d55519b073Chris Lattner // .. 1224f10a56a86f8ae32d0493c7de770493d55519b073Chris Lattner // ret 1225f10a56a86f8ae32d0493c7de770493d55519b073Chris Lattner // 1226f10a56a86f8ae32d0493c7de770493d55519b073Chris Lattner // In this case, we could actually be moving the return block *into* a 1227f10a56a86f8ae32d0493c7de770493d55519b073Chris Lattner // loop! 12284b105912657c0472dc4f6f7244ce20bf7cf9a7dcChris Lattner if (DoTransform && !MBB->succ_empty() && 12294b105912657c0472dc4f6f7244ce20bf7cf9a7dcChris Lattner (!CanFallThrough(PriorTBB) || PriorTBB->empty())) 1230f10a56a86f8ae32d0493c7de770493d55519b073Chris Lattner DoTransform = false; 12314e3f125e184f96ae72f2c44d16cafe0d44158283Dan Gohman 12324e3f125e184f96ae72f2c44d16cafe0d44158283Dan Gohman 1233f10a56a86f8ae32d0493c7de770493d55519b073Chris Lattner if (DoTransform) { 1234a7bef4a4e49f461984c04ef6be6eef3f1c023558Chris Lattner // Reverse the branch so we will fall through on the previous true cond. 123544eb65cf58e3ab9b5621ce72256d1621a18aeed7Owen Anderson SmallVector<MachineOperand, 4> NewPriorCond(PriorCond); 1236a7bef4a4e49f461984c04ef6be6eef3f1c023558Chris Lattner if (!TII->ReverseBranchCondition(NewPriorCond)) { 12373403bcd8f943cb053a7d9bbf8eb8135407699afaBill Wendling DEBUG(errs() << "\nMoving MBB: " << *MBB 12383403bcd8f943cb053a7d9bbf8eb8135407699afaBill Wendling << "To make fallthrough to: " << *PriorTBB << "\n"); 12394e3f125e184f96ae72f2c44d16cafe0d44158283Dan Gohman 1240a7bef4a4e49f461984c04ef6be6eef3f1c023558Chris Lattner TII->RemoveBranch(PrevBB); 1241a7bef4a4e49f461984c04ef6be6eef3f1c023558Chris Lattner TII->InsertBranch(PrevBB, MBB, 0, NewPriorCond); 1242a7bef4a4e49f461984c04ef6be6eef3f1c023558Chris Lattner 1243a7bef4a4e49f461984c04ef6be6eef3f1c023558Chris Lattner // Move this block to the end of the function. 1244d194498d2669e28cd8e85b0ceb7c69a7ec66da13Dan Gohman MBB->moveAfter(--MF.end()); 1245a7bef4a4e49f461984c04ef6be6eef3f1c023558Chris Lattner MadeChange = true; 1246a7bef4a4e49f461984c04ef6be6eef3f1c023558Chris Lattner ++NumBranchOpts; 1247030a0a0cdb38924e55773a8e0b5fe7347aa664aaEvan Cheng return MadeChange; 1248a7bef4a4e49f461984c04ef6be6eef3f1c023558Chris Lattner } 1249a7bef4a4e49f461984c04ef6be6eef3f1c023558Chris Lattner } 1250a7bef4a4e49f461984c04ef6be6eef3f1c023558Chris Lattner } 12517821a8afd3009c3c2760592e61de9e2c31c73e18Chris Lattner } 12524e3f125e184f96ae72f2c44d16cafe0d44158283Dan Gohman 1253386e29065db5b05b57440f6b2a6dfa1e7f29a00dChris Lattner // Analyze the branch in the current block. 1254386e29065db5b05b57440f6b2a6dfa1e7f29a00dChris Lattner MachineBasicBlock *CurTBB = 0, *CurFBB = 0; 125544eb65cf58e3ab9b5621ce72256d1621a18aeed7Owen Anderson SmallVector<MachineOperand, 4> CurCond; 1256dc54d317e7a381ef8e4aca80d54ad1466bb85ddaEvan Cheng bool CurUnAnalyzable= TII->AnalyzeBranch(*MBB, CurTBB, CurFBB, CurCond, true); 12576b0e3f890779b7fc912bec8d40a9590e44742737Chris Lattner if (!CurUnAnalyzable) { 1258386e29065db5b05b57440f6b2a6dfa1e7f29a00dChris Lattner // If the CFG for the prior block has extra edges, remove them. 12592bdb7d0cc88881857073b36f4a09ebe2f2008c24Evan Cheng MadeChange |= MBB->CorrectExtraCFGEdges(CurTBB, CurFBB, !CurCond.empty()); 1260386e29065db5b05b57440f6b2a6dfa1e7f29a00dChris Lattner 12614e3f125e184f96ae72f2c44d16cafe0d44158283Dan Gohman // If this is a two-way branch, and the FBB branches to this block, reverse 12625d056952ba2f97729c5db69a3f14250595fa1ee8Chris Lattner // the condition so the single-basic-block loop is faster. Instead of: 12635d056952ba2f97729c5db69a3f14250595fa1ee8Chris Lattner // Loop: xxx; jcc Out; jmp Loop 12645d056952ba2f97729c5db69a3f14250595fa1ee8Chris Lattner // we want: 12655d056952ba2f97729c5db69a3f14250595fa1ee8Chris Lattner // Loop: xxx; jncc Loop; jmp Out 12665d056952ba2f97729c5db69a3f14250595fa1ee8Chris Lattner if (CurTBB && CurFBB && CurFBB == MBB && CurTBB != MBB) { 126744eb65cf58e3ab9b5621ce72256d1621a18aeed7Owen Anderson SmallVector<MachineOperand, 4> NewCond(CurCond); 12685d056952ba2f97729c5db69a3f14250595fa1ee8Chris Lattner if (!TII->ReverseBranchCondition(NewCond)) { 12695d056952ba2f97729c5db69a3f14250595fa1ee8Chris Lattner TII->RemoveBranch(*MBB); 12705d056952ba2f97729c5db69a3f14250595fa1ee8Chris Lattner TII->InsertBranch(*MBB, CurFBB, CurTBB, NewCond); 12715d056952ba2f97729c5db69a3f14250595fa1ee8Chris Lattner MadeChange = true; 12725d056952ba2f97729c5db69a3f14250595fa1ee8Chris Lattner ++NumBranchOpts; 12732210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman goto ReoptimizeBlock; 12745d056952ba2f97729c5db69a3f14250595fa1ee8Chris Lattner } 12755d056952ba2f97729c5db69a3f14250595fa1ee8Chris Lattner } 12764e3f125e184f96ae72f2c44d16cafe0d44158283Dan Gohman 12774e3f125e184f96ae72f2c44d16cafe0d44158283Dan Gohman 1278386e29065db5b05b57440f6b2a6dfa1e7f29a00dChris Lattner // If this branch is the only thing in its block, see if we can forward 1279386e29065db5b05b57440f6b2a6dfa1e7f29a00dChris Lattner // other blocks across it. 12804e3f125e184f96ae72f2c44d16cafe0d44158283Dan Gohman if (CurTBB && CurCond.empty() && CurFBB == 0 && 1281888acc35a3e271d092f9b1efc7c32b94ff17fbf7Bob Wilson MBB->begin()->getDesc().isBranch() && CurTBB != MBB && 1282888acc35a3e271d092f9b1efc7c32b94ff17fbf7Bob Wilson !MBB->hasAddressTaken()) { 1283386e29065db5b05b57440f6b2a6dfa1e7f29a00dChris Lattner // This block may contain just an unconditional branch. Because there can 1284386e29065db5b05b57440f6b2a6dfa1e7f29a00dChris Lattner // be 'non-branch terminators' in the block, try removing the branch and 1285386e29065db5b05b57440f6b2a6dfa1e7f29a00dChris Lattner // then seeing if the block is empty. 1286386e29065db5b05b57440f6b2a6dfa1e7f29a00dChris Lattner TII->RemoveBranch(*MBB); 1287386e29065db5b05b57440f6b2a6dfa1e7f29a00dChris Lattner 1288386e29065db5b05b57440f6b2a6dfa1e7f29a00dChris Lattner // If this block is just an unconditional branch to CurTBB, we can 1289386e29065db5b05b57440f6b2a6dfa1e7f29a00dChris Lattner // usually completely eliminate the block. The only case we cannot 1290386e29065db5b05b57440f6b2a6dfa1e7f29a00dChris Lattner // completely eliminate the block is when the block before this one 1291386e29065db5b05b57440f6b2a6dfa1e7f29a00dChris Lattner // falls through into MBB and we can't understand the prior block's branch 1292386e29065db5b05b57440f6b2a6dfa1e7f29a00dChris Lattner // condition. 1293cf420cca572b061fdd63587cb90904c641b6e216Chris Lattner if (MBB->empty()) { 1294cf420cca572b061fdd63587cb90904c641b6e216Chris Lattner bool PredHasNoFallThrough = TII->BlockHasNoFallThrough(PrevBB); 1295cf420cca572b061fdd63587cb90904c641b6e216Chris Lattner if (PredHasNoFallThrough || !PriorUnAnalyzable || 1296cf420cca572b061fdd63587cb90904c641b6e216Chris Lattner !PrevBB.isSuccessor(MBB)) { 1297cf420cca572b061fdd63587cb90904c641b6e216Chris Lattner // If the prior block falls through into us, turn it into an 1298cf420cca572b061fdd63587cb90904c641b6e216Chris Lattner // explicit branch to us to make updates simpler. 12994e3f125e184f96ae72f2c44d16cafe0d44158283Dan Gohman if (!PredHasNoFallThrough && PrevBB.isSuccessor(MBB) && 1300cf420cca572b061fdd63587cb90904c641b6e216Chris Lattner PriorTBB != MBB && PriorFBB != MBB) { 1301cf420cca572b061fdd63587cb90904c641b6e216Chris Lattner if (PriorTBB == 0) { 13026acfe12dd6d52c801f78c240528b7cb42fa91159Chris Lattner assert(PriorCond.empty() && PriorFBB == 0 && 13036acfe12dd6d52c801f78c240528b7cb42fa91159Chris Lattner "Bad branch analysis"); 1304cf420cca572b061fdd63587cb90904c641b6e216Chris Lattner PriorTBB = MBB; 1305cf420cca572b061fdd63587cb90904c641b6e216Chris Lattner } else { 1306cf420cca572b061fdd63587cb90904c641b6e216Chris Lattner assert(PriorFBB == 0 && "Machine CFG out of date!"); 1307cf420cca572b061fdd63587cb90904c641b6e216Chris Lattner PriorFBB = MBB; 1308cf420cca572b061fdd63587cb90904c641b6e216Chris Lattner } 1309cf420cca572b061fdd63587cb90904c641b6e216Chris Lattner TII->RemoveBranch(PrevBB); 1310cf420cca572b061fdd63587cb90904c641b6e216Chris Lattner TII->InsertBranch(PrevBB, PriorTBB, PriorFBB, PriorCond); 1311386e29065db5b05b57440f6b2a6dfa1e7f29a00dChris Lattner } 131221ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner 1313cf420cca572b061fdd63587cb90904c641b6e216Chris Lattner // Iterate through all the predecessors, revectoring each in-turn. 13148a46d342d8cbca7c9c7be6c66007d41329babad0David Greene size_t PI = 0; 1315cf420cca572b061fdd63587cb90904c641b6e216Chris Lattner bool DidChange = false; 1316cf420cca572b061fdd63587cb90904c641b6e216Chris Lattner bool HasBranchToSelf = false; 13178a46d342d8cbca7c9c7be6c66007d41329babad0David Greene while(PI != MBB->pred_size()) { 13188a46d342d8cbca7c9c7be6c66007d41329babad0David Greene MachineBasicBlock *PMBB = *(MBB->pred_begin() + PI); 13198a46d342d8cbca7c9c7be6c66007d41329babad0David Greene if (PMBB == MBB) { 1320cf420cca572b061fdd63587cb90904c641b6e216Chris Lattner // If this block has an uncond branch to itself, leave it. 1321cf420cca572b061fdd63587cb90904c641b6e216Chris Lattner ++PI; 1322cf420cca572b061fdd63587cb90904c641b6e216Chris Lattner HasBranchToSelf = true; 1323cf420cca572b061fdd63587cb90904c641b6e216Chris Lattner } else { 1324cf420cca572b061fdd63587cb90904c641b6e216Chris Lattner DidChange = true; 13258a46d342d8cbca7c9c7be6c66007d41329babad0David Greene PMBB->ReplaceUsesOfBlockWith(MBB, CurTBB); 1326bf06f6a6f1be0802ad7b761138ecba568814008aDale Johannesen // If this change resulted in PMBB ending in a conditional 1327bf06f6a6f1be0802ad7b761138ecba568814008aDale Johannesen // branch where both conditions go to the same destination, 1328bf06f6a6f1be0802ad7b761138ecba568814008aDale Johannesen // change this to an unconditional branch (and fix the CFG). 1329bf06f6a6f1be0802ad7b761138ecba568814008aDale Johannesen MachineBasicBlock *NewCurTBB = 0, *NewCurFBB = 0; 1330bf06f6a6f1be0802ad7b761138ecba568814008aDale Johannesen SmallVector<MachineOperand, 4> NewCurCond; 1331bf06f6a6f1be0802ad7b761138ecba568814008aDale Johannesen bool NewCurUnAnalyzable = TII->AnalyzeBranch(*PMBB, NewCurTBB, 1332bf06f6a6f1be0802ad7b761138ecba568814008aDale Johannesen NewCurFBB, NewCurCond, true); 1333bf06f6a6f1be0802ad7b761138ecba568814008aDale Johannesen if (!NewCurUnAnalyzable && NewCurTBB && NewCurTBB == NewCurFBB) { 1334bf06f6a6f1be0802ad7b761138ecba568814008aDale Johannesen TII->RemoveBranch(*PMBB); 13354e3f125e184f96ae72f2c44d16cafe0d44158283Dan Gohman NewCurCond.clear(); 1336bf06f6a6f1be0802ad7b761138ecba568814008aDale Johannesen TII->InsertBranch(*PMBB, NewCurTBB, 0, NewCurCond); 1337bf06f6a6f1be0802ad7b761138ecba568814008aDale Johannesen MadeChange = true; 1338bf06f6a6f1be0802ad7b761138ecba568814008aDale Johannesen ++NumBranchOpts; 13392210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman PMBB->CorrectExtraCFGEdges(NewCurTBB, 0, false); 1340bf06f6a6f1be0802ad7b761138ecba568814008aDale Johannesen } 1341cf420cca572b061fdd63587cb90904c641b6e216Chris Lattner } 13424bc135e93beebdcb3b9c44745c5ccbc91199ac0bChris Lattner } 134321ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner 1344cf420cca572b061fdd63587cb90904c641b6e216Chris Lattner // Change any jumptables to go to the new MBB. 1345d194498d2669e28cd8e85b0ceb7c69a7ec66da13Dan Gohman MF.getJumpTableInfo()->ReplaceMBBInJumpTables(MBB, CurTBB); 1346cf420cca572b061fdd63587cb90904c641b6e216Chris Lattner if (DidChange) { 1347cf420cca572b061fdd63587cb90904c641b6e216Chris Lattner ++NumBranchOpts; 1348cf420cca572b061fdd63587cb90904c641b6e216Chris Lattner MadeChange = true; 1349030a0a0cdb38924e55773a8e0b5fe7347aa664aaEvan Cheng if (!HasBranchToSelf) return MadeChange; 1350cf420cca572b061fdd63587cb90904c641b6e216Chris Lattner } 13514bc135e93beebdcb3b9c44745c5ccbc91199ac0bChris Lattner } 135221ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner } 13534e3f125e184f96ae72f2c44d16cafe0d44158283Dan Gohman 1354386e29065db5b05b57440f6b2a6dfa1e7f29a00dChris Lattner // Add the branch back if the block is more than just an uncond branch. 1355386e29065db5b05b57440f6b2a6dfa1e7f29a00dChris Lattner TII->InsertBranch(*MBB, CurTBB, 0, CurCond); 135621ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner } 13576b0e3f890779b7fc912bec8d40a9590e44742737Chris Lattner } 13586b0e3f890779b7fc912bec8d40a9590e44742737Chris Lattner 13592210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman // Now we know that there was no fall-through into this block, check to 13602210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman // see if it has a fall-through into its successor. 13612210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman bool CurFallsThru = CanFallThrough(MBB, CurUnAnalyzable, CurTBB, CurFBB, 13622210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman CurCond); 13632210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman bool PrevFallsThru = CanFallThrough(&PrevBB, PriorUnAnalyzable, 13642210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman PriorTBB, PriorFBB, PriorCond); 13652210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman 13662210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman // If this block is small, unconditionally branched to, and does not 13672210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman // fall through, tail-duplicate its instructions into its predecessors 13682210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman // to eliminate a (dynamic) branch. 13692210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman if (!CurFallsThru) 13702210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman if (TailDuplicate(MBB, PrevFallsThru, MF)) { 13712210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman MadeChange = true; 13722210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman return MadeChange; 13732210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman } 13742210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman 13756b0e3f890779b7fc912bec8d40a9590e44742737Chris Lattner // If the prior block doesn't fall through into this block, and if this 13766b0e3f890779b7fc912bec8d40a9590e44742737Chris Lattner // block doesn't fall through into some other block, see if we can find a 13776b0e3f890779b7fc912bec8d40a9590e44742737Chris Lattner // place to move this block where a fall-through will happen. 13782210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman if (!PrevFallsThru) { 137902b3f5ec4ac120d14a63f7fd4f4388b7d0ab6c22Jim Laskey if (!MBB->isLandingPad()) { 138002b3f5ec4ac120d14a63f7fd4f4388b7d0ab6c22Jim Laskey // Check all the predecessors of this block. If one of them has no fall 138102b3f5ec4ac120d14a63f7fd4f4388b7d0ab6c22Jim Laskey // throughs, move this block right after it. 138202b3f5ec4ac120d14a63f7fd4f4388b7d0ab6c22Jim Laskey for (MachineBasicBlock::pred_iterator PI = MBB->pred_begin(), 138302b3f5ec4ac120d14a63f7fd4f4388b7d0ab6c22Jim Laskey E = MBB->pred_end(); PI != E; ++PI) { 138402b3f5ec4ac120d14a63f7fd4f4388b7d0ab6c22Jim Laskey // Analyze the branch at the end of the pred. 138502b3f5ec4ac120d14a63f7fd4f4388b7d0ab6c22Jim Laskey MachineBasicBlock *PredBB = *PI; 138602b3f5ec4ac120d14a63f7fd4f4388b7d0ab6c22Jim Laskey MachineFunction::iterator PredFallthrough = PredBB; ++PredFallthrough; 13872210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman MachineBasicBlock *PredTBB, *PredFBB; 13882210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman SmallVector<MachineOperand, 4> PredCond; 13892210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman if (PredBB != MBB && !CanFallThrough(PredBB) && 13902210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman !TII->AnalyzeBranch(*PredBB, PredTBB, PredFBB, PredCond, true) 139176b38fcabeba725e166a2ff72c56fe31d784b229Dale Johannesen && (!CurFallsThru || !CurTBB || !CurFBB) 139202b3f5ec4ac120d14a63f7fd4f4388b7d0ab6c22Jim Laskey && (!CurFallsThru || MBB->getNumber() >= PredBB->getNumber())) { 139302b3f5ec4ac120d14a63f7fd4f4388b7d0ab6c22Jim Laskey // If the current block doesn't fall through, just move it. 139402b3f5ec4ac120d14a63f7fd4f4388b7d0ab6c22Jim Laskey // If the current block can fall through and does not end with a 13954e3f125e184f96ae72f2c44d16cafe0d44158283Dan Gohman // conditional branch, we need to append an unconditional jump to 139602b3f5ec4ac120d14a63f7fd4f4388b7d0ab6c22Jim Laskey // the (current) next block. To avoid a possible compile-time 139702b3f5ec4ac120d14a63f7fd4f4388b7d0ab6c22Jim Laskey // infinite loop, move blocks only backward in this case. 139876b38fcabeba725e166a2ff72c56fe31d784b229Dale Johannesen // Also, if there are already 2 branches here, we cannot add a third; 139976b38fcabeba725e166a2ff72c56fe31d784b229Dale Johannesen // this means we have the case 140076b38fcabeba725e166a2ff72c56fe31d784b229Dale Johannesen // Bcc next 140176b38fcabeba725e166a2ff72c56fe31d784b229Dale Johannesen // B elsewhere 140276b38fcabeba725e166a2ff72c56fe31d784b229Dale Johannesen // next: 140302b3f5ec4ac120d14a63f7fd4f4388b7d0ab6c22Jim Laskey if (CurFallsThru) { 140402b3f5ec4ac120d14a63f7fd4f4388b7d0ab6c22Jim Laskey MachineBasicBlock *NextBB = next(MachineFunction::iterator(MBB)); 140502b3f5ec4ac120d14a63f7fd4f4388b7d0ab6c22Jim Laskey CurCond.clear(); 140602b3f5ec4ac120d14a63f7fd4f4388b7d0ab6c22Jim Laskey TII->InsertBranch(*MBB, NextBB, 0, CurCond); 140702b3f5ec4ac120d14a63f7fd4f4388b7d0ab6c22Jim Laskey } 140802b3f5ec4ac120d14a63f7fd4f4388b7d0ab6c22Jim Laskey MBB->moveAfter(PredBB); 140902b3f5ec4ac120d14a63f7fd4f4388b7d0ab6c22Jim Laskey MadeChange = true; 14102210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman goto ReoptimizeBlock; 14117d09784d3fc652131a2afbf06a0f2ed893837fb9Chris Lattner } 14126b0e3f890779b7fc912bec8d40a9590e44742737Chris Lattner } 14136b896cec8b703e08e5f3d809e086a39b6ebe6589Dale Johannesen } 14144e3f125e184f96ae72f2c44d16cafe0d44158283Dan Gohman 14156b896cec8b703e08e5f3d809e086a39b6ebe6589Dale Johannesen if (!CurFallsThru) { 14166b0e3f890779b7fc912bec8d40a9590e44742737Chris Lattner // Check all successors to see if we can move this block before it. 14176b0e3f890779b7fc912bec8d40a9590e44742737Chris Lattner for (MachineBasicBlock::succ_iterator SI = MBB->succ_begin(), 14186b0e3f890779b7fc912bec8d40a9590e44742737Chris Lattner E = MBB->succ_end(); SI != E; ++SI) { 14196b0e3f890779b7fc912bec8d40a9590e44742737Chris Lattner // Analyze the branch at the end of the block before the succ. 14206b0e3f890779b7fc912bec8d40a9590e44742737Chris Lattner MachineBasicBlock *SuccBB = *SI; 14216b0e3f890779b7fc912bec8d40a9590e44742737Chris Lattner MachineFunction::iterator SuccPrev = SuccBB; --SuccPrev; 14224e3f125e184f96ae72f2c44d16cafe0d44158283Dan Gohman 142377edc4b1b004726d96c932356750b9f3c96d74ddChris Lattner // If this block doesn't already fall-through to that successor, and if 142477edc4b1b004726d96c932356750b9f3c96d74ddChris Lattner // the succ doesn't already have a block that can fall through into it, 142577edc4b1b004726d96c932356750b9f3c96d74ddChris Lattner // and if the successor isn't an EH destination, we can arrange for the 142677edc4b1b004726d96c932356750b9f3c96d74ddChris Lattner // fallthrough to happen. 14272210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman if (SuccBB != MBB && &*SuccPrev != MBB && 14282210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman !CanFallThrough(SuccPrev) && !CurUnAnalyzable && 142977edc4b1b004726d96c932356750b9f3c96d74ddChris Lattner !SuccBB->isLandingPad()) { 14306b0e3f890779b7fc912bec8d40a9590e44742737Chris Lattner MBB->moveBefore(SuccBB); 14317d09784d3fc652131a2afbf06a0f2ed893837fb9Chris Lattner MadeChange = true; 14322210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman goto ReoptimizeBlock; 14337d09784d3fc652131a2afbf06a0f2ed893837fb9Chris Lattner } 14347d09784d3fc652131a2afbf06a0f2ed893837fb9Chris Lattner } 14354e3f125e184f96ae72f2c44d16cafe0d44158283Dan Gohman 14366b0e3f890779b7fc912bec8d40a9590e44742737Chris Lattner // Okay, there is no really great place to put this block. If, however, 14376b0e3f890779b7fc912bec8d40a9590e44742737Chris Lattner // the block before this one would be a fall-through if this block were 14386b0e3f890779b7fc912bec8d40a9590e44742737Chris Lattner // removed, move this block to the end of the function. 14392210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman MachineBasicBlock *PrevTBB, *PrevFBB; 14402210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman SmallVector<MachineOperand, 4> PrevCond; 1441d194498d2669e28cd8e85b0ceb7c69a7ec66da13Dan Gohman if (FallThrough != MF.end() && 14422210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman !TII->AnalyzeBranch(PrevBB, PrevTBB, PrevFBB, PrevCond, true) && 14436b0e3f890779b7fc912bec8d40a9590e44742737Chris Lattner PrevBB.isSuccessor(FallThrough)) { 1444d194498d2669e28cd8e85b0ceb7c69a7ec66da13Dan Gohman MBB->moveAfter(--MF.end()); 14456b0e3f890779b7fc912bec8d40a9590e44742737Chris Lattner MadeChange = true; 1446030a0a0cdb38924e55773a8e0b5fe7347aa664aaEvan Cheng return MadeChange; 14476b0e3f890779b7fc912bec8d40a9590e44742737Chris Lattner } 14487d09784d3fc652131a2afbf06a0f2ed893837fb9Chris Lattner } 144921ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner } 1450030a0a0cdb38924e55773a8e0b5fe7347aa664aaEvan Cheng 1451030a0a0cdb38924e55773a8e0b5fe7347aa664aaEvan Cheng return MadeChange; 145221ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner} 1453