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