BranchFolding.cpp revision 794fd75c67a2cdc128d67342c6d88a504d186896
15821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)//===-- BranchFolding.cpp - Fold machine code branch instructions ---------===// 25821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// 35821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// The LLVM Compiler Infrastructure 45821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// 55821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// This file was developed by the LLVM research group and is distributed under 65821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// the University of Illinois Open Source License. See LICENSE.TXT for details. 75821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// 85821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)//===----------------------------------------------------------------------===// 95821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// 105821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// This pass forwards branches to unconditional branches to make them branch 115821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// directly to the target block. This pass often results in dead MBB's, which 125821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// it then removes. 135821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// 145821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// Note that this pass must be run after register allocation, it cannot handle 155821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// SSA form. 165821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// 175821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)//===----------------------------------------------------------------------===// 185821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 195821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#define DEBUG_TYPE "branchfolding" 205821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include "llvm/CodeGen/Passes.h" 215821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include "llvm/CodeGen/MachineModuleInfo.h" 225821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include "llvm/CodeGen/MachineFunctionPass.h" 235821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include "llvm/CodeGen/MachineJumpTableInfo.h" 245821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include "llvm/CodeGen/RegisterScavenging.h" 255821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include "llvm/Target/TargetInstrInfo.h" 265821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include "llvm/Target/TargetMachine.h" 275821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include "llvm/Target/MRegisterInfo.h" 285821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include "llvm/Support/CommandLine.h" 295821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include "llvm/Support/Debug.h" 305821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include "llvm/ADT/Statistic.h" 315821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include "llvm/ADT/STLExtras.h" 325821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include <algorithm> 335821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)using namespace llvm; 345821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 355821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)STATISTIC(NumDeadBlocks, "Number of dead blocks removed"); 365821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)STATISTIC(NumBranchOpts, "Number of branches optimized"); 375821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)STATISTIC(NumTailMerge , "Number of block tails merged"); 385821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)static cl::opt<bool> EnableTailMerge("enable-tail-merge", cl::Hidden); 395821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 405821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)namespace { 415821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) struct BranchFolder : public MachineFunctionPass { 425821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) static const int ID; 435821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) BranchFolder() : MachineFunctionPass((intptr_t)&ID) {} 445821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 455821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) virtual bool runOnMachineFunction(MachineFunction &MF); 465821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) virtual const char *getPassName() const { return "Control Flow Optimizer"; } 475821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const TargetInstrInfo *TII; 485821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) MachineModuleInfo *MMI; 495821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) bool MadeChange; 505821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) private: 515821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Tail Merging. 525821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) bool TailMergeBlocks(MachineFunction &MF); 535821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) void ReplaceTailWithBranchTo(MachineBasicBlock::iterator OldInst, 545821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) MachineBasicBlock *NewDest); 555821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) MachineBasicBlock *SplitMBBAt(MachineBasicBlock &CurMBB, 565821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) MachineBasicBlock::iterator BBI1); 575821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 585821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const MRegisterInfo *RegInfo; 595821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) RegScavenger *RS; 605821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Branch optzn. 615821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) bool OptimizeBranches(MachineFunction &MF); 625821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) void OptimizeBlock(MachineBasicBlock *MBB); 635821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) void RemoveDeadBlock(MachineBasicBlock *MBB); 645821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 655821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) bool CanFallThrough(MachineBasicBlock *CurBB); 665821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) bool CanFallThrough(MachineBasicBlock *CurBB, bool BranchUnAnalyzable, 675821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) MachineBasicBlock *TBB, MachineBasicBlock *FBB, 685821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const std::vector<MachineOperand> &Cond); 695821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) }; 705821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const int BranchFolder::ID = 0; 715821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 725821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 735821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)FunctionPass *llvm::createBranchFoldingPass() { return new BranchFolder(); } 745821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 755821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)/// RemoveDeadBlock - Remove the specified dead machine basic block from the 765821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)/// function, updating the CFG. 775821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)void BranchFolder::RemoveDeadBlock(MachineBasicBlock *MBB) { 785821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) assert(MBB->pred_empty() && "MBB must be dead!"); 795821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) DOUT << "\nRemoving MBB: " << *MBB; 805821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 815821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) MachineFunction *MF = MBB->getParent(); 825821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // drop all successors. 835821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) while (!MBB->succ_empty()) 845821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) MBB->removeSuccessor(MBB->succ_end()-1); 855821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 865821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // If there is DWARF info to active, check to see if there are any LABEL 875821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // records in the basic block. If so, unregister them from MachineModuleInfo. 885821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (MMI && !MBB->empty()) { 895821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) for (MachineBasicBlock::iterator I = MBB->begin(), E = MBB->end(); 905821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) I != E; ++I) { 915821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if ((unsigned)I->getOpcode() == TargetInstrInfo::LABEL) { 925821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // The label ID # is always operand #0, an immediate. 935821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) MMI->InvalidateLabel(I->getOperand(0).getImm()); 945821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 955821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 965821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 975821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 985821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Remove the block. 995821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) MF->getBasicBlockList().erase(MBB); 1005821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 1015821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1025821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)bool BranchFolder::runOnMachineFunction(MachineFunction &MF) { 1035821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) TII = MF.getTarget().getInstrInfo(); 1045821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (!TII) return false; 1055821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1065821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) RegInfo = MF.getTarget().getRegisterInfo(); 1075821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) RS = RegInfo->requiresRegisterScavenging(MF) ? new RegScavenger() : NULL; 1085821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1095821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) MMI = getAnalysisToUpdate<MachineModuleInfo>(); 1105821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1115821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) bool EverMadeChange = false; 1125821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) bool MadeChangeThisIteration = true; 1135821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) while (MadeChangeThisIteration) { 1145821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) MadeChangeThisIteration = false; 1155821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) MadeChangeThisIteration |= TailMergeBlocks(MF); 1165821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) MadeChangeThisIteration |= OptimizeBranches(MF); 1175821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) EverMadeChange |= MadeChangeThisIteration; 1185821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 1195821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1205821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // See if any jump tables have become mergable or dead as the code generator 1215821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // did its thing. 1225821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) MachineJumpTableInfo *JTI = MF.getJumpTableInfo(); 1235821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const std::vector<MachineJumpTableEntry> &JTs = JTI->getJumpTables(); 1245821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (!JTs.empty()) { 1255821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Figure out how these jump tables should be merged. 1265821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) std::vector<unsigned> JTMapping; 1275821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) JTMapping.reserve(JTs.size()); 1285821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1295821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // We always keep the 0th jump table. 1305821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) JTMapping.push_back(0); 1315821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1325821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Scan the jump tables, seeing if there are any duplicates. Note that this 1335821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // is N^2, which should be fixed someday. 1345821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) for (unsigned i = 1, e = JTs.size(); i != e; ++i) 1355821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) JTMapping.push_back(JTI->getJumpTableIndex(JTs[i].MBBs)); 1365821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1375821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // If a jump table was merge with another one, walk the function rewriting 1385821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // references to jump tables to reference the new JT ID's. Keep track of 1395821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // whether we see a jump table idx, if not, we can delete the JT. 1405821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) std::vector<bool> JTIsLive; 1415821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) JTIsLive.resize(JTs.size()); 1425821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) for (MachineFunction::iterator BB = MF.begin(), E = MF.end(); 1435821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) BB != E; ++BB) { 1445821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) for (MachineBasicBlock::iterator I = BB->begin(), E = BB->end(); 1455821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) I != E; ++I) 1465821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) for (unsigned op = 0, e = I->getNumOperands(); op != e; ++op) { 1475821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) MachineOperand &Op = I->getOperand(op); 1485821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (!Op.isJumpTableIndex()) continue; 1495821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) unsigned NewIdx = JTMapping[Op.getJumpTableIndex()]; 1505821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Op.setJumpTableIndex(NewIdx); 1515821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1525821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Remember that this JT is live. 1535821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) JTIsLive[NewIdx] = true; 1545821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 1555821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 1565821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1575821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Finally, remove dead jump tables. This happens either because the 1585821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // indirect jump was unreachable (and thus deleted) or because the jump 1595821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // table was merged with some other one. 1605821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) for (unsigned i = 0, e = JTIsLive.size(); i != e; ++i) 1615821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (!JTIsLive[i]) { 1625821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) JTI->RemoveJumpTable(i); 1635821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) EverMadeChange = true; 1645821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 1655821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 1665821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1675821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) delete RS; 1685821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return EverMadeChange; 1695821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 1705821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1715821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)//===----------------------------------------------------------------------===// 1725821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// Tail Merging of Blocks 1735821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)//===----------------------------------------------------------------------===// 1745821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1755821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)/// HashMachineInstr - Compute a hash value for MI and its operands. 1765821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)static unsigned HashMachineInstr(const MachineInstr *MI) { 1775821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) unsigned Hash = MI->getOpcode(); 1785821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 1795821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const MachineOperand &Op = MI->getOperand(i); 1805821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1815821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Merge in bits from the operand if easy. 1825821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) unsigned OperandHash = 0; 1835821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) switch (Op.getType()) { 1845821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) case MachineOperand::MO_Register: OperandHash = Op.getReg(); break; 1855821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) case MachineOperand::MO_Immediate: OperandHash = Op.getImm(); break; 1865821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) case MachineOperand::MO_MachineBasicBlock: 1875821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) OperandHash = Op.getMachineBasicBlock()->getNumber(); 1885821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) break; 1895821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) case MachineOperand::MO_FrameIndex: OperandHash = Op.getFrameIndex(); break; 1905821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) case MachineOperand::MO_ConstantPoolIndex: 1915821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) OperandHash = Op.getConstantPoolIndex(); 1925821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) break; 1935821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) case MachineOperand::MO_JumpTableIndex: 1945821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) OperandHash = Op.getJumpTableIndex(); 1955821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) break; 1965821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) case MachineOperand::MO_GlobalAddress: 1975821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) case MachineOperand::MO_ExternalSymbol: 1985821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Global address / external symbol are too hard, don't bother, but do 1995821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // pull in the offset. 2005821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) OperandHash = Op.getOffset(); 2015821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) break; 2025821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) default: break; 2035821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 2045821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2055821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Hash += ((OperandHash << 3) | Op.getType()) << (i&31); 2065821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 2075821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return Hash; 2085821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 2095821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2105821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)/// HashEndOfMBB - Hash the last two instructions in the MBB. We hash two 2115821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)/// instructions, because cross-jumping only saves code when at least two 2125821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)/// instructions are removed (since a branch must be inserted). 2135821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)static unsigned HashEndOfMBB(const MachineBasicBlock *MBB) { 2145821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) MachineBasicBlock::const_iterator I = MBB->end(); 2155821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (I == MBB->begin()) 2165821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return 0; // Empty MBB. 2175821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2185821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) --I; 2195821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) unsigned Hash = HashMachineInstr(I); 2205821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2215821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (I == MBB->begin()) 2225821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return Hash; // Single instr MBB. 2235821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2245821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) --I; 2255821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Hash in the second-to-last instruction. 2265821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Hash ^= HashMachineInstr(I) << 2; 2275821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return Hash; 2285821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 2295821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2305821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)/// ComputeCommonTailLength - Given two machine basic blocks, compute the number 2315821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)/// of instructions they actually have in common together at their end. Return 2325821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)/// iterators for the first shared instruction in each block. 2335821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)static unsigned ComputeCommonTailLength(MachineBasicBlock *MBB1, 2345821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) MachineBasicBlock *MBB2, 2355821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) MachineBasicBlock::iterator &I1, 2365821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) MachineBasicBlock::iterator &I2) { 2375821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) I1 = MBB1->end(); 2385821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) I2 = MBB2->end(); 2395821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2405821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) unsigned TailLen = 0; 2415821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) while (I1 != MBB1->begin() && I2 != MBB2->begin()) { 2425821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) --I1; --I2; 2435821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (!I1->isIdenticalTo(I2)) { 2445821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ++I1; ++I2; 2455821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) break; 2465821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 2475821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ++TailLen; 2485821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 2495821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return TailLen; 2505821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 2515821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2525821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)/// ReplaceTailWithBranchTo - Delete the instruction OldInst and everything 2535821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)/// after it, replacing it with an unconditional branch to NewDest. This 2545821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)/// returns true if OldInst's block is modified, false if NewDest is modified. 2555821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)void BranchFolder::ReplaceTailWithBranchTo(MachineBasicBlock::iterator OldInst, 2565821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) MachineBasicBlock *NewDest) { 2575821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) MachineBasicBlock *OldBB = OldInst->getParent(); 2585821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2595821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Remove all the old successors of OldBB from the CFG. 2605821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) while (!OldBB->succ_empty()) 2615821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) OldBB->removeSuccessor(OldBB->succ_begin()); 2625821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2635821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Remove all the dead instructions from the end of OldBB. 2645821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) OldBB->erase(OldInst, OldBB->end()); 2655821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2665821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // If OldBB isn't immediately before OldBB, insert a branch to it. 2675821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (++MachineFunction::iterator(OldBB) != MachineFunction::iterator(NewDest)) 2685821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) TII->InsertBranch(*OldBB, NewDest, 0, std::vector<MachineOperand>()); 2695821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) OldBB->addSuccessor(NewDest); 2705821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ++NumTailMerge; 2715821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 2725821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2735821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)/// SplitMBBAt - Given a machine basic block and an iterator into it, split the 2745821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)/// MBB so that the part before the iterator falls into the part starting at the 2755821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)/// iterator. This returns the new MBB. 2765821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)MachineBasicBlock *BranchFolder::SplitMBBAt(MachineBasicBlock &CurMBB, 2775821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) MachineBasicBlock::iterator BBI1) { 2785821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Create the fall-through block. 2795821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) MachineFunction::iterator MBBI = &CurMBB; 2805821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) MachineBasicBlock *NewMBB = new MachineBasicBlock(CurMBB.getBasicBlock()); 2815821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) CurMBB.getParent()->getBasicBlockList().insert(++MBBI, NewMBB); 2825821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2835821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Move all the successors of this block to the specified block. 2845821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) while (!CurMBB.succ_empty()) { 2855821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) MachineBasicBlock *S = *(CurMBB.succ_end()-1); 2865821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) NewMBB->addSuccessor(S); 2875821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) CurMBB.removeSuccessor(S); 2885821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 2895821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2905821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Add an edge from CurMBB to NewMBB for the fall-through. 2915821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) CurMBB.addSuccessor(NewMBB); 2925821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2935821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Splice the code over. 2945821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) NewMBB->splice(NewMBB->end(), &CurMBB, BBI1, CurMBB.end()); 2955821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2965821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // For targets that use the register scavenger, we must maintain LiveIns. 2975821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (RS) { 2985821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) RS->enterBasicBlock(&CurMBB); 2995821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (!CurMBB.empty()) 3005821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) RS->forward(prior(CurMBB.end())); 3015821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) BitVector RegsLiveAtExit(RegInfo->getNumRegs()); 3025821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) RS->getRegsUsed(RegsLiveAtExit, false); 3035821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) for (unsigned int i=0, e=RegInfo->getNumRegs(); i!=e; i++) 3045821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (RegsLiveAtExit[i]) 3055821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) NewMBB->addLiveIn(i); 3065821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 3075821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 3085821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return NewMBB; 3095821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 3105821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 3115821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)/// EstimateRuntime - Make a rough estimate for how long it will take to run 3125821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)/// the specified code. 3135821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)static unsigned EstimateRuntime(MachineBasicBlock::iterator I, 3145821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) MachineBasicBlock::iterator E, 3155821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const TargetInstrInfo *TII) { 3165821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) unsigned Time = 0; 3175821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) for (; I != E; ++I) { 3185821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const TargetInstrDescriptor &TID = TII->get(I->getOpcode()); 3195821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (TID.Flags & M_CALL_FLAG) 3205821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Time += 10; 3215821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) else if (TID.Flags & (M_LOAD_FLAG|M_STORE_FLAG)) 3225821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Time += 2; 3235821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) else 3245821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ++Time; 3255821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 3265821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return Time; 3275821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 3285821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 3295821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)/// ShouldSplitFirstBlock - We need to either split MBB1 at MBB1I or MBB2 at 3305821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)/// MBB2I and then insert an unconditional branch in the other block. Determine 3315821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)/// which is the best to split 3325821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)static bool ShouldSplitFirstBlock(MachineBasicBlock *MBB1, 3335821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) MachineBasicBlock::iterator MBB1I, 3345821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) MachineBasicBlock *MBB2, 3355821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) MachineBasicBlock::iterator MBB2I, 3365821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const TargetInstrInfo *TII) { 3375821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // TODO: if we had some notion of which block was hotter, we could split 3385821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // the hot block, so it is the fall-through. Since we don't have profile info 3395821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // make a decision based on which will hurt most to split. 3405821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) unsigned MBB1Time = EstimateRuntime(MBB1->begin(), MBB1I, TII); 3415821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) unsigned MBB2Time = EstimateRuntime(MBB2->begin(), MBB2I, TII); 3425821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 3435821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // If the MBB1 prefix takes "less time" to run than the MBB2 prefix, split the 3445821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // MBB1 block so it falls through. This will penalize the MBB2 path, but will 3455821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // have a lower overall impact on the program execution. 3465821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return MBB1Time < MBB2Time; 3475821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 3485821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 3495821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)bool BranchFolder::TailMergeBlocks(MachineFunction &MF) { 3505821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) MadeChange = false; 3515821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 3525821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (!EnableTailMerge) return false; 3535821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 3545821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Find blocks with no successors. 3555821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) std::vector<std::pair<unsigned,MachineBasicBlock*> > MergePotentials; 3565821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) for (MachineFunction::iterator I = MF.begin(), E = MF.end(); I != E; ++I) { 3575821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (I->succ_empty()) 3585821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) MergePotentials.push_back(std::make_pair(HashEndOfMBB(I), I)); 3595821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 3605821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 3615821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Sort by hash value so that blocks with identical end sequences sort 3625821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // together. 3635821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) std::stable_sort(MergePotentials.begin(), MergePotentials.end()); 3645821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 3655821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Walk through equivalence sets looking for actual exact matches. 3665821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) while (MergePotentials.size() > 1) { 3675821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) unsigned CurHash = (MergePotentials.end()-1)->first; 3685821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) unsigned PrevHash = (MergePotentials.end()-2)->first; 3695821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) MachineBasicBlock *CurMBB = (MergePotentials.end()-1)->second; 3705821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 3715821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // If there is nothing that matches the hash of the current basic block, 3725821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // give up. 3735821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (CurHash != PrevHash) { 3745821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) MergePotentials.pop_back(); 3755821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) continue; 3765821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 3775821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 3785821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Determine the actual length of the shared tail between these two basic 3795821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // blocks. Because the hash can have collisions, it's possible that this is 3805821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // less than 2. 3815821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) MachineBasicBlock::iterator BBI1, BBI2; 3825821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) unsigned CommonTailLen = 3835821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ComputeCommonTailLength(CurMBB, (MergePotentials.end()-2)->second, 3845821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) BBI1, BBI2); 3855821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 3865821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // If the tails don't have at least two instructions in common, see if there 3875821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // is anything else in the equivalence class that does match. 3885821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (CommonTailLen < 2) { 3895821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) unsigned FoundMatch = ~0U; 3905821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) for (int i = MergePotentials.size()-2; 3915821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) i != -1 && MergePotentials[i].first == CurHash; --i) { 3925821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) CommonTailLen = ComputeCommonTailLength(CurMBB, 3935821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) MergePotentials[i].second, 3945821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) BBI1, BBI2); 3955821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (CommonTailLen >= 2) { 3965821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) FoundMatch = i; 3975821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) break; 3985821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 3995821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 4005821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 4015821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // If we didn't find anything that has at least two instructions matching 4025821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // this one, bail out. 4035821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (FoundMatch == ~0U) { 4045821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) MergePotentials.pop_back(); 4055821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) continue; 4065821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 4075821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 4085821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Otherwise, move the matching block to the right position. 4095821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) std::swap(MergePotentials[FoundMatch], *(MergePotentials.end()-2)); 4105821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 4115821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 4125821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) MachineBasicBlock *MBB2 = (MergePotentials.end()-2)->second; 4135821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 4145821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // If neither block is the entire common tail, split the tail of one block 4155821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // to make it redundant with the other tail. 4165821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (CurMBB->begin() != BBI1 && MBB2->begin() != BBI2) { 4175821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (0) { // Enable this to disable partial tail merges. 4185821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) MergePotentials.pop_back(); 4195821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) continue; 4205821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 4215821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 4225821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Decide whether we want to split CurMBB or MBB2. 4235821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (ShouldSplitFirstBlock(CurMBB, BBI1, MBB2, BBI2, TII)) { 4245821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) CurMBB = SplitMBBAt(*CurMBB, BBI1); 4255821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) BBI1 = CurMBB->begin(); 4265821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) MergePotentials.back().second = CurMBB; 4275821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } else { 4285821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) MBB2 = SplitMBBAt(*MBB2, BBI2); 4295821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) BBI2 = MBB2->begin(); 4305821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) (MergePotentials.end()-2)->second = MBB2; 4315821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 4325821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 4335821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 4345821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (MBB2->begin() == BBI2) { 4355821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Hack the end off CurMBB, making it jump to MBBI@ instead. 4365821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ReplaceTailWithBranchTo(BBI1, MBB2); 4375821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // This modifies CurMBB, so remove it from the worklist. 4385821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) MergePotentials.pop_back(); 4395821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } else { 4405821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) assert(CurMBB->begin() == BBI1 && "Didn't split block correctly?"); 4415821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Hack the end off MBB2, making it jump to CurMBB instead. 4425821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ReplaceTailWithBranchTo(BBI2, CurMBB); 4435821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // This modifies MBB2, so remove it from the worklist. 4445821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) MergePotentials.erase(MergePotentials.end()-2); 4455821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 4465821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) MadeChange = true; 4475821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 4485821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 4495821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return MadeChange; 4505821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 4515821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 4525821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 4535821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)//===----------------------------------------------------------------------===// 4545821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// Branch Optimization 4555821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)//===----------------------------------------------------------------------===// 4565821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 4575821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)bool BranchFolder::OptimizeBranches(MachineFunction &MF) { 4585821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) MadeChange = false; 4595821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 4605821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Make sure blocks are numbered in order 4615821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) MF.RenumberBlocks(); 4625821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 4635821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) for (MachineFunction::iterator I = ++MF.begin(), E = MF.end(); I != E; ) { 4645821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) MachineBasicBlock *MBB = I++; 4655821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) OptimizeBlock(MBB); 4665821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 4675821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // If it is dead, remove it. 4685821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (MBB->pred_empty()) { 4695821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) RemoveDeadBlock(MBB); 4705821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) MadeChange = true; 4715821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ++NumDeadBlocks; 4725821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 4735821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 4745821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return MadeChange; 4755821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 4765821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 4775821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 4785821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)/// CorrectExtraCFGEdges - Various pieces of code can cause excess edges in the 4795821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)/// CFG to be inserted. If we have proven that MBB can only branch to DestA and 4805821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)/// DestB, remove any other MBB successors from the CFG. DestA and DestB can 4815821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)/// be null. 4825821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)static bool CorrectExtraCFGEdges(MachineBasicBlock &MBB, 4835821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) MachineBasicBlock *DestA, 4845821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) MachineBasicBlock *DestB, 4855821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) bool isCond, 4865821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) MachineFunction::iterator FallThru) { 4875821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) bool MadeChange = false; 4885821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) bool AddedFallThrough = false; 4895821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 4905821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // If this block ends with a conditional branch that falls through to its 4915821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // successor, set DestB as the successor. 4925821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (isCond) { 4935821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (DestB == 0 && FallThru != MBB.getParent()->end()) { 4945821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) DestB = FallThru; 4955821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) AddedFallThrough = true; 4965821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 4975821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } else { 4985821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // If this is an unconditional branch with no explicit dest, it must just be 4995821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // a fallthrough into DestB. 5005821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (DestA == 0 && FallThru != MBB.getParent()->end()) { 5015821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) DestA = FallThru; 5025821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) AddedFallThrough = true; 5035821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 5045821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 5055821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 5065821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) MachineBasicBlock::pred_iterator SI = MBB.succ_begin(); 5075821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) while (SI != MBB.succ_end()) { 5085821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (*SI == DestA) { 5095821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) DestA = 0; 5105821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ++SI; 5115821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } else if (*SI == DestB) { 5125821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) DestB = 0; 5135821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ++SI; 5145821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } else if ((*SI)->isLandingPad()) { 5155821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ++SI; 5165821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } else { 5175821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Otherwise, this is a superfluous edge, remove it. 5185821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) MBB.removeSuccessor(SI); 5195821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) MadeChange = true; 5205821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 5215821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 5225821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (!AddedFallThrough) { 5235821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) assert(DestA == 0 && DestB == 0 && 5245821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) "MachineCFG is missing edges!"); 5255821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } else if (isCond) { 5265821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) assert(DestA == 0 && "MachineCFG is missing edges!"); 5275821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 5285821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return MadeChange; 5295821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 5305821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 5315821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 5325821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)/// ReplaceUsesOfBlockWith - Given a machine basic block 'BB' that branched to 5335821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)/// 'Old', change the code and CFG so that it branches to 'New' instead. 5345821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)static void ReplaceUsesOfBlockWith(MachineBasicBlock *BB, 5355821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) MachineBasicBlock *Old, 5365821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) MachineBasicBlock *New, 5375821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const TargetInstrInfo *TII) { 5385821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) assert(Old != New && "Cannot replace self with self!"); 5395821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 5405821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) MachineBasicBlock::iterator I = BB->end(); 5415821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) while (I != BB->begin()) { 5425821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) --I; 5435821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (!TII->isTerminatorInstr(I->getOpcode())) break; 5445821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 5455821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Scan the operands of this machine instruction, replacing any uses of Old 5465821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // with New. 5475821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i) 5485821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (I->getOperand(i).isMachineBasicBlock() && 5495821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) I->getOperand(i).getMachineBasicBlock() == Old) 5505821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) I->getOperand(i).setMachineBasicBlock(New); 5515821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 5525821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 5535821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Update the successor information. 5545821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) std::vector<MachineBasicBlock*> Succs(BB->succ_begin(), BB->succ_end()); 5555821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) for (int i = Succs.size()-1; i >= 0; --i) 5565821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (Succs[i] == Old) { 5575821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) BB->removeSuccessor(Old); 5585821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) BB->addSuccessor(New); 5595821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 5605821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 5615821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 5625821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)/// CanFallThrough - Return true if the specified block (with the specified 5635821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)/// branch condition) can implicitly transfer control to the block after it by 5645821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)/// falling off the end of it. This should return false if it can reach the 5655821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)/// block after it, but it uses an explicit branch to do so (e.g. a table jump). 5665821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)/// 5675821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)/// True is a conservative answer. 5685821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)/// 5695821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)bool BranchFolder::CanFallThrough(MachineBasicBlock *CurBB, 5705821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) bool BranchUnAnalyzable, 5715821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) MachineBasicBlock *TBB, MachineBasicBlock *FBB, 5725821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const std::vector<MachineOperand> &Cond) { 5735821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) MachineFunction::iterator Fallthrough = CurBB; 5745821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ++Fallthrough; 5755821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // If FallthroughBlock is off the end of the function, it can't fall through. 5765821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (Fallthrough == CurBB->getParent()->end()) 5775821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return false; 5785821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 5795821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // If FallthroughBlock isn't a successor of CurBB, no fallthrough is possible. 5805821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (!CurBB->isSuccessor(Fallthrough)) 5815821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return false; 5825821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 5835821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // If we couldn't analyze the branch, assume it could fall through. 5845821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (BranchUnAnalyzable) return true; 5855821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 5865821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // If there is no branch, control always falls through. 5875821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (TBB == 0) return true; 5885821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 5895821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // If there is some explicit branch to the fallthrough block, it can obviously 5905821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // reach, even though the branch should get folded to fall through implicitly. 5915821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (MachineFunction::iterator(TBB) == Fallthrough || 5925821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) MachineFunction::iterator(FBB) == Fallthrough) 5935821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return true; 5945821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 5955821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // If it's an unconditional branch to some block not the fall through, it 5965821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // doesn't fall through. 5975821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (Cond.empty()) return false; 5985821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 5995821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Otherwise, if it is conditional and has no explicit false block, it falls 6005821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // through. 6015821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return FBB == 0; 6025821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 6035821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 6045821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)/// CanFallThrough - Return true if the specified can implicitly transfer 6055821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)/// control to the block after it by falling off the end of it. This should 6065821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)/// return false if it can reach the block after it, but it uses an explicit 6075821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)/// branch to do so (e.g. a table jump). 6085821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)/// 6095821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)/// True is a conservative answer. 6105821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)/// 6115821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)bool BranchFolder::CanFallThrough(MachineBasicBlock *CurBB) { 6125821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) MachineBasicBlock *TBB = 0, *FBB = 0; 6135821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) std::vector<MachineOperand> Cond; 6145821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) bool CurUnAnalyzable = TII->AnalyzeBranch(*CurBB, TBB, FBB, Cond); 6155821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return CanFallThrough(CurBB, CurUnAnalyzable, TBB, FBB, Cond); 6165821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 6175821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 6185821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)/// IsBetterFallthrough - Return true if it would be clearly better to 6195821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)/// fall-through to MBB1 than to fall through into MBB2. This has to return 6205821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)/// a strict ordering, returning true for both (MBB1,MBB2) and (MBB2,MBB1) will 6215821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)/// result in infinite loops. 6225821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)static bool IsBetterFallthrough(MachineBasicBlock *MBB1, 6235821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) MachineBasicBlock *MBB2, 6245821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const TargetInstrInfo &TII) { 6255821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Right now, we use a simple heuristic. If MBB2 ends with a call, and 6265821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // MBB1 doesn't, we prefer to fall through into MBB1. This allows us to 6275821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // optimize branches that branch to either a return block or an assert block 6285821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // into a fallthrough to the return. 6295821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (MBB1->empty() || MBB2->empty()) return false; 6305821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 6315821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) MachineInstr *MBB1I = --MBB1->end(); 6325821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) MachineInstr *MBB2I = --MBB2->end(); 6335821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return TII.isCall(MBB2I->getOpcode()) && !TII.isCall(MBB1I->getOpcode()); 6345821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 6355821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 6365821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)/// OptimizeBlock - Analyze and optimize control flow related to the specified 6375821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)/// block. This is never called on the entry block. 6385821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)void BranchFolder::OptimizeBlock(MachineBasicBlock *MBB) { 6395821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) MachineFunction::iterator FallThrough = MBB; 6405821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ++FallThrough; 6415821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 6425821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // If this block is empty, make everyone use its fall-through, not the block 6435821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // explicitly. 6445821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (MBB->empty()) { 6455821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Dead block? Leave for cleanup later. 6465821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (MBB->pred_empty()) return; 6475821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 6485821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (FallThrough == MBB->getParent()->end()) { 6495821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // TODO: Simplify preds to not branch here if possible! 6505821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } else { 6515821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Rewrite all predecessors of the old block to go to the fallthrough 6525821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // instead. 6535821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) while (!MBB->pred_empty()) { 6545821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) MachineBasicBlock *Pred = *(MBB->pred_end()-1); 6555821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ReplaceUsesOfBlockWith(Pred, MBB, FallThrough, TII); 6565821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 6575821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 6585821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // If MBB was the target of a jump table, update jump tables to go to the 6595821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // fallthrough instead. 6605821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) MBB->getParent()->getJumpTableInfo()-> 6615821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ReplaceMBBInJumpTables(MBB, FallThrough); 6625821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) MadeChange = true; 6635821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 6645821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return; 6655821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 6665821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 6675821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Check to see if we can simplify the terminator of the block before this 6685821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // one. 6695821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) MachineBasicBlock &PrevBB = *prior(MachineFunction::iterator(MBB)); 6705821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 6715821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) MachineBasicBlock *PriorTBB = 0, *PriorFBB = 0; 6725821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) std::vector<MachineOperand> PriorCond; 6735821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) bool PriorUnAnalyzable = 6745821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) TII->AnalyzeBranch(PrevBB, PriorTBB, PriorFBB, PriorCond); 6755821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (!PriorUnAnalyzable) { 6765821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // If the CFG for the prior block has extra edges, remove them. 6775821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) MadeChange |= CorrectExtraCFGEdges(PrevBB, PriorTBB, PriorFBB, 6785821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) !PriorCond.empty(), MBB); 6795821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 6805821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // If the previous branch is conditional and both conditions go to the same 6815821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // destination, remove the branch, replacing it with an unconditional one or 6825821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // a fall-through. 6835821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (PriorTBB && PriorTBB == PriorFBB) { 6845821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) TII->RemoveBranch(PrevBB); 6855821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) PriorCond.clear(); 6865821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (PriorTBB != MBB) 6875821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) TII->InsertBranch(PrevBB, PriorTBB, 0, PriorCond); 6885821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) MadeChange = true; 6895821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ++NumBranchOpts; 6905821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return OptimizeBlock(MBB); 6915821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 6925821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 6935821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // If the previous branch *only* branches to *this* block (conditional or 6945821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // not) remove the branch. 6955821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (PriorTBB == MBB && PriorFBB == 0) { 6965821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) TII->RemoveBranch(PrevBB); 6975821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) MadeChange = true; 6985821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ++NumBranchOpts; 6995821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return OptimizeBlock(MBB); 7005821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 7015821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 7025821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // If the prior block branches somewhere else on the condition and here if 7035821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // the condition is false, remove the uncond second branch. 7045821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (PriorFBB == MBB) { 7055821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) TII->RemoveBranch(PrevBB); 7065821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) TII->InsertBranch(PrevBB, PriorTBB, 0, PriorCond); 7075821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) MadeChange = true; 7085821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ++NumBranchOpts; 7095821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return OptimizeBlock(MBB); 7105821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 7115821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 7125821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // If the prior block branches here on true and somewhere else on false, and 7135821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // if the branch condition is reversible, reverse the branch to create a 7145821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // fall-through. 7155821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (PriorTBB == MBB) { 7165821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) std::vector<MachineOperand> NewPriorCond(PriorCond); 7175821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (!TII->ReverseBranchCondition(NewPriorCond)) { 7185821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) TII->RemoveBranch(PrevBB); 7195821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) TII->InsertBranch(PrevBB, PriorFBB, 0, NewPriorCond); 7205821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) MadeChange = true; 7215821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ++NumBranchOpts; 7225821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return OptimizeBlock(MBB); 7235821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 7245821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 7255821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 7265821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // If this block doesn't fall through (e.g. it ends with an uncond branch or 7275821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // has no successors) and if the pred falls through into this block, and if 7285821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // it would otherwise fall through into the block after this, move this 7295821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // block to the end of the function. 7305821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // 7315821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // We consider it more likely that execution will stay in the function (e.g. 7325821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // due to loops) than it is to exit it. This asserts in loops etc, moving 7335821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // the assert condition out of the loop body. 7345821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (!PriorCond.empty() && PriorFBB == 0 && 7355821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) MachineFunction::iterator(PriorTBB) == FallThrough && 7365821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) !CanFallThrough(MBB)) { 7375821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) bool DoTransform = true; 7385821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 7395821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // We have to be careful that the succs of PredBB aren't both no-successor 7405821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // blocks. If neither have successors and if PredBB is the second from 7415821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // last block in the function, we'd just keep swapping the two blocks for 7425821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // last. Only do the swap if one is clearly better to fall through than 7435821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // the other. 7445821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (FallThrough == --MBB->getParent()->end() && 7455821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) !IsBetterFallthrough(PriorTBB, MBB, *TII)) 7465821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) DoTransform = false; 7475821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 7485821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // We don't want to do this transformation if we have control flow like: 7495821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // br cond BB2 7505821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // BB1: 7515821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // .. 7525821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // jmp BBX 7535821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // BB2: 7545821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // .. 7555821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // ret 7565821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // 7575821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // In this case, we could actually be moving the return block *into* a 7585821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // loop! 7595821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (DoTransform && !MBB->succ_empty() && 7605821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) (!CanFallThrough(PriorTBB) || PriorTBB->empty())) 7615821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) DoTransform = false; 7625821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 7635821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 7645821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (DoTransform) { 7655821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Reverse the branch so we will fall through on the previous true cond. 7665821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) std::vector<MachineOperand> NewPriorCond(PriorCond); 7675821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (!TII->ReverseBranchCondition(NewPriorCond)) { 7685821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) DOUT << "\nMoving MBB: " << *MBB; 7695821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) DOUT << "To make fallthrough to: " << *PriorTBB << "\n"; 7705821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 7715821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) TII->RemoveBranch(PrevBB); 7725821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) TII->InsertBranch(PrevBB, MBB, 0, NewPriorCond); 7735821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 7745821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Move this block to the end of the function. 7755821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) MBB->moveAfter(--MBB->getParent()->end()); 7765821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) MadeChange = true; 7775821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ++NumBranchOpts; 7785821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return; 7795821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 7805821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 7815821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 7825821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 7835821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 7845821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Analyze the branch in the current block. 7855821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) MachineBasicBlock *CurTBB = 0, *CurFBB = 0; 7865821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) std::vector<MachineOperand> CurCond; 7875821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) bool CurUnAnalyzable = TII->AnalyzeBranch(*MBB, CurTBB, CurFBB, CurCond); 7885821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (!CurUnAnalyzable) { 7895821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // If the CFG for the prior block has extra edges, remove them. 7905821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) MadeChange |= CorrectExtraCFGEdges(*MBB, CurTBB, CurFBB, 7915821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) !CurCond.empty(), 7925821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ++MachineFunction::iterator(MBB)); 7935821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 7945821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // If this is a two-way branch, and the FBB branches to this block, reverse 7955821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // the condition so the single-basic-block loop is faster. Instead of: 7965821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Loop: xxx; jcc Out; jmp Loop 7975821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // we want: 7985821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Loop: xxx; jncc Loop; jmp Out 7995821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (CurTBB && CurFBB && CurFBB == MBB && CurTBB != MBB) { 8005821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) std::vector<MachineOperand> NewCond(CurCond); 8015821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (!TII->ReverseBranchCondition(NewCond)) { 8025821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) TII->RemoveBranch(*MBB); 8035821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) TII->InsertBranch(*MBB, CurFBB, CurTBB, NewCond); 8045821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) MadeChange = true; 8055821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ++NumBranchOpts; 8065821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return OptimizeBlock(MBB); 8075821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 8085821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 8095821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 8105821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 8115821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // If this branch is the only thing in its block, see if we can forward 8125821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // other blocks across it. 8135821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (CurTBB && CurCond.empty() && CurFBB == 0 && 8145821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) TII->isBranch(MBB->begin()->getOpcode()) && CurTBB != MBB) { 8155821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // This block may contain just an unconditional branch. Because there can 8165821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // be 'non-branch terminators' in the block, try removing the branch and 8175821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // then seeing if the block is empty. 8185821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) TII->RemoveBranch(*MBB); 8195821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 8205821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // If this block is just an unconditional branch to CurTBB, we can 8215821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // usually completely eliminate the block. The only case we cannot 8225821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // completely eliminate the block is when the block before this one 8235821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // falls through into MBB and we can't understand the prior block's branch 8245821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // condition. 8255821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (MBB->empty()) { 8265821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) bool PredHasNoFallThrough = TII->BlockHasNoFallThrough(PrevBB); 8275821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (PredHasNoFallThrough || !PriorUnAnalyzable || 8285821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) !PrevBB.isSuccessor(MBB)) { 8295821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // If the prior block falls through into us, turn it into an 8305821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // explicit branch to us to make updates simpler. 8315821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (!PredHasNoFallThrough && PrevBB.isSuccessor(MBB) && 8325821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) PriorTBB != MBB && PriorFBB != MBB) { 8335821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (PriorTBB == 0) { 8345821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) assert(PriorCond.empty() && PriorFBB == 0 && 8355821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) "Bad branch analysis"); 8365821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) PriorTBB = MBB; 8375821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } else { 8385821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) assert(PriorFBB == 0 && "Machine CFG out of date!"); 8395821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) PriorFBB = MBB; 8405821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 8415821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) TII->RemoveBranch(PrevBB); 8425821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) TII->InsertBranch(PrevBB, PriorTBB, PriorFBB, PriorCond); 8435821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 8445821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 8455821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Iterate through all the predecessors, revectoring each in-turn. 8465821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) MachineBasicBlock::pred_iterator PI = MBB->pred_begin(); 8475821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) bool DidChange = false; 8485821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) bool HasBranchToSelf = false; 8495821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) while (PI != MBB->pred_end()) { 8505821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (*PI == MBB) { 8515821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // If this block has an uncond branch to itself, leave it. 8525821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ++PI; 8535821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) HasBranchToSelf = true; 8545821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } else { 8555821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) DidChange = true; 8565821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ReplaceUsesOfBlockWith(*PI, MBB, CurTBB, TII); 8575821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 8585821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 8595821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 8605821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Change any jumptables to go to the new MBB. 8615821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) MBB->getParent()->getJumpTableInfo()-> 8625821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ReplaceMBBInJumpTables(MBB, CurTBB); 8635821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (DidChange) { 8645821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ++NumBranchOpts; 8655821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) MadeChange = true; 8665821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (!HasBranchToSelf) return; 8675821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 8685821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 8695821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 8705821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 8715821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Add the branch back if the block is more than just an uncond branch. 8725821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) TII->InsertBranch(*MBB, CurTBB, 0, CurCond); 8735821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 8745821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 8755821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 8765821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // If the prior block doesn't fall through into this block, and if this 8775821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // block doesn't fall through into some other block, see if we can find a 8785821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // place to move this block where a fall-through will happen. 8795821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (!CanFallThrough(&PrevBB, PriorUnAnalyzable, 8805821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) PriorTBB, PriorFBB, PriorCond)) { 8815821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Now we know that there was no fall-through into this block, check to 8825821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // see if it has a fall-through into its successor. 8835821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) bool CurFallsThru = CanFallThrough(MBB, CurUnAnalyzable, CurTBB, CurFBB, 8845821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) CurCond); 8855821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 8865821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (!MBB->isLandingPad()) { 8875821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Check all the predecessors of this block. If one of them has no fall 8885821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // throughs, move this block right after it. 8895821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) for (MachineBasicBlock::pred_iterator PI = MBB->pred_begin(), 8905821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) E = MBB->pred_end(); PI != E; ++PI) { 8915821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Analyze the branch at the end of the pred. 8925821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) MachineBasicBlock *PredBB = *PI; 8935821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) MachineFunction::iterator PredFallthrough = PredBB; ++PredFallthrough; 8945821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (PredBB != MBB && !CanFallThrough(PredBB) 8955821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) && (!CurFallsThru || MBB->getNumber() >= PredBB->getNumber())) { 8965821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // If the current block doesn't fall through, just move it. 8975821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // If the current block can fall through and does not end with a 8985821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // conditional branch, we need to append an unconditional jump to 8995821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // the (current) next block. To avoid a possible compile-time 9005821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // infinite loop, move blocks only backward in this case. 9015821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (CurFallsThru) { 9025821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) MachineBasicBlock *NextBB = next(MachineFunction::iterator(MBB)); 9035821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) CurCond.clear(); 9045821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) TII->InsertBranch(*MBB, NextBB, 0, CurCond); 9055821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 9065821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) MBB->moveAfter(PredBB); 9075821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) MadeChange = true; 9085821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return OptimizeBlock(MBB); 9095821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 9105821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 9115821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 9125821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 9135821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (!CurFallsThru) { 9145821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Check all successors to see if we can move this block before it. 9155821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) for (MachineBasicBlock::succ_iterator SI = MBB->succ_begin(), 9165821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) E = MBB->succ_end(); SI != E; ++SI) { 9175821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Analyze the branch at the end of the block before the succ. 9185821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) MachineBasicBlock *SuccBB = *SI; 9195821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) MachineFunction::iterator SuccPrev = SuccBB; --SuccPrev; 9205821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) std::vector<MachineOperand> SuccPrevCond; 9215821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 9225821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // If this block doesn't already fall-through to that successor, and if 9235821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // the succ doesn't already have a block that can fall through into it, 9245821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // and if the successor isn't an EH destination, we can arrange for the 9255821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // fallthrough to happen. 9265821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (SuccBB != MBB && !CanFallThrough(SuccPrev) && 9275821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) !SuccBB->isLandingPad()) { 9285821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) MBB->moveBefore(SuccBB); 9295821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) MadeChange = true; 9305821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return OptimizeBlock(MBB); 9315821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 9325821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 9335821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 9345821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Okay, there is no really great place to put this block. If, however, 9355821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // the block before this one would be a fall-through if this block were 9365821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // removed, move this block to the end of the function. 9375821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (FallThrough != MBB->getParent()->end() && 9385821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) PrevBB.isSuccessor(FallThrough)) { 9395821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) MBB->moveAfter(--MBB->getParent()->end()); 9405821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) MadeChange = true; 9415821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return; 9425821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 9435821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 9445821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 9455821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 9465821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)