1 //===-- BranchFolding.cpp - Fold machine code branch instructions ---------===//
3 // The LLVM Compiler Infrastructure
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.
8 //===----------------------------------------------------------------------===//
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
14 // Note that this pass must be run after register allocation, it cannot handle
17 //===----------------------------------------------------------------------===//
19 #include "llvm/CodeGen/Passes.h"
20 #include "llvm/CodeGen/MachineDebugInfo.h"
21 #include "llvm/CodeGen/MachineFunctionPass.h"
22 #include "llvm/CodeGen/MachineJumpTableInfo.h"
23 #include "llvm/Target/TargetInstrInfo.h"
24 #include "llvm/Target/TargetMachine.h"
25 #include "llvm/ADT/STLExtras.h"
29 struct BranchFolder : public MachineFunctionPass {
30 virtual bool runOnMachineFunction(MachineFunction &MF);
31 virtual const char *getPassName() const { return "Control Flow Optimizer"; }
32 const TargetInstrInfo *TII;
33 MachineDebugInfo *MDI;
36 void OptimizeBlock(MachineFunction::iterator MBB);
37 void RemoveDeadBlock(MachineBasicBlock *MBB);
41 FunctionPass *llvm::createBranchFoldingPass() { return new BranchFolder(); }
43 /// RemoveDeadBlock - Remove the specified dead machine basic block from the
44 /// function, updating the CFG.
45 void BranchFolder::RemoveDeadBlock(MachineBasicBlock *MBB) {
46 assert(MBB->pred_empty() && "MBB must be dead!");
48 MachineFunction *MF = MBB->getParent();
49 // drop all successors.
50 while (!MBB->succ_empty())
51 MBB->removeSuccessor(MBB->succ_end()-1);
53 // If there is DWARF info to active, check to see if there are any DWARF_LABEL
54 // records in the basic block. If so, unregister them from MachineDebugInfo.
55 if (MDI && !MBB->empty()) {
56 unsigned DWARF_LABELOpc = TII->getDWARF_LABELOpcode();
57 assert(DWARF_LABELOpc &&
58 "Target supports dwarf but didn't implement getDWARF_LABELOpcode!");
60 for (MachineBasicBlock::iterator I = MBB->begin(), E = MBB->end();
62 if ((unsigned)I->getOpcode() == DWARF_LABELOpc) {
63 // The label ID # is always operand #0, an immediate.
64 MDI->RemoveLabelInfo(I->getOperand(0).getImm());
70 MF->getBasicBlockList().erase(MBB);
73 bool BranchFolder::runOnMachineFunction(MachineFunction &MF) {
74 TII = MF.getTarget().getInstrInfo();
75 if (!TII) return false;
77 MDI = getAnalysisToUpdate<MachineDebugInfo>();
79 bool EverMadeChange = false;
84 for (MachineFunction::iterator I = ++MF.begin(), E = MF.end(); I != E; ) {
85 MachineBasicBlock *MBB = I++;
88 // If it is dead, remove it.
89 if (MBB->pred_empty()) {
94 EverMadeChange |= MadeChange;
97 return EverMadeChange;
100 /// ReplaceUsesOfBlockWith - Given a machine basic block 'BB' that branched to
101 /// 'Old', change the code and CFG so that it branches to 'New' instead.
102 static void ReplaceUsesOfBlockWith(MachineBasicBlock *BB,
103 MachineBasicBlock *Old,
104 MachineBasicBlock *New,
105 const TargetInstrInfo *TII) {
106 assert(Old != New && "Cannot replace self with self!");
108 MachineBasicBlock::iterator I = BB->end();
109 while (I != BB->begin()) {
111 if (!TII->isTerminatorInstr(I->getOpcode())) break;
113 // Scan the operands of this machine instruction, replacing any uses of Old
115 for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i)
116 if (I->getOperand(i).isMachineBasicBlock() &&
117 I->getOperand(i).getMachineBasicBlock() == Old)
118 I->getOperand(i).setMachineBasicBlock(New);
121 // Update the successor information.
122 std::vector<MachineBasicBlock*> Succs(BB->succ_begin(), BB->succ_end());
123 for (int i = Succs.size()-1; i >= 0; --i)
124 if (Succs[i] == Old) {
125 BB->removeSuccessor(Old);
126 BB->addSuccessor(New);
130 /// OptimizeBlock - Analyze and optimize control flow related to the specified
131 /// block. This is never called on the entry block.
132 void BranchFolder::OptimizeBlock(MachineFunction::iterator MBB) {
133 // If this block is empty, make everyone use its fall-through, not the block
136 if (MBB->pred_empty()) return; // dead block? Leave for cleanup later.
138 MachineFunction::iterator FallThrough = next(MBB);
140 if (FallThrough == MBB->getParent()->end()) {
141 // TODO: Simplify preds to not branch here if possible!
143 // Rewrite all predecessors of the old block to go to the fallthrough
145 while (!MBB->pred_empty()) {
146 MachineBasicBlock *Pred = *(MBB->pred_end()-1);
147 ReplaceUsesOfBlockWith(Pred, MBB, FallThrough, TII);
150 // If MBB was the target of a jump table, update jump tables to go to the
151 // fallthrough instead.
152 MBB->getParent()->getJumpTableInfo()->ReplaceMBBInJumpTables(MBB,
159 // Check to see if we can simplify the terminator of the block before this
161 MachineBasicBlock &PrevBB = *prior(MBB);
163 MachineBasicBlock *PriorTBB = 0, *PriorFBB = 0;
164 std::vector<MachineOperand> PriorCond;
165 if (!TII->AnalyzeBranch(PrevBB, PriorTBB, PriorFBB, PriorCond)) {
166 // If the previous branch is conditional and both conditions go to the same
167 // destination, remove the branch, replacing it with an unconditional one.
168 if (PriorTBB && PriorTBB == PriorFBB) {
169 TII->RemoveBranch(*prior(MBB));
171 if (PriorTBB != &*MBB)
172 TII->InsertBranch(*prior(MBB), PriorTBB, 0, PriorCond);
174 return OptimizeBlock(MBB);
177 // If the previous branch *only* branches to *this* block (conditional or
178 // not) remove the branch.
179 if (PriorTBB == &*MBB && PriorFBB == 0) {
180 TII->RemoveBranch(*prior(MBB));
182 return OptimizeBlock(MBB);
188 if (MBB->pred_size() == 1) {
189 // If this block has a single predecessor, and if that block has a single
190 // successor, merge this block into that block.
191 MachineBasicBlock *Pred = *MBB->pred_begin();
192 if (Pred->succ_size() == 1) {
193 // Delete all of the terminators from end of the pred block. NOTE, this
194 // assumes that terminators do not have side effects!
195 // FIXME: This doesn't work for FP_REG_KILL.
197 while (!Pred->empty() && TII.isTerminatorInstr(Pred->back().getOpcode()))
200 // Splice the instructions over.
201 Pred->splice(Pred->end(), MBB, MBB->begin(), MBB->end());
203 // If MBB does not end with a barrier, add a goto instruction to the end.
204 if (Pred->empty() || !TII.isBarrier(Pred->back().getOpcode()))
205 TII.insertGoto(*Pred, *next(MBB));
207 // Update the CFG now.
208 Pred->removeSuccessor(Pred->succ_begin());
209 while (!MBB->succ_empty()) {
210 Pred->addSuccessor(*(MBB->succ_end()-1));
211 MBB->removeSuccessor(MBB->succ_end()-1);
217 // If BB falls through into Old, insert an unconditional branch to New.
218 MachineFunction::iterator BBSucc = BB; ++BBSucc;
219 if (BBSucc != BB->getParent()->end() && &*BBSucc == Old)
220 TII.insertGoto(*BB, *New);
223 if (MBB->pred_size() == 1) {
224 // If this block has a single predecessor, and if that block has a single
225 // successor, merge this block into that block.
226 MachineBasicBlock *Pred = *MBB->pred_begin();
227 if (Pred->succ_size() == 1) {
228 // Delete all of the terminators from end of the pred block. NOTE, this
229 // assumes that terminators do not have side effects!
230 // FIXME: This doesn't work for FP_REG_KILL.
232 while (!Pred->empty() && TII.isTerminatorInstr(Pred->back().getOpcode()))
235 // Splice the instructions over.
236 Pred->splice(Pred->end(), MBB, MBB->begin(), MBB->end());
238 // If MBB does not end with a barrier, add a goto instruction to the end.
239 if (Pred->empty() || !TII.isBarrier(Pred->back().getOpcode()))
240 TII.insertGoto(*Pred, *next(MBB));
242 // Update the CFG now.
243 Pred->removeSuccessor(Pred->succ_begin());
244 while (!MBB->succ_empty()) {
245 Pred->addSuccessor(*(MBB->succ_end()-1));
246 MBB->removeSuccessor(MBB->succ_end()-1);
252 // If the first instruction in this block is an unconditional branch, and if
253 // there are predecessors, fold the branch into the predecessors.
254 if (!MBB->pred_empty() && isUncondBranch(MBB->begin(), TII)) {
255 MachineInstr *Br = MBB->begin();
256 assert(Br->getNumOperands() == 1 && Br->getOperand(0).isMachineBasicBlock()
257 && "Uncond branch should take one MBB argument!");
258 MachineBasicBlock *Dest = Br->getOperand(0).getMachineBasicBlock();
260 while (!MBB->pred_empty()) {
261 MachineBasicBlock *Pred = *(MBB->pred_end()-1);
262 ReplaceUsesOfBlockWith(Pred, MBB, Dest, TII);
267 // If the last instruction is an unconditional branch and the fall through
268 // block is the destination, just delete the branch.
269 if (isUncondBranch(--MBB->end(), TII)) {
270 MachineBasicBlock::iterator MI = --MBB->end();
271 MachineInstr *UncondBr = MI;
272 MachineFunction::iterator FallThrough = next(MBB);
274 MachineFunction::iterator UncondDest =
275 MI->getOperand(0).getMachineBasicBlock();
276 if (UncondDest == FallThrough) {
277 // Just delete the branch. This does not effect the CFG.
278 MBB->erase(UncondBr);
282 // Okay, so we don't have a fall-through. Check to see if we have an
283 // conditional branch that would be a fall through if we reversed it. If
284 // so, invert the condition and delete the uncond branch.
285 if (MI != MBB->begin() && isCondBranch(--MI, TII)) {
286 // We assume that conditional branches always have the branch dest as the
287 // last operand. This could be generalized in the future if needed.
288 unsigned LastOpnd = MI->getNumOperands()-1;
289 if (MachineFunction::iterator(
290 MI->getOperand(LastOpnd).getMachineBasicBlock()) == FallThrough) {
291 // Change the cond branch to go to the uncond dest, nuke the uncond,
292 // then reverse the condition.
293 MI->getOperand(LastOpnd).setMachineBasicBlock(UncondDest);
294 MBB->erase(UncondBr);
295 TII.reverseBranchCondition(MI);