BranchFolding.cpp revision 14ba0cc42959a3fcc9b6781aea614b01877fb55f
121ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner//===-- BranchFolding.cpp - Fold machine code branch instructions ---------===// 2edf128a7fa90f2b0b7ee24741a04a7ae1ecd6f7eMisha Brukman// 321ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner// The LLVM Compiler Infrastructure 421ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner// 521ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner// This file was developed by the LLVM research group and is distributed under 621ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner// the University of Illinois Open Source 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" 2021ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner#include "llvm/CodeGen/Passes.h" 2144c3b9fdd416c79f4b67cde1aecfced5921efd81Jim Laskey#include "llvm/CodeGen/MachineModuleInfo.h" 2221ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner#include "llvm/CodeGen/MachineFunctionPass.h" 23c50ffcb7fcb7c1109fee2406e8f74d096f755f47Chris Lattner#include "llvm/CodeGen/MachineJumpTableInfo.h" 2469cb9b78f11d505f4351a269fc90e7b77fcda437Dale Johannesen#include "llvm/CodeGen/RegisterScavenging.h" 2521ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner#include "llvm/Target/TargetInstrInfo.h" 2621ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner#include "llvm/Target/TargetMachine.h" 2769cb9b78f11d505f4351a269fc90e7b77fcda437Dale Johannesen#include "llvm/Target/MRegisterInfo.h" 2812143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner#include "llvm/Support/CommandLine.h" 29f10a56a86f8ae32d0493c7de770493d55519b073Chris Lattner#include "llvm/Support/Debug.h" 3012143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner#include "llvm/ADT/Statistic.h" 31551ccae044b0ff658fe629dd67edd5ffe75d10e8Reid Spencer#include "llvm/ADT/STLExtras.h" 32d41b30def3181bce4bf87e8bde664d15663165d0Jeff Cohen#include <algorithm> 3321ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattnerusing namespace llvm; 3421ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner 35cd3245ac45c595da96bb768a55cddc356dff55feChris LattnerSTATISTIC(NumDeadBlocks, "Number of dead blocks removed"); 36cd3245ac45c595da96bb768a55cddc356dff55feChris LattnerSTATISTIC(NumBranchOpts, "Number of branches optimized"); 37cd3245ac45c595da96bb768a55cddc356dff55feChris LattnerSTATISTIC(NumTailMerge , "Number of block tails merged"); 38d8ccff0c3e5028019a02dd44bf7d906efc9effd8Chris Lattnerstatic cl::opt<bool> EnableTailMerge("enable-tail-merge", cl::Hidden); 3912143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner 4021ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattnernamespace { 4121ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner struct BranchFolder : public MachineFunctionPass { 421997473cf72957d0e70322e2fe6fe2ab141c58a6Devang Patel static char ID; 43794fd75c67a2cdc128d67342c6d88a504d186896Devang Patel BranchFolder() : MachineFunctionPass((intptr_t)&ID) {} 44794fd75c67a2cdc128d67342c6d88a504d186896Devang Patel 4521ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner virtual bool runOnMachineFunction(MachineFunction &MF); 467821a8afd3009c3c2760592e61de9e2c31c73e18Chris Lattner virtual const char *getPassName() const { return "Control Flow Optimizer"; } 477821a8afd3009c3c2760592e61de9e2c31c73e18Chris Lattner const TargetInstrInfo *TII; 4844c3b9fdd416c79f4b67cde1aecfced5921efd81Jim Laskey MachineModuleInfo *MMI; 497821a8afd3009c3c2760592e61de9e2c31c73e18Chris Lattner bool MadeChange; 5021ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner private: 5112143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner // Tail Merging. 5212143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner bool TailMergeBlocks(MachineFunction &MF); 537d33b4c59b56afb96feea71073c1d9e70c457e28Dale Johannesen bool TryMergeBlocks(MachineBasicBlock* SuccBB, 547d33b4c59b56afb96feea71073c1d9e70c457e28Dale Johannesen MachineBasicBlock* PredBB); 5512143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner void ReplaceTailWithBranchTo(MachineBasicBlock::iterator OldInst, 5612143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner MachineBasicBlock *NewDest); 571d08d83230338ca5969ff6ae6737a978336538bfChris Lattner MachineBasicBlock *SplitMBBAt(MachineBasicBlock &CurMBB, 581d08d83230338ca5969ff6ae6737a978336538bfChris Lattner MachineBasicBlock::iterator BBI1); 5969cb9b78f11d505f4351a269fc90e7b77fcda437Dale Johannesen 607d33b4c59b56afb96feea71073c1d9e70c457e28Dale Johannesen std::vector<std::pair<unsigned,MachineBasicBlock*> > MergePotentials; 6169cb9b78f11d505f4351a269fc90e7b77fcda437Dale Johannesen const MRegisterInfo *RegInfo; 6269cb9b78f11d505f4351a269fc90e7b77fcda437Dale Johannesen RegScavenger *RS; 6312143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner // Branch optzn. 6412143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner bool OptimizeBranches(MachineFunction &MF); 657d09784d3fc652131a2afbf06a0f2ed893837fb9Chris Lattner void OptimizeBlock(MachineBasicBlock *MBB); 66683747abb81a7b7711ad6cb5abf5a4227f7ab691Chris Lattner void RemoveDeadBlock(MachineBasicBlock *MBB); 676b0e3f890779b7fc912bec8d40a9590e44742737Chris Lattner 686b0e3f890779b7fc912bec8d40a9590e44742737Chris Lattner bool CanFallThrough(MachineBasicBlock *CurBB); 696b0e3f890779b7fc912bec8d40a9590e44742737Chris Lattner bool CanFallThrough(MachineBasicBlock *CurBB, bool BranchUnAnalyzable, 706b0e3f890779b7fc912bec8d40a9590e44742737Chris Lattner MachineBasicBlock *TBB, MachineBasicBlock *FBB, 716b0e3f890779b7fc912bec8d40a9590e44742737Chris Lattner const std::vector<MachineOperand> &Cond); 7221ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner }; 731997473cf72957d0e70322e2fe6fe2ab141c58a6Devang Patel char BranchFolder::ID = 0; 7421ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner} 7521ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner 7614ba0cc42959a3fcc9b6781aea614b01877fb55fDale Johannesenstatic bool CorrectExtraCFGEdges(MachineBasicBlock &MBB, 7714ba0cc42959a3fcc9b6781aea614b01877fb55fDale Johannesen MachineBasicBlock *DestA, 7814ba0cc42959a3fcc9b6781aea614b01877fb55fDale Johannesen MachineBasicBlock *DestB, 7914ba0cc42959a3fcc9b6781aea614b01877fb55fDale Johannesen bool isCond, 8014ba0cc42959a3fcc9b6781aea614b01877fb55fDale Johannesen MachineFunction::iterator FallThru); 8114ba0cc42959a3fcc9b6781aea614b01877fb55fDale Johannesen 8221ab22e47592d8a4046cfdac844d76b2cb76d711Chris LattnerFunctionPass *llvm::createBranchFoldingPass() { return new BranchFolder(); } 8321ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner 84c50ffcb7fcb7c1109fee2406e8f74d096f755f47Chris Lattner/// RemoveDeadBlock - Remove the specified dead machine basic block from the 85c50ffcb7fcb7c1109fee2406e8f74d096f755f47Chris Lattner/// function, updating the CFG. 86683747abb81a7b7711ad6cb5abf5a4227f7ab691Chris Lattnervoid BranchFolder::RemoveDeadBlock(MachineBasicBlock *MBB) { 87033c9715d9bf7ce59ad2e466bf0720811b34da08Jim Laskey assert(MBB->pred_empty() && "MBB must be dead!"); 8802b3f5ec4ac120d14a63f7fd4f4388b7d0ab6c22Jim Laskey DOUT << "\nRemoving MBB: " << *MBB; 89683747abb81a7b7711ad6cb5abf5a4227f7ab691Chris Lattner 90c50ffcb7fcb7c1109fee2406e8f74d096f755f47Chris Lattner MachineFunction *MF = MBB->getParent(); 91c50ffcb7fcb7c1109fee2406e8f74d096f755f47Chris Lattner // drop all successors. 92c50ffcb7fcb7c1109fee2406e8f74d096f755f47Chris Lattner while (!MBB->succ_empty()) 93c50ffcb7fcb7c1109fee2406e8f74d096f755f47Chris Lattner MBB->removeSuccessor(MBB->succ_end()-1); 94683747abb81a7b7711ad6cb5abf5a4227f7ab691Chris Lattner 951ee29257428960fede862fcfdbe80d5d007927e9Jim Laskey // If there is DWARF info to active, check to see if there are any LABEL 9644c3b9fdd416c79f4b67cde1aecfced5921efd81Jim Laskey // records in the basic block. If so, unregister them from MachineModuleInfo. 9744c3b9fdd416c79f4b67cde1aecfced5921efd81Jim Laskey if (MMI && !MBB->empty()) { 98683747abb81a7b7711ad6cb5abf5a4227f7ab691Chris Lattner for (MachineBasicBlock::iterator I = MBB->begin(), E = MBB->end(); 99683747abb81a7b7711ad6cb5abf5a4227f7ab691Chris Lattner I != E; ++I) { 1001ee29257428960fede862fcfdbe80d5d007927e9Jim Laskey if ((unsigned)I->getOpcode() == TargetInstrInfo::LABEL) { 101683747abb81a7b7711ad6cb5abf5a4227f7ab691Chris Lattner // The label ID # is always operand #0, an immediate. 10244c3b9fdd416c79f4b67cde1aecfced5921efd81Jim Laskey MMI->InvalidateLabel(I->getOperand(0).getImm()); 103683747abb81a7b7711ad6cb5abf5a4227f7ab691Chris Lattner } 104683747abb81a7b7711ad6cb5abf5a4227f7ab691Chris Lattner } 105683747abb81a7b7711ad6cb5abf5a4227f7ab691Chris Lattner } 106683747abb81a7b7711ad6cb5abf5a4227f7ab691Chris Lattner 107c50ffcb7fcb7c1109fee2406e8f74d096f755f47Chris Lattner // Remove the block. 108c50ffcb7fcb7c1109fee2406e8f74d096f755f47Chris Lattner MF->getBasicBlockList().erase(MBB); 109c50ffcb7fcb7c1109fee2406e8f74d096f755f47Chris Lattner} 110c50ffcb7fcb7c1109fee2406e8f74d096f755f47Chris Lattner 11121ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattnerbool BranchFolder::runOnMachineFunction(MachineFunction &MF) { 1127821a8afd3009c3c2760592e61de9e2c31c73e18Chris Lattner TII = MF.getTarget().getInstrInfo(); 1137821a8afd3009c3c2760592e61de9e2c31c73e18Chris Lattner if (!TII) return false; 1147821a8afd3009c3c2760592e61de9e2c31c73e18Chris Lattner 11514ba0cc42959a3fcc9b6781aea614b01877fb55fDale Johannesen // Fix CFG. The later algorithms expect it to be right. 11614ba0cc42959a3fcc9b6781aea614b01877fb55fDale Johannesen bool EverMadeChange = false; 11714ba0cc42959a3fcc9b6781aea614b01877fb55fDale Johannesen for (MachineFunction::iterator I = MF.begin(), E = MF.end(); I != E; I++) { 11814ba0cc42959a3fcc9b6781aea614b01877fb55fDale Johannesen MachineBasicBlock *MBB = I, *TBB = 0, *FBB = 0; 11914ba0cc42959a3fcc9b6781aea614b01877fb55fDale Johannesen std::vector<MachineOperand> Cond; 12014ba0cc42959a3fcc9b6781aea614b01877fb55fDale Johannesen if (!TII->AnalyzeBranch(*MBB, TBB, FBB, Cond)) 12114ba0cc42959a3fcc9b6781aea614b01877fb55fDale Johannesen EverMadeChange |= CorrectExtraCFGEdges(*MBB, TBB, FBB, 12214ba0cc42959a3fcc9b6781aea614b01877fb55fDale Johannesen !Cond.empty(), next(I)); 12314ba0cc42959a3fcc9b6781aea614b01877fb55fDale Johannesen } 12414ba0cc42959a3fcc9b6781aea614b01877fb55fDale Johannesen 12569cb9b78f11d505f4351a269fc90e7b77fcda437Dale Johannesen RegInfo = MF.getTarget().getRegisterInfo(); 12669cb9b78f11d505f4351a269fc90e7b77fcda437Dale Johannesen RS = RegInfo->requiresRegisterScavenging(MF) ? new RegScavenger() : NULL; 12769cb9b78f11d505f4351a269fc90e7b77fcda437Dale Johannesen 12844c3b9fdd416c79f4b67cde1aecfced5921efd81Jim Laskey MMI = getAnalysisToUpdate<MachineModuleInfo>(); 12976b38fcabeba725e166a2ff72c56fe31d784b229Dale Johannesen 13012143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner bool MadeChangeThisIteration = true; 13112143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner while (MadeChangeThisIteration) { 13212143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner MadeChangeThisIteration = false; 13312143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner MadeChangeThisIteration |= TailMergeBlocks(MF); 13412143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner MadeChangeThisIteration |= OptimizeBranches(MF); 13512143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner EverMadeChange |= MadeChangeThisIteration; 13612143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner } 13712143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner 1386acfe12dd6d52c801f78c240528b7cb42fa91159Chris Lattner // See if any jump tables have become mergable or dead as the code generator 1396acfe12dd6d52c801f78c240528b7cb42fa91159Chris Lattner // did its thing. 1406acfe12dd6d52c801f78c240528b7cb42fa91159Chris Lattner MachineJumpTableInfo *JTI = MF.getJumpTableInfo(); 1416acfe12dd6d52c801f78c240528b7cb42fa91159Chris Lattner const std::vector<MachineJumpTableEntry> &JTs = JTI->getJumpTables(); 1426acfe12dd6d52c801f78c240528b7cb42fa91159Chris Lattner if (!JTs.empty()) { 1436acfe12dd6d52c801f78c240528b7cb42fa91159Chris Lattner // Figure out how these jump tables should be merged. 1446acfe12dd6d52c801f78c240528b7cb42fa91159Chris Lattner std::vector<unsigned> JTMapping; 1456acfe12dd6d52c801f78c240528b7cb42fa91159Chris Lattner JTMapping.reserve(JTs.size()); 1466acfe12dd6d52c801f78c240528b7cb42fa91159Chris Lattner 1476acfe12dd6d52c801f78c240528b7cb42fa91159Chris Lattner // We always keep the 0th jump table. 1486acfe12dd6d52c801f78c240528b7cb42fa91159Chris Lattner JTMapping.push_back(0); 1496acfe12dd6d52c801f78c240528b7cb42fa91159Chris Lattner 1506acfe12dd6d52c801f78c240528b7cb42fa91159Chris Lattner // Scan the jump tables, seeing if there are any duplicates. Note that this 1516acfe12dd6d52c801f78c240528b7cb42fa91159Chris Lattner // is N^2, which should be fixed someday. 1526acfe12dd6d52c801f78c240528b7cb42fa91159Chris Lattner for (unsigned i = 1, e = JTs.size(); i != e; ++i) 1536acfe12dd6d52c801f78c240528b7cb42fa91159Chris Lattner JTMapping.push_back(JTI->getJumpTableIndex(JTs[i].MBBs)); 1546acfe12dd6d52c801f78c240528b7cb42fa91159Chris Lattner 1556acfe12dd6d52c801f78c240528b7cb42fa91159Chris Lattner // If a jump table was merge with another one, walk the function rewriting 1566acfe12dd6d52c801f78c240528b7cb42fa91159Chris Lattner // references to jump tables to reference the new JT ID's. Keep track of 1576acfe12dd6d52c801f78c240528b7cb42fa91159Chris Lattner // whether we see a jump table idx, if not, we can delete the JT. 1586acfe12dd6d52c801f78c240528b7cb42fa91159Chris Lattner std::vector<bool> JTIsLive; 1596acfe12dd6d52c801f78c240528b7cb42fa91159Chris Lattner JTIsLive.resize(JTs.size()); 1606acfe12dd6d52c801f78c240528b7cb42fa91159Chris Lattner for (MachineFunction::iterator BB = MF.begin(), E = MF.end(); 1616acfe12dd6d52c801f78c240528b7cb42fa91159Chris Lattner BB != E; ++BB) { 1626acfe12dd6d52c801f78c240528b7cb42fa91159Chris Lattner for (MachineBasicBlock::iterator I = BB->begin(), E = BB->end(); 1636acfe12dd6d52c801f78c240528b7cb42fa91159Chris Lattner I != E; ++I) 1646acfe12dd6d52c801f78c240528b7cb42fa91159Chris Lattner for (unsigned op = 0, e = I->getNumOperands(); op != e; ++op) { 1656acfe12dd6d52c801f78c240528b7cb42fa91159Chris Lattner MachineOperand &Op = I->getOperand(op); 1666acfe12dd6d52c801f78c240528b7cb42fa91159Chris Lattner if (!Op.isJumpTableIndex()) continue; 1676acfe12dd6d52c801f78c240528b7cb42fa91159Chris Lattner unsigned NewIdx = JTMapping[Op.getJumpTableIndex()]; 1686acfe12dd6d52c801f78c240528b7cb42fa91159Chris Lattner Op.setJumpTableIndex(NewIdx); 1696acfe12dd6d52c801f78c240528b7cb42fa91159Chris Lattner 1706acfe12dd6d52c801f78c240528b7cb42fa91159Chris Lattner // Remember that this JT is live. 1716acfe12dd6d52c801f78c240528b7cb42fa91159Chris Lattner JTIsLive[NewIdx] = true; 1726acfe12dd6d52c801f78c240528b7cb42fa91159Chris Lattner } 1736acfe12dd6d52c801f78c240528b7cb42fa91159Chris Lattner } 1746acfe12dd6d52c801f78c240528b7cb42fa91159Chris Lattner 1756acfe12dd6d52c801f78c240528b7cb42fa91159Chris Lattner // Finally, remove dead jump tables. This happens either because the 1766acfe12dd6d52c801f78c240528b7cb42fa91159Chris Lattner // indirect jump was unreachable (and thus deleted) or because the jump 1776acfe12dd6d52c801f78c240528b7cb42fa91159Chris Lattner // table was merged with some other one. 1786acfe12dd6d52c801f78c240528b7cb42fa91159Chris Lattner for (unsigned i = 0, e = JTIsLive.size(); i != e; ++i) 1796acfe12dd6d52c801f78c240528b7cb42fa91159Chris Lattner if (!JTIsLive[i]) { 1806acfe12dd6d52c801f78c240528b7cb42fa91159Chris Lattner JTI->RemoveJumpTable(i); 1816acfe12dd6d52c801f78c240528b7cb42fa91159Chris Lattner EverMadeChange = true; 1826acfe12dd6d52c801f78c240528b7cb42fa91159Chris Lattner } 1836acfe12dd6d52c801f78c240528b7cb42fa91159Chris Lattner } 1846acfe12dd6d52c801f78c240528b7cb42fa91159Chris Lattner 18569cb9b78f11d505f4351a269fc90e7b77fcda437Dale Johannesen delete RS; 18612143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner return EverMadeChange; 18712143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner} 18812143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner 18912143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner//===----------------------------------------------------------------------===// 19012143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner// Tail Merging of Blocks 19112143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner//===----------------------------------------------------------------------===// 19212143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner 19312143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner/// HashMachineInstr - Compute a hash value for MI and its operands. 19412143054aa6d120f029d268a5154bf2ecd0f707fChris Lattnerstatic unsigned HashMachineInstr(const MachineInstr *MI) { 19512143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner unsigned Hash = MI->getOpcode(); 19612143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 19712143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner const MachineOperand &Op = MI->getOperand(i); 19812143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner 19912143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner // Merge in bits from the operand if easy. 20012143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner unsigned OperandHash = 0; 20112143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner switch (Op.getType()) { 20212143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner case MachineOperand::MO_Register: OperandHash = Op.getReg(); break; 20312143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner case MachineOperand::MO_Immediate: OperandHash = Op.getImm(); break; 20412143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner case MachineOperand::MO_MachineBasicBlock: 20512143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner OperandHash = Op.getMachineBasicBlock()->getNumber(); 20612143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner break; 20712143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner case MachineOperand::MO_FrameIndex: OperandHash = Op.getFrameIndex(); break; 20812143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner case MachineOperand::MO_ConstantPoolIndex: 20912143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner OperandHash = Op.getConstantPoolIndex(); 21012143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner break; 21112143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner case MachineOperand::MO_JumpTableIndex: 21212143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner OperandHash = Op.getJumpTableIndex(); 21312143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner break; 21412143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner case MachineOperand::MO_GlobalAddress: 21512143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner case MachineOperand::MO_ExternalSymbol: 21612143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner // Global address / external symbol are too hard, don't bother, but do 21712143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner // pull in the offset. 21812143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner OperandHash = Op.getOffset(); 21912143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner break; 22012143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner default: break; 22112143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner } 22212143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner 22312143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner Hash += ((OperandHash << 3) | Op.getType()) << (i&31); 22412143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner } 22512143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner return Hash; 22612143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner} 22712143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner 22812143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner/// HashEndOfMBB - Hash the last two instructions in the MBB. We hash two 22912143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner/// instructions, because cross-jumping only saves code when at least two 23012143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner/// instructions are removed (since a branch must be inserted). 23112143054aa6d120f029d268a5154bf2ecd0f707fChris Lattnerstatic unsigned HashEndOfMBB(const MachineBasicBlock *MBB) { 23212143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner MachineBasicBlock::const_iterator I = MBB->end(); 23312143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner if (I == MBB->begin()) 23412143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner return 0; // Empty MBB. 23512143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner 23612143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner --I; 23712143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner unsigned Hash = HashMachineInstr(I); 23812143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner 23912143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner if (I == MBB->begin()) 24012143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner return Hash; // Single instr MBB. 24112143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner 24212143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner --I; 24312143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner // Hash in the second-to-last instruction. 24412143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner Hash ^= HashMachineInstr(I) << 2; 24512143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner return Hash; 24612143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner} 24712143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner 24812143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner/// ComputeCommonTailLength - Given two machine basic blocks, compute the number 24912143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner/// of instructions they actually have in common together at their end. Return 25012143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner/// iterators for the first shared instruction in each block. 25112143054aa6d120f029d268a5154bf2ecd0f707fChris Lattnerstatic unsigned ComputeCommonTailLength(MachineBasicBlock *MBB1, 25212143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner MachineBasicBlock *MBB2, 25312143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner MachineBasicBlock::iterator &I1, 25412143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner MachineBasicBlock::iterator &I2) { 25512143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner I1 = MBB1->end(); 25612143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner I2 = MBB2->end(); 25712143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner 25812143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner unsigned TailLen = 0; 25912143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner while (I1 != MBB1->begin() && I2 != MBB2->begin()) { 26012143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner --I1; --I2; 26112143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner if (!I1->isIdenticalTo(I2)) { 26212143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner ++I1; ++I2; 26312143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner break; 26412143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner } 26512143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner ++TailLen; 26612143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner } 26712143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner return TailLen; 26812143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner} 26912143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner 27012143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner/// ReplaceTailWithBranchTo - Delete the instruction OldInst and everything 271386e29065db5b05b57440f6b2a6dfa1e7f29a00dChris Lattner/// after it, replacing it with an unconditional branch to NewDest. This 272386e29065db5b05b57440f6b2a6dfa1e7f29a00dChris Lattner/// returns true if OldInst's block is modified, false if NewDest is modified. 27312143054aa6d120f029d268a5154bf2ecd0f707fChris Lattnervoid BranchFolder::ReplaceTailWithBranchTo(MachineBasicBlock::iterator OldInst, 27412143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner MachineBasicBlock *NewDest) { 27512143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner MachineBasicBlock *OldBB = OldInst->getParent(); 27612143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner 27712143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner // Remove all the old successors of OldBB from the CFG. 27812143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner while (!OldBB->succ_empty()) 27912143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner OldBB->removeSuccessor(OldBB->succ_begin()); 28012143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner 28112143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner // Remove all the dead instructions from the end of OldBB. 28212143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner OldBB->erase(OldInst, OldBB->end()); 28312143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner 284386e29065db5b05b57440f6b2a6dfa1e7f29a00dChris Lattner // If OldBB isn't immediately before OldBB, insert a branch to it. 285386e29065db5b05b57440f6b2a6dfa1e7f29a00dChris Lattner if (++MachineFunction::iterator(OldBB) != MachineFunction::iterator(NewDest)) 286386e29065db5b05b57440f6b2a6dfa1e7f29a00dChris Lattner TII->InsertBranch(*OldBB, NewDest, 0, std::vector<MachineOperand>()); 28712143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner OldBB->addSuccessor(NewDest); 28812143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner ++NumTailMerge; 28912143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner} 29012143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner 2911d08d83230338ca5969ff6ae6737a978336538bfChris Lattner/// SplitMBBAt - Given a machine basic block and an iterator into it, split the 2921d08d83230338ca5969ff6ae6737a978336538bfChris Lattner/// MBB so that the part before the iterator falls into the part starting at the 2931d08d83230338ca5969ff6ae6737a978336538bfChris Lattner/// iterator. This returns the new MBB. 2941d08d83230338ca5969ff6ae6737a978336538bfChris LattnerMachineBasicBlock *BranchFolder::SplitMBBAt(MachineBasicBlock &CurMBB, 2951d08d83230338ca5969ff6ae6737a978336538bfChris Lattner MachineBasicBlock::iterator BBI1) { 2961d08d83230338ca5969ff6ae6737a978336538bfChris Lattner // Create the fall-through block. 2971d08d83230338ca5969ff6ae6737a978336538bfChris Lattner MachineFunction::iterator MBBI = &CurMBB; 2981d08d83230338ca5969ff6ae6737a978336538bfChris Lattner MachineBasicBlock *NewMBB = new MachineBasicBlock(CurMBB.getBasicBlock()); 2991d08d83230338ca5969ff6ae6737a978336538bfChris Lattner CurMBB.getParent()->getBasicBlockList().insert(++MBBI, NewMBB); 3001d08d83230338ca5969ff6ae6737a978336538bfChris Lattner 3011d08d83230338ca5969ff6ae6737a978336538bfChris Lattner // Move all the successors of this block to the specified block. 3021d08d83230338ca5969ff6ae6737a978336538bfChris Lattner while (!CurMBB.succ_empty()) { 3031d08d83230338ca5969ff6ae6737a978336538bfChris Lattner MachineBasicBlock *S = *(CurMBB.succ_end()-1); 3041d08d83230338ca5969ff6ae6737a978336538bfChris Lattner NewMBB->addSuccessor(S); 3051d08d83230338ca5969ff6ae6737a978336538bfChris Lattner CurMBB.removeSuccessor(S); 3061d08d83230338ca5969ff6ae6737a978336538bfChris Lattner } 3071d08d83230338ca5969ff6ae6737a978336538bfChris Lattner 3081d08d83230338ca5969ff6ae6737a978336538bfChris Lattner // Add an edge from CurMBB to NewMBB for the fall-through. 3091d08d83230338ca5969ff6ae6737a978336538bfChris Lattner CurMBB.addSuccessor(NewMBB); 3101d08d83230338ca5969ff6ae6737a978336538bfChris Lattner 3111d08d83230338ca5969ff6ae6737a978336538bfChris Lattner // Splice the code over. 3121d08d83230338ca5969ff6ae6737a978336538bfChris Lattner NewMBB->splice(NewMBB->end(), &CurMBB, BBI1, CurMBB.end()); 31369cb9b78f11d505f4351a269fc90e7b77fcda437Dale Johannesen 31469cb9b78f11d505f4351a269fc90e7b77fcda437Dale Johannesen // For targets that use the register scavenger, we must maintain LiveIns. 31569cb9b78f11d505f4351a269fc90e7b77fcda437Dale Johannesen if (RS) { 31669cb9b78f11d505f4351a269fc90e7b77fcda437Dale Johannesen RS->enterBasicBlock(&CurMBB); 31769cb9b78f11d505f4351a269fc90e7b77fcda437Dale Johannesen if (!CurMBB.empty()) 31869cb9b78f11d505f4351a269fc90e7b77fcda437Dale Johannesen RS->forward(prior(CurMBB.end())); 31969cb9b78f11d505f4351a269fc90e7b77fcda437Dale Johannesen BitVector RegsLiveAtExit(RegInfo->getNumRegs()); 32069cb9b78f11d505f4351a269fc90e7b77fcda437Dale Johannesen RS->getRegsUsed(RegsLiveAtExit, false); 32169cb9b78f11d505f4351a269fc90e7b77fcda437Dale Johannesen for (unsigned int i=0, e=RegInfo->getNumRegs(); i!=e; i++) 32269cb9b78f11d505f4351a269fc90e7b77fcda437Dale Johannesen if (RegsLiveAtExit[i]) 32369cb9b78f11d505f4351a269fc90e7b77fcda437Dale Johannesen NewMBB->addLiveIn(i); 32469cb9b78f11d505f4351a269fc90e7b77fcda437Dale Johannesen } 32569cb9b78f11d505f4351a269fc90e7b77fcda437Dale Johannesen 3261d08d83230338ca5969ff6ae6737a978336538bfChris Lattner return NewMBB; 3271d08d83230338ca5969ff6ae6737a978336538bfChris Lattner} 3281d08d83230338ca5969ff6ae6737a978336538bfChris Lattner 329d4bf3c2fd60975b30cd067b59f743a3ea45e45b5Chris Lattner/// EstimateRuntime - Make a rough estimate for how long it will take to run 330d4bf3c2fd60975b30cd067b59f743a3ea45e45b5Chris Lattner/// the specified code. 331d4bf3c2fd60975b30cd067b59f743a3ea45e45b5Chris Lattnerstatic unsigned EstimateRuntime(MachineBasicBlock::iterator I, 332d4bf3c2fd60975b30cd067b59f743a3ea45e45b5Chris Lattner MachineBasicBlock::iterator E, 333d4bf3c2fd60975b30cd067b59f743a3ea45e45b5Chris Lattner const TargetInstrInfo *TII) { 334d4bf3c2fd60975b30cd067b59f743a3ea45e45b5Chris Lattner unsigned Time = 0; 335d4bf3c2fd60975b30cd067b59f743a3ea45e45b5Chris Lattner for (; I != E; ++I) { 336d4bf3c2fd60975b30cd067b59f743a3ea45e45b5Chris Lattner const TargetInstrDescriptor &TID = TII->get(I->getOpcode()); 337d4bf3c2fd60975b30cd067b59f743a3ea45e45b5Chris Lattner if (TID.Flags & M_CALL_FLAG) 338d4bf3c2fd60975b30cd067b59f743a3ea45e45b5Chris Lattner Time += 10; 339d4bf3c2fd60975b30cd067b59f743a3ea45e45b5Chris Lattner else if (TID.Flags & (M_LOAD_FLAG|M_STORE_FLAG)) 340d4bf3c2fd60975b30cd067b59f743a3ea45e45b5Chris Lattner Time += 2; 341d4bf3c2fd60975b30cd067b59f743a3ea45e45b5Chris Lattner else 342d4bf3c2fd60975b30cd067b59f743a3ea45e45b5Chris Lattner ++Time; 343d4bf3c2fd60975b30cd067b59f743a3ea45e45b5Chris Lattner } 344d4bf3c2fd60975b30cd067b59f743a3ea45e45b5Chris Lattner return Time; 345d4bf3c2fd60975b30cd067b59f743a3ea45e45b5Chris Lattner} 346d4bf3c2fd60975b30cd067b59f743a3ea45e45b5Chris Lattner 347d4bf3c2fd60975b30cd067b59f743a3ea45e45b5Chris Lattner/// ShouldSplitFirstBlock - We need to either split MBB1 at MBB1I or MBB2 at 348d4bf3c2fd60975b30cd067b59f743a3ea45e45b5Chris Lattner/// MBB2I and then insert an unconditional branch in the other block. Determine 349d4bf3c2fd60975b30cd067b59f743a3ea45e45b5Chris Lattner/// which is the best to split 350d4bf3c2fd60975b30cd067b59f743a3ea45e45b5Chris Lattnerstatic bool ShouldSplitFirstBlock(MachineBasicBlock *MBB1, 351d4bf3c2fd60975b30cd067b59f743a3ea45e45b5Chris Lattner MachineBasicBlock::iterator MBB1I, 352d4bf3c2fd60975b30cd067b59f743a3ea45e45b5Chris Lattner MachineBasicBlock *MBB2, 353d4bf3c2fd60975b30cd067b59f743a3ea45e45b5Chris Lattner MachineBasicBlock::iterator MBB2I, 35476b38fcabeba725e166a2ff72c56fe31d784b229Dale Johannesen const TargetInstrInfo *TII, 35576b38fcabeba725e166a2ff72c56fe31d784b229Dale Johannesen MachineBasicBlock *PredBB) { 35654f4a6780a33043031af97571dfffdac5a4aa35cDale Johannesen // If one block is the entry block, split the other one; we can't generate 35754f4a6780a33043031af97571dfffdac5a4aa35cDale Johannesen // a branch to the entry block, as its label is not emitted. 35854f4a6780a33043031af97571dfffdac5a4aa35cDale Johannesen MachineBasicBlock *Entry = MBB1->getParent()->begin(); 35954f4a6780a33043031af97571dfffdac5a4aa35cDale Johannesen if (MBB1 == Entry) 36054f4a6780a33043031af97571dfffdac5a4aa35cDale Johannesen return false; 36154f4a6780a33043031af97571dfffdac5a4aa35cDale Johannesen if (MBB2 == Entry) 36254f4a6780a33043031af97571dfffdac5a4aa35cDale Johannesen return true; 36354f4a6780a33043031af97571dfffdac5a4aa35cDale Johannesen 36476b38fcabeba725e166a2ff72c56fe31d784b229Dale Johannesen // If one block falls through into the common successor, choose that 36576b38fcabeba725e166a2ff72c56fe31d784b229Dale Johannesen // one to split; it is one instruction less to do that. 36676b38fcabeba725e166a2ff72c56fe31d784b229Dale Johannesen if (PredBB) { 36776b38fcabeba725e166a2ff72c56fe31d784b229Dale Johannesen if (MBB1 == PredBB) 36876b38fcabeba725e166a2ff72c56fe31d784b229Dale Johannesen return true; 36976b38fcabeba725e166a2ff72c56fe31d784b229Dale Johannesen else if (MBB2 == PredBB) 37076b38fcabeba725e166a2ff72c56fe31d784b229Dale Johannesen return false; 37176b38fcabeba725e166a2ff72c56fe31d784b229Dale Johannesen } 372d4bf3c2fd60975b30cd067b59f743a3ea45e45b5Chris Lattner // TODO: if we had some notion of which block was hotter, we could split 373d4bf3c2fd60975b30cd067b59f743a3ea45e45b5Chris Lattner // the hot block, so it is the fall-through. Since we don't have profile info 374d4bf3c2fd60975b30cd067b59f743a3ea45e45b5Chris Lattner // make a decision based on which will hurt most to split. 375d4bf3c2fd60975b30cd067b59f743a3ea45e45b5Chris Lattner unsigned MBB1Time = EstimateRuntime(MBB1->begin(), MBB1I, TII); 376d4bf3c2fd60975b30cd067b59f743a3ea45e45b5Chris Lattner unsigned MBB2Time = EstimateRuntime(MBB2->begin(), MBB2I, TII); 377d4bf3c2fd60975b30cd067b59f743a3ea45e45b5Chris Lattner 378d4bf3c2fd60975b30cd067b59f743a3ea45e45b5Chris Lattner // If the MBB1 prefix takes "less time" to run than the MBB2 prefix, split the 379d4bf3c2fd60975b30cd067b59f743a3ea45e45b5Chris Lattner // MBB1 block so it falls through. This will penalize the MBB2 path, but will 380d4bf3c2fd60975b30cd067b59f743a3ea45e45b5Chris Lattner // have a lower overall impact on the program execution. 381d4bf3c2fd60975b30cd067b59f743a3ea45e45b5Chris Lattner return MBB1Time < MBB2Time; 382d4bf3c2fd60975b30cd067b59f743a3ea45e45b5Chris Lattner} 383d4bf3c2fd60975b30cd067b59f743a3ea45e45b5Chris Lattner 38476b38fcabeba725e166a2ff72c56fe31d784b229Dale Johannesen// CurMBB needs to add an unconditional branch to SuccMBB (we removed these 38576b38fcabeba725e166a2ff72c56fe31d784b229Dale Johannesen// branches temporarily for tail merging). In the case where CurMBB ends 38676b38fcabeba725e166a2ff72c56fe31d784b229Dale Johannesen// with a conditional branch to the next block, optimize by reversing the 38776b38fcabeba725e166a2ff72c56fe31d784b229Dale Johannesen// test and conditionally branching to SuccMBB instead. 38876b38fcabeba725e166a2ff72c56fe31d784b229Dale Johannesen 38976b38fcabeba725e166a2ff72c56fe31d784b229Dale Johannesenstatic void FixTail(MachineBasicBlock* CurMBB, MachineBasicBlock *SuccBB, 39076b38fcabeba725e166a2ff72c56fe31d784b229Dale Johannesen const TargetInstrInfo *TII) { 39176b38fcabeba725e166a2ff72c56fe31d784b229Dale Johannesen MachineFunction *MF = CurMBB->getParent(); 39276b38fcabeba725e166a2ff72c56fe31d784b229Dale Johannesen MachineFunction::iterator I = next(MachineFunction::iterator(CurMBB)); 39376b38fcabeba725e166a2ff72c56fe31d784b229Dale Johannesen MachineBasicBlock *TBB = 0, *FBB = 0; 39476b38fcabeba725e166a2ff72c56fe31d784b229Dale Johannesen std::vector<MachineOperand> Cond; 39576b38fcabeba725e166a2ff72c56fe31d784b229Dale Johannesen if (I != MF->end() && 39676b38fcabeba725e166a2ff72c56fe31d784b229Dale Johannesen !TII->AnalyzeBranch(*CurMBB, TBB, FBB, Cond)) { 39776b38fcabeba725e166a2ff72c56fe31d784b229Dale Johannesen MachineBasicBlock *NextBB = I; 39876b38fcabeba725e166a2ff72c56fe31d784b229Dale Johannesen if (TBB == NextBB && Cond.size() && !FBB) { 39976b38fcabeba725e166a2ff72c56fe31d784b229Dale Johannesen if (!TII->ReverseBranchCondition(Cond)) { 40076b38fcabeba725e166a2ff72c56fe31d784b229Dale Johannesen TII->RemoveBranch(*CurMBB); 40176b38fcabeba725e166a2ff72c56fe31d784b229Dale Johannesen TII->InsertBranch(*CurMBB, SuccBB, NULL, Cond); 40276b38fcabeba725e166a2ff72c56fe31d784b229Dale Johannesen return; 40376b38fcabeba725e166a2ff72c56fe31d784b229Dale Johannesen } 40476b38fcabeba725e166a2ff72c56fe31d784b229Dale Johannesen } 40576b38fcabeba725e166a2ff72c56fe31d784b229Dale Johannesen } 40676b38fcabeba725e166a2ff72c56fe31d784b229Dale Johannesen TII->InsertBranch(*CurMBB, SuccBB, NULL, std::vector<MachineOperand>()); 40776b38fcabeba725e166a2ff72c56fe31d784b229Dale Johannesen} 40876b38fcabeba725e166a2ff72c56fe31d784b229Dale Johannesen 4097d33b4c59b56afb96feea71073c1d9e70c457e28Dale Johannesen// See if any of the blocks in MergePotentials (which all have a common single 4107d33b4c59b56afb96feea71073c1d9e70c457e28Dale Johannesen// successor, or all have no successor) can be tail-merged. If there is a 4117d33b4c59b56afb96feea71073c1d9e70c457e28Dale Johannesen// successor, any blocks in MergePotentials that are not tail-merged and 4127d33b4c59b56afb96feea71073c1d9e70c457e28Dale Johannesen// are not immediately before Succ must have an unconditional branch to 4137d33b4c59b56afb96feea71073c1d9e70c457e28Dale Johannesen// Succ added (but the predecessor/successor lists need no adjustment). 4147d33b4c59b56afb96feea71073c1d9e70c457e28Dale Johannesen// The lone predecessor of Succ that falls through into Succ, 4157d33b4c59b56afb96feea71073c1d9e70c457e28Dale Johannesen// if any, is given in PredBB. 4167d33b4c59b56afb96feea71073c1d9e70c457e28Dale Johannesen 4177d33b4c59b56afb96feea71073c1d9e70c457e28Dale Johannesenbool BranchFolder::TryMergeBlocks(MachineBasicBlock *SuccBB, 4187d33b4c59b56afb96feea71073c1d9e70c457e28Dale Johannesen MachineBasicBlock* PredBB) { 41912143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner MadeChange = false; 42012143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner 42112143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner // Sort by hash value so that blocks with identical end sequences sort 42212143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner // together. 42312143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner std::stable_sort(MergePotentials.begin(), MergePotentials.end()); 42412143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner 42512143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner // Walk through equivalence sets looking for actual exact matches. 42612143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner while (MergePotentials.size() > 1) { 42712143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner unsigned CurHash = (MergePotentials.end()-1)->first; 42812143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner unsigned PrevHash = (MergePotentials.end()-2)->first; 42912143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner MachineBasicBlock *CurMBB = (MergePotentials.end()-1)->second; 43012143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner 43112143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner // If there is nothing that matches the hash of the current basic block, 43212143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner // give up. 43312143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner if (CurHash != PrevHash) { 4347d33b4c59b56afb96feea71073c1d9e70c457e28Dale Johannesen if (SuccBB && CurMBB != PredBB) 43576b38fcabeba725e166a2ff72c56fe31d784b229Dale Johannesen FixTail(CurMBB, SuccBB, TII); 43612143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner MergePotentials.pop_back(); 43712143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner continue; 43812143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner } 4397821a8afd3009c3c2760592e61de9e2c31c73e18Chris Lattner 44012143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner // Determine the actual length of the shared tail between these two basic 44112143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner // blocks. Because the hash can have collisions, it's possible that this is 44212143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner // less than 2. 44312143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner MachineBasicBlock::iterator BBI1, BBI2; 44412143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner unsigned CommonTailLen = 44512143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner ComputeCommonTailLength(CurMBB, (MergePotentials.end()-2)->second, 44612143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner BBI1, BBI2); 44712143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner 44812143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner // If the tails don't have at least two instructions in common, see if there 44912143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner // is anything else in the equivalence class that does match. 45076b38fcabeba725e166a2ff72c56fe31d784b229Dale Johannesen // Since instructions may get combined later (e.g. single stores into 45176b38fcabeba725e166a2ff72c56fe31d784b229Dale Johannesen // store multiple) this measure is not particularly accurate. 45212143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner if (CommonTailLen < 2) { 45312143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner unsigned FoundMatch = ~0U; 45412143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner for (int i = MergePotentials.size()-2; 45512143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner i != -1 && MergePotentials[i].first == CurHash; --i) { 45612143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner CommonTailLen = ComputeCommonTailLength(CurMBB, 45712143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner MergePotentials[i].second, 45812143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner BBI1, BBI2); 45912143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner if (CommonTailLen >= 2) { 46012143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner FoundMatch = i; 46112143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner break; 46212143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner } 46312143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner } 464c50ffcb7fcb7c1109fee2406e8f74d096f755f47Chris Lattner 46512143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner // If we didn't find anything that has at least two instructions matching 46612143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner // this one, bail out. 46712143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner if (FoundMatch == ~0U) { 4687d33b4c59b56afb96feea71073c1d9e70c457e28Dale Johannesen // Put the unconditional branch back, if we need one. 4697d33b4c59b56afb96feea71073c1d9e70c457e28Dale Johannesen if (SuccBB && CurMBB != PredBB) 47076b38fcabeba725e166a2ff72c56fe31d784b229Dale Johannesen FixTail(CurMBB, SuccBB, TII); 47112143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner MergePotentials.pop_back(); 47212143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner continue; 47321ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner } 47412143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner 47512143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner // Otherwise, move the matching block to the right position. 47612143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner std::swap(MergePotentials[FoundMatch], *(MergePotentials.end()-2)); 47712143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner } 4781d08d83230338ca5969ff6ae6737a978336538bfChris Lattner 47912143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner MachineBasicBlock *MBB2 = (MergePotentials.end()-2)->second; 4801d08d83230338ca5969ff6ae6737a978336538bfChris Lattner 4811d08d83230338ca5969ff6ae6737a978336538bfChris Lattner // If neither block is the entire common tail, split the tail of one block 48254f4a6780a33043031af97571dfffdac5a4aa35cDale Johannesen // to make it redundant with the other tail. Also, we cannot jump to the 48354f4a6780a33043031af97571dfffdac5a4aa35cDale Johannesen // entry block, so if one block is the entry block, split the other one. 48454f4a6780a33043031af97571dfffdac5a4aa35cDale Johannesen MachineBasicBlock *Entry = CurMBB->getParent()->begin(); 48554f4a6780a33043031af97571dfffdac5a4aa35cDale Johannesen if (CurMBB->begin() == BBI1 && CurMBB != Entry) 48654f4a6780a33043031af97571dfffdac5a4aa35cDale Johannesen ; // CurMBB is common tail 48754f4a6780a33043031af97571dfffdac5a4aa35cDale Johannesen else if (MBB2->begin() == BBI2 && MBB2 != Entry) 48854f4a6780a33043031af97571dfffdac5a4aa35cDale Johannesen ; // MBB2 is common tail 48954f4a6780a33043031af97571dfffdac5a4aa35cDale Johannesen else { 4901d08d83230338ca5969ff6ae6737a978336538bfChris Lattner if (0) { // Enable this to disable partial tail merges. 4911d08d83230338ca5969ff6ae6737a978336538bfChris Lattner MergePotentials.pop_back(); 4921d08d83230338ca5969ff6ae6737a978336538bfChris Lattner continue; 4931d08d83230338ca5969ff6ae6737a978336538bfChris Lattner } 494d4bf3c2fd60975b30cd067b59f743a3ea45e45b5Chris Lattner 495d4bf3c2fd60975b30cd067b59f743a3ea45e45b5Chris Lattner // Decide whether we want to split CurMBB or MBB2. 49676b38fcabeba725e166a2ff72c56fe31d784b229Dale Johannesen if (ShouldSplitFirstBlock(CurMBB, BBI1, MBB2, BBI2, TII, PredBB)) { 497d4bf3c2fd60975b30cd067b59f743a3ea45e45b5Chris Lattner CurMBB = SplitMBBAt(*CurMBB, BBI1); 498d4bf3c2fd60975b30cd067b59f743a3ea45e45b5Chris Lattner BBI1 = CurMBB->begin(); 499d4bf3c2fd60975b30cd067b59f743a3ea45e45b5Chris Lattner MergePotentials.back().second = CurMBB; 500d4bf3c2fd60975b30cd067b59f743a3ea45e45b5Chris Lattner } else { 501d4bf3c2fd60975b30cd067b59f743a3ea45e45b5Chris Lattner MBB2 = SplitMBBAt(*MBB2, BBI2); 502d4bf3c2fd60975b30cd067b59f743a3ea45e45b5Chris Lattner BBI2 = MBB2->begin(); 503d4bf3c2fd60975b30cd067b59f743a3ea45e45b5Chris Lattner (MergePotentials.end()-2)->second = MBB2; 504d4bf3c2fd60975b30cd067b59f743a3ea45e45b5Chris Lattner } 5051d08d83230338ca5969ff6ae6737a978336538bfChris Lattner } 5061d08d83230338ca5969ff6ae6737a978336538bfChris Lattner 50754f4a6780a33043031af97571dfffdac5a4aa35cDale Johannesen if (MBB2->begin() == BBI2 && MBB2 != Entry) { 50812143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner // Hack the end off CurMBB, making it jump to MBBI@ instead. 50912143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner ReplaceTailWithBranchTo(BBI1, MBB2); 51012143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner // This modifies CurMBB, so remove it from the worklist. 51112143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner MergePotentials.pop_back(); 5121d08d83230338ca5969ff6ae6737a978336538bfChris Lattner } else { 51354f4a6780a33043031af97571dfffdac5a4aa35cDale Johannesen assert(CurMBB->begin() == BBI1 && CurMBB != Entry && 51454f4a6780a33043031af97571dfffdac5a4aa35cDale Johannesen "Didn't split block correctly?"); 5151d08d83230338ca5969ff6ae6737a978336538bfChris Lattner // Hack the end off MBB2, making it jump to CurMBB instead. 5161d08d83230338ca5969ff6ae6737a978336538bfChris Lattner ReplaceTailWithBranchTo(BBI2, CurMBB); 5171d08d83230338ca5969ff6ae6737a978336538bfChris Lattner // This modifies MBB2, so remove it from the worklist. 5181d08d83230338ca5969ff6ae6737a978336538bfChris Lattner MergePotentials.erase(MergePotentials.end()-2); 51912143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner } 5201d08d83230338ca5969ff6ae6737a978336538bfChris Lattner MadeChange = true; 52121ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner } 52212143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner return MadeChange; 52312143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner} 52421ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner 5257d33b4c59b56afb96feea71073c1d9e70c457e28Dale Johannesenbool BranchFolder::TailMergeBlocks(MachineFunction &MF) { 52676b38fcabeba725e166a2ff72c56fe31d784b229Dale Johannesen 5277d33b4c59b56afb96feea71073c1d9e70c457e28Dale Johannesen if (!EnableTailMerge) return false; 52876b38fcabeba725e166a2ff72c56fe31d784b229Dale Johannesen 52976b38fcabeba725e166a2ff72c56fe31d784b229Dale Johannesen MadeChange = false; 53076b38fcabeba725e166a2ff72c56fe31d784b229Dale Johannesen 5317d33b4c59b56afb96feea71073c1d9e70c457e28Dale Johannesen // First find blocks with no successors. 53276b38fcabeba725e166a2ff72c56fe31d784b229Dale Johannesen MergePotentials.clear(); 5337d33b4c59b56afb96feea71073c1d9e70c457e28Dale Johannesen for (MachineFunction::iterator I = MF.begin(), E = MF.end(); I != E; ++I) { 5347d33b4c59b56afb96feea71073c1d9e70c457e28Dale Johannesen if (I->succ_empty()) 5357d33b4c59b56afb96feea71073c1d9e70c457e28Dale Johannesen MergePotentials.push_back(std::make_pair(HashEndOfMBB(I), I)); 5367d33b4c59b56afb96feea71073c1d9e70c457e28Dale Johannesen } 53776b38fcabeba725e166a2ff72c56fe31d784b229Dale Johannesen // See if we can do any tail merging on those. 5387d33b4c59b56afb96feea71073c1d9e70c457e28Dale Johannesen MadeChange |= TryMergeBlocks(NULL, NULL); 5397d33b4c59b56afb96feea71073c1d9e70c457e28Dale Johannesen 54076b38fcabeba725e166a2ff72c56fe31d784b229Dale Johannesen // Look at blocks (IBB) with multiple predecessors (PBB). 54176b38fcabeba725e166a2ff72c56fe31d784b229Dale Johannesen // We change each predecessor to a canonical form, by 54276b38fcabeba725e166a2ff72c56fe31d784b229Dale Johannesen // (1) temporarily removing any unconditional branch from the predecessor 54376b38fcabeba725e166a2ff72c56fe31d784b229Dale Johannesen // to IBB, and 54476b38fcabeba725e166a2ff72c56fe31d784b229Dale Johannesen // (2) alter conditional branches so they branch to the other block 54576b38fcabeba725e166a2ff72c56fe31d784b229Dale Johannesen // not IBB; this may require adding back an unconditional branch to IBB 54676b38fcabeba725e166a2ff72c56fe31d784b229Dale Johannesen // later, where there wasn't one coming in. E.g. 54776b38fcabeba725e166a2ff72c56fe31d784b229Dale Johannesen // Bcc IBB 54876b38fcabeba725e166a2ff72c56fe31d784b229Dale Johannesen // fallthrough to QBB 54976b38fcabeba725e166a2ff72c56fe31d784b229Dale Johannesen // here becomes 55076b38fcabeba725e166a2ff72c56fe31d784b229Dale Johannesen // Bncc QBB 55176b38fcabeba725e166a2ff72c56fe31d784b229Dale Johannesen // with a conceptual B to IBB after that, which never actually exists. 55276b38fcabeba725e166a2ff72c56fe31d784b229Dale Johannesen // With those changes, we see whether the predecessors' tails match, 55376b38fcabeba725e166a2ff72c56fe31d784b229Dale Johannesen // and merge them if so. We change things out of canonical form and 55476b38fcabeba725e166a2ff72c56fe31d784b229Dale Johannesen // back to the way they were later in the process. (OptimizeBranches 55576b38fcabeba725e166a2ff72c56fe31d784b229Dale Johannesen // would undo some of this, but we can't use it, because we'd get into 55676b38fcabeba725e166a2ff72c56fe31d784b229Dale Johannesen // a compile-time infinite loop repeatedly doing and undoing the same 55776b38fcabeba725e166a2ff72c56fe31d784b229Dale Johannesen // transformations.) 5587d33b4c59b56afb96feea71073c1d9e70c457e28Dale Johannesen 5597d33b4c59b56afb96feea71073c1d9e70c457e28Dale Johannesen for (MachineFunction::iterator I = MF.begin(), E = MF.end(); I != E; ++I) { 5607d33b4c59b56afb96feea71073c1d9e70c457e28Dale Johannesen if (!I->succ_empty() && I->pred_size() >= 2) { 5617d33b4c59b56afb96feea71073c1d9e70c457e28Dale Johannesen MachineBasicBlock *IBB = I; 5627d33b4c59b56afb96feea71073c1d9e70c457e28Dale Johannesen MachineBasicBlock *PredBB = prior(I); 56376b38fcabeba725e166a2ff72c56fe31d784b229Dale Johannesen MergePotentials.clear(); 5647d33b4c59b56afb96feea71073c1d9e70c457e28Dale Johannesen for (MachineBasicBlock::pred_iterator P = I->pred_begin(), E2 = I->pred_end(); 5657d33b4c59b56afb96feea71073c1d9e70c457e28Dale Johannesen P != E2; ++P) { 5667d33b4c59b56afb96feea71073c1d9e70c457e28Dale Johannesen MachineBasicBlock* PBB = *P; 56776b38fcabeba725e166a2ff72c56fe31d784b229Dale Johannesen // Skip blocks that loop to themselves, can't tail merge these. 56876b38fcabeba725e166a2ff72c56fe31d784b229Dale Johannesen if (PBB==IBB) 56976b38fcabeba725e166a2ff72c56fe31d784b229Dale Johannesen continue; 5707d33b4c59b56afb96feea71073c1d9e70c457e28Dale Johannesen MachineBasicBlock *TBB = 0, *FBB = 0; 5717d33b4c59b56afb96feea71073c1d9e70c457e28Dale Johannesen std::vector<MachineOperand> Cond; 57276b38fcabeba725e166a2ff72c56fe31d784b229Dale Johannesen if (!TII->AnalyzeBranch(*PBB, TBB, FBB, Cond)) { 57376b38fcabeba725e166a2ff72c56fe31d784b229Dale Johannesen // Failing case: IBB is the target of a cbr, and 57476b38fcabeba725e166a2ff72c56fe31d784b229Dale Johannesen // we cannot reverse the branch. 57576b38fcabeba725e166a2ff72c56fe31d784b229Dale Johannesen std::vector<MachineOperand> NewCond(Cond); 57676b38fcabeba725e166a2ff72c56fe31d784b229Dale Johannesen if (Cond.size() && TBB==IBB) { 57776b38fcabeba725e166a2ff72c56fe31d784b229Dale Johannesen if (TII->ReverseBranchCondition(NewCond)) 57876b38fcabeba725e166a2ff72c56fe31d784b229Dale Johannesen continue; 57976b38fcabeba725e166a2ff72c56fe31d784b229Dale Johannesen // This is the QBB case described above 58076b38fcabeba725e166a2ff72c56fe31d784b229Dale Johannesen if (!FBB) 58176b38fcabeba725e166a2ff72c56fe31d784b229Dale Johannesen FBB = next(MachineFunction::iterator(PBB)); 58276b38fcabeba725e166a2ff72c56fe31d784b229Dale Johannesen } 58376b38fcabeba725e166a2ff72c56fe31d784b229Dale Johannesen // Remove the unconditional branch at the end, if any. 58476b38fcabeba725e166a2ff72c56fe31d784b229Dale Johannesen if (TBB && (Cond.size()==0 || FBB)) { 5857d33b4c59b56afb96feea71073c1d9e70c457e28Dale Johannesen TII->RemoveBranch(*PBB); 58676b38fcabeba725e166a2ff72c56fe31d784b229Dale Johannesen if (Cond.size()) 5877d33b4c59b56afb96feea71073c1d9e70c457e28Dale Johannesen // reinsert conditional branch only, for now 58876b38fcabeba725e166a2ff72c56fe31d784b229Dale Johannesen TII->InsertBranch(*PBB, (TBB==IBB) ? FBB : TBB, 0, NewCond); 5897d33b4c59b56afb96feea71073c1d9e70c457e28Dale Johannesen } 5907d33b4c59b56afb96feea71073c1d9e70c457e28Dale Johannesen MergePotentials.push_back(std::make_pair(HashEndOfMBB(PBB), *P)); 5917d33b4c59b56afb96feea71073c1d9e70c457e28Dale Johannesen } 5927d33b4c59b56afb96feea71073c1d9e70c457e28Dale Johannesen } 5937d33b4c59b56afb96feea71073c1d9e70c457e28Dale Johannesen if (MergePotentials.size() >= 2) 5947d33b4c59b56afb96feea71073c1d9e70c457e28Dale Johannesen MadeChange |= TryMergeBlocks(I, PredBB); 5957d33b4c59b56afb96feea71073c1d9e70c457e28Dale Johannesen // Reinsert an unconditional branch if needed. 5967d33b4c59b56afb96feea71073c1d9e70c457e28Dale Johannesen // The 1 below can be either an original single predecessor, or a result 5977d33b4c59b56afb96feea71073c1d9e70c457e28Dale Johannesen // of removing blocks in TryMergeBlocks. 5987d33b4c59b56afb96feea71073c1d9e70c457e28Dale Johannesen if (MergePotentials.size()==1 && 5997d33b4c59b56afb96feea71073c1d9e70c457e28Dale Johannesen (MergePotentials.begin())->second != PredBB) 60076b38fcabeba725e166a2ff72c56fe31d784b229Dale Johannesen FixTail((MergePotentials.begin())->second, I, TII); 6017d33b4c59b56afb96feea71073c1d9e70c457e28Dale Johannesen } 6027d33b4c59b56afb96feea71073c1d9e70c457e28Dale Johannesen } 6037d33b4c59b56afb96feea71073c1d9e70c457e28Dale Johannesen return MadeChange; 6047d33b4c59b56afb96feea71073c1d9e70c457e28Dale Johannesen} 60512143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner 60612143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner//===----------------------------------------------------------------------===// 60712143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner// Branch Optimization 60812143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner//===----------------------------------------------------------------------===// 60912143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner 61012143054aa6d120f029d268a5154bf2ecd0f707fChris Lattnerbool BranchFolder::OptimizeBranches(MachineFunction &MF) { 61112143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner MadeChange = false; 61212143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner 6136b896cec8b703e08e5f3d809e086a39b6ebe6589Dale Johannesen // Make sure blocks are numbered in order 6146b896cec8b703e08e5f3d809e086a39b6ebe6589Dale Johannesen MF.RenumberBlocks(); 6156b896cec8b703e08e5f3d809e086a39b6ebe6589Dale Johannesen 61612143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner for (MachineFunction::iterator I = ++MF.begin(), E = MF.end(); I != E; ) { 61712143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner MachineBasicBlock *MBB = I++; 61812143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner OptimizeBlock(MBB); 61912143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner 62012143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner // If it is dead, remove it. 621033c9715d9bf7ce59ad2e466bf0720811b34da08Jim Laskey if (MBB->pred_empty()) { 62212143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner RemoveDeadBlock(MBB); 62312143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner MadeChange = true; 62412143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner ++NumDeadBlocks; 62512143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner } 62612143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner } 62712143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner return MadeChange; 62821ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner} 62921ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner 63012143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner 631386e29065db5b05b57440f6b2a6dfa1e7f29a00dChris Lattner/// CorrectExtraCFGEdges - Various pieces of code can cause excess edges in the 632386e29065db5b05b57440f6b2a6dfa1e7f29a00dChris Lattner/// CFG to be inserted. If we have proven that MBB can only branch to DestA and 633386e29065db5b05b57440f6b2a6dfa1e7f29a00dChris Lattner/// DestB, remove any other MBB successors from the CFG. DestA and DestB can 634386e29065db5b05b57440f6b2a6dfa1e7f29a00dChris Lattner/// be null. 635386e29065db5b05b57440f6b2a6dfa1e7f29a00dChris Lattnerstatic bool CorrectExtraCFGEdges(MachineBasicBlock &MBB, 636386e29065db5b05b57440f6b2a6dfa1e7f29a00dChris Lattner MachineBasicBlock *DestA, 637386e29065db5b05b57440f6b2a6dfa1e7f29a00dChris Lattner MachineBasicBlock *DestB, 638386e29065db5b05b57440f6b2a6dfa1e7f29a00dChris Lattner bool isCond, 639386e29065db5b05b57440f6b2a6dfa1e7f29a00dChris Lattner MachineFunction::iterator FallThru) { 640386e29065db5b05b57440f6b2a6dfa1e7f29a00dChris Lattner bool MadeChange = false; 641386e29065db5b05b57440f6b2a6dfa1e7f29a00dChris Lattner bool AddedFallThrough = false; 642386e29065db5b05b57440f6b2a6dfa1e7f29a00dChris Lattner 643386e29065db5b05b57440f6b2a6dfa1e7f29a00dChris Lattner // If this block ends with a conditional branch that falls through to its 644386e29065db5b05b57440f6b2a6dfa1e7f29a00dChris Lattner // successor, set DestB as the successor. 645386e29065db5b05b57440f6b2a6dfa1e7f29a00dChris Lattner if (isCond) { 646386e29065db5b05b57440f6b2a6dfa1e7f29a00dChris Lattner if (DestB == 0 && FallThru != MBB.getParent()->end()) { 647386e29065db5b05b57440f6b2a6dfa1e7f29a00dChris Lattner DestB = FallThru; 648386e29065db5b05b57440f6b2a6dfa1e7f29a00dChris Lattner AddedFallThrough = true; 649386e29065db5b05b57440f6b2a6dfa1e7f29a00dChris Lattner } 650386e29065db5b05b57440f6b2a6dfa1e7f29a00dChris Lattner } else { 651386e29065db5b05b57440f6b2a6dfa1e7f29a00dChris Lattner // If this is an unconditional branch with no explicit dest, it must just be 652386e29065db5b05b57440f6b2a6dfa1e7f29a00dChris Lattner // a fallthrough into DestB. 653386e29065db5b05b57440f6b2a6dfa1e7f29a00dChris Lattner if (DestA == 0 && FallThru != MBB.getParent()->end()) { 654386e29065db5b05b57440f6b2a6dfa1e7f29a00dChris Lattner DestA = FallThru; 655386e29065db5b05b57440f6b2a6dfa1e7f29a00dChris Lattner AddedFallThrough = true; 656386e29065db5b05b57440f6b2a6dfa1e7f29a00dChris Lattner } 657386e29065db5b05b57440f6b2a6dfa1e7f29a00dChris Lattner } 658386e29065db5b05b57440f6b2a6dfa1e7f29a00dChris Lattner 659386e29065db5b05b57440f6b2a6dfa1e7f29a00dChris Lattner MachineBasicBlock::pred_iterator SI = MBB.succ_begin(); 660386e29065db5b05b57440f6b2a6dfa1e7f29a00dChris Lattner while (SI != MBB.succ_end()) { 661386e29065db5b05b57440f6b2a6dfa1e7f29a00dChris Lattner if (*SI == DestA) { 662386e29065db5b05b57440f6b2a6dfa1e7f29a00dChris Lattner DestA = 0; 663386e29065db5b05b57440f6b2a6dfa1e7f29a00dChris Lattner ++SI; 664386e29065db5b05b57440f6b2a6dfa1e7f29a00dChris Lattner } else if (*SI == DestB) { 665386e29065db5b05b57440f6b2a6dfa1e7f29a00dChris Lattner DestB = 0; 666386e29065db5b05b57440f6b2a6dfa1e7f29a00dChris Lattner ++SI; 66702b3f5ec4ac120d14a63f7fd4f4388b7d0ab6c22Jim Laskey } else if ((*SI)->isLandingPad()) { 66802b3f5ec4ac120d14a63f7fd4f4388b7d0ab6c22Jim Laskey ++SI; 669386e29065db5b05b57440f6b2a6dfa1e7f29a00dChris Lattner } else { 670386e29065db5b05b57440f6b2a6dfa1e7f29a00dChris Lattner // Otherwise, this is a superfluous edge, remove it. 671386e29065db5b05b57440f6b2a6dfa1e7f29a00dChris Lattner MBB.removeSuccessor(SI); 672386e29065db5b05b57440f6b2a6dfa1e7f29a00dChris Lattner MadeChange = true; 673386e29065db5b05b57440f6b2a6dfa1e7f29a00dChris Lattner } 674386e29065db5b05b57440f6b2a6dfa1e7f29a00dChris Lattner } 675386e29065db5b05b57440f6b2a6dfa1e7f29a00dChris Lattner if (!AddedFallThrough) { 676386e29065db5b05b57440f6b2a6dfa1e7f29a00dChris Lattner assert(DestA == 0 && DestB == 0 && 677386e29065db5b05b57440f6b2a6dfa1e7f29a00dChris Lattner "MachineCFG is missing edges!"); 678386e29065db5b05b57440f6b2a6dfa1e7f29a00dChris Lattner } else if (isCond) { 679386e29065db5b05b57440f6b2a6dfa1e7f29a00dChris Lattner assert(DestA == 0 && "MachineCFG is missing edges!"); 680386e29065db5b05b57440f6b2a6dfa1e7f29a00dChris Lattner } 681386e29065db5b05b57440f6b2a6dfa1e7f29a00dChris Lattner return MadeChange; 682386e29065db5b05b57440f6b2a6dfa1e7f29a00dChris Lattner} 683386e29065db5b05b57440f6b2a6dfa1e7f29a00dChris Lattner 684386e29065db5b05b57440f6b2a6dfa1e7f29a00dChris Lattner 68521ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner/// ReplaceUsesOfBlockWith - Given a machine basic block 'BB' that branched to 68621ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner/// 'Old', change the code and CFG so that it branches to 'New' instead. 68721ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattnerstatic void ReplaceUsesOfBlockWith(MachineBasicBlock *BB, 68821ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner MachineBasicBlock *Old, 68921ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner MachineBasicBlock *New, 6907821a8afd3009c3c2760592e61de9e2c31c73e18Chris Lattner const TargetInstrInfo *TII) { 69121ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner assert(Old != New && "Cannot replace self with self!"); 69221ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner 69321ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner MachineBasicBlock::iterator I = BB->end(); 69421ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner while (I != BB->begin()) { 69521ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner --I; 6967821a8afd3009c3c2760592e61de9e2c31c73e18Chris Lattner if (!TII->isTerminatorInstr(I->getOpcode())) break; 69721ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner 69821ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner // Scan the operands of this machine instruction, replacing any uses of Old 69921ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner // with New. 70021ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i) 70121ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner if (I->getOperand(i).isMachineBasicBlock() && 70221ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner I->getOperand(i).getMachineBasicBlock() == Old) 70321ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner I->getOperand(i).setMachineBasicBlock(New); 70421ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner } 70521ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner 706eb15eeec396145b6f5028d07bd2c4a5e903fdec5Chris Lattner // Update the successor information. 70721ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner std::vector<MachineBasicBlock*> Succs(BB->succ_begin(), BB->succ_end()); 70821ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner for (int i = Succs.size()-1; i >= 0; --i) 70921ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner if (Succs[i] == Old) { 71021ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner BB->removeSuccessor(Old); 71121ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner BB->addSuccessor(New); 71221ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner } 71321ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner} 71421ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner 7156b0e3f890779b7fc912bec8d40a9590e44742737Chris Lattner/// CanFallThrough - Return true if the specified block (with the specified 7166b0e3f890779b7fc912bec8d40a9590e44742737Chris Lattner/// branch condition) can implicitly transfer control to the block after it by 7176b0e3f890779b7fc912bec8d40a9590e44742737Chris Lattner/// falling off the end of it. This should return false if it can reach the 7186b0e3f890779b7fc912bec8d40a9590e44742737Chris Lattner/// block after it, but it uses an explicit branch to do so (e.g. a table jump). 7196b0e3f890779b7fc912bec8d40a9590e44742737Chris Lattner/// 7206b0e3f890779b7fc912bec8d40a9590e44742737Chris Lattner/// True is a conservative answer. 7216b0e3f890779b7fc912bec8d40a9590e44742737Chris Lattner/// 7226b0e3f890779b7fc912bec8d40a9590e44742737Chris Lattnerbool BranchFolder::CanFallThrough(MachineBasicBlock *CurBB, 7236b0e3f890779b7fc912bec8d40a9590e44742737Chris Lattner bool BranchUnAnalyzable, 7246b0e3f890779b7fc912bec8d40a9590e44742737Chris Lattner MachineBasicBlock *TBB, MachineBasicBlock *FBB, 7256b0e3f890779b7fc912bec8d40a9590e44742737Chris Lattner const std::vector<MachineOperand> &Cond) { 7266b0e3f890779b7fc912bec8d40a9590e44742737Chris Lattner MachineFunction::iterator Fallthrough = CurBB; 7276b0e3f890779b7fc912bec8d40a9590e44742737Chris Lattner ++Fallthrough; 7286b0e3f890779b7fc912bec8d40a9590e44742737Chris Lattner // If FallthroughBlock is off the end of the function, it can't fall through. 7296b0e3f890779b7fc912bec8d40a9590e44742737Chris Lattner if (Fallthrough == CurBB->getParent()->end()) 7306b0e3f890779b7fc912bec8d40a9590e44742737Chris Lattner return false; 7316b0e3f890779b7fc912bec8d40a9590e44742737Chris Lattner 7326b0e3f890779b7fc912bec8d40a9590e44742737Chris Lattner // If FallthroughBlock isn't a successor of CurBB, no fallthrough is possible. 7336b0e3f890779b7fc912bec8d40a9590e44742737Chris Lattner if (!CurBB->isSuccessor(Fallthrough)) 7346b0e3f890779b7fc912bec8d40a9590e44742737Chris Lattner return false; 7356b0e3f890779b7fc912bec8d40a9590e44742737Chris Lattner 7366b0e3f890779b7fc912bec8d40a9590e44742737Chris Lattner // If we couldn't analyze the branch, assume it could fall through. 7376b0e3f890779b7fc912bec8d40a9590e44742737Chris Lattner if (BranchUnAnalyzable) return true; 7386b0e3f890779b7fc912bec8d40a9590e44742737Chris Lattner 7397d09784d3fc652131a2afbf06a0f2ed893837fb9Chris Lattner // If there is no branch, control always falls through. 7407d09784d3fc652131a2afbf06a0f2ed893837fb9Chris Lattner if (TBB == 0) return true; 7417d09784d3fc652131a2afbf06a0f2ed893837fb9Chris Lattner 7427d09784d3fc652131a2afbf06a0f2ed893837fb9Chris Lattner // If there is some explicit branch to the fallthrough block, it can obviously 7437d09784d3fc652131a2afbf06a0f2ed893837fb9Chris Lattner // reach, even though the branch should get folded to fall through implicitly. 7446b0e3f890779b7fc912bec8d40a9590e44742737Chris Lattner if (MachineFunction::iterator(TBB) == Fallthrough || 7456b0e3f890779b7fc912bec8d40a9590e44742737Chris Lattner MachineFunction::iterator(FBB) == Fallthrough) 7467d09784d3fc652131a2afbf06a0f2ed893837fb9Chris Lattner return true; 7477d09784d3fc652131a2afbf06a0f2ed893837fb9Chris Lattner 7487d09784d3fc652131a2afbf06a0f2ed893837fb9Chris Lattner // If it's an unconditional branch to some block not the fall through, it 7497d09784d3fc652131a2afbf06a0f2ed893837fb9Chris Lattner // doesn't fall through. 7507d09784d3fc652131a2afbf06a0f2ed893837fb9Chris Lattner if (Cond.empty()) return false; 7517d09784d3fc652131a2afbf06a0f2ed893837fb9Chris Lattner 7527d09784d3fc652131a2afbf06a0f2ed893837fb9Chris Lattner // Otherwise, if it is conditional and has no explicit false block, it falls 7537d09784d3fc652131a2afbf06a0f2ed893837fb9Chris Lattner // through. 754c2e91e34dc18d794435db86713c06400ea60e930Chris Lattner return FBB == 0; 7557d09784d3fc652131a2afbf06a0f2ed893837fb9Chris Lattner} 7567d09784d3fc652131a2afbf06a0f2ed893837fb9Chris Lattner 7576b0e3f890779b7fc912bec8d40a9590e44742737Chris Lattner/// CanFallThrough - Return true if the specified can implicitly transfer 7586b0e3f890779b7fc912bec8d40a9590e44742737Chris Lattner/// control to the block after it by falling off the end of it. This should 7596b0e3f890779b7fc912bec8d40a9590e44742737Chris Lattner/// return false if it can reach the block after it, but it uses an explicit 7606b0e3f890779b7fc912bec8d40a9590e44742737Chris Lattner/// branch to do so (e.g. a table jump). 7616b0e3f890779b7fc912bec8d40a9590e44742737Chris Lattner/// 7626b0e3f890779b7fc912bec8d40a9590e44742737Chris Lattner/// True is a conservative answer. 7636b0e3f890779b7fc912bec8d40a9590e44742737Chris Lattner/// 7646b0e3f890779b7fc912bec8d40a9590e44742737Chris Lattnerbool BranchFolder::CanFallThrough(MachineBasicBlock *CurBB) { 7656b0e3f890779b7fc912bec8d40a9590e44742737Chris Lattner MachineBasicBlock *TBB = 0, *FBB = 0; 7666b0e3f890779b7fc912bec8d40a9590e44742737Chris Lattner std::vector<MachineOperand> Cond; 7676b0e3f890779b7fc912bec8d40a9590e44742737Chris Lattner bool CurUnAnalyzable = TII->AnalyzeBranch(*CurBB, TBB, FBB, Cond); 7686b0e3f890779b7fc912bec8d40a9590e44742737Chris Lattner return CanFallThrough(CurBB, CurUnAnalyzable, TBB, FBB, Cond); 7696b0e3f890779b7fc912bec8d40a9590e44742737Chris Lattner} 7706b0e3f890779b7fc912bec8d40a9590e44742737Chris Lattner 771a7bef4a4e49f461984c04ef6be6eef3f1c023558Chris Lattner/// IsBetterFallthrough - Return true if it would be clearly better to 772a7bef4a4e49f461984c04ef6be6eef3f1c023558Chris Lattner/// fall-through to MBB1 than to fall through into MBB2. This has to return 773a7bef4a4e49f461984c04ef6be6eef3f1c023558Chris Lattner/// a strict ordering, returning true for both (MBB1,MBB2) and (MBB2,MBB1) will 774a7bef4a4e49f461984c04ef6be6eef3f1c023558Chris Lattner/// result in infinite loops. 775a7bef4a4e49f461984c04ef6be6eef3f1c023558Chris Lattnerstatic bool IsBetterFallthrough(MachineBasicBlock *MBB1, 776a7bef4a4e49f461984c04ef6be6eef3f1c023558Chris Lattner MachineBasicBlock *MBB2, 777a7bef4a4e49f461984c04ef6be6eef3f1c023558Chris Lattner const TargetInstrInfo &TII) { 778154e1047184384afd0a701a9f8816459cf0b3490Chris Lattner // Right now, we use a simple heuristic. If MBB2 ends with a call, and 779154e1047184384afd0a701a9f8816459cf0b3490Chris Lattner // MBB1 doesn't, we prefer to fall through into MBB1. This allows us to 780a7bef4a4e49f461984c04ef6be6eef3f1c023558Chris Lattner // optimize branches that branch to either a return block or an assert block 781a7bef4a4e49f461984c04ef6be6eef3f1c023558Chris Lattner // into a fallthrough to the return. 782a7bef4a4e49f461984c04ef6be6eef3f1c023558Chris Lattner if (MBB1->empty() || MBB2->empty()) return false; 783a7bef4a4e49f461984c04ef6be6eef3f1c023558Chris Lattner 784a7bef4a4e49f461984c04ef6be6eef3f1c023558Chris Lattner MachineInstr *MBB1I = --MBB1->end(); 785a7bef4a4e49f461984c04ef6be6eef3f1c023558Chris Lattner MachineInstr *MBB2I = --MBB2->end(); 786154e1047184384afd0a701a9f8816459cf0b3490Chris Lattner return TII.isCall(MBB2I->getOpcode()) && !TII.isCall(MBB1I->getOpcode()); 787a7bef4a4e49f461984c04ef6be6eef3f1c023558Chris Lattner} 788a7bef4a4e49f461984c04ef6be6eef3f1c023558Chris Lattner 7897821a8afd3009c3c2760592e61de9e2c31c73e18Chris Lattner/// OptimizeBlock - Analyze and optimize control flow related to the specified 7907821a8afd3009c3c2760592e61de9e2c31c73e18Chris Lattner/// block. This is never called on the entry block. 7917d09784d3fc652131a2afbf06a0f2ed893837fb9Chris Lattnervoid BranchFolder::OptimizeBlock(MachineBasicBlock *MBB) { 7927d09784d3fc652131a2afbf06a0f2ed893837fb9Chris Lattner MachineFunction::iterator FallThrough = MBB; 7937d09784d3fc652131a2afbf06a0f2ed893837fb9Chris Lattner ++FallThrough; 7947d09784d3fc652131a2afbf06a0f2ed893837fb9Chris Lattner 795eb15eeec396145b6f5028d07bd2c4a5e903fdec5Chris Lattner // If this block is empty, make everyone use its fall-through, not the block 79621ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner // explicitly. 79721ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner if (MBB->empty()) { 798386e29065db5b05b57440f6b2a6dfa1e7f29a00dChris Lattner // Dead block? Leave for cleanup later. 799033c9715d9bf7ce59ad2e466bf0720811b34da08Jim Laskey if (MBB->pred_empty()) return; 8007821a8afd3009c3c2760592e61de9e2c31c73e18Chris Lattner 801c50ffcb7fcb7c1109fee2406e8f74d096f755f47Chris Lattner if (FallThrough == MBB->getParent()->end()) { 802c50ffcb7fcb7c1109fee2406e8f74d096f755f47Chris Lattner // TODO: Simplify preds to not branch here if possible! 803c50ffcb7fcb7c1109fee2406e8f74d096f755f47Chris Lattner } else { 804c50ffcb7fcb7c1109fee2406e8f74d096f755f47Chris Lattner // Rewrite all predecessors of the old block to go to the fallthrough 805c50ffcb7fcb7c1109fee2406e8f74d096f755f47Chris Lattner // instead. 806033c9715d9bf7ce59ad2e466bf0720811b34da08Jim Laskey while (!MBB->pred_empty()) { 8077821a8afd3009c3c2760592e61de9e2c31c73e18Chris Lattner MachineBasicBlock *Pred = *(MBB->pred_end()-1); 8087821a8afd3009c3c2760592e61de9e2c31c73e18Chris Lattner ReplaceUsesOfBlockWith(Pred, MBB, FallThrough, TII); 8097821a8afd3009c3c2760592e61de9e2c31c73e18Chris Lattner } 810c50ffcb7fcb7c1109fee2406e8f74d096f755f47Chris Lattner 811c50ffcb7fcb7c1109fee2406e8f74d096f755f47Chris Lattner // If MBB was the target of a jump table, update jump tables to go to the 812c50ffcb7fcb7c1109fee2406e8f74d096f755f47Chris Lattner // fallthrough instead. 8136acfe12dd6d52c801f78c240528b7cb42fa91159Chris Lattner MBB->getParent()->getJumpTableInfo()-> 8146acfe12dd6d52c801f78c240528b7cb42fa91159Chris Lattner ReplaceMBBInJumpTables(MBB, FallThrough); 8157821a8afd3009c3c2760592e61de9e2c31c73e18Chris Lattner MadeChange = true; 81621ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner } 8177821a8afd3009c3c2760592e61de9e2c31c73e18Chris Lattner return; 81821ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner } 81921ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner 8207821a8afd3009c3c2760592e61de9e2c31c73e18Chris Lattner // Check to see if we can simplify the terminator of the block before this 8217821a8afd3009c3c2760592e61de9e2c31c73e18Chris Lattner // one. 8227d09784d3fc652131a2afbf06a0f2ed893837fb9Chris Lattner MachineBasicBlock &PrevBB = *prior(MachineFunction::iterator(MBB)); 823ffddf6ba1c58b42dcfd071972754649c3ca5dff7Chris Lattner 8247821a8afd3009c3c2760592e61de9e2c31c73e18Chris Lattner MachineBasicBlock *PriorTBB = 0, *PriorFBB = 0; 8257821a8afd3009c3c2760592e61de9e2c31c73e18Chris Lattner std::vector<MachineOperand> PriorCond; 8266b0e3f890779b7fc912bec8d40a9590e44742737Chris Lattner bool PriorUnAnalyzable = 8276b0e3f890779b7fc912bec8d40a9590e44742737Chris Lattner TII->AnalyzeBranch(PrevBB, PriorTBB, PriorFBB, PriorCond); 828386e29065db5b05b57440f6b2a6dfa1e7f29a00dChris Lattner if (!PriorUnAnalyzable) { 829386e29065db5b05b57440f6b2a6dfa1e7f29a00dChris Lattner // If the CFG for the prior block has extra edges, remove them. 830386e29065db5b05b57440f6b2a6dfa1e7f29a00dChris Lattner MadeChange |= CorrectExtraCFGEdges(PrevBB, PriorTBB, PriorFBB, 831386e29065db5b05b57440f6b2a6dfa1e7f29a00dChris Lattner !PriorCond.empty(), MBB); 832386e29065db5b05b57440f6b2a6dfa1e7f29a00dChris Lattner 8337821a8afd3009c3c2760592e61de9e2c31c73e18Chris Lattner // If the previous branch is conditional and both conditions go to the same 8342d47bd937c13556ace07b2b2daf4dfe75f4e1e90Chris Lattner // destination, remove the branch, replacing it with an unconditional one or 8352d47bd937c13556ace07b2b2daf4dfe75f4e1e90Chris Lattner // a fall-through. 8367821a8afd3009c3c2760592e61de9e2c31c73e18Chris Lattner if (PriorTBB && PriorTBB == PriorFBB) { 837386e29065db5b05b57440f6b2a6dfa1e7f29a00dChris Lattner TII->RemoveBranch(PrevBB); 8387821a8afd3009c3c2760592e61de9e2c31c73e18Chris Lattner PriorCond.clear(); 8397d09784d3fc652131a2afbf06a0f2ed893837fb9Chris Lattner if (PriorTBB != MBB) 840386e29065db5b05b57440f6b2a6dfa1e7f29a00dChris Lattner TII->InsertBranch(PrevBB, PriorTBB, 0, PriorCond); 8417821a8afd3009c3c2760592e61de9e2c31c73e18Chris Lattner MadeChange = true; 84212143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner ++NumBranchOpts; 8437821a8afd3009c3c2760592e61de9e2c31c73e18Chris Lattner return OptimizeBlock(MBB); 8447821a8afd3009c3c2760592e61de9e2c31c73e18Chris Lattner } 8457821a8afd3009c3c2760592e61de9e2c31c73e18Chris Lattner 8467821a8afd3009c3c2760592e61de9e2c31c73e18Chris Lattner // If the previous branch *only* branches to *this* block (conditional or 8477821a8afd3009c3c2760592e61de9e2c31c73e18Chris Lattner // not) remove the branch. 8487d09784d3fc652131a2afbf06a0f2ed893837fb9Chris Lattner if (PriorTBB == MBB && PriorFBB == 0) { 849386e29065db5b05b57440f6b2a6dfa1e7f29a00dChris Lattner TII->RemoveBranch(PrevBB); 8507821a8afd3009c3c2760592e61de9e2c31c73e18Chris Lattner MadeChange = true; 85112143054aa6d120f029d268a5154bf2ecd0f707fChris Lattner ++NumBranchOpts; 8527821a8afd3009c3c2760592e61de9e2c31c73e18Chris Lattner return OptimizeBlock(MBB); 8537821a8afd3009c3c2760592e61de9e2c31c73e18Chris Lattner } 8542d47bd937c13556ace07b2b2daf4dfe75f4e1e90Chris Lattner 8552d47bd937c13556ace07b2b2daf4dfe75f4e1e90Chris Lattner // If the prior block branches somewhere else on the condition and here if 8562d47bd937c13556ace07b2b2daf4dfe75f4e1e90Chris Lattner // the condition is false, remove the uncond second branch. 8577d09784d3fc652131a2afbf06a0f2ed893837fb9Chris Lattner if (PriorFBB == MBB) { 8582d47bd937c13556ace07b2b2daf4dfe75f4e1e90Chris Lattner TII->RemoveBranch(PrevBB); 8592d47bd937c13556ace07b2b2daf4dfe75f4e1e90Chris Lattner TII->InsertBranch(PrevBB, PriorTBB, 0, PriorCond); 8602d47bd937c13556ace07b2b2daf4dfe75f4e1e90Chris Lattner MadeChange = true; 8612d47bd937c13556ace07b2b2daf4dfe75f4e1e90Chris Lattner ++NumBranchOpts; 8622d47bd937c13556ace07b2b2daf4dfe75f4e1e90Chris Lattner return OptimizeBlock(MBB); 8632d47bd937c13556ace07b2b2daf4dfe75f4e1e90Chris Lattner } 864a2d799531a748a349b9a458dbbc580b134074c49Chris Lattner 865a2d799531a748a349b9a458dbbc580b134074c49Chris Lattner // If the prior block branches here on true and somewhere else on false, and 866a2d799531a748a349b9a458dbbc580b134074c49Chris Lattner // if the branch condition is reversible, reverse the branch to create a 867a2d799531a748a349b9a458dbbc580b134074c49Chris Lattner // fall-through. 8687d09784d3fc652131a2afbf06a0f2ed893837fb9Chris Lattner if (PriorTBB == MBB) { 869a2d799531a748a349b9a458dbbc580b134074c49Chris Lattner std::vector<MachineOperand> NewPriorCond(PriorCond); 870a2d799531a748a349b9a458dbbc580b134074c49Chris Lattner if (!TII->ReverseBranchCondition(NewPriorCond)) { 871a2d799531a748a349b9a458dbbc580b134074c49Chris Lattner TII->RemoveBranch(PrevBB); 872a2d799531a748a349b9a458dbbc580b134074c49Chris Lattner TII->InsertBranch(PrevBB, PriorFBB, 0, NewPriorCond); 873a2d799531a748a349b9a458dbbc580b134074c49Chris Lattner MadeChange = true; 874a2d799531a748a349b9a458dbbc580b134074c49Chris Lattner ++NumBranchOpts; 875a2d799531a748a349b9a458dbbc580b134074c49Chris Lattner return OptimizeBlock(MBB); 876a2d799531a748a349b9a458dbbc580b134074c49Chris Lattner } 877a2d799531a748a349b9a458dbbc580b134074c49Chris Lattner } 878a7bef4a4e49f461984c04ef6be6eef3f1c023558Chris Lattner 879154e1047184384afd0a701a9f8816459cf0b3490Chris Lattner // If this block doesn't fall through (e.g. it ends with an uncond branch or 880154e1047184384afd0a701a9f8816459cf0b3490Chris Lattner // has no successors) and if the pred falls through into this block, and if 881154e1047184384afd0a701a9f8816459cf0b3490Chris Lattner // it would otherwise fall through into the block after this, move this 882154e1047184384afd0a701a9f8816459cf0b3490Chris Lattner // block to the end of the function. 883154e1047184384afd0a701a9f8816459cf0b3490Chris Lattner // 884a7bef4a4e49f461984c04ef6be6eef3f1c023558Chris Lattner // We consider it more likely that execution will stay in the function (e.g. 885a7bef4a4e49f461984c04ef6be6eef3f1c023558Chris Lattner // due to loops) than it is to exit it. This asserts in loops etc, moving 886a7bef4a4e49f461984c04ef6be6eef3f1c023558Chris Lattner // the assert condition out of the loop body. 887154e1047184384afd0a701a9f8816459cf0b3490Chris Lattner if (!PriorCond.empty() && PriorFBB == 0 && 888154e1047184384afd0a701a9f8816459cf0b3490Chris Lattner MachineFunction::iterator(PriorTBB) == FallThrough && 889154e1047184384afd0a701a9f8816459cf0b3490Chris Lattner !CanFallThrough(MBB)) { 890f10a56a86f8ae32d0493c7de770493d55519b073Chris Lattner bool DoTransform = true; 891f10a56a86f8ae32d0493c7de770493d55519b073Chris Lattner 892a7bef4a4e49f461984c04ef6be6eef3f1c023558Chris Lattner // We have to be careful that the succs of PredBB aren't both no-successor 893a7bef4a4e49f461984c04ef6be6eef3f1c023558Chris Lattner // blocks. If neither have successors and if PredBB is the second from 894a7bef4a4e49f461984c04ef6be6eef3f1c023558Chris Lattner // last block in the function, we'd just keep swapping the two blocks for 895a7bef4a4e49f461984c04ef6be6eef3f1c023558Chris Lattner // last. Only do the swap if one is clearly better to fall through than 896a7bef4a4e49f461984c04ef6be6eef3f1c023558Chris Lattner // the other. 897f10a56a86f8ae32d0493c7de770493d55519b073Chris Lattner if (FallThrough == --MBB->getParent()->end() && 898f10a56a86f8ae32d0493c7de770493d55519b073Chris Lattner !IsBetterFallthrough(PriorTBB, MBB, *TII)) 899f10a56a86f8ae32d0493c7de770493d55519b073Chris Lattner DoTransform = false; 900f10a56a86f8ae32d0493c7de770493d55519b073Chris Lattner 901f10a56a86f8ae32d0493c7de770493d55519b073Chris Lattner // We don't want to do this transformation if we have control flow like: 902f10a56a86f8ae32d0493c7de770493d55519b073Chris Lattner // br cond BB2 903f10a56a86f8ae32d0493c7de770493d55519b073Chris Lattner // BB1: 904f10a56a86f8ae32d0493c7de770493d55519b073Chris Lattner // .. 905f10a56a86f8ae32d0493c7de770493d55519b073Chris Lattner // jmp BBX 906f10a56a86f8ae32d0493c7de770493d55519b073Chris Lattner // BB2: 907f10a56a86f8ae32d0493c7de770493d55519b073Chris Lattner // .. 908f10a56a86f8ae32d0493c7de770493d55519b073Chris Lattner // ret 909f10a56a86f8ae32d0493c7de770493d55519b073Chris Lattner // 910f10a56a86f8ae32d0493c7de770493d55519b073Chris Lattner // In this case, we could actually be moving the return block *into* a 911f10a56a86f8ae32d0493c7de770493d55519b073Chris Lattner // loop! 9124b105912657c0472dc4f6f7244ce20bf7cf9a7dcChris Lattner if (DoTransform && !MBB->succ_empty() && 9134b105912657c0472dc4f6f7244ce20bf7cf9a7dcChris Lattner (!CanFallThrough(PriorTBB) || PriorTBB->empty())) 914f10a56a86f8ae32d0493c7de770493d55519b073Chris Lattner DoTransform = false; 915f10a56a86f8ae32d0493c7de770493d55519b073Chris Lattner 916a7bef4a4e49f461984c04ef6be6eef3f1c023558Chris Lattner 917f10a56a86f8ae32d0493c7de770493d55519b073Chris Lattner if (DoTransform) { 918a7bef4a4e49f461984c04ef6be6eef3f1c023558Chris Lattner // Reverse the branch so we will fall through on the previous true cond. 919a7bef4a4e49f461984c04ef6be6eef3f1c023558Chris Lattner std::vector<MachineOperand> NewPriorCond(PriorCond); 920a7bef4a4e49f461984c04ef6be6eef3f1c023558Chris Lattner if (!TII->ReverseBranchCondition(NewPriorCond)) { 921f10a56a86f8ae32d0493c7de770493d55519b073Chris Lattner DOUT << "\nMoving MBB: " << *MBB; 922f10a56a86f8ae32d0493c7de770493d55519b073Chris Lattner DOUT << "To make fallthrough to: " << *PriorTBB << "\n"; 923f10a56a86f8ae32d0493c7de770493d55519b073Chris Lattner 924a7bef4a4e49f461984c04ef6be6eef3f1c023558Chris Lattner TII->RemoveBranch(PrevBB); 925a7bef4a4e49f461984c04ef6be6eef3f1c023558Chris Lattner TII->InsertBranch(PrevBB, MBB, 0, NewPriorCond); 926a7bef4a4e49f461984c04ef6be6eef3f1c023558Chris Lattner 927a7bef4a4e49f461984c04ef6be6eef3f1c023558Chris Lattner // Move this block to the end of the function. 928a7bef4a4e49f461984c04ef6be6eef3f1c023558Chris Lattner MBB->moveAfter(--MBB->getParent()->end()); 929a7bef4a4e49f461984c04ef6be6eef3f1c023558Chris Lattner MadeChange = true; 930a7bef4a4e49f461984c04ef6be6eef3f1c023558Chris Lattner ++NumBranchOpts; 931a7bef4a4e49f461984c04ef6be6eef3f1c023558Chris Lattner return; 932a7bef4a4e49f461984c04ef6be6eef3f1c023558Chris Lattner } 933a7bef4a4e49f461984c04ef6be6eef3f1c023558Chris Lattner } 934a7bef4a4e49f461984c04ef6be6eef3f1c023558Chris Lattner } 9357821a8afd3009c3c2760592e61de9e2c31c73e18Chris Lattner } 9367821a8afd3009c3c2760592e61de9e2c31c73e18Chris Lattner 937386e29065db5b05b57440f6b2a6dfa1e7f29a00dChris Lattner // Analyze the branch in the current block. 938386e29065db5b05b57440f6b2a6dfa1e7f29a00dChris Lattner MachineBasicBlock *CurTBB = 0, *CurFBB = 0; 939386e29065db5b05b57440f6b2a6dfa1e7f29a00dChris Lattner std::vector<MachineOperand> CurCond; 9406b0e3f890779b7fc912bec8d40a9590e44742737Chris Lattner bool CurUnAnalyzable = TII->AnalyzeBranch(*MBB, CurTBB, CurFBB, CurCond); 9416b0e3f890779b7fc912bec8d40a9590e44742737Chris Lattner if (!CurUnAnalyzable) { 942386e29065db5b05b57440f6b2a6dfa1e7f29a00dChris Lattner // If the CFG for the prior block has extra edges, remove them. 943386e29065db5b05b57440f6b2a6dfa1e7f29a00dChris Lattner MadeChange |= CorrectExtraCFGEdges(*MBB, CurTBB, CurFBB, 9447d09784d3fc652131a2afbf06a0f2ed893837fb9Chris Lattner !CurCond.empty(), 9457d09784d3fc652131a2afbf06a0f2ed893837fb9Chris Lattner ++MachineFunction::iterator(MBB)); 946386e29065db5b05b57440f6b2a6dfa1e7f29a00dChris Lattner 9475d056952ba2f97729c5db69a3f14250595fa1ee8Chris Lattner // If this is a two-way branch, and the FBB branches to this block, reverse 9485d056952ba2f97729c5db69a3f14250595fa1ee8Chris Lattner // the condition so the single-basic-block loop is faster. Instead of: 9495d056952ba2f97729c5db69a3f14250595fa1ee8Chris Lattner // Loop: xxx; jcc Out; jmp Loop 9505d056952ba2f97729c5db69a3f14250595fa1ee8Chris Lattner // we want: 9515d056952ba2f97729c5db69a3f14250595fa1ee8Chris Lattner // Loop: xxx; jncc Loop; jmp Out 9525d056952ba2f97729c5db69a3f14250595fa1ee8Chris Lattner if (CurTBB && CurFBB && CurFBB == MBB && CurTBB != MBB) { 9535d056952ba2f97729c5db69a3f14250595fa1ee8Chris Lattner std::vector<MachineOperand> NewCond(CurCond); 9545d056952ba2f97729c5db69a3f14250595fa1ee8Chris Lattner if (!TII->ReverseBranchCondition(NewCond)) { 9555d056952ba2f97729c5db69a3f14250595fa1ee8Chris Lattner TII->RemoveBranch(*MBB); 9565d056952ba2f97729c5db69a3f14250595fa1ee8Chris Lattner TII->InsertBranch(*MBB, CurFBB, CurTBB, NewCond); 9575d056952ba2f97729c5db69a3f14250595fa1ee8Chris Lattner MadeChange = true; 9585d056952ba2f97729c5db69a3f14250595fa1ee8Chris Lattner ++NumBranchOpts; 9595d056952ba2f97729c5db69a3f14250595fa1ee8Chris Lattner return OptimizeBlock(MBB); 9605d056952ba2f97729c5db69a3f14250595fa1ee8Chris Lattner } 9615d056952ba2f97729c5db69a3f14250595fa1ee8Chris Lattner } 9625d056952ba2f97729c5db69a3f14250595fa1ee8Chris Lattner 9635d056952ba2f97729c5db69a3f14250595fa1ee8Chris Lattner 964386e29065db5b05b57440f6b2a6dfa1e7f29a00dChris Lattner // If this branch is the only thing in its block, see if we can forward 965386e29065db5b05b57440f6b2a6dfa1e7f29a00dChris Lattner // other blocks across it. 966386e29065db5b05b57440f6b2a6dfa1e7f29a00dChris Lattner if (CurTBB && CurCond.empty() && CurFBB == 0 && 9677d09784d3fc652131a2afbf06a0f2ed893837fb9Chris Lattner TII->isBranch(MBB->begin()->getOpcode()) && CurTBB != MBB) { 968386e29065db5b05b57440f6b2a6dfa1e7f29a00dChris Lattner // This block may contain just an unconditional branch. Because there can 969386e29065db5b05b57440f6b2a6dfa1e7f29a00dChris Lattner // be 'non-branch terminators' in the block, try removing the branch and 970386e29065db5b05b57440f6b2a6dfa1e7f29a00dChris Lattner // then seeing if the block is empty. 971386e29065db5b05b57440f6b2a6dfa1e7f29a00dChris Lattner TII->RemoveBranch(*MBB); 972386e29065db5b05b57440f6b2a6dfa1e7f29a00dChris Lattner 973386e29065db5b05b57440f6b2a6dfa1e7f29a00dChris Lattner // If this block is just an unconditional branch to CurTBB, we can 974386e29065db5b05b57440f6b2a6dfa1e7f29a00dChris Lattner // usually completely eliminate the block. The only case we cannot 975386e29065db5b05b57440f6b2a6dfa1e7f29a00dChris Lattner // completely eliminate the block is when the block before this one 976386e29065db5b05b57440f6b2a6dfa1e7f29a00dChris Lattner // falls through into MBB and we can't understand the prior block's branch 977386e29065db5b05b57440f6b2a6dfa1e7f29a00dChris Lattner // condition. 978cf420cca572b061fdd63587cb90904c641b6e216Chris Lattner if (MBB->empty()) { 979cf420cca572b061fdd63587cb90904c641b6e216Chris Lattner bool PredHasNoFallThrough = TII->BlockHasNoFallThrough(PrevBB); 980cf420cca572b061fdd63587cb90904c641b6e216Chris Lattner if (PredHasNoFallThrough || !PriorUnAnalyzable || 981cf420cca572b061fdd63587cb90904c641b6e216Chris Lattner !PrevBB.isSuccessor(MBB)) { 982cf420cca572b061fdd63587cb90904c641b6e216Chris Lattner // If the prior block falls through into us, turn it into an 983cf420cca572b061fdd63587cb90904c641b6e216Chris Lattner // explicit branch to us to make updates simpler. 984cf420cca572b061fdd63587cb90904c641b6e216Chris Lattner if (!PredHasNoFallThrough && PrevBB.isSuccessor(MBB) && 985cf420cca572b061fdd63587cb90904c641b6e216Chris Lattner PriorTBB != MBB && PriorFBB != MBB) { 986cf420cca572b061fdd63587cb90904c641b6e216Chris Lattner if (PriorTBB == 0) { 9876acfe12dd6d52c801f78c240528b7cb42fa91159Chris Lattner assert(PriorCond.empty() && PriorFBB == 0 && 9886acfe12dd6d52c801f78c240528b7cb42fa91159Chris Lattner "Bad branch analysis"); 989cf420cca572b061fdd63587cb90904c641b6e216Chris Lattner PriorTBB = MBB; 990cf420cca572b061fdd63587cb90904c641b6e216Chris Lattner } else { 991cf420cca572b061fdd63587cb90904c641b6e216Chris Lattner assert(PriorFBB == 0 && "Machine CFG out of date!"); 992cf420cca572b061fdd63587cb90904c641b6e216Chris Lattner PriorFBB = MBB; 993cf420cca572b061fdd63587cb90904c641b6e216Chris Lattner } 994cf420cca572b061fdd63587cb90904c641b6e216Chris Lattner TII->RemoveBranch(PrevBB); 995cf420cca572b061fdd63587cb90904c641b6e216Chris Lattner TII->InsertBranch(PrevBB, PriorTBB, PriorFBB, PriorCond); 996386e29065db5b05b57440f6b2a6dfa1e7f29a00dChris Lattner } 99721ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner 998cf420cca572b061fdd63587cb90904c641b6e216Chris Lattner // Iterate through all the predecessors, revectoring each in-turn. 999cf420cca572b061fdd63587cb90904c641b6e216Chris Lattner MachineBasicBlock::pred_iterator PI = MBB->pred_begin(); 1000cf420cca572b061fdd63587cb90904c641b6e216Chris Lattner bool DidChange = false; 1001cf420cca572b061fdd63587cb90904c641b6e216Chris Lattner bool HasBranchToSelf = false; 1002cf420cca572b061fdd63587cb90904c641b6e216Chris Lattner while (PI != MBB->pred_end()) { 1003cf420cca572b061fdd63587cb90904c641b6e216Chris Lattner if (*PI == MBB) { 1004cf420cca572b061fdd63587cb90904c641b6e216Chris Lattner // If this block has an uncond branch to itself, leave it. 1005cf420cca572b061fdd63587cb90904c641b6e216Chris Lattner ++PI; 1006cf420cca572b061fdd63587cb90904c641b6e216Chris Lattner HasBranchToSelf = true; 1007cf420cca572b061fdd63587cb90904c641b6e216Chris Lattner } else { 1008cf420cca572b061fdd63587cb90904c641b6e216Chris Lattner DidChange = true; 1009cf420cca572b061fdd63587cb90904c641b6e216Chris Lattner ReplaceUsesOfBlockWith(*PI, MBB, CurTBB, TII); 1010cf420cca572b061fdd63587cb90904c641b6e216Chris Lattner } 10114bc135e93beebdcb3b9c44745c5ccbc91199ac0bChris Lattner } 101221ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner 1013cf420cca572b061fdd63587cb90904c641b6e216Chris Lattner // Change any jumptables to go to the new MBB. 10146acfe12dd6d52c801f78c240528b7cb42fa91159Chris Lattner MBB->getParent()->getJumpTableInfo()-> 10156acfe12dd6d52c801f78c240528b7cb42fa91159Chris Lattner ReplaceMBBInJumpTables(MBB, CurTBB); 1016cf420cca572b061fdd63587cb90904c641b6e216Chris Lattner if (DidChange) { 1017cf420cca572b061fdd63587cb90904c641b6e216Chris Lattner ++NumBranchOpts; 1018cf420cca572b061fdd63587cb90904c641b6e216Chris Lattner MadeChange = true; 1019cf420cca572b061fdd63587cb90904c641b6e216Chris Lattner if (!HasBranchToSelf) return; 1020cf420cca572b061fdd63587cb90904c641b6e216Chris Lattner } 10214bc135e93beebdcb3b9c44745c5ccbc91199ac0bChris Lattner } 102221ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner } 1023386e29065db5b05b57440f6b2a6dfa1e7f29a00dChris Lattner 1024386e29065db5b05b57440f6b2a6dfa1e7f29a00dChris Lattner // Add the branch back if the block is more than just an uncond branch. 1025386e29065db5b05b57440f6b2a6dfa1e7f29a00dChris Lattner TII->InsertBranch(*MBB, CurTBB, 0, CurCond); 102621ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner } 10276b0e3f890779b7fc912bec8d40a9590e44742737Chris Lattner } 10286b0e3f890779b7fc912bec8d40a9590e44742737Chris Lattner 10296b0e3f890779b7fc912bec8d40a9590e44742737Chris Lattner // If the prior block doesn't fall through into this block, and if this 10306b0e3f890779b7fc912bec8d40a9590e44742737Chris Lattner // block doesn't fall through into some other block, see if we can find a 10316b0e3f890779b7fc912bec8d40a9590e44742737Chris Lattner // place to move this block where a fall-through will happen. 10326b0e3f890779b7fc912bec8d40a9590e44742737Chris Lattner if (!CanFallThrough(&PrevBB, PriorUnAnalyzable, 10336b0e3f890779b7fc912bec8d40a9590e44742737Chris Lattner PriorTBB, PriorFBB, PriorCond)) { 10346b0e3f890779b7fc912bec8d40a9590e44742737Chris Lattner // Now we know that there was no fall-through into this block, check to 10356b0e3f890779b7fc912bec8d40a9590e44742737Chris Lattner // see if it has a fall-through into its successor. 10366b896cec8b703e08e5f3d809e086a39b6ebe6589Dale Johannesen bool CurFallsThru = CanFallThrough(MBB, CurUnAnalyzable, CurTBB, CurFBB, 103777edc4b1b004726d96c932356750b9f3c96d74ddChris Lattner CurCond); 10386b896cec8b703e08e5f3d809e086a39b6ebe6589Dale Johannesen 103902b3f5ec4ac120d14a63f7fd4f4388b7d0ab6c22Jim Laskey if (!MBB->isLandingPad()) { 104002b3f5ec4ac120d14a63f7fd4f4388b7d0ab6c22Jim Laskey // Check all the predecessors of this block. If one of them has no fall 104102b3f5ec4ac120d14a63f7fd4f4388b7d0ab6c22Jim Laskey // throughs, move this block right after it. 104202b3f5ec4ac120d14a63f7fd4f4388b7d0ab6c22Jim Laskey for (MachineBasicBlock::pred_iterator PI = MBB->pred_begin(), 104302b3f5ec4ac120d14a63f7fd4f4388b7d0ab6c22Jim Laskey E = MBB->pred_end(); PI != E; ++PI) { 104402b3f5ec4ac120d14a63f7fd4f4388b7d0ab6c22Jim Laskey // Analyze the branch at the end of the pred. 104502b3f5ec4ac120d14a63f7fd4f4388b7d0ab6c22Jim Laskey MachineBasicBlock *PredBB = *PI; 104602b3f5ec4ac120d14a63f7fd4f4388b7d0ab6c22Jim Laskey MachineFunction::iterator PredFallthrough = PredBB; ++PredFallthrough; 104702b3f5ec4ac120d14a63f7fd4f4388b7d0ab6c22Jim Laskey if (PredBB != MBB && !CanFallThrough(PredBB) 104876b38fcabeba725e166a2ff72c56fe31d784b229Dale Johannesen && (!CurFallsThru || !CurTBB || !CurFBB) 104902b3f5ec4ac120d14a63f7fd4f4388b7d0ab6c22Jim Laskey && (!CurFallsThru || MBB->getNumber() >= PredBB->getNumber())) { 105002b3f5ec4ac120d14a63f7fd4f4388b7d0ab6c22Jim Laskey // If the current block doesn't fall through, just move it. 105102b3f5ec4ac120d14a63f7fd4f4388b7d0ab6c22Jim Laskey // If the current block can fall through and does not end with a 105202b3f5ec4ac120d14a63f7fd4f4388b7d0ab6c22Jim Laskey // conditional branch, we need to append an unconditional jump to 105302b3f5ec4ac120d14a63f7fd4f4388b7d0ab6c22Jim Laskey // the (current) next block. To avoid a possible compile-time 105402b3f5ec4ac120d14a63f7fd4f4388b7d0ab6c22Jim Laskey // infinite loop, move blocks only backward in this case. 105576b38fcabeba725e166a2ff72c56fe31d784b229Dale Johannesen // Also, if there are already 2 branches here, we cannot add a third; 105676b38fcabeba725e166a2ff72c56fe31d784b229Dale Johannesen // this means we have the case 105776b38fcabeba725e166a2ff72c56fe31d784b229Dale Johannesen // Bcc next 105876b38fcabeba725e166a2ff72c56fe31d784b229Dale Johannesen // B elsewhere 105976b38fcabeba725e166a2ff72c56fe31d784b229Dale Johannesen // next: 106002b3f5ec4ac120d14a63f7fd4f4388b7d0ab6c22Jim Laskey if (CurFallsThru) { 106102b3f5ec4ac120d14a63f7fd4f4388b7d0ab6c22Jim Laskey MachineBasicBlock *NextBB = next(MachineFunction::iterator(MBB)); 106202b3f5ec4ac120d14a63f7fd4f4388b7d0ab6c22Jim Laskey CurCond.clear(); 106302b3f5ec4ac120d14a63f7fd4f4388b7d0ab6c22Jim Laskey TII->InsertBranch(*MBB, NextBB, 0, CurCond); 106402b3f5ec4ac120d14a63f7fd4f4388b7d0ab6c22Jim Laskey } 106502b3f5ec4ac120d14a63f7fd4f4388b7d0ab6c22Jim Laskey MBB->moveAfter(PredBB); 106602b3f5ec4ac120d14a63f7fd4f4388b7d0ab6c22Jim Laskey MadeChange = true; 106702b3f5ec4ac120d14a63f7fd4f4388b7d0ab6c22Jim Laskey return OptimizeBlock(MBB); 10687d09784d3fc652131a2afbf06a0f2ed893837fb9Chris Lattner } 10696b0e3f890779b7fc912bec8d40a9590e44742737Chris Lattner } 10706b896cec8b703e08e5f3d809e086a39b6ebe6589Dale Johannesen } 10717d09784d3fc652131a2afbf06a0f2ed893837fb9Chris Lattner 10726b896cec8b703e08e5f3d809e086a39b6ebe6589Dale Johannesen if (!CurFallsThru) { 10736b0e3f890779b7fc912bec8d40a9590e44742737Chris Lattner // Check all successors to see if we can move this block before it. 10746b0e3f890779b7fc912bec8d40a9590e44742737Chris Lattner for (MachineBasicBlock::succ_iterator SI = MBB->succ_begin(), 10756b0e3f890779b7fc912bec8d40a9590e44742737Chris Lattner E = MBB->succ_end(); SI != E; ++SI) { 10766b0e3f890779b7fc912bec8d40a9590e44742737Chris Lattner // Analyze the branch at the end of the block before the succ. 10776b0e3f890779b7fc912bec8d40a9590e44742737Chris Lattner MachineBasicBlock *SuccBB = *SI; 10786b0e3f890779b7fc912bec8d40a9590e44742737Chris Lattner MachineFunction::iterator SuccPrev = SuccBB; --SuccPrev; 10796b0e3f890779b7fc912bec8d40a9590e44742737Chris Lattner std::vector<MachineOperand> SuccPrevCond; 108077edc4b1b004726d96c932356750b9f3c96d74ddChris Lattner 108177edc4b1b004726d96c932356750b9f3c96d74ddChris Lattner // If this block doesn't already fall-through to that successor, and if 108277edc4b1b004726d96c932356750b9f3c96d74ddChris Lattner // the succ doesn't already have a block that can fall through into it, 108377edc4b1b004726d96c932356750b9f3c96d74ddChris Lattner // and if the successor isn't an EH destination, we can arrange for the 108477edc4b1b004726d96c932356750b9f3c96d74ddChris Lattner // fallthrough to happen. 108577edc4b1b004726d96c932356750b9f3c96d74ddChris Lattner if (SuccBB != MBB && !CanFallThrough(SuccPrev) && 108677edc4b1b004726d96c932356750b9f3c96d74ddChris Lattner !SuccBB->isLandingPad()) { 10876b0e3f890779b7fc912bec8d40a9590e44742737Chris Lattner MBB->moveBefore(SuccBB); 10887d09784d3fc652131a2afbf06a0f2ed893837fb9Chris Lattner MadeChange = true; 10896b0e3f890779b7fc912bec8d40a9590e44742737Chris Lattner return OptimizeBlock(MBB); 10907d09784d3fc652131a2afbf06a0f2ed893837fb9Chris Lattner } 10917d09784d3fc652131a2afbf06a0f2ed893837fb9Chris Lattner } 10926b0e3f890779b7fc912bec8d40a9590e44742737Chris Lattner 10936b0e3f890779b7fc912bec8d40a9590e44742737Chris Lattner // Okay, there is no really great place to put this block. If, however, 10946b0e3f890779b7fc912bec8d40a9590e44742737Chris Lattner // the block before this one would be a fall-through if this block were 10956b0e3f890779b7fc912bec8d40a9590e44742737Chris Lattner // removed, move this block to the end of the function. 10966b0e3f890779b7fc912bec8d40a9590e44742737Chris Lattner if (FallThrough != MBB->getParent()->end() && 10976b0e3f890779b7fc912bec8d40a9590e44742737Chris Lattner PrevBB.isSuccessor(FallThrough)) { 10986b0e3f890779b7fc912bec8d40a9590e44742737Chris Lattner MBB->moveAfter(--MBB->getParent()->end()); 10996b0e3f890779b7fc912bec8d40a9590e44742737Chris Lattner MadeChange = true; 11006b0e3f890779b7fc912bec8d40a9590e44742737Chris Lattner return; 11016b0e3f890779b7fc912bec8d40a9590e44742737Chris Lattner } 11027d09784d3fc652131a2afbf06a0f2ed893837fb9Chris Lattner } 110321ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner } 110421ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner} 1105