LLVM API Documentation
00001 //===-- BranchFolding.cpp - Fold machine code branch instructions ---------===// 00002 // 00003 // The LLVM Compiler Infrastructure 00004 // 00005 // This file was developed by the LLVM research group and is distributed under 00006 // the University of Illinois Open Source License. See LICENSE.TXT for details. 00007 // 00008 //===----------------------------------------------------------------------===// 00009 // 00010 // This pass forwards branches to unconditional branches to make them branch 00011 // directly to the target block. This pass often results in dead MBB's, which 00012 // it then removes. 00013 // 00014 // Note that this pass must be run after register allocation, it cannot handle 00015 // SSA form. 00016 // 00017 //===----------------------------------------------------------------------===// 00018 00019 #include "llvm/CodeGen/Passes.h" 00020 #include "llvm/CodeGen/MachineFunctionPass.h" 00021 #include "llvm/Target/TargetInstrInfo.h" 00022 #include "llvm/Target/TargetMachine.h" 00023 #include "llvm/ADT/STLExtras.h" 00024 using namespace llvm; 00025 00026 namespace { 00027 struct BranchFolder : public MachineFunctionPass { 00028 virtual bool runOnMachineFunction(MachineFunction &MF); 00029 virtual const char *getPassName() const { return "Branch Folder"; } 00030 private: 00031 bool OptimizeBlock(MachineFunction::iterator MBB, 00032 const TargetInstrInfo &TII); 00033 00034 bool isUncondBranch(const MachineInstr *MI, const TargetInstrInfo &TII) { 00035 return TII.isBarrier(MI->getOpcode()) && TII.isBranch(MI->getOpcode()); 00036 } 00037 bool isCondBranch(const MachineInstr *MI, const TargetInstrInfo &TII) { 00038 return TII.isBranch(MI->getOpcode()) && !TII.isBarrier(MI->getOpcode()); 00039 } 00040 }; 00041 } 00042 00043 FunctionPass *llvm::createBranchFoldingPass() { return new BranchFolder(); } 00044 00045 bool BranchFolder::runOnMachineFunction(MachineFunction &MF) { 00046 bool EverMadeChange = false; 00047 bool MadeChange = true; 00048 const TargetInstrInfo &TII = *MF.getTarget().getInstrInfo(); 00049 while (MadeChange) { 00050 MadeChange = false; 00051 for (MachineFunction::iterator MBB = ++MF.begin(), E = MF.end(); MBB != E; 00052 ++MBB) 00053 MadeChange |= OptimizeBlock(MBB, TII); 00054 00055 // If branches were folded away somehow, do a quick scan and delete any dead 00056 // blocks. 00057 if (MadeChange) { 00058 for (MachineFunction::iterator I = ++MF.begin(), E = MF.end(); I != E; ) { 00059 MachineBasicBlock *MBB = I++; 00060 // Is it dead? 00061 if (MBB->pred_empty()) { 00062 // drop all successors. 00063 while (!MBB->succ_empty()) 00064 MBB->removeSuccessor(MBB->succ_end()-1); 00065 MF.getBasicBlockList().erase(MBB); 00066 } 00067 } 00068 } 00069 00070 EverMadeChange |= MadeChange; 00071 } 00072 00073 return EverMadeChange; 00074 } 00075 00076 /// ReplaceUsesOfBlockWith - Given a machine basic block 'BB' that branched to 00077 /// 'Old', change the code and CFG so that it branches to 'New' instead. 00078 static void ReplaceUsesOfBlockWith(MachineBasicBlock *BB, 00079 MachineBasicBlock *Old, 00080 MachineBasicBlock *New, 00081 const TargetInstrInfo &TII) { 00082 assert(Old != New && "Cannot replace self with self!"); 00083 00084 MachineBasicBlock::iterator I = BB->end(); 00085 while (I != BB->begin()) { 00086 --I; 00087 if (!TII.isTerminatorInstr(I->getOpcode())) break; 00088 00089 // Scan the operands of this machine instruction, replacing any uses of Old 00090 // with New. 00091 for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i) 00092 if (I->getOperand(i).isMachineBasicBlock() && 00093 I->getOperand(i).getMachineBasicBlock() == Old) 00094 I->getOperand(i).setMachineBasicBlock(New); 00095 } 00096 00097 // If BB falls through into Old, insert an unconditional branch to New. 00098 MachineFunction::iterator BBSucc = BB; ++BBSucc; 00099 if (BBSucc != BB->getParent()->end() && &*BBSucc == Old) 00100 TII.insertGoto(*BB, *New); 00101 00102 std::vector<MachineBasicBlock*> Succs(BB->succ_begin(), BB->succ_end()); 00103 for (int i = Succs.size()-1; i >= 0; --i) 00104 if (Succs[i] == Old) { 00105 BB->removeSuccessor(Old); 00106 BB->addSuccessor(New); 00107 } 00108 } 00109 00110 00111 bool BranchFolder::OptimizeBlock(MachineFunction::iterator MBB, 00112 const TargetInstrInfo &TII) { 00113 // If this block is empty, make everyone use it's fall-through, not the block 00114 // explicitly. 00115 if (MBB->empty()) { 00116 if (MBB->pred_empty()) return false; 00117 MachineFunction::iterator FallThrough =next(MBB); 00118 assert(FallThrough != MBB->getParent()->end() && 00119 "Fell off the end of the function!"); 00120 while (!MBB->pred_empty()) { 00121 MachineBasicBlock *Pred = *(MBB->pred_end()-1); 00122 ReplaceUsesOfBlockWith(Pred, MBB, FallThrough, TII); 00123 } 00124 return true; 00125 } 00126 00127 if (MBB->pred_size() == 1) { 00128 // If this block has a single predecessor, and if that block has a single 00129 // successor, merge this block into that block. 00130 MachineBasicBlock *Pred = *MBB->pred_begin(); 00131 if (Pred->succ_size() == 1) { 00132 // Delete all of the terminators from end of the pred block. NOTE, this 00133 // assumes that terminators do not have side effects! 00134 while (!Pred->empty() && TII.isTerminatorInstr(Pred->back().getOpcode())) 00135 Pred->pop_back(); 00136 00137 // Splice the instructions over. 00138 Pred->splice(Pred->end(), MBB, MBB->begin(), MBB->end()); 00139 00140 // If MBB does not end with a barrier, add a goto instruction to the end. 00141 if (Pred->empty() || !TII.isBarrier(Pred->back().getOpcode())) 00142 TII.insertGoto(*Pred, *next(MBB)); 00143 00144 // Update the CFG now. 00145 Pred->removeSuccessor(Pred->succ_begin()); 00146 while (!MBB->succ_empty()) { 00147 Pred->addSuccessor(*(MBB->succ_end()-1)); 00148 MBB->removeSuccessor(MBB->succ_end()-1); 00149 } 00150 return true; 00151 } 00152 } 00153 00154 // If the first instruction in this block is an unconditional branch, and if 00155 // there are predecessors, fold the branch into the predecessors. 00156 if (!MBB->pred_empty() && isUncondBranch(MBB->begin(), TII)) { 00157 MachineInstr *Br = MBB->begin(); 00158 assert(Br->getNumOperands() == 1 && Br->getOperand(0).isMachineBasicBlock() 00159 && "Uncond branch should take one MBB argument!"); 00160 MachineBasicBlock *Dest = Br->getOperand(0).getMachineBasicBlock(); 00161 00162 while (!MBB->pred_empty()) { 00163 MachineBasicBlock *Pred = *(MBB->pred_end()-1); 00164 ReplaceUsesOfBlockWith(Pred, MBB, Dest, TII); 00165 } 00166 return true; 00167 } 00168 00169 // If the last instruction is an unconditional branch and the fall through 00170 // block is the destination, just delete the branch. 00171 if (isUncondBranch(--MBB->end(), TII)) { 00172 MachineBasicBlock::iterator MI = --MBB->end(); 00173 MachineInstr *UncondBr = MI; 00174 MachineFunction::iterator FallThrough = next(MBB); 00175 00176 MachineFunction::iterator UncondDest = 00177 MI->getOperand(0).getMachineBasicBlock(); 00178 if (UncondDest == FallThrough) { 00179 // Just delete the branch. This does not effect the CFG. 00180 MBB->erase(UncondBr); 00181 return true; 00182 } 00183 00184 // Okay, so we don't have a fall-through. Check to see if we have an 00185 // conditional branch that would be a fall through if we reversed it. If 00186 // so, invert the condition and delete the uncond branch. 00187 if (MI != MBB->begin() && isCondBranch(--MI, TII)) { 00188 // We assume that conditional branches always have the branch dest as the 00189 // last operand. This could be generalized in the future if needed. 00190 unsigned LastOpnd = MI->getNumOperands()-1; 00191 if (MachineFunction::iterator( 00192 MI->getOperand(LastOpnd).getMachineBasicBlock()) == FallThrough) { 00193 // Change the cond branch to go to the uncond dest, nuke the uncond, 00194 // then reverse the condition. 00195 MI->getOperand(LastOpnd).setMachineBasicBlock(UncondDest); 00196 MBB->erase(UncondBr); 00197 TII.reverseBranchCondition(MI); 00198 return true; 00199 } 00200 } 00201 } 00202 00203 return false; 00204 }