BranchFolding.cpp revision 4ae131e5da124bb5f7455133fefb1fa3b336192b
1//===-- BranchFolding.cpp - Fold machine code branch instructions ---------===// 2// 3// The LLVM Compiler Infrastructure 4// 5// This file was developed by the LLVM research group and is distributed under 6// the University of Illinois Open Source License. See LICENSE.TXT for details. 7// 8//===----------------------------------------------------------------------===// 9// 10// This pass forwards branches to unconditional branches to make them branch 11// directly to the target block. This pass often results in dead MBB's, which 12// it then removes. 13// 14// Note that this pass must be run after register allocation, it cannot handle 15// SSA form. 16// 17//===----------------------------------------------------------------------===// 18 19#include "llvm/CodeGen/Passes.h" 20#include "llvm/CodeGen/MachineFunctionPass.h" 21#include "llvm/Target/TargetInstrInfo.h" 22#include "llvm/Target/TargetMachine.h" 23#include "Support/STLExtras.h" 24using namespace llvm; 25 26namespace { 27 struct BranchFolder : public MachineFunctionPass { 28 virtual bool runOnMachineFunction(MachineFunction &MF); 29 virtual const char *getPassName() const { return "Branch Folder"; } 30 private: 31 bool OptimizeBlock(MachineFunction::iterator MBB, 32 const TargetInstrInfo &TII); 33 34 bool isUncondBranch(const MachineInstr *MI, const TargetInstrInfo &TII) { 35 return TII.isBarrier(MI->getOpcode()) && TII.isBranch(MI->getOpcode()); 36 } 37 bool isCondBranch(const MachineInstr *MI, const TargetInstrInfo &TII) { 38 return TII.isBranch(MI->getOpcode()) && !TII.isBarrier(MI->getOpcode()); 39 } 40 }; 41} 42 43FunctionPass *llvm::createBranchFoldingPass() { return new BranchFolder(); } 44 45bool BranchFolder::runOnMachineFunction(MachineFunction &MF) { 46 bool EverMadeChange = false; 47 bool MadeChange = true; 48 const TargetInstrInfo &TII = *MF.getTarget().getInstrInfo(); 49 while (MadeChange) { 50 MadeChange = false; 51 for (MachineFunction::iterator MBB = ++MF.begin(), E = MF.end(); MBB != E; 52 ++MBB) 53 MadeChange |= OptimizeBlock(MBB, TII); 54 55 // If branches were folded away somehow, do a quick scan and delete any dead 56 // blocks. 57 if (MadeChange) { 58 for (MachineFunction::iterator I = ++MF.begin(), E = MF.end(); I != E; ) { 59 MachineBasicBlock *MBB = I++; 60 // Is it dead? 61 if (MBB->pred_empty()) { 62 // drop all successors. 63 while (!MBB->succ_empty()) 64 MBB->removeSuccessor(MBB->succ_end()-1); 65 MF.getBasicBlockList().erase(MBB); 66 } 67 } 68 } 69 70 EverMadeChange |= MadeChange; 71 } 72 73 return EverMadeChange; 74} 75 76/// ReplaceUsesOfBlockWith - Given a machine basic block 'BB' that branched to 77/// 'Old', change the code and CFG so that it branches to 'New' instead. 78static void ReplaceUsesOfBlockWith(MachineBasicBlock *BB, 79 MachineBasicBlock *Old, 80 MachineBasicBlock *New, 81 const TargetInstrInfo &TII) { 82 assert(Old != New && "Cannot replace self with self!"); 83 84 MachineBasicBlock::iterator I = BB->end(); 85 while (I != BB->begin()) { 86 --I; 87 if (!TII.isTerminatorInstr(I->getOpcode())) break; 88 89 // Scan the operands of this machine instruction, replacing any uses of Old 90 // with New. 91 for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i) 92 if (I->getOperand(i).isMachineBasicBlock() && 93 I->getOperand(i).getMachineBasicBlock() == Old) 94 I->getOperand(i).setMachineBasicBlock(New); 95 } 96 97 // If BB falls through into Old, insert an unconditional branch to New. 98 MachineFunction::iterator BBSucc = BB; ++BBSucc; 99 if (BBSucc != BB->getParent()->end() && &*BBSucc == Old) 100 TII.insertGoto(*BB, *New); 101 102 std::vector<MachineBasicBlock*> Succs(BB->succ_begin(), BB->succ_end()); 103 for (int i = Succs.size()-1; i >= 0; --i) 104 if (Succs[i] == Old) { 105 BB->removeSuccessor(Old); 106 BB->addSuccessor(New); 107 } 108} 109 110 111bool BranchFolder::OptimizeBlock(MachineFunction::iterator MBB, 112 const TargetInstrInfo &TII) { 113 // If this block is empty, make everyone use it's fall-through, not the block 114 // explicitly. 115 if (MBB->empty()) { 116 if (MBB->pred_empty()) return false; 117 MachineFunction::iterator FallThrough =next(MBB); 118 assert(FallThrough != MBB->getParent()->end() && 119 "Fell off the end of the function!"); 120 while (!MBB->pred_empty()) { 121 MachineBasicBlock *Pred = *(MBB->pred_end()-1); 122 ReplaceUsesOfBlockWith(Pred, MBB, FallThrough, TII); 123 } 124 return true; 125 } 126 127 if (MBB->pred_size() == 1) { 128 // If this block has a single predecessor, and if that block has a single 129 // successor, merge this block into that block. 130 MachineBasicBlock *Pred = *MBB->pred_begin(); 131 if (Pred->succ_size() == 1) { 132 // Delete all of the terminators from end of the pred block. NOTE, this 133 // assumes that terminators do not have side effects! 134 while (!Pred->empty() && TII.isTerminatorInstr(Pred->back().getOpcode())) 135 Pred->pop_back(); 136 137 // Splice the instructions over. 138 Pred->splice(Pred->end(), MBB, MBB->begin(), MBB->end()); 139 140 // If MBB does not end with a barrier, add a goto instruction to the end. 141 if (Pred->empty() || !TII.isBarrier(Pred->back().getOpcode())) 142 TII.insertGoto(*Pred, *next(MBB)); 143 144 // Update the CFG now. 145 Pred->removeSuccessor(Pred->succ_begin()); 146 while (!MBB->succ_empty()) { 147 Pred->addSuccessor(*(MBB->succ_end()-1)); 148 MBB->removeSuccessor(MBB->succ_end()-1); 149 } 150 return true; 151 } 152 } 153 154 // If the first instruction in this block is an unconditional branch, and if 155 // there are predecessors, fold the branch into the predecessors. 156 if (!MBB->pred_empty() && isUncondBranch(MBB->begin(), TII)) { 157 MachineInstr *Br = MBB->begin(); 158 assert(Br->getNumOperands() == 1 && Br->getOperand(0).isMachineBasicBlock() 159 && "Uncond branch should take one MBB argument!"); 160 MachineBasicBlock *Dest = Br->getOperand(0).getMachineBasicBlock(); 161 162 while (!MBB->pred_empty()) { 163 MachineBasicBlock *Pred = *(MBB->pred_end()-1); 164 ReplaceUsesOfBlockWith(Pred, MBB, Dest, TII); 165 } 166 return true; 167 } 168 169 // If the last instruction is an unconditional branch and the fall through 170 // block is the destination, just delete the branch. 171 if (isUncondBranch(--MBB->end(), TII)) { 172 MachineBasicBlock::iterator MI = --MBB->end(); 173 MachineInstr *UncondBr = MI; 174 MachineFunction::iterator FallThrough = next(MBB); 175 176 MachineFunction::iterator UncondDest = 177 MI->getOperand(0).getMachineBasicBlock(); 178 if (UncondDest == FallThrough) { 179 // Just delete the branch. This does not effect the CFG. 180 MBB->erase(UncondBr); 181 return true; 182 } 183 184 // Okay, so we don't have a fall-through. Check to see if we have an 185 // conditional branch that would be a fall through if we reversed it. If 186 // so, invert the condition and delete the uncond branch. 187 if (MI != MBB->begin() && isCondBranch(--MI, TII)) { 188 // We assume that conditional branches always have the branch dest as the 189 // last operand. This could be generalized in the future if needed. 190 unsigned LastOpnd = MI->getNumOperands()-1; 191 if (MachineFunction::iterator( 192 MI->getOperand(LastOpnd).getMachineBasicBlock()) == FallThrough) { 193 // Change the cond branch to go to the uncond dest, nuke the uncond, 194 // then reverse the condition. 195 MI->getOperand(LastOpnd).setMachineBasicBlock(UncondDest); 196 MBB->erase(UncondBr); 197 TII.reverseBranchCondition(MI); 198 return true; 199 } 200 } 201 } 202 203 return false; 204} 205