BranchFolding.cpp revision edf128a7fa90f2b0b7ee24741a04a7ae1ecd6f7e 
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 "Branch Folder"; }
30  private:
31    bool OptimizeBlock(MachineFunction::iterator MBB,
32                       const TargetInstrInfo &TII);
33
34    bool isUncondBranch(const MachineInstr *MI, const TargetInstrInfo &TII) {
35      return TII.isBarrier(MI->getOpcode()) && TII.isBranch(MI->getOpcode());
36    }
37    bool isCondBranch(const MachineInstr *MI, const TargetInstrInfo &TII) {
38      return TII.isBranch(MI->getOpcode()) && !TII.isBarrier(MI->getOpcode());
39    }
40  };
41}
42
43FunctionPass *llvm::createBranchFoldingPass() { return new BranchFolder(); }
44
45bool BranchFolder::runOnMachineFunction(MachineFunction &MF) {
46  bool EverMadeChange = false;
47  bool MadeChange = true;
48  const TargetInstrInfo &TII = *MF.getTarget().getInstrInfo();
49  while (MadeChange) {
50    MadeChange = false;
51    for (MachineFunction::iterator MBB = ++MF.begin(), E = MF.end(); MBB != E;
52         ++MBB)
53      MadeChange |= OptimizeBlock(MBB, TII);
54
55    // If branches were folded away somehow, do a quick scan and delete any dead
56    // blocks.
57    if (MadeChange) {
58      for (MachineFunction::iterator I = ++MF.begin(), E = MF.end(); I != E; ) {
59        MachineBasicBlock *MBB = I++;
60        // Is it dead?
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);
66        }
67      }
68    }
69
70    EverMadeChange |= MadeChange;
71  }
72
73  return EverMadeChange;
74}
75
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.
78static void ReplaceUsesOfBlockWith(MachineBasicBlock *BB,
79                                   MachineBasicBlock *Old,
80                                   MachineBasicBlock *New,
81                                   const TargetInstrInfo &TII) {
82  assert(Old != New && "Cannot replace self with self!");
83
84  MachineBasicBlock::iterator I = BB->end();
85  while (I != BB->begin()) {
86    --I;
87    if (!TII.isTerminatorInstr(I->getOpcode())) break;
88
89    // Scan the operands of this machine instruction, replacing any uses of Old
90    // with New.
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);
95  }
96
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);
101
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);
107    }
108}
109
110
111bool 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
114  // explicitly.
115  if (MBB->empty()) {
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);
123    }
124    return true;
125  }
126
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()))
135        Pred->pop_back();
136
137      // Splice the instructions over.
138      Pred->splice(Pred->end(), MBB, MBB->begin(), MBB->end());
139
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));
143
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);
149      }
150      return true;
151    }
152  }
153
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();
161
162    while (!MBB->pred_empty()) {
163      MachineBasicBlock *Pred = *(MBB->pred_end()-1);
164      ReplaceUsesOfBlockWith(Pred, MBB, Dest, TII);
165    }
166    return true;
167  }
168
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);
175
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);
181      return true;
182    }
183
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);
198        return true;
199      }
200    }
201  }
202
203  return false;
204}
205