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