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