LLVM API Documentation

Main Page | Namespace List | Class Hierarchy | Alphabetical List | Class List | Directories | File List | Namespace Members | Class Members | File Members | Related Pages

BranchFolding.cpp

Go to the documentation of this file.
00001 //===-- BranchFolding.cpp - Fold machine code branch instructions ---------===//
00002 // 
00003 //                     The LLVM Compiler Infrastructure
00004 //
00005 // This file was developed by the LLVM research group and is distributed under
00006 // the University of Illinois Open Source License. See LICENSE.TXT for details.
00007 // 
00008 //===----------------------------------------------------------------------===//
00009 //
00010 // This pass forwards branches to unconditional branches to make them branch
00011 // directly to the target block.  This pass often results in dead MBB's, which
00012 // it then removes.
00013 //
00014 // Note that this pass must be run after register allocation, it cannot handle
00015 // SSA form.
00016 //
00017 //===----------------------------------------------------------------------===//
00018 
00019 #include "llvm/CodeGen/Passes.h"
00020 #include "llvm/CodeGen/MachineFunctionPass.h"
00021 #include "llvm/Target/TargetInstrInfo.h"
00022 #include "llvm/Target/TargetMachine.h"
00023 #include "llvm/ADT/STLExtras.h"
00024 using namespace llvm;
00025 
00026 namespace {
00027   struct BranchFolder : public MachineFunctionPass {
00028     virtual bool runOnMachineFunction(MachineFunction &MF);
00029     virtual const char *getPassName() const { return "Branch Folder"; }
00030   private:
00031     bool OptimizeBlock(MachineFunction::iterator MBB,
00032                        const TargetInstrInfo &TII);
00033 
00034     bool isUncondBranch(const MachineInstr *MI, const TargetInstrInfo &TII) {
00035       return TII.isBarrier(MI->getOpcode()) && TII.isBranch(MI->getOpcode());
00036     }
00037     bool isCondBranch(const MachineInstr *MI, const TargetInstrInfo &TII) {
00038       return TII.isBranch(MI->getOpcode()) && !TII.isBarrier(MI->getOpcode());
00039     }
00040   };
00041 }
00042 
00043 FunctionPass *llvm::createBranchFoldingPass() { return new BranchFolder(); }
00044 
00045 bool BranchFolder::runOnMachineFunction(MachineFunction &MF) {
00046   bool EverMadeChange = false;
00047   bool MadeChange = true;
00048   const TargetInstrInfo &TII = *MF.getTarget().getInstrInfo();
00049   while (MadeChange) {
00050     MadeChange = false;
00051     for (MachineFunction::iterator MBB = ++MF.begin(), E = MF.end(); MBB != E;
00052          ++MBB)
00053       MadeChange |= OptimizeBlock(MBB, TII);
00054 
00055     // If branches were folded away somehow, do a quick scan and delete any dead
00056     // blocks.
00057     if (MadeChange) {
00058       for (MachineFunction::iterator I = ++MF.begin(), E = MF.end(); I != E; ) {
00059         MachineBasicBlock *MBB = I++;
00060         // Is it dead?
00061         if (MBB->pred_empty()) {
00062           // drop all successors.
00063           while (!MBB->succ_empty())
00064             MBB->removeSuccessor(MBB->succ_end()-1);
00065           MF.getBasicBlockList().erase(MBB);
00066         }
00067       }
00068     }
00069 
00070     EverMadeChange |= MadeChange;
00071   }
00072 
00073   return EverMadeChange;
00074 }
00075 
00076 /// ReplaceUsesOfBlockWith - Given a machine basic block 'BB' that branched to
00077 /// 'Old', change the code and CFG so that it branches to 'New' instead.
00078 static void ReplaceUsesOfBlockWith(MachineBasicBlock *BB,
00079                                    MachineBasicBlock *Old,
00080                                    MachineBasicBlock *New,
00081                                    const TargetInstrInfo &TII) {
00082   assert(Old != New && "Cannot replace self with self!");
00083 
00084   MachineBasicBlock::iterator I = BB->end();
00085   while (I != BB->begin()) {
00086     --I;
00087     if (!TII.isTerminatorInstr(I->getOpcode())) break;
00088 
00089     // Scan the operands of this machine instruction, replacing any uses of Old
00090     // with New.
00091     for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i)
00092       if (I->getOperand(i).isMachineBasicBlock() &&
00093           I->getOperand(i).getMachineBasicBlock() == Old)
00094         I->getOperand(i).setMachineBasicBlock(New);
00095   }
00096 
00097   // If BB falls through into Old, insert an unconditional branch to New.
00098   MachineFunction::iterator BBSucc = BB; ++BBSucc;
00099   if (BBSucc != BB->getParent()->end() && &*BBSucc == Old)
00100     TII.insertGoto(*BB, *New);
00101 
00102   std::vector<MachineBasicBlock*> Succs(BB->succ_begin(), BB->succ_end());
00103   for (int i = Succs.size()-1; i >= 0; --i)
00104     if (Succs[i] == Old) {
00105       BB->removeSuccessor(Old);
00106       BB->addSuccessor(New);
00107     }
00108 }
00109 
00110 
00111 bool BranchFolder::OptimizeBlock(MachineFunction::iterator MBB,
00112                                  const TargetInstrInfo &TII) {
00113   // If this block is empty, make everyone use it's fall-through, not the block
00114   // explicitly.
00115   if (MBB->empty()) {
00116     if (MBB->pred_empty()) return false;
00117     MachineFunction::iterator FallThrough =next(MBB);
00118     assert(FallThrough != MBB->getParent()->end() &&
00119            "Fell off the end of the function!");
00120     while (!MBB->pred_empty()) {
00121       MachineBasicBlock *Pred = *(MBB->pred_end()-1);
00122       ReplaceUsesOfBlockWith(Pred, MBB, FallThrough, TII);
00123     }
00124     return true;
00125   }
00126 
00127   if (MBB->pred_size() == 1) {
00128     // If this block has a single predecessor, and if that block has a single
00129     // successor, merge this block into that block.
00130     MachineBasicBlock *Pred = *MBB->pred_begin();
00131     if (Pred->succ_size() == 1) {
00132       // Delete all of the terminators from end of the pred block.  NOTE, this
00133       // assumes that terminators do not have side effects!
00134       while (!Pred->empty() && TII.isTerminatorInstr(Pred->back().getOpcode()))
00135         Pred->pop_back();
00136 
00137       // Splice the instructions over.
00138       Pred->splice(Pred->end(), MBB, MBB->begin(), MBB->end());
00139 
00140       // If MBB does not end with a barrier, add a goto instruction to the end.
00141       if (Pred->empty() || !TII.isBarrier(Pred->back().getOpcode()))
00142         TII.insertGoto(*Pred, *next(MBB));
00143 
00144       // Update the CFG now.
00145       Pred->removeSuccessor(Pred->succ_begin());
00146       while (!MBB->succ_empty()) {
00147         Pred->addSuccessor(*(MBB->succ_end()-1));
00148         MBB->removeSuccessor(MBB->succ_end()-1);
00149       }
00150       return true;
00151     }
00152   }
00153 
00154   // If the first instruction in this block is an unconditional branch, and if
00155   // there are predecessors, fold the branch into the predecessors.
00156   if (!MBB->pred_empty() && isUncondBranch(MBB->begin(), TII)) {
00157     MachineInstr *Br = MBB->begin();
00158     assert(Br->getNumOperands() == 1 && Br->getOperand(0).isMachineBasicBlock()
00159            && "Uncond branch should take one MBB argument!");
00160     MachineBasicBlock *Dest = Br->getOperand(0).getMachineBasicBlock();
00161     
00162     while (!MBB->pred_empty()) {
00163       MachineBasicBlock *Pred = *(MBB->pred_end()-1);
00164       ReplaceUsesOfBlockWith(Pred, MBB, Dest, TII);
00165     }
00166     return true;
00167   }
00168 
00169   // If the last instruction is an unconditional branch and the fall through
00170   // block is the destination, just delete the branch.
00171   if (isUncondBranch(--MBB->end(), TII)) {
00172     MachineBasicBlock::iterator MI = --MBB->end();
00173     MachineInstr *UncondBr = MI;
00174     MachineFunction::iterator FallThrough = next(MBB);
00175 
00176     MachineFunction::iterator UncondDest =
00177       MI->getOperand(0).getMachineBasicBlock();
00178     if (UncondDest == FallThrough) {
00179       // Just delete the branch.  This does not effect the CFG.
00180       MBB->erase(UncondBr);
00181       return true;
00182     }
00183 
00184     // Okay, so we don't have a fall-through.  Check to see if we have an
00185     // conditional branch that would be a fall through if we reversed it.  If
00186     // so, invert the condition and delete the uncond branch.
00187     if (MI != MBB->begin() && isCondBranch(--MI, TII)) {
00188       // We assume that conditional branches always have the branch dest as the
00189       // last operand.  This could be generalized in the future if needed.
00190       unsigned LastOpnd = MI->getNumOperands()-1;
00191       if (MachineFunction::iterator(
00192             MI->getOperand(LastOpnd).getMachineBasicBlock()) == FallThrough) {
00193         // Change the cond branch to go to the uncond dest, nuke the uncond,
00194         // then reverse the condition.
00195         MI->getOperand(LastOpnd).setMachineBasicBlock(UncondDest);
00196         MBB->erase(UncondBr);
00197         TII.reverseBranchCondition(MI);
00198         return true;
00199       }
00200     }
00201   }
00202 
00203   return false;
00204 }