lib/CodeGen/BranchFolding.cpp

   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 "Support/STLExtras.h"
  24 using namespace llvm;
  25
  26 namespace {
  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
  43 FunctionPass *llvm::createBranchFoldingPass() { return new BranchFolder(); }
  44
  45 bool 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.
  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!");
  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
 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
 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 }