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/MachineFunctionPass.h"
21 #include "llvm/Target/TargetInstrInfo.h"
22 #include "llvm/Target/TargetMachine.h"
23 #include "llvm/ADT/STLExtras.h"
27 struct BranchFolder : public MachineFunctionPass {
28 virtual bool runOnMachineFunction(MachineFunction &MF);
29 virtual const char *getPassName() const { return "Branch Folder"; }
31 bool OptimizeBlock(MachineFunction::iterator MBB,
32 const TargetInstrInfo &TII);
34 bool isUncondBranch(const MachineInstr *MI, const TargetInstrInfo &TII) {
35 return TII.isBarrier(MI->getOpcode()) && TII.isBranch(MI->getOpcode());
37 bool isCondBranch(const MachineInstr *MI, const TargetInstrInfo &TII) {
38 return TII.isBranch(MI->getOpcode()) && !TII.isBarrier(MI->getOpcode());
43 FunctionPass *llvm::createBranchFoldingPass() { return new BranchFolder(); }
45 bool BranchFolder::runOnMachineFunction(MachineFunction &MF) {
46 bool EverMadeChange = false;
47 bool MadeChange = true;
48 const TargetInstrInfo &TII = *MF.getTarget().getInstrInfo();
51 for (MachineFunction::iterator MBB = ++MF.begin(), E = MF.end(); MBB != E;
53 MadeChange |= OptimizeBlock(MBB, TII);
55 // If branches were folded away somehow, do a quick scan and delete any dead
58 for (MachineFunction::iterator I = ++MF.begin(), E = MF.end(); I != E; ) {
59 MachineBasicBlock *MBB = I++;
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);
70 EverMadeChange |= MadeChange;
73 return EverMadeChange;
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.
78 static void ReplaceUsesOfBlockWith(MachineBasicBlock *BB,
79 MachineBasicBlock *Old,
80 MachineBasicBlock *New,
81 const TargetInstrInfo &TII) {
82 assert(Old != New && "Cannot replace self with self!");
84 MachineBasicBlock::iterator I = BB->end();
85 while (I != BB->begin()) {
87 if (!TII.isTerminatorInstr(I->getOpcode())) break;
89 // Scan the operands of this machine instruction, replacing any uses of Old
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);
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);
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);
111 bool 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
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);
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()))
137 // Splice the instructions over.
138 Pred->splice(Pred->end(), MBB, MBB->begin(), MBB->end());
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));
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);
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();
162 while (!MBB->pred_empty()) {
163 MachineBasicBlock *Pred = *(MBB->pred_end()-1);
164 ReplaceUsesOfBlockWith(Pred, MBB, Dest, TII);
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);
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);
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);