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