BranchFolding.cpp revision 8f16eb98ed21a642d7f75c76f4b1acf0f199ee6d
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 "llvm/ADT/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 "Control Flow Optimizer"; } 30 const TargetInstrInfo *TII; 31 bool MadeChange; 32 private: 33 void OptimizeBlock(MachineFunction::iterator MBB); 34 }; 35} 36 37FunctionPass *llvm::createBranchFoldingPass() { return new BranchFolder(); } 38 39bool BranchFolder::runOnMachineFunction(MachineFunction &MF) { 40 TII = MF.getTarget().getInstrInfo(); 41 if (!TII) return false; 42 43 44 // DISABLED FOR NOW. 45 return false; 46 47 //MF.dump(); 48 49 bool EverMadeChange = false; 50 MadeChange = true; 51 while (MadeChange) { 52 MadeChange = false; 53 for (MachineFunction::iterator MBB = ++MF.begin(), E = MF.end(); MBB != E; 54 ++MBB) 55 OptimizeBlock(MBB); 56 57 // If branches were folded away somehow, do a quick scan and delete any dead 58 // blocks. 59 if (MadeChange) { 60 for (MachineFunction::iterator I = ++MF.begin(), E = MF.end(); I != E; ) { 61 MachineBasicBlock *MBB = I++; 62 // Is it dead? 63 if (MBB->pred_empty()) { 64 // drop all successors. 65 while (!MBB->succ_empty()) 66 MBB->removeSuccessor(MBB->succ_end()-1); 67 MF.getBasicBlockList().erase(MBB); 68 } 69 } 70 } 71 72 EverMadeChange |= MadeChange; 73 } 74 75 return EverMadeChange; 76} 77 78/// ReplaceUsesOfBlockWith - Given a machine basic block 'BB' that branched to 79/// 'Old', change the code and CFG so that it branches to 'New' instead. 80static void ReplaceUsesOfBlockWith(MachineBasicBlock *BB, 81 MachineBasicBlock *Old, 82 MachineBasicBlock *New, 83 const TargetInstrInfo *TII) { 84 assert(Old != New && "Cannot replace self with self!"); 85 86 MachineBasicBlock::iterator I = BB->end(); 87 while (I != BB->begin()) { 88 --I; 89 if (!TII->isTerminatorInstr(I->getOpcode())) break; 90 91 // Scan the operands of this machine instruction, replacing any uses of Old 92 // with New. 93 for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i) 94 if (I->getOperand(i).isMachineBasicBlock() && 95 I->getOperand(i).getMachineBasicBlock() == Old) 96 I->getOperand(i).setMachineBasicBlock(New); 97 } 98 99 // Update the successor information. 100 std::vector<MachineBasicBlock*> Succs(BB->succ_begin(), BB->succ_end()); 101 for (int i = Succs.size()-1; i >= 0; --i) 102 if (Succs[i] == Old) { 103 BB->removeSuccessor(Old); 104 BB->addSuccessor(New); 105 } 106} 107 108/// OptimizeBlock - Analyze and optimize control flow related to the specified 109/// block. This is never called on the entry block. 110void BranchFolder::OptimizeBlock(MachineFunction::iterator MBB) { 111 // If this block is empty, make everyone use its fall-through, not the block 112 // explicitly. 113 if (MBB->empty()) { 114 if (MBB->pred_empty()) return; // dead block? Leave for cleanup later. 115 116 MachineFunction::iterator FallThrough = next(MBB); 117 118 if (FallThrough != MBB->getParent()->end()) { 119 while (!MBB->pred_empty()) { 120 MachineBasicBlock *Pred = *(MBB->pred_end()-1); 121 ReplaceUsesOfBlockWith(Pred, MBB, FallThrough, TII); 122 } 123 MadeChange = true; 124 } 125 // TODO: CHANGE STUFF TO NOT BRANCH HERE! 126 return; 127 } 128 129 // Check to see if we can simplify the terminator of the block before this 130 // one. 131#if 0 132 MachineBasicBlock *PriorTBB = 0, *PriorFBB = 0; 133 std::vector<MachineOperand> PriorCond; 134 if (!TII->AnalyzeBranch(*prior(MBB), PriorTBB, PriorFBB, PriorCond)) { 135 // If the previous branch is conditional and both conditions go to the same 136 // destination, remove the branch, replacing it with an unconditional one. 137 if (PriorTBB && PriorTBB == PriorFBB) { 138 TII->RemoveBranch(*prior(MBB)); 139 PriorCond.clear(); 140 if (PriorTBB != &*MBB) 141 TII->InsertBranch(*prior(MBB), PriorTBB, 0, PriorCond); 142 MadeChange = true; 143 return OptimizeBlock(MBB); 144 } 145 146 // If the previous branch *only* branches to *this* block (conditional or 147 // not) remove the branch. 148 if (PriorTBB == &*MBB && PriorFBB == 0) { 149 TII->RemoveBranch(*prior(MBB)); 150 MadeChange = true; 151 return OptimizeBlock(MBB); 152 } 153 } 154#endif 155 156 157#if 0 158 159 if (MBB->pred_size() == 1) { 160 // If this block has a single predecessor, and if that block has a single 161 // successor, merge this block into that block. 162 MachineBasicBlock *Pred = *MBB->pred_begin(); 163 if (Pred->succ_size() == 1) { 164 // Delete all of the terminators from end of the pred block. NOTE, this 165 // assumes that terminators do not have side effects! 166 // FIXME: This doesn't work for FP_REG_KILL. 167 168 while (!Pred->empty() && TII.isTerminatorInstr(Pred->back().getOpcode())) 169 Pred->pop_back(); 170 171 // Splice the instructions over. 172 Pred->splice(Pred->end(), MBB, MBB->begin(), MBB->end()); 173 174 // If MBB does not end with a barrier, add a goto instruction to the end. 175 if (Pred->empty() || !TII.isBarrier(Pred->back().getOpcode())) 176 TII.insertGoto(*Pred, *next(MBB)); 177 178 // Update the CFG now. 179 Pred->removeSuccessor(Pred->succ_begin()); 180 while (!MBB->succ_empty()) { 181 Pred->addSuccessor(*(MBB->succ_end()-1)); 182 MBB->removeSuccessor(MBB->succ_end()-1); 183 } 184 return true; 185 } 186 } 187 188 // If BB falls through into Old, insert an unconditional branch to New. 189 MachineFunction::iterator BBSucc = BB; ++BBSucc; 190 if (BBSucc != BB->getParent()->end() && &*BBSucc == Old) 191 TII.insertGoto(*BB, *New); 192 193 194 if (MBB->pred_size() == 1) { 195 // If this block has a single predecessor, and if that block has a single 196 // successor, merge this block into that block. 197 MachineBasicBlock *Pred = *MBB->pred_begin(); 198 if (Pred->succ_size() == 1) { 199 // Delete all of the terminators from end of the pred block. NOTE, this 200 // assumes that terminators do not have side effects! 201 // FIXME: This doesn't work for FP_REG_KILL. 202 203 while (!Pred->empty() && TII.isTerminatorInstr(Pred->back().getOpcode())) 204 Pred->pop_back(); 205 206 // Splice the instructions over. 207 Pred->splice(Pred->end(), MBB, MBB->begin(), MBB->end()); 208 209 // If MBB does not end with a barrier, add a goto instruction to the end. 210 if (Pred->empty() || !TII.isBarrier(Pred->back().getOpcode())) 211 TII.insertGoto(*Pred, *next(MBB)); 212 213 // Update the CFG now. 214 Pred->removeSuccessor(Pred->succ_begin()); 215 while (!MBB->succ_empty()) { 216 Pred->addSuccessor(*(MBB->succ_end()-1)); 217 MBB->removeSuccessor(MBB->succ_end()-1); 218 } 219 return true; 220 } 221 } 222 223 // If the first instruction in this block is an unconditional branch, and if 224 // there are predecessors, fold the branch into the predecessors. 225 if (!MBB->pred_empty() && isUncondBranch(MBB->begin(), TII)) { 226 MachineInstr *Br = MBB->begin(); 227 assert(Br->getNumOperands() == 1 && Br->getOperand(0).isMachineBasicBlock() 228 && "Uncond branch should take one MBB argument!"); 229 MachineBasicBlock *Dest = Br->getOperand(0).getMachineBasicBlock(); 230 231 while (!MBB->pred_empty()) { 232 MachineBasicBlock *Pred = *(MBB->pred_end()-1); 233 ReplaceUsesOfBlockWith(Pred, MBB, Dest, TII); 234 } 235 return true; 236 } 237 238 // If the last instruction is an unconditional branch and the fall through 239 // block is the destination, just delete the branch. 240 if (isUncondBranch(--MBB->end(), TII)) { 241 MachineBasicBlock::iterator MI = --MBB->end(); 242 MachineInstr *UncondBr = MI; 243 MachineFunction::iterator FallThrough = next(MBB); 244 245 MachineFunction::iterator UncondDest = 246 MI->getOperand(0).getMachineBasicBlock(); 247 if (UncondDest == FallThrough) { 248 // Just delete the branch. This does not effect the CFG. 249 MBB->erase(UncondBr); 250 return true; 251 } 252 253 // Okay, so we don't have a fall-through. Check to see if we have an 254 // conditional branch that would be a fall through if we reversed it. If 255 // so, invert the condition and delete the uncond branch. 256 if (MI != MBB->begin() && isCondBranch(--MI, TII)) { 257 // We assume that conditional branches always have the branch dest as the 258 // last operand. This could be generalized in the future if needed. 259 unsigned LastOpnd = MI->getNumOperands()-1; 260 if (MachineFunction::iterator( 261 MI->getOperand(LastOpnd).getMachineBasicBlock()) == FallThrough) { 262 // Change the cond branch to go to the uncond dest, nuke the uncond, 263 // then reverse the condition. 264 MI->getOperand(LastOpnd).setMachineBasicBlock(UncondDest); 265 MBB->erase(UncondBr); 266 TII.reverseBranchCondition(MI); 267 return true; 268 } 269 } 270 } 271#endif 272} 273