LLVM API Documentation

CondPropagate.cpp

Go to the documentation of this file.
00001 //===-- CondPropagate.cpp - Propagate Conditional Expressions -------------===//
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 propagates information about conditional expressions through the
00011 // program, allowing it to eliminate conditional branches in some cases.
00012 //
00013 //===----------------------------------------------------------------------===//
00014 
00015 #define DEBUG_TYPE "condprop"
00016 #include "llvm/Transforms/Scalar.h"
00017 #include "llvm/Transforms/Utils/Local.h"
00018 #include "llvm/Constants.h"
00019 #include "llvm/Function.h"
00020 #include "llvm/Instructions.h"
00021 #include "llvm/Pass.h"
00022 #include "llvm/Type.h"
00023 #include "llvm/ADT/STLExtras.h"
00024 #include "llvm/ADT/Statistic.h"
00025 #include <iostream>
00026 using namespace llvm;
00027 
00028 namespace {
00029   Statistic<>
00030   NumBrThread("condprop", "Number of CFG edges threaded through branches");
00031   Statistic<>
00032   NumSwThread("condprop", "Number of CFG edges threaded through switches");
00033 
00034   struct CondProp : public FunctionPass {
00035     virtual bool runOnFunction(Function &F);
00036 
00037     virtual void getAnalysisUsage(AnalysisUsage &AU) const {
00038       AU.addRequiredID(BreakCriticalEdgesID);
00039       //AU.addRequired<DominanceFrontier>();
00040     }
00041 
00042   private:
00043     bool MadeChange;
00044     void SimplifyBlock(BasicBlock *BB);
00045     void SimplifyPredecessors(BranchInst *BI);
00046     void SimplifyPredecessors(SwitchInst *SI);
00047     void RevectorBlockTo(BasicBlock *FromBB, BasicBlock *ToBB);
00048   };
00049   RegisterOpt<CondProp> X("condprop", "Conditional Propagation");
00050 }
00051 
00052 FunctionPass *llvm::createCondPropagationPass() {
00053   return new CondProp();
00054 }
00055 
00056 bool CondProp::runOnFunction(Function &F) {
00057   bool EverMadeChange = false;
00058 
00059   // While we are simplifying blocks, keep iterating.
00060   do {
00061     MadeChange = false;
00062     for (Function::iterator BB = F.begin(), E = F.end(); BB != E; ++BB)
00063       SimplifyBlock(BB);
00064     EverMadeChange = MadeChange;
00065   } while (MadeChange);
00066   return EverMadeChange;
00067 }
00068 
00069 void CondProp::SimplifyBlock(BasicBlock *BB) {
00070   if (BranchInst *BI = dyn_cast<BranchInst>(BB->getTerminator())) {
00071     // If this is a conditional branch based on a phi node that is defined in
00072     // this block, see if we can simplify predecessors of this block.
00073     if (BI->isConditional() && isa<PHINode>(BI->getCondition()) &&
00074         cast<PHINode>(BI->getCondition())->getParent() == BB)
00075       SimplifyPredecessors(BI);
00076 
00077   } else if (SwitchInst *SI = dyn_cast<SwitchInst>(BB->getTerminator())) {
00078     if (isa<PHINode>(SI->getCondition()) &&
00079         cast<PHINode>(SI->getCondition())->getParent() == BB)
00080       SimplifyPredecessors(SI);
00081   }
00082 
00083   // If possible, simplify the terminator of this block.
00084   if (ConstantFoldTerminator(BB))
00085     MadeChange = true;
00086 
00087   // If this block ends with an unconditional branch and the only successor has
00088   // only this block as a predecessor, merge the two blocks together.
00089   if (BranchInst *BI = dyn_cast<BranchInst>(BB->getTerminator()))
00090     if (BI->isUnconditional() && BI->getSuccessor(0)->getSinglePredecessor()) {
00091       BasicBlock *Succ = BI->getSuccessor(0);
00092       // Remove BI.
00093       BI->eraseFromParent();
00094 
00095       // Move over all of the instructions.
00096       BB->getInstList().splice(BB->end(), Succ->getInstList());
00097 
00098       // Any phi nodes that had entries for Succ now have entries from BB.
00099       Succ->replaceAllUsesWith(BB);
00100 
00101       // Succ is now dead, but we cannot delete it without potentially
00102       // invalidating iterators elsewhere.  Just insert an unreachable
00103       // instruction in it.
00104       new UnreachableInst(Succ);
00105       MadeChange = true;
00106     }
00107 }
00108 
00109 // SimplifyPredecessors(branches) - We know that BI is a conditional branch
00110 // based on a PHI node defined in this block.  If the phi node contains constant
00111 // operands, then the blocks corresponding to those operands can be modified to
00112 // jump directly to the destination instead of going through this block.
00113 void CondProp::SimplifyPredecessors(BranchInst *BI) {
00114   // TODO: We currently only handle the most trival case, where the PHI node has
00115   // one use (the branch), and is the only instruction besides the branch in the
00116   // block.
00117   PHINode *PN = cast<PHINode>(BI->getCondition());
00118   if (!PN->hasOneUse()) return;
00119 
00120   BasicBlock *BB = BI->getParent();
00121   if (&*BB->begin() != PN || &*next(BB->begin()) != BI)
00122     return;
00123 
00124   // Ok, we have this really simple case, walk the PHI operands, looking for
00125   // constants.  Walk from the end to remove operands from the end when
00126   // possible, and to avoid invalidating "i".
00127   for (unsigned i = PN->getNumIncomingValues(); i != 0; --i)
00128     if (ConstantBool *CB = dyn_cast<ConstantBool>(PN->getIncomingValue(i-1))) {
00129       // If we have a constant, forward the edge from its current to its
00130       // ultimate destination.
00131       bool PHIGone = PN->getNumIncomingValues() == 2;
00132       RevectorBlockTo(PN->getIncomingBlock(i-1),
00133                       BI->getSuccessor(CB->getValue() == 0));
00134       ++NumBrThread;
00135 
00136       // If there were two predecessors before this simplification, the PHI node
00137       // will be deleted.  Don't iterate through it the last time.
00138       if (PHIGone) return;
00139     }
00140 }
00141 
00142 // SimplifyPredecessors(switch) - We know that SI is switch based on a PHI node
00143 // defined in this block.  If the phi node contains constant operands, then the
00144 // blocks corresponding to those operands can be modified to jump directly to
00145 // the destination instead of going through this block.
00146 void CondProp::SimplifyPredecessors(SwitchInst *SI) {
00147   // TODO: We currently only handle the most trival case, where the PHI node has
00148   // one use (the branch), and is the only instruction besides the branch in the
00149   // block.
00150   PHINode *PN = cast<PHINode>(SI->getCondition());
00151   if (!PN->hasOneUse()) return;
00152 
00153   BasicBlock *BB = SI->getParent();
00154   if (&*BB->begin() != PN || &*next(BB->begin()) != SI)
00155     return;
00156 
00157   bool RemovedPreds = false;
00158 
00159   // Ok, we have this really simple case, walk the PHI operands, looking for
00160   // constants.  Walk from the end to remove operands from the end when
00161   // possible, and to avoid invalidating "i".
00162   for (unsigned i = PN->getNumIncomingValues(); i != 0; --i)
00163     if (ConstantInt *CI = dyn_cast<ConstantInt>(PN->getIncomingValue(i-1))) {
00164       // If we have a constant, forward the edge from its current to its
00165       // ultimate destination.
00166       bool PHIGone = PN->getNumIncomingValues() == 2;
00167       unsigned DestCase = SI->findCaseValue(CI);
00168       RevectorBlockTo(PN->getIncomingBlock(i-1),
00169                       SI->getSuccessor(DestCase));
00170       ++NumSwThread;
00171       RemovedPreds = true;
00172 
00173       // If there were two predecessors before this simplification, the PHI node
00174       // will be deleted.  Don't iterate through it the last time.
00175       if (PHIGone) return;
00176     }
00177 }
00178 
00179 
00180 // RevectorBlockTo - Revector the unconditional branch at the end of FromBB to
00181 // the ToBB block, which is one of the successors of its current successor.
00182 void CondProp::RevectorBlockTo(BasicBlock *FromBB, BasicBlock *ToBB) {
00183   BranchInst *FromBr = cast<BranchInst>(FromBB->getTerminator());
00184   assert(FromBr->isUnconditional() && "FromBB should end with uncond br!");
00185 
00186   // Get the old block we are threading through.
00187   BasicBlock *OldSucc = FromBr->getSuccessor(0);
00188 
00189   // ToBB should not have any PHI nodes in it to update, because OldSucc had
00190   // multiple successors.  If OldSucc had multiple successor and ToBB had
00191   // multiple predecessors, the edge between them would be critical, which we
00192   // already took care of.
00193   assert(!isa<PHINode>(ToBB->begin()) && "Critical Edge Found!");
00194 
00195   // Update PHI nodes in OldSucc to know that FromBB no longer branches to it.
00196   OldSucc->removePredecessor(FromBB);
00197 
00198   // Change FromBr to branch to the new destination.
00199   FromBr->setSuccessor(0, ToBB);
00200 
00201   MadeChange = true;
00202 }