BranchFolding.cpp revision c5cf227f3dac755508928b9dee8ac6a45dcb4e4f
121ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner//===-- BranchFolding.cpp - Fold machine code branch instructions ---------===// 2edf128a7fa90f2b0b7ee24741a04a7ae1ecd6f7eMisha Brukman// 321ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner// The LLVM Compiler Infrastructure 421ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner// 54ee451de366474b9c228b4e5fa573795a715216dChris Lattner// This file is distributed under the University of Illinois Open Source 64ee451de366474b9c228b4e5fa573795a715216dChris Lattner// License. See LICENSE.TXT for details. 7edf128a7fa90f2b0b7ee24741a04a7ae1ecd6f7eMisha Brukman// 821ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner//===----------------------------------------------------------------------===// 921ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner// 1021ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner// This pass forwards branches to unconditional branches to make them branch 1121ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner// directly to the target block. This pass often results in dead MBB's, which 1221ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner// it then removes. 1321ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner// 1421ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner// Note that this pass must be run after register allocation, it cannot handle 1521ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner// SSA form. 1621ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner// 1721ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner//===----------------------------------------------------------------------===// 1821ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner 19f10a56a86f8ae32d0493c7de770493d55519b073Chris Lattner#define DEBUG_TYPE "branchfolding" 20030a0a0cdb38924e55773a8e0b5fe7347aa664aaEvan Cheng#include "BranchFolding.h" 212c04dae715b05017d7d2c19ab4f8cb37c1e650aeBob Wilson#include "llvm/Function.h" 2221ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner#include "llvm/CodeGen/Passes.h" 2344c3b9fdd416c79f4b67cde1aecfced5921efd81Jim Laskey#include "llvm/CodeGen/MachineModuleInfo.h" 2421ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner#include "llvm/CodeGen/MachineFunctionPass.h" 25c50ffcb7fcb7c1109fee2406e8f74d096f755f47Chris Lattner#include "llvm/CodeGen/MachineJumpTableInfo.h" 2669cb9b78f11d505f4351a269fc90e7b77fcda437Dale Johannesen#include "llvm/CodeGen/RegisterScavenging.h" 2721ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner#include "llvm/Target/TargetInstrInfo.h" 2821ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner#include "llvm/Target/TargetMachine.h" 296f0d024a534af18d9e60b3ea757376cd8a3a980eDan Gohman#include "llvm/Target/TargetRegisterInfo.h" 3012143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner#include "llvm/Support/CommandLine.h" 31f10a56a86f8ae32d0493c7de770493d55519b073Chris Lattner#include "llvm/Support/Debug.h" 32c25e7581b9b8088910da31702d4ca21c4734c6d7Torok Edwin#include "llvm/Support/ErrorHandling.h" 333403bcd8f943cb053a7d9bbf8eb8135407699afaBill Wendling#include "llvm/Support/raw_ostream.h" 3480b09fe8bc1d2755ef9a6b03b8862a657db42f06Evan Cheng#include "llvm/ADT/SmallSet.h" 352210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman#include "llvm/ADT/SetVector.h" 3612143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner#include "llvm/ADT/Statistic.h" 37551ccae044b0ff658fe629dd67edd5ffe75d10e8Reid Spencer#include "llvm/ADT/STLExtras.h" 38d41b30def3181bce4bf87e8bde664d15663165d0Jeff Cohen#include <algorithm> 3921ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattnerusing namespace llvm; 4021ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner 41cd3245ac45c595da96bb768a55cddc356dff55feChris LattnerSTATISTIC(NumDeadBlocks, "Number of dead blocks removed"); 42cd3245ac45c595da96bb768a55cddc356dff55feChris LattnerSTATISTIC(NumBranchOpts, "Number of branches optimized"); 43cd3245ac45c595da96bb768a55cddc356dff55feChris LattnerSTATISTIC(NumTailMerge , "Number of block tails merged"); 447cd5d3e05ca9573dbac1a01846813037f901480cBob Wilson 454e3f125e184f96ae72f2c44d16cafe0d44158283Dan Gohmanstatic cl::opt<cl::boolOrDefault> FlagEnableTailMerge("enable-tail-merge", 4681da02b553b86868637f27b89c6e919c31ed5b51Dale Johannesen cl::init(cl::BOU_UNSET), cl::Hidden); 477cd5d3e05ca9573dbac1a01846813037f901480cBob Wilson 48844731a7f1909f55935e3514c9e713a62d67662eDan Gohman// Throttle for huge numbers of predecessors (compile speed problems) 49844731a7f1909f55935e3514c9e713a62d67662eDan Gohmanstatic cl::opt<unsigned> 504e3f125e184f96ae72f2c44d16cafe0d44158283Dan GohmanTailMergeThreshold("tail-merge-threshold", 51844731a7f1909f55935e3514c9e713a62d67662eDan Gohman cl::desc("Max number of predecessors to consider tail merging"), 52622addbe49ffdc611adb315fb22756e23fe7b222Dale Johannesen cl::init(150), cl::Hidden); 531a90a5aebe3488dc3feaab60ba16bed1659ba27bDale Johannesen 542210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman// Heuristic for tail merging (and, inversely, tail duplication). 552210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman// TODO: This should be replaced with a target query. 562210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohmanstatic cl::opt<unsigned> 573cbc3120873242d93e469b4635c0bbd09fdb6438Bob WilsonTailMergeSize("tail-merge-size", 582210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman cl::desc("Min number of instructions to consider tail merging"), 592210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman cl::init(3), cl::Hidden); 60794fd75c67a2cdc128d67342c6d88a504d186896Devang Patel 6172b2990a7495b9df89e151eb711c1e7abdd5f2e5Dan Gohmannamespace { 6272b2990a7495b9df89e151eb711c1e7abdd5f2e5Dan Gohman /// BranchFolderPass - Wrap branch folder in a machine function pass. 6372b2990a7495b9df89e151eb711c1e7abdd5f2e5Dan Gohman class BranchFolderPass : public MachineFunctionPass, 6472b2990a7495b9df89e151eb711c1e7abdd5f2e5Dan Gohman public BranchFolder { 6572b2990a7495b9df89e151eb711c1e7abdd5f2e5Dan Gohman public: 6672b2990a7495b9df89e151eb711c1e7abdd5f2e5Dan Gohman static char ID; 6772b2990a7495b9df89e151eb711c1e7abdd5f2e5Dan Gohman explicit BranchFolderPass(bool defaultEnableTailMerge) 6872b2990a7495b9df89e151eb711c1e7abdd5f2e5Dan Gohman : MachineFunctionPass(&ID), BranchFolder(defaultEnableTailMerge) {} 6972b2990a7495b9df89e151eb711c1e7abdd5f2e5Dan Gohman 7072b2990a7495b9df89e151eb711c1e7abdd5f2e5Dan Gohman virtual bool runOnMachineFunction(MachineFunction &MF); 7172b2990a7495b9df89e151eb711c1e7abdd5f2e5Dan Gohman virtual const char *getPassName() const { return "Control Flow Optimizer"; } 7272b2990a7495b9df89e151eb711c1e7abdd5f2e5Dan Gohman }; 7372b2990a7495b9df89e151eb711c1e7abdd5f2e5Dan Gohman} 7472b2990a7495b9df89e151eb711c1e7abdd5f2e5Dan Gohman 75030a0a0cdb38924e55773a8e0b5fe7347aa664aaEvan Chengchar BranchFolderPass::ID = 0; 7621ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner 777cc253e3b85b27540bbc91b8331e06e7a65fbc4cDan GohmanFunctionPass *llvm::createBranchFoldingPass(bool DefaultEnableTailMerge) { 78a597103c328e29fb763e7a4864bd7c29a588fc9dBob Wilson return new BranchFolderPass(DefaultEnableTailMerge); 79030a0a0cdb38924e55773a8e0b5fe7347aa664aaEvan Cheng} 80030a0a0cdb38924e55773a8e0b5fe7347aa664aaEvan Cheng 81030a0a0cdb38924e55773a8e0b5fe7347aa664aaEvan Chengbool BranchFolderPass::runOnMachineFunction(MachineFunction &MF) { 82030a0a0cdb38924e55773a8e0b5fe7347aa664aaEvan Cheng return OptimizeFunction(MF, 83030a0a0cdb38924e55773a8e0b5fe7347aa664aaEvan Cheng MF.getTarget().getInstrInfo(), 84030a0a0cdb38924e55773a8e0b5fe7347aa664aaEvan Cheng MF.getTarget().getRegisterInfo(), 85030a0a0cdb38924e55773a8e0b5fe7347aa664aaEvan Cheng getAnalysisIfAvailable<MachineModuleInfo>()); 86030a0a0cdb38924e55773a8e0b5fe7347aa664aaEvan Cheng} 87030a0a0cdb38924e55773a8e0b5fe7347aa664aaEvan Cheng 88030a0a0cdb38924e55773a8e0b5fe7347aa664aaEvan Cheng 89a597103c328e29fb763e7a4864bd7c29a588fc9dBob WilsonBranchFolder::BranchFolder(bool defaultEnableTailMerge) { 90030a0a0cdb38924e55773a8e0b5fe7347aa664aaEvan Cheng switch (FlagEnableTailMerge) { 91030a0a0cdb38924e55773a8e0b5fe7347aa664aaEvan Cheng case cl::BOU_UNSET: EnableTailMerge = defaultEnableTailMerge; break; 92030a0a0cdb38924e55773a8e0b5fe7347aa664aaEvan Cheng case cl::BOU_TRUE: EnableTailMerge = true; break; 93030a0a0cdb38924e55773a8e0b5fe7347aa664aaEvan Cheng case cl::BOU_FALSE: EnableTailMerge = false; break; 94030a0a0cdb38924e55773a8e0b5fe7347aa664aaEvan Cheng } 95b3c27428969b3cc52ab8493e91b5dd1465325fedEvan Cheng} 9621ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner 97c50ffcb7fcb7c1109fee2406e8f74d096f755f47Chris Lattner/// RemoveDeadBlock - Remove the specified dead machine basic block from the 98c50ffcb7fcb7c1109fee2406e8f74d096f755f47Chris Lattner/// function, updating the CFG. 99683747abb81a7b7711ad6cb5abf5a4227f7ab691Chris Lattnervoid BranchFolder::RemoveDeadBlock(MachineBasicBlock *MBB) { 100033c9715d9bf7ce59ad2e466bf0720811b34da08Jim Laskey assert(MBB->pred_empty() && "MBB must be dead!"); 101465e2b950d61c870fb3120c80191973e8282a3efDavid Greene DEBUG(dbgs() << "\nRemoving MBB: " << *MBB); 1024e3f125e184f96ae72f2c44d16cafe0d44158283Dan Gohman 103c50ffcb7fcb7c1109fee2406e8f74d096f755f47Chris Lattner MachineFunction *MF = MBB->getParent(); 104c50ffcb7fcb7c1109fee2406e8f74d096f755f47Chris Lattner // drop all successors. 105c50ffcb7fcb7c1109fee2406e8f74d096f755f47Chris Lattner while (!MBB->succ_empty()) 106c50ffcb7fcb7c1109fee2406e8f74d096f755f47Chris Lattner MBB->removeSuccessor(MBB->succ_end()-1); 1074e3f125e184f96ae72f2c44d16cafe0d44158283Dan Gohman 10868d4d1d49c813d10047ad116e897a17d67112c10Duncan Sands // If there are any labels in the basic block, unregister them from 10968d4d1d49c813d10047ad116e897a17d67112c10Duncan Sands // MachineModuleInfo. 11044c3b9fdd416c79f4b67cde1aecfced5921efd81Jim Laskey if (MMI && !MBB->empty()) { 111683747abb81a7b7711ad6cb5abf5a4227f7ab691Chris Lattner for (MachineBasicBlock::iterator I = MBB->begin(), E = MBB->end(); 112683747abb81a7b7711ad6cb5abf5a4227f7ab691Chris Lattner I != E; ++I) { 11368d4d1d49c813d10047ad116e897a17d67112c10Duncan Sands if (I->isLabel()) 114683747abb81a7b7711ad6cb5abf5a4227f7ab691Chris Lattner // The label ID # is always operand #0, an immediate. 11544c3b9fdd416c79f4b67cde1aecfced5921efd81Jim Laskey MMI->InvalidateLabel(I->getOperand(0).getImm()); 116683747abb81a7b7711ad6cb5abf5a4227f7ab691Chris Lattner } 117683747abb81a7b7711ad6cb5abf5a4227f7ab691Chris Lattner } 1184e3f125e184f96ae72f2c44d16cafe0d44158283Dan Gohman 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); 140030a0a0cdb38924e55773a8e0b5fe7347aa664aaEvan Cheng for (const unsigned *SubRegs = TRI->getSubRegisters(Reg); 14180b09fe8bc1d2755ef9a6b03b8862a657db42f06Evan Cheng unsigned SubReg = *SubRegs; ++SubRegs) 14280b09fe8bc1d2755ef9a6b03b8862a657db42f06Evan Cheng ImpDefRegs.insert(SubReg); 14380b09fe8bc1d2755ef9a6b03b8862a657db42f06Evan Cheng ++I; 14480b09fe8bc1d2755ef9a6b03b8862a657db42f06Evan Cheng } 14580b09fe8bc1d2755ef9a6b03b8862a657db42f06Evan Cheng if (ImpDefRegs.empty()) 14680b09fe8bc1d2755ef9a6b03b8862a657db42f06Evan Cheng return false; 14780b09fe8bc1d2755ef9a6b03b8862a657db42f06Evan Cheng 14880b09fe8bc1d2755ef9a6b03b8862a657db42f06Evan Cheng MachineBasicBlock::iterator FirstTerm = I; 14980b09fe8bc1d2755ef9a6b03b8862a657db42f06Evan Cheng while (I != MBB->end()) { 15080b09fe8bc1d2755ef9a6b03b8862a657db42f06Evan Cheng if (!TII->isUnpredicatedTerminator(I)) 15180b09fe8bc1d2755ef9a6b03b8862a657db42f06Evan Cheng return false; 15280b09fe8bc1d2755ef9a6b03b8862a657db42f06Evan Cheng // See if it uses any of the implicitly defined registers. 15380b09fe8bc1d2755ef9a6b03b8862a657db42f06Evan Cheng for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i) { 15480b09fe8bc1d2755ef9a6b03b8862a657db42f06Evan Cheng MachineOperand &MO = I->getOperand(i); 155d735b8019b0f297d7c14b55adcd887af24d8e602Dan Gohman if (!MO.isReg() || !MO.isUse()) 15680b09fe8bc1d2755ef9a6b03b8862a657db42f06Evan Cheng continue; 15780b09fe8bc1d2755ef9a6b03b8862a657db42f06Evan Cheng unsigned Reg = MO.getReg(); 15880b09fe8bc1d2755ef9a6b03b8862a657db42f06Evan Cheng if (ImpDefRegs.count(Reg)) 15980b09fe8bc1d2755ef9a6b03b8862a657db42f06Evan Cheng return false; 16080b09fe8bc1d2755ef9a6b03b8862a657db42f06Evan Cheng } 16180b09fe8bc1d2755ef9a6b03b8862a657db42f06Evan Cheng ++I; 16280b09fe8bc1d2755ef9a6b03b8862a657db42f06Evan Cheng } 16380b09fe8bc1d2755ef9a6b03b8862a657db42f06Evan Cheng 16480b09fe8bc1d2755ef9a6b03b8862a657db42f06Evan Cheng I = MBB->begin(); 16580b09fe8bc1d2755ef9a6b03b8862a657db42f06Evan Cheng while (I != FirstTerm) { 16680b09fe8bc1d2755ef9a6b03b8862a657db42f06Evan Cheng MachineInstr *ImpDefMI = &*I; 16780b09fe8bc1d2755ef9a6b03b8862a657db42f06Evan Cheng ++I; 16880b09fe8bc1d2755ef9a6b03b8862a657db42f06Evan Cheng MBB->erase(ImpDefMI); 16980b09fe8bc1d2755ef9a6b03b8862a657db42f06Evan Cheng } 17080b09fe8bc1d2755ef9a6b03b8862a657db42f06Evan Cheng 17180b09fe8bc1d2755ef9a6b03b8862a657db42f06Evan Cheng return true; 17280b09fe8bc1d2755ef9a6b03b8862a657db42f06Evan Cheng} 17380b09fe8bc1d2755ef9a6b03b8862a657db42f06Evan Cheng 174030a0a0cdb38924e55773a8e0b5fe7347aa664aaEvan Cheng/// OptimizeFunction - Perhaps branch folding, tail merging and other 175030a0a0cdb38924e55773a8e0b5fe7347aa664aaEvan Cheng/// CFG optimizations on the given function. 176030a0a0cdb38924e55773a8e0b5fe7347aa664aaEvan Chengbool BranchFolder::OptimizeFunction(MachineFunction &MF, 177030a0a0cdb38924e55773a8e0b5fe7347aa664aaEvan Cheng const TargetInstrInfo *tii, 178030a0a0cdb38924e55773a8e0b5fe7347aa664aaEvan Cheng const TargetRegisterInfo *tri, 179030a0a0cdb38924e55773a8e0b5fe7347aa664aaEvan Cheng MachineModuleInfo *mmi) { 180030a0a0cdb38924e55773a8e0b5fe7347aa664aaEvan Cheng if (!tii) return false; 181030a0a0cdb38924e55773a8e0b5fe7347aa664aaEvan Cheng 182030a0a0cdb38924e55773a8e0b5fe7347aa664aaEvan Cheng TII = tii; 183030a0a0cdb38924e55773a8e0b5fe7347aa664aaEvan Cheng TRI = tri; 184030a0a0cdb38924e55773a8e0b5fe7347aa664aaEvan Cheng MMI = mmi; 1857821a8afd3009c3c2760592e61de9e2c31c73e18Chris Lattner 186030a0a0cdb38924e55773a8e0b5fe7347aa664aaEvan Cheng RS = TRI->requiresRegisterScavenging(MF) ? new RegScavenger() : NULL; 18780b09fe8bc1d2755ef9a6b03b8862a657db42f06Evan Cheng 18814ba0cc42959a3fcc9b6781aea614b01877fb55fDale Johannesen // Fix CFG. The later algorithms expect it to be right. 189030a0a0cdb38924e55773a8e0b5fe7347aa664aaEvan Cheng bool MadeChange = false; 19014ba0cc42959a3fcc9b6781aea614b01877fb55fDale Johannesen for (MachineFunction::iterator I = MF.begin(), E = MF.end(); I != E; I++) { 19114ba0cc42959a3fcc9b6781aea614b01877fb55fDale Johannesen MachineBasicBlock *MBB = I, *TBB = 0, *FBB = 0; 19244eb65cf58e3ab9b5621ce72256d1621a18aeed7Owen Anderson SmallVector<MachineOperand, 4> Cond; 193dc54d317e7a381ef8e4aca80d54ad1466bb85ddaEvan Cheng if (!TII->AnalyzeBranch(*MBB, TBB, FBB, Cond, true)) 194030a0a0cdb38924e55773a8e0b5fe7347aa664aaEvan Cheng MadeChange |= MBB->CorrectExtraCFGEdges(TBB, FBB, !Cond.empty()); 195030a0a0cdb38924e55773a8e0b5fe7347aa664aaEvan Cheng MadeChange |= OptimizeImpDefsBlock(MBB); 19614ba0cc42959a3fcc9b6781aea614b01877fb55fDale Johannesen } 19714ba0cc42959a3fcc9b6781aea614b01877fb55fDale Johannesen 19812143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner bool MadeChangeThisIteration = true; 19912143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner while (MadeChangeThisIteration) { 20012143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner MadeChangeThisIteration = false; 20112143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner MadeChangeThisIteration |= TailMergeBlocks(MF); 20212143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner MadeChangeThisIteration |= OptimizeBranches(MF); 203030a0a0cdb38924e55773a8e0b5fe7347aa664aaEvan Cheng MadeChange |= MadeChangeThisIteration; 20412143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner } 20512143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner 2066acfe12dd6d52c801f78c240528b7cb42fa91159Chris Lattner // See if any jump tables have become mergable or dead as the code generator 2076acfe12dd6d52c801f78c240528b7cb42fa91159Chris Lattner // did its thing. 2086acfe12dd6d52c801f78c240528b7cb42fa91159Chris Lattner MachineJumpTableInfo *JTI = MF.getJumpTableInfo(); 209071c62fad0b25ad4131e7f984173a796c1e63f61Chris Lattner if (JTI == 0) { 210071c62fad0b25ad4131e7f984173a796c1e63f61Chris Lattner delete RS; 211071c62fad0b25ad4131e7f984173a796c1e63f61Chris Lattner return MadeChange; 212071c62fad0b25ad4131e7f984173a796c1e63f61Chris Lattner } 213071c62fad0b25ad4131e7f984173a796c1e63f61Chris Lattner 2146acfe12dd6d52c801f78c240528b7cb42fa91159Chris Lattner const std::vector<MachineJumpTableEntry> &JTs = JTI->getJumpTables(); 215071c62fad0b25ad4131e7f984173a796c1e63f61Chris Lattner // Figure out how these jump tables should be merged. 216071c62fad0b25ad4131e7f984173a796c1e63f61Chris Lattner std::vector<unsigned> JTMapping; 217071c62fad0b25ad4131e7f984173a796c1e63f61Chris Lattner JTMapping.reserve(JTs.size()); 218071c62fad0b25ad4131e7f984173a796c1e63f61Chris Lattner 219071c62fad0b25ad4131e7f984173a796c1e63f61Chris Lattner // We always keep the 0th jump table. 220071c62fad0b25ad4131e7f984173a796c1e63f61Chris Lattner JTMapping.push_back(0); 221071c62fad0b25ad4131e7f984173a796c1e63f61Chris Lattner 222071c62fad0b25ad4131e7f984173a796c1e63f61Chris Lattner // Scan the jump tables, seeing if there are any duplicates. Note that this 223071c62fad0b25ad4131e7f984173a796c1e63f61Chris Lattner // is N^2, which should be fixed someday. 224071c62fad0b25ad4131e7f984173a796c1e63f61Chris Lattner for (unsigned i = 1, e = JTs.size(); i != e; ++i) { 225071c62fad0b25ad4131e7f984173a796c1e63f61Chris Lattner if (JTs[i].MBBs.empty()) 226071c62fad0b25ad4131e7f984173a796c1e63f61Chris Lattner JTMapping.push_back(i); 227071c62fad0b25ad4131e7f984173a796c1e63f61Chris Lattner else 228071c62fad0b25ad4131e7f984173a796c1e63f61Chris Lattner JTMapping.push_back(JTI->getJumpTableIndex(JTs[i].MBBs)); 229071c62fad0b25ad4131e7f984173a796c1e63f61Chris Lattner } 2304e3f125e184f96ae72f2c44d16cafe0d44158283Dan Gohman 231071c62fad0b25ad4131e7f984173a796c1e63f61Chris Lattner // If a jump table was merge with another one, walk the function rewriting 232071c62fad0b25ad4131e7f984173a796c1e63f61Chris Lattner // references to jump tables to reference the new JT ID's. Keep track of 233071c62fad0b25ad4131e7f984173a796c1e63f61Chris Lattner // whether we see a jump table idx, if not, we can delete the JT. 234071c62fad0b25ad4131e7f984173a796c1e63f61Chris Lattner BitVector JTIsLive(JTs.size()); 235071c62fad0b25ad4131e7f984173a796c1e63f61Chris Lattner for (MachineFunction::iterator BB = MF.begin(), E = MF.end(); 236071c62fad0b25ad4131e7f984173a796c1e63f61Chris Lattner BB != E; ++BB) { 237071c62fad0b25ad4131e7f984173a796c1e63f61Chris Lattner for (MachineBasicBlock::iterator I = BB->begin(), E = BB->end(); 238071c62fad0b25ad4131e7f984173a796c1e63f61Chris Lattner I != E; ++I) 239071c62fad0b25ad4131e7f984173a796c1e63f61Chris Lattner for (unsigned op = 0, e = I->getNumOperands(); op != e; ++op) { 240071c62fad0b25ad4131e7f984173a796c1e63f61Chris Lattner MachineOperand &Op = I->getOperand(op); 241071c62fad0b25ad4131e7f984173a796c1e63f61Chris Lattner if (!Op.isJTI()) continue; 242071c62fad0b25ad4131e7f984173a796c1e63f61Chris Lattner unsigned NewIdx = JTMapping[Op.getIndex()]; 243071c62fad0b25ad4131e7f984173a796c1e63f61Chris Lattner Op.setIndex(NewIdx); 244071c62fad0b25ad4131e7f984173a796c1e63f61Chris Lattner 245071c62fad0b25ad4131e7f984173a796c1e63f61Chris Lattner // Remember that this JT is live. 246071c62fad0b25ad4131e7f984173a796c1e63f61Chris Lattner JTIsLive.set(NewIdx); 2476acfe12dd6d52c801f78c240528b7cb42fa91159Chris Lattner } 2486acfe12dd6d52c801f78c240528b7cb42fa91159Chris Lattner } 249030a0a0cdb38924e55773a8e0b5fe7347aa664aaEvan Cheng 250071c62fad0b25ad4131e7f984173a796c1e63f61Chris Lattner // Finally, remove dead jump tables. This happens either because the 251071c62fad0b25ad4131e7f984173a796c1e63f61Chris Lattner // indirect jump was unreachable (and thus deleted) or because the jump 252071c62fad0b25ad4131e7f984173a796c1e63f61Chris Lattner // table was merged with some other one. 253071c62fad0b25ad4131e7f984173a796c1e63f61Chris Lattner for (unsigned i = 0, e = JTIsLive.size(); i != e; ++i) 254071c62fad0b25ad4131e7f984173a796c1e63f61Chris Lattner if (!JTIsLive.test(i)) { 255071c62fad0b25ad4131e7f984173a796c1e63f61Chris Lattner JTI->RemoveJumpTable(i); 256071c62fad0b25ad4131e7f984173a796c1e63f61Chris Lattner MadeChange = true; 257071c62fad0b25ad4131e7f984173a796c1e63f61Chris Lattner } 258071c62fad0b25ad4131e7f984173a796c1e63f61Chris Lattner 25969cb9b78f11d505f4351a269fc90e7b77fcda437Dale Johannesen delete RS; 260030a0a0cdb38924e55773a8e0b5fe7347aa664aaEvan Cheng return MadeChange; 26112143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner} 26212143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner 26312143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner//===----------------------------------------------------------------------===// 26412143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner// Tail Merging of Blocks 26512143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner//===----------------------------------------------------------------------===// 26612143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner 26712143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner/// HashMachineInstr - Compute a hash value for MI and its operands. 26812143054aa6d120f029d268a5154bf2ecd0f707fChris Lattnerstatic unsigned HashMachineInstr(const MachineInstr *MI) { 26912143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner unsigned Hash = MI->getOpcode(); 27012143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 27112143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner const MachineOperand &Op = MI->getOperand(i); 2724e3f125e184f96ae72f2c44d16cafe0d44158283Dan Gohman 27312143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner // Merge in bits from the operand if easy. 27412143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner unsigned OperandHash = 0; 27512143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner switch (Op.getType()) { 27612143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner case MachineOperand::MO_Register: OperandHash = Op.getReg(); break; 27712143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner case MachineOperand::MO_Immediate: OperandHash = Op.getImm(); break; 27812143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner case MachineOperand::MO_MachineBasicBlock: 2798aa797aa51cd4ea1ec6f46f4891a6897944b75b2Chris Lattner OperandHash = Op.getMBB()->getNumber(); 28012143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner break; 2818aa797aa51cd4ea1ec6f46f4891a6897944b75b2Chris Lattner case MachineOperand::MO_FrameIndex: 28212143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner case MachineOperand::MO_ConstantPoolIndex: 28312143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner case MachineOperand::MO_JumpTableIndex: 2848aa797aa51cd4ea1ec6f46f4891a6897944b75b2Chris Lattner OperandHash = Op.getIndex(); 28512143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner break; 28612143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner case MachineOperand::MO_GlobalAddress: 28712143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner case MachineOperand::MO_ExternalSymbol: 28812143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner // Global address / external symbol are too hard, don't bother, but do 28912143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner // pull in the offset. 29012143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner OperandHash = Op.getOffset(); 29112143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner break; 29212143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner default: break; 29312143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner } 2944e3f125e184f96ae72f2c44d16cafe0d44158283Dan Gohman 29512143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner Hash += ((OperandHash << 3) | Op.getType()) << (i&31); 29612143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner } 29712143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner return Hash; 29812143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner} 29912143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner 3007aea8320340ce867eb4328aeec52cb02c88ef0b3Dale Johannesen/// HashEndOfMBB - Hash the last few instructions in the MBB. For blocks 3014e3f125e184f96ae72f2c44d16cafe0d44158283Dan Gohman/// with no successors, we hash two instructions, because cross-jumping 3024e3f125e184f96ae72f2c44d16cafe0d44158283Dan Gohman/// only saves code when at least two instructions are removed (since a 3037aea8320340ce867eb4328aeec52cb02c88ef0b3Dale Johannesen/// branch must be inserted). For blocks with a successor, one of the 3047aea8320340ce867eb4328aeec52cb02c88ef0b3Dale Johannesen/// two blocks to be tail-merged will end with a branch already, so 3057aea8320340ce867eb4328aeec52cb02c88ef0b3Dale Johannesen/// it gains to cross-jump even for one instruction. 3067aea8320340ce867eb4328aeec52cb02c88ef0b3Dale Johannesenstatic unsigned HashEndOfMBB(const MachineBasicBlock *MBB, 3077aea8320340ce867eb4328aeec52cb02c88ef0b3Dale Johannesen unsigned minCommonTailLength) { 30812143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner MachineBasicBlock::const_iterator I = MBB->end(); 30912143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner if (I == MBB->begin()) 31012143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner return 0; // Empty MBB. 3114e3f125e184f96ae72f2c44d16cafe0d44158283Dan Gohman 31212143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner --I; 31384839daa595968286acd25644820c644867f0c52Dale Johannesen // Skip debug info so it will not affect codegen. 31484839daa595968286acd25644820c644867f0c52Dale Johannesen while (I->isDebugValue()) { 31584839daa595968286acd25644820c644867f0c52Dale Johannesen if (I==MBB->begin()) 31684839daa595968286acd25644820c644867f0c52Dale Johannesen return 0; // MBB empty except for debug info. 31784839daa595968286acd25644820c644867f0c52Dale Johannesen --I; 31884839daa595968286acd25644820c644867f0c52Dale Johannesen } 31912143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner unsigned Hash = HashMachineInstr(I); 3204e3f125e184f96ae72f2c44d16cafe0d44158283Dan Gohman 3217aea8320340ce867eb4328aeec52cb02c88ef0b3Dale Johannesen if (I == MBB->begin() || minCommonTailLength == 1) 32212143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner return Hash; // Single instr MBB. 3234e3f125e184f96ae72f2c44d16cafe0d44158283Dan Gohman 32412143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner --I; 32584839daa595968286acd25644820c644867f0c52Dale Johannesen while (I->isDebugValue()) { 32684839daa595968286acd25644820c644867f0c52Dale Johannesen if (I==MBB->begin()) 32784839daa595968286acd25644820c644867f0c52Dale Johannesen return Hash; // MBB with single non-debug instr. 32884839daa595968286acd25644820c644867f0c52Dale Johannesen --I; 32984839daa595968286acd25644820c644867f0c52Dale Johannesen } 33012143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner // Hash in the second-to-last instruction. 33112143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner Hash ^= HashMachineInstr(I) << 2; 33212143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner return Hash; 33312143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner} 33412143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner 33512143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner/// ComputeCommonTailLength - Given two machine basic blocks, compute the number 33612143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner/// of instructions they actually have in common together at their end. Return 33712143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner/// iterators for the first shared instruction in each block. 33812143054aa6d120f029d268a5154bf2ecd0f707fChris Lattnerstatic unsigned ComputeCommonTailLength(MachineBasicBlock *MBB1, 33912143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner MachineBasicBlock *MBB2, 34012143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner MachineBasicBlock::iterator &I1, 34112143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner MachineBasicBlock::iterator &I2) { 34212143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner I1 = MBB1->end(); 34312143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner I2 = MBB2->end(); 3444e3f125e184f96ae72f2c44d16cafe0d44158283Dan Gohman 34512143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner unsigned TailLen = 0; 34612143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner while (I1 != MBB1->begin() && I2 != MBB2->begin()) { 34712143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner --I1; --I2; 34884839daa595968286acd25644820c644867f0c52Dale Johannesen // Skip debugging pseudos; necessary to avoid changing the code. 34984839daa595968286acd25644820c644867f0c52Dale Johannesen while (I1->isDebugValue()) { 350c5cf227f3dac755508928b9dee8ac6a45dcb4e4fDale Johannesen if (I1==MBB1->begin()) { 351c5cf227f3dac755508928b9dee8ac6a45dcb4e4fDale Johannesen while (I2->isDebugValue()) { 352c5cf227f3dac755508928b9dee8ac6a45dcb4e4fDale Johannesen if (I2==MBB2->begin()) 353c5cf227f3dac755508928b9dee8ac6a45dcb4e4fDale Johannesen // I1==DBG at begin; I2==DBG at begin 354c5cf227f3dac755508928b9dee8ac6a45dcb4e4fDale Johannesen return TailLen; 355c5cf227f3dac755508928b9dee8ac6a45dcb4e4fDale Johannesen --I2; 356c5cf227f3dac755508928b9dee8ac6a45dcb4e4fDale Johannesen } 357c5cf227f3dac755508928b9dee8ac6a45dcb4e4fDale Johannesen ++I2; 358c5cf227f3dac755508928b9dee8ac6a45dcb4e4fDale Johannesen // I1==DBG at begin; I2==non-DBG, or first of DBGs not at begin 35984839daa595968286acd25644820c644867f0c52Dale Johannesen return TailLen; 360c5cf227f3dac755508928b9dee8ac6a45dcb4e4fDale Johannesen } 36184839daa595968286acd25644820c644867f0c52Dale Johannesen --I1; 36284839daa595968286acd25644820c644867f0c52Dale Johannesen } 363c5cf227f3dac755508928b9dee8ac6a45dcb4e4fDale Johannesen // I1==first (untested) non-DBG preceding known match 36484839daa595968286acd25644820c644867f0c52Dale Johannesen while (I2->isDebugValue()) { 365c5cf227f3dac755508928b9dee8ac6a45dcb4e4fDale Johannesen if (I2==MBB2->begin()) { 366c5cf227f3dac755508928b9dee8ac6a45dcb4e4fDale Johannesen ++I1; 367c5cf227f3dac755508928b9dee8ac6a45dcb4e4fDale Johannesen // I1==non-DBG, or first of DBGs not at begin; I2==DBG at begin 36884839daa595968286acd25644820c644867f0c52Dale Johannesen return TailLen; 369c5cf227f3dac755508928b9dee8ac6a45dcb4e4fDale Johannesen } 37084839daa595968286acd25644820c644867f0c52Dale Johannesen --I2; 37184839daa595968286acd25644820c644867f0c52Dale Johannesen } 372c5cf227f3dac755508928b9dee8ac6a45dcb4e4fDale Johannesen // I1, I2==first (untested) non-DBGs preceding known match 37384839daa595968286acd25644820c644867f0c52Dale Johannesen if (!I1->isIdenticalTo(I2) || 374da6efc5268958a0668806e989c1c5a1f788543e5Bill Wendling // FIXME: This check is dubious. It's used to get around a problem where 3750713a224234b4596709c7582ebf17a1ccb95c872Bill Wendling // people incorrectly expect inline asm directives to remain in the same 3760713a224234b4596709c7582ebf17a1ccb95c872Bill Wendling // relative order. This is untenable because normal compiler 3770713a224234b4596709c7582ebf17a1ccb95c872Bill Wendling // optimizations (like this one) may reorder and/or merge these 3780713a224234b4596709c7582ebf17a1ccb95c872Bill Wendling // directives. 379518bb53485df640d7b7e3f6b0544099020c42aa7Chris Lattner I1->isInlineAsm()) { 38012143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner ++I1; ++I2; 38112143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner break; 38212143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner } 38312143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner ++TailLen; 38412143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner } 385c5cf227f3dac755508928b9dee8ac6a45dcb4e4fDale Johannesen // Back past possible debugging pseudos at beginning of block. This matters 386c5cf227f3dac755508928b9dee8ac6a45dcb4e4fDale Johannesen // when one block differs from the other only by whether debugging pseudos 387c5cf227f3dac755508928b9dee8ac6a45dcb4e4fDale Johannesen // are present at the beginning. (This way, the various checks later for 388c5cf227f3dac755508928b9dee8ac6a45dcb4e4fDale Johannesen // I1==MBB1->begin() work as expected.) 389c5cf227f3dac755508928b9dee8ac6a45dcb4e4fDale Johannesen if (I1 == MBB1->begin() && I2 != MBB2->begin()) { 390c5cf227f3dac755508928b9dee8ac6a45dcb4e4fDale Johannesen --I2; 391c5cf227f3dac755508928b9dee8ac6a45dcb4e4fDale Johannesen while (I2->isDebugValue()) { 392c5cf227f3dac755508928b9dee8ac6a45dcb4e4fDale Johannesen if (I2 == MBB2->begin()) { 393c5cf227f3dac755508928b9dee8ac6a45dcb4e4fDale Johannesen return TailLen; 394c5cf227f3dac755508928b9dee8ac6a45dcb4e4fDale Johannesen } 395c5cf227f3dac755508928b9dee8ac6a45dcb4e4fDale Johannesen --I2; 396c5cf227f3dac755508928b9dee8ac6a45dcb4e4fDale Johannesen } 397c5cf227f3dac755508928b9dee8ac6a45dcb4e4fDale Johannesen ++I2; 398c5cf227f3dac755508928b9dee8ac6a45dcb4e4fDale Johannesen } 399c5cf227f3dac755508928b9dee8ac6a45dcb4e4fDale Johannesen if (I2 == MBB2->begin() && I1 != MBB1->begin()) { 400c5cf227f3dac755508928b9dee8ac6a45dcb4e4fDale Johannesen --I1; 401c5cf227f3dac755508928b9dee8ac6a45dcb4e4fDale Johannesen while (I1->isDebugValue()) { 402c5cf227f3dac755508928b9dee8ac6a45dcb4e4fDale Johannesen if (I1 == MBB1->begin()) 403c5cf227f3dac755508928b9dee8ac6a45dcb4e4fDale Johannesen return TailLen; 404c5cf227f3dac755508928b9dee8ac6a45dcb4e4fDale Johannesen --I1; 405c5cf227f3dac755508928b9dee8ac6a45dcb4e4fDale Johannesen } 406c5cf227f3dac755508928b9dee8ac6a45dcb4e4fDale Johannesen ++I1; 407c5cf227f3dac755508928b9dee8ac6a45dcb4e4fDale Johannesen } 40812143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner return TailLen; 40912143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner} 41012143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner 41112143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner/// ReplaceTailWithBranchTo - Delete the instruction OldInst and everything 412386e29065db5b05b57440f6b2a6dfa1e7f29a00dChris Lattner/// after it, replacing it with an unconditional branch to NewDest. This 413386e29065db5b05b57440f6b2a6dfa1e7f29a00dChris Lattner/// returns true if OldInst's block is modified, false if NewDest is modified. 41412143054aa6d120f029d268a5154bf2ecd0f707fChris Lattnervoid BranchFolder::ReplaceTailWithBranchTo(MachineBasicBlock::iterator OldInst, 41512143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner MachineBasicBlock *NewDest) { 41612143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner MachineBasicBlock *OldBB = OldInst->getParent(); 4174e3f125e184f96ae72f2c44d16cafe0d44158283Dan Gohman 41812143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner // Remove all the old successors of OldBB from the CFG. 41912143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner while (!OldBB->succ_empty()) 42012143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner OldBB->removeSuccessor(OldBB->succ_begin()); 4214e3f125e184f96ae72f2c44d16cafe0d44158283Dan Gohman 42212143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner // Remove all the dead instructions from the end of OldBB. 42312143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner OldBB->erase(OldInst, OldBB->end()); 42412143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner 425386e29065db5b05b57440f6b2a6dfa1e7f29a00dChris Lattner // If OldBB isn't immediately before OldBB, insert a branch to it. 426386e29065db5b05b57440f6b2a6dfa1e7f29a00dChris Lattner if (++MachineFunction::iterator(OldBB) != MachineFunction::iterator(NewDest)) 4271501cdbf63cff3afd92df6cd249096770334b268Dan Gohman TII->InsertBranch(*OldBB, NewDest, 0, SmallVector<MachineOperand, 0>()); 42812143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner OldBB->addSuccessor(NewDest); 42912143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner ++NumTailMerge; 43012143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner} 43112143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner 4321d08d83230338ca5969ff6ae6737a978336538bfChris Lattner/// SplitMBBAt - Given a machine basic block and an iterator into it, split the 4331d08d83230338ca5969ff6ae6737a978336538bfChris Lattner/// MBB so that the part before the iterator falls into the part starting at the 4341d08d83230338ca5969ff6ae6737a978336538bfChris Lattner/// iterator. This returns the new MBB. 4351d08d83230338ca5969ff6ae6737a978336538bfChris LattnerMachineBasicBlock *BranchFolder::SplitMBBAt(MachineBasicBlock &CurMBB, 4361d08d83230338ca5969ff6ae6737a978336538bfChris Lattner MachineBasicBlock::iterator BBI1) { 4378e5f2c6f65841542e2a7092553fe42a00048e4c7Dan Gohman MachineFunction &MF = *CurMBB.getParent(); 4388e5f2c6f65841542e2a7092553fe42a00048e4c7Dan Gohman 4391d08d83230338ca5969ff6ae6737a978336538bfChris Lattner // Create the fall-through block. 4401d08d83230338ca5969ff6ae6737a978336538bfChris Lattner MachineFunction::iterator MBBI = &CurMBB; 4418e5f2c6f65841542e2a7092553fe42a00048e4c7Dan Gohman MachineBasicBlock *NewMBB =MF.CreateMachineBasicBlock(CurMBB.getBasicBlock()); 4428e5f2c6f65841542e2a7092553fe42a00048e4c7Dan Gohman CurMBB.getParent()->insert(++MBBI, NewMBB); 4431d08d83230338ca5969ff6ae6737a978336538bfChris Lattner 4441d08d83230338ca5969ff6ae6737a978336538bfChris Lattner // Move all the successors of this block to the specified block. 44504478e56f736325d3567e7c0efe2bb5c2766c63bDan Gohman NewMBB->transferSuccessors(&CurMBB); 4464e3f125e184f96ae72f2c44d16cafe0d44158283Dan Gohman 4471d08d83230338ca5969ff6ae6737a978336538bfChris Lattner // Add an edge from CurMBB to NewMBB for the fall-through. 4481d08d83230338ca5969ff6ae6737a978336538bfChris Lattner CurMBB.addSuccessor(NewMBB); 4494e3f125e184f96ae72f2c44d16cafe0d44158283Dan Gohman 4501d08d83230338ca5969ff6ae6737a978336538bfChris Lattner // Splice the code over. 4511d08d83230338ca5969ff6ae6737a978336538bfChris Lattner NewMBB->splice(NewMBB->end(), &CurMBB, BBI1, CurMBB.end()); 45269cb9b78f11d505f4351a269fc90e7b77fcda437Dale Johannesen 45369cb9b78f11d505f4351a269fc90e7b77fcda437Dale Johannesen // For targets that use the register scavenger, we must maintain LiveIns. 45469cb9b78f11d505f4351a269fc90e7b77fcda437Dale Johannesen if (RS) { 45569cb9b78f11d505f4351a269fc90e7b77fcda437Dale Johannesen RS->enterBasicBlock(&CurMBB); 45669cb9b78f11d505f4351a269fc90e7b77fcda437Dale Johannesen if (!CurMBB.empty()) 45769cb9b78f11d505f4351a269fc90e7b77fcda437Dale Johannesen RS->forward(prior(CurMBB.end())); 458030a0a0cdb38924e55773a8e0b5fe7347aa664aaEvan Cheng BitVector RegsLiveAtExit(TRI->getNumRegs()); 45969cb9b78f11d505f4351a269fc90e7b77fcda437Dale Johannesen RS->getRegsUsed(RegsLiveAtExit, false); 4608520149db158427339a235a74dd2cc19553a7328Dan Gohman for (unsigned int i = 0, e = TRI->getNumRegs(); i != e; i++) 46169cb9b78f11d505f4351a269fc90e7b77fcda437Dale Johannesen if (RegsLiveAtExit[i]) 46269cb9b78f11d505f4351a269fc90e7b77fcda437Dale Johannesen NewMBB->addLiveIn(i); 46369cb9b78f11d505f4351a269fc90e7b77fcda437Dale Johannesen } 46469cb9b78f11d505f4351a269fc90e7b77fcda437Dale Johannesen 4651d08d83230338ca5969ff6ae6737a978336538bfChris Lattner return NewMBB; 4661d08d83230338ca5969ff6ae6737a978336538bfChris Lattner} 4671d08d83230338ca5969ff6ae6737a978336538bfChris Lattner 468d4bf3c2fd60975b30cd067b59f743a3ea45e45b5Chris Lattner/// EstimateRuntime - Make a rough estimate for how long it will take to run 469d4bf3c2fd60975b30cd067b59f743a3ea45e45b5Chris Lattner/// the specified code. 470d4bf3c2fd60975b30cd067b59f743a3ea45e45b5Chris Lattnerstatic unsigned EstimateRuntime(MachineBasicBlock::iterator I, 47169244300b8a0112efb44b6273ecea4ca6264b8cfChris Lattner MachineBasicBlock::iterator E) { 472d4bf3c2fd60975b30cd067b59f743a3ea45e45b5Chris Lattner unsigned Time = 0; 473d4bf3c2fd60975b30cd067b59f743a3ea45e45b5Chris Lattner for (; I != E; ++I) { 474b0812f114b83a32c4b90a4b553c7177c557558b5Dale Johannesen if (I->isDebugValue()) 475b0812f114b83a32c4b90a4b553c7177c557558b5Dale Johannesen continue; 476749c6f6b5ed301c84aac562e414486549d7b98ebChris Lattner const TargetInstrDesc &TID = I->getDesc(); 477749c6f6b5ed301c84aac562e414486549d7b98ebChris Lattner if (TID.isCall()) 478d4bf3c2fd60975b30cd067b59f743a3ea45e45b5Chris Lattner Time += 10; 47941474baac839da410302950305722cb0e026a094Dan Gohman else if (TID.mayLoad() || TID.mayStore()) 480d4bf3c2fd60975b30cd067b59f743a3ea45e45b5Chris Lattner Time += 2; 481d4bf3c2fd60975b30cd067b59f743a3ea45e45b5Chris Lattner else 482d4bf3c2fd60975b30cd067b59f743a3ea45e45b5Chris Lattner ++Time; 483d4bf3c2fd60975b30cd067b59f743a3ea45e45b5Chris Lattner } 484d4bf3c2fd60975b30cd067b59f743a3ea45e45b5Chris Lattner return Time; 485d4bf3c2fd60975b30cd067b59f743a3ea45e45b5Chris Lattner} 486d4bf3c2fd60975b30cd067b59f743a3ea45e45b5Chris Lattner 48776b38fcabeba725e166a2ff72c56fe31d784b229Dale Johannesen// CurMBB needs to add an unconditional branch to SuccMBB (we removed these 48876b38fcabeba725e166a2ff72c56fe31d784b229Dale Johannesen// branches temporarily for tail merging). In the case where CurMBB ends 48976b38fcabeba725e166a2ff72c56fe31d784b229Dale Johannesen// with a conditional branch to the next block, optimize by reversing the 49076b38fcabeba725e166a2ff72c56fe31d784b229Dale Johannesen// test and conditionally branching to SuccMBB instead. 491d34f5d91bc6fdc55085d3c4d509c778d6bcc5f0aBob Wilsonstatic void FixTail(MachineBasicBlock *CurMBB, MachineBasicBlock *SuccBB, 49276b38fcabeba725e166a2ff72c56fe31d784b229Dale Johannesen const TargetInstrInfo *TII) { 49376b38fcabeba725e166a2ff72c56fe31d784b229Dale Johannesen MachineFunction *MF = CurMBB->getParent(); 4947896c9f436a4eda5ec15e882a7505ba482a2fcd0Chris Lattner MachineFunction::iterator I = llvm::next(MachineFunction::iterator(CurMBB)); 49576b38fcabeba725e166a2ff72c56fe31d784b229Dale Johannesen MachineBasicBlock *TBB = 0, *FBB = 0; 49644eb65cf58e3ab9b5621ce72256d1621a18aeed7Owen Anderson SmallVector<MachineOperand, 4> Cond; 49776b38fcabeba725e166a2ff72c56fe31d784b229Dale Johannesen if (I != MF->end() && 498dc54d317e7a381ef8e4aca80d54ad1466bb85ddaEvan Cheng !TII->AnalyzeBranch(*CurMBB, TBB, FBB, Cond, true)) { 49976b38fcabeba725e166a2ff72c56fe31d784b229Dale Johannesen MachineBasicBlock *NextBB = I; 5006b8583cbf1f8a3df5ae859d3da2ca690ff57f91cDale Johannesen if (TBB == NextBB && !Cond.empty() && !FBB) { 50176b38fcabeba725e166a2ff72c56fe31d784b229Dale Johannesen if (!TII->ReverseBranchCondition(Cond)) { 50276b38fcabeba725e166a2ff72c56fe31d784b229Dale Johannesen TII->RemoveBranch(*CurMBB); 50376b38fcabeba725e166a2ff72c56fe31d784b229Dale Johannesen TII->InsertBranch(*CurMBB, SuccBB, NULL, Cond); 50476b38fcabeba725e166a2ff72c56fe31d784b229Dale Johannesen return; 50576b38fcabeba725e166a2ff72c56fe31d784b229Dale Johannesen } 50676b38fcabeba725e166a2ff72c56fe31d784b229Dale Johannesen } 50776b38fcabeba725e166a2ff72c56fe31d784b229Dale Johannesen } 5081501cdbf63cff3afd92df6cd249096770334b268Dan Gohman TII->InsertBranch(*CurMBB, SuccBB, NULL, SmallVector<MachineOperand, 0>()); 50976b38fcabeba725e166a2ff72c56fe31d784b229Dale Johannesen} 51076b38fcabeba725e166a2ff72c56fe31d784b229Dale Johannesen 511ffe644ebf4dcc50b314261ddd2d08c841f629349Dan Gohmanbool 512ffe644ebf4dcc50b314261ddd2d08c841f629349Dan GohmanBranchFolder::MergePotentialsElt::operator<(const MergePotentialsElt &o) const { 513ffe644ebf4dcc50b314261ddd2d08c841f629349Dan Gohman if (getHash() < o.getHash()) 514ffe644ebf4dcc50b314261ddd2d08c841f629349Dan Gohman return true; 515ffe644ebf4dcc50b314261ddd2d08c841f629349Dan Gohman else if (getHash() > o.getHash()) 516ffe644ebf4dcc50b314261ddd2d08c841f629349Dan Gohman return false; 517ffe644ebf4dcc50b314261ddd2d08c841f629349Dan Gohman else if (getBlock()->getNumber() < o.getBlock()->getNumber()) 518ffe644ebf4dcc50b314261ddd2d08c841f629349Dan Gohman return true; 519ffe644ebf4dcc50b314261ddd2d08c841f629349Dan Gohman else if (getBlock()->getNumber() > o.getBlock()->getNumber()) 520ffe644ebf4dcc50b314261ddd2d08c841f629349Dan Gohman return false; 521ffe644ebf4dcc50b314261ddd2d08c841f629349Dan Gohman else { 522ffe644ebf4dcc50b314261ddd2d08c841f629349Dan Gohman // _GLIBCXX_DEBUG checks strict weak ordering, which involves comparing 523ffe644ebf4dcc50b314261ddd2d08c841f629349Dan Gohman // an object with itself. 52497b4ac8c844e08ce1c4f4a73b85ba56775a2a6c5Duncan Sands#ifndef _GLIBCXX_DEBUG 525ffe644ebf4dcc50b314261ddd2d08c841f629349Dan Gohman llvm_unreachable("Predecessor appears twice"); 52667fcdf7f6579fcc070f019096cedf80d5a834554David Greene#endif 527ffe644ebf4dcc50b314261ddd2d08c841f629349Dan Gohman return false; 528ffe644ebf4dcc50b314261ddd2d08c841f629349Dan Gohman } 52995ef406e0f2da0197f8b46849319c07e9bea1e55Dale Johannesen} 53095ef406e0f2da0197f8b46849319c07e9bea1e55Dale Johannesen 5312210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman/// CountTerminators - Count the number of terminators in the given 5322210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman/// block and set I to the position of the first non-terminator, if there 5332210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman/// is one, or MBB->end() otherwise. 5342210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohmanstatic unsigned CountTerminators(MachineBasicBlock *MBB, 5352210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman MachineBasicBlock::iterator &I) { 5362210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman I = MBB->end(); 5372210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman unsigned NumTerms = 0; 5382210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman for (;;) { 5392210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman if (I == MBB->begin()) { 5402210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman I = MBB->end(); 5412210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman break; 5422210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman } 5432210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman --I; 5442210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman if (!I->getDesc().isTerminator()) break; 5452210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman ++NumTerms; 5462210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman } 5472210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman return NumTerms; 5482210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman} 5492210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman 5507b888b8ad07cccec099634bc838eed5da3f336b1Bob Wilson/// ProfitableToMerge - Check if two machine basic blocks have a common tail 5517b888b8ad07cccec099634bc838eed5da3f336b1Bob Wilson/// and decide if it would be profitable to merge those tails. Return the 5527b888b8ad07cccec099634bc838eed5da3f336b1Bob Wilson/// length of the common tail and iterators to the first common instruction 5537b888b8ad07cccec099634bc838eed5da3f336b1Bob Wilson/// in each block. 5547b888b8ad07cccec099634bc838eed5da3f336b1Bob Wilsonstatic bool ProfitableToMerge(MachineBasicBlock *MBB1, 5557b888b8ad07cccec099634bc838eed5da3f336b1Bob Wilson MachineBasicBlock *MBB2, 5567b888b8ad07cccec099634bc838eed5da3f336b1Bob Wilson unsigned minCommonTailLength, 5577b888b8ad07cccec099634bc838eed5da3f336b1Bob Wilson unsigned &CommonTailLen, 5587b888b8ad07cccec099634bc838eed5da3f336b1Bob Wilson MachineBasicBlock::iterator &I1, 5592210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman MachineBasicBlock::iterator &I2, 5602210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman MachineBasicBlock *SuccBB, 5612210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman MachineBasicBlock *PredBB) { 5627b888b8ad07cccec099634bc838eed5da3f336b1Bob Wilson CommonTailLen = ComputeCommonTailLength(MBB1, MBB2, I1, I2); 5637b888b8ad07cccec099634bc838eed5da3f336b1Bob Wilson MachineFunction *MF = MBB1->getParent(); 5647b888b8ad07cccec099634bc838eed5da3f336b1Bob Wilson 5657b888b8ad07cccec099634bc838eed5da3f336b1Bob Wilson if (CommonTailLen == 0) 5667b888b8ad07cccec099634bc838eed5da3f336b1Bob Wilson return false; 5677b888b8ad07cccec099634bc838eed5da3f336b1Bob Wilson 5682210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman // It's almost always profitable to merge any number of non-terminator 5692210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman // instructions with the block that falls through into the common successor. 5702210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman if (MBB1 == PredBB || MBB2 == PredBB) { 5712210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman MachineBasicBlock::iterator I; 5722210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman unsigned NumTerms = CountTerminators(MBB1 == PredBB ? MBB2 : MBB1, I); 5732210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman if (CommonTailLen > NumTerms) 5742210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman return true; 5752210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman } 5762210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman 577ad6af45dc172fe23801771200eabb6a7f764e2cbDan Gohman // If one of the blocks can be completely merged and happens to be in 578ad6af45dc172fe23801771200eabb6a7f764e2cbDan Gohman // a position where the other could fall through into it, merge any number 579ad6af45dc172fe23801771200eabb6a7f764e2cbDan Gohman // of instructions, because it can be done without a branch. 580ad6af45dc172fe23801771200eabb6a7f764e2cbDan Gohman // TODO: If the blocks are not adjacent, move one of them so that they are? 581ad6af45dc172fe23801771200eabb6a7f764e2cbDan Gohman if (MBB1->isLayoutSuccessor(MBB2) && I2 == MBB2->begin()) 582ad6af45dc172fe23801771200eabb6a7f764e2cbDan Gohman return true; 583ad6af45dc172fe23801771200eabb6a7f764e2cbDan Gohman if (MBB2->isLayoutSuccessor(MBB1) && I1 == MBB1->begin()) 584ad6af45dc172fe23801771200eabb6a7f764e2cbDan Gohman return true; 585ad6af45dc172fe23801771200eabb6a7f764e2cbDan Gohman 5862210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman // If both blocks have an unconditional branch temporarily stripped out, 587c4c550c7584b3240bda71d4339ec49c1cf731d55Dan Gohman // count that as an additional common instruction for the following 588c4c550c7584b3240bda71d4339ec49c1cf731d55Dan Gohman // heuristics. 589c4c550c7584b3240bda71d4339ec49c1cf731d55Dan Gohman unsigned EffectiveTailLen = CommonTailLen; 5903cbc3120873242d93e469b4635c0bbd09fdb6438Bob Wilson if (SuccBB && MBB1 != PredBB && MBB2 != PredBB && 5912210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman !MBB1->back().getDesc().isBarrier() && 5922210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman !MBB2->back().getDesc().isBarrier()) 593c4c550c7584b3240bda71d4339ec49c1cf731d55Dan Gohman ++EffectiveTailLen; 5942210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman 5952210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman // Check if the common tail is long enough to be worthwhile. 596c4c550c7584b3240bda71d4339ec49c1cf731d55Dan Gohman if (EffectiveTailLen >= minCommonTailLength) 5972210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman return true; 5982210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman 599c4c550c7584b3240bda71d4339ec49c1cf731d55Dan Gohman // If we are optimizing for code size, 2 instructions in common is enough if 600c4c550c7584b3240bda71d4339ec49c1cf731d55Dan Gohman // we don't have to split a block. At worst we will be introducing 1 new 601c4c550c7584b3240bda71d4339ec49c1cf731d55Dan Gohman // branch instruction, which is likely to be smaller than the 2 602c4c550c7584b3240bda71d4339ec49c1cf731d55Dan Gohman // instructions that would be deleted in the merge. 603c4c550c7584b3240bda71d4339ec49c1cf731d55Dan Gohman if (EffectiveTailLen >= 2 && 604c4c550c7584b3240bda71d4339ec49c1cf731d55Dan Gohman MF->getFunction()->hasFnAttr(Attribute::OptimizeForSize) && 6057b888b8ad07cccec099634bc838eed5da3f336b1Bob Wilson (I1 == MBB1->begin() || I2 == MBB2->begin())) 6067b888b8ad07cccec099634bc838eed5da3f336b1Bob Wilson return true; 6077b888b8ad07cccec099634bc838eed5da3f336b1Bob Wilson 6087b888b8ad07cccec099634bc838eed5da3f336b1Bob Wilson return false; 6097b888b8ad07cccec099634bc838eed5da3f336b1Bob Wilson} 6107b888b8ad07cccec099634bc838eed5da3f336b1Bob Wilson 6116b8583cbf1f8a3df5ae859d3da2ca690ff57f91cDale Johannesen/// ComputeSameTails - Look through all the blocks in MergePotentials that have 6124e3f125e184f96ae72f2c44d16cafe0d44158283Dan Gohman/// hash CurHash (guaranteed to match the last element). Build the vector 6136b8583cbf1f8a3df5ae859d3da2ca690ff57f91cDale Johannesen/// SameTails of all those that have the (same) largest number of instructions 6146b8583cbf1f8a3df5ae859d3da2ca690ff57f91cDale Johannesen/// in common of any pair of these blocks. SameTails entries contain an 6154e3f125e184f96ae72f2c44d16cafe0d44158283Dan Gohman/// iterator into MergePotentials (from which the MachineBasicBlock can be 6164e3f125e184f96ae72f2c44d16cafe0d44158283Dan Gohman/// found) and a MachineBasicBlock::iterator into that MBB indicating the 6176b8583cbf1f8a3df5ae859d3da2ca690ff57f91cDale Johannesen/// instruction where the matching code sequence begins. 6186b8583cbf1f8a3df5ae859d3da2ca690ff57f91cDale Johannesen/// Order of elements in SameTails is the reverse of the order in which 6196b8583cbf1f8a3df5ae859d3da2ca690ff57f91cDale Johannesen/// those blocks appear in MergePotentials (where they are not necessarily 6206b8583cbf1f8a3df5ae859d3da2ca690ff57f91cDale Johannesen/// consecutive). 6214e3f125e184f96ae72f2c44d16cafe0d44158283Dan Gohmanunsigned BranchFolder::ComputeSameTails(unsigned CurHash, 6222210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman unsigned minCommonTailLength, 6232210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman MachineBasicBlock *SuccBB, 6242210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman MachineBasicBlock *PredBB) { 6256b8583cbf1f8a3df5ae859d3da2ca690ff57f91cDale Johannesen unsigned maxCommonTailLength = 0U; 6266b8583cbf1f8a3df5ae859d3da2ca690ff57f91cDale Johannesen SameTails.clear(); 6276b8583cbf1f8a3df5ae859d3da2ca690ff57f91cDale Johannesen MachineBasicBlock::iterator TrialBBI1, TrialBBI2; 6286b8583cbf1f8a3df5ae859d3da2ca690ff57f91cDale Johannesen MPIterator HighestMPIter = prior(MergePotentials.end()); 6296b8583cbf1f8a3df5ae859d3da2ca690ff57f91cDale Johannesen for (MPIterator CurMPIter = prior(MergePotentials.end()), 6304e3f125e184f96ae72f2c44d16cafe0d44158283Dan Gohman B = MergePotentials.begin(); 6318520149db158427339a235a74dd2cc19553a7328Dan Gohman CurMPIter != B && CurMPIter->getHash() == CurHash; 6326b8583cbf1f8a3df5ae859d3da2ca690ff57f91cDale Johannesen --CurMPIter) { 633ffe644ebf4dcc50b314261ddd2d08c841f629349Dan Gohman for (MPIterator I = prior(CurMPIter); I->getHash() == CurHash ; --I) { 6347b888b8ad07cccec099634bc838eed5da3f336b1Bob Wilson unsigned CommonTailLen; 635ffe644ebf4dcc50b314261ddd2d08c841f629349Dan Gohman if (ProfitableToMerge(CurMPIter->getBlock(), I->getBlock(), 636ffe644ebf4dcc50b314261ddd2d08c841f629349Dan Gohman minCommonTailLength, 6372210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman CommonTailLen, TrialBBI1, TrialBBI2, 6382210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman SuccBB, PredBB)) { 6396b8583cbf1f8a3df5ae859d3da2ca690ff57f91cDale Johannesen if (CommonTailLen > maxCommonTailLength) { 6406b8583cbf1f8a3df5ae859d3da2ca690ff57f91cDale Johannesen SameTails.clear(); 6416b8583cbf1f8a3df5ae859d3da2ca690ff57f91cDale Johannesen maxCommonTailLength = CommonTailLen; 6426b8583cbf1f8a3df5ae859d3da2ca690ff57f91cDale Johannesen HighestMPIter = CurMPIter; 643ffe644ebf4dcc50b314261ddd2d08c841f629349Dan Gohman SameTails.push_back(SameTailElt(CurMPIter, TrialBBI1)); 6446b8583cbf1f8a3df5ae859d3da2ca690ff57f91cDale Johannesen } 6456b8583cbf1f8a3df5ae859d3da2ca690ff57f91cDale Johannesen if (HighestMPIter == CurMPIter && 6466b8583cbf1f8a3df5ae859d3da2ca690ff57f91cDale Johannesen CommonTailLen == maxCommonTailLength) 647ffe644ebf4dcc50b314261ddd2d08c841f629349Dan Gohman SameTails.push_back(SameTailElt(I, TrialBBI2)); 6486b8583cbf1f8a3df5ae859d3da2ca690ff57f91cDale Johannesen } 6494e3f125e184f96ae72f2c44d16cafe0d44158283Dan Gohman if (I == B) 6506b8583cbf1f8a3df5ae859d3da2ca690ff57f91cDale Johannesen break; 6516b8583cbf1f8a3df5ae859d3da2ca690ff57f91cDale Johannesen } 6526b8583cbf1f8a3df5ae859d3da2ca690ff57f91cDale Johannesen } 6536b8583cbf1f8a3df5ae859d3da2ca690ff57f91cDale Johannesen return maxCommonTailLength; 6546b8583cbf1f8a3df5ae859d3da2ca690ff57f91cDale Johannesen} 6556b8583cbf1f8a3df5ae859d3da2ca690ff57f91cDale Johannesen 6566b8583cbf1f8a3df5ae859d3da2ca690ff57f91cDale Johannesen/// RemoveBlocksWithHash - Remove all blocks with hash CurHash from 6576b8583cbf1f8a3df5ae859d3da2ca690ff57f91cDale Johannesen/// MergePotentials, restoring branches at ends of blocks as appropriate. 6584e3f125e184f96ae72f2c44d16cafe0d44158283Dan Gohmanvoid BranchFolder::RemoveBlocksWithHash(unsigned CurHash, 659d34f5d91bc6fdc55085d3c4d509c778d6bcc5f0aBob Wilson MachineBasicBlock *SuccBB, 660d34f5d91bc6fdc55085d3c4d509c778d6bcc5f0aBob Wilson MachineBasicBlock *PredBB) { 661679860e31bd7b8f043ba1ccdc5990cb9bafd9055Dale Johannesen MPIterator CurMPIter, B; 6624e3f125e184f96ae72f2c44d16cafe0d44158283Dan Gohman for (CurMPIter = prior(MergePotentials.end()), B = MergePotentials.begin(); 663ffe644ebf4dcc50b314261ddd2d08c841f629349Dan Gohman CurMPIter->getHash() == CurHash; 6646b8583cbf1f8a3df5ae859d3da2ca690ff57f91cDale Johannesen --CurMPIter) { 6656b8583cbf1f8a3df5ae859d3da2ca690ff57f91cDale Johannesen // Put the unconditional branch back, if we need one. 666ffe644ebf4dcc50b314261ddd2d08c841f629349Dan Gohman MachineBasicBlock *CurMBB = CurMPIter->getBlock(); 6676b8583cbf1f8a3df5ae859d3da2ca690ff57f91cDale Johannesen if (SuccBB && CurMBB != PredBB) 6686b8583cbf1f8a3df5ae859d3da2ca690ff57f91cDale Johannesen FixTail(CurMBB, SuccBB, TII); 6694e3f125e184f96ae72f2c44d16cafe0d44158283Dan Gohman if (CurMPIter == B) 6706b8583cbf1f8a3df5ae859d3da2ca690ff57f91cDale Johannesen break; 6716b8583cbf1f8a3df5ae859d3da2ca690ff57f91cDale Johannesen } 672ffe644ebf4dcc50b314261ddd2d08c841f629349Dan Gohman if (CurMPIter->getHash() != CurHash) 673679860e31bd7b8f043ba1ccdc5990cb9bafd9055Dale Johannesen CurMPIter++; 674679860e31bd7b8f043ba1ccdc5990cb9bafd9055Dale Johannesen MergePotentials.erase(CurMPIter, MergePotentials.end()); 6756b8583cbf1f8a3df5ae859d3da2ca690ff57f91cDale Johannesen} 6766b8583cbf1f8a3df5ae859d3da2ca690ff57f91cDale Johannesen 67751b2b9e29e4fa828ffd83d36f548bc44a4007822Dale Johannesen/// CreateCommonTailOnlyBlock - None of the blocks to be tail-merged consist 67851b2b9e29e4fa828ffd83d36f548bc44a4007822Dale Johannesen/// only of the common tail. Create a block that does by splitting one. 67951b2b9e29e4fa828ffd83d36f548bc44a4007822Dale Johannesenunsigned BranchFolder::CreateCommonTailOnlyBlock(MachineBasicBlock *&PredBB, 68051b2b9e29e4fa828ffd83d36f548bc44a4007822Dale Johannesen unsigned maxCommonTailLength) { 6818520149db158427339a235a74dd2cc19553a7328Dan Gohman unsigned commonTailIndex = 0; 68251b2b9e29e4fa828ffd83d36f548bc44a4007822Dale Johannesen unsigned TimeEstimate = ~0U; 6838520149db158427339a235a74dd2cc19553a7328Dan Gohman for (unsigned i = 0, e = SameTails.size(); i != e; ++i) { 68451b2b9e29e4fa828ffd83d36f548bc44a4007822Dale Johannesen // Use PredBB if possible; that doesn't require a new branch. 685ffe644ebf4dcc50b314261ddd2d08c841f629349Dan Gohman if (SameTails[i].getBlock() == PredBB) { 68651b2b9e29e4fa828ffd83d36f548bc44a4007822Dale Johannesen commonTailIndex = i; 68751b2b9e29e4fa828ffd83d36f548bc44a4007822Dale Johannesen break; 68851b2b9e29e4fa828ffd83d36f548bc44a4007822Dale Johannesen } 68951b2b9e29e4fa828ffd83d36f548bc44a4007822Dale Johannesen // Otherwise, make a (fairly bogus) choice based on estimate of 69051b2b9e29e4fa828ffd83d36f548bc44a4007822Dale Johannesen // how long it will take the various blocks to execute. 691ffe644ebf4dcc50b314261ddd2d08c841f629349Dan Gohman unsigned t = EstimateRuntime(SameTails[i].getBlock()->begin(), 692ffe644ebf4dcc50b314261ddd2d08c841f629349Dan Gohman SameTails[i].getTailStartPos()); 6934e3f125e184f96ae72f2c44d16cafe0d44158283Dan Gohman if (t <= TimeEstimate) { 69451b2b9e29e4fa828ffd83d36f548bc44a4007822Dale Johannesen TimeEstimate = t; 69551b2b9e29e4fa828ffd83d36f548bc44a4007822Dale Johannesen commonTailIndex = i; 69651b2b9e29e4fa828ffd83d36f548bc44a4007822Dale Johannesen } 69751b2b9e29e4fa828ffd83d36f548bc44a4007822Dale Johannesen } 69851b2b9e29e4fa828ffd83d36f548bc44a4007822Dale Johannesen 699ffe644ebf4dcc50b314261ddd2d08c841f629349Dan Gohman MachineBasicBlock::iterator BBI = 700ffe644ebf4dcc50b314261ddd2d08c841f629349Dan Gohman SameTails[commonTailIndex].getTailStartPos(); 701ffe644ebf4dcc50b314261ddd2d08c841f629349Dan Gohman MachineBasicBlock *MBB = SameTails[commonTailIndex].getBlock(); 70251b2b9e29e4fa828ffd83d36f548bc44a4007822Dale Johannesen 70384839daa595968286acd25644820c644867f0c52Dale Johannesen // If the common tail includes any debug info we will take it pretty 70484839daa595968286acd25644820c644867f0c52Dale Johannesen // randomly from one of the inputs. Might be better to remove it? 705465e2b950d61c870fb3120c80191973e8282a3efDavid Greene DEBUG(dbgs() << "\nSplitting BB#" << MBB->getNumber() << ", size " 7063403bcd8f943cb053a7d9bbf8eb8135407699afaBill Wendling << maxCommonTailLength); 70751b2b9e29e4fa828ffd83d36f548bc44a4007822Dale Johannesen 70851b2b9e29e4fa828ffd83d36f548bc44a4007822Dale Johannesen MachineBasicBlock *newMBB = SplitMBBAt(*MBB, BBI); 709ffe644ebf4dcc50b314261ddd2d08c841f629349Dan Gohman SameTails[commonTailIndex].setBlock(newMBB); 710ffe644ebf4dcc50b314261ddd2d08c841f629349Dan Gohman SameTails[commonTailIndex].setTailStartPos(newMBB->begin()); 7114e3f125e184f96ae72f2c44d16cafe0d44158283Dan Gohman 71251b2b9e29e4fa828ffd83d36f548bc44a4007822Dale Johannesen // If we split PredBB, newMBB is the new predecessor. 7134e3f125e184f96ae72f2c44d16cafe0d44158283Dan Gohman if (PredBB == MBB) 71451b2b9e29e4fa828ffd83d36f548bc44a4007822Dale Johannesen PredBB = newMBB; 71551b2b9e29e4fa828ffd83d36f548bc44a4007822Dale Johannesen 71651b2b9e29e4fa828ffd83d36f548bc44a4007822Dale Johannesen return commonTailIndex; 71751b2b9e29e4fa828ffd83d36f548bc44a4007822Dale Johannesen} 71851b2b9e29e4fa828ffd83d36f548bc44a4007822Dale Johannesen 7197d33b4c59b56afb96feea71073c1d9e70c457e28Dale Johannesen// See if any of the blocks in MergePotentials (which all have a common single 7207d33b4c59b56afb96feea71073c1d9e70c457e28Dale Johannesen// successor, or all have no successor) can be tail-merged. If there is a 7217d33b4c59b56afb96feea71073c1d9e70c457e28Dale Johannesen// successor, any blocks in MergePotentials that are not tail-merged and 7227d33b4c59b56afb96feea71073c1d9e70c457e28Dale Johannesen// are not immediately before Succ must have an unconditional branch to 7234e3f125e184f96ae72f2c44d16cafe0d44158283Dan Gohman// Succ added (but the predecessor/successor lists need no adjustment). 7247d33b4c59b56afb96feea71073c1d9e70c457e28Dale Johannesen// The lone predecessor of Succ that falls through into Succ, 7257d33b4c59b56afb96feea71073c1d9e70c457e28Dale Johannesen// if any, is given in PredBB. 7267d33b4c59b56afb96feea71073c1d9e70c457e28Dale Johannesen 7272210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohmanbool BranchFolder::TryTailMergeBlocks(MachineBasicBlock *SuccBB, 728d34f5d91bc6fdc55085d3c4d509c778d6bcc5f0aBob Wilson MachineBasicBlock *PredBB) { 729030a0a0cdb38924e55773a8e0b5fe7347aa664aaEvan Cheng bool MadeChange = false; 730030a0a0cdb38924e55773a8e0b5fe7347aa664aaEvan Cheng 7312210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman // Except for the special cases below, tail-merge if there are at least 7322210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman // this many instructions in common. 7332210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman unsigned minCommonTailLength = TailMergeSize; 7342210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman 735465e2b950d61c870fb3120c80191973e8282a3efDavid Greene DEBUG(dbgs() << "\nTryTailMergeBlocks: "; 7362210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman for (unsigned i = 0, e = MergePotentials.size(); i != e; ++i) 737465e2b950d61c870fb3120c80191973e8282a3efDavid Greene dbgs() << "BB#" << MergePotentials[i].getBlock()->getNumber() 7382210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman << (i == e-1 ? "" : ", "); 739465e2b950d61c870fb3120c80191973e8282a3efDavid Greene dbgs() << "\n"; 7402210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman if (SuccBB) { 741465e2b950d61c870fb3120c80191973e8282a3efDavid Greene dbgs() << " with successor BB#" << SuccBB->getNumber() << '\n'; 7422210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman if (PredBB) 743465e2b950d61c870fb3120c80191973e8282a3efDavid Greene dbgs() << " which has fall-through from BB#" 7442210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman << PredBB->getNumber() << "\n"; 7452210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman } 746465e2b950d61c870fb3120c80191973e8282a3efDavid Greene dbgs() << "Looking for common tails of at least " 7472210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman << minCommonTailLength << " instruction" 7482210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman << (minCommonTailLength == 1 ? "" : "s") << '\n'; 7492210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman ); 7506b8583cbf1f8a3df5ae859d3da2ca690ff57f91cDale Johannesen 75112143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner // Sort by hash value so that blocks with identical end sequences sort 75212143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner // together. 753ffe644ebf4dcc50b314261ddd2d08c841f629349Dan Gohman std::stable_sort(MergePotentials.begin(), MergePotentials.end()); 75412143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner 75512143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner // Walk through equivalence sets looking for actual exact matches. 75612143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner while (MergePotentials.size() > 1) { 757ffe644ebf4dcc50b314261ddd2d08c841f629349Dan Gohman unsigned CurHash = MergePotentials.back().getHash(); 7584e3f125e184f96ae72f2c44d16cafe0d44158283Dan Gohman 7596b8583cbf1f8a3df5ae859d3da2ca690ff57f91cDale Johannesen // Build SameTails, identifying the set of blocks with this hash code 7606b8583cbf1f8a3df5ae859d3da2ca690ff57f91cDale Johannesen // and with the maximum number of instructions in common. 7614e3f125e184f96ae72f2c44d16cafe0d44158283Dan Gohman unsigned maxCommonTailLength = ComputeSameTails(CurHash, 7622210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman minCommonTailLength, 7632210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman SuccBB, PredBB); 7647aea8320340ce867eb4328aeec52cb02c88ef0b3Dale Johannesen 7654e3f125e184f96ae72f2c44d16cafe0d44158283Dan Gohman // If we didn't find any pair that has at least minCommonTailLength 7666ae83faadf715c398e637424a764f6b02f0b6df2Dale Johannesen // instructions in common, remove all blocks with this hash code and retry. 7676ae83faadf715c398e637424a764f6b02f0b6df2Dale Johannesen if (SameTails.empty()) { 7686b8583cbf1f8a3df5ae859d3da2ca690ff57f91cDale Johannesen RemoveBlocksWithHash(CurHash, SuccBB, PredBB); 7697aea8320340ce867eb4328aeec52cb02c88ef0b3Dale Johannesen continue; 7707aea8320340ce867eb4328aeec52cb02c88ef0b3Dale Johannesen } 7711d08d83230338ca5969ff6ae6737a978336538bfChris Lattner 7726ae83faadf715c398e637424a764f6b02f0b6df2Dale Johannesen // If one of the blocks is the entire common tail (and not the entry 77351b2b9e29e4fa828ffd83d36f548bc44a4007822Dale Johannesen // block, which we can't jump to), we can treat all blocks with this same 77451b2b9e29e4fa828ffd83d36f548bc44a4007822Dale Johannesen // tail at once. Use PredBB if that is one of the possibilities, as that 77551b2b9e29e4fa828ffd83d36f548bc44a4007822Dale Johannesen // will not introduce any extra branches. 776ffe644ebf4dcc50b314261ddd2d08c841f629349Dan Gohman MachineBasicBlock *EntryBB = MergePotentials.begin()->getBlock()-> 777ffe644ebf4dcc50b314261ddd2d08c841f629349Dan Gohman getParent()->begin(); 778ffe644ebf4dcc50b314261ddd2d08c841f629349Dan Gohman unsigned commonTailIndex = SameTails.size(); 779ad6af45dc172fe23801771200eabb6a7f764e2cbDan Gohman // If there are two blocks, check to see if one can be made to fall through 780ad6af45dc172fe23801771200eabb6a7f764e2cbDan Gohman // into the other. 781ad6af45dc172fe23801771200eabb6a7f764e2cbDan Gohman if (SameTails.size() == 2 && 782ad6af45dc172fe23801771200eabb6a7f764e2cbDan Gohman SameTails[0].getBlock()->isLayoutSuccessor(SameTails[1].getBlock()) && 783ad6af45dc172fe23801771200eabb6a7f764e2cbDan Gohman SameTails[1].tailIsWholeBlock()) 784ad6af45dc172fe23801771200eabb6a7f764e2cbDan Gohman commonTailIndex = 1; 785ad6af45dc172fe23801771200eabb6a7f764e2cbDan Gohman else if (SameTails.size() == 2 && 786ad6af45dc172fe23801771200eabb6a7f764e2cbDan Gohman SameTails[1].getBlock()->isLayoutSuccessor( 787ad6af45dc172fe23801771200eabb6a7f764e2cbDan Gohman SameTails[0].getBlock()) && 788ad6af45dc172fe23801771200eabb6a7f764e2cbDan Gohman SameTails[0].tailIsWholeBlock()) 789ad6af45dc172fe23801771200eabb6a7f764e2cbDan Gohman commonTailIndex = 0; 790ad6af45dc172fe23801771200eabb6a7f764e2cbDan Gohman else { 791ad6af45dc172fe23801771200eabb6a7f764e2cbDan Gohman // Otherwise just pick one, favoring the fall-through predecessor if 792ad6af45dc172fe23801771200eabb6a7f764e2cbDan Gohman // there is one. 793ad6af45dc172fe23801771200eabb6a7f764e2cbDan Gohman for (unsigned i = 0, e = SameTails.size(); i != e; ++i) { 794ad6af45dc172fe23801771200eabb6a7f764e2cbDan Gohman MachineBasicBlock *MBB = SameTails[i].getBlock(); 795ad6af45dc172fe23801771200eabb6a7f764e2cbDan Gohman if (MBB == EntryBB && SameTails[i].tailIsWholeBlock()) 796ad6af45dc172fe23801771200eabb6a7f764e2cbDan Gohman continue; 797ad6af45dc172fe23801771200eabb6a7f764e2cbDan Gohman if (MBB == PredBB) { 798ad6af45dc172fe23801771200eabb6a7f764e2cbDan Gohman commonTailIndex = i; 799ad6af45dc172fe23801771200eabb6a7f764e2cbDan Gohman break; 800ad6af45dc172fe23801771200eabb6a7f764e2cbDan Gohman } 801ad6af45dc172fe23801771200eabb6a7f764e2cbDan Gohman if (SameTails[i].tailIsWholeBlock()) 802ad6af45dc172fe23801771200eabb6a7f764e2cbDan Gohman commonTailIndex = i; 8036ae83faadf715c398e637424a764f6b02f0b6df2Dale Johannesen } 8046ae83faadf715c398e637424a764f6b02f0b6df2Dale Johannesen } 8056ae83faadf715c398e637424a764f6b02f0b6df2Dale Johannesen 8062210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman if (commonTailIndex == SameTails.size() || 807ffe644ebf4dcc50b314261ddd2d08c841f629349Dan Gohman (SameTails[commonTailIndex].getBlock() == PredBB && 808ffe644ebf4dcc50b314261ddd2d08c841f629349Dan Gohman !SameTails[commonTailIndex].tailIsWholeBlock())) { 80951b2b9e29e4fa828ffd83d36f548bc44a4007822Dale Johannesen // None of the blocks consist entirely of the common tail. 81051b2b9e29e4fa828ffd83d36f548bc44a4007822Dale Johannesen // Split a block so that one does. 8112210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman commonTailIndex = CreateCommonTailOnlyBlock(PredBB, maxCommonTailLength); 8121d08d83230338ca5969ff6ae6737a978336538bfChris Lattner } 81351b2b9e29e4fa828ffd83d36f548bc44a4007822Dale Johannesen 814ffe644ebf4dcc50b314261ddd2d08c841f629349Dan Gohman MachineBasicBlock *MBB = SameTails[commonTailIndex].getBlock(); 81551b2b9e29e4fa828ffd83d36f548bc44a4007822Dale Johannesen // MBB is common tail. Adjust all other BB's to jump to this one. 81651b2b9e29e4fa828ffd83d36f548bc44a4007822Dale Johannesen // Traversal must be forwards so erases work. 817465e2b950d61c870fb3120c80191973e8282a3efDavid Greene DEBUG(dbgs() << "\nUsing common tail in BB#" << MBB->getNumber() 8182210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman << " for "); 8192210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman for (unsigned int i=0, e = SameTails.size(); i != e; ++i) { 8204e3f125e184f96ae72f2c44d16cafe0d44158283Dan Gohman if (commonTailIndex == i) 82151b2b9e29e4fa828ffd83d36f548bc44a4007822Dale Johannesen continue; 822465e2b950d61c870fb3120c80191973e8282a3efDavid Greene DEBUG(dbgs() << "BB#" << SameTails[i].getBlock()->getNumber() 8232210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman << (i == e-1 ? "" : ", ")); 82451b2b9e29e4fa828ffd83d36f548bc44a4007822Dale Johannesen // Hack the end off BB i, making it jump to BB commonTailIndex instead. 825ffe644ebf4dcc50b314261ddd2d08c841f629349Dan Gohman ReplaceTailWithBranchTo(SameTails[i].getTailStartPos(), MBB); 82651b2b9e29e4fa828ffd83d36f548bc44a4007822Dale Johannesen // BB i is no longer a predecessor of SuccBB; remove it from the worklist. 827ffe644ebf4dcc50b314261ddd2d08c841f629349Dan Gohman MergePotentials.erase(SameTails[i].getMPIter()); 82812143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner } 829465e2b950d61c870fb3120c80191973e8282a3efDavid Greene DEBUG(dbgs() << "\n"); 83051b2b9e29e4fa828ffd83d36f548bc44a4007822Dale Johannesen // We leave commonTailIndex in the worklist in case there are other blocks 83151b2b9e29e4fa828ffd83d36f548bc44a4007822Dale Johannesen // that match it with a smaller number of instructions. 8321d08d83230338ca5969ff6ae6737a978336538bfChris Lattner MadeChange = true; 83321ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner } 83412143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner return MadeChange; 83512143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner} 83621ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner 8377d33b4c59b56afb96feea71073c1d9e70c457e28Dale Johannesenbool BranchFolder::TailMergeBlocks(MachineFunction &MF) { 83876b38fcabeba725e166a2ff72c56fe31d784b229Dale Johannesen 8397d33b4c59b56afb96feea71073c1d9e70c457e28Dale Johannesen if (!EnableTailMerge) return false; 8404e3f125e184f96ae72f2c44d16cafe0d44158283Dan Gohman 841030a0a0cdb38924e55773a8e0b5fe7347aa664aaEvan Cheng bool MadeChange = false; 84276b38fcabeba725e166a2ff72c56fe31d784b229Dale Johannesen 8437d33b4c59b56afb96feea71073c1d9e70c457e28Dale Johannesen // First find blocks with no successors. 84476b38fcabeba725e166a2ff72c56fe31d784b229Dale Johannesen MergePotentials.clear(); 8457d33b4c59b56afb96feea71073c1d9e70c457e28Dale Johannesen for (MachineFunction::iterator I = MF.begin(), E = MF.end(); I != E; ++I) { 8467d33b4c59b56afb96feea71073c1d9e70c457e28Dale Johannesen if (I->succ_empty()) 847ffe644ebf4dcc50b314261ddd2d08c841f629349Dan Gohman MergePotentials.push_back(MergePotentialsElt(HashEndOfMBB(I, 2U), I)); 8487d33b4c59b56afb96feea71073c1d9e70c457e28Dale Johannesen } 8494e3f125e184f96ae72f2c44d16cafe0d44158283Dan Gohman 85076b38fcabeba725e166a2ff72c56fe31d784b229Dale Johannesen // See if we can do any tail merging on those. 8516ae83faadf715c398e637424a764f6b02f0b6df2Dale Johannesen if (MergePotentials.size() < TailMergeThreshold && 8526ae83faadf715c398e637424a764f6b02f0b6df2Dale Johannesen MergePotentials.size() >= 2) 8532210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman MadeChange |= TryTailMergeBlocks(NULL, NULL); 8547d33b4c59b56afb96feea71073c1d9e70c457e28Dale Johannesen 85576b38fcabeba725e166a2ff72c56fe31d784b229Dale Johannesen // Look at blocks (IBB) with multiple predecessors (PBB). 85676b38fcabeba725e166a2ff72c56fe31d784b229Dale Johannesen // We change each predecessor to a canonical form, by 85776b38fcabeba725e166a2ff72c56fe31d784b229Dale Johannesen // (1) temporarily removing any unconditional branch from the predecessor 85876b38fcabeba725e166a2ff72c56fe31d784b229Dale Johannesen // to IBB, and 85976b38fcabeba725e166a2ff72c56fe31d784b229Dale Johannesen // (2) alter conditional branches so they branch to the other block 8604e3f125e184f96ae72f2c44d16cafe0d44158283Dan Gohman // not IBB; this may require adding back an unconditional branch to IBB 86176b38fcabeba725e166a2ff72c56fe31d784b229Dale Johannesen // later, where there wasn't one coming in. E.g. 86276b38fcabeba725e166a2ff72c56fe31d784b229Dale Johannesen // Bcc IBB 86376b38fcabeba725e166a2ff72c56fe31d784b229Dale Johannesen // fallthrough to QBB 86476b38fcabeba725e166a2ff72c56fe31d784b229Dale Johannesen // here becomes 86576b38fcabeba725e166a2ff72c56fe31d784b229Dale Johannesen // Bncc QBB 86676b38fcabeba725e166a2ff72c56fe31d784b229Dale Johannesen // with a conceptual B to IBB after that, which never actually exists. 86776b38fcabeba725e166a2ff72c56fe31d784b229Dale Johannesen // With those changes, we see whether the predecessors' tails match, 86876b38fcabeba725e166a2ff72c56fe31d784b229Dale Johannesen // and merge them if so. We change things out of canonical form and 86976b38fcabeba725e166a2ff72c56fe31d784b229Dale Johannesen // back to the way they were later in the process. (OptimizeBranches 87076b38fcabeba725e166a2ff72c56fe31d784b229Dale Johannesen // would undo some of this, but we can't use it, because we'd get into 87176b38fcabeba725e166a2ff72c56fe31d784b229Dale Johannesen // a compile-time infinite loop repeatedly doing and undoing the same 87276b38fcabeba725e166a2ff72c56fe31d784b229Dale Johannesen // transformations.) 8737d33b4c59b56afb96feea71073c1d9e70c457e28Dale Johannesen 8747896c9f436a4eda5ec15e882a7505ba482a2fcd0Chris Lattner for (MachineFunction::iterator I = llvm::next(MF.begin()), E = MF.end(); 8752210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman I != E; ++I) { 87662bc8a44868bd86e96bdbd2f0d66dda690cc66adDale Johannesen if (I->pred_size() >= 2 && I->pred_size() < TailMergeThreshold) { 877da65822cfc938594f8fb7840947c1eb77e057a48Dan Gohman SmallPtrSet<MachineBasicBlock *, 8> UniquePreds; 8787d33b4c59b56afb96feea71073c1d9e70c457e28Dale Johannesen MachineBasicBlock *IBB = I; 8797d33b4c59b56afb96feea71073c1d9e70c457e28Dale Johannesen MachineBasicBlock *PredBB = prior(I); 88076b38fcabeba725e166a2ff72c56fe31d784b229Dale Johannesen MergePotentials.clear(); 8814e3f125e184f96ae72f2c44d16cafe0d44158283Dan Gohman for (MachineBasicBlock::pred_iterator P = I->pred_begin(), 8821a90a5aebe3488dc3feaab60ba16bed1659ba27bDale Johannesen E2 = I->pred_end(); 8837d33b4c59b56afb96feea71073c1d9e70c457e28Dale Johannesen P != E2; ++P) { 884d34f5d91bc6fdc55085d3c4d509c778d6bcc5f0aBob Wilson MachineBasicBlock *PBB = *P; 88576b38fcabeba725e166a2ff72c56fe31d784b229Dale Johannesen // Skip blocks that loop to themselves, can't tail merge these. 8864e3f125e184f96ae72f2c44d16cafe0d44158283Dan Gohman if (PBB == IBB) 88776b38fcabeba725e166a2ff72c56fe31d784b229Dale Johannesen continue; 888da65822cfc938594f8fb7840947c1eb77e057a48Dan Gohman // Visit each predecessor only once. 889da65822cfc938594f8fb7840947c1eb77e057a48Dan Gohman if (!UniquePreds.insert(PBB)) 890da65822cfc938594f8fb7840947c1eb77e057a48Dan Gohman continue; 8917d33b4c59b56afb96feea71073c1d9e70c457e28Dale Johannesen MachineBasicBlock *TBB = 0, *FBB = 0; 89244eb65cf58e3ab9b5621ce72256d1621a18aeed7Owen Anderson SmallVector<MachineOperand, 4> Cond; 893dc54d317e7a381ef8e4aca80d54ad1466bb85ddaEvan Cheng if (!TII->AnalyzeBranch(*PBB, TBB, FBB, Cond, true)) { 89476b38fcabeba725e166a2ff72c56fe31d784b229Dale Johannesen // Failing case: IBB is the target of a cbr, and 89576b38fcabeba725e166a2ff72c56fe31d784b229Dale Johannesen // we cannot reverse the branch. 89644eb65cf58e3ab9b5621ce72256d1621a18aeed7Owen Anderson SmallVector<MachineOperand, 4> NewCond(Cond); 8974e3f125e184f96ae72f2c44d16cafe0d44158283Dan Gohman if (!Cond.empty() && TBB == IBB) { 89876b38fcabeba725e166a2ff72c56fe31d784b229Dale Johannesen if (TII->ReverseBranchCondition(NewCond)) 89976b38fcabeba725e166a2ff72c56fe31d784b229Dale Johannesen continue; 90076b38fcabeba725e166a2ff72c56fe31d784b229Dale Johannesen // This is the QBB case described above 90176b38fcabeba725e166a2ff72c56fe31d784b229Dale Johannesen if (!FBB) 9027896c9f436a4eda5ec15e882a7505ba482a2fcd0Chris Lattner FBB = llvm::next(MachineFunction::iterator(PBB)); 90376b38fcabeba725e166a2ff72c56fe31d784b229Dale Johannesen } 904fe7e397100edd4f2d618a1ff938dfa8624670ec1Dale Johannesen // Failing case: the only way IBB can be reached from PBB is via 905fe7e397100edd4f2d618a1ff938dfa8624670ec1Dale Johannesen // exception handling. Happens for landing pads. Would be nice 906fe7e397100edd4f2d618a1ff938dfa8624670ec1Dale Johannesen // to have a bit in the edge so we didn't have to do all this. 907fe7e397100edd4f2d618a1ff938dfa8624670ec1Dale Johannesen if (IBB->isLandingPad()) { 908fe7e397100edd4f2d618a1ff938dfa8624670ec1Dale Johannesen MachineFunction::iterator IP = PBB; IP++; 909d34f5d91bc6fdc55085d3c4d509c778d6bcc5f0aBob Wilson MachineBasicBlock *PredNextBB = NULL; 9108520149db158427339a235a74dd2cc19553a7328Dan Gohman if (IP != MF.end()) 911fe7e397100edd4f2d618a1ff938dfa8624670ec1Dale Johannesen PredNextBB = IP; 9124e3f125e184f96ae72f2c44d16cafe0d44158283Dan Gohman if (TBB == NULL) { 9138520149db158427339a235a74dd2cc19553a7328Dan Gohman if (IBB != PredNextBB) // fallthrough 914fe7e397100edd4f2d618a1ff938dfa8624670ec1Dale Johannesen continue; 915fe7e397100edd4f2d618a1ff938dfa8624670ec1Dale Johannesen } else if (FBB) { 9168520149db158427339a235a74dd2cc19553a7328Dan Gohman if (TBB != IBB && FBB != IBB) // cbr then ubr 917fe7e397100edd4f2d618a1ff938dfa8624670ec1Dale Johannesen continue; 918303595942502f17c087fa28874c2b89117148c45Dan Gohman } else if (Cond.empty()) { 9198520149db158427339a235a74dd2cc19553a7328Dan Gohman if (TBB != IBB) // ubr 920fe7e397100edd4f2d618a1ff938dfa8624670ec1Dale Johannesen continue; 921fe7e397100edd4f2d618a1ff938dfa8624670ec1Dale Johannesen } else { 9228520149db158427339a235a74dd2cc19553a7328Dan Gohman if (TBB != IBB && IBB != PredNextBB) // cbr 923fe7e397100edd4f2d618a1ff938dfa8624670ec1Dale Johannesen continue; 924fe7e397100edd4f2d618a1ff938dfa8624670ec1Dale Johannesen } 925fe7e397100edd4f2d618a1ff938dfa8624670ec1Dale Johannesen } 92676b38fcabeba725e166a2ff72c56fe31d784b229Dale Johannesen // Remove the unconditional branch at the end, if any. 9276b8583cbf1f8a3df5ae859d3da2ca690ff57f91cDale Johannesen if (TBB && (Cond.empty() || FBB)) { 9287d33b4c59b56afb96feea71073c1d9e70c457e28Dale Johannesen TII->RemoveBranch(*PBB); 9296b8583cbf1f8a3df5ae859d3da2ca690ff57f91cDale Johannesen if (!Cond.empty()) 9307d33b4c59b56afb96feea71073c1d9e70c457e28Dale Johannesen // reinsert conditional branch only, for now 9314e3f125e184f96ae72f2c44d16cafe0d44158283Dan Gohman TII->InsertBranch(*PBB, (TBB == IBB) ? FBB : TBB, 0, NewCond); 9327d33b4c59b56afb96feea71073c1d9e70c457e28Dale Johannesen } 933ffe644ebf4dcc50b314261ddd2d08c841f629349Dan Gohman MergePotentials.push_back(MergePotentialsElt(HashEndOfMBB(PBB, 1U), 934ffe644ebf4dcc50b314261ddd2d08c841f629349Dan Gohman *P)); 9357d33b4c59b56afb96feea71073c1d9e70c457e28Dale Johannesen } 9367d33b4c59b56afb96feea71073c1d9e70c457e28Dale Johannesen } 937cdc06ba5dfdded6cdc48061d36b63b807962ab31Dan Gohman if (MergePotentials.size() >= 2) 9382210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman MadeChange |= TryTailMergeBlocks(IBB, PredBB); 939cdc06ba5dfdded6cdc48061d36b63b807962ab31Dan Gohman // Reinsert an unconditional branch if needed. 9402210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman // The 1 below can occur as a result of removing blocks in TryTailMergeBlocks. 9412210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman PredBB = prior(I); // this may have been changed in TryTailMergeBlocks 942cdc06ba5dfdded6cdc48061d36b63b807962ab31Dan Gohman if (MergePotentials.size() == 1 && 943ffe644ebf4dcc50b314261ddd2d08c841f629349Dan Gohman MergePotentials.begin()->getBlock() != PredBB) 944ffe644ebf4dcc50b314261ddd2d08c841f629349Dan Gohman FixTail(MergePotentials.begin()->getBlock(), IBB, TII); 9457d33b4c59b56afb96feea71073c1d9e70c457e28Dale Johannesen } 9467d33b4c59b56afb96feea71073c1d9e70c457e28Dale Johannesen } 9477d33b4c59b56afb96feea71073c1d9e70c457e28Dale Johannesen return MadeChange; 9487d33b4c59b56afb96feea71073c1d9e70c457e28Dale Johannesen} 94912143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner 95012143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner//===----------------------------------------------------------------------===// 95112143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner// Branch Optimization 95212143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner//===----------------------------------------------------------------------===// 95312143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner 95412143054aa6d120f029d268a5154bf2ecd0f707fChris Lattnerbool BranchFolder::OptimizeBranches(MachineFunction &MF) { 955030a0a0cdb38924e55773a8e0b5fe7347aa664aaEvan Cheng bool MadeChange = false; 9564e3f125e184f96ae72f2c44d16cafe0d44158283Dan Gohman 9576b896cec8b703e08e5f3d809e086a39b6ebe6589Dale Johannesen // Make sure blocks are numbered in order 9586b896cec8b703e08e5f3d809e086a39b6ebe6589Dale Johannesen MF.RenumberBlocks(); 9596b896cec8b703e08e5f3d809e086a39b6ebe6589Dale Johannesen 96012143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner for (MachineFunction::iterator I = ++MF.begin(), E = MF.end(); I != E; ) { 96112143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner MachineBasicBlock *MBB = I++; 962030a0a0cdb38924e55773a8e0b5fe7347aa664aaEvan Cheng MadeChange |= OptimizeBlock(MBB); 9634e3f125e184f96ae72f2c44d16cafe0d44158283Dan Gohman 96412143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner // If it is dead, remove it. 965033c9715d9bf7ce59ad2e466bf0720811b34da08Jim Laskey if (MBB->pred_empty()) { 96612143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner RemoveDeadBlock(MBB); 96712143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner MadeChange = true; 96812143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner ++NumDeadBlocks; 96912143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner } 97012143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner } 97112143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner return MadeChange; 97221ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner} 97321ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner 974c5cf227f3dac755508928b9dee8ac6a45dcb4e4fDale Johannesen// Blocks should be considered empty if they contain only debug info; 975c5cf227f3dac755508928b9dee8ac6a45dcb4e4fDale Johannesen// else the debug info would affect codegen. 976c5cf227f3dac755508928b9dee8ac6a45dcb4e4fDale Johannesenstatic bool IsEmptyBlock(MachineBasicBlock *MBB) { 977c5cf227f3dac755508928b9dee8ac6a45dcb4e4fDale Johannesen if (MBB->empty()) 978c5cf227f3dac755508928b9dee8ac6a45dcb4e4fDale Johannesen return true; 979c5cf227f3dac755508928b9dee8ac6a45dcb4e4fDale Johannesen for (MachineBasicBlock::iterator MBBI = MBB->begin(), MBBE = MBB->end(); 980c5cf227f3dac755508928b9dee8ac6a45dcb4e4fDale Johannesen MBBI!=MBBE; ++MBBI) { 981c5cf227f3dac755508928b9dee8ac6a45dcb4e4fDale Johannesen if (!MBBI->isDebugValue()) 982c5cf227f3dac755508928b9dee8ac6a45dcb4e4fDale Johannesen return false; 983c5cf227f3dac755508928b9dee8ac6a45dcb4e4fDale Johannesen } 984c5cf227f3dac755508928b9dee8ac6a45dcb4e4fDale Johannesen return true; 985c5cf227f3dac755508928b9dee8ac6a45dcb4e4fDale Johannesen} 98612143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner 987a7bef4a4e49f461984c04ef6be6eef3f1c023558Chris Lattner/// IsBetterFallthrough - Return true if it would be clearly better to 988a7bef4a4e49f461984c04ef6be6eef3f1c023558Chris Lattner/// fall-through to MBB1 than to fall through into MBB2. This has to return 989a7bef4a4e49f461984c04ef6be6eef3f1c023558Chris Lattner/// a strict ordering, returning true for both (MBB1,MBB2) and (MBB2,MBB1) will 990a7bef4a4e49f461984c04ef6be6eef3f1c023558Chris Lattner/// result in infinite loops. 9914e3f125e184f96ae72f2c44d16cafe0d44158283Dan Gohmanstatic bool IsBetterFallthrough(MachineBasicBlock *MBB1, 99269244300b8a0112efb44b6273ecea4ca6264b8cfChris Lattner MachineBasicBlock *MBB2) { 993154e1047184384afd0a701a9f8816459cf0b3490Chris Lattner // Right now, we use a simple heuristic. If MBB2 ends with a call, and 994154e1047184384afd0a701a9f8816459cf0b3490Chris Lattner // MBB1 doesn't, we prefer to fall through into MBB1. This allows us to 995a7bef4a4e49f461984c04ef6be6eef3f1c023558Chris Lattner // optimize branches that branch to either a return block or an assert block 996a7bef4a4e49f461984c04ef6be6eef3f1c023558Chris Lattner // into a fallthrough to the return. 997a7bef4a4e49f461984c04ef6be6eef3f1c023558Chris Lattner if (MBB1->empty() || MBB2->empty()) return false; 9984e3f125e184f96ae72f2c44d16cafe0d44158283Dan Gohman 99911a4f64bd4cb6d438dd4b5882ee1b7404832f27fChristopher Lamb // If there is a clear successor ordering we make sure that one block 100011a4f64bd4cb6d438dd4b5882ee1b7404832f27fChristopher Lamb // will fall through to the next 100111a4f64bd4cb6d438dd4b5882ee1b7404832f27fChristopher Lamb if (MBB1->isSuccessor(MBB2)) return true; 100211a4f64bd4cb6d438dd4b5882ee1b7404832f27fChristopher Lamb if (MBB2->isSuccessor(MBB1)) return false; 1003a7bef4a4e49f461984c04ef6be6eef3f1c023558Chris Lattner 1004a7bef4a4e49f461984c04ef6be6eef3f1c023558Chris Lattner MachineInstr *MBB1I = --MBB1->end(); 1005a7bef4a4e49f461984c04ef6be6eef3f1c023558Chris Lattner MachineInstr *MBB2I = --MBB2->end(); 1006749c6f6b5ed301c84aac562e414486549d7b98ebChris Lattner return MBB2I->getDesc().isCall() && !MBB1I->getDesc().isCall(); 1007a7bef4a4e49f461984c04ef6be6eef3f1c023558Chris Lattner} 1008a7bef4a4e49f461984c04ef6be6eef3f1c023558Chris Lattner 10097821a8afd3009c3c2760592e61de9e2c31c73e18Chris Lattner/// OptimizeBlock - Analyze and optimize control flow related to the specified 10107821a8afd3009c3c2760592e61de9e2c31c73e18Chris Lattner/// block. This is never called on the entry block. 1011030a0a0cdb38924e55773a8e0b5fe7347aa664aaEvan Chengbool BranchFolder::OptimizeBlock(MachineBasicBlock *MBB) { 1012030a0a0cdb38924e55773a8e0b5fe7347aa664aaEvan Cheng bool MadeChange = false; 1013d194498d2669e28cd8e85b0ceb7c69a7ec66da13Dan Gohman MachineFunction &MF = *MBB->getParent(); 10142210c0bea83aa8a8585d793a1f63e8c01b65be38Dan GohmanReoptimizeBlock: 1015030a0a0cdb38924e55773a8e0b5fe7347aa664aaEvan Cheng 10167d09784d3fc652131a2afbf06a0f2ed893837fb9Chris Lattner MachineFunction::iterator FallThrough = MBB; 10177d09784d3fc652131a2afbf06a0f2ed893837fb9Chris Lattner ++FallThrough; 10184e3f125e184f96ae72f2c44d16cafe0d44158283Dan Gohman 1019eb15eeec396145b6f5028d07bd2c4a5e903fdec5Chris Lattner // If this block is empty, make everyone use its fall-through, not the block 1020a52dd151378eeaad1369829b1dc3164874774e04Dale Johannesen // explicitly. Landing pads should not do this since the landing-pad table 1021ab918103d284b91105831c6b198ad2ab760b907dDan Gohman // points to this block. Blocks with their addresses taken shouldn't be 1022ab918103d284b91105831c6b198ad2ab760b907dDan Gohman // optimized away. 1023c5cf227f3dac755508928b9dee8ac6a45dcb4e4fDale Johannesen if (IsEmptyBlock(MBB) && !MBB->isLandingPad() && !MBB->hasAddressTaken()) { 1024386e29065db5b05b57440f6b2a6dfa1e7f29a00dChris Lattner // Dead block? Leave for cleanup later. 1025030a0a0cdb38924e55773a8e0b5fe7347aa664aaEvan Cheng if (MBB->pred_empty()) return MadeChange; 10264e3f125e184f96ae72f2c44d16cafe0d44158283Dan Gohman 1027d194498d2669e28cd8e85b0ceb7c69a7ec66da13Dan Gohman if (FallThrough == MF.end()) { 1028c50ffcb7fcb7c1109fee2406e8f74d096f755f47Chris Lattner // TODO: Simplify preds to not branch here if possible! 1029c50ffcb7fcb7c1109fee2406e8f74d096f755f47Chris Lattner } else { 1030c50ffcb7fcb7c1109fee2406e8f74d096f755f47Chris Lattner // Rewrite all predecessors of the old block to go to the fallthrough 1031c50ffcb7fcb7c1109fee2406e8f74d096f755f47Chris Lattner // instead. 1032033c9715d9bf7ce59ad2e466bf0720811b34da08Jim Laskey while (!MBB->pred_empty()) { 10337821a8afd3009c3c2760592e61de9e2c31c73e18Chris Lattner MachineBasicBlock *Pred = *(MBB->pred_end()-1); 10340370fad74b48388412c52d1325512f2c218487faEvan Cheng Pred->ReplaceUsesOfBlockWith(MBB, FallThrough); 10357821a8afd3009c3c2760592e61de9e2c31c73e18Chris Lattner } 1036c50ffcb7fcb7c1109fee2406e8f74d096f755f47Chris Lattner // If MBB was the target of a jump table, update jump tables to go to the 1037c50ffcb7fcb7c1109fee2406e8f74d096f755f47Chris Lattner // fallthrough instead. 1038071c62fad0b25ad4131e7f984173a796c1e63f61Chris Lattner if (MachineJumpTableInfo *MJTI = MF.getJumpTableInfo()) 1039071c62fad0b25ad4131e7f984173a796c1e63f61Chris Lattner MJTI->ReplaceMBBInJumpTables(MBB, FallThrough); 10407821a8afd3009c3c2760592e61de9e2c31c73e18Chris Lattner MadeChange = true; 104121ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner } 1042030a0a0cdb38924e55773a8e0b5fe7347aa664aaEvan Cheng return MadeChange; 104321ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner } 104421ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner 10457821a8afd3009c3c2760592e61de9e2c31c73e18Chris Lattner // Check to see if we can simplify the terminator of the block before this 10467821a8afd3009c3c2760592e61de9e2c31c73e18Chris Lattner // one. 10477d09784d3fc652131a2afbf06a0f2ed893837fb9Chris Lattner MachineBasicBlock &PrevBB = *prior(MachineFunction::iterator(MBB)); 1048ffddf6ba1c58b42dcfd071972754649c3ca5dff7Chris Lattner 10497821a8afd3009c3c2760592e61de9e2c31c73e18Chris Lattner MachineBasicBlock *PriorTBB = 0, *PriorFBB = 0; 105044eb65cf58e3ab9b5621ce72256d1621a18aeed7Owen Anderson SmallVector<MachineOperand, 4> PriorCond; 10516b0e3f890779b7fc912bec8d40a9590e44742737Chris Lattner bool PriorUnAnalyzable = 1052dc54d317e7a381ef8e4aca80d54ad1466bb85ddaEvan Cheng TII->AnalyzeBranch(PrevBB, PriorTBB, PriorFBB, PriorCond, true); 1053386e29065db5b05b57440f6b2a6dfa1e7f29a00dChris Lattner if (!PriorUnAnalyzable) { 1054386e29065db5b05b57440f6b2a6dfa1e7f29a00dChris Lattner // If the CFG for the prior block has extra edges, remove them. 10552bdb7d0cc88881857073b36f4a09ebe2f2008c24Evan Cheng MadeChange |= PrevBB.CorrectExtraCFGEdges(PriorTBB, PriorFBB, 10562bdb7d0cc88881857073b36f4a09ebe2f2008c24Evan Cheng !PriorCond.empty()); 10574e3f125e184f96ae72f2c44d16cafe0d44158283Dan Gohman 10587821a8afd3009c3c2760592e61de9e2c31c73e18Chris Lattner // If the previous branch is conditional and both conditions go to the same 10592d47bd937c13556ace07b2b2daf4dfe75f4e1e90Chris Lattner // destination, remove the branch, replacing it with an unconditional one or 10602d47bd937c13556ace07b2b2daf4dfe75f4e1e90Chris Lattner // a fall-through. 10617821a8afd3009c3c2760592e61de9e2c31c73e18Chris Lattner if (PriorTBB && PriorTBB == PriorFBB) { 1062386e29065db5b05b57440f6b2a6dfa1e7f29a00dChris Lattner TII->RemoveBranch(PrevBB); 10634e3f125e184f96ae72f2c44d16cafe0d44158283Dan Gohman PriorCond.clear(); 10647d09784d3fc652131a2afbf06a0f2ed893837fb9Chris Lattner if (PriorTBB != MBB) 1065386e29065db5b05b57440f6b2a6dfa1e7f29a00dChris Lattner TII->InsertBranch(PrevBB, PriorTBB, 0, PriorCond); 10667821a8afd3009c3c2760592e61de9e2c31c73e18Chris Lattner MadeChange = true; 106712143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner ++NumBranchOpts; 10682210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman goto ReoptimizeBlock; 10697821a8afd3009c3c2760592e61de9e2c31c73e18Chris Lattner } 10704e3f125e184f96ae72f2c44d16cafe0d44158283Dan Gohman 10712210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman // If the previous block unconditionally falls through to this block and 10722210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman // this block has no other predecessors, move the contents of this block 10732210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman // into the prior block. This doesn't usually happen when SimplifyCFG 1074465c8252f282fda26db6962a81948afce7f01cc2Bob Wilson // has been used, but it can happen if tail merging splits a fall-through 1075465c8252f282fda26db6962a81948afce7f01cc2Bob Wilson // predecessor of a block. 10762210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman // This has to check PrevBB->succ_size() because EH edges are ignored by 10772210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman // AnalyzeBranch. 10782210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman if (PriorCond.empty() && !PriorTBB && MBB->pred_size() == 1 && 10792210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman PrevBB.succ_size() == 1 && 10802210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman !MBB->hasAddressTaken()) { 1081465e2b950d61c870fb3120c80191973e8282a3efDavid Greene DEBUG(dbgs() << "\nMerging into block: " << PrevBB 10822210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman << "From MBB: " << *MBB); 10832210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman PrevBB.splice(PrevBB.end(), MBB, MBB->begin(), MBB->end()); 10842210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman PrevBB.removeSuccessor(PrevBB.succ_begin());; 10852210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman assert(PrevBB.succ_empty()); 10862210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman PrevBB.transferSuccessors(MBB); 10872210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman MadeChange = true; 10882210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman return MadeChange; 10892210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman } 10903cbc3120873242d93e469b4635c0bbd09fdb6438Bob Wilson 10917821a8afd3009c3c2760592e61de9e2c31c73e18Chris Lattner // If the previous branch *only* branches to *this* block (conditional or 10927821a8afd3009c3c2760592e61de9e2c31c73e18Chris Lattner // not) remove the branch. 10937d09784d3fc652131a2afbf06a0f2ed893837fb9Chris Lattner if (PriorTBB == MBB && PriorFBB == 0) { 1094386e29065db5b05b57440f6b2a6dfa1e7f29a00dChris Lattner TII->RemoveBranch(PrevBB); 10957821a8afd3009c3c2760592e61de9e2c31c73e18Chris Lattner MadeChange = true; 109612143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner ++NumBranchOpts; 10972210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman goto ReoptimizeBlock; 10987821a8afd3009c3c2760592e61de9e2c31c73e18Chris Lattner } 10994e3f125e184f96ae72f2c44d16cafe0d44158283Dan Gohman 11002d47bd937c13556ace07b2b2daf4dfe75f4e1e90Chris Lattner // If the prior block branches somewhere else on the condition and here if 11012d47bd937c13556ace07b2b2daf4dfe75f4e1e90Chris Lattner // the condition is false, remove the uncond second branch. 11027d09784d3fc652131a2afbf06a0f2ed893837fb9Chris Lattner if (PriorFBB == MBB) { 11032d47bd937c13556ace07b2b2daf4dfe75f4e1e90Chris Lattner TII->RemoveBranch(PrevBB); 11042d47bd937c13556ace07b2b2daf4dfe75f4e1e90Chris Lattner TII->InsertBranch(PrevBB, PriorTBB, 0, PriorCond); 11052d47bd937c13556ace07b2b2daf4dfe75f4e1e90Chris Lattner MadeChange = true; 11062d47bd937c13556ace07b2b2daf4dfe75f4e1e90Chris Lattner ++NumBranchOpts; 11072210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman goto ReoptimizeBlock; 11082d47bd937c13556ace07b2b2daf4dfe75f4e1e90Chris Lattner } 11094e3f125e184f96ae72f2c44d16cafe0d44158283Dan Gohman 1110a2d799531a748a349b9a458dbbc580b134074c49Chris Lattner // If the prior block branches here on true and somewhere else on false, and 1111a2d799531a748a349b9a458dbbc580b134074c49Chris Lattner // if the branch condition is reversible, reverse the branch to create a 1112a2d799531a748a349b9a458dbbc580b134074c49Chris Lattner // fall-through. 11137d09784d3fc652131a2afbf06a0f2ed893837fb9Chris Lattner if (PriorTBB == MBB) { 111444eb65cf58e3ab9b5621ce72256d1621a18aeed7Owen Anderson SmallVector<MachineOperand, 4> NewPriorCond(PriorCond); 1115a2d799531a748a349b9a458dbbc580b134074c49Chris Lattner if (!TII->ReverseBranchCondition(NewPriorCond)) { 1116a2d799531a748a349b9a458dbbc580b134074c49Chris Lattner TII->RemoveBranch(PrevBB); 1117a2d799531a748a349b9a458dbbc580b134074c49Chris Lattner TII->InsertBranch(PrevBB, PriorFBB, 0, NewPriorCond); 1118a2d799531a748a349b9a458dbbc580b134074c49Chris Lattner MadeChange = true; 1119a2d799531a748a349b9a458dbbc580b134074c49Chris Lattner ++NumBranchOpts; 11202210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman goto ReoptimizeBlock; 1121a2d799531a748a349b9a458dbbc580b134074c49Chris Lattner } 1122a2d799531a748a349b9a458dbbc580b134074c49Chris Lattner } 11234e3f125e184f96ae72f2c44d16cafe0d44158283Dan Gohman 11246d31268a7dc9854fa5a5cb9227ba9a15c5898414Dan Gohman // If this block has no successors (e.g. it is a return block or ends with 11256d31268a7dc9854fa5a5cb9227ba9a15c5898414Dan Gohman // a call to a no-return function like abort or __cxa_throw) and if the pred 11266d31268a7dc9854fa5a5cb9227ba9a15c5898414Dan Gohman // falls through into this block, and if it would otherwise fall through 11276d31268a7dc9854fa5a5cb9227ba9a15c5898414Dan Gohman // into the block after this, move this block to the end of the function. 1128154e1047184384afd0a701a9f8816459cf0b3490Chris Lattner // 1129a7bef4a4e49f461984c04ef6be6eef3f1c023558Chris Lattner // We consider it more likely that execution will stay in the function (e.g. 1130a7bef4a4e49f461984c04ef6be6eef3f1c023558Chris Lattner // due to loops) than it is to exit it. This asserts in loops etc, moving 1131a7bef4a4e49f461984c04ef6be6eef3f1c023558Chris Lattner // the assert condition out of the loop body. 11326d31268a7dc9854fa5a5cb9227ba9a15c5898414Dan Gohman if (MBB->succ_empty() && !PriorCond.empty() && PriorFBB == 0 && 1133154e1047184384afd0a701a9f8816459cf0b3490Chris Lattner MachineFunction::iterator(PriorTBB) == FallThrough && 113415acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson !MBB->canFallThrough()) { 1135f10a56a86f8ae32d0493c7de770493d55519b073Chris Lattner bool DoTransform = true; 11364e3f125e184f96ae72f2c44d16cafe0d44158283Dan Gohman 1137a7bef4a4e49f461984c04ef6be6eef3f1c023558Chris Lattner // We have to be careful that the succs of PredBB aren't both no-successor 1138a7bef4a4e49f461984c04ef6be6eef3f1c023558Chris Lattner // blocks. If neither have successors and if PredBB is the second from 1139a7bef4a4e49f461984c04ef6be6eef3f1c023558Chris Lattner // last block in the function, we'd just keep swapping the two blocks for 1140a7bef4a4e49f461984c04ef6be6eef3f1c023558Chris Lattner // last. Only do the swap if one is clearly better to fall through than 1141a7bef4a4e49f461984c04ef6be6eef3f1c023558Chris Lattner // the other. 1142d194498d2669e28cd8e85b0ceb7c69a7ec66da13Dan Gohman if (FallThrough == --MF.end() && 114369244300b8a0112efb44b6273ecea4ca6264b8cfChris Lattner !IsBetterFallthrough(PriorTBB, MBB)) 1144f10a56a86f8ae32d0493c7de770493d55519b073Chris Lattner DoTransform = false; 1145f10a56a86f8ae32d0493c7de770493d55519b073Chris Lattner 1146f10a56a86f8ae32d0493c7de770493d55519b073Chris Lattner // We don't want to do this transformation if we have control flow like: 1147f10a56a86f8ae32d0493c7de770493d55519b073Chris Lattner // br cond BB2 1148f10a56a86f8ae32d0493c7de770493d55519b073Chris Lattner // BB1: 1149f10a56a86f8ae32d0493c7de770493d55519b073Chris Lattner // .. 1150f10a56a86f8ae32d0493c7de770493d55519b073Chris Lattner // jmp BBX 1151f10a56a86f8ae32d0493c7de770493d55519b073Chris Lattner // BB2: 1152f10a56a86f8ae32d0493c7de770493d55519b073Chris Lattner // .. 1153f10a56a86f8ae32d0493c7de770493d55519b073Chris Lattner // ret 1154f10a56a86f8ae32d0493c7de770493d55519b073Chris Lattner // 1155f10a56a86f8ae32d0493c7de770493d55519b073Chris Lattner // In this case, we could actually be moving the return block *into* a 1156f10a56a86f8ae32d0493c7de770493d55519b073Chris Lattner // loop! 11574b105912657c0472dc4f6f7244ce20bf7cf9a7dcChris Lattner if (DoTransform && !MBB->succ_empty() && 115815acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson (!PriorTBB->canFallThrough() || PriorTBB->empty())) 1159f10a56a86f8ae32d0493c7de770493d55519b073Chris Lattner DoTransform = false; 11604e3f125e184f96ae72f2c44d16cafe0d44158283Dan Gohman 11614e3f125e184f96ae72f2c44d16cafe0d44158283Dan Gohman 1162f10a56a86f8ae32d0493c7de770493d55519b073Chris Lattner if (DoTransform) { 1163a7bef4a4e49f461984c04ef6be6eef3f1c023558Chris Lattner // Reverse the branch so we will fall through on the previous true cond. 116444eb65cf58e3ab9b5621ce72256d1621a18aeed7Owen Anderson SmallVector<MachineOperand, 4> NewPriorCond(PriorCond); 1165a7bef4a4e49f461984c04ef6be6eef3f1c023558Chris Lattner if (!TII->ReverseBranchCondition(NewPriorCond)) { 1166465e2b950d61c870fb3120c80191973e8282a3efDavid Greene DEBUG(dbgs() << "\nMoving MBB: " << *MBB 11673403bcd8f943cb053a7d9bbf8eb8135407699afaBill Wendling << "To make fallthrough to: " << *PriorTBB << "\n"); 11684e3f125e184f96ae72f2c44d16cafe0d44158283Dan Gohman 1169a7bef4a4e49f461984c04ef6be6eef3f1c023558Chris Lattner TII->RemoveBranch(PrevBB); 1170a7bef4a4e49f461984c04ef6be6eef3f1c023558Chris Lattner TII->InsertBranch(PrevBB, MBB, 0, NewPriorCond); 1171a7bef4a4e49f461984c04ef6be6eef3f1c023558Chris Lattner 1172a7bef4a4e49f461984c04ef6be6eef3f1c023558Chris Lattner // Move this block to the end of the function. 1173d194498d2669e28cd8e85b0ceb7c69a7ec66da13Dan Gohman MBB->moveAfter(--MF.end()); 1174a7bef4a4e49f461984c04ef6be6eef3f1c023558Chris Lattner MadeChange = true; 1175a7bef4a4e49f461984c04ef6be6eef3f1c023558Chris Lattner ++NumBranchOpts; 1176030a0a0cdb38924e55773a8e0b5fe7347aa664aaEvan Cheng return MadeChange; 1177a7bef4a4e49f461984c04ef6be6eef3f1c023558Chris Lattner } 1178a7bef4a4e49f461984c04ef6be6eef3f1c023558Chris Lattner } 1179a7bef4a4e49f461984c04ef6be6eef3f1c023558Chris Lattner } 11807821a8afd3009c3c2760592e61de9e2c31c73e18Chris Lattner } 11814e3f125e184f96ae72f2c44d16cafe0d44158283Dan Gohman 1182386e29065db5b05b57440f6b2a6dfa1e7f29a00dChris Lattner // Analyze the branch in the current block. 1183386e29065db5b05b57440f6b2a6dfa1e7f29a00dChris Lattner MachineBasicBlock *CurTBB = 0, *CurFBB = 0; 118444eb65cf58e3ab9b5621ce72256d1621a18aeed7Owen Anderson SmallVector<MachineOperand, 4> CurCond; 1185dc54d317e7a381ef8e4aca80d54ad1466bb85ddaEvan Cheng bool CurUnAnalyzable= TII->AnalyzeBranch(*MBB, CurTBB, CurFBB, CurCond, true); 11866b0e3f890779b7fc912bec8d40a9590e44742737Chris Lattner if (!CurUnAnalyzable) { 1187386e29065db5b05b57440f6b2a6dfa1e7f29a00dChris Lattner // If the CFG for the prior block has extra edges, remove them. 11882bdb7d0cc88881857073b36f4a09ebe2f2008c24Evan Cheng MadeChange |= MBB->CorrectExtraCFGEdges(CurTBB, CurFBB, !CurCond.empty()); 1189386e29065db5b05b57440f6b2a6dfa1e7f29a00dChris Lattner 11904e3f125e184f96ae72f2c44d16cafe0d44158283Dan Gohman // If this is a two-way branch, and the FBB branches to this block, reverse 11915d056952ba2f97729c5db69a3f14250595fa1ee8Chris Lattner // the condition so the single-basic-block loop is faster. Instead of: 11925d056952ba2f97729c5db69a3f14250595fa1ee8Chris Lattner // Loop: xxx; jcc Out; jmp Loop 11935d056952ba2f97729c5db69a3f14250595fa1ee8Chris Lattner // we want: 11945d056952ba2f97729c5db69a3f14250595fa1ee8Chris Lattner // Loop: xxx; jncc Loop; jmp Out 11955d056952ba2f97729c5db69a3f14250595fa1ee8Chris Lattner if (CurTBB && CurFBB && CurFBB == MBB && CurTBB != MBB) { 119644eb65cf58e3ab9b5621ce72256d1621a18aeed7Owen Anderson SmallVector<MachineOperand, 4> NewCond(CurCond); 11975d056952ba2f97729c5db69a3f14250595fa1ee8Chris Lattner if (!TII->ReverseBranchCondition(NewCond)) { 11985d056952ba2f97729c5db69a3f14250595fa1ee8Chris Lattner TII->RemoveBranch(*MBB); 11995d056952ba2f97729c5db69a3f14250595fa1ee8Chris Lattner TII->InsertBranch(*MBB, CurFBB, CurTBB, NewCond); 12005d056952ba2f97729c5db69a3f14250595fa1ee8Chris Lattner MadeChange = true; 12015d056952ba2f97729c5db69a3f14250595fa1ee8Chris Lattner ++NumBranchOpts; 12022210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman goto ReoptimizeBlock; 12035d056952ba2f97729c5db69a3f14250595fa1ee8Chris Lattner } 12045d056952ba2f97729c5db69a3f14250595fa1ee8Chris Lattner } 12054e3f125e184f96ae72f2c44d16cafe0d44158283Dan Gohman 1206386e29065db5b05b57440f6b2a6dfa1e7f29a00dChris Lattner // If this branch is the only thing in its block, see if we can forward 1207386e29065db5b05b57440f6b2a6dfa1e7f29a00dChris Lattner // other blocks across it. 12084e3f125e184f96ae72f2c44d16cafe0d44158283Dan Gohman if (CurTBB && CurCond.empty() && CurFBB == 0 && 1209888acc35a3e271d092f9b1efc7c32b94ff17fbf7Bob Wilson MBB->begin()->getDesc().isBranch() && CurTBB != MBB && 1210888acc35a3e271d092f9b1efc7c32b94ff17fbf7Bob Wilson !MBB->hasAddressTaken()) { 1211386e29065db5b05b57440f6b2a6dfa1e7f29a00dChris Lattner // This block may contain just an unconditional branch. Because there can 1212386e29065db5b05b57440f6b2a6dfa1e7f29a00dChris Lattner // be 'non-branch terminators' in the block, try removing the branch and 1213386e29065db5b05b57440f6b2a6dfa1e7f29a00dChris Lattner // then seeing if the block is empty. 1214386e29065db5b05b57440f6b2a6dfa1e7f29a00dChris Lattner TII->RemoveBranch(*MBB); 1215c5cf227f3dac755508928b9dee8ac6a45dcb4e4fDale Johannesen // If the only things remaining in the block are debug info, remove these 1216c5cf227f3dac755508928b9dee8ac6a45dcb4e4fDale Johannesen // as well, so this will behave the same as an empty block in non-debug 1217c5cf227f3dac755508928b9dee8ac6a45dcb4e4fDale Johannesen // mode. 1218c5cf227f3dac755508928b9dee8ac6a45dcb4e4fDale Johannesen if (!MBB->empty()) { 1219c5cf227f3dac755508928b9dee8ac6a45dcb4e4fDale Johannesen bool NonDebugInfoFound = false; 1220c5cf227f3dac755508928b9dee8ac6a45dcb4e4fDale Johannesen for (MachineBasicBlock::iterator I = MBB->begin(), E = MBB->end(); 1221c5cf227f3dac755508928b9dee8ac6a45dcb4e4fDale Johannesen I != E; ++I) { 1222c5cf227f3dac755508928b9dee8ac6a45dcb4e4fDale Johannesen if (!I->isDebugValue()) { 1223c5cf227f3dac755508928b9dee8ac6a45dcb4e4fDale Johannesen NonDebugInfoFound = true; 1224c5cf227f3dac755508928b9dee8ac6a45dcb4e4fDale Johannesen break; 1225c5cf227f3dac755508928b9dee8ac6a45dcb4e4fDale Johannesen } 1226c5cf227f3dac755508928b9dee8ac6a45dcb4e4fDale Johannesen } 1227c5cf227f3dac755508928b9dee8ac6a45dcb4e4fDale Johannesen if (!NonDebugInfoFound) 1228c5cf227f3dac755508928b9dee8ac6a45dcb4e4fDale Johannesen // Make the block empty, losing the debug info (we could probably 1229c5cf227f3dac755508928b9dee8ac6a45dcb4e4fDale Johannesen // improve this in some cases.) 1230c5cf227f3dac755508928b9dee8ac6a45dcb4e4fDale Johannesen MBB->erase(MBB->begin(), MBB->end()); 1231c5cf227f3dac755508928b9dee8ac6a45dcb4e4fDale Johannesen } 1232386e29065db5b05b57440f6b2a6dfa1e7f29a00dChris Lattner // If this block is just an unconditional branch to CurTBB, we can 1233386e29065db5b05b57440f6b2a6dfa1e7f29a00dChris Lattner // usually completely eliminate the block. The only case we cannot 1234386e29065db5b05b57440f6b2a6dfa1e7f29a00dChris Lattner // completely eliminate the block is when the block before this one 1235386e29065db5b05b57440f6b2a6dfa1e7f29a00dChris Lattner // falls through into MBB and we can't understand the prior block's branch 1236386e29065db5b05b57440f6b2a6dfa1e7f29a00dChris Lattner // condition. 1237cf420cca572b061fdd63587cb90904c641b6e216Chris Lattner if (MBB->empty()) { 1238864e2efce2cb5d02e376933933d96074723fe77cDan Gohman bool PredHasNoFallThrough = !PrevBB.canFallThrough(); 1239cf420cca572b061fdd63587cb90904c641b6e216Chris Lattner if (PredHasNoFallThrough || !PriorUnAnalyzable || 1240cf420cca572b061fdd63587cb90904c641b6e216Chris Lattner !PrevBB.isSuccessor(MBB)) { 1241cf420cca572b061fdd63587cb90904c641b6e216Chris Lattner // If the prior block falls through into us, turn it into an 1242cf420cca572b061fdd63587cb90904c641b6e216Chris Lattner // explicit branch to us to make updates simpler. 12434e3f125e184f96ae72f2c44d16cafe0d44158283Dan Gohman if (!PredHasNoFallThrough && PrevBB.isSuccessor(MBB) && 1244cf420cca572b061fdd63587cb90904c641b6e216Chris Lattner PriorTBB != MBB && PriorFBB != MBB) { 1245cf420cca572b061fdd63587cb90904c641b6e216Chris Lattner if (PriorTBB == 0) { 12466acfe12dd6d52c801f78c240528b7cb42fa91159Chris Lattner assert(PriorCond.empty() && PriorFBB == 0 && 12476acfe12dd6d52c801f78c240528b7cb42fa91159Chris Lattner "Bad branch analysis"); 1248cf420cca572b061fdd63587cb90904c641b6e216Chris Lattner PriorTBB = MBB; 1249cf420cca572b061fdd63587cb90904c641b6e216Chris Lattner } else { 1250cf420cca572b061fdd63587cb90904c641b6e216Chris Lattner assert(PriorFBB == 0 && "Machine CFG out of date!"); 1251cf420cca572b061fdd63587cb90904c641b6e216Chris Lattner PriorFBB = MBB; 1252cf420cca572b061fdd63587cb90904c641b6e216Chris Lattner } 1253cf420cca572b061fdd63587cb90904c641b6e216Chris Lattner TII->RemoveBranch(PrevBB); 1254cf420cca572b061fdd63587cb90904c641b6e216Chris Lattner TII->InsertBranch(PrevBB, PriorTBB, PriorFBB, PriorCond); 1255386e29065db5b05b57440f6b2a6dfa1e7f29a00dChris Lattner } 125621ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner 1257cf420cca572b061fdd63587cb90904c641b6e216Chris Lattner // Iterate through all the predecessors, revectoring each in-turn. 12588a46d342d8cbca7c9c7be6c66007d41329babad0David Greene size_t PI = 0; 1259cf420cca572b061fdd63587cb90904c641b6e216Chris Lattner bool DidChange = false; 1260cf420cca572b061fdd63587cb90904c641b6e216Chris Lattner bool HasBranchToSelf = false; 12618a46d342d8cbca7c9c7be6c66007d41329babad0David Greene while(PI != MBB->pred_size()) { 12628a46d342d8cbca7c9c7be6c66007d41329babad0David Greene MachineBasicBlock *PMBB = *(MBB->pred_begin() + PI); 12638a46d342d8cbca7c9c7be6c66007d41329babad0David Greene if (PMBB == MBB) { 1264cf420cca572b061fdd63587cb90904c641b6e216Chris Lattner // If this block has an uncond branch to itself, leave it. 1265cf420cca572b061fdd63587cb90904c641b6e216Chris Lattner ++PI; 1266cf420cca572b061fdd63587cb90904c641b6e216Chris Lattner HasBranchToSelf = true; 1267cf420cca572b061fdd63587cb90904c641b6e216Chris Lattner } else { 1268cf420cca572b061fdd63587cb90904c641b6e216Chris Lattner DidChange = true; 12698a46d342d8cbca7c9c7be6c66007d41329babad0David Greene PMBB->ReplaceUsesOfBlockWith(MBB, CurTBB); 1270bf06f6a6f1be0802ad7b761138ecba568814008aDale Johannesen // If this change resulted in PMBB ending in a conditional 1271bf06f6a6f1be0802ad7b761138ecba568814008aDale Johannesen // branch where both conditions go to the same destination, 1272bf06f6a6f1be0802ad7b761138ecba568814008aDale Johannesen // change this to an unconditional branch (and fix the CFG). 1273bf06f6a6f1be0802ad7b761138ecba568814008aDale Johannesen MachineBasicBlock *NewCurTBB = 0, *NewCurFBB = 0; 1274bf06f6a6f1be0802ad7b761138ecba568814008aDale Johannesen SmallVector<MachineOperand, 4> NewCurCond; 1275bf06f6a6f1be0802ad7b761138ecba568814008aDale Johannesen bool NewCurUnAnalyzable = TII->AnalyzeBranch(*PMBB, NewCurTBB, 1276bf06f6a6f1be0802ad7b761138ecba568814008aDale Johannesen NewCurFBB, NewCurCond, true); 1277bf06f6a6f1be0802ad7b761138ecba568814008aDale Johannesen if (!NewCurUnAnalyzable && NewCurTBB && NewCurTBB == NewCurFBB) { 1278bf06f6a6f1be0802ad7b761138ecba568814008aDale Johannesen TII->RemoveBranch(*PMBB); 12794e3f125e184f96ae72f2c44d16cafe0d44158283Dan Gohman NewCurCond.clear(); 1280bf06f6a6f1be0802ad7b761138ecba568814008aDale Johannesen TII->InsertBranch(*PMBB, NewCurTBB, 0, NewCurCond); 1281bf06f6a6f1be0802ad7b761138ecba568814008aDale Johannesen MadeChange = true; 1282bf06f6a6f1be0802ad7b761138ecba568814008aDale Johannesen ++NumBranchOpts; 12832210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman PMBB->CorrectExtraCFGEdges(NewCurTBB, 0, false); 1284bf06f6a6f1be0802ad7b761138ecba568814008aDale Johannesen } 1285cf420cca572b061fdd63587cb90904c641b6e216Chris Lattner } 12864bc135e93beebdcb3b9c44745c5ccbc91199ac0bChris Lattner } 128721ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner 1288cf420cca572b061fdd63587cb90904c641b6e216Chris Lattner // Change any jumptables to go to the new MBB. 1289071c62fad0b25ad4131e7f984173a796c1e63f61Chris Lattner if (MachineJumpTableInfo *MJTI = MF.getJumpTableInfo()) 1290071c62fad0b25ad4131e7f984173a796c1e63f61Chris Lattner MJTI->ReplaceMBBInJumpTables(MBB, CurTBB); 1291cf420cca572b061fdd63587cb90904c641b6e216Chris Lattner if (DidChange) { 1292cf420cca572b061fdd63587cb90904c641b6e216Chris Lattner ++NumBranchOpts; 1293cf420cca572b061fdd63587cb90904c641b6e216Chris Lattner MadeChange = true; 1294030a0a0cdb38924e55773a8e0b5fe7347aa664aaEvan Cheng if (!HasBranchToSelf) return MadeChange; 1295cf420cca572b061fdd63587cb90904c641b6e216Chris Lattner } 12964bc135e93beebdcb3b9c44745c5ccbc91199ac0bChris Lattner } 129721ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner } 12984e3f125e184f96ae72f2c44d16cafe0d44158283Dan Gohman 1299386e29065db5b05b57440f6b2a6dfa1e7f29a00dChris Lattner // Add the branch back if the block is more than just an uncond branch. 1300386e29065db5b05b57440f6b2a6dfa1e7f29a00dChris Lattner TII->InsertBranch(*MBB, CurTBB, 0, CurCond); 130121ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner } 13026b0e3f890779b7fc912bec8d40a9590e44742737Chris Lattner } 13036b0e3f890779b7fc912bec8d40a9590e44742737Chris Lattner 130443cf6c3939176e8d87719516f0b2e4c6c346f340Bill Wendling // If the prior block doesn't fall through into this block, and if this 130543cf6c3939176e8d87719516f0b2e4c6c346f340Bill Wendling // block doesn't fall through into some other block, see if we can find a 130643cf6c3939176e8d87719516f0b2e4c6c346f340Bill Wendling // place to move this block where a fall-through will happen. 130743cf6c3939176e8d87719516f0b2e4c6c346f340Bill Wendling if (!PrevBB.canFallThrough()) { 130843cf6c3939176e8d87719516f0b2e4c6c346f340Bill Wendling 130956ea69c3a251434db3fef489881368e29c95712dBob Wilson // Now we know that there was no fall-through into this block, check to 131056ea69c3a251434db3fef489881368e29c95712dBob Wilson // see if it has a fall-through into its successor. 131115acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson bool CurFallsThru = MBB->canFallThrough(); 131256ea69c3a251434db3fef489881368e29c95712dBob Wilson 131302b3f5ec4ac120d14a63f7fd4f4388b7d0ab6c22Jim Laskey if (!MBB->isLandingPad()) { 131402b3f5ec4ac120d14a63f7fd4f4388b7d0ab6c22Jim Laskey // Check all the predecessors of this block. If one of them has no fall 131502b3f5ec4ac120d14a63f7fd4f4388b7d0ab6c22Jim Laskey // throughs, move this block right after it. 131602b3f5ec4ac120d14a63f7fd4f4388b7d0ab6c22Jim Laskey for (MachineBasicBlock::pred_iterator PI = MBB->pred_begin(), 131702b3f5ec4ac120d14a63f7fd4f4388b7d0ab6c22Jim Laskey E = MBB->pred_end(); PI != E; ++PI) { 131802b3f5ec4ac120d14a63f7fd4f4388b7d0ab6c22Jim Laskey // Analyze the branch at the end of the pred. 131902b3f5ec4ac120d14a63f7fd4f4388b7d0ab6c22Jim Laskey MachineBasicBlock *PredBB = *PI; 132043cf6c3939176e8d87719516f0b2e4c6c346f340Bill Wendling MachineFunction::iterator PredFallthrough = PredBB; ++PredFallthrough; 1321408e9d166a66c8891637975921de2980c1940c3fBill Wendling MachineBasicBlock *PredTBB = 0, *PredFBB = 0; 13222210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman SmallVector<MachineOperand, 4> PredCond; 132343cf6c3939176e8d87719516f0b2e4c6c346f340Bill Wendling if (PredBB != MBB && !PredBB->canFallThrough() && 132443cf6c3939176e8d87719516f0b2e4c6c346f340Bill Wendling !TII->AnalyzeBranch(*PredBB, PredTBB, PredFBB, PredCond, true) 132576b38fcabeba725e166a2ff72c56fe31d784b229Dale Johannesen && (!CurFallsThru || !CurTBB || !CurFBB) 132602b3f5ec4ac120d14a63f7fd4f4388b7d0ab6c22Jim Laskey && (!CurFallsThru || MBB->getNumber() >= PredBB->getNumber())) { 132743cf6c3939176e8d87719516f0b2e4c6c346f340Bill Wendling // If the current block doesn't fall through, just move it. 132843cf6c3939176e8d87719516f0b2e4c6c346f340Bill Wendling // If the current block can fall through and does not end with a 132943cf6c3939176e8d87719516f0b2e4c6c346f340Bill Wendling // conditional branch, we need to append an unconditional jump to 133043cf6c3939176e8d87719516f0b2e4c6c346f340Bill Wendling // the (current) next block. To avoid a possible compile-time 133143cf6c3939176e8d87719516f0b2e4c6c346f340Bill Wendling // infinite loop, move blocks only backward in this case. 133243cf6c3939176e8d87719516f0b2e4c6c346f340Bill Wendling // Also, if there are already 2 branches here, we cannot add a third; 133343cf6c3939176e8d87719516f0b2e4c6c346f340Bill Wendling // this means we have the case 133443cf6c3939176e8d87719516f0b2e4c6c346f340Bill Wendling // Bcc next 133543cf6c3939176e8d87719516f0b2e4c6c346f340Bill Wendling // B elsewhere 133643cf6c3939176e8d87719516f0b2e4c6c346f340Bill Wendling // next: 133702b3f5ec4ac120d14a63f7fd4f4388b7d0ab6c22Jim Laskey if (CurFallsThru) { 133843cf6c3939176e8d87719516f0b2e4c6c346f340Bill Wendling MachineBasicBlock *NextBB = llvm::next(MachineFunction::iterator(MBB)); 133902b3f5ec4ac120d14a63f7fd4f4388b7d0ab6c22Jim Laskey CurCond.clear(); 134002b3f5ec4ac120d14a63f7fd4f4388b7d0ab6c22Jim Laskey TII->InsertBranch(*MBB, NextBB, 0, CurCond); 134102b3f5ec4ac120d14a63f7fd4f4388b7d0ab6c22Jim Laskey } 134202b3f5ec4ac120d14a63f7fd4f4388b7d0ab6c22Jim Laskey MBB->moveAfter(PredBB); 134302b3f5ec4ac120d14a63f7fd4f4388b7d0ab6c22Jim Laskey MadeChange = true; 13442210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman goto ReoptimizeBlock; 13457d09784d3fc652131a2afbf06a0f2ed893837fb9Chris Lattner } 13466b0e3f890779b7fc912bec8d40a9590e44742737Chris Lattner } 13476b896cec8b703e08e5f3d809e086a39b6ebe6589Dale Johannesen } 13484e3f125e184f96ae72f2c44d16cafe0d44158283Dan Gohman 13496b896cec8b703e08e5f3d809e086a39b6ebe6589Dale Johannesen if (!CurFallsThru) { 13506b0e3f890779b7fc912bec8d40a9590e44742737Chris Lattner // Check all successors to see if we can move this block before it. 13516b0e3f890779b7fc912bec8d40a9590e44742737Chris Lattner for (MachineBasicBlock::succ_iterator SI = MBB->succ_begin(), 13526b0e3f890779b7fc912bec8d40a9590e44742737Chris Lattner E = MBB->succ_end(); SI != E; ++SI) { 13536b0e3f890779b7fc912bec8d40a9590e44742737Chris Lattner // Analyze the branch at the end of the block before the succ. 13546b0e3f890779b7fc912bec8d40a9590e44742737Chris Lattner MachineBasicBlock *SuccBB = *SI; 13556b0e3f890779b7fc912bec8d40a9590e44742737Chris Lattner MachineFunction::iterator SuccPrev = SuccBB; --SuccPrev; 13564e3f125e184f96ae72f2c44d16cafe0d44158283Dan Gohman 135777edc4b1b004726d96c932356750b9f3c96d74ddChris Lattner // If this block doesn't already fall-through to that successor, and if 135877edc4b1b004726d96c932356750b9f3c96d74ddChris Lattner // the succ doesn't already have a block that can fall through into it, 135977edc4b1b004726d96c932356750b9f3c96d74ddChris Lattner // and if the successor isn't an EH destination, we can arrange for the 136077edc4b1b004726d96c932356750b9f3c96d74ddChris Lattner // fallthrough to happen. 13612210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman if (SuccBB != MBB && &*SuccPrev != MBB && 136215acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson !SuccPrev->canFallThrough() && !CurUnAnalyzable && 136377edc4b1b004726d96c932356750b9f3c96d74ddChris Lattner !SuccBB->isLandingPad()) { 13646b0e3f890779b7fc912bec8d40a9590e44742737Chris Lattner MBB->moveBefore(SuccBB); 13657d09784d3fc652131a2afbf06a0f2ed893837fb9Chris Lattner MadeChange = true; 13662210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman goto ReoptimizeBlock; 13677d09784d3fc652131a2afbf06a0f2ed893837fb9Chris Lattner } 13687d09784d3fc652131a2afbf06a0f2ed893837fb9Chris Lattner } 13694e3f125e184f96ae72f2c44d16cafe0d44158283Dan Gohman 13706b0e3f890779b7fc912bec8d40a9590e44742737Chris Lattner // Okay, there is no really great place to put this block. If, however, 13716b0e3f890779b7fc912bec8d40a9590e44742737Chris Lattner // the block before this one would be a fall-through if this block were 13726b0e3f890779b7fc912bec8d40a9590e44742737Chris Lattner // removed, move this block to the end of the function. 1373fe586b3e3800b397256ca9ee6a2811fc6ce7dce9Bill Wendling MachineBasicBlock *PrevTBB = 0, *PrevFBB = 0; 13742210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman SmallVector<MachineOperand, 4> PrevCond; 1375d194498d2669e28cd8e85b0ceb7c69a7ec66da13Dan Gohman if (FallThrough != MF.end() && 13762210c0bea83aa8a8585d793a1f63e8c01b65be38Dan Gohman !TII->AnalyzeBranch(PrevBB, PrevTBB, PrevFBB, PrevCond, true) && 13776b0e3f890779b7fc912bec8d40a9590e44742737Chris Lattner PrevBB.isSuccessor(FallThrough)) { 1378d194498d2669e28cd8e85b0ceb7c69a7ec66da13Dan Gohman MBB->moveAfter(--MF.end()); 13796b0e3f890779b7fc912bec8d40a9590e44742737Chris Lattner MadeChange = true; 1380030a0a0cdb38924e55773a8e0b5fe7347aa664aaEvan Cheng return MadeChange; 13816b0e3f890779b7fc912bec8d40a9590e44742737Chris Lattner } 13827d09784d3fc652131a2afbf06a0f2ed893837fb9Chris Lattner } 138321ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner } 1384030a0a0cdb38924e55773a8e0b5fe7347aa664aaEvan Cheng 1385030a0a0cdb38924e55773a8e0b5fe7347aa664aaEvan Cheng return MadeChange; 138621ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner} 1387