BranchFolding.cpp revision 7821a8afd3009c3c2760592e61de9e2c31c73e18
121ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner//===-- BranchFolding.cpp - Fold machine code branch instructions ---------===// 2edf128a7fa90f2b0b7ee24741a04a7ae1ecd6f7eMisha Brukman// 321ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner// The LLVM Compiler Infrastructure 421ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner// 521ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner// This file was developed by the LLVM research group and is distributed under 621ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner// the University of Illinois Open Source License. See LICENSE.TXT for details. 7edf128a7fa90f2b0b7ee24741a04a7ae1ecd6f7eMisha Brukman// 821ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner//===----------------------------------------------------------------------===// 921ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner// 1021ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner// This pass forwards branches to unconditional branches to make them branch 1121ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner// directly to the target block. This pass often results in dead MBB's, which 1221ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner// it then removes. 1321ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner// 1421ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner// Note that this pass must be run after register allocation, it cannot handle 1521ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner// SSA form. 1621ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner// 1721ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner//===----------------------------------------------------------------------===// 1821ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner 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); 297821a8afd3009c3c2760592e61de9e2c31c73e18Chris Lattner virtual const char *getPassName() const { return "Control Flow Optimizer"; } 307821a8afd3009c3c2760592e61de9e2c31c73e18Chris Lattner const TargetInstrInfo *TII; 317821a8afd3009c3c2760592e61de9e2c31c73e18Chris Lattner bool MadeChange; 3221ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner private: 337821a8afd3009c3c2760592e61de9e2c31c73e18Chris Lattner void OptimizeBlock(MachineFunction::iterator MBB); 3421ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner }; 3521ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner} 3621ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner 3721ab22e47592d8a4046cfdac844d76b2cb76d711Chris LattnerFunctionPass *llvm::createBranchFoldingPass() { return new BranchFolder(); } 3821ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner 3921ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattnerbool BranchFolder::runOnMachineFunction(MachineFunction &MF) { 407821a8afd3009c3c2760592e61de9e2c31c73e18Chris Lattner TII = MF.getTarget().getInstrInfo(); 417821a8afd3009c3c2760592e61de9e2c31c73e18Chris Lattner if (!TII) return false; 427821a8afd3009c3c2760592e61de9e2c31c73e18Chris Lattner 437821a8afd3009c3c2760592e61de9e2c31c73e18Chris Lattner //MF.dump(); 447821a8afd3009c3c2760592e61de9e2c31c73e18Chris Lattner 4521ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner bool EverMadeChange = false; 467821a8afd3009c3c2760592e61de9e2c31c73e18Chris Lattner MadeChange = true; 4721ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner while (MadeChange) { 4821ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner MadeChange = false; 4921ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner for (MachineFunction::iterator MBB = ++MF.begin(), E = MF.end(); MBB != E; 5021ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner ++MBB) 517821a8afd3009c3c2760592e61de9e2c31c73e18Chris Lattner OptimizeBlock(MBB); 527821a8afd3009c3c2760592e61de9e2c31c73e18Chris Lattner 5321ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner // If branches were folded away somehow, do a quick scan and delete any dead 5421ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner // blocks. 5521ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner if (MadeChange) { 5621ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner for (MachineFunction::iterator I = ++MF.begin(), E = MF.end(); I != E; ) { 5721ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner MachineBasicBlock *MBB = I++; 5821ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner // Is it dead? 5921ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner if (MBB->pred_empty()) { 6021ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner // drop all successors. 6121ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner while (!MBB->succ_empty()) 6221ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner MBB->removeSuccessor(MBB->succ_end()-1); 6321ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner MF.getBasicBlockList().erase(MBB); 6421ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner } 6521ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner } 6621ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner } 6721ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner 6821ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner EverMadeChange |= MadeChange; 6921ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner } 7021ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner 7121ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner return EverMadeChange; 7221ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner} 7321ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner 7421ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner/// ReplaceUsesOfBlockWith - Given a machine basic block 'BB' that branched to 7521ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner/// 'Old', change the code and CFG so that it branches to 'New' instead. 7621ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattnerstatic void ReplaceUsesOfBlockWith(MachineBasicBlock *BB, 7721ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner MachineBasicBlock *Old, 7821ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner MachineBasicBlock *New, 797821a8afd3009c3c2760592e61de9e2c31c73e18Chris Lattner const TargetInstrInfo *TII) { 8021ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner assert(Old != New && "Cannot replace self with self!"); 8121ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner 8221ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner MachineBasicBlock::iterator I = BB->end(); 8321ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner while (I != BB->begin()) { 8421ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner --I; 857821a8afd3009c3c2760592e61de9e2c31c73e18Chris Lattner if (!TII->isTerminatorInstr(I->getOpcode())) break; 8621ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner 8721ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner // Scan the operands of this machine instruction, replacing any uses of Old 8821ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner // with New. 8921ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i) 9021ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner if (I->getOperand(i).isMachineBasicBlock() && 9121ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner I->getOperand(i).getMachineBasicBlock() == Old) 9221ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner I->getOperand(i).setMachineBasicBlock(New); 9321ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner } 9421ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner 95eb15eeec396145b6f5028d07bd2c4a5e903fdec5Chris Lattner // Update the successor information. 9621ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner std::vector<MachineBasicBlock*> Succs(BB->succ_begin(), BB->succ_end()); 9721ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner for (int i = Succs.size()-1; i >= 0; --i) 9821ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner if (Succs[i] == Old) { 9921ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner BB->removeSuccessor(Old); 10021ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner BB->addSuccessor(New); 10121ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner } 10221ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner} 10321ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner 1047821a8afd3009c3c2760592e61de9e2c31c73e18Chris Lattner/// OptimizeBlock - Analyze and optimize control flow related to the specified 1057821a8afd3009c3c2760592e61de9e2c31c73e18Chris Lattner/// block. This is never called on the entry block. 1067821a8afd3009c3c2760592e61de9e2c31c73e18Chris Lattnervoid BranchFolder::OptimizeBlock(MachineFunction::iterator MBB) { 107eb15eeec396145b6f5028d07bd2c4a5e903fdec5Chris Lattner // If this block is empty, make everyone use its fall-through, not the block 10821ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner // explicitly. 10921ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner if (MBB->empty()) { 1107821a8afd3009c3c2760592e61de9e2c31c73e18Chris Lattner if (MBB->pred_empty()) return; // dead block? Leave for cleanup later. 1117821a8afd3009c3c2760592e61de9e2c31c73e18Chris Lattner 1127821a8afd3009c3c2760592e61de9e2c31c73e18Chris Lattner MachineFunction::iterator FallThrough = next(MBB); 1137821a8afd3009c3c2760592e61de9e2c31c73e18Chris Lattner 1147821a8afd3009c3c2760592e61de9e2c31c73e18Chris Lattner if (FallThrough != MBB->getParent()->end()) { 1157821a8afd3009c3c2760592e61de9e2c31c73e18Chris Lattner while (!MBB->pred_empty()) { 1167821a8afd3009c3c2760592e61de9e2c31c73e18Chris Lattner MachineBasicBlock *Pred = *(MBB->pred_end()-1); 1177821a8afd3009c3c2760592e61de9e2c31c73e18Chris Lattner ReplaceUsesOfBlockWith(Pred, MBB, FallThrough, TII); 1187821a8afd3009c3c2760592e61de9e2c31c73e18Chris Lattner } 1197821a8afd3009c3c2760592e61de9e2c31c73e18Chris Lattner MadeChange = true; 12021ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner } 1217821a8afd3009c3c2760592e61de9e2c31c73e18Chris Lattner // TODO: CHANGE STUFF TO NOT BRANCH HERE! 1227821a8afd3009c3c2760592e61de9e2c31c73e18Chris Lattner return; 12321ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner } 12421ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner 1257821a8afd3009c3c2760592e61de9e2c31c73e18Chris Lattner // Check to see if we can simplify the terminator of the block before this 1267821a8afd3009c3c2760592e61de9e2c31c73e18Chris Lattner // one. 1277821a8afd3009c3c2760592e61de9e2c31c73e18Chris Lattner#if 0 1287821a8afd3009c3c2760592e61de9e2c31c73e18Chris Lattner MachineBasicBlock *PriorTBB = 0, *PriorFBB = 0; 1297821a8afd3009c3c2760592e61de9e2c31c73e18Chris Lattner std::vector<MachineOperand> PriorCond; 1307821a8afd3009c3c2760592e61de9e2c31c73e18Chris Lattner if (!TII->AnalyzeBranch(*prior(MBB), PriorTBB, PriorFBB, PriorCond)) { 1317821a8afd3009c3c2760592e61de9e2c31c73e18Chris Lattner // If the previous branch is conditional and both conditions go to the same 1327821a8afd3009c3c2760592e61de9e2c31c73e18Chris Lattner // destination, remove the branch, replacing it with an unconditional one. 1337821a8afd3009c3c2760592e61de9e2c31c73e18Chris Lattner if (PriorTBB && PriorTBB == PriorFBB) { 1347821a8afd3009c3c2760592e61de9e2c31c73e18Chris Lattner TII->RemoveBranch(*prior(MBB)); 1357821a8afd3009c3c2760592e61de9e2c31c73e18Chris Lattner PriorCond.clear(); 1367821a8afd3009c3c2760592e61de9e2c31c73e18Chris Lattner if (PriorTBB != &*MBB) 1377821a8afd3009c3c2760592e61de9e2c31c73e18Chris Lattner TII->InsertBranch(*prior(MBB), PriorTBB, 0, PriorCond); 1387821a8afd3009c3c2760592e61de9e2c31c73e18Chris Lattner MadeChange = true; 1397821a8afd3009c3c2760592e61de9e2c31c73e18Chris Lattner return OptimizeBlock(MBB); 1407821a8afd3009c3c2760592e61de9e2c31c73e18Chris Lattner } 1417821a8afd3009c3c2760592e61de9e2c31c73e18Chris Lattner 1427821a8afd3009c3c2760592e61de9e2c31c73e18Chris Lattner // If the previous branch *only* branches to *this* block (conditional or 1437821a8afd3009c3c2760592e61de9e2c31c73e18Chris Lattner // not) remove the branch. 1447821a8afd3009c3c2760592e61de9e2c31c73e18Chris Lattner if (PriorTBB == &*MBB && PriorFBB == 0) { 1457821a8afd3009c3c2760592e61de9e2c31c73e18Chris Lattner TII->RemoveBranch(*prior(MBB)); 1467821a8afd3009c3c2760592e61de9e2c31c73e18Chris Lattner MadeChange = true; 1477821a8afd3009c3c2760592e61de9e2c31c73e18Chris Lattner return OptimizeBlock(MBB); 1487821a8afd3009c3c2760592e61de9e2c31c73e18Chris Lattner } 1497821a8afd3009c3c2760592e61de9e2c31c73e18Chris Lattner } 1507821a8afd3009c3c2760592e61de9e2c31c73e18Chris Lattner#endif 1517821a8afd3009c3c2760592e61de9e2c31c73e18Chris Lattner 1527821a8afd3009c3c2760592e61de9e2c31c73e18Chris Lattner 153eb15eeec396145b6f5028d07bd2c4a5e903fdec5Chris Lattner#if 0 154eb15eeec396145b6f5028d07bd2c4a5e903fdec5Chris Lattner 155eb15eeec396145b6f5028d07bd2c4a5e903fdec5Chris Lattner if (MBB->pred_size() == 1) { 156eb15eeec396145b6f5028d07bd2c4a5e903fdec5Chris Lattner // If this block has a single predecessor, and if that block has a single 157eb15eeec396145b6f5028d07bd2c4a5e903fdec5Chris Lattner // successor, merge this block into that block. 158eb15eeec396145b6f5028d07bd2c4a5e903fdec5Chris Lattner MachineBasicBlock *Pred = *MBB->pred_begin(); 159eb15eeec396145b6f5028d07bd2c4a5e903fdec5Chris Lattner if (Pred->succ_size() == 1) { 160eb15eeec396145b6f5028d07bd2c4a5e903fdec5Chris Lattner // Delete all of the terminators from end of the pred block. NOTE, this 161eb15eeec396145b6f5028d07bd2c4a5e903fdec5Chris Lattner // assumes that terminators do not have side effects! 162eb15eeec396145b6f5028d07bd2c4a5e903fdec5Chris Lattner // FIXME: This doesn't work for FP_REG_KILL. 163eb15eeec396145b6f5028d07bd2c4a5e903fdec5Chris Lattner 164eb15eeec396145b6f5028d07bd2c4a5e903fdec5Chris Lattner while (!Pred->empty() && TII.isTerminatorInstr(Pred->back().getOpcode())) 165eb15eeec396145b6f5028d07bd2c4a5e903fdec5Chris Lattner Pred->pop_back(); 166eb15eeec396145b6f5028d07bd2c4a5e903fdec5Chris Lattner 167eb15eeec396145b6f5028d07bd2c4a5e903fdec5Chris Lattner // Splice the instructions over. 168eb15eeec396145b6f5028d07bd2c4a5e903fdec5Chris Lattner Pred->splice(Pred->end(), MBB, MBB->begin(), MBB->end()); 169eb15eeec396145b6f5028d07bd2c4a5e903fdec5Chris Lattner 170eb15eeec396145b6f5028d07bd2c4a5e903fdec5Chris Lattner // If MBB does not end with a barrier, add a goto instruction to the end. 171eb15eeec396145b6f5028d07bd2c4a5e903fdec5Chris Lattner if (Pred->empty() || !TII.isBarrier(Pred->back().getOpcode())) 172eb15eeec396145b6f5028d07bd2c4a5e903fdec5Chris Lattner TII.insertGoto(*Pred, *next(MBB)); 173eb15eeec396145b6f5028d07bd2c4a5e903fdec5Chris Lattner 174eb15eeec396145b6f5028d07bd2c4a5e903fdec5Chris Lattner // Update the CFG now. 175eb15eeec396145b6f5028d07bd2c4a5e903fdec5Chris Lattner Pred->removeSuccessor(Pred->succ_begin()); 176eb15eeec396145b6f5028d07bd2c4a5e903fdec5Chris Lattner while (!MBB->succ_empty()) { 177eb15eeec396145b6f5028d07bd2c4a5e903fdec5Chris Lattner Pred->addSuccessor(*(MBB->succ_end()-1)); 178eb15eeec396145b6f5028d07bd2c4a5e903fdec5Chris Lattner MBB->removeSuccessor(MBB->succ_end()-1); 179eb15eeec396145b6f5028d07bd2c4a5e903fdec5Chris Lattner } 180eb15eeec396145b6f5028d07bd2c4a5e903fdec5Chris Lattner return true; 181eb15eeec396145b6f5028d07bd2c4a5e903fdec5Chris Lattner } 182eb15eeec396145b6f5028d07bd2c4a5e903fdec5Chris Lattner } 183eb15eeec396145b6f5028d07bd2c4a5e903fdec5Chris Lattner 184eb15eeec396145b6f5028d07bd2c4a5e903fdec5Chris Lattner // If BB falls through into Old, insert an unconditional branch to New. 185eb15eeec396145b6f5028d07bd2c4a5e903fdec5Chris Lattner MachineFunction::iterator BBSucc = BB; ++BBSucc; 186eb15eeec396145b6f5028d07bd2c4a5e903fdec5Chris Lattner if (BBSucc != BB->getParent()->end() && &*BBSucc == Old) 187eb15eeec396145b6f5028d07bd2c4a5e903fdec5Chris Lattner TII.insertGoto(*BB, *New); 188eb15eeec396145b6f5028d07bd2c4a5e903fdec5Chris Lattner 189eb15eeec396145b6f5028d07bd2c4a5e903fdec5Chris Lattner 19021ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner if (MBB->pred_size() == 1) { 19121ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner // If this block has a single predecessor, and if that block has a single 19221ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner // successor, merge this block into that block. 19321ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner MachineBasicBlock *Pred = *MBB->pred_begin(); 19421ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner if (Pred->succ_size() == 1) { 19521ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner // Delete all of the terminators from end of the pred block. NOTE, this 19621ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner // assumes that terminators do not have side effects! 197eb15eeec396145b6f5028d07bd2c4a5e903fdec5Chris Lattner // FIXME: This doesn't work for FP_REG_KILL. 198eb15eeec396145b6f5028d07bd2c4a5e903fdec5Chris Lattner 19921ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner while (!Pred->empty() && TII.isTerminatorInstr(Pred->back().getOpcode())) 20021ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner Pred->pop_back(); 20121ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner 20221ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner // Splice the instructions over. 20321ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner Pred->splice(Pred->end(), MBB, MBB->begin(), MBB->end()); 20421ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner 20521ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner // If MBB does not end with a barrier, add a goto instruction to the end. 20621ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner if (Pred->empty() || !TII.isBarrier(Pred->back().getOpcode())) 2079fd332392c184b13eeb2bd3ffc4347034bc7408aAlkis Evlogimenos TII.insertGoto(*Pred, *next(MBB)); 20821ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner 20921ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner // Update the CFG now. 21021ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner Pred->removeSuccessor(Pred->succ_begin()); 21121ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner while (!MBB->succ_empty()) { 21221ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner Pred->addSuccessor(*(MBB->succ_end()-1)); 21321ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner MBB->removeSuccessor(MBB->succ_end()-1); 21421ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner } 21521ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner return true; 21621ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner } 21721ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner } 21821ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner 21921ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner // If the first instruction in this block is an unconditional branch, and if 22021ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner // there are predecessors, fold the branch into the predecessors. 22121ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner if (!MBB->pred_empty() && isUncondBranch(MBB->begin(), TII)) { 22221ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner MachineInstr *Br = MBB->begin(); 22321ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner assert(Br->getNumOperands() == 1 && Br->getOperand(0).isMachineBasicBlock() 22421ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner && "Uncond branch should take one MBB argument!"); 22521ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner MachineBasicBlock *Dest = Br->getOperand(0).getMachineBasicBlock(); 226edf128a7fa90f2b0b7ee24741a04a7ae1ecd6f7eMisha Brukman 22721ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner while (!MBB->pred_empty()) { 22821ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner MachineBasicBlock *Pred = *(MBB->pred_end()-1); 22921ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner ReplaceUsesOfBlockWith(Pred, MBB, Dest, TII); 23021ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner } 23121ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner return true; 23221ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner } 23321ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner 23421ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner // If the last instruction is an unconditional branch and the fall through 23521ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner // block is the destination, just delete the branch. 23621ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner if (isUncondBranch(--MBB->end(), TII)) { 23721ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner MachineBasicBlock::iterator MI = --MBB->end(); 23821ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner MachineInstr *UncondBr = MI; 2399fd332392c184b13eeb2bd3ffc4347034bc7408aAlkis Evlogimenos MachineFunction::iterator FallThrough = next(MBB); 24021ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner 241dd0458378128b748d4ac6c6035cd47d021faf507Alkis Evlogimenos MachineFunction::iterator UncondDest = 242dd0458378128b748d4ac6c6035cd47d021faf507Alkis Evlogimenos MI->getOperand(0).getMachineBasicBlock(); 243dd0458378128b748d4ac6c6035cd47d021faf507Alkis Evlogimenos if (UncondDest == FallThrough) { 24421ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner // Just delete the branch. This does not effect the CFG. 24521ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner MBB->erase(UncondBr); 24621ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner return true; 24721ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner } 24821ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner 24921ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner // Okay, so we don't have a fall-through. Check to see if we have an 25021ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner // conditional branch that would be a fall through if we reversed it. If 25121ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner // so, invert the condition and delete the uncond branch. 25221ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner if (MI != MBB->begin() && isCondBranch(--MI, TII)) { 25321ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner // We assume that conditional branches always have the branch dest as the 25421ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner // last operand. This could be generalized in the future if needed. 25521ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner unsigned LastOpnd = MI->getNumOperands()-1; 2569fd332392c184b13eeb2bd3ffc4347034bc7408aAlkis Evlogimenos if (MachineFunction::iterator( 2579fd332392c184b13eeb2bd3ffc4347034bc7408aAlkis Evlogimenos MI->getOperand(LastOpnd).getMachineBasicBlock()) == FallThrough) { 25821ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner // Change the cond branch to go to the uncond dest, nuke the uncond, 25921ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner // then reverse the condition. 26021ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner MI->getOperand(LastOpnd).setMachineBasicBlock(UncondDest); 26121ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner MBB->erase(UncondBr); 26221ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner TII.reverseBranchCondition(MI); 26321ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner return true; 26421ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner } 26521ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner } 26621ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner } 267eb15eeec396145b6f5028d07bd2c4a5e903fdec5Chris Lattner#endif 26821ab22e47592d8a4046cfdac844d76b2cb76d711Chris Lattner} 269