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" 2680799fbe3c048cc78aba59c389e4b33e936bc190Jakob Stoklund Olesen#include "llvm/CodeGen/MachineRegisterInfo.h" 2769cb9b78f11d505f4351a269fc90e7b77fcda437Dale Johannesen#include "llvm/CodeGen/RegisterScavenging.h" 2821ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner#include "llvm/Target/TargetInstrInfo.h" 2921ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner#include "llvm/Target/TargetMachine.h" 306f0d024a534af18d9e60b3ea757376cd8a3a980eDan Gohman#include "llvm/Target/TargetRegisterInfo.h" 3112143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner#include "llvm/Support/CommandLine.h" 32f10a56a86f8ae32d0493c7de770493d55519b073Chris Lattner#include "llvm/Support/Debug.h" 33c25e7581b9b8088910da31702d4ca21c4734c6d7Torok Edwin#include "llvm/Support/ErrorHandling.h" 343403bcd8f943cb053a7d9bbf8eb8135407699afaBill Wendling#include "llvm/Support/raw_ostream.h" 3580b09fe8bc1d2755ef9a6b03b8862a657db42f06Evan Cheng#include "llvm/ADT/SmallSet.h" 362210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman#include "llvm/ADT/SetVector.h" 3712143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner#include "llvm/ADT/Statistic.h" 38551ccae044b0ff658fe629dd67edd5ffe75d10e8Reid Spencer#include "llvm/ADT/STLExtras.h" 39d41b30def3181bce4bf87e8bde664d15663165d0Jeff Cohen#include <algorithm> 4021ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattnerusing namespace llvm; 4121ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner 42cd3245ac45c595da96bb768a55cddc356dff55feChris LattnerSTATISTIC(NumDeadBlocks, "Number of dead blocks removed"); 43cd3245ac45c595da96bb768a55cddc356dff55feChris LattnerSTATISTIC(NumBranchOpts, "Number of branches optimized"); 44cd3245ac45c595da96bb768a55cddc356dff55feChris LattnerSTATISTIC(NumTailMerge , "Number of block tails merged"); 45cbc988be22bc9411d95215c8b7251b5f85710674Evan ChengSTATISTIC(NumHoist , "Number of times common instructions are hoisted"); 467cd5d3e05ca9573dbac1a01846813037f901480cBob Wilson 474e3f125e184f96ae72f2c44d16cafe0d44158283Dan Gohmanstatic cl::opt<cl::boolOrDefault> FlagEnableTailMerge("enable-tail-merge", 4881da02b553b86868637f27b89c6e919c31ed5b51Dale Johannesen cl::init(cl::BOU_UNSET), cl::Hidden); 497cd5d3e05ca9573dbac1a01846813037f901480cBob Wilson 50844731a7f1909f55935e3514c9e713a62d67662eDan Gohman// Throttle for huge numbers of predecessors (compile speed problems) 51844731a7f1909f55935e3514c9e713a62d67662eDan Gohmanstatic cl::opt<unsigned> 524e3f125e184f96ae72f2c44d16cafe0d44158283Dan GohmanTailMergeThreshold("tail-merge-threshold", 53844731a7f1909f55935e3514c9e713a62d67662eDan Gohman cl::desc("Max number of predecessors to consider tail merging"), 54622addbe49ffdc611adb315fb22756e23fe7b222Dale Johannesen cl::init(150), cl::Hidden); 551a90a5aebe3488dc3feaab60ba16bed1659ba27bDale Johannesen 562210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman// Heuristic for tail merging (and, inversely, tail duplication). 572210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman// TODO: This should be replaced with a target query. 582210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohmanstatic cl::opt<unsigned> 593cbc3120873242d93e469b4635c0bbd09fdb6438Bob WilsonTailMergeSize("tail-merge-size", 602210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman cl::desc("Min number of instructions to consider tail merging"), 612210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman cl::init(3), cl::Hidden); 62794fd75c67a2cdc128d67342c6d88a504d186896Devang Patel 6372b2990a7495b9df89e151eb711c1e7abdd5f2e5Dan Gohmannamespace { 6472b2990a7495b9df89e151eb711c1e7abdd5f2e5Dan Gohman /// BranchFolderPass - Wrap branch folder in a machine function pass. 6561f1e3db43e556f495b6b9360d2f550291f78471Andrew Trick class BranchFolderPass : public MachineFunctionPass { 6672b2990a7495b9df89e151eb711c1e7abdd5f2e5Dan Gohman public: 6772b2990a7495b9df89e151eb711c1e7abdd5f2e5Dan Gohman static char ID; 6861f1e3db43e556f495b6b9360d2f550291f78471Andrew Trick explicit BranchFolderPass(): MachineFunctionPass(ID) {} 6972b2990a7495b9df89e151eb711c1e7abdd5f2e5Dan Gohman 7072b2990a7495b9df89e151eb711c1e7abdd5f2e5Dan Gohman virtual bool runOnMachineFunction(MachineFunction &MF); 7161f1e3db43e556f495b6b9360d2f550291f78471Andrew Trick 7261f1e3db43e556f495b6b9360d2f550291f78471Andrew Trick virtual void getAnalysisUsage(AnalysisUsage &AU) const { 7361f1e3db43e556f495b6b9360d2f550291f78471Andrew Trick AU.addRequired<TargetPassConfig>(); 7461f1e3db43e556f495b6b9360d2f550291f78471Andrew Trick MachineFunctionPass::getAnalysisUsage(AU); 7561f1e3db43e556f495b6b9360d2f550291f78471Andrew Trick } 7672b2990a7495b9df89e151eb711c1e7abdd5f2e5Dan Gohman }; 7772b2990a7495b9df89e151eb711c1e7abdd5f2e5Dan Gohman} 7872b2990a7495b9df89e151eb711c1e7abdd5f2e5Dan Gohman 79030a0a0cdb38924e55773a8e0b5fe7347aa664aaEvan Chengchar BranchFolderPass::ID = 0; 8061f1e3db43e556f495b6b9360d2f550291f78471Andrew Trickchar &llvm::BranchFolderPassID = BranchFolderPass::ID; 8121ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner 8261f1e3db43e556f495b6b9360d2f550291f78471Andrew TrickINITIALIZE_PASS(BranchFolderPass, "branch-folder", 8361f1e3db43e556f495b6b9360d2f550291f78471Andrew Trick "Control Flow Optimizer", false, false) 84030a0a0cdb38924e55773a8e0b5fe7347aa664aaEvan Cheng 85030a0a0cdb38924e55773a8e0b5fe7347aa664aaEvan Chengbool BranchFolderPass::runOnMachineFunction(MachineFunction &MF) { 8661f1e3db43e556f495b6b9360d2f550291f78471Andrew Trick TargetPassConfig *PassConfig = &getAnalysis<TargetPassConfig>(); 8761f1e3db43e556f495b6b9360d2f550291f78471Andrew Trick BranchFolder Folder(PassConfig->getEnableTailMerge(), /*CommonHoist=*/true); 8861f1e3db43e556f495b6b9360d2f550291f78471Andrew Trick return Folder.OptimizeFunction(MF, 8961f1e3db43e556f495b6b9360d2f550291f78471Andrew Trick MF.getTarget().getInstrInfo(), 9061f1e3db43e556f495b6b9360d2f550291f78471Andrew Trick MF.getTarget().getRegisterInfo(), 9161f1e3db43e556f495b6b9360d2f550291f78471Andrew Trick getAnalysisIfAvailable<MachineModuleInfo>()); 92030a0a0cdb38924e55773a8e0b5fe7347aa664aaEvan Cheng} 93030a0a0cdb38924e55773a8e0b5fe7347aa664aaEvan Cheng 94030a0a0cdb38924e55773a8e0b5fe7347aa664aaEvan Cheng 95cbc988be22bc9411d95215c8b7251b5f85710674Evan ChengBranchFolder::BranchFolder(bool defaultEnableTailMerge, bool CommonHoist) { 96030a0a0cdb38924e55773a8e0b5fe7347aa664aaEvan Cheng switch (FlagEnableTailMerge) { 97030a0a0cdb38924e55773a8e0b5fe7347aa664aaEvan Cheng case cl::BOU_UNSET: EnableTailMerge = defaultEnableTailMerge; break; 98030a0a0cdb38924e55773a8e0b5fe7347aa664aaEvan Cheng case cl::BOU_TRUE: EnableTailMerge = true; break; 99030a0a0cdb38924e55773a8e0b5fe7347aa664aaEvan Cheng case cl::BOU_FALSE: EnableTailMerge = false; break; 100030a0a0cdb38924e55773a8e0b5fe7347aa664aaEvan Cheng } 101cbc988be22bc9411d95215c8b7251b5f85710674Evan Cheng 102cbc988be22bc9411d95215c8b7251b5f85710674Evan Cheng EnableHoistCommonCode = CommonHoist; 103b3c27428969b3cc52ab8493e91b5dd1465325fedEvan Cheng} 10421ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner 105c50ffcb7fcb7c1109fee2406e8f74d096f755f47Chris Lattner/// RemoveDeadBlock - Remove the specified dead machine basic block from the 106c50ffcb7fcb7c1109fee2406e8f74d096f755f47Chris Lattner/// function, updating the CFG. 107683747abb81a7b7711ad6cb5abf5a4227f7ab691Chris Lattnervoid BranchFolder::RemoveDeadBlock(MachineBasicBlock *MBB) { 108033c9715d9bf7ce59ad2e466bf0720811b34da08Jim Laskey assert(MBB->pred_empty() && "MBB must be dead!"); 109465e2b950d61c870fb3120c80191973e8282a3efDavid Greene DEBUG(dbgs() << "\nRemoving MBB: " << *MBB); 1104e3f125e184f96ae72f2c44d16cafe0d44158283Dan Gohman 111c50ffcb7fcb7c1109fee2406e8f74d096f755f47Chris Lattner MachineFunction *MF = MBB->getParent(); 112c50ffcb7fcb7c1109fee2406e8f74d096f755f47Chris Lattner // drop all successors. 113c50ffcb7fcb7c1109fee2406e8f74d096f755f47Chris Lattner while (!MBB->succ_empty()) 114c50ffcb7fcb7c1109fee2406e8f74d096f755f47Chris Lattner MBB->removeSuccessor(MBB->succ_end()-1); 1154e3f125e184f96ae72f2c44d16cafe0d44158283Dan Gohman 116f924dea8ddb74df8d591f8fdc409fc5b8b5e10d4Rafael Espindola // Avoid matching if this pointer gets reused. 117f924dea8ddb74df8d591f8fdc409fc5b8b5e10d4Rafael Espindola TriedMerging.erase(MBB); 118f924dea8ddb74df8d591f8fdc409fc5b8b5e10d4Rafael Espindola 119c50ffcb7fcb7c1109fee2406e8f74d096f755f47Chris Lattner // Remove the block. 1208e5f2c6f65841542e2a7092553fe42a00048e4c7Dan Gohman MF->erase(MBB); 121c50ffcb7fcb7c1109fee2406e8f74d096f755f47Chris Lattner} 122c50ffcb7fcb7c1109fee2406e8f74d096f755f47Chris Lattner 12380b09fe8bc1d2755ef9a6b03b8862a657db42f06Evan Cheng/// OptimizeImpDefsBlock - If a basic block is just a bunch of implicit_def 12480b09fe8bc1d2755ef9a6b03b8862a657db42f06Evan Cheng/// followed by terminators, and if the implicitly defined registers are not 12580b09fe8bc1d2755ef9a6b03b8862a657db42f06Evan Cheng/// used by the terminators, remove those implicit_def's. e.g. 12680b09fe8bc1d2755ef9a6b03b8862a657db42f06Evan Cheng/// BB1: 12780b09fe8bc1d2755ef9a6b03b8862a657db42f06Evan Cheng/// r0 = implicit_def 12880b09fe8bc1d2755ef9a6b03b8862a657db42f06Evan Cheng/// r1 = implicit_def 12980b09fe8bc1d2755ef9a6b03b8862a657db42f06Evan Cheng/// br 13080b09fe8bc1d2755ef9a6b03b8862a657db42f06Evan Cheng/// This block can be optimized away later if the implicit instructions are 13180b09fe8bc1d2755ef9a6b03b8862a657db42f06Evan Cheng/// removed. 13280b09fe8bc1d2755ef9a6b03b8862a657db42f06Evan Chengbool BranchFolder::OptimizeImpDefsBlock(MachineBasicBlock *MBB) { 13380b09fe8bc1d2755ef9a6b03b8862a657db42f06Evan Cheng SmallSet<unsigned, 4> ImpDefRegs; 13480b09fe8bc1d2755ef9a6b03b8862a657db42f06Evan Cheng MachineBasicBlock::iterator I = MBB->begin(); 13580b09fe8bc1d2755ef9a6b03b8862a657db42f06Evan Cheng while (I != MBB->end()) { 136518bb53485df640d7b7e3f6b0544099020c42aa7Chris Lattner if (!I->isImplicitDef()) 13780b09fe8bc1d2755ef9a6b03b8862a657db42f06Evan Cheng break; 13880b09fe8bc1d2755ef9a6b03b8862a657db42f06Evan Cheng unsigned Reg = I->getOperand(0).getReg(); 13980b09fe8bc1d2755ef9a6b03b8862a657db42f06Evan Cheng ImpDefRegs.insert(Reg); 140396618b43a85e12d290a90b181c6af5d7c0c5f11Jakob Stoklund Olesen for (MCSubRegIterator SubRegs(Reg, TRI); SubRegs.isValid(); ++SubRegs) 141396618b43a85e12d290a90b181c6af5d7c0c5f11Jakob Stoklund Olesen ImpDefRegs.insert(*SubRegs); 14280b09fe8bc1d2755ef9a6b03b8862a657db42f06Evan Cheng ++I; 14380b09fe8bc1d2755ef9a6b03b8862a657db42f06Evan Cheng } 14480b09fe8bc1d2755ef9a6b03b8862a657db42f06Evan Cheng if (ImpDefRegs.empty()) 14580b09fe8bc1d2755ef9a6b03b8862a657db42f06Evan Cheng return false; 14680b09fe8bc1d2755ef9a6b03b8862a657db42f06Evan Cheng 14780b09fe8bc1d2755ef9a6b03b8862a657db42f06Evan Cheng MachineBasicBlock::iterator FirstTerm = I; 14880b09fe8bc1d2755ef9a6b03b8862a657db42f06Evan Cheng while (I != MBB->end()) { 14980b09fe8bc1d2755ef9a6b03b8862a657db42f06Evan Cheng if (!TII->isUnpredicatedTerminator(I)) 15080b09fe8bc1d2755ef9a6b03b8862a657db42f06Evan Cheng return false; 15180b09fe8bc1d2755ef9a6b03b8862a657db42f06Evan Cheng // See if it uses any of the implicitly defined registers. 15280b09fe8bc1d2755ef9a6b03b8862a657db42f06Evan Cheng for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i) { 15380b09fe8bc1d2755ef9a6b03b8862a657db42f06Evan Cheng MachineOperand &MO = I->getOperand(i); 154d735b8019b0f297d7c14b55adcd887af24d8e602Dan Gohman if (!MO.isReg() || !MO.isUse()) 15580b09fe8bc1d2755ef9a6b03b8862a657db42f06Evan Cheng continue; 15680b09fe8bc1d2755ef9a6b03b8862a657db42f06Evan Cheng unsigned Reg = MO.getReg(); 15780b09fe8bc1d2755ef9a6b03b8862a657db42f06Evan Cheng if (ImpDefRegs.count(Reg)) 15880b09fe8bc1d2755ef9a6b03b8862a657db42f06Evan Cheng return false; 15980b09fe8bc1d2755ef9a6b03b8862a657db42f06Evan Cheng } 16080b09fe8bc1d2755ef9a6b03b8862a657db42f06Evan Cheng ++I; 16180b09fe8bc1d2755ef9a6b03b8862a657db42f06Evan Cheng } 16280b09fe8bc1d2755ef9a6b03b8862a657db42f06Evan Cheng 16380b09fe8bc1d2755ef9a6b03b8862a657db42f06Evan Cheng I = MBB->begin(); 16480b09fe8bc1d2755ef9a6b03b8862a657db42f06Evan Cheng while (I != FirstTerm) { 16580b09fe8bc1d2755ef9a6b03b8862a657db42f06Evan Cheng MachineInstr *ImpDefMI = &*I; 16680b09fe8bc1d2755ef9a6b03b8862a657db42f06Evan Cheng ++I; 16780b09fe8bc1d2755ef9a6b03b8862a657db42f06Evan Cheng MBB->erase(ImpDefMI); 16880b09fe8bc1d2755ef9a6b03b8862a657db42f06Evan Cheng } 16980b09fe8bc1d2755ef9a6b03b8862a657db42f06Evan Cheng 17080b09fe8bc1d2755ef9a6b03b8862a657db42f06Evan Cheng return true; 17180b09fe8bc1d2755ef9a6b03b8862a657db42f06Evan Cheng} 17280b09fe8bc1d2755ef9a6b03b8862a657db42f06Evan Cheng 173030a0a0cdb38924e55773a8e0b5fe7347aa664aaEvan Cheng/// OptimizeFunction - Perhaps branch folding, tail merging and other 174030a0a0cdb38924e55773a8e0b5fe7347aa664aaEvan Cheng/// CFG optimizations on the given function. 175030a0a0cdb38924e55773a8e0b5fe7347aa664aaEvan Chengbool BranchFolder::OptimizeFunction(MachineFunction &MF, 176030a0a0cdb38924e55773a8e0b5fe7347aa664aaEvan Cheng const TargetInstrInfo *tii, 177030a0a0cdb38924e55773a8e0b5fe7347aa664aaEvan Cheng const TargetRegisterInfo *tri, 178030a0a0cdb38924e55773a8e0b5fe7347aa664aaEvan Cheng MachineModuleInfo *mmi) { 179030a0a0cdb38924e55773a8e0b5fe7347aa664aaEvan Cheng if (!tii) return false; 180030a0a0cdb38924e55773a8e0b5fe7347aa664aaEvan Cheng 181f924dea8ddb74df8d591f8fdc409fc5b8b5e10d4Rafael Espindola TriedMerging.clear(); 182f924dea8ddb74df8d591f8fdc409fc5b8b5e10d4Rafael Espindola 183030a0a0cdb38924e55773a8e0b5fe7347aa664aaEvan Cheng TII = tii; 184030a0a0cdb38924e55773a8e0b5fe7347aa664aaEvan Cheng TRI = tri; 185030a0a0cdb38924e55773a8e0b5fe7347aa664aaEvan Cheng MMI = mmi; 18680799fbe3c048cc78aba59c389e4b33e936bc190Jakob Stoklund Olesen RS = NULL; 18780799fbe3c048cc78aba59c389e4b33e936bc190Jakob Stoklund Olesen 18880799fbe3c048cc78aba59c389e4b33e936bc190Jakob Stoklund Olesen // Use a RegScavenger to help update liveness when required. 18980799fbe3c048cc78aba59c389e4b33e936bc190Jakob Stoklund Olesen MachineRegisterInfo &MRI = MF.getRegInfo(); 1906a8c7bf8e72338e55f0f9583e1828f62da165d4aPreston Gurd if (MRI.tracksLiveness() && TRI->trackLivenessAfterRegAlloc(MF)) 19180799fbe3c048cc78aba59c389e4b33e936bc190Jakob Stoklund Olesen RS = new RegScavenger(); 19280799fbe3c048cc78aba59c389e4b33e936bc190Jakob Stoklund Olesen else 19380799fbe3c048cc78aba59c389e4b33e936bc190Jakob Stoklund Olesen MRI.invalidateLiveness(); 19480b09fe8bc1d2755ef9a6b03b8862a657db42f06Evan Cheng 19514ba0cc42959a3fcc9b6781aea614b01877fb55fDale Johannesen // Fix CFG. The later algorithms expect it to be right. 196030a0a0cdb38924e55773a8e0b5fe7347aa664aaEvan Cheng bool MadeChange = false; 19714ba0cc42959a3fcc9b6781aea614b01877fb55fDale Johannesen for (MachineFunction::iterator I = MF.begin(), E = MF.end(); I != E; I++) { 19814ba0cc42959a3fcc9b6781aea614b01877fb55fDale Johannesen MachineBasicBlock *MBB = I, *TBB = 0, *FBB = 0; 19944eb65cf58e3ab9b5621ce72256d1621a18aeed7Owen Anderson SmallVector<MachineOperand, 4> Cond; 200dc54d317e7a381ef8e4aca80d54ad1466bb85ddaEvan Cheng if (!TII->AnalyzeBranch(*MBB, TBB, FBB, Cond, true)) 201030a0a0cdb38924e55773a8e0b5fe7347aa664aaEvan Cheng MadeChange |= MBB->CorrectExtraCFGEdges(TBB, FBB, !Cond.empty()); 202030a0a0cdb38924e55773a8e0b5fe7347aa664aaEvan Cheng MadeChange |= OptimizeImpDefsBlock(MBB); 20314ba0cc42959a3fcc9b6781aea614b01877fb55fDale Johannesen } 20414ba0cc42959a3fcc9b6781aea614b01877fb55fDale Johannesen 20512143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner bool MadeChangeThisIteration = true; 20612143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner while (MadeChangeThisIteration) { 207cbc988be22bc9411d95215c8b7251b5f85710674Evan Cheng MadeChangeThisIteration = TailMergeBlocks(MF); 208cbc988be22bc9411d95215c8b7251b5f85710674Evan Cheng MadeChangeThisIteration |= OptimizeBranches(MF); 209cbc988be22bc9411d95215c8b7251b5f85710674Evan Cheng if (EnableHoistCommonCode) 210cbc988be22bc9411d95215c8b7251b5f85710674Evan Cheng MadeChangeThisIteration |= HoistCommonCode(MF); 211030a0a0cdb38924e55773a8e0b5fe7347aa664aaEvan Cheng MadeChange |= MadeChangeThisIteration; 21212143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner } 21312143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner 21480d23705e6df49a41298fd345be6f8a8d72f4fd0Bob Wilson // See if any jump tables have become dead as the code generator 2156acfe12dd6d52c801f78c240528b7cb42fa91159Chris Lattner // did its thing. 2166acfe12dd6d52c801f78c240528b7cb42fa91159Chris Lattner MachineJumpTableInfo *JTI = MF.getJumpTableInfo(); 217071c62fad0b25ad4131e7f984173a796c1e63f61Chris Lattner if (JTI == 0) { 218071c62fad0b25ad4131e7f984173a796c1e63f61Chris Lattner delete RS; 219071c62fad0b25ad4131e7f984173a796c1e63f61Chris Lattner return MadeChange; 220071c62fad0b25ad4131e7f984173a796c1e63f61Chris Lattner } 2211df91b0e54bc62f8fc7a06a4f75220e40aa2dfe0Andrew Trick 22280d23705e6df49a41298fd345be6f8a8d72f4fd0Bob Wilson // Walk the function to find jump tables that are live. 22380d23705e6df49a41298fd345be6f8a8d72f4fd0Bob Wilson BitVector JTIsLive(JTI->getJumpTables().size()); 224071c62fad0b25ad4131e7f984173a796c1e63f61Chris Lattner for (MachineFunction::iterator BB = MF.begin(), E = MF.end(); 225071c62fad0b25ad4131e7f984173a796c1e63f61Chris Lattner BB != E; ++BB) { 226071c62fad0b25ad4131e7f984173a796c1e63f61Chris Lattner for (MachineBasicBlock::iterator I = BB->begin(), E = BB->end(); 227071c62fad0b25ad4131e7f984173a796c1e63f61Chris Lattner I != E; ++I) 228071c62fad0b25ad4131e7f984173a796c1e63f61Chris Lattner for (unsigned op = 0, e = I->getNumOperands(); op != e; ++op) { 229071c62fad0b25ad4131e7f984173a796c1e63f61Chris Lattner MachineOperand &Op = I->getOperand(op); 230071c62fad0b25ad4131e7f984173a796c1e63f61Chris Lattner if (!Op.isJTI()) continue; 231071c62fad0b25ad4131e7f984173a796c1e63f61Chris Lattner 232071c62fad0b25ad4131e7f984173a796c1e63f61Chris Lattner // Remember that this JT is live. 23380d23705e6df49a41298fd345be6f8a8d72f4fd0Bob Wilson JTIsLive.set(Op.getIndex()); 2346acfe12dd6d52c801f78c240528b7cb42fa91159Chris Lattner } 2356acfe12dd6d52c801f78c240528b7cb42fa91159Chris Lattner } 236030a0a0cdb38924e55773a8e0b5fe7347aa664aaEvan Cheng 23780d23705e6df49a41298fd345be6f8a8d72f4fd0Bob Wilson // Finally, remove dead jump tables. This happens when the 23880d23705e6df49a41298fd345be6f8a8d72f4fd0Bob Wilson // indirect jump was unreachable (and thus deleted). 239071c62fad0b25ad4131e7f984173a796c1e63f61Chris Lattner for (unsigned i = 0, e = JTIsLive.size(); i != e; ++i) 240071c62fad0b25ad4131e7f984173a796c1e63f61Chris Lattner if (!JTIsLive.test(i)) { 241071c62fad0b25ad4131e7f984173a796c1e63f61Chris Lattner JTI->RemoveJumpTable(i); 242071c62fad0b25ad4131e7f984173a796c1e63f61Chris Lattner MadeChange = true; 243071c62fad0b25ad4131e7f984173a796c1e63f61Chris Lattner } 244071c62fad0b25ad4131e7f984173a796c1e63f61Chris Lattner 24569cb9b78f11d505f4351a269fc90e7b77fcda437Dale Johannesen delete RS; 246030a0a0cdb38924e55773a8e0b5fe7347aa664aaEvan Cheng return MadeChange; 24712143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner} 24812143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner 24912143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner//===----------------------------------------------------------------------===// 25012143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner// Tail Merging of Blocks 25112143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner//===----------------------------------------------------------------------===// 25212143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner 25312143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner/// HashMachineInstr - Compute a hash value for MI and its operands. 25412143054aa6d120f029d268a5154bf2ecd0f707fChris Lattnerstatic unsigned HashMachineInstr(const MachineInstr *MI) { 25512143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner unsigned Hash = MI->getOpcode(); 25612143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 25712143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner const MachineOperand &Op = MI->getOperand(i); 2584e3f125e184f96ae72f2c44d16cafe0d44158283Dan Gohman 25912143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner // Merge in bits from the operand if easy. 26012143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner unsigned OperandHash = 0; 26112143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner switch (Op.getType()) { 26212143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner case MachineOperand::MO_Register: OperandHash = Op.getReg(); break; 26312143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner case MachineOperand::MO_Immediate: OperandHash = Op.getImm(); break; 26412143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner case MachineOperand::MO_MachineBasicBlock: 2658aa797aa51cd4ea1ec6f46f4891a6897944b75b2Chris Lattner OperandHash = Op.getMBB()->getNumber(); 26612143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner break; 2678aa797aa51cd4ea1ec6f46f4891a6897944b75b2Chris Lattner case MachineOperand::MO_FrameIndex: 26812143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner case MachineOperand::MO_ConstantPoolIndex: 26912143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner case MachineOperand::MO_JumpTableIndex: 2708aa797aa51cd4ea1ec6f46f4891a6897944b75b2Chris Lattner OperandHash = Op.getIndex(); 27112143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner break; 27212143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner case MachineOperand::MO_GlobalAddress: 27312143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner case MachineOperand::MO_ExternalSymbol: 27412143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner // Global address / external symbol are too hard, don't bother, but do 27512143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner // pull in the offset. 27612143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner OperandHash = Op.getOffset(); 27712143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner break; 27812143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner default: break; 27912143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner } 2804e3f125e184f96ae72f2c44d16cafe0d44158283Dan Gohman 28112143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner Hash += ((OperandHash << 3) | Op.getType()) << (i&31); 28212143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner } 28312143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner return Hash; 28412143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner} 28512143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner 28630fc5bbfd1047c666bfd653fefb74ffdc6e966f5Dan Gohman/// HashEndOfMBB - Hash the last instruction in the MBB. 28730fc5bbfd1047c666bfd653fefb74ffdc6e966f5Dan Gohmanstatic unsigned HashEndOfMBB(const MachineBasicBlock *MBB) { 28812143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner MachineBasicBlock::const_iterator I = MBB->end(); 28912143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner if (I == MBB->begin()) 29012143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner return 0; // Empty MBB. 2914e3f125e184f96ae72f2c44d16cafe0d44158283Dan Gohman 29212143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner --I; 29384839daa595968286acd25644820c644867f0c52Dale Johannesen // Skip debug info so it will not affect codegen. 29484839daa595968286acd25644820c644867f0c52Dale Johannesen while (I->isDebugValue()) { 29584839daa595968286acd25644820c644867f0c52Dale Johannesen if (I==MBB->begin()) 29684839daa595968286acd25644820c644867f0c52Dale Johannesen return 0; // MBB empty except for debug info. 29784839daa595968286acd25644820c644867f0c52Dale Johannesen --I; 29884839daa595968286acd25644820c644867f0c52Dale Johannesen } 2994e3f125e184f96ae72f2c44d16cafe0d44158283Dan Gohman 30030fc5bbfd1047c666bfd653fefb74ffdc6e966f5Dan Gohman return HashMachineInstr(I); 30112143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner} 30212143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner 30312143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner/// ComputeCommonTailLength - Given two machine basic blocks, compute the number 30412143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner/// of instructions they actually have in common together at their end. Return 30512143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner/// iterators for the first shared instruction in each block. 30612143054aa6d120f029d268a5154bf2ecd0f707fChris Lattnerstatic unsigned ComputeCommonTailLength(MachineBasicBlock *MBB1, 30712143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner MachineBasicBlock *MBB2, 30812143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner MachineBasicBlock::iterator &I1, 30912143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner MachineBasicBlock::iterator &I2) { 31012143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner I1 = MBB1->end(); 31112143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner I2 = MBB2->end(); 3124e3f125e184f96ae72f2c44d16cafe0d44158283Dan Gohman 31312143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner unsigned TailLen = 0; 31412143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner while (I1 != MBB1->begin() && I2 != MBB2->begin()) { 31512143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner --I1; --I2; 31684839daa595968286acd25644820c644867f0c52Dale Johannesen // Skip debugging pseudos; necessary to avoid changing the code. 31784839daa595968286acd25644820c644867f0c52Dale Johannesen while (I1->isDebugValue()) { 318c5cf227f3dac755508928b9dee8ac6a45dcb4e4fDale Johannesen if (I1==MBB1->begin()) { 319c5cf227f3dac755508928b9dee8ac6a45dcb4e4fDale Johannesen while (I2->isDebugValue()) { 320c5cf227f3dac755508928b9dee8ac6a45dcb4e4fDale Johannesen if (I2==MBB2->begin()) 321c5cf227f3dac755508928b9dee8ac6a45dcb4e4fDale Johannesen // I1==DBG at begin; I2==DBG at begin 322c5cf227f3dac755508928b9dee8ac6a45dcb4e4fDale Johannesen return TailLen; 323c5cf227f3dac755508928b9dee8ac6a45dcb4e4fDale Johannesen --I2; 324c5cf227f3dac755508928b9dee8ac6a45dcb4e4fDale Johannesen } 325c5cf227f3dac755508928b9dee8ac6a45dcb4e4fDale Johannesen ++I2; 326c5cf227f3dac755508928b9dee8ac6a45dcb4e4fDale Johannesen // I1==DBG at begin; I2==non-DBG, or first of DBGs not at begin 32784839daa595968286acd25644820c644867f0c52Dale Johannesen return TailLen; 328c5cf227f3dac755508928b9dee8ac6a45dcb4e4fDale Johannesen } 32984839daa595968286acd25644820c644867f0c52Dale Johannesen --I1; 33084839daa595968286acd25644820c644867f0c52Dale Johannesen } 331c5cf227f3dac755508928b9dee8ac6a45dcb4e4fDale Johannesen // I1==first (untested) non-DBG preceding known match 33284839daa595968286acd25644820c644867f0c52Dale Johannesen while (I2->isDebugValue()) { 333c5cf227f3dac755508928b9dee8ac6a45dcb4e4fDale Johannesen if (I2==MBB2->begin()) { 334c5cf227f3dac755508928b9dee8ac6a45dcb4e4fDale Johannesen ++I1; 335c5cf227f3dac755508928b9dee8ac6a45dcb4e4fDale Johannesen // I1==non-DBG, or first of DBGs not at begin; I2==DBG at begin 33684839daa595968286acd25644820c644867f0c52Dale Johannesen return TailLen; 337c5cf227f3dac755508928b9dee8ac6a45dcb4e4fDale Johannesen } 33884839daa595968286acd25644820c644867f0c52Dale Johannesen --I2; 33984839daa595968286acd25644820c644867f0c52Dale Johannesen } 340c5cf227f3dac755508928b9dee8ac6a45dcb4e4fDale Johannesen // I1, I2==first (untested) non-DBGs preceding known match 34184839daa595968286acd25644820c644867f0c52Dale Johannesen if (!I1->isIdenticalTo(I2) || 342da6efc5268958a0668806e989c1c5a1f788543e5Bill Wendling // FIXME: This check is dubious. It's used to get around a problem where 3430713a224234b4596709c7582ebf17a1ccb95c872Bill Wendling // people incorrectly expect inline asm directives to remain in the same 3440713a224234b4596709c7582ebf17a1ccb95c872Bill Wendling // relative order. This is untenable because normal compiler 3450713a224234b4596709c7582ebf17a1ccb95c872Bill Wendling // optimizations (like this one) may reorder and/or merge these 3460713a224234b4596709c7582ebf17a1ccb95c872Bill Wendling // directives. 347518bb53485df640d7b7e3f6b0544099020c42aa7Chris Lattner I1->isInlineAsm()) { 34812143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner ++I1; ++I2; 34912143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner break; 35012143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner } 35112143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner ++TailLen; 35212143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner } 353c5cf227f3dac755508928b9dee8ac6a45dcb4e4fDale Johannesen // Back past possible debugging pseudos at beginning of block. This matters 354c5cf227f3dac755508928b9dee8ac6a45dcb4e4fDale Johannesen // when one block differs from the other only by whether debugging pseudos 355c5cf227f3dac755508928b9dee8ac6a45dcb4e4fDale Johannesen // are present at the beginning. (This way, the various checks later for 356c5cf227f3dac755508928b9dee8ac6a45dcb4e4fDale Johannesen // I1==MBB1->begin() work as expected.) 357c5cf227f3dac755508928b9dee8ac6a45dcb4e4fDale Johannesen if (I1 == MBB1->begin() && I2 != MBB2->begin()) { 358c5cf227f3dac755508928b9dee8ac6a45dcb4e4fDale Johannesen --I2; 359c5cf227f3dac755508928b9dee8ac6a45dcb4e4fDale Johannesen while (I2->isDebugValue()) { 360c5cf227f3dac755508928b9dee8ac6a45dcb4e4fDale Johannesen if (I2 == MBB2->begin()) { 361c5cf227f3dac755508928b9dee8ac6a45dcb4e4fDale Johannesen return TailLen; 362c5cf227f3dac755508928b9dee8ac6a45dcb4e4fDale Johannesen } 363c5cf227f3dac755508928b9dee8ac6a45dcb4e4fDale Johannesen --I2; 364c5cf227f3dac755508928b9dee8ac6a45dcb4e4fDale Johannesen } 365c5cf227f3dac755508928b9dee8ac6a45dcb4e4fDale Johannesen ++I2; 366c5cf227f3dac755508928b9dee8ac6a45dcb4e4fDale Johannesen } 367c5cf227f3dac755508928b9dee8ac6a45dcb4e4fDale Johannesen if (I2 == MBB2->begin() && I1 != MBB1->begin()) { 368c5cf227f3dac755508928b9dee8ac6a45dcb4e4fDale Johannesen --I1; 369c5cf227f3dac755508928b9dee8ac6a45dcb4e4fDale Johannesen while (I1->isDebugValue()) { 370c5cf227f3dac755508928b9dee8ac6a45dcb4e4fDale Johannesen if (I1 == MBB1->begin()) 371c5cf227f3dac755508928b9dee8ac6a45dcb4e4fDale Johannesen return TailLen; 372c5cf227f3dac755508928b9dee8ac6a45dcb4e4fDale Johannesen --I1; 373c5cf227f3dac755508928b9dee8ac6a45dcb4e4fDale Johannesen } 374c5cf227f3dac755508928b9dee8ac6a45dcb4e4fDale Johannesen ++I1; 375c5cf227f3dac755508928b9dee8ac6a45dcb4e4fDale Johannesen } 37612143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner return TailLen; 37712143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner} 37812143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner 379a38cfb2fceb266bd78164021c08284dc59a1e8a3Eli Friedmanvoid BranchFolder::MaintainLiveIns(MachineBasicBlock *CurMBB, 380a38cfb2fceb266bd78164021c08284dc59a1e8a3Eli Friedman MachineBasicBlock *NewMBB) { 38170017fb01bba634649f7f3b1dee33c6cda0721d0Evan Cheng if (RS) { 38270017fb01bba634649f7f3b1dee33c6cda0721d0Evan Cheng RS->enterBasicBlock(CurMBB); 38370017fb01bba634649f7f3b1dee33c6cda0721d0Evan Cheng if (!CurMBB->empty()) 38470017fb01bba634649f7f3b1dee33c6cda0721d0Evan Cheng RS->forward(prior(CurMBB->end())); 38570017fb01bba634649f7f3b1dee33c6cda0721d0Evan Cheng BitVector RegsLiveAtExit(TRI->getNumRegs()); 38670017fb01bba634649f7f3b1dee33c6cda0721d0Evan Cheng RS->getRegsUsed(RegsLiveAtExit, false); 38770017fb01bba634649f7f3b1dee33c6cda0721d0Evan Cheng for (unsigned int i = 0, e = TRI->getNumRegs(); i != e; i++) 38870017fb01bba634649f7f3b1dee33c6cda0721d0Evan Cheng if (RegsLiveAtExit[i]) 38970017fb01bba634649f7f3b1dee33c6cda0721d0Evan Cheng NewMBB->addLiveIn(i); 39070017fb01bba634649f7f3b1dee33c6cda0721d0Evan Cheng } 391a38cfb2fceb266bd78164021c08284dc59a1e8a3Eli Friedman} 392a38cfb2fceb266bd78164021c08284dc59a1e8a3Eli Friedman 39312143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner/// ReplaceTailWithBranchTo - Delete the instruction OldInst and everything 39486050dc8cc0aaea8c9dfeb89de02cafbd7f48d92Evan Cheng/// after it, replacing it with an unconditional branch to NewDest. 39512143054aa6d120f029d268a5154bf2ecd0f707fChris Lattnervoid BranchFolder::ReplaceTailWithBranchTo(MachineBasicBlock::iterator OldInst, 39612143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner MachineBasicBlock *NewDest) { 397a38cfb2fceb266bd78164021c08284dc59a1e8a3Eli Friedman MachineBasicBlock *CurMBB = OldInst->getParent(); 398a38cfb2fceb266bd78164021c08284dc59a1e8a3Eli Friedman 39986050dc8cc0aaea8c9dfeb89de02cafbd7f48d92Evan Cheng TII->ReplaceTailWithBranchTo(OldInst, NewDest); 400a38cfb2fceb266bd78164021c08284dc59a1e8a3Eli Friedman 401a38cfb2fceb266bd78164021c08284dc59a1e8a3Eli Friedman // For targets that use the register scavenger, we must maintain LiveIns. 402a38cfb2fceb266bd78164021c08284dc59a1e8a3Eli Friedman MaintainLiveIns(CurMBB, NewDest); 403a38cfb2fceb266bd78164021c08284dc59a1e8a3Eli Friedman 40412143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner ++NumTailMerge; 40512143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner} 40612143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner 4071d08d83230338ca5969ff6ae6737a978336538bfChris Lattner/// SplitMBBAt - Given a machine basic block and an iterator into it, split the 4081d08d83230338ca5969ff6ae6737a978336538bfChris Lattner/// MBB so that the part before the iterator falls into the part starting at the 4091d08d83230338ca5969ff6ae6737a978336538bfChris Lattner/// iterator. This returns the new MBB. 4101d08d83230338ca5969ff6ae6737a978336538bfChris LattnerMachineBasicBlock *BranchFolder::SplitMBBAt(MachineBasicBlock &CurMBB, 4111d08d83230338ca5969ff6ae6737a978336538bfChris Lattner MachineBasicBlock::iterator BBI1) { 4124d54e5b2dd4a3d3bed38ff9c7aa57fc66adb5855Evan Cheng if (!TII->isLegalToSplitMBBAt(CurMBB, BBI1)) 4134d54e5b2dd4a3d3bed38ff9c7aa57fc66adb5855Evan Cheng return 0; 4144d54e5b2dd4a3d3bed38ff9c7aa57fc66adb5855Evan Cheng 4158e5f2c6f65841542e2a7092553fe42a00048e4c7Dan Gohman MachineFunction &MF = *CurMBB.getParent(); 4168e5f2c6f65841542e2a7092553fe42a00048e4c7Dan Gohman 4171d08d83230338ca5969ff6ae6737a978336538bfChris Lattner // Create the fall-through block. 4181d08d83230338ca5969ff6ae6737a978336538bfChris Lattner MachineFunction::iterator MBBI = &CurMBB; 4198e5f2c6f65841542e2a7092553fe42a00048e4c7Dan Gohman MachineBasicBlock *NewMBB =MF.CreateMachineBasicBlock(CurMBB.getBasicBlock()); 4208e5f2c6f65841542e2a7092553fe42a00048e4c7Dan Gohman CurMBB.getParent()->insert(++MBBI, NewMBB); 4211d08d83230338ca5969ff6ae6737a978336538bfChris Lattner 4221d08d83230338ca5969ff6ae6737a978336538bfChris Lattner // Move all the successors of this block to the specified block. 42304478e56f736325d3567e7c0efe2bb5c2766c63bDan Gohman NewMBB->transferSuccessors(&CurMBB); 4244e3f125e184f96ae72f2c44d16cafe0d44158283Dan Gohman 4251d08d83230338ca5969ff6ae6737a978336538bfChris Lattner // Add an edge from CurMBB to NewMBB for the fall-through. 4261d08d83230338ca5969ff6ae6737a978336538bfChris Lattner CurMBB.addSuccessor(NewMBB); 4274e3f125e184f96ae72f2c44d16cafe0d44158283Dan Gohman 4281d08d83230338ca5969ff6ae6737a978336538bfChris Lattner // Splice the code over. 4291d08d83230338ca5969ff6ae6737a978336538bfChris Lattner NewMBB->splice(NewMBB->end(), &CurMBB, BBI1, CurMBB.end()); 43069cb9b78f11d505f4351a269fc90e7b77fcda437Dale Johannesen 43169cb9b78f11d505f4351a269fc90e7b77fcda437Dale Johannesen // For targets that use the register scavenger, we must maintain LiveIns. 432a38cfb2fceb266bd78164021c08284dc59a1e8a3Eli Friedman MaintainLiveIns(&CurMBB, NewMBB); 43369cb9b78f11d505f4351a269fc90e7b77fcda437Dale Johannesen 4341d08d83230338ca5969ff6ae6737a978336538bfChris Lattner return NewMBB; 4351d08d83230338ca5969ff6ae6737a978336538bfChris Lattner} 4361d08d83230338ca5969ff6ae6737a978336538bfChris Lattner 437d4bf3c2fd60975b30cd067b59f743a3ea45e45b5Chris Lattner/// EstimateRuntime - Make a rough estimate for how long it will take to run 438d4bf3c2fd60975b30cd067b59f743a3ea45e45b5Chris Lattner/// the specified code. 439d4bf3c2fd60975b30cd067b59f743a3ea45e45b5Chris Lattnerstatic unsigned EstimateRuntime(MachineBasicBlock::iterator I, 44069244300b8a0112efb44b6273ecea4ca6264b8cfChris Lattner MachineBasicBlock::iterator E) { 441d4bf3c2fd60975b30cd067b59f743a3ea45e45b5Chris Lattner unsigned Time = 0; 442d4bf3c2fd60975b30cd067b59f743a3ea45e45b5Chris Lattner for (; I != E; ++I) { 443b0812f114b83a32c4b90a4b553c7177c557558b5Dale Johannesen if (I->isDebugValue()) 444b0812f114b83a32c4b90a4b553c7177c557558b5Dale Johannesen continue; 4455a96b3dad2f634c9081c8b2b6c2575441dc5a2bdEvan Cheng if (I->isCall()) 446d4bf3c2fd60975b30cd067b59f743a3ea45e45b5Chris Lattner Time += 10; 4475a96b3dad2f634c9081c8b2b6c2575441dc5a2bdEvan Cheng else if (I->mayLoad() || I->mayStore()) 448d4bf3c2fd60975b30cd067b59f743a3ea45e45b5Chris Lattner Time += 2; 449d4bf3c2fd60975b30cd067b59f743a3ea45e45b5Chris Lattner else 450d4bf3c2fd60975b30cd067b59f743a3ea45e45b5Chris Lattner ++Time; 451d4bf3c2fd60975b30cd067b59f743a3ea45e45b5Chris Lattner } 452d4bf3c2fd60975b30cd067b59f743a3ea45e45b5Chris Lattner return Time; 453d4bf3c2fd60975b30cd067b59f743a3ea45e45b5Chris Lattner} 454d4bf3c2fd60975b30cd067b59f743a3ea45e45b5Chris Lattner 45576b38fcabeba725e166a2ff72c56fe31d784b229Dale Johannesen// CurMBB needs to add an unconditional branch to SuccMBB (we removed these 45676b38fcabeba725e166a2ff72c56fe31d784b229Dale Johannesen// branches temporarily for tail merging). In the case where CurMBB ends 45776b38fcabeba725e166a2ff72c56fe31d784b229Dale Johannesen// with a conditional branch to the next block, optimize by reversing the 45876b38fcabeba725e166a2ff72c56fe31d784b229Dale Johannesen// test and conditionally branching to SuccMBB instead. 459d34f5d91bc6fdc55085d3c4d509c778d6bcc5f0aBob Wilsonstatic void FixTail(MachineBasicBlock *CurMBB, MachineBasicBlock *SuccBB, 46076b38fcabeba725e166a2ff72c56fe31d784b229Dale Johannesen const TargetInstrInfo *TII) { 46176b38fcabeba725e166a2ff72c56fe31d784b229Dale Johannesen MachineFunction *MF = CurMBB->getParent(); 4627896c9f436a4eda5ec15e882a7505ba482a2fcd0Chris Lattner MachineFunction::iterator I = llvm::next(MachineFunction::iterator(CurMBB)); 46376b38fcabeba725e166a2ff72c56fe31d784b229Dale Johannesen MachineBasicBlock *TBB = 0, *FBB = 0; 46444eb65cf58e3ab9b5621ce72256d1621a18aeed7Owen Anderson SmallVector<MachineOperand, 4> Cond; 4653bf912593301152b65accb9d9c37a95172f1df5aStuart Hastings DebugLoc dl; // FIXME: this is nowhere 46676b38fcabeba725e166a2ff72c56fe31d784b229Dale Johannesen if (I != MF->end() && 467dc54d317e7a381ef8e4aca80d54ad1466bb85ddaEvan Cheng !TII->AnalyzeBranch(*CurMBB, TBB, FBB, Cond, true)) { 46876b38fcabeba725e166a2ff72c56fe31d784b229Dale Johannesen MachineBasicBlock *NextBB = I; 4696b8583cbf1f8a3df5ae859d3da2ca690ff57f91cDale Johannesen if (TBB == NextBB && !Cond.empty() && !FBB) { 47076b38fcabeba725e166a2ff72c56fe31d784b229Dale Johannesen if (!TII->ReverseBranchCondition(Cond)) { 47176b38fcabeba725e166a2ff72c56fe31d784b229Dale Johannesen TII->RemoveBranch(*CurMBB); 4723bf912593301152b65accb9d9c37a95172f1df5aStuart Hastings TII->InsertBranch(*CurMBB, SuccBB, NULL, Cond, dl); 47376b38fcabeba725e166a2ff72c56fe31d784b229Dale Johannesen return; 47476b38fcabeba725e166a2ff72c56fe31d784b229Dale Johannesen } 47576b38fcabeba725e166a2ff72c56fe31d784b229Dale Johannesen } 47676b38fcabeba725e166a2ff72c56fe31d784b229Dale Johannesen } 4773bf912593301152b65accb9d9c37a95172f1df5aStuart Hastings TII->InsertBranch(*CurMBB, SuccBB, NULL, 4783bf912593301152b65accb9d9c37a95172f1df5aStuart Hastings SmallVector<MachineOperand, 0>(), dl); 47976b38fcabeba725e166a2ff72c56fe31d784b229Dale Johannesen} 48076b38fcabeba725e166a2ff72c56fe31d784b229Dale Johannesen 481ffe644ebf4dcc50b314261ddd2d08c841f629349Dan Gohmanbool 482ffe644ebf4dcc50b314261ddd2d08c841f629349Dan GohmanBranchFolder::MergePotentialsElt::operator<(const MergePotentialsElt &o) const { 483ffe644ebf4dcc50b314261ddd2d08c841f629349Dan Gohman if (getHash() < o.getHash()) 484ffe644ebf4dcc50b314261ddd2d08c841f629349Dan Gohman return true; 485ffe644ebf4dcc50b314261ddd2d08c841f629349Dan Gohman else if (getHash() > o.getHash()) 486ffe644ebf4dcc50b314261ddd2d08c841f629349Dan Gohman return false; 487ffe644ebf4dcc50b314261ddd2d08c841f629349Dan Gohman else if (getBlock()->getNumber() < o.getBlock()->getNumber()) 488ffe644ebf4dcc50b314261ddd2d08c841f629349Dan Gohman return true; 489ffe644ebf4dcc50b314261ddd2d08c841f629349Dan Gohman else if (getBlock()->getNumber() > o.getBlock()->getNumber()) 490ffe644ebf4dcc50b314261ddd2d08c841f629349Dan Gohman return false; 491ffe644ebf4dcc50b314261ddd2d08c841f629349Dan Gohman else { 492ffe644ebf4dcc50b314261ddd2d08c841f629349Dan Gohman // _GLIBCXX_DEBUG checks strict weak ordering, which involves comparing 493ffe644ebf4dcc50b314261ddd2d08c841f629349Dan Gohman // an object with itself. 49497b4ac8c844e08ce1c4f4a73b85ba56775a2a6c5Duncan Sands#ifndef _GLIBCXX_DEBUG 495ffe644ebf4dcc50b314261ddd2d08c841f629349Dan Gohman llvm_unreachable("Predecessor appears twice"); 4964d6ccb5f68cd7c6418a209f1fa4dbade569e4493David Blaikie#else 497ffe644ebf4dcc50b314261ddd2d08c841f629349Dan Gohman return false; 4984d6ccb5f68cd7c6418a209f1fa4dbade569e4493David Blaikie#endif 499ffe644ebf4dcc50b314261ddd2d08c841f629349Dan Gohman } 50095ef406e0f2da0197f8b46849319c07e9bea1e55Dale Johannesen} 50195ef406e0f2da0197f8b46849319c07e9bea1e55Dale Johannesen 5022210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman/// CountTerminators - Count the number of terminators in the given 5032210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman/// block and set I to the position of the first non-terminator, if there 5042210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman/// is one, or MBB->end() otherwise. 5052210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohmanstatic unsigned CountTerminators(MachineBasicBlock *MBB, 5062210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman MachineBasicBlock::iterator &I) { 5072210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman I = MBB->end(); 5082210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman unsigned NumTerms = 0; 5092210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman for (;;) { 5102210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman if (I == MBB->begin()) { 5112210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman I = MBB->end(); 5122210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman break; 5132210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman } 5142210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman --I; 5155a96b3dad2f634c9081c8b2b6c2575441dc5a2bdEvan Cheng if (!I->isTerminator()) break; 5162210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman ++NumTerms; 5172210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman } 5182210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman return NumTerms; 5192210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman} 5202210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman 5217b888b8ad07cccec099634bc838eed5da3f336b1Bob Wilson/// ProfitableToMerge - Check if two machine basic blocks have a common tail 5227b888b8ad07cccec099634bc838eed5da3f336b1Bob Wilson/// and decide if it would be profitable to merge those tails. Return the 5237b888b8ad07cccec099634bc838eed5da3f336b1Bob Wilson/// length of the common tail and iterators to the first common instruction 5247b888b8ad07cccec099634bc838eed5da3f336b1Bob Wilson/// in each block. 5257b888b8ad07cccec099634bc838eed5da3f336b1Bob Wilsonstatic bool ProfitableToMerge(MachineBasicBlock *MBB1, 5267b888b8ad07cccec099634bc838eed5da3f336b1Bob Wilson MachineBasicBlock *MBB2, 5277b888b8ad07cccec099634bc838eed5da3f336b1Bob Wilson unsigned minCommonTailLength, 5287b888b8ad07cccec099634bc838eed5da3f336b1Bob Wilson unsigned &CommonTailLen, 5297b888b8ad07cccec099634bc838eed5da3f336b1Bob Wilson MachineBasicBlock::iterator &I1, 5302210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman MachineBasicBlock::iterator &I2, 5312210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman MachineBasicBlock *SuccBB, 5322210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman MachineBasicBlock *PredBB) { 5337b888b8ad07cccec099634bc838eed5da3f336b1Bob Wilson CommonTailLen = ComputeCommonTailLength(MBB1, MBB2, I1, I2); 5347b888b8ad07cccec099634bc838eed5da3f336b1Bob Wilson if (CommonTailLen == 0) 5357b888b8ad07cccec099634bc838eed5da3f336b1Bob Wilson return false; 536cf13af6fdee302c2cc8628ae95b40b2bccfdde4bEvan Cheng DEBUG(dbgs() << "Common tail length of BB#" << MBB1->getNumber() 537cf13af6fdee302c2cc8628ae95b40b2bccfdde4bEvan Cheng << " and BB#" << MBB2->getNumber() << " is " << CommonTailLen 538cf13af6fdee302c2cc8628ae95b40b2bccfdde4bEvan Cheng << '\n'); 5397b888b8ad07cccec099634bc838eed5da3f336b1Bob Wilson 5402210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman // It's almost always profitable to merge any number of non-terminator 5412210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman // instructions with the block that falls through into the common successor. 5422210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman if (MBB1 == PredBB || MBB2 == PredBB) { 5432210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman MachineBasicBlock::iterator I; 5442210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman unsigned NumTerms = CountTerminators(MBB1 == PredBB ? MBB2 : MBB1, I); 5452210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman if (CommonTailLen > NumTerms) 5462210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman return true; 5472210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman } 5482210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman 549ad6af45dc172fe23801771200eabb6a7f764e2cbDan Gohman // If one of the blocks can be completely merged and happens to be in 550ad6af45dc172fe23801771200eabb6a7f764e2cbDan Gohman // a position where the other could fall through into it, merge any number 551ad6af45dc172fe23801771200eabb6a7f764e2cbDan Gohman // of instructions, because it can be done without a branch. 552ad6af45dc172fe23801771200eabb6a7f764e2cbDan Gohman // TODO: If the blocks are not adjacent, move one of them so that they are? 553ad6af45dc172fe23801771200eabb6a7f764e2cbDan Gohman if (MBB1->isLayoutSuccessor(MBB2) && I2 == MBB2->begin()) 554ad6af45dc172fe23801771200eabb6a7f764e2cbDan Gohman return true; 555ad6af45dc172fe23801771200eabb6a7f764e2cbDan Gohman if (MBB2->isLayoutSuccessor(MBB1) && I1 == MBB1->begin()) 556ad6af45dc172fe23801771200eabb6a7f764e2cbDan Gohman return true; 557ad6af45dc172fe23801771200eabb6a7f764e2cbDan Gohman 5582210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman // If both blocks have an unconditional branch temporarily stripped out, 559c4c550c7584b3240bda71d4339ec49c1cf731d55Dan Gohman // count that as an additional common instruction for the following 560c4c550c7584b3240bda71d4339ec49c1cf731d55Dan Gohman // heuristics. 561c4c550c7584b3240bda71d4339ec49c1cf731d55Dan Gohman unsigned EffectiveTailLen = CommonTailLen; 5623cbc3120873242d93e469b4635c0bbd09fdb6438Bob Wilson if (SuccBB && MBB1 != PredBB && MBB2 != PredBB && 5635a96b3dad2f634c9081c8b2b6c2575441dc5a2bdEvan Cheng !MBB1->back().isBarrier() && 5645a96b3dad2f634c9081c8b2b6c2575441dc5a2bdEvan Cheng !MBB2->back().isBarrier()) 565c4c550c7584b3240bda71d4339ec49c1cf731d55Dan Gohman ++EffectiveTailLen; 5662210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman 5672210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman // Check if the common tail is long enough to be worthwhile. 568c4c550c7584b3240bda71d4339ec49c1cf731d55Dan Gohman if (EffectiveTailLen >= minCommonTailLength) 5692210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman return true; 5702210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman 571c4c550c7584b3240bda71d4339ec49c1cf731d55Dan Gohman // If we are optimizing for code size, 2 instructions in common is enough if 572c4c550c7584b3240bda71d4339ec49c1cf731d55Dan Gohman // we don't have to split a block. At worst we will be introducing 1 new 573c4c550c7584b3240bda71d4339ec49c1cf731d55Dan Gohman // branch instruction, which is likely to be smaller than the 2 574c4c550c7584b3240bda71d4339ec49c1cf731d55Dan Gohman // instructions that would be deleted in the merge. 575cf13af6fdee302c2cc8628ae95b40b2bccfdde4bEvan Cheng MachineFunction *MF = MBB1->getParent(); 576c4c550c7584b3240bda71d4339ec49c1cf731d55Dan Gohman if (EffectiveTailLen >= 2 && 577c4c550c7584b3240bda71d4339ec49c1cf731d55Dan Gohman MF->getFunction()->hasFnAttr(Attribute::OptimizeForSize) && 5787b888b8ad07cccec099634bc838eed5da3f336b1Bob Wilson (I1 == MBB1->begin() || I2 == MBB2->begin())) 5797b888b8ad07cccec099634bc838eed5da3f336b1Bob Wilson return true; 5807b888b8ad07cccec099634bc838eed5da3f336b1Bob Wilson 5817b888b8ad07cccec099634bc838eed5da3f336b1Bob Wilson return false; 5827b888b8ad07cccec099634bc838eed5da3f336b1Bob Wilson} 5837b888b8ad07cccec099634bc838eed5da3f336b1Bob Wilson 5846b8583cbf1f8a3df5ae859d3da2ca690ff57f91cDale Johannesen/// ComputeSameTails - Look through all the blocks in MergePotentials that have 5854e3f125e184f96ae72f2c44d16cafe0d44158283Dan Gohman/// hash CurHash (guaranteed to match the last element). Build the vector 5866b8583cbf1f8a3df5ae859d3da2ca690ff57f91cDale Johannesen/// SameTails of all those that have the (same) largest number of instructions 5876b8583cbf1f8a3df5ae859d3da2ca690ff57f91cDale Johannesen/// in common of any pair of these blocks. SameTails entries contain an 5884e3f125e184f96ae72f2c44d16cafe0d44158283Dan Gohman/// iterator into MergePotentials (from which the MachineBasicBlock can be 5894e3f125e184f96ae72f2c44d16cafe0d44158283Dan Gohman/// found) and a MachineBasicBlock::iterator into that MBB indicating the 5906b8583cbf1f8a3df5ae859d3da2ca690ff57f91cDale Johannesen/// instruction where the matching code sequence begins. 5916b8583cbf1f8a3df5ae859d3da2ca690ff57f91cDale Johannesen/// Order of elements in SameTails is the reverse of the order in which 5926b8583cbf1f8a3df5ae859d3da2ca690ff57f91cDale Johannesen/// those blocks appear in MergePotentials (where they are not necessarily 5936b8583cbf1f8a3df5ae859d3da2ca690ff57f91cDale Johannesen/// consecutive). 5944e3f125e184f96ae72f2c44d16cafe0d44158283Dan Gohmanunsigned BranchFolder::ComputeSameTails(unsigned CurHash, 5952210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman unsigned minCommonTailLength, 5962210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman MachineBasicBlock *SuccBB, 5972210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman MachineBasicBlock *PredBB) { 5986b8583cbf1f8a3df5ae859d3da2ca690ff57f91cDale Johannesen unsigned maxCommonTailLength = 0U; 5996b8583cbf1f8a3df5ae859d3da2ca690ff57f91cDale Johannesen SameTails.clear(); 6006b8583cbf1f8a3df5ae859d3da2ca690ff57f91cDale Johannesen MachineBasicBlock::iterator TrialBBI1, TrialBBI2; 6016b8583cbf1f8a3df5ae859d3da2ca690ff57f91cDale Johannesen MPIterator HighestMPIter = prior(MergePotentials.end()); 6026b8583cbf1f8a3df5ae859d3da2ca690ff57f91cDale Johannesen for (MPIterator CurMPIter = prior(MergePotentials.end()), 6034e3f125e184f96ae72f2c44d16cafe0d44158283Dan Gohman B = MergePotentials.begin(); 6048520149db158427339a235a74dd2cc19553a7328Dan Gohman CurMPIter != B && CurMPIter->getHash() == CurHash; 6056b8583cbf1f8a3df5ae859d3da2ca690ff57f91cDale Johannesen --CurMPIter) { 606ffe644ebf4dcc50b314261ddd2d08c841f629349Dan Gohman for (MPIterator I = prior(CurMPIter); I->getHash() == CurHash ; --I) { 6077b888b8ad07cccec099634bc838eed5da3f336b1Bob Wilson unsigned CommonTailLen; 608ffe644ebf4dcc50b314261ddd2d08c841f629349Dan Gohman if (ProfitableToMerge(CurMPIter->getBlock(), I->getBlock(), 609ffe644ebf4dcc50b314261ddd2d08c841f629349Dan Gohman minCommonTailLength, 6102210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman CommonTailLen, TrialBBI1, TrialBBI2, 6112210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman SuccBB, PredBB)) { 6126b8583cbf1f8a3df5ae859d3da2ca690ff57f91cDale Johannesen if (CommonTailLen > maxCommonTailLength) { 6136b8583cbf1f8a3df5ae859d3da2ca690ff57f91cDale Johannesen SameTails.clear(); 6146b8583cbf1f8a3df5ae859d3da2ca690ff57f91cDale Johannesen maxCommonTailLength = CommonTailLen; 6156b8583cbf1f8a3df5ae859d3da2ca690ff57f91cDale Johannesen HighestMPIter = CurMPIter; 616ffe644ebf4dcc50b314261ddd2d08c841f629349Dan Gohman SameTails.push_back(SameTailElt(CurMPIter, TrialBBI1)); 6176b8583cbf1f8a3df5ae859d3da2ca690ff57f91cDale Johannesen } 6186b8583cbf1f8a3df5ae859d3da2ca690ff57f91cDale Johannesen if (HighestMPIter == CurMPIter && 6196b8583cbf1f8a3df5ae859d3da2ca690ff57f91cDale Johannesen CommonTailLen == maxCommonTailLength) 620ffe644ebf4dcc50b314261ddd2d08c841f629349Dan Gohman SameTails.push_back(SameTailElt(I, TrialBBI2)); 6216b8583cbf1f8a3df5ae859d3da2ca690ff57f91cDale Johannesen } 6224e3f125e184f96ae72f2c44d16cafe0d44158283Dan Gohman if (I == B) 6236b8583cbf1f8a3df5ae859d3da2ca690ff57f91cDale Johannesen break; 6246b8583cbf1f8a3df5ae859d3da2ca690ff57f91cDale Johannesen } 6256b8583cbf1f8a3df5ae859d3da2ca690ff57f91cDale Johannesen } 6266b8583cbf1f8a3df5ae859d3da2ca690ff57f91cDale Johannesen return maxCommonTailLength; 6276b8583cbf1f8a3df5ae859d3da2ca690ff57f91cDale Johannesen} 6286b8583cbf1f8a3df5ae859d3da2ca690ff57f91cDale Johannesen 6296b8583cbf1f8a3df5ae859d3da2ca690ff57f91cDale Johannesen/// RemoveBlocksWithHash - Remove all blocks with hash CurHash from 6306b8583cbf1f8a3df5ae859d3da2ca690ff57f91cDale Johannesen/// MergePotentials, restoring branches at ends of blocks as appropriate. 6314e3f125e184f96ae72f2c44d16cafe0d44158283Dan Gohmanvoid BranchFolder::RemoveBlocksWithHash(unsigned CurHash, 632d34f5d91bc6fdc55085d3c4d509c778d6bcc5f0aBob Wilson MachineBasicBlock *SuccBB, 633d34f5d91bc6fdc55085d3c4d509c778d6bcc5f0aBob Wilson MachineBasicBlock *PredBB) { 634679860e31bd7b8f043ba1ccdc5990cb9bafd9055Dale Johannesen MPIterator CurMPIter, B; 6354e3f125e184f96ae72f2c44d16cafe0d44158283Dan Gohman for (CurMPIter = prior(MergePotentials.end()), B = MergePotentials.begin(); 636ffe644ebf4dcc50b314261ddd2d08c841f629349Dan Gohman CurMPIter->getHash() == CurHash; 6376b8583cbf1f8a3df5ae859d3da2ca690ff57f91cDale Johannesen --CurMPIter) { 6386b8583cbf1f8a3df5ae859d3da2ca690ff57f91cDale Johannesen // Put the unconditional branch back, if we need one. 639ffe644ebf4dcc50b314261ddd2d08c841f629349Dan Gohman MachineBasicBlock *CurMBB = CurMPIter->getBlock(); 6406b8583cbf1f8a3df5ae859d3da2ca690ff57f91cDale Johannesen if (SuccBB && CurMBB != PredBB) 6416b8583cbf1f8a3df5ae859d3da2ca690ff57f91cDale Johannesen FixTail(CurMBB, SuccBB, TII); 6424e3f125e184f96ae72f2c44d16cafe0d44158283Dan Gohman if (CurMPIter == B) 6436b8583cbf1f8a3df5ae859d3da2ca690ff57f91cDale Johannesen break; 6446b8583cbf1f8a3df5ae859d3da2ca690ff57f91cDale Johannesen } 645ffe644ebf4dcc50b314261ddd2d08c841f629349Dan Gohman if (CurMPIter->getHash() != CurHash) 646679860e31bd7b8f043ba1ccdc5990cb9bafd9055Dale Johannesen CurMPIter++; 647679860e31bd7b8f043ba1ccdc5990cb9bafd9055Dale Johannesen MergePotentials.erase(CurMPIter, MergePotentials.end()); 6486b8583cbf1f8a3df5ae859d3da2ca690ff57f91cDale Johannesen} 6496b8583cbf1f8a3df5ae859d3da2ca690ff57f91cDale Johannesen 65051b2b9e29e4fa828ffd83d36f548bc44a4007822Dale Johannesen/// CreateCommonTailOnlyBlock - None of the blocks to be tail-merged consist 65151b2b9e29e4fa828ffd83d36f548bc44a4007822Dale Johannesen/// only of the common tail. Create a block that does by splitting one. 6524d54e5b2dd4a3d3bed38ff9c7aa57fc66adb5855Evan Chengbool BranchFolder::CreateCommonTailOnlyBlock(MachineBasicBlock *&PredBB, 6534d54e5b2dd4a3d3bed38ff9c7aa57fc66adb5855Evan Cheng unsigned maxCommonTailLength, 6544d54e5b2dd4a3d3bed38ff9c7aa57fc66adb5855Evan Cheng unsigned &commonTailIndex) { 6554d54e5b2dd4a3d3bed38ff9c7aa57fc66adb5855Evan Cheng commonTailIndex = 0; 65651b2b9e29e4fa828ffd83d36f548bc44a4007822Dale Johannesen unsigned TimeEstimate = ~0U; 6578520149db158427339a235a74dd2cc19553a7328Dan Gohman for (unsigned i = 0, e = SameTails.size(); i != e; ++i) { 65851b2b9e29e4fa828ffd83d36f548bc44a4007822Dale Johannesen // Use PredBB if possible; that doesn't require a new branch. 659ffe644ebf4dcc50b314261ddd2d08c841f629349Dan Gohman if (SameTails[i].getBlock() == PredBB) { 66051b2b9e29e4fa828ffd83d36f548bc44a4007822Dale Johannesen commonTailIndex = i; 66151b2b9e29e4fa828ffd83d36f548bc44a4007822Dale Johannesen break; 66251b2b9e29e4fa828ffd83d36f548bc44a4007822Dale Johannesen } 66351b2b9e29e4fa828ffd83d36f548bc44a4007822Dale Johannesen // Otherwise, make a (fairly bogus) choice based on estimate of 66451b2b9e29e4fa828ffd83d36f548bc44a4007822Dale Johannesen // how long it will take the various blocks to execute. 665ffe644ebf4dcc50b314261ddd2d08c841f629349Dan Gohman unsigned t = EstimateRuntime(SameTails[i].getBlock()->begin(), 666ffe644ebf4dcc50b314261ddd2d08c841f629349Dan Gohman SameTails[i].getTailStartPos()); 6674e3f125e184f96ae72f2c44d16cafe0d44158283Dan Gohman if (t <= TimeEstimate) { 66851b2b9e29e4fa828ffd83d36f548bc44a4007822Dale Johannesen TimeEstimate = t; 66951b2b9e29e4fa828ffd83d36f548bc44a4007822Dale Johannesen commonTailIndex = i; 67051b2b9e29e4fa828ffd83d36f548bc44a4007822Dale Johannesen } 67151b2b9e29e4fa828ffd83d36f548bc44a4007822Dale Johannesen } 67251b2b9e29e4fa828ffd83d36f548bc44a4007822Dale Johannesen 673ffe644ebf4dcc50b314261ddd2d08c841f629349Dan Gohman MachineBasicBlock::iterator BBI = 674ffe644ebf4dcc50b314261ddd2d08c841f629349Dan Gohman SameTails[commonTailIndex].getTailStartPos(); 675ffe644ebf4dcc50b314261ddd2d08c841f629349Dan Gohman MachineBasicBlock *MBB = SameTails[commonTailIndex].getBlock(); 67651b2b9e29e4fa828ffd83d36f548bc44a4007822Dale Johannesen 67784839daa595968286acd25644820c644867f0c52Dale Johannesen // If the common tail includes any debug info we will take it pretty 67884839daa595968286acd25644820c644867f0c52Dale Johannesen // randomly from one of the inputs. Might be better to remove it? 679465e2b950d61c870fb3120c80191973e8282a3efDavid Greene DEBUG(dbgs() << "\nSplitting BB#" << MBB->getNumber() << ", size " 6803403bcd8f943cb053a7d9bbf8eb8135407699afaBill Wendling << maxCommonTailLength); 68151b2b9e29e4fa828ffd83d36f548bc44a4007822Dale Johannesen 68251b2b9e29e4fa828ffd83d36f548bc44a4007822Dale Johannesen MachineBasicBlock *newMBB = SplitMBBAt(*MBB, BBI); 6834d54e5b2dd4a3d3bed38ff9c7aa57fc66adb5855Evan Cheng if (!newMBB) { 6844d54e5b2dd4a3d3bed38ff9c7aa57fc66adb5855Evan Cheng DEBUG(dbgs() << "... failed!"); 6854d54e5b2dd4a3d3bed38ff9c7aa57fc66adb5855Evan Cheng return false; 6864d54e5b2dd4a3d3bed38ff9c7aa57fc66adb5855Evan Cheng } 6874d54e5b2dd4a3d3bed38ff9c7aa57fc66adb5855Evan Cheng 688ffe644ebf4dcc50b314261ddd2d08c841f629349Dan Gohman SameTails[commonTailIndex].setBlock(newMBB); 689ffe644ebf4dcc50b314261ddd2d08c841f629349Dan Gohman SameTails[commonTailIndex].setTailStartPos(newMBB->begin()); 6904e3f125e184f96ae72f2c44d16cafe0d44158283Dan Gohman 69151b2b9e29e4fa828ffd83d36f548bc44a4007822Dale Johannesen // If we split PredBB, newMBB is the new predecessor. 6924e3f125e184f96ae72f2c44d16cafe0d44158283Dan Gohman if (PredBB == MBB) 69351b2b9e29e4fa828ffd83d36f548bc44a4007822Dale Johannesen PredBB = newMBB; 69451b2b9e29e4fa828ffd83d36f548bc44a4007822Dale Johannesen 6954d54e5b2dd4a3d3bed38ff9c7aa57fc66adb5855Evan Cheng return true; 69651b2b9e29e4fa828ffd83d36f548bc44a4007822Dale Johannesen} 69751b2b9e29e4fa828ffd83d36f548bc44a4007822Dale Johannesen 6987d33b4c59b56afb96feea71073c1d9e70c457e28Dale Johannesen// See if any of the blocks in MergePotentials (which all have a common single 6997d33b4c59b56afb96feea71073c1d9e70c457e28Dale Johannesen// successor, or all have no successor) can be tail-merged. If there is a 7007d33b4c59b56afb96feea71073c1d9e70c457e28Dale Johannesen// successor, any blocks in MergePotentials that are not tail-merged and 7017d33b4c59b56afb96feea71073c1d9e70c457e28Dale Johannesen// are not immediately before Succ must have an unconditional branch to 7024e3f125e184f96ae72f2c44d16cafe0d44158283Dan Gohman// Succ added (but the predecessor/successor lists need no adjustment). 7037d33b4c59b56afb96feea71073c1d9e70c457e28Dale Johannesen// The lone predecessor of Succ that falls through into Succ, 7047d33b4c59b56afb96feea71073c1d9e70c457e28Dale Johannesen// if any, is given in PredBB. 7057d33b4c59b56afb96feea71073c1d9e70c457e28Dale Johannesen 7062210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohmanbool BranchFolder::TryTailMergeBlocks(MachineBasicBlock *SuccBB, 707d34f5d91bc6fdc55085d3c4d509c778d6bcc5f0aBob Wilson MachineBasicBlock *PredBB) { 708030a0a0cdb38924e55773a8e0b5fe7347aa664aaEvan Cheng bool MadeChange = false; 709030a0a0cdb38924e55773a8e0b5fe7347aa664aaEvan Cheng 7102210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman // Except for the special cases below, tail-merge if there are at least 7112210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman // this many instructions in common. 7122210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman unsigned minCommonTailLength = TailMergeSize; 7132210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman 714465e2b950d61c870fb3120c80191973e8282a3efDavid Greene DEBUG(dbgs() << "\nTryTailMergeBlocks: "; 7152210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman for (unsigned i = 0, e = MergePotentials.size(); i != e; ++i) 716465e2b950d61c870fb3120c80191973e8282a3efDavid Greene dbgs() << "BB#" << MergePotentials[i].getBlock()->getNumber() 7172210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman << (i == e-1 ? "" : ", "); 718465e2b950d61c870fb3120c80191973e8282a3efDavid Greene dbgs() << "\n"; 7192210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman if (SuccBB) { 720465e2b950d61c870fb3120c80191973e8282a3efDavid Greene dbgs() << " with successor BB#" << SuccBB->getNumber() << '\n'; 7212210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman if (PredBB) 722465e2b950d61c870fb3120c80191973e8282a3efDavid Greene dbgs() << " which has fall-through from BB#" 7232210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman << PredBB->getNumber() << "\n"; 7242210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman } 725465e2b950d61c870fb3120c80191973e8282a3efDavid Greene dbgs() << "Looking for common tails of at least " 7262210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman << minCommonTailLength << " instruction" 7272210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman << (minCommonTailLength == 1 ? "" : "s") << '\n'; 7282210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman ); 7296b8583cbf1f8a3df5ae859d3da2ca690ff57f91cDale Johannesen 73012143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner // Sort by hash value so that blocks with identical end sequences sort 73112143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner // together. 732ffe644ebf4dcc50b314261ddd2d08c841f629349Dan Gohman std::stable_sort(MergePotentials.begin(), MergePotentials.end()); 73312143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner 73412143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner // Walk through equivalence sets looking for actual exact matches. 73512143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner while (MergePotentials.size() > 1) { 736ffe644ebf4dcc50b314261ddd2d08c841f629349Dan Gohman unsigned CurHash = MergePotentials.back().getHash(); 7374e3f125e184f96ae72f2c44d16cafe0d44158283Dan Gohman 7386b8583cbf1f8a3df5ae859d3da2ca690ff57f91cDale Johannesen // Build SameTails, identifying the set of blocks with this hash code 7396b8583cbf1f8a3df5ae859d3da2ca690ff57f91cDale Johannesen // and with the maximum number of instructions in common. 7404e3f125e184f96ae72f2c44d16cafe0d44158283Dan Gohman unsigned maxCommonTailLength = ComputeSameTails(CurHash, 7412210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman minCommonTailLength, 7422210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman SuccBB, PredBB); 7437aea8320340ce867eb4328aeec52cb02c88ef0b3Dale Johannesen 7444e3f125e184f96ae72f2c44d16cafe0d44158283Dan Gohman // If we didn't find any pair that has at least minCommonTailLength 7456ae83faadf715c398e637424a764f6b02f0b6df2Dale Johannesen // instructions in common, remove all blocks with this hash code and retry. 7466ae83faadf715c398e637424a764f6b02f0b6df2Dale Johannesen if (SameTails.empty()) { 7476b8583cbf1f8a3df5ae859d3da2ca690ff57f91cDale Johannesen RemoveBlocksWithHash(CurHash, SuccBB, PredBB); 7487aea8320340ce867eb4328aeec52cb02c88ef0b3Dale Johannesen continue; 7497aea8320340ce867eb4328aeec52cb02c88ef0b3Dale Johannesen } 7501d08d83230338ca5969ff6ae6737a978336538bfChris Lattner 7516ae83faadf715c398e637424a764f6b02f0b6df2Dale Johannesen // If one of the blocks is the entire common tail (and not the entry 75251b2b9e29e4fa828ffd83d36f548bc44a4007822Dale Johannesen // block, which we can't jump to), we can treat all blocks with this same 75351b2b9e29e4fa828ffd83d36f548bc44a4007822Dale Johannesen // tail at once. Use PredBB if that is one of the possibilities, as that 75451b2b9e29e4fa828ffd83d36f548bc44a4007822Dale Johannesen // will not introduce any extra branches. 755ffe644ebf4dcc50b314261ddd2d08c841f629349Dan Gohman MachineBasicBlock *EntryBB = MergePotentials.begin()->getBlock()-> 756ffe644ebf4dcc50b314261ddd2d08c841f629349Dan Gohman getParent()->begin(); 757ffe644ebf4dcc50b314261ddd2d08c841f629349Dan Gohman unsigned commonTailIndex = SameTails.size(); 758ad6af45dc172fe23801771200eabb6a7f764e2cbDan Gohman // If there are two blocks, check to see if one can be made to fall through 759ad6af45dc172fe23801771200eabb6a7f764e2cbDan Gohman // into the other. 760ad6af45dc172fe23801771200eabb6a7f764e2cbDan Gohman if (SameTails.size() == 2 && 761ad6af45dc172fe23801771200eabb6a7f764e2cbDan Gohman SameTails[0].getBlock()->isLayoutSuccessor(SameTails[1].getBlock()) && 762ad6af45dc172fe23801771200eabb6a7f764e2cbDan Gohman SameTails[1].tailIsWholeBlock()) 763ad6af45dc172fe23801771200eabb6a7f764e2cbDan Gohman commonTailIndex = 1; 764ad6af45dc172fe23801771200eabb6a7f764e2cbDan Gohman else if (SameTails.size() == 2 && 765ad6af45dc172fe23801771200eabb6a7f764e2cbDan Gohman SameTails[1].getBlock()->isLayoutSuccessor( 766ad6af45dc172fe23801771200eabb6a7f764e2cbDan Gohman SameTails[0].getBlock()) && 767ad6af45dc172fe23801771200eabb6a7f764e2cbDan Gohman SameTails[0].tailIsWholeBlock()) 768ad6af45dc172fe23801771200eabb6a7f764e2cbDan Gohman commonTailIndex = 0; 769ad6af45dc172fe23801771200eabb6a7f764e2cbDan Gohman else { 770ad6af45dc172fe23801771200eabb6a7f764e2cbDan Gohman // Otherwise just pick one, favoring the fall-through predecessor if 771ad6af45dc172fe23801771200eabb6a7f764e2cbDan Gohman // there is one. 772ad6af45dc172fe23801771200eabb6a7f764e2cbDan Gohman for (unsigned i = 0, e = SameTails.size(); i != e; ++i) { 773ad6af45dc172fe23801771200eabb6a7f764e2cbDan Gohman MachineBasicBlock *MBB = SameTails[i].getBlock(); 774ad6af45dc172fe23801771200eabb6a7f764e2cbDan Gohman if (MBB == EntryBB && SameTails[i].tailIsWholeBlock()) 775ad6af45dc172fe23801771200eabb6a7f764e2cbDan Gohman continue; 776ad6af45dc172fe23801771200eabb6a7f764e2cbDan Gohman if (MBB == PredBB) { 777ad6af45dc172fe23801771200eabb6a7f764e2cbDan Gohman commonTailIndex = i; 778ad6af45dc172fe23801771200eabb6a7f764e2cbDan Gohman break; 779ad6af45dc172fe23801771200eabb6a7f764e2cbDan Gohman } 780ad6af45dc172fe23801771200eabb6a7f764e2cbDan Gohman if (SameTails[i].tailIsWholeBlock()) 781ad6af45dc172fe23801771200eabb6a7f764e2cbDan Gohman commonTailIndex = i; 7826ae83faadf715c398e637424a764f6b02f0b6df2Dale Johannesen } 7836ae83faadf715c398e637424a764f6b02f0b6df2Dale Johannesen } 7846ae83faadf715c398e637424a764f6b02f0b6df2Dale Johannesen 7852210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman if (commonTailIndex == SameTails.size() || 786ffe644ebf4dcc50b314261ddd2d08c841f629349Dan Gohman (SameTails[commonTailIndex].getBlock() == PredBB && 787ffe644ebf4dcc50b314261ddd2d08c841f629349Dan Gohman !SameTails[commonTailIndex].tailIsWholeBlock())) { 78851b2b9e29e4fa828ffd83d36f548bc44a4007822Dale Johannesen // None of the blocks consist entirely of the common tail. 78951b2b9e29e4fa828ffd83d36f548bc44a4007822Dale Johannesen // Split a block so that one does. 7904d54e5b2dd4a3d3bed38ff9c7aa57fc66adb5855Evan Cheng if (!CreateCommonTailOnlyBlock(PredBB, 7914d54e5b2dd4a3d3bed38ff9c7aa57fc66adb5855Evan Cheng maxCommonTailLength, commonTailIndex)) { 7924d54e5b2dd4a3d3bed38ff9c7aa57fc66adb5855Evan Cheng RemoveBlocksWithHash(CurHash, SuccBB, PredBB); 7934d54e5b2dd4a3d3bed38ff9c7aa57fc66adb5855Evan Cheng continue; 7944d54e5b2dd4a3d3bed38ff9c7aa57fc66adb5855Evan Cheng } 7951d08d83230338ca5969ff6ae6737a978336538bfChris Lattner } 79651b2b9e29e4fa828ffd83d36f548bc44a4007822Dale Johannesen 797ffe644ebf4dcc50b314261ddd2d08c841f629349Dan Gohman MachineBasicBlock *MBB = SameTails[commonTailIndex].getBlock(); 79851b2b9e29e4fa828ffd83d36f548bc44a4007822Dale Johannesen // MBB is common tail. Adjust all other BB's to jump to this one. 79951b2b9e29e4fa828ffd83d36f548bc44a4007822Dale Johannesen // Traversal must be forwards so erases work. 800465e2b950d61c870fb3120c80191973e8282a3efDavid Greene DEBUG(dbgs() << "\nUsing common tail in BB#" << MBB->getNumber() 8012210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman << " for "); 8022210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman for (unsigned int i=0, e = SameTails.size(); i != e; ++i) { 8034e3f125e184f96ae72f2c44d16cafe0d44158283Dan Gohman if (commonTailIndex == i) 80451b2b9e29e4fa828ffd83d36f548bc44a4007822Dale Johannesen continue; 805465e2b950d61c870fb3120c80191973e8282a3efDavid Greene DEBUG(dbgs() << "BB#" << SameTails[i].getBlock()->getNumber() 8062210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman << (i == e-1 ? "" : ", ")); 80751b2b9e29e4fa828ffd83d36f548bc44a4007822Dale Johannesen // Hack the end off BB i, making it jump to BB commonTailIndex instead. 808ffe644ebf4dcc50b314261ddd2d08c841f629349Dan Gohman ReplaceTailWithBranchTo(SameTails[i].getTailStartPos(), MBB); 80951b2b9e29e4fa828ffd83d36f548bc44a4007822Dale Johannesen // BB i is no longer a predecessor of SuccBB; remove it from the worklist. 810ffe644ebf4dcc50b314261ddd2d08c841f629349Dan Gohman MergePotentials.erase(SameTails[i].getMPIter()); 81112143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner } 812465e2b950d61c870fb3120c80191973e8282a3efDavid Greene DEBUG(dbgs() << "\n"); 81351b2b9e29e4fa828ffd83d36f548bc44a4007822Dale Johannesen // We leave commonTailIndex in the worklist in case there are other blocks 81451b2b9e29e4fa828ffd83d36f548bc44a4007822Dale Johannesen // that match it with a smaller number of instructions. 8151d08d83230338ca5969ff6ae6737a978336538bfChris Lattner MadeChange = true; 81621ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner } 81712143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner return MadeChange; 81812143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner} 81921ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner 8207d33b4c59b56afb96feea71073c1d9e70c457e28Dale Johannesenbool BranchFolder::TailMergeBlocks(MachineFunction &MF) { 821030a0a0cdb38924e55773a8e0b5fe7347aa664aaEvan Cheng bool MadeChange = false; 82220350db44807f6863c3c00345934d45763ed21d3Bill Wendling if (!EnableTailMerge) return MadeChange; 82376b38fcabeba725e166a2ff72c56fe31d784b229Dale Johannesen 8247d33b4c59b56afb96feea71073c1d9e70c457e28Dale Johannesen // First find blocks with no successors. 82576b38fcabeba725e166a2ff72c56fe31d784b229Dale Johannesen MergePotentials.clear(); 826f924dea8ddb74df8d591f8fdc409fc5b8b5e10d4Rafael Espindola for (MachineFunction::iterator I = MF.begin(), E = MF.end(); 827f924dea8ddb74df8d591f8fdc409fc5b8b5e10d4Rafael Espindola I != E && MergePotentials.size() < TailMergeThreshold; ++I) { 828f924dea8ddb74df8d591f8fdc409fc5b8b5e10d4Rafael Espindola if (TriedMerging.count(I)) 829f924dea8ddb74df8d591f8fdc409fc5b8b5e10d4Rafael Espindola continue; 8307d33b4c59b56afb96feea71073c1d9e70c457e28Dale Johannesen if (I->succ_empty()) 83130fc5bbfd1047c666bfd653fefb74ffdc6e966f5Dan Gohman MergePotentials.push_back(MergePotentialsElt(HashEndOfMBB(I), I)); 8327d33b4c59b56afb96feea71073c1d9e70c457e28Dale Johannesen } 8334e3f125e184f96ae72f2c44d16cafe0d44158283Dan Gohman 834f924dea8ddb74df8d591f8fdc409fc5b8b5e10d4Rafael Espindola // If this is a large problem, avoid visiting the same basic blocks 835f924dea8ddb74df8d591f8fdc409fc5b8b5e10d4Rafael Espindola // multiple times. 836f924dea8ddb74df8d591f8fdc409fc5b8b5e10d4Rafael Espindola if (MergePotentials.size() == TailMergeThreshold) 837f924dea8ddb74df8d591f8fdc409fc5b8b5e10d4Rafael Espindola for (unsigned i = 0, e = MergePotentials.size(); i != e; ++i) 838f924dea8ddb74df8d591f8fdc409fc5b8b5e10d4Rafael Espindola TriedMerging.insert(MergePotentials[i].getBlock()); 83920350db44807f6863c3c00345934d45763ed21d3Bill Wendling 84076b38fcabeba725e166a2ff72c56fe31d784b229Dale Johannesen // See if we can do any tail merging on those. 841f924dea8ddb74df8d591f8fdc409fc5b8b5e10d4Rafael Espindola if (MergePotentials.size() >= 2) 8422210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman MadeChange |= TryTailMergeBlocks(NULL, NULL); 8437d33b4c59b56afb96feea71073c1d9e70c457e28Dale Johannesen 84476b38fcabeba725e166a2ff72c56fe31d784b229Dale Johannesen // Look at blocks (IBB) with multiple predecessors (PBB). 84576b38fcabeba725e166a2ff72c56fe31d784b229Dale Johannesen // We change each predecessor to a canonical form, by 84676b38fcabeba725e166a2ff72c56fe31d784b229Dale Johannesen // (1) temporarily removing any unconditional branch from the predecessor 84776b38fcabeba725e166a2ff72c56fe31d784b229Dale Johannesen // to IBB, and 84876b38fcabeba725e166a2ff72c56fe31d784b229Dale Johannesen // (2) alter conditional branches so they branch to the other block 8494e3f125e184f96ae72f2c44d16cafe0d44158283Dan Gohman // not IBB; this may require adding back an unconditional branch to IBB 85076b38fcabeba725e166a2ff72c56fe31d784b229Dale Johannesen // later, where there wasn't one coming in. E.g. 85176b38fcabeba725e166a2ff72c56fe31d784b229Dale Johannesen // Bcc IBB 85276b38fcabeba725e166a2ff72c56fe31d784b229Dale Johannesen // fallthrough to QBB 85376b38fcabeba725e166a2ff72c56fe31d784b229Dale Johannesen // here becomes 85476b38fcabeba725e166a2ff72c56fe31d784b229Dale Johannesen // Bncc QBB 85576b38fcabeba725e166a2ff72c56fe31d784b229Dale Johannesen // with a conceptual B to IBB after that, which never actually exists. 85676b38fcabeba725e166a2ff72c56fe31d784b229Dale Johannesen // With those changes, we see whether the predecessors' tails match, 85776b38fcabeba725e166a2ff72c56fe31d784b229Dale Johannesen // and merge them if so. We change things out of canonical form and 85876b38fcabeba725e166a2ff72c56fe31d784b229Dale Johannesen // back to the way they were later in the process. (OptimizeBranches 85976b38fcabeba725e166a2ff72c56fe31d784b229Dale Johannesen // would undo some of this, but we can't use it, because we'd get into 86076b38fcabeba725e166a2ff72c56fe31d784b229Dale Johannesen // a compile-time infinite loop repeatedly doing and undoing the same 86176b38fcabeba725e166a2ff72c56fe31d784b229Dale Johannesen // transformations.) 8627d33b4c59b56afb96feea71073c1d9e70c457e28Dale Johannesen 8637896c9f436a4eda5ec15e882a7505ba482a2fcd0Chris Lattner for (MachineFunction::iterator I = llvm::next(MF.begin()), E = MF.end(); 8642210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman I != E; ++I) { 865dbb4e57a3c7fb18d5ff2d9504c5cacb5df20fab4Bill Wendling if (I->pred_size() < 2) continue; 86620350db44807f6863c3c00345934d45763ed21d3Bill Wendling SmallPtrSet<MachineBasicBlock *, 8> UniquePreds; 86720350db44807f6863c3c00345934d45763ed21d3Bill Wendling MachineBasicBlock *IBB = I; 86820350db44807f6863c3c00345934d45763ed21d3Bill Wendling MachineBasicBlock *PredBB = prior(I); 86920350db44807f6863c3c00345934d45763ed21d3Bill Wendling MergePotentials.clear(); 87020350db44807f6863c3c00345934d45763ed21d3Bill Wendling for (MachineBasicBlock::pred_iterator P = I->pred_begin(), 87120350db44807f6863c3c00345934d45763ed21d3Bill Wendling E2 = I->pred_end(); 87220350db44807f6863c3c00345934d45763ed21d3Bill Wendling P != E2 && MergePotentials.size() < TailMergeThreshold; ++P) { 87320350db44807f6863c3c00345934d45763ed21d3Bill Wendling MachineBasicBlock *PBB = *P; 87420350db44807f6863c3c00345934d45763ed21d3Bill Wendling if (TriedMerging.count(PBB)) 87520350db44807f6863c3c00345934d45763ed21d3Bill Wendling continue; 87620350db44807f6863c3c00345934d45763ed21d3Bill Wendling 87720350db44807f6863c3c00345934d45763ed21d3Bill Wendling // Skip blocks that loop to themselves, can't tail merge these. 87820350db44807f6863c3c00345934d45763ed21d3Bill Wendling if (PBB == IBB) 87920350db44807f6863c3c00345934d45763ed21d3Bill Wendling continue; 88020350db44807f6863c3c00345934d45763ed21d3Bill Wendling 88120350db44807f6863c3c00345934d45763ed21d3Bill Wendling // Visit each predecessor only once. 88220350db44807f6863c3c00345934d45763ed21d3Bill Wendling if (!UniquePreds.insert(PBB)) 88320350db44807f6863c3c00345934d45763ed21d3Bill Wendling continue; 88420350db44807f6863c3c00345934d45763ed21d3Bill Wendling 88520350db44807f6863c3c00345934d45763ed21d3Bill Wendling // Skip blocks which may jump to a landing pad. Can't tail merge these. 88620350db44807f6863c3c00345934d45763ed21d3Bill Wendling if (PBB->getLandingPadSuccessor()) 88720350db44807f6863c3c00345934d45763ed21d3Bill Wendling continue; 88820350db44807f6863c3c00345934d45763ed21d3Bill Wendling 88920350db44807f6863c3c00345934d45763ed21d3Bill Wendling MachineBasicBlock *TBB = 0, *FBB = 0; 89020350db44807f6863c3c00345934d45763ed21d3Bill Wendling SmallVector<MachineOperand, 4> Cond; 89120350db44807f6863c3c00345934d45763ed21d3Bill Wendling if (!TII->AnalyzeBranch(*PBB, TBB, FBB, Cond, true)) { 89220350db44807f6863c3c00345934d45763ed21d3Bill Wendling // Failing case: IBB is the target of a cbr, and we cannot reverse the 89320350db44807f6863c3c00345934d45763ed21d3Bill Wendling // branch. 89420350db44807f6863c3c00345934d45763ed21d3Bill Wendling SmallVector<MachineOperand, 4> NewCond(Cond); 89520350db44807f6863c3c00345934d45763ed21d3Bill Wendling if (!Cond.empty() && TBB == IBB) { 89620350db44807f6863c3c00345934d45763ed21d3Bill Wendling if (TII->ReverseBranchCondition(NewCond)) 89720350db44807f6863c3c00345934d45763ed21d3Bill Wendling continue; 89820350db44807f6863c3c00345934d45763ed21d3Bill Wendling // This is the QBB case described above 89920350db44807f6863c3c00345934d45763ed21d3Bill Wendling if (!FBB) 90020350db44807f6863c3c00345934d45763ed21d3Bill Wendling FBB = llvm::next(MachineFunction::iterator(PBB)); 90120350db44807f6863c3c00345934d45763ed21d3Bill Wendling } 90220350db44807f6863c3c00345934d45763ed21d3Bill Wendling 90320350db44807f6863c3c00345934d45763ed21d3Bill Wendling // Failing case: the only way IBB can be reached from PBB is via 90420350db44807f6863c3c00345934d45763ed21d3Bill Wendling // exception handling. Happens for landing pads. Would be nice to have 90520350db44807f6863c3c00345934d45763ed21d3Bill Wendling // a bit in the edge so we didn't have to do all this. 90620350db44807f6863c3c00345934d45763ed21d3Bill Wendling if (IBB->isLandingPad()) { 90720350db44807f6863c3c00345934d45763ed21d3Bill Wendling MachineFunction::iterator IP = PBB; IP++; 90820350db44807f6863c3c00345934d45763ed21d3Bill Wendling MachineBasicBlock *PredNextBB = NULL; 90920350db44807f6863c3c00345934d45763ed21d3Bill Wendling if (IP != MF.end()) 91020350db44807f6863c3c00345934d45763ed21d3Bill Wendling PredNextBB = IP; 91120350db44807f6863c3c00345934d45763ed21d3Bill Wendling if (TBB == NULL) { 91220350db44807f6863c3c00345934d45763ed21d3Bill Wendling if (IBB != PredNextBB) // fallthrough 91320350db44807f6863c3c00345934d45763ed21d3Bill Wendling continue; 91420350db44807f6863c3c00345934d45763ed21d3Bill Wendling } else if (FBB) { 91520350db44807f6863c3c00345934d45763ed21d3Bill Wendling if (TBB != IBB && FBB != IBB) // cbr then ubr 91620350db44807f6863c3c00345934d45763ed21d3Bill Wendling continue; 91720350db44807f6863c3c00345934d45763ed21d3Bill Wendling } else if (Cond.empty()) { 91820350db44807f6863c3c00345934d45763ed21d3Bill Wendling if (TBB != IBB) // ubr 91920350db44807f6863c3c00345934d45763ed21d3Bill Wendling continue; 92020350db44807f6863c3c00345934d45763ed21d3Bill Wendling } else { 92120350db44807f6863c3c00345934d45763ed21d3Bill Wendling if (TBB != IBB && IBB != PredNextBB) // cbr 92276b38fcabeba725e166a2ff72c56fe31d784b229Dale Johannesen continue; 9237d33b4c59b56afb96feea71073c1d9e70c457e28Dale Johannesen } 9247d33b4c59b56afb96feea71073c1d9e70c457e28Dale Johannesen } 92520350db44807f6863c3c00345934d45763ed21d3Bill Wendling 92620350db44807f6863c3c00345934d45763ed21d3Bill Wendling // Remove the unconditional branch at the end, if any. 92720350db44807f6863c3c00345934d45763ed21d3Bill Wendling if (TBB && (Cond.empty() || FBB)) { 92820350db44807f6863c3c00345934d45763ed21d3Bill Wendling DebugLoc dl; // FIXME: this is nowhere 92920350db44807f6863c3c00345934d45763ed21d3Bill Wendling TII->RemoveBranch(*PBB); 93020350db44807f6863c3c00345934d45763ed21d3Bill Wendling if (!Cond.empty()) 93120350db44807f6863c3c00345934d45763ed21d3Bill Wendling // reinsert conditional branch only, for now 93220350db44807f6863c3c00345934d45763ed21d3Bill Wendling TII->InsertBranch(*PBB, (TBB == IBB) ? FBB : TBB, 0, NewCond, dl); 93320350db44807f6863c3c00345934d45763ed21d3Bill Wendling } 93420350db44807f6863c3c00345934d45763ed21d3Bill Wendling 93520350db44807f6863c3c00345934d45763ed21d3Bill Wendling MergePotentials.push_back(MergePotentialsElt(HashEndOfMBB(PBB), *P)); 9367d33b4c59b56afb96feea71073c1d9e70c457e28Dale Johannesen } 9377d33b4c59b56afb96feea71073c1d9e70c457e28Dale Johannesen } 93820350db44807f6863c3c00345934d45763ed21d3Bill Wendling 93920350db44807f6863c3c00345934d45763ed21d3Bill Wendling // If this is a large problem, avoid visiting the same basic blocks multiple 94020350db44807f6863c3c00345934d45763ed21d3Bill Wendling // times. 94120350db44807f6863c3c00345934d45763ed21d3Bill Wendling if (MergePotentials.size() == TailMergeThreshold) 94220350db44807f6863c3c00345934d45763ed21d3Bill Wendling for (unsigned i = 0, e = MergePotentials.size(); i != e; ++i) 94320350db44807f6863c3c00345934d45763ed21d3Bill Wendling TriedMerging.insert(MergePotentials[i].getBlock()); 94420350db44807f6863c3c00345934d45763ed21d3Bill Wendling 94520350db44807f6863c3c00345934d45763ed21d3Bill Wendling if (MergePotentials.size() >= 2) 94620350db44807f6863c3c00345934d45763ed21d3Bill Wendling MadeChange |= TryTailMergeBlocks(IBB, PredBB); 94720350db44807f6863c3c00345934d45763ed21d3Bill Wendling 94820350db44807f6863c3c00345934d45763ed21d3Bill Wendling // Reinsert an unconditional branch if needed. The 1 below can occur as a 94920350db44807f6863c3c00345934d45763ed21d3Bill Wendling // result of removing blocks in TryTailMergeBlocks. 95020350db44807f6863c3c00345934d45763ed21d3Bill Wendling PredBB = prior(I); // this may have been changed in TryTailMergeBlocks 95120350db44807f6863c3c00345934d45763ed21d3Bill Wendling if (MergePotentials.size() == 1 && 95220350db44807f6863c3c00345934d45763ed21d3Bill Wendling MergePotentials.begin()->getBlock() != PredBB) 95320350db44807f6863c3c00345934d45763ed21d3Bill Wendling FixTail(MergePotentials.begin()->getBlock(), IBB, TII); 9547d33b4c59b56afb96feea71073c1d9e70c457e28Dale Johannesen } 95520350db44807f6863c3c00345934d45763ed21d3Bill Wendling 9567d33b4c59b56afb96feea71073c1d9e70c457e28Dale Johannesen return MadeChange; 9577d33b4c59b56afb96feea71073c1d9e70c457e28Dale Johannesen} 95812143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner 95912143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner//===----------------------------------------------------------------------===// 96012143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner// Branch Optimization 96112143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner//===----------------------------------------------------------------------===// 96212143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner 96312143054aa6d120f029d268a5154bf2ecd0f707fChris Lattnerbool BranchFolder::OptimizeBranches(MachineFunction &MF) { 964030a0a0cdb38924e55773a8e0b5fe7347aa664aaEvan Cheng bool MadeChange = false; 9654e3f125e184f96ae72f2c44d16cafe0d44158283Dan Gohman 9666b896cec8b703e08e5f3d809e086a39b6ebe6589Dale Johannesen // Make sure blocks are numbered in order 9676b896cec8b703e08e5f3d809e086a39b6ebe6589Dale Johannesen MF.RenumberBlocks(); 9686b896cec8b703e08e5f3d809e086a39b6ebe6589Dale Johannesen 969cbc988be22bc9411d95215c8b7251b5f85710674Evan Cheng for (MachineFunction::iterator I = llvm::next(MF.begin()), E = MF.end(); 970cbc988be22bc9411d95215c8b7251b5f85710674Evan Cheng I != E; ) { 97112143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner MachineBasicBlock *MBB = I++; 972030a0a0cdb38924e55773a8e0b5fe7347aa664aaEvan Cheng MadeChange |= OptimizeBlock(MBB); 9734e3f125e184f96ae72f2c44d16cafe0d44158283Dan Gohman 97412143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner // If it is dead, remove it. 975033c9715d9bf7ce59ad2e466bf0720811b34da08Jim Laskey if (MBB->pred_empty()) { 97612143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner RemoveDeadBlock(MBB); 97712143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner MadeChange = true; 97812143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner ++NumDeadBlocks; 97912143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner } 98012143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner } 98112143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner return MadeChange; 98221ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner} 98321ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner 984c5cf227f3dac755508928b9dee8ac6a45dcb4e4fDale Johannesen// Blocks should be considered empty if they contain only debug info; 985c5cf227f3dac755508928b9dee8ac6a45dcb4e4fDale Johannesen// else the debug info would affect codegen. 986c5cf227f3dac755508928b9dee8ac6a45dcb4e4fDale Johannesenstatic bool IsEmptyBlock(MachineBasicBlock *MBB) { 987c5cf227f3dac755508928b9dee8ac6a45dcb4e4fDale Johannesen if (MBB->empty()) 988c5cf227f3dac755508928b9dee8ac6a45dcb4e4fDale Johannesen return true; 989c5cf227f3dac755508928b9dee8ac6a45dcb4e4fDale Johannesen for (MachineBasicBlock::iterator MBBI = MBB->begin(), MBBE = MBB->end(); 990c5cf227f3dac755508928b9dee8ac6a45dcb4e4fDale Johannesen MBBI!=MBBE; ++MBBI) { 991c5cf227f3dac755508928b9dee8ac6a45dcb4e4fDale Johannesen if (!MBBI->isDebugValue()) 992c5cf227f3dac755508928b9dee8ac6a45dcb4e4fDale Johannesen return false; 993c5cf227f3dac755508928b9dee8ac6a45dcb4e4fDale Johannesen } 994c5cf227f3dac755508928b9dee8ac6a45dcb4e4fDale Johannesen return true; 995c5cf227f3dac755508928b9dee8ac6a45dcb4e4fDale Johannesen} 99612143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner 9972cd9ffef6e74febd727f0b548c21ba3f4e5cd26fDale Johannesen// Blocks with only debug info and branches should be considered the same 9982cd9ffef6e74febd727f0b548c21ba3f4e5cd26fDale Johannesen// as blocks with only branches. 9992cd9ffef6e74febd727f0b548c21ba3f4e5cd26fDale Johannesenstatic bool IsBranchOnlyBlock(MachineBasicBlock *MBB) { 10002cd9ffef6e74febd727f0b548c21ba3f4e5cd26fDale Johannesen MachineBasicBlock::iterator MBBI, MBBE; 10012cd9ffef6e74febd727f0b548c21ba3f4e5cd26fDale Johannesen for (MBBI = MBB->begin(), MBBE = MBB->end(); MBBI!=MBBE; ++MBBI) { 10022cd9ffef6e74febd727f0b548c21ba3f4e5cd26fDale Johannesen if (!MBBI->isDebugValue()) 10032cd9ffef6e74febd727f0b548c21ba3f4e5cd26fDale Johannesen break; 10042cd9ffef6e74febd727f0b548c21ba3f4e5cd26fDale Johannesen } 10055a96b3dad2f634c9081c8b2b6c2575441dc5a2bdEvan Cheng return (MBBI->isBranch()); 10062cd9ffef6e74febd727f0b548c21ba3f4e5cd26fDale Johannesen} 10072cd9ffef6e74febd727f0b548c21ba3f4e5cd26fDale Johannesen 1008a7bef4a4e49f461984c04ef6be6eef3f1c023558Chris Lattner/// IsBetterFallthrough - Return true if it would be clearly better to 1009a7bef4a4e49f461984c04ef6be6eef3f1c023558Chris Lattner/// fall-through to MBB1 than to fall through into MBB2. This has to return 1010a7bef4a4e49f461984c04ef6be6eef3f1c023558Chris Lattner/// a strict ordering, returning true for both (MBB1,MBB2) and (MBB2,MBB1) will 1011a7bef4a4e49f461984c04ef6be6eef3f1c023558Chris Lattner/// result in infinite loops. 10124e3f125e184f96ae72f2c44d16cafe0d44158283Dan Gohmanstatic bool IsBetterFallthrough(MachineBasicBlock *MBB1, 101369244300b8a0112efb44b6273ecea4ca6264b8cfChris Lattner MachineBasicBlock *MBB2) { 1014154e1047184384afd0a701a9f8816459cf0b3490Chris Lattner // Right now, we use a simple heuristic. If MBB2 ends with a call, and 1015154e1047184384afd0a701a9f8816459cf0b3490Chris Lattner // MBB1 doesn't, we prefer to fall through into MBB1. This allows us to 1016a7bef4a4e49f461984c04ef6be6eef3f1c023558Chris Lattner // optimize branches that branch to either a return block or an assert block 1017a7bef4a4e49f461984c04ef6be6eef3f1c023558Chris Lattner // into a fallthrough to the return. 101893d6a7e9c21204c52d6efec6c672163e7de79660Dale Johannesen if (IsEmptyBlock(MBB1) || IsEmptyBlock(MBB2)) return false; 10194e3f125e184f96ae72f2c44d16cafe0d44158283Dan Gohman 102011a4f64bd4cb6d438dd4b5882ee1b7404832f27fChristopher Lamb // If there is a clear successor ordering we make sure that one block 102111a4f64bd4cb6d438dd4b5882ee1b7404832f27fChristopher Lamb // will fall through to the next 102211a4f64bd4cb6d438dd4b5882ee1b7404832f27fChristopher Lamb if (MBB1->isSuccessor(MBB2)) return true; 102311a4f64bd4cb6d438dd4b5882ee1b7404832f27fChristopher Lamb if (MBB2->isSuccessor(MBB1)) return false; 1024a7bef4a4e49f461984c04ef6be6eef3f1c023558Chris Lattner 102593d6a7e9c21204c52d6efec6c672163e7de79660Dale Johannesen // Neither block consists entirely of debug info (per IsEmptyBlock check), 102693d6a7e9c21204c52d6efec6c672163e7de79660Dale Johannesen // so we needn't test for falling off the beginning here. 102793d6a7e9c21204c52d6efec6c672163e7de79660Dale Johannesen MachineBasicBlock::iterator MBB1I = --MBB1->end(); 102893d6a7e9c21204c52d6efec6c672163e7de79660Dale Johannesen while (MBB1I->isDebugValue()) 102993d6a7e9c21204c52d6efec6c672163e7de79660Dale Johannesen --MBB1I; 103093d6a7e9c21204c52d6efec6c672163e7de79660Dale Johannesen MachineBasicBlock::iterator MBB2I = --MBB2->end(); 103193d6a7e9c21204c52d6efec6c672163e7de79660Dale Johannesen while (MBB2I->isDebugValue()) 103293d6a7e9c21204c52d6efec6c672163e7de79660Dale Johannesen --MBB2I; 10335a96b3dad2f634c9081c8b2b6c2575441dc5a2bdEvan Cheng return MBB2I->isCall() && !MBB1I->isCall(); 1034a7bef4a4e49f461984c04ef6be6eef3f1c023558Chris Lattner} 1035a7bef4a4e49f461984c04ef6be6eef3f1c023558Chris Lattner 10365b2749abf585f9e28656c289001c2327eed401afBill Wendling/// getBranchDebugLoc - Find and return, if any, the DebugLoc of the branch 10375b2749abf585f9e28656c289001c2327eed401afBill Wendling/// instructions on the block. Always use the DebugLoc of the first 10385b2749abf585f9e28656c289001c2327eed401afBill Wendling/// branching instruction found unless its absent, in which case use the 10395b2749abf585f9e28656c289001c2327eed401afBill Wendling/// DebugLoc of the second if present. 10405b2749abf585f9e28656c289001c2327eed401afBill Wendlingstatic DebugLoc getBranchDebugLoc(MachineBasicBlock &MBB) { 10415b2749abf585f9e28656c289001c2327eed401afBill Wendling MachineBasicBlock::iterator I = MBB.end(); 10425b2749abf585f9e28656c289001c2327eed401afBill Wendling if (I == MBB.begin()) 10435b2749abf585f9e28656c289001c2327eed401afBill Wendling return DebugLoc(); 10445b2749abf585f9e28656c289001c2327eed401afBill Wendling --I; 10455b2749abf585f9e28656c289001c2327eed401afBill Wendling while (I->isDebugValue() && I != MBB.begin()) 10465b2749abf585f9e28656c289001c2327eed401afBill Wendling --I; 10475b2749abf585f9e28656c289001c2327eed401afBill Wendling if (I->isBranch()) 10485b2749abf585f9e28656c289001c2327eed401afBill Wendling return I->getDebugLoc(); 10495b2749abf585f9e28656c289001c2327eed401afBill Wendling return DebugLoc(); 10505b2749abf585f9e28656c289001c2327eed401afBill Wendling} 10515b2749abf585f9e28656c289001c2327eed401afBill Wendling 10527821a8afd3009c3c2760592e61de9e2c31c73e18Chris Lattner/// OptimizeBlock - Analyze and optimize control flow related to the specified 10537821a8afd3009c3c2760592e61de9e2c31c73e18Chris Lattner/// block. This is never called on the entry block. 1054030a0a0cdb38924e55773a8e0b5fe7347aa664aaEvan Chengbool BranchFolder::OptimizeBlock(MachineBasicBlock *MBB) { 1055030a0a0cdb38924e55773a8e0b5fe7347aa664aaEvan Cheng bool MadeChange = false; 1056d194498d2669e28cd8e85b0ceb7c69a7ec66da13Dan Gohman MachineFunction &MF = *MBB->getParent(); 10572210c0bea83aa8a8585d793a1f63e8c01b65be38Dan GohmanReoptimizeBlock: 1058030a0a0cdb38924e55773a8e0b5fe7347aa664aaEvan Cheng 10597d09784d3fc652131a2afbf06a0f2ed893837fb9Chris Lattner MachineFunction::iterator FallThrough = MBB; 10607d09784d3fc652131a2afbf06a0f2ed893837fb9Chris Lattner ++FallThrough; 10614e3f125e184f96ae72f2c44d16cafe0d44158283Dan Gohman 1062eb15eeec396145b6f5028d07bd2c4a5e903fdec5Chris Lattner // If this block is empty, make everyone use its fall-through, not the block 1063a52dd151378eeaad1369829b1dc3164874774e04Dale Johannesen // explicitly. Landing pads should not do this since the landing-pad table 1064ab918103d284b91105831c6b198ad2ab760b907dDan Gohman // points to this block. Blocks with their addresses taken shouldn't be 1065ab918103d284b91105831c6b198ad2ab760b907dDan Gohman // optimized away. 1066c5cf227f3dac755508928b9dee8ac6a45dcb4e4fDale Johannesen if (IsEmptyBlock(MBB) && !MBB->isLandingPad() && !MBB->hasAddressTaken()) { 1067386e29065db5b05b57440f6b2a6dfa1e7f29a00dChris Lattner // Dead block? Leave for cleanup later. 1068030a0a0cdb38924e55773a8e0b5fe7347aa664aaEvan Cheng if (MBB->pred_empty()) return MadeChange; 10694e3f125e184f96ae72f2c44d16cafe0d44158283Dan Gohman 1070d194498d2669e28cd8e85b0ceb7c69a7ec66da13Dan Gohman if (FallThrough == MF.end()) { 1071c50ffcb7fcb7c1109fee2406e8f74d096f755f47Chris Lattner // TODO: Simplify preds to not branch here if possible! 1072c50ffcb7fcb7c1109fee2406e8f74d096f755f47Chris Lattner } else { 1073c50ffcb7fcb7c1109fee2406e8f74d096f755f47Chris Lattner // Rewrite all predecessors of the old block to go to the fallthrough 1074c50ffcb7fcb7c1109fee2406e8f74d096f755f47Chris Lattner // instead. 1075033c9715d9bf7ce59ad2e466bf0720811b34da08Jim Laskey while (!MBB->pred_empty()) { 10767821a8afd3009c3c2760592e61de9e2c31c73e18Chris Lattner MachineBasicBlock *Pred = *(MBB->pred_end()-1); 10770370fad74b48388412c52d1325512f2c218487faEvan Cheng Pred->ReplaceUsesOfBlockWith(MBB, FallThrough); 10787821a8afd3009c3c2760592e61de9e2c31c73e18Chris Lattner } 1079c50ffcb7fcb7c1109fee2406e8f74d096f755f47Chris Lattner // If MBB was the target of a jump table, update jump tables to go to the 1080c50ffcb7fcb7c1109fee2406e8f74d096f755f47Chris Lattner // fallthrough instead. 1081071c62fad0b25ad4131e7f984173a796c1e63f61Chris Lattner if (MachineJumpTableInfo *MJTI = MF.getJumpTableInfo()) 1082071c62fad0b25ad4131e7f984173a796c1e63f61Chris Lattner MJTI->ReplaceMBBInJumpTables(MBB, FallThrough); 10837821a8afd3009c3c2760592e61de9e2c31c73e18Chris Lattner MadeChange = true; 108421ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner } 1085030a0a0cdb38924e55773a8e0b5fe7347aa664aaEvan Cheng return MadeChange; 108621ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner } 108721ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner 10887821a8afd3009c3c2760592e61de9e2c31c73e18Chris Lattner // Check to see if we can simplify the terminator of the block before this 10897821a8afd3009c3c2760592e61de9e2c31c73e18Chris Lattner // one. 10907d09784d3fc652131a2afbf06a0f2ed893837fb9Chris Lattner MachineBasicBlock &PrevBB = *prior(MachineFunction::iterator(MBB)); 1091ffddf6ba1c58b42dcfd071972754649c3ca5dff7Chris Lattner 10927821a8afd3009c3c2760592e61de9e2c31c73e18Chris Lattner MachineBasicBlock *PriorTBB = 0, *PriorFBB = 0; 109344eb65cf58e3ab9b5621ce72256d1621a18aeed7Owen Anderson SmallVector<MachineOperand, 4> PriorCond; 10946b0e3f890779b7fc912bec8d40a9590e44742737Chris Lattner bool PriorUnAnalyzable = 1095dc54d317e7a381ef8e4aca80d54ad1466bb85ddaEvan Cheng TII->AnalyzeBranch(PrevBB, PriorTBB, PriorFBB, PriorCond, true); 1096386e29065db5b05b57440f6b2a6dfa1e7f29a00dChris Lattner if (!PriorUnAnalyzable) { 1097386e29065db5b05b57440f6b2a6dfa1e7f29a00dChris Lattner // If the CFG for the prior block has extra edges, remove them. 10982bdb7d0cc88881857073b36f4a09ebe2f2008c24Evan Cheng MadeChange |= PrevBB.CorrectExtraCFGEdges(PriorTBB, PriorFBB, 10992bdb7d0cc88881857073b36f4a09ebe2f2008c24Evan Cheng !PriorCond.empty()); 11004e3f125e184f96ae72f2c44d16cafe0d44158283Dan Gohman 11017821a8afd3009c3c2760592e61de9e2c31c73e18Chris Lattner // If the previous branch is conditional and both conditions go to the same 11022d47bd937c13556ace07b2b2daf4dfe75f4e1e90Chris Lattner // destination, remove the branch, replacing it with an unconditional one or 11032d47bd937c13556ace07b2b2daf4dfe75f4e1e90Chris Lattner // a fall-through. 11047821a8afd3009c3c2760592e61de9e2c31c73e18Chris Lattner if (PriorTBB && PriorTBB == PriorFBB) { 11055b2749abf585f9e28656c289001c2327eed401afBill Wendling DebugLoc dl = getBranchDebugLoc(PrevBB); 1106386e29065db5b05b57440f6b2a6dfa1e7f29a00dChris Lattner TII->RemoveBranch(PrevBB); 11074e3f125e184f96ae72f2c44d16cafe0d44158283Dan Gohman PriorCond.clear(); 11087d09784d3fc652131a2afbf06a0f2ed893837fb9Chris Lattner if (PriorTBB != MBB) 11093bf912593301152b65accb9d9c37a95172f1df5aStuart Hastings TII->InsertBranch(PrevBB, PriorTBB, 0, PriorCond, dl); 11107821a8afd3009c3c2760592e61de9e2c31c73e18Chris Lattner MadeChange = true; 111112143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner ++NumBranchOpts; 11122210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman goto ReoptimizeBlock; 11137821a8afd3009c3c2760592e61de9e2c31c73e18Chris Lattner } 11144e3f125e184f96ae72f2c44d16cafe0d44158283Dan Gohman 11152210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman // If the previous block unconditionally falls through to this block and 11162210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman // this block has no other predecessors, move the contents of this block 11172210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman // into the prior block. This doesn't usually happen when SimplifyCFG 1118465c8252f282fda26db6962a81948afce7f01cc2Bob Wilson // has been used, but it can happen if tail merging splits a fall-through 1119465c8252f282fda26db6962a81948afce7f01cc2Bob Wilson // predecessor of a block. 11202210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman // This has to check PrevBB->succ_size() because EH edges are ignored by 11212210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman // AnalyzeBranch. 11222210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman if (PriorCond.empty() && !PriorTBB && MBB->pred_size() == 1 && 11232210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman PrevBB.succ_size() == 1 && 1124d3dbd5f5cdb54b5e9472ec6040612fc4d898d297Bill Wendling !MBB->hasAddressTaken() && !MBB->isLandingPad()) { 1125465e2b950d61c870fb3120c80191973e8282a3efDavid Greene DEBUG(dbgs() << "\nMerging into block: " << PrevBB 11262210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman << "From MBB: " << *MBB); 112795ba669e09c30f9aa1a7d754199548b8e6a227ceDevang Patel // Remove redundant DBG_VALUEs first. 1128785badb83e09ebae485c40f3fd86576581dd516eDevang Patel if (PrevBB.begin() != PrevBB.end()) { 1129785badb83e09ebae485c40f3fd86576581dd516eDevang Patel MachineBasicBlock::iterator PrevBBIter = PrevBB.end(); 1130785badb83e09ebae485c40f3fd86576581dd516eDevang Patel --PrevBBIter; 1131785badb83e09ebae485c40f3fd86576581dd516eDevang Patel MachineBasicBlock::iterator MBBIter = MBB->begin(); 11321df91b0e54bc62f8fc7a06a4f75220e40aa2dfe0Andrew Trick // Check if DBG_VALUE at the end of PrevBB is identical to the 113395ba669e09c30f9aa1a7d754199548b8e6a227ceDevang Patel // DBG_VALUE at the beginning of MBB. 1134785badb83e09ebae485c40f3fd86576581dd516eDevang Patel while (PrevBBIter != PrevBB.begin() && MBBIter != MBB->end() 1135785badb83e09ebae485c40f3fd86576581dd516eDevang Patel && PrevBBIter->isDebugValue() && MBBIter->isDebugValue()) { 1136785badb83e09ebae485c40f3fd86576581dd516eDevang Patel if (!MBBIter->isIdenticalTo(PrevBBIter)) 1137785badb83e09ebae485c40f3fd86576581dd516eDevang Patel break; 1138785badb83e09ebae485c40f3fd86576581dd516eDevang Patel MachineInstr *DuplicateDbg = MBBIter; 1139785badb83e09ebae485c40f3fd86576581dd516eDevang Patel ++MBBIter; -- PrevBBIter; 1140785badb83e09ebae485c40f3fd86576581dd516eDevang Patel DuplicateDbg->eraseFromParent(); 1141785badb83e09ebae485c40f3fd86576581dd516eDevang Patel } 1142785badb83e09ebae485c40f3fd86576581dd516eDevang Patel } 11432210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman PrevBB.splice(PrevBB.end(), MBB, MBB->begin(), MBB->end()); 114490f20044ade3712c8b0c3f4ebe47d57ad15ae6ceChad Rosier PrevBB.removeSuccessor(PrevBB.succ_begin()); 11452210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman assert(PrevBB.succ_empty()); 11462210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman PrevBB.transferSuccessors(MBB); 11472210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman MadeChange = true; 11482210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman return MadeChange; 11492210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman } 11503cbc3120873242d93e469b4635c0bbd09fdb6438Bob Wilson 11517821a8afd3009c3c2760592e61de9e2c31c73e18Chris Lattner // If the previous branch *only* branches to *this* block (conditional or 11527821a8afd3009c3c2760592e61de9e2c31c73e18Chris Lattner // not) remove the branch. 11537d09784d3fc652131a2afbf06a0f2ed893837fb9Chris Lattner if (PriorTBB == MBB && PriorFBB == 0) { 1154386e29065db5b05b57440f6b2a6dfa1e7f29a00dChris Lattner TII->RemoveBranch(PrevBB); 11557821a8afd3009c3c2760592e61de9e2c31c73e18Chris Lattner MadeChange = true; 115612143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner ++NumBranchOpts; 11572210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman goto ReoptimizeBlock; 11587821a8afd3009c3c2760592e61de9e2c31c73e18Chris Lattner } 11594e3f125e184f96ae72f2c44d16cafe0d44158283Dan Gohman 11602d47bd937c13556ace07b2b2daf4dfe75f4e1e90Chris Lattner // If the prior block branches somewhere else on the condition and here if 11612d47bd937c13556ace07b2b2daf4dfe75f4e1e90Chris Lattner // the condition is false, remove the uncond second branch. 11627d09784d3fc652131a2afbf06a0f2ed893837fb9Chris Lattner if (PriorFBB == MBB) { 11635b2749abf585f9e28656c289001c2327eed401afBill Wendling DebugLoc dl = getBranchDebugLoc(PrevBB); 11642d47bd937c13556ace07b2b2daf4dfe75f4e1e90Chris Lattner TII->RemoveBranch(PrevBB); 11653bf912593301152b65accb9d9c37a95172f1df5aStuart Hastings TII->InsertBranch(PrevBB, PriorTBB, 0, PriorCond, dl); 11662d47bd937c13556ace07b2b2daf4dfe75f4e1e90Chris Lattner MadeChange = true; 11672d47bd937c13556ace07b2b2daf4dfe75f4e1e90Chris Lattner ++NumBranchOpts; 11682210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman goto ReoptimizeBlock; 11692d47bd937c13556ace07b2b2daf4dfe75f4e1e90Chris Lattner } 11704e3f125e184f96ae72f2c44d16cafe0d44158283Dan Gohman 1171a2d799531a748a349b9a458dbbc580b134074c49Chris Lattner // If the prior block branches here on true and somewhere else on false, and 1172a2d799531a748a349b9a458dbbc580b134074c49Chris Lattner // if the branch condition is reversible, reverse the branch to create a 1173a2d799531a748a349b9a458dbbc580b134074c49Chris Lattner // fall-through. 11747d09784d3fc652131a2afbf06a0f2ed893837fb9Chris Lattner if (PriorTBB == MBB) { 117544eb65cf58e3ab9b5621ce72256d1621a18aeed7Owen Anderson SmallVector<MachineOperand, 4> NewPriorCond(PriorCond); 1176a2d799531a748a349b9a458dbbc580b134074c49Chris Lattner if (!TII->ReverseBranchCondition(NewPriorCond)) { 11775b2749abf585f9e28656c289001c2327eed401afBill Wendling DebugLoc dl = getBranchDebugLoc(PrevBB); 1178a2d799531a748a349b9a458dbbc580b134074c49Chris Lattner TII->RemoveBranch(PrevBB); 11793bf912593301152b65accb9d9c37a95172f1df5aStuart Hastings TII->InsertBranch(PrevBB, PriorFBB, 0, NewPriorCond, dl); 1180a2d799531a748a349b9a458dbbc580b134074c49Chris Lattner MadeChange = true; 1181a2d799531a748a349b9a458dbbc580b134074c49Chris Lattner ++NumBranchOpts; 11822210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman goto ReoptimizeBlock; 1183a2d799531a748a349b9a458dbbc580b134074c49Chris Lattner } 1184a2d799531a748a349b9a458dbbc580b134074c49Chris Lattner } 11854e3f125e184f96ae72f2c44d16cafe0d44158283Dan Gohman 11866d31268a7dc9854fa5a5cb9227ba9a15c5898414Dan Gohman // If this block has no successors (e.g. it is a return block or ends with 11876d31268a7dc9854fa5a5cb9227ba9a15c5898414Dan Gohman // a call to a no-return function like abort or __cxa_throw) and if the pred 11886d31268a7dc9854fa5a5cb9227ba9a15c5898414Dan Gohman // falls through into this block, and if it would otherwise fall through 11896d31268a7dc9854fa5a5cb9227ba9a15c5898414Dan Gohman // into the block after this, move this block to the end of the function. 1190154e1047184384afd0a701a9f8816459cf0b3490Chris Lattner // 1191a7bef4a4e49f461984c04ef6be6eef3f1c023558Chris Lattner // We consider it more likely that execution will stay in the function (e.g. 1192a7bef4a4e49f461984c04ef6be6eef3f1c023558Chris Lattner // due to loops) than it is to exit it. This asserts in loops etc, moving 1193a7bef4a4e49f461984c04ef6be6eef3f1c023558Chris Lattner // the assert condition out of the loop body. 11946d31268a7dc9854fa5a5cb9227ba9a15c5898414Dan Gohman if (MBB->succ_empty() && !PriorCond.empty() && PriorFBB == 0 && 1195154e1047184384afd0a701a9f8816459cf0b3490Chris Lattner MachineFunction::iterator(PriorTBB) == FallThrough && 119615acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson !MBB->canFallThrough()) { 1197f10a56a86f8ae32d0493c7de770493d55519b073Chris Lattner bool DoTransform = true; 11984e3f125e184f96ae72f2c44d16cafe0d44158283Dan Gohman 1199a7bef4a4e49f461984c04ef6be6eef3f1c023558Chris Lattner // We have to be careful that the succs of PredBB aren't both no-successor 1200a7bef4a4e49f461984c04ef6be6eef3f1c023558Chris Lattner // blocks. If neither have successors and if PredBB is the second from 1201a7bef4a4e49f461984c04ef6be6eef3f1c023558Chris Lattner // last block in the function, we'd just keep swapping the two blocks for 1202a7bef4a4e49f461984c04ef6be6eef3f1c023558Chris Lattner // last. Only do the swap if one is clearly better to fall through than 1203a7bef4a4e49f461984c04ef6be6eef3f1c023558Chris Lattner // the other. 1204d194498d2669e28cd8e85b0ceb7c69a7ec66da13Dan Gohman if (FallThrough == --MF.end() && 120569244300b8a0112efb44b6273ecea4ca6264b8cfChris Lattner !IsBetterFallthrough(PriorTBB, MBB)) 1206f10a56a86f8ae32d0493c7de770493d55519b073Chris Lattner DoTransform = false; 1207f10a56a86f8ae32d0493c7de770493d55519b073Chris Lattner 1208f10a56a86f8ae32d0493c7de770493d55519b073Chris Lattner if (DoTransform) { 1209a7bef4a4e49f461984c04ef6be6eef3f1c023558Chris Lattner // Reverse the branch so we will fall through on the previous true cond. 121044eb65cf58e3ab9b5621ce72256d1621a18aeed7Owen Anderson SmallVector<MachineOperand, 4> NewPriorCond(PriorCond); 1211a7bef4a4e49f461984c04ef6be6eef3f1c023558Chris Lattner if (!TII->ReverseBranchCondition(NewPriorCond)) { 1212465e2b950d61c870fb3120c80191973e8282a3efDavid Greene DEBUG(dbgs() << "\nMoving MBB: " << *MBB 12133403bcd8f943cb053a7d9bbf8eb8135407699afaBill Wendling << "To make fallthrough to: " << *PriorTBB << "\n"); 12144e3f125e184f96ae72f2c44d16cafe0d44158283Dan Gohman 12155b2749abf585f9e28656c289001c2327eed401afBill Wendling DebugLoc dl = getBranchDebugLoc(PrevBB); 1216a7bef4a4e49f461984c04ef6be6eef3f1c023558Chris Lattner TII->RemoveBranch(PrevBB); 12173bf912593301152b65accb9d9c37a95172f1df5aStuart Hastings TII->InsertBranch(PrevBB, MBB, 0, NewPriorCond, dl); 1218a7bef4a4e49f461984c04ef6be6eef3f1c023558Chris Lattner 1219a7bef4a4e49f461984c04ef6be6eef3f1c023558Chris Lattner // Move this block to the end of the function. 1220d194498d2669e28cd8e85b0ceb7c69a7ec66da13Dan Gohman MBB->moveAfter(--MF.end()); 1221a7bef4a4e49f461984c04ef6be6eef3f1c023558Chris Lattner MadeChange = true; 1222a7bef4a4e49f461984c04ef6be6eef3f1c023558Chris Lattner ++NumBranchOpts; 1223030a0a0cdb38924e55773a8e0b5fe7347aa664aaEvan Cheng return MadeChange; 1224a7bef4a4e49f461984c04ef6be6eef3f1c023558Chris Lattner } 1225a7bef4a4e49f461984c04ef6be6eef3f1c023558Chris Lattner } 1226a7bef4a4e49f461984c04ef6be6eef3f1c023558Chris Lattner } 12277821a8afd3009c3c2760592e61de9e2c31c73e18Chris Lattner } 12284e3f125e184f96ae72f2c44d16cafe0d44158283Dan Gohman 1229386e29065db5b05b57440f6b2a6dfa1e7f29a00dChris Lattner // Analyze the branch in the current block. 1230386e29065db5b05b57440f6b2a6dfa1e7f29a00dChris Lattner MachineBasicBlock *CurTBB = 0, *CurFBB = 0; 123144eb65cf58e3ab9b5621ce72256d1621a18aeed7Owen Anderson SmallVector<MachineOperand, 4> CurCond; 1232dc54d317e7a381ef8e4aca80d54ad1466bb85ddaEvan Cheng bool CurUnAnalyzable= TII->AnalyzeBranch(*MBB, CurTBB, CurFBB, CurCond, true); 12336b0e3f890779b7fc912bec8d40a9590e44742737Chris Lattner if (!CurUnAnalyzable) { 1234386e29065db5b05b57440f6b2a6dfa1e7f29a00dChris Lattner // If the CFG for the prior block has extra edges, remove them. 12352bdb7d0cc88881857073b36f4a09ebe2f2008c24Evan Cheng MadeChange |= MBB->CorrectExtraCFGEdges(CurTBB, CurFBB, !CurCond.empty()); 1236386e29065db5b05b57440f6b2a6dfa1e7f29a00dChris Lattner 12374e3f125e184f96ae72f2c44d16cafe0d44158283Dan Gohman // If this is a two-way branch, and the FBB branches to this block, reverse 12385d056952ba2f97729c5db69a3f14250595fa1ee8Chris Lattner // the condition so the single-basic-block loop is faster. Instead of: 12395d056952ba2f97729c5db69a3f14250595fa1ee8Chris Lattner // Loop: xxx; jcc Out; jmp Loop 12405d056952ba2f97729c5db69a3f14250595fa1ee8Chris Lattner // we want: 12415d056952ba2f97729c5db69a3f14250595fa1ee8Chris Lattner // Loop: xxx; jncc Loop; jmp Out 12425d056952ba2f97729c5db69a3f14250595fa1ee8Chris Lattner if (CurTBB && CurFBB && CurFBB == MBB && CurTBB != MBB) { 124344eb65cf58e3ab9b5621ce72256d1621a18aeed7Owen Anderson SmallVector<MachineOperand, 4> NewCond(CurCond); 12445d056952ba2f97729c5db69a3f14250595fa1ee8Chris Lattner if (!TII->ReverseBranchCondition(NewCond)) { 12455b2749abf585f9e28656c289001c2327eed401afBill Wendling DebugLoc dl = getBranchDebugLoc(*MBB); 12465d056952ba2f97729c5db69a3f14250595fa1ee8Chris Lattner TII->RemoveBranch(*MBB); 12473bf912593301152b65accb9d9c37a95172f1df5aStuart Hastings TII->InsertBranch(*MBB, CurFBB, CurTBB, NewCond, dl); 12485d056952ba2f97729c5db69a3f14250595fa1ee8Chris Lattner MadeChange = true; 12495d056952ba2f97729c5db69a3f14250595fa1ee8Chris Lattner ++NumBranchOpts; 12502210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman goto ReoptimizeBlock; 12515d056952ba2f97729c5db69a3f14250595fa1ee8Chris Lattner } 12525d056952ba2f97729c5db69a3f14250595fa1ee8Chris Lattner } 12534e3f125e184f96ae72f2c44d16cafe0d44158283Dan Gohman 1254386e29065db5b05b57440f6b2a6dfa1e7f29a00dChris Lattner // If this branch is the only thing in its block, see if we can forward 1255386e29065db5b05b57440f6b2a6dfa1e7f29a00dChris Lattner // other blocks across it. 12564e3f125e184f96ae72f2c44d16cafe0d44158283Dan Gohman if (CurTBB && CurCond.empty() && CurFBB == 0 && 12572cd9ffef6e74febd727f0b548c21ba3f4e5cd26fDale Johannesen IsBranchOnlyBlock(MBB) && CurTBB != MBB && 1258888acc35a3e271d092f9b1efc7c32b94ff17fbf7Bob Wilson !MBB->hasAddressTaken()) { 12595b2749abf585f9e28656c289001c2327eed401afBill Wendling DebugLoc dl = getBranchDebugLoc(*MBB); 1260386e29065db5b05b57440f6b2a6dfa1e7f29a00dChris Lattner // This block may contain just an unconditional branch. Because there can 1261386e29065db5b05b57440f6b2a6dfa1e7f29a00dChris Lattner // be 'non-branch terminators' in the block, try removing the branch and 1262386e29065db5b05b57440f6b2a6dfa1e7f29a00dChris Lattner // then seeing if the block is empty. 1263386e29065db5b05b57440f6b2a6dfa1e7f29a00dChris Lattner TII->RemoveBranch(*MBB); 1264c5cf227f3dac755508928b9dee8ac6a45dcb4e4fDale Johannesen // If the only things remaining in the block are debug info, remove these 1265c5cf227f3dac755508928b9dee8ac6a45dcb4e4fDale Johannesen // as well, so this will behave the same as an empty block in non-debug 1266c5cf227f3dac755508928b9dee8ac6a45dcb4e4fDale Johannesen // mode. 1267c5cf227f3dac755508928b9dee8ac6a45dcb4e4fDale Johannesen if (!MBB->empty()) { 1268c5cf227f3dac755508928b9dee8ac6a45dcb4e4fDale Johannesen bool NonDebugInfoFound = false; 1269c5cf227f3dac755508928b9dee8ac6a45dcb4e4fDale Johannesen for (MachineBasicBlock::iterator I = MBB->begin(), E = MBB->end(); 1270c5cf227f3dac755508928b9dee8ac6a45dcb4e4fDale Johannesen I != E; ++I) { 1271c5cf227f3dac755508928b9dee8ac6a45dcb4e4fDale Johannesen if (!I->isDebugValue()) { 1272c5cf227f3dac755508928b9dee8ac6a45dcb4e4fDale Johannesen NonDebugInfoFound = true; 1273c5cf227f3dac755508928b9dee8ac6a45dcb4e4fDale Johannesen break; 1274c5cf227f3dac755508928b9dee8ac6a45dcb4e4fDale Johannesen } 1275c5cf227f3dac755508928b9dee8ac6a45dcb4e4fDale Johannesen } 1276c5cf227f3dac755508928b9dee8ac6a45dcb4e4fDale Johannesen if (!NonDebugInfoFound) 1277c5cf227f3dac755508928b9dee8ac6a45dcb4e4fDale Johannesen // Make the block empty, losing the debug info (we could probably 1278c5cf227f3dac755508928b9dee8ac6a45dcb4e4fDale Johannesen // improve this in some cases.) 1279c5cf227f3dac755508928b9dee8ac6a45dcb4e4fDale Johannesen MBB->erase(MBB->begin(), MBB->end()); 1280c5cf227f3dac755508928b9dee8ac6a45dcb4e4fDale Johannesen } 1281386e29065db5b05b57440f6b2a6dfa1e7f29a00dChris Lattner // If this block is just an unconditional branch to CurTBB, we can 1282386e29065db5b05b57440f6b2a6dfa1e7f29a00dChris Lattner // usually completely eliminate the block. The only case we cannot 1283386e29065db5b05b57440f6b2a6dfa1e7f29a00dChris Lattner // completely eliminate the block is when the block before this one 1284386e29065db5b05b57440f6b2a6dfa1e7f29a00dChris Lattner // falls through into MBB and we can't understand the prior block's branch 1285386e29065db5b05b57440f6b2a6dfa1e7f29a00dChris Lattner // condition. 1286cf420cca572b061fdd63587cb90904c641b6e216Chris Lattner if (MBB->empty()) { 1287864e2efce2cb5d02e376933933d96074723fe77cDan Gohman bool PredHasNoFallThrough = !PrevBB.canFallThrough(); 1288cf420cca572b061fdd63587cb90904c641b6e216Chris Lattner if (PredHasNoFallThrough || !PriorUnAnalyzable || 1289cf420cca572b061fdd63587cb90904c641b6e216Chris Lattner !PrevBB.isSuccessor(MBB)) { 1290cf420cca572b061fdd63587cb90904c641b6e216Chris Lattner // If the prior block falls through into us, turn it into an 1291cf420cca572b061fdd63587cb90904c641b6e216Chris Lattner // explicit branch to us to make updates simpler. 12924e3f125e184f96ae72f2c44d16cafe0d44158283Dan Gohman if (!PredHasNoFallThrough && PrevBB.isSuccessor(MBB) && 1293cf420cca572b061fdd63587cb90904c641b6e216Chris Lattner PriorTBB != MBB && PriorFBB != MBB) { 1294cf420cca572b061fdd63587cb90904c641b6e216Chris Lattner if (PriorTBB == 0) { 12956acfe12dd6d52c801f78c240528b7cb42fa91159Chris Lattner assert(PriorCond.empty() && PriorFBB == 0 && 12966acfe12dd6d52c801f78c240528b7cb42fa91159Chris Lattner "Bad branch analysis"); 1297cf420cca572b061fdd63587cb90904c641b6e216Chris Lattner PriorTBB = MBB; 1298cf420cca572b061fdd63587cb90904c641b6e216Chris Lattner } else { 1299cf420cca572b061fdd63587cb90904c641b6e216Chris Lattner assert(PriorFBB == 0 && "Machine CFG out of date!"); 1300cf420cca572b061fdd63587cb90904c641b6e216Chris Lattner PriorFBB = MBB; 1301cf420cca572b061fdd63587cb90904c641b6e216Chris Lattner } 13025b2749abf585f9e28656c289001c2327eed401afBill Wendling DebugLoc pdl = getBranchDebugLoc(PrevBB); 1303cf420cca572b061fdd63587cb90904c641b6e216Chris Lattner TII->RemoveBranch(PrevBB); 13045b2749abf585f9e28656c289001c2327eed401afBill Wendling TII->InsertBranch(PrevBB, PriorTBB, PriorFBB, PriorCond, pdl); 1305386e29065db5b05b57440f6b2a6dfa1e7f29a00dChris Lattner } 130621ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner 1307cf420cca572b061fdd63587cb90904c641b6e216Chris Lattner // Iterate through all the predecessors, revectoring each in-turn. 13088a46d342d8cbca7c9c7be6c66007d41329babad0David Greene size_t PI = 0; 1309cf420cca572b061fdd63587cb90904c641b6e216Chris Lattner bool DidChange = false; 1310cf420cca572b061fdd63587cb90904c641b6e216Chris Lattner bool HasBranchToSelf = false; 13118a46d342d8cbca7c9c7be6c66007d41329babad0David Greene while(PI != MBB->pred_size()) { 13128a46d342d8cbca7c9c7be6c66007d41329babad0David Greene MachineBasicBlock *PMBB = *(MBB->pred_begin() + PI); 13138a46d342d8cbca7c9c7be6c66007d41329babad0David Greene if (PMBB == MBB) { 1314cf420cca572b061fdd63587cb90904c641b6e216Chris Lattner // If this block has an uncond branch to itself, leave it. 1315cf420cca572b061fdd63587cb90904c641b6e216Chris Lattner ++PI; 1316cf420cca572b061fdd63587cb90904c641b6e216Chris Lattner HasBranchToSelf = true; 1317cf420cca572b061fdd63587cb90904c641b6e216Chris Lattner } else { 1318cf420cca572b061fdd63587cb90904c641b6e216Chris Lattner DidChange = true; 13198a46d342d8cbca7c9c7be6c66007d41329babad0David Greene PMBB->ReplaceUsesOfBlockWith(MBB, CurTBB); 1320bf06f6a6f1be0802ad7b761138ecba568814008aDale Johannesen // If this change resulted in PMBB ending in a conditional 1321bf06f6a6f1be0802ad7b761138ecba568814008aDale Johannesen // branch where both conditions go to the same destination, 1322bf06f6a6f1be0802ad7b761138ecba568814008aDale Johannesen // change this to an unconditional branch (and fix the CFG). 1323bf06f6a6f1be0802ad7b761138ecba568814008aDale Johannesen MachineBasicBlock *NewCurTBB = 0, *NewCurFBB = 0; 1324bf06f6a6f1be0802ad7b761138ecba568814008aDale Johannesen SmallVector<MachineOperand, 4> NewCurCond; 1325bf06f6a6f1be0802ad7b761138ecba568814008aDale Johannesen bool NewCurUnAnalyzable = TII->AnalyzeBranch(*PMBB, NewCurTBB, 1326bf06f6a6f1be0802ad7b761138ecba568814008aDale Johannesen NewCurFBB, NewCurCond, true); 1327bf06f6a6f1be0802ad7b761138ecba568814008aDale Johannesen if (!NewCurUnAnalyzable && NewCurTBB && NewCurTBB == NewCurFBB) { 13285b2749abf585f9e28656c289001c2327eed401afBill Wendling DebugLoc pdl = getBranchDebugLoc(*PMBB); 1329bf06f6a6f1be0802ad7b761138ecba568814008aDale Johannesen TII->RemoveBranch(*PMBB); 13304e3f125e184f96ae72f2c44d16cafe0d44158283Dan Gohman NewCurCond.clear(); 13315b2749abf585f9e28656c289001c2327eed401afBill Wendling TII->InsertBranch(*PMBB, NewCurTBB, 0, NewCurCond, pdl); 1332bf06f6a6f1be0802ad7b761138ecba568814008aDale Johannesen MadeChange = true; 1333bf06f6a6f1be0802ad7b761138ecba568814008aDale Johannesen ++NumBranchOpts; 13342210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman PMBB->CorrectExtraCFGEdges(NewCurTBB, 0, false); 1335bf06f6a6f1be0802ad7b761138ecba568814008aDale Johannesen } 1336cf420cca572b061fdd63587cb90904c641b6e216Chris Lattner } 13374bc135e93beebdcb3b9c44745c5ccbc91199ac0bChris Lattner } 133821ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner 1339cf420cca572b061fdd63587cb90904c641b6e216Chris Lattner // Change any jumptables to go to the new MBB. 1340071c62fad0b25ad4131e7f984173a796c1e63f61Chris Lattner if (MachineJumpTableInfo *MJTI = MF.getJumpTableInfo()) 1341071c62fad0b25ad4131e7f984173a796c1e63f61Chris Lattner MJTI->ReplaceMBBInJumpTables(MBB, CurTBB); 1342cf420cca572b061fdd63587cb90904c641b6e216Chris Lattner if (DidChange) { 1343cf420cca572b061fdd63587cb90904c641b6e216Chris Lattner ++NumBranchOpts; 1344cf420cca572b061fdd63587cb90904c641b6e216Chris Lattner MadeChange = true; 1345030a0a0cdb38924e55773a8e0b5fe7347aa664aaEvan Cheng if (!HasBranchToSelf) return MadeChange; 1346cf420cca572b061fdd63587cb90904c641b6e216Chris Lattner } 13474bc135e93beebdcb3b9c44745c5ccbc91199ac0bChris Lattner } 134821ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner } 13494e3f125e184f96ae72f2c44d16cafe0d44158283Dan Gohman 1350386e29065db5b05b57440f6b2a6dfa1e7f29a00dChris Lattner // Add the branch back if the block is more than just an uncond branch. 13513bf912593301152b65accb9d9c37a95172f1df5aStuart Hastings TII->InsertBranch(*MBB, CurTBB, 0, CurCond, dl); 135221ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner } 13536b0e3f890779b7fc912bec8d40a9590e44742737Chris Lattner } 13546b0e3f890779b7fc912bec8d40a9590e44742737Chris Lattner 135543cf6c3939176e8d87719516f0b2e4c6c346f340Bill Wendling // If the prior block doesn't fall through into this block, and if this 135643cf6c3939176e8d87719516f0b2e4c6c346f340Bill Wendling // block doesn't fall through into some other block, see if we can find a 135743cf6c3939176e8d87719516f0b2e4c6c346f340Bill Wendling // place to move this block where a fall-through will happen. 135843cf6c3939176e8d87719516f0b2e4c6c346f340Bill Wendling if (!PrevBB.canFallThrough()) { 135943cf6c3939176e8d87719516f0b2e4c6c346f340Bill Wendling 136056ea69c3a251434db3fef489881368e29c95712dBob Wilson // Now we know that there was no fall-through into this block, check to 136156ea69c3a251434db3fef489881368e29c95712dBob Wilson // see if it has a fall-through into its successor. 136215acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson bool CurFallsThru = MBB->canFallThrough(); 136356ea69c3a251434db3fef489881368e29c95712dBob Wilson 136402b3f5ec4ac120d14a63f7fd4f4388b7d0ab6c22Jim Laskey if (!MBB->isLandingPad()) { 136502b3f5ec4ac120d14a63f7fd4f4388b7d0ab6c22Jim Laskey // Check all the predecessors of this block. If one of them has no fall 136602b3f5ec4ac120d14a63f7fd4f4388b7d0ab6c22Jim Laskey // throughs, move this block right after it. 136702b3f5ec4ac120d14a63f7fd4f4388b7d0ab6c22Jim Laskey for (MachineBasicBlock::pred_iterator PI = MBB->pred_begin(), 136802b3f5ec4ac120d14a63f7fd4f4388b7d0ab6c22Jim Laskey E = MBB->pred_end(); PI != E; ++PI) { 136902b3f5ec4ac120d14a63f7fd4f4388b7d0ab6c22Jim Laskey // Analyze the branch at the end of the pred. 137002b3f5ec4ac120d14a63f7fd4f4388b7d0ab6c22Jim Laskey MachineBasicBlock *PredBB = *PI; 137143cf6c3939176e8d87719516f0b2e4c6c346f340Bill Wendling MachineFunction::iterator PredFallthrough = PredBB; ++PredFallthrough; 1372408e9d166a66c8891637975921de2980c1940c3fBill Wendling MachineBasicBlock *PredTBB = 0, *PredFBB = 0; 13732210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman SmallVector<MachineOperand, 4> PredCond; 137443cf6c3939176e8d87719516f0b2e4c6c346f340Bill Wendling if (PredBB != MBB && !PredBB->canFallThrough() && 137543cf6c3939176e8d87719516f0b2e4c6c346f340Bill Wendling !TII->AnalyzeBranch(*PredBB, PredTBB, PredFBB, PredCond, true) 137676b38fcabeba725e166a2ff72c56fe31d784b229Dale Johannesen && (!CurFallsThru || !CurTBB || !CurFBB) 137702b3f5ec4ac120d14a63f7fd4f4388b7d0ab6c22Jim Laskey && (!CurFallsThru || MBB->getNumber() >= PredBB->getNumber())) { 137843cf6c3939176e8d87719516f0b2e4c6c346f340Bill Wendling // If the current block doesn't fall through, just move it. 137943cf6c3939176e8d87719516f0b2e4c6c346f340Bill Wendling // If the current block can fall through and does not end with a 138043cf6c3939176e8d87719516f0b2e4c6c346f340Bill Wendling // conditional branch, we need to append an unconditional jump to 138143cf6c3939176e8d87719516f0b2e4c6c346f340Bill Wendling // the (current) next block. To avoid a possible compile-time 138243cf6c3939176e8d87719516f0b2e4c6c346f340Bill Wendling // infinite loop, move blocks only backward in this case. 138343cf6c3939176e8d87719516f0b2e4c6c346f340Bill Wendling // Also, if there are already 2 branches here, we cannot add a third; 138443cf6c3939176e8d87719516f0b2e4c6c346f340Bill Wendling // this means we have the case 138543cf6c3939176e8d87719516f0b2e4c6c346f340Bill Wendling // Bcc next 138643cf6c3939176e8d87719516f0b2e4c6c346f340Bill Wendling // B elsewhere 138743cf6c3939176e8d87719516f0b2e4c6c346f340Bill Wendling // next: 138802b3f5ec4ac120d14a63f7fd4f4388b7d0ab6c22Jim Laskey if (CurFallsThru) { 138943cf6c3939176e8d87719516f0b2e4c6c346f340Bill Wendling MachineBasicBlock *NextBB = llvm::next(MachineFunction::iterator(MBB)); 139002b3f5ec4ac120d14a63f7fd4f4388b7d0ab6c22Jim Laskey CurCond.clear(); 13915b2749abf585f9e28656c289001c2327eed401afBill Wendling TII->InsertBranch(*MBB, NextBB, 0, CurCond, DebugLoc()); 139202b3f5ec4ac120d14a63f7fd4f4388b7d0ab6c22Jim Laskey } 139302b3f5ec4ac120d14a63f7fd4f4388b7d0ab6c22Jim Laskey MBB->moveAfter(PredBB); 139402b3f5ec4ac120d14a63f7fd4f4388b7d0ab6c22Jim Laskey MadeChange = true; 13952210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman goto ReoptimizeBlock; 13967d09784d3fc652131a2afbf06a0f2ed893837fb9Chris Lattner } 13976b0e3f890779b7fc912bec8d40a9590e44742737Chris Lattner } 13986b896cec8b703e08e5f3d809e086a39b6ebe6589Dale Johannesen } 13994e3f125e184f96ae72f2c44d16cafe0d44158283Dan Gohman 14006b896cec8b703e08e5f3d809e086a39b6ebe6589Dale Johannesen if (!CurFallsThru) { 14016b0e3f890779b7fc912bec8d40a9590e44742737Chris Lattner // Check all successors to see if we can move this block before it. 14026b0e3f890779b7fc912bec8d40a9590e44742737Chris Lattner for (MachineBasicBlock::succ_iterator SI = MBB->succ_begin(), 14036b0e3f890779b7fc912bec8d40a9590e44742737Chris Lattner E = MBB->succ_end(); SI != E; ++SI) { 14046b0e3f890779b7fc912bec8d40a9590e44742737Chris Lattner // Analyze the branch at the end of the block before the succ. 14056b0e3f890779b7fc912bec8d40a9590e44742737Chris Lattner MachineBasicBlock *SuccBB = *SI; 14066b0e3f890779b7fc912bec8d40a9590e44742737Chris Lattner MachineFunction::iterator SuccPrev = SuccBB; --SuccPrev; 14074e3f125e184f96ae72f2c44d16cafe0d44158283Dan Gohman 140877edc4b1b004726d96c932356750b9f3c96d74ddChris Lattner // If this block doesn't already fall-through to that successor, and if 140977edc4b1b004726d96c932356750b9f3c96d74ddChris Lattner // the succ doesn't already have a block that can fall through into it, 141077edc4b1b004726d96c932356750b9f3c96d74ddChris Lattner // and if the successor isn't an EH destination, we can arrange for the 141177edc4b1b004726d96c932356750b9f3c96d74ddChris Lattner // fallthrough to happen. 14122210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman if (SuccBB != MBB && &*SuccPrev != MBB && 141315acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson !SuccPrev->canFallThrough() && !CurUnAnalyzable && 141477edc4b1b004726d96c932356750b9f3c96d74ddChris Lattner !SuccBB->isLandingPad()) { 14156b0e3f890779b7fc912bec8d40a9590e44742737Chris Lattner MBB->moveBefore(SuccBB); 14167d09784d3fc652131a2afbf06a0f2ed893837fb9Chris Lattner MadeChange = true; 14172210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman goto ReoptimizeBlock; 14187d09784d3fc652131a2afbf06a0f2ed893837fb9Chris Lattner } 14197d09784d3fc652131a2afbf06a0f2ed893837fb9Chris Lattner } 14204e3f125e184f96ae72f2c44d16cafe0d44158283Dan Gohman 14216b0e3f890779b7fc912bec8d40a9590e44742737Chris Lattner // Okay, there is no really great place to put this block. If, however, 14226b0e3f890779b7fc912bec8d40a9590e44742737Chris Lattner // the block before this one would be a fall-through if this block were 14236b0e3f890779b7fc912bec8d40a9590e44742737Chris Lattner // removed, move this block to the end of the function. 1424fe586b3e3800b397256ca9ee6a2811fc6ce7dce9Bill Wendling MachineBasicBlock *PrevTBB = 0, *PrevFBB = 0; 14252210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman SmallVector<MachineOperand, 4> PrevCond; 1426d194498d2669e28cd8e85b0ceb7c69a7ec66da13Dan Gohman if (FallThrough != MF.end() && 14272210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman !TII->AnalyzeBranch(PrevBB, PrevTBB, PrevFBB, PrevCond, true) && 14286b0e3f890779b7fc912bec8d40a9590e44742737Chris Lattner PrevBB.isSuccessor(FallThrough)) { 1429d194498d2669e28cd8e85b0ceb7c69a7ec66da13Dan Gohman MBB->moveAfter(--MF.end()); 14306b0e3f890779b7fc912bec8d40a9590e44742737Chris Lattner MadeChange = true; 1431030a0a0cdb38924e55773a8e0b5fe7347aa664aaEvan Cheng return MadeChange; 14326b0e3f890779b7fc912bec8d40a9590e44742737Chris Lattner } 14337d09784d3fc652131a2afbf06a0f2ed893837fb9Chris Lattner } 143421ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner } 1435030a0a0cdb38924e55773a8e0b5fe7347aa664aaEvan Cheng 1436030a0a0cdb38924e55773a8e0b5fe7347aa664aaEvan Cheng return MadeChange; 143721ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner} 1438cbc988be22bc9411d95215c8b7251b5f85710674Evan Cheng 1439cbc988be22bc9411d95215c8b7251b5f85710674Evan Cheng//===----------------------------------------------------------------------===// 1440cbc988be22bc9411d95215c8b7251b5f85710674Evan Cheng// Hoist Common Code 1441cbc988be22bc9411d95215c8b7251b5f85710674Evan Cheng//===----------------------------------------------------------------------===// 1442cbc988be22bc9411d95215c8b7251b5f85710674Evan Cheng 1443cbc988be22bc9411d95215c8b7251b5f85710674Evan Cheng/// HoistCommonCode - Hoist common instruction sequences at the start of basic 1444cbc988be22bc9411d95215c8b7251b5f85710674Evan Cheng/// blocks to their common predecessor. 1445cbc988be22bc9411d95215c8b7251b5f85710674Evan Chengbool BranchFolder::HoistCommonCode(MachineFunction &MF) { 1446cbc988be22bc9411d95215c8b7251b5f85710674Evan Cheng bool MadeChange = false; 1447cbc988be22bc9411d95215c8b7251b5f85710674Evan Cheng for (MachineFunction::iterator I = MF.begin(), E = MF.end(); I != E; ) { 1448cbc988be22bc9411d95215c8b7251b5f85710674Evan Cheng MachineBasicBlock *MBB = I++; 1449cbc988be22bc9411d95215c8b7251b5f85710674Evan Cheng MadeChange |= HoistCommonCodeInSuccs(MBB); 1450cbc988be22bc9411d95215c8b7251b5f85710674Evan Cheng } 1451cbc988be22bc9411d95215c8b7251b5f85710674Evan Cheng 1452cbc988be22bc9411d95215c8b7251b5f85710674Evan Cheng return MadeChange; 1453cbc988be22bc9411d95215c8b7251b5f85710674Evan Cheng} 1454cbc988be22bc9411d95215c8b7251b5f85710674Evan Cheng 1455cbc988be22bc9411d95215c8b7251b5f85710674Evan Cheng/// findFalseBlock - BB has a fallthrough. Find its 'false' successor given 1456cbc988be22bc9411d95215c8b7251b5f85710674Evan Cheng/// its 'true' successor. 1457cbc988be22bc9411d95215c8b7251b5f85710674Evan Chengstatic MachineBasicBlock *findFalseBlock(MachineBasicBlock *BB, 1458cbc988be22bc9411d95215c8b7251b5f85710674Evan Cheng MachineBasicBlock *TrueBB) { 1459cbc988be22bc9411d95215c8b7251b5f85710674Evan Cheng for (MachineBasicBlock::succ_iterator SI = BB->succ_begin(), 1460cbc988be22bc9411d95215c8b7251b5f85710674Evan Cheng E = BB->succ_end(); SI != E; ++SI) { 1461cbc988be22bc9411d95215c8b7251b5f85710674Evan Cheng MachineBasicBlock *SuccBB = *SI; 1462cbc988be22bc9411d95215c8b7251b5f85710674Evan Cheng if (SuccBB != TrueBB) 1463cbc988be22bc9411d95215c8b7251b5f85710674Evan Cheng return SuccBB; 1464cbc988be22bc9411d95215c8b7251b5f85710674Evan Cheng } 1465cbc988be22bc9411d95215c8b7251b5f85710674Evan Cheng return NULL; 1466cbc988be22bc9411d95215c8b7251b5f85710674Evan Cheng} 1467cbc988be22bc9411d95215c8b7251b5f85710674Evan Cheng 1468cbc988be22bc9411d95215c8b7251b5f85710674Evan Cheng/// findHoistingInsertPosAndDeps - Find the location to move common instructions 1469d9b0b025612992a0b724eeca8bdf10b1d7a5c355Benjamin Kramer/// in successors to. The location is usually just before the terminator, 1470cbc988be22bc9411d95215c8b7251b5f85710674Evan Cheng/// however if the terminator is a conditional branch and its previous 1471cbc988be22bc9411d95215c8b7251b5f85710674Evan Cheng/// instruction is the flag setting instruction, the previous instruction is 1472cbc988be22bc9411d95215c8b7251b5f85710674Evan Cheng/// the preferred location. This function also gathers uses and defs of the 1473cbc988be22bc9411d95215c8b7251b5f85710674Evan Cheng/// instructions from the insertion point to the end of the block. The data is 1474cbc988be22bc9411d95215c8b7251b5f85710674Evan Cheng/// used by HoistCommonCodeInSuccs to ensure safety. 1475cbc988be22bc9411d95215c8b7251b5f85710674Evan Chengstatic 1476cbc988be22bc9411d95215c8b7251b5f85710674Evan ChengMachineBasicBlock::iterator findHoistingInsertPosAndDeps(MachineBasicBlock *MBB, 1477cbc988be22bc9411d95215c8b7251b5f85710674Evan Cheng const TargetInstrInfo *TII, 1478cbc988be22bc9411d95215c8b7251b5f85710674Evan Cheng const TargetRegisterInfo *TRI, 1479cbc988be22bc9411d95215c8b7251b5f85710674Evan Cheng SmallSet<unsigned,4> &Uses, 1480cbc988be22bc9411d95215c8b7251b5f85710674Evan Cheng SmallSet<unsigned,4> &Defs) { 1481cbc988be22bc9411d95215c8b7251b5f85710674Evan Cheng MachineBasicBlock::iterator Loc = MBB->getFirstTerminator(); 1482cbc988be22bc9411d95215c8b7251b5f85710674Evan Cheng if (!TII->isUnpredicatedTerminator(Loc)) 1483cbc988be22bc9411d95215c8b7251b5f85710674Evan Cheng return MBB->end(); 1484cbc988be22bc9411d95215c8b7251b5f85710674Evan Cheng 1485cbc988be22bc9411d95215c8b7251b5f85710674Evan Cheng for (unsigned i = 0, e = Loc->getNumOperands(); i != e; ++i) { 1486cbc988be22bc9411d95215c8b7251b5f85710674Evan Cheng const MachineOperand &MO = Loc->getOperand(i); 1487cbc988be22bc9411d95215c8b7251b5f85710674Evan Cheng if (!MO.isReg()) 1488cbc988be22bc9411d95215c8b7251b5f85710674Evan Cheng continue; 1489cbc988be22bc9411d95215c8b7251b5f85710674Evan Cheng unsigned Reg = MO.getReg(); 1490cbc988be22bc9411d95215c8b7251b5f85710674Evan Cheng if (!Reg) 1491cbc988be22bc9411d95215c8b7251b5f85710674Evan Cheng continue; 1492cbc988be22bc9411d95215c8b7251b5f85710674Evan Cheng if (MO.isUse()) { 1493f152fe8d487c46873bbdd4abab43200f783e978bJakob Stoklund Olesen for (MCRegAliasIterator AI(Reg, TRI, true); AI.isValid(); ++AI) 1494f152fe8d487c46873bbdd4abab43200f783e978bJakob Stoklund Olesen Uses.insert(*AI); 1495cbc988be22bc9411d95215c8b7251b5f85710674Evan Cheng } else if (!MO.isDead()) 1496cbc988be22bc9411d95215c8b7251b5f85710674Evan Cheng // Don't try to hoist code in the rare case the terminator defines a 1497cbc988be22bc9411d95215c8b7251b5f85710674Evan Cheng // register that is later used. 1498cbc988be22bc9411d95215c8b7251b5f85710674Evan Cheng return MBB->end(); 1499cbc988be22bc9411d95215c8b7251b5f85710674Evan Cheng } 1500cbc988be22bc9411d95215c8b7251b5f85710674Evan Cheng 1501cbc988be22bc9411d95215c8b7251b5f85710674Evan Cheng if (Uses.empty()) 1502cbc988be22bc9411d95215c8b7251b5f85710674Evan Cheng return Loc; 1503cbc988be22bc9411d95215c8b7251b5f85710674Evan Cheng if (Loc == MBB->begin()) 1504cbc988be22bc9411d95215c8b7251b5f85710674Evan Cheng return MBB->end(); 1505cbc988be22bc9411d95215c8b7251b5f85710674Evan Cheng 1506cbc988be22bc9411d95215c8b7251b5f85710674Evan Cheng // The terminator is probably a conditional branch, try not to separate the 1507cbc988be22bc9411d95215c8b7251b5f85710674Evan Cheng // branch from condition setting instruction. 1508cbc988be22bc9411d95215c8b7251b5f85710674Evan Cheng MachineBasicBlock::iterator PI = Loc; 1509cbc988be22bc9411d95215c8b7251b5f85710674Evan Cheng --PI; 1510cbc988be22bc9411d95215c8b7251b5f85710674Evan Cheng while (PI != MBB->begin() && Loc->isDebugValue()) 1511cbc988be22bc9411d95215c8b7251b5f85710674Evan Cheng --PI; 1512cbc988be22bc9411d95215c8b7251b5f85710674Evan Cheng 1513cbc988be22bc9411d95215c8b7251b5f85710674Evan Cheng bool IsDef = false; 1514cbc988be22bc9411d95215c8b7251b5f85710674Evan Cheng for (unsigned i = 0, e = PI->getNumOperands(); !IsDef && i != e; ++i) { 1515cbc988be22bc9411d95215c8b7251b5f85710674Evan Cheng const MachineOperand &MO = PI->getOperand(i); 1516a230262791397c88beeb7ca9bb97c8a8a026e848Jakob Stoklund Olesen // If PI has a regmask operand, it is probably a call. Separate away. 1517a230262791397c88beeb7ca9bb97c8a8a026e848Jakob Stoklund Olesen if (MO.isRegMask()) 1518a230262791397c88beeb7ca9bb97c8a8a026e848Jakob Stoklund Olesen return Loc; 1519cbc988be22bc9411d95215c8b7251b5f85710674Evan Cheng if (!MO.isReg() || MO.isUse()) 1520cbc988be22bc9411d95215c8b7251b5f85710674Evan Cheng continue; 1521cbc988be22bc9411d95215c8b7251b5f85710674Evan Cheng unsigned Reg = MO.getReg(); 1522cbc988be22bc9411d95215c8b7251b5f85710674Evan Cheng if (!Reg) 1523cbc988be22bc9411d95215c8b7251b5f85710674Evan Cheng continue; 1524cbc988be22bc9411d95215c8b7251b5f85710674Evan Cheng if (Uses.count(Reg)) 1525cbc988be22bc9411d95215c8b7251b5f85710674Evan Cheng IsDef = true; 1526cbc988be22bc9411d95215c8b7251b5f85710674Evan Cheng } 1527cbc988be22bc9411d95215c8b7251b5f85710674Evan Cheng if (!IsDef) 1528cbc988be22bc9411d95215c8b7251b5f85710674Evan Cheng // The condition setting instruction is not just before the conditional 1529cbc988be22bc9411d95215c8b7251b5f85710674Evan Cheng // branch. 1530cbc988be22bc9411d95215c8b7251b5f85710674Evan Cheng return Loc; 1531cbc988be22bc9411d95215c8b7251b5f85710674Evan Cheng 1532cbc988be22bc9411d95215c8b7251b5f85710674Evan Cheng // Be conservative, don't insert instruction above something that may have 1533cbc988be22bc9411d95215c8b7251b5f85710674Evan Cheng // side-effects. And since it's potentially bad to separate flag setting 1534cbc988be22bc9411d95215c8b7251b5f85710674Evan Cheng // instruction from the conditional branch, just abort the optimization 1535cbc988be22bc9411d95215c8b7251b5f85710674Evan Cheng // completely. 1536cbc988be22bc9411d95215c8b7251b5f85710674Evan Cheng // Also avoid moving code above predicated instruction since it's hard to 1537cbc988be22bc9411d95215c8b7251b5f85710674Evan Cheng // reason about register liveness with predicated instruction. 1538cbc988be22bc9411d95215c8b7251b5f85710674Evan Cheng bool DontMoveAcrossStore = true; 1539cbc988be22bc9411d95215c8b7251b5f85710674Evan Cheng if (!PI->isSafeToMove(TII, 0, DontMoveAcrossStore) || 1540cbc988be22bc9411d95215c8b7251b5f85710674Evan Cheng TII->isPredicated(PI)) 1541cbc988be22bc9411d95215c8b7251b5f85710674Evan Cheng return MBB->end(); 1542cbc988be22bc9411d95215c8b7251b5f85710674Evan Cheng 1543cbc988be22bc9411d95215c8b7251b5f85710674Evan Cheng 1544cbc988be22bc9411d95215c8b7251b5f85710674Evan Cheng // Find out what registers are live. Note this routine is ignoring other live 1545cbc988be22bc9411d95215c8b7251b5f85710674Evan Cheng // registers which are only used by instructions in successor blocks. 1546cbc988be22bc9411d95215c8b7251b5f85710674Evan Cheng for (unsigned i = 0, e = PI->getNumOperands(); i != e; ++i) { 1547cbc988be22bc9411d95215c8b7251b5f85710674Evan Cheng const MachineOperand &MO = PI->getOperand(i); 1548cbc988be22bc9411d95215c8b7251b5f85710674Evan Cheng if (!MO.isReg()) 1549cbc988be22bc9411d95215c8b7251b5f85710674Evan Cheng continue; 1550cbc988be22bc9411d95215c8b7251b5f85710674Evan Cheng unsigned Reg = MO.getReg(); 1551cbc988be22bc9411d95215c8b7251b5f85710674Evan Cheng if (!Reg) 1552cbc988be22bc9411d95215c8b7251b5f85710674Evan Cheng continue; 1553cbc988be22bc9411d95215c8b7251b5f85710674Evan Cheng if (MO.isUse()) { 1554f152fe8d487c46873bbdd4abab43200f783e978bJakob Stoklund Olesen for (MCRegAliasIterator AI(Reg, TRI, true); AI.isValid(); ++AI) 1555f152fe8d487c46873bbdd4abab43200f783e978bJakob Stoklund Olesen Uses.insert(*AI); 1556cbc988be22bc9411d95215c8b7251b5f85710674Evan Cheng } else { 155705d96f98cbd96dab7f4ea1ea4ebe4285597e7e88Benjamin Kramer if (Uses.erase(Reg)) { 1558396618b43a85e12d290a90b181c6af5d7c0c5f11Jakob Stoklund Olesen for (MCSubRegIterator SubRegs(Reg, TRI); SubRegs.isValid(); ++SubRegs) 1559396618b43a85e12d290a90b181c6af5d7c0c5f11Jakob Stoklund Olesen Uses.erase(*SubRegs); // Use sub-registers to be conservative 1560cbc988be22bc9411d95215c8b7251b5f85710674Evan Cheng } 1561f152fe8d487c46873bbdd4abab43200f783e978bJakob Stoklund Olesen for (MCRegAliasIterator AI(Reg, TRI, true); AI.isValid(); ++AI) 1562f152fe8d487c46873bbdd4abab43200f783e978bJakob Stoklund Olesen Defs.insert(*AI); 1563cbc988be22bc9411d95215c8b7251b5f85710674Evan Cheng } 1564cbc988be22bc9411d95215c8b7251b5f85710674Evan Cheng } 1565cbc988be22bc9411d95215c8b7251b5f85710674Evan Cheng 1566cbc988be22bc9411d95215c8b7251b5f85710674Evan Cheng return PI; 1567cbc988be22bc9411d95215c8b7251b5f85710674Evan Cheng} 1568cbc988be22bc9411d95215c8b7251b5f85710674Evan Cheng 1569cbc988be22bc9411d95215c8b7251b5f85710674Evan Cheng/// HoistCommonCodeInSuccs - If the successors of MBB has common instruction 1570cbc988be22bc9411d95215c8b7251b5f85710674Evan Cheng/// sequence at the start of the function, move the instructions before MBB 1571cbc988be22bc9411d95215c8b7251b5f85710674Evan Cheng/// terminator if it's legal. 1572cbc988be22bc9411d95215c8b7251b5f85710674Evan Chengbool BranchFolder::HoistCommonCodeInSuccs(MachineBasicBlock *MBB) { 1573cbc988be22bc9411d95215c8b7251b5f85710674Evan Cheng MachineBasicBlock *TBB = 0, *FBB = 0; 1574cbc988be22bc9411d95215c8b7251b5f85710674Evan Cheng SmallVector<MachineOperand, 4> Cond; 1575cbc988be22bc9411d95215c8b7251b5f85710674Evan Cheng if (TII->AnalyzeBranch(*MBB, TBB, FBB, Cond, true) || !TBB || Cond.empty()) 1576cbc988be22bc9411d95215c8b7251b5f85710674Evan Cheng return false; 1577cbc988be22bc9411d95215c8b7251b5f85710674Evan Cheng 1578cbc988be22bc9411d95215c8b7251b5f85710674Evan Cheng if (!FBB) FBB = findFalseBlock(MBB, TBB); 1579cbc988be22bc9411d95215c8b7251b5f85710674Evan Cheng if (!FBB) 1580cbc988be22bc9411d95215c8b7251b5f85710674Evan Cheng // Malformed bcc? True and false blocks are the same? 1581cbc988be22bc9411d95215c8b7251b5f85710674Evan Cheng return false; 1582cbc988be22bc9411d95215c8b7251b5f85710674Evan Cheng 1583cbc988be22bc9411d95215c8b7251b5f85710674Evan Cheng // Restrict the optimization to cases where MBB is the only predecessor, 1584cbc988be22bc9411d95215c8b7251b5f85710674Evan Cheng // it is an obvious win. 1585cbc988be22bc9411d95215c8b7251b5f85710674Evan Cheng if (TBB->pred_size() > 1 || FBB->pred_size() > 1) 1586cbc988be22bc9411d95215c8b7251b5f85710674Evan Cheng return false; 1587cbc988be22bc9411d95215c8b7251b5f85710674Evan Cheng 1588cbc988be22bc9411d95215c8b7251b5f85710674Evan Cheng // Find a suitable position to hoist the common instructions to. Also figure 1589cbc988be22bc9411d95215c8b7251b5f85710674Evan Cheng // out which registers are used or defined by instructions from the insertion 1590cbc988be22bc9411d95215c8b7251b5f85710674Evan Cheng // point to the end of the block. 1591cbc988be22bc9411d95215c8b7251b5f85710674Evan Cheng SmallSet<unsigned, 4> Uses, Defs; 1592cbc988be22bc9411d95215c8b7251b5f85710674Evan Cheng MachineBasicBlock::iterator Loc = 1593cbc988be22bc9411d95215c8b7251b5f85710674Evan Cheng findHoistingInsertPosAndDeps(MBB, TII, TRI, Uses, Defs); 1594cbc988be22bc9411d95215c8b7251b5f85710674Evan Cheng if (Loc == MBB->end()) 1595cbc988be22bc9411d95215c8b7251b5f85710674Evan Cheng return false; 1596cbc988be22bc9411d95215c8b7251b5f85710674Evan Cheng 1597cbc988be22bc9411d95215c8b7251b5f85710674Evan Cheng bool HasDups = false; 15987139d3516526317497e70348e33a57b52ddc053cEvan Cheng SmallVector<unsigned, 4> LocalDefs; 15997139d3516526317497e70348e33a57b52ddc053cEvan Cheng SmallSet<unsigned, 4> LocalDefsSet; 1600cbc988be22bc9411d95215c8b7251b5f85710674Evan Cheng MachineBasicBlock::iterator TIB = TBB->begin(); 1601cbc988be22bc9411d95215c8b7251b5f85710674Evan Cheng MachineBasicBlock::iterator FIB = FBB->begin(); 1602cbc988be22bc9411d95215c8b7251b5f85710674Evan Cheng MachineBasicBlock::iterator TIE = TBB->end(); 1603cbc988be22bc9411d95215c8b7251b5f85710674Evan Cheng MachineBasicBlock::iterator FIE = FBB->end(); 1604cbc988be22bc9411d95215c8b7251b5f85710674Evan Cheng while (TIB != TIE && FIB != FIE) { 1605cbc988be22bc9411d95215c8b7251b5f85710674Evan Cheng // Skip dbg_value instructions. These do not count. 1606cbc988be22bc9411d95215c8b7251b5f85710674Evan Cheng if (TIB->isDebugValue()) { 1607cbc988be22bc9411d95215c8b7251b5f85710674Evan Cheng while (TIB != TIE && TIB->isDebugValue()) 1608cbc988be22bc9411d95215c8b7251b5f85710674Evan Cheng ++TIB; 1609cbc988be22bc9411d95215c8b7251b5f85710674Evan Cheng if (TIB == TIE) 1610cbc988be22bc9411d95215c8b7251b5f85710674Evan Cheng break; 1611cbc988be22bc9411d95215c8b7251b5f85710674Evan Cheng } 1612cbc988be22bc9411d95215c8b7251b5f85710674Evan Cheng if (FIB->isDebugValue()) { 1613cbc988be22bc9411d95215c8b7251b5f85710674Evan Cheng while (FIB != FIE && FIB->isDebugValue()) 1614cbc988be22bc9411d95215c8b7251b5f85710674Evan Cheng ++FIB; 1615cbc988be22bc9411d95215c8b7251b5f85710674Evan Cheng if (FIB == FIE) 1616cbc988be22bc9411d95215c8b7251b5f85710674Evan Cheng break; 1617cbc988be22bc9411d95215c8b7251b5f85710674Evan Cheng } 1618cbc988be22bc9411d95215c8b7251b5f85710674Evan Cheng if (!TIB->isIdenticalTo(FIB, MachineInstr::CheckKillDead)) 1619cbc988be22bc9411d95215c8b7251b5f85710674Evan Cheng break; 1620cbc988be22bc9411d95215c8b7251b5f85710674Evan Cheng 1621cbc988be22bc9411d95215c8b7251b5f85710674Evan Cheng if (TII->isPredicated(TIB)) 1622cbc988be22bc9411d95215c8b7251b5f85710674Evan Cheng // Hard to reason about register liveness with predicated instruction. 1623cbc988be22bc9411d95215c8b7251b5f85710674Evan Cheng break; 1624cbc988be22bc9411d95215c8b7251b5f85710674Evan Cheng 1625cbc988be22bc9411d95215c8b7251b5f85710674Evan Cheng bool IsSafe = true; 1626cbc988be22bc9411d95215c8b7251b5f85710674Evan Cheng for (unsigned i = 0, e = TIB->getNumOperands(); i != e; ++i) { 1627cbc988be22bc9411d95215c8b7251b5f85710674Evan Cheng MachineOperand &MO = TIB->getOperand(i); 1628a230262791397c88beeb7ca9bb97c8a8a026e848Jakob Stoklund Olesen // Don't attempt to hoist instructions with register masks. 1629a230262791397c88beeb7ca9bb97c8a8a026e848Jakob Stoklund Olesen if (MO.isRegMask()) { 1630a230262791397c88beeb7ca9bb97c8a8a026e848Jakob Stoklund Olesen IsSafe = false; 1631a230262791397c88beeb7ca9bb97c8a8a026e848Jakob Stoklund Olesen break; 1632a230262791397c88beeb7ca9bb97c8a8a026e848Jakob Stoklund Olesen } 1633cbc988be22bc9411d95215c8b7251b5f85710674Evan Cheng if (!MO.isReg()) 1634cbc988be22bc9411d95215c8b7251b5f85710674Evan Cheng continue; 1635cbc988be22bc9411d95215c8b7251b5f85710674Evan Cheng unsigned Reg = MO.getReg(); 1636cbc988be22bc9411d95215c8b7251b5f85710674Evan Cheng if (!Reg) 1637cbc988be22bc9411d95215c8b7251b5f85710674Evan Cheng continue; 1638cbc988be22bc9411d95215c8b7251b5f85710674Evan Cheng if (MO.isDef()) { 1639cbc988be22bc9411d95215c8b7251b5f85710674Evan Cheng if (Uses.count(Reg)) { 1640cbc988be22bc9411d95215c8b7251b5f85710674Evan Cheng // Avoid clobbering a register that's used by the instruction at 1641cbc988be22bc9411d95215c8b7251b5f85710674Evan Cheng // the point of insertion. 1642cbc988be22bc9411d95215c8b7251b5f85710674Evan Cheng IsSafe = false; 1643cbc988be22bc9411d95215c8b7251b5f85710674Evan Cheng break; 1644cbc988be22bc9411d95215c8b7251b5f85710674Evan Cheng } 1645cbc988be22bc9411d95215c8b7251b5f85710674Evan Cheng 1646cbc988be22bc9411d95215c8b7251b5f85710674Evan Cheng if (Defs.count(Reg) && !MO.isDead()) { 1647cbc988be22bc9411d95215c8b7251b5f85710674Evan Cheng // Don't hoist the instruction if the def would be clobber by the 1648cbc988be22bc9411d95215c8b7251b5f85710674Evan Cheng // instruction at the point insertion. FIXME: This is overly 1649cbc988be22bc9411d95215c8b7251b5f85710674Evan Cheng // conservative. It should be possible to hoist the instructions 1650cbc988be22bc9411d95215c8b7251b5f85710674Evan Cheng // in BB2 in the following example: 1651cbc988be22bc9411d95215c8b7251b5f85710674Evan Cheng // BB1: 1652cbc988be22bc9411d95215c8b7251b5f85710674Evan Cheng // r1, eflag = op1 r2, r3 1653cbc988be22bc9411d95215c8b7251b5f85710674Evan Cheng // brcc eflag 1654cbc988be22bc9411d95215c8b7251b5f85710674Evan Cheng // 1655cbc988be22bc9411d95215c8b7251b5f85710674Evan Cheng // BB2: 1656cbc988be22bc9411d95215c8b7251b5f85710674Evan Cheng // r1 = op2, ... 1657cbc988be22bc9411d95215c8b7251b5f85710674Evan Cheng // = op3, r1<kill> 1658cbc988be22bc9411d95215c8b7251b5f85710674Evan Cheng IsSafe = false; 1659cbc988be22bc9411d95215c8b7251b5f85710674Evan Cheng break; 1660cbc988be22bc9411d95215c8b7251b5f85710674Evan Cheng } 16617139d3516526317497e70348e33a57b52ddc053cEvan Cheng } else if (!LocalDefsSet.count(Reg)) { 1662cbc988be22bc9411d95215c8b7251b5f85710674Evan Cheng if (Defs.count(Reg)) { 1663cbc988be22bc9411d95215c8b7251b5f85710674Evan Cheng // Use is defined by the instruction at the point of insertion. 1664cbc988be22bc9411d95215c8b7251b5f85710674Evan Cheng IsSafe = false; 1665cbc988be22bc9411d95215c8b7251b5f85710674Evan Cheng break; 1666cbc988be22bc9411d95215c8b7251b5f85710674Evan Cheng } 1667c16c25fbc3b53da99dcaf27685a6116249f79b30Evan Cheng 1668c16c25fbc3b53da99dcaf27685a6116249f79b30Evan Cheng if (MO.isKill() && Uses.count(Reg)) 1669c16c25fbc3b53da99dcaf27685a6116249f79b30Evan Cheng // Kills a register that's read by the instruction at the point of 1670c16c25fbc3b53da99dcaf27685a6116249f79b30Evan Cheng // insertion. Remove the kill marker. 1671c16c25fbc3b53da99dcaf27685a6116249f79b30Evan Cheng MO.setIsKill(false); 1672cbc988be22bc9411d95215c8b7251b5f85710674Evan Cheng } 1673cbc988be22bc9411d95215c8b7251b5f85710674Evan Cheng } 1674cbc988be22bc9411d95215c8b7251b5f85710674Evan Cheng if (!IsSafe) 1675cbc988be22bc9411d95215c8b7251b5f85710674Evan Cheng break; 1676cbc988be22bc9411d95215c8b7251b5f85710674Evan Cheng 1677cbc988be22bc9411d95215c8b7251b5f85710674Evan Cheng bool DontMoveAcrossStore = true; 1678cbc988be22bc9411d95215c8b7251b5f85710674Evan Cheng if (!TIB->isSafeToMove(TII, 0, DontMoveAcrossStore)) 1679cbc988be22bc9411d95215c8b7251b5f85710674Evan Cheng break; 1680cbc988be22bc9411d95215c8b7251b5f85710674Evan Cheng 168154cfeda74574ee167fc1261ddc71d64ee94add11Jakob Stoklund Olesen // Remove kills from LocalDefsSet, these registers had short live ranges. 168254cfeda74574ee167fc1261ddc71d64ee94add11Jakob Stoklund Olesen for (unsigned i = 0, e = TIB->getNumOperands(); i != e; ++i) { 168354cfeda74574ee167fc1261ddc71d64ee94add11Jakob Stoklund Olesen MachineOperand &MO = TIB->getOperand(i); 168454cfeda74574ee167fc1261ddc71d64ee94add11Jakob Stoklund Olesen if (!MO.isReg() || !MO.isUse() || !MO.isKill()) 168554cfeda74574ee167fc1261ddc71d64ee94add11Jakob Stoklund Olesen continue; 168654cfeda74574ee167fc1261ddc71d64ee94add11Jakob Stoklund Olesen unsigned Reg = MO.getReg(); 168754cfeda74574ee167fc1261ddc71d64ee94add11Jakob Stoklund Olesen if (!Reg || !LocalDefsSet.count(Reg)) 168854cfeda74574ee167fc1261ddc71d64ee94add11Jakob Stoklund Olesen continue; 1689396618b43a85e12d290a90b181c6af5d7c0c5f11Jakob Stoklund Olesen for (MCRegAliasIterator AI(Reg, TRI, true); AI.isValid(); ++AI) 1690396618b43a85e12d290a90b181c6af5d7c0c5f11Jakob Stoklund Olesen LocalDefsSet.erase(*AI); 169154cfeda74574ee167fc1261ddc71d64ee94add11Jakob Stoklund Olesen } 169254cfeda74574ee167fc1261ddc71d64ee94add11Jakob Stoklund Olesen 16937139d3516526317497e70348e33a57b52ddc053cEvan Cheng // Track local defs so we can update liveins. 16947139d3516526317497e70348e33a57b52ddc053cEvan Cheng for (unsigned i = 0, e = TIB->getNumOperands(); i != e; ++i) { 16957139d3516526317497e70348e33a57b52ddc053cEvan Cheng MachineOperand &MO = TIB->getOperand(i); 169654cfeda74574ee167fc1261ddc71d64ee94add11Jakob Stoklund Olesen if (!MO.isReg() || !MO.isDef() || MO.isDead()) 16977139d3516526317497e70348e33a57b52ddc053cEvan Cheng continue; 16987139d3516526317497e70348e33a57b52ddc053cEvan Cheng unsigned Reg = MO.getReg(); 16997139d3516526317497e70348e33a57b52ddc053cEvan Cheng if (!Reg) 17007139d3516526317497e70348e33a57b52ddc053cEvan Cheng continue; 170154cfeda74574ee167fc1261ddc71d64ee94add11Jakob Stoklund Olesen LocalDefs.push_back(Reg); 1702396618b43a85e12d290a90b181c6af5d7c0c5f11Jakob Stoklund Olesen for (MCRegAliasIterator AI(Reg, TRI, true); AI.isValid(); ++AI) 1703396618b43a85e12d290a90b181c6af5d7c0c5f11Jakob Stoklund Olesen LocalDefsSet.insert(*AI); 17047139d3516526317497e70348e33a57b52ddc053cEvan Cheng } 17057139d3516526317497e70348e33a57b52ddc053cEvan Cheng 170690f20044ade3712c8b0c3f4ebe47d57ad15ae6ceChad Rosier HasDups = true; 1707cbc988be22bc9411d95215c8b7251b5f85710674Evan Cheng ++TIB; 1708cbc988be22bc9411d95215c8b7251b5f85710674Evan Cheng ++FIB; 1709cbc988be22bc9411d95215c8b7251b5f85710674Evan Cheng } 1710cbc988be22bc9411d95215c8b7251b5f85710674Evan Cheng 1711cbc988be22bc9411d95215c8b7251b5f85710674Evan Cheng if (!HasDups) 1712cbc988be22bc9411d95215c8b7251b5f85710674Evan Cheng return false; 1713cbc988be22bc9411d95215c8b7251b5f85710674Evan Cheng 1714cbc988be22bc9411d95215c8b7251b5f85710674Evan Cheng MBB->splice(Loc, TBB, TBB->begin(), TIB); 1715cbc988be22bc9411d95215c8b7251b5f85710674Evan Cheng FBB->erase(FBB->begin(), FIB); 17167139d3516526317497e70348e33a57b52ddc053cEvan Cheng 17177139d3516526317497e70348e33a57b52ddc053cEvan Cheng // Update livein's. 17187139d3516526317497e70348e33a57b52ddc053cEvan Cheng for (unsigned i = 0, e = LocalDefs.size(); i != e; ++i) { 17197139d3516526317497e70348e33a57b52ddc053cEvan Cheng unsigned Def = LocalDefs[i]; 17207139d3516526317497e70348e33a57b52ddc053cEvan Cheng if (LocalDefsSet.count(Def)) { 17217139d3516526317497e70348e33a57b52ddc053cEvan Cheng TBB->addLiveIn(Def); 17227139d3516526317497e70348e33a57b52ddc053cEvan Cheng FBB->addLiveIn(Def); 17237139d3516526317497e70348e33a57b52ddc053cEvan Cheng } 17247139d3516526317497e70348e33a57b52ddc053cEvan Cheng } 17257139d3516526317497e70348e33a57b52ddc053cEvan Cheng 1726cbc988be22bc9411d95215c8b7251b5f85710674Evan Cheng ++NumHoist; 1727cbc988be22bc9411d95215c8b7251b5f85710674Evan Cheng return true; 1728cbc988be22bc9411d95215c8b7251b5f85710674Evan Cheng} 1729