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 "llvm/ADT/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 "Control Flow Optimizer"; }
  30     const TargetInstrInfo *TII;
  31     bool MadeChange;
  32   private:
  33     void OptimizeBlock(MachineFunction::iterator MBB);
  34   };
  35 }
  36
  37 FunctionPass *llvm::createBranchFoldingPass() { return new BranchFolder(); }
  38
  39 bool BranchFolder::runOnMachineFunction(MachineFunction &MF) {
  40   TII = MF.getTarget().getInstrInfo();
  41   if (!TII) return false;
  42
  43   //MF.dump();
  44
  45   bool EverMadeChange = false;
  46   MadeChange = true;
  47   while (MadeChange) {
  48     MadeChange = false;
  49     for (MachineFunction::iterator MBB = ++MF.begin(), E = MF.end(); MBB != E;
  50          ++MBB)
  51       OptimizeBlock(MBB);
  52
  53     // If branches were folded away somehow, do a quick scan and delete any dead
  54     // blocks.
  55     if (MadeChange) {
  56       for (MachineFunction::iterator I = ++MF.begin(), E = MF.end(); I != E; ) {
  57         MachineBasicBlock *MBB = I++;
  58         // Is it dead?
  59         if (MBB->pred_empty()) {
  60           // drop all successors.
  61           while (!MBB->succ_empty())
  62             MBB->removeSuccessor(MBB->succ_end()-1);
  63           MF.getBasicBlockList().erase(MBB);
  64         }
  65       }
  66     }
  67
  68     EverMadeChange |= MadeChange;
  69   }
  70
  71   return EverMadeChange;
  72 }
  73
  74 /// ReplaceUsesOfBlockWith - Given a machine basic block 'BB' that branched to
  75 /// 'Old', change the code and CFG so that it branches to 'New' instead.
  76 static void ReplaceUsesOfBlockWith(MachineBasicBlock *BB,
  77                                    MachineBasicBlock *Old,
  78                                    MachineBasicBlock *New,
  79                                    const TargetInstrInfo *TII) {
  80   assert(Old != New && "Cannot replace self with self!");
  81
  82   MachineBasicBlock::iterator I = BB->end();
  83   while (I != BB->begin()) {
  84     --I;
  85     if (!TII->isTerminatorInstr(I->getOpcode())) break;
  86
  87     // Scan the operands of this machine instruction, replacing any uses of Old
  88     // with New.
  89     for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i)
  90       if (I->getOperand(i).isMachineBasicBlock() &&
  91           I->getOperand(i).getMachineBasicBlock() == Old)
  92         I->getOperand(i).setMachineBasicBlock(New);
  93   }
  94
  95   // Update the successor information.
  96   std::vector<MachineBasicBlock*> Succs(BB->succ_begin(), BB->succ_end());
  97   for (int i = Succs.size()-1; i >= 0; --i)
  98     if (Succs[i] == Old) {
  99       BB->removeSuccessor(Old);
 100       BB->addSuccessor(New);
 101     }
 102 }
 103
 104 /// OptimizeBlock - Analyze and optimize control flow related to the specified
 105 /// block.  This is never called on the entry block.
 106 void BranchFolder::OptimizeBlock(MachineFunction::iterator MBB) {
 107   // If this block is empty, make everyone use its fall-through, not the block
 108   // explicitly.
 109   if (MBB->empty()) {
 110     if (MBB->pred_empty()) return;  // dead block?  Leave for cleanup later.
 111
 112     MachineFunction::iterator FallThrough = next(MBB);
 113
 114     if (FallThrough != MBB->getParent()->end()) {
 115       while (!MBB->pred_empty()) {
 116         MachineBasicBlock *Pred = *(MBB->pred_end()-1);
 117         ReplaceUsesOfBlockWith(Pred, MBB, FallThrough, TII);
 118       }
 119       MadeChange = true;
 120     }
 121     // TODO: CHANGE STUFF TO NOT BRANCH HERE!
 122     return;
 123   }
 124
 125   // Check to see if we can simplify the terminator of the block before this
 126   // one.
 127 #if 0
 128   MachineBasicBlock *PriorTBB = 0, *PriorFBB = 0;
 129   std::vector<MachineOperand> PriorCond;
 130   if (!TII->AnalyzeBranch(*prior(MBB), PriorTBB, PriorFBB, PriorCond)) {
 131     // If the previous branch is conditional and both conditions go to the same
 132     // destination, remove the branch, replacing it with an unconditional one.
 133     if (PriorTBB && PriorTBB == PriorFBB) {
 134       TII->RemoveBranch(*prior(MBB));
 135       PriorCond.clear();
 136       if (PriorTBB != &*MBB)
 137         TII->InsertBranch(*prior(MBB), PriorTBB, 0, PriorCond);
 138       MadeChange = true;
 139       return OptimizeBlock(MBB);
 140     }
 141
 142     // If the previous branch *only* branches to *this* block (conditional or
 143     // not) remove the branch.
 144     if (PriorTBB == &*MBB && PriorFBB == 0) {
 145       TII->RemoveBranch(*prior(MBB));
 146       MadeChange = true;
 147       return OptimizeBlock(MBB);
 148     }
 149   }
 150 #endif
 151
 152
 153 #if 0
 154
 155   if (MBB->pred_size() == 1) {
 156     // If this block has a single predecessor, and if that block has a single
 157     // successor, merge this block into that block.
 158     MachineBasicBlock *Pred = *MBB->pred_begin();
 159     if (Pred->succ_size() == 1) {
 160       // Delete all of the terminators from end of the pred block.  NOTE, this
 161       // assumes that terminators do not have side effects!
 162       // FIXME: This doesn't work for FP_REG_KILL.
 163
 164       while (!Pred->empty() && TII.isTerminatorInstr(Pred->back().getOpcode()))
 165         Pred->pop_back();
 166
 167       // Splice the instructions over.
 168       Pred->splice(Pred->end(), MBB, MBB->begin(), MBB->end());
 169
 170       // If MBB does not end with a barrier, add a goto instruction to the end.
 171       if (Pred->empty() || !TII.isBarrier(Pred->back().getOpcode()))
 172         TII.insertGoto(*Pred, *next(MBB));
 173
 174       // Update the CFG now.
 175       Pred->removeSuccessor(Pred->succ_begin());
 176       while (!MBB->succ_empty()) {
 177         Pred->addSuccessor(*(MBB->succ_end()-1));
 178         MBB->removeSuccessor(MBB->succ_end()-1);
 179       }
 180       return true;
 181     }
 182   }
 183
 184   // If BB falls through into Old, insert an unconditional branch to New.
 185   MachineFunction::iterator BBSucc = BB; ++BBSucc;
 186   if (BBSucc != BB->getParent()->end() && &*BBSucc == Old)
 187     TII.insertGoto(*BB, *New);
 188
 189
 190   if (MBB->pred_size() == 1) {
 191     // If this block has a single predecessor, and if that block has a single
 192     // successor, merge this block into that block.
 193     MachineBasicBlock *Pred = *MBB->pred_begin();
 194     if (Pred->succ_size() == 1) {
 195       // Delete all of the terminators from end of the pred block.  NOTE, this
 196       // assumes that terminators do not have side effects!
 197       // FIXME: This doesn't work for FP_REG_KILL.
 198
 199       while (!Pred->empty() && TII.isTerminatorInstr(Pred->back().getOpcode()))
 200         Pred->pop_back();
 201
 202       // Splice the instructions over.
 203       Pred->splice(Pred->end(), MBB, MBB->begin(), MBB->end());
 204
 205       // If MBB does not end with a barrier, add a goto instruction to the end.
 206       if (Pred->empty() || !TII.isBarrier(Pred->back().getOpcode()))
 207         TII.insertGoto(*Pred, *next(MBB));
 208
 209       // Update the CFG now.
 210       Pred->removeSuccessor(Pred->succ_begin());
 211       while (!MBB->succ_empty()) {
 212         Pred->addSuccessor(*(MBB->succ_end()-1));
 213         MBB->removeSuccessor(MBB->succ_end()-1);
 214       }
 215       return true;
 216     }
 217   }
 218
 219   // If the first instruction in this block is an unconditional branch, and if
 220   // there are predecessors, fold the branch into the predecessors.
 221   if (!MBB->pred_empty() && isUncondBranch(MBB->begin(), TII)) {
 222     MachineInstr *Br = MBB->begin();
 223     assert(Br->getNumOperands() == 1 && Br->getOperand(0).isMachineBasicBlock()
 224            && "Uncond branch should take one MBB argument!");
 225     MachineBasicBlock *Dest = Br->getOperand(0).getMachineBasicBlock();
 226
 227     while (!MBB->pred_empty()) {
 228       MachineBasicBlock *Pred = *(MBB->pred_end()-1);
 229       ReplaceUsesOfBlockWith(Pred, MBB, Dest, TII);
 230     }
 231     return true;
 232   }
 233
 234   // If the last instruction is an unconditional branch and the fall through
 235   // block is the destination, just delete the branch.
 236   if (isUncondBranch(--MBB->end(), TII)) {
 237     MachineBasicBlock::iterator MI = --MBB->end();
 238     MachineInstr *UncondBr = MI;
 239     MachineFunction::iterator FallThrough = next(MBB);
 240
 241     MachineFunction::iterator UncondDest =
 242       MI->getOperand(0).getMachineBasicBlock();
 243     if (UncondDest == FallThrough) {
 244       // Just delete the branch.  This does not effect the CFG.
 245       MBB->erase(UncondBr);
 246       return true;
 247     }
 248
 249     // Okay, so we don't have a fall-through.  Check to see if we have an
 250     // conditional branch that would be a fall through if we reversed it.  If
 251     // so, invert the condition and delete the uncond branch.
 252     if (MI != MBB->begin() && isCondBranch(--MI, TII)) {
 253       // We assume that conditional branches always have the branch dest as the
 254       // last operand.  This could be generalized in the future if needed.
 255       unsigned LastOpnd = MI->getNumOperands()-1;
 256       if (MachineFunction::iterator(
 257             MI->getOperand(LastOpnd).getMachineBasicBlock()) == FallThrough) {
 258         // Change the cond branch to go to the uncond dest, nuke the uncond,
 259         // then reverse the condition.
 260         MI->getOperand(LastOpnd).setMachineBasicBlock(UncondDest);
 261         MBB->erase(UncondBr);
 262         TII.reverseBranchCondition(MI);
 263         return true;
 264       }
 265     }
 266   }
 267 #endif
 268 }