BranchFolding.cpp revision 551ccae044b0ff658fe629dd67edd5ffe75d10e8
121ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner//===-- BranchFolding.cpp - Fold machine code branch instructions ---------===// 221ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner// 321ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner// The LLVM Compiler Infrastructure 421ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner// 521ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner// This file was developed by the LLVM research group and is distributed under 621ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner// the University of Illinois Open Source License. See LICENSE.TXT for details. 721ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner// 821ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner//===----------------------------------------------------------------------===// 921ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner// 1021ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner// This pass forwards branches to unconditional branches to make them branch 1121ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner// directly to the target block. This pass often results in dead MBB's, which 1221ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner// it then removes. 1321ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner// 1421ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner// Note that this pass must be run after register allocation, it cannot handle 1521ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner// SSA form. 1621ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner// 1721ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner//===----------------------------------------------------------------------===// 1821ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner 1921ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner#include "llvm/CodeGen/Passes.h" 2021ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner#include "llvm/CodeGen/MachineFunctionPass.h" 2121ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner#include "llvm/Target/TargetInstrInfo.h" 2221ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner#include "llvm/Target/TargetMachine.h" 23551ccae044b0ff658fe629dd67edd5ffe75d10e8Reid Spencer#include "llvm/ADT/STLExtras.h" 2421ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattnerusing namespace llvm; 2521ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner 2621ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattnernamespace { 2721ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner struct BranchFolder : public MachineFunctionPass { 2821ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner virtual bool runOnMachineFunction(MachineFunction &MF); 2921ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner virtual const char *getPassName() const { return "Branch Folder"; } 3021ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner private: 31f978a1db517749e91210b7df17b7f11b9a30ae47Alkis Evlogimenos bool OptimizeBlock(MachineFunction::iterator MBB, 32f978a1db517749e91210b7df17b7f11b9a30ae47Alkis Evlogimenos const TargetInstrInfo &TII); 3321ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner 3421ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner bool isUncondBranch(const MachineInstr *MI, const TargetInstrInfo &TII) { 3521ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner return TII.isBarrier(MI->getOpcode()) && TII.isBranch(MI->getOpcode()); 3621ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner } 3721ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner bool isCondBranch(const MachineInstr *MI, const TargetInstrInfo &TII) { 3821ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner return TII.isBranch(MI->getOpcode()) && !TII.isBarrier(MI->getOpcode()); 3921ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner } 4021ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner }; 4121ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner} 4221ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner 4321ab22e47592d8a4046cfdac844d76b2cb76d711Chris LattnerFunctionPass *llvm::createBranchFoldingPass() { return new BranchFolder(); } 4421ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner 4521ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattnerbool BranchFolder::runOnMachineFunction(MachineFunction &MF) { 4621ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner bool EverMadeChange = false; 4721ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner bool MadeChange = true; 4821ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner const TargetInstrInfo &TII = *MF.getTarget().getInstrInfo(); 4921ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner while (MadeChange) { 5021ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner MadeChange = false; 5121ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner for (MachineFunction::iterator MBB = ++MF.begin(), E = MF.end(); MBB != E; 5221ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner ++MBB) 5321ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner MadeChange |= OptimizeBlock(MBB, TII); 5421ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner 5521ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner // If branches were folded away somehow, do a quick scan and delete any dead 5621ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner // blocks. 5721ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner if (MadeChange) { 5821ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner for (MachineFunction::iterator I = ++MF.begin(), E = MF.end(); I != E; ) { 5921ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner MachineBasicBlock *MBB = I++; 6021ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner // Is it dead? 6121ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner if (MBB->pred_empty()) { 6221ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner // drop all successors. 6321ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner while (!MBB->succ_empty()) 6421ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner MBB->removeSuccessor(MBB->succ_end()-1); 6521ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner MF.getBasicBlockList().erase(MBB); 6621ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner } 6721ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner } 6821ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner } 6921ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner 7021ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner EverMadeChange |= MadeChange; 7121ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner } 7221ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner 7321ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner return EverMadeChange; 7421ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner} 7521ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner 7621ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner/// ReplaceUsesOfBlockWith - Given a machine basic block 'BB' that branched to 7721ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner/// 'Old', change the code and CFG so that it branches to 'New' instead. 7821ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattnerstatic void ReplaceUsesOfBlockWith(MachineBasicBlock *BB, 7921ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner MachineBasicBlock *Old, 8021ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner MachineBasicBlock *New, 8121ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner const TargetInstrInfo &TII) { 8221ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner assert(Old != New && "Cannot replace self with self!"); 8321ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner 8421ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner MachineBasicBlock::iterator I = BB->end(); 8521ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner while (I != BB->begin()) { 8621ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner --I; 8721ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner if (!TII.isTerminatorInstr(I->getOpcode())) break; 8821ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner 8921ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner // Scan the operands of this machine instruction, replacing any uses of Old 9021ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner // with New. 9121ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i) 9221ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner if (I->getOperand(i).isMachineBasicBlock() && 9321ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner I->getOperand(i).getMachineBasicBlock() == Old) 9421ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner I->getOperand(i).setMachineBasicBlock(New); 9521ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner } 9621ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner 9721ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner // If BB falls through into Old, insert an unconditional branch to New. 9821ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner MachineFunction::iterator BBSucc = BB; ++BBSucc; 994ae131e5da124bb5f7455133fefb1fa3b336192bChris Lattner if (BBSucc != BB->getParent()->end() && &*BBSucc == Old) 10021ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner TII.insertGoto(*BB, *New); 10121ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner 10221ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner std::vector<MachineBasicBlock*> Succs(BB->succ_begin(), BB->succ_end()); 10321ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner for (int i = Succs.size()-1; i >= 0; --i) 10421ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner if (Succs[i] == Old) { 10521ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner BB->removeSuccessor(Old); 10621ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner BB->addSuccessor(New); 10721ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner } 10821ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner} 10921ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner 11021ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner 111f978a1db517749e91210b7df17b7f11b9a30ae47Alkis Evlogimenosbool BranchFolder::OptimizeBlock(MachineFunction::iterator MBB, 11221ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner const TargetInstrInfo &TII) { 11321ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner // If this block is empty, make everyone use it's fall-through, not the block 11421ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner // explicitly. 11521ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner if (MBB->empty()) { 11621ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner if (MBB->pred_empty()) return false; 117f978a1db517749e91210b7df17b7f11b9a30ae47Alkis Evlogimenos MachineFunction::iterator FallThrough =next(MBB); 11821ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner assert(FallThrough != MBB->getParent()->end() && 11921ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner "Fell off the end of the function!"); 12021ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner while (!MBB->pred_empty()) { 12121ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner MachineBasicBlock *Pred = *(MBB->pred_end()-1); 12221ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner ReplaceUsesOfBlockWith(Pred, MBB, FallThrough, TII); 12321ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner } 12421ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner return true; 12521ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner } 12621ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner 12721ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner if (MBB->pred_size() == 1) { 12821ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner // If this block has a single predecessor, and if that block has a single 12921ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner // successor, merge this block into that block. 13021ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner MachineBasicBlock *Pred = *MBB->pred_begin(); 13121ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner if (Pred->succ_size() == 1) { 13221ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner // Delete all of the terminators from end of the pred block. NOTE, this 13321ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner // assumes that terminators do not have side effects! 13421ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner while (!Pred->empty() && TII.isTerminatorInstr(Pred->back().getOpcode())) 13521ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner Pred->pop_back(); 13621ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner 13721ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner // Splice the instructions over. 13821ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner Pred->splice(Pred->end(), MBB, MBB->begin(), MBB->end()); 13921ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner 14021ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner // If MBB does not end with a barrier, add a goto instruction to the end. 14121ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner if (Pred->empty() || !TII.isBarrier(Pred->back().getOpcode())) 1429fd332392c184b13eeb2bd3ffc4347034bc7408aAlkis Evlogimenos TII.insertGoto(*Pred, *next(MBB)); 14321ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner 14421ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner // Update the CFG now. 14521ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner Pred->removeSuccessor(Pred->succ_begin()); 14621ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner while (!MBB->succ_empty()) { 14721ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner Pred->addSuccessor(*(MBB->succ_end()-1)); 14821ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner MBB->removeSuccessor(MBB->succ_end()-1); 14921ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner } 15021ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner return true; 15121ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner } 15221ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner } 15321ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner 15421ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner // If the first instruction in this block is an unconditional branch, and if 15521ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner // there are predecessors, fold the branch into the predecessors. 15621ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner if (!MBB->pred_empty() && isUncondBranch(MBB->begin(), TII)) { 15721ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner MachineInstr *Br = MBB->begin(); 15821ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner assert(Br->getNumOperands() == 1 && Br->getOperand(0).isMachineBasicBlock() 15921ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner && "Uncond branch should take one MBB argument!"); 16021ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner MachineBasicBlock *Dest = Br->getOperand(0).getMachineBasicBlock(); 16121ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner 16221ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner while (!MBB->pred_empty()) { 16321ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner MachineBasicBlock *Pred = *(MBB->pred_end()-1); 16421ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner ReplaceUsesOfBlockWith(Pred, MBB, Dest, TII); 16521ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner } 16621ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner return true; 16721ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner } 16821ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner 16921ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner // If the last instruction is an unconditional branch and the fall through 17021ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner // block is the destination, just delete the branch. 17121ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner if (isUncondBranch(--MBB->end(), TII)) { 17221ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner MachineBasicBlock::iterator MI = --MBB->end(); 17321ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner MachineInstr *UncondBr = MI; 1749fd332392c184b13eeb2bd3ffc4347034bc7408aAlkis Evlogimenos MachineFunction::iterator FallThrough = next(MBB); 17521ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner 176dd0458378128b748d4ac6c6035cd47d021faf507Alkis Evlogimenos MachineFunction::iterator UncondDest = 177dd0458378128b748d4ac6c6035cd47d021faf507Alkis Evlogimenos MI->getOperand(0).getMachineBasicBlock(); 178dd0458378128b748d4ac6c6035cd47d021faf507Alkis Evlogimenos if (UncondDest == FallThrough) { 17921ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner // Just delete the branch. This does not effect the CFG. 18021ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner MBB->erase(UncondBr); 18121ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner return true; 18221ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner } 18321ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner 18421ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner // Okay, so we don't have a fall-through. Check to see if we have an 18521ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner // conditional branch that would be a fall through if we reversed it. If 18621ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner // so, invert the condition and delete the uncond branch. 18721ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner if (MI != MBB->begin() && isCondBranch(--MI, TII)) { 18821ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner // We assume that conditional branches always have the branch dest as the 18921ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner // last operand. This could be generalized in the future if needed. 19021ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner unsigned LastOpnd = MI->getNumOperands()-1; 1919fd332392c184b13eeb2bd3ffc4347034bc7408aAlkis Evlogimenos if (MachineFunction::iterator( 1929fd332392c184b13eeb2bd3ffc4347034bc7408aAlkis Evlogimenos MI->getOperand(LastOpnd).getMachineBasicBlock()) == FallThrough) { 19321ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner // Change the cond branch to go to the uncond dest, nuke the uncond, 19421ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner // then reverse the condition. 19521ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner MI->getOperand(LastOpnd).setMachineBasicBlock(UncondDest); 19621ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner MBB->erase(UncondBr); 19721ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner TII.reverseBranchCondition(MI); 19821ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner return true; 19921ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner } 20021ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner } 20121ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner } 20221ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner 20321ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner return false; 20421ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner} 205