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 is distributed under the University of Illinois Open Source
00006 // 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/Constants.h"
00018 #include "llvm/Function.h"
00019 #include "llvm/Instructions.h"
00020 #include "llvm/IntrinsicInst.h"
00021 #include "llvm/Pass.h"
00022 #include "llvm/Type.h"
00023 #include "llvm/Transforms/Utils/BasicBlockUtils.h"
00024 #include "llvm/Transforms/Utils/Local.h"
00025 #include "llvm/ADT/STLExtras.h"
00026 #include "llvm/ADT/Statistic.h"
00027 #include "llvm/ADT/SmallVector.h"
00028 #include "llvm/Support/Compiler.h"
00029 #include "llvm/Support/Streams.h"
00030 using namespace llvm;
00031 
00032 STATISTIC(NumBrThread, "Number of CFG edges threaded through branches");
00033 STATISTIC(NumSwThread, "Number of CFG edges threaded through switches");
00034 
00035 namespace {
00036   struct VISIBILITY_HIDDEN CondProp : public FunctionPass {
00037     static char ID; // Pass identification, replacement for typeid
00038     CondProp() : FunctionPass(&ID) {}
00039 
00040     virtual bool runOnFunction(Function &F);
00041 
00042     virtual void getAnalysisUsage(AnalysisUsage &AU) const {
00043       AU.addRequiredID(BreakCriticalEdgesID);
00044       //AU.addRequired<DominanceFrontier>();
00045     }
00046 
00047   private:
00048     bool MadeChange;
00049     SmallVector<BasicBlock *, 4> DeadBlocks;
00050     void SimplifyBlock(BasicBlock *BB);
00051     void SimplifyPredecessors(BranchInst *BI);
00052     void SimplifyPredecessors(SwitchInst *SI);
00053     void RevectorBlockTo(BasicBlock *FromBB, BasicBlock *ToBB);
00054     bool RevectorBlockTo(BasicBlock *FromBB, Value *Cond, BranchInst *BI);
00055   };
00056 }
00057   
00058 char CondProp::ID = 0;
00059 static RegisterPass<CondProp> X("condprop", "Conditional Propagation");
00060 
00061 FunctionPass *llvm::createCondPropagationPass() {
00062   return new CondProp();
00063 }
00064 
00065 bool CondProp::runOnFunction(Function &F) {
00066   bool EverMadeChange = false;
00067   DeadBlocks.clear();
00068 
00069   // While we are simplifying blocks, keep iterating.
00070   do {
00071     MadeChange = false;
00072     for (Function::iterator BB = F.begin(), E = F.end(); BB != E;)
00073       SimplifyBlock(BB++);
00074     EverMadeChange = EverMadeChange || MadeChange;
00075   } while (MadeChange);
00076 
00077   if (EverMadeChange) {
00078     while (!DeadBlocks.empty()) {
00079       BasicBlock *BB = DeadBlocks.back(); DeadBlocks.pop_back();
00080       DeleteDeadBlock(BB);
00081     }
00082   }
00083   return EverMadeChange;
00084 }
00085 
00086 void CondProp::SimplifyBlock(BasicBlock *BB) {
00087   if (BranchInst *BI = dyn_cast<BranchInst>(BB->getTerminator())) {
00088     // If this is a conditional branch based on a phi node that is defined in
00089     // this block, see if we can simplify predecessors of this block.
00090     if (BI->isConditional() && isa<PHINode>(BI->getCondition()) &&
00091         cast<PHINode>(BI->getCondition())->getParent() == BB)
00092       SimplifyPredecessors(BI);
00093 
00094   } else if (SwitchInst *SI = dyn_cast<SwitchInst>(BB->getTerminator())) {
00095     if (isa<PHINode>(SI->getCondition()) &&
00096         cast<PHINode>(SI->getCondition())->getParent() == BB)
00097       SimplifyPredecessors(SI);
00098   }
00099 
00100   // If possible, simplify the terminator of this block.
00101   if (ConstantFoldTerminator(BB))
00102     MadeChange = true;
00103 
00104   // If this block ends with an unconditional branch and the only successor has
00105   // only this block as a predecessor, merge the two blocks together.
00106   if (BranchInst *BI = dyn_cast<BranchInst>(BB->getTerminator()))
00107     if (BI->isUnconditional() && BI->getSuccessor(0)->getSinglePredecessor() &&
00108         BB != BI->getSuccessor(0)) {
00109       BasicBlock *Succ = BI->getSuccessor(0);
00110       
00111       // If Succ has any PHI nodes, they are all single-entry PHI's.  Eliminate
00112       // them.
00113       FoldSingleEntryPHINodes(Succ);
00114       
00115       // Remove BI.
00116       BI->eraseFromParent();
00117 
00118       // Move over all of the instructions.
00119       BB->getInstList().splice(BB->end(), Succ->getInstList());
00120 
00121       // Any phi nodes that had entries for Succ now have entries from BB.
00122       Succ->replaceAllUsesWith(BB);
00123 
00124       // Succ is now dead, but we cannot delete it without potentially
00125       // invalidating iterators elsewhere.  Just insert an unreachable
00126       // instruction in it and delete this block later on.
00127       new UnreachableInst(BB->getContext(), Succ);
00128       DeadBlocks.push_back(Succ);
00129       MadeChange = true;
00130     }
00131 }
00132 
00133 // SimplifyPredecessors(branches) - We know that BI is a conditional branch
00134 // based on a PHI node defined in this block.  If the phi node contains constant
00135 // operands, then the blocks corresponding to those operands can be modified to
00136 // jump directly to the destination instead of going through this block.
00137 void CondProp::SimplifyPredecessors(BranchInst *BI) {
00138   // TODO: We currently only handle the most trival case, where the PHI node has
00139   // one use (the branch), and is the only instruction besides the branch and dbg
00140   // intrinsics in the block.
00141   PHINode *PN = cast<PHINode>(BI->getCondition());
00142 
00143   if (PN->getNumIncomingValues() == 1) {
00144     // Eliminate single-entry PHI nodes.
00145     FoldSingleEntryPHINodes(PN->getParent());
00146     return;
00147   }
00148   
00149   
00150   if (!PN->hasOneUse()) return;
00151 
00152   BasicBlock *BB = BI->getParent();
00153   if (&*BB->begin() != PN)
00154     return;
00155   BasicBlock::iterator BBI = BB->begin();
00156   BasicBlock::iterator BBE = BB->end();
00157   while (BBI != BBE && isa<DbgInfoIntrinsic>(++BBI)) /* empty */;
00158   if (&*BBI != BI)
00159     return;
00160 
00161   // Ok, we have this really simple case, walk the PHI operands, looking for
00162   // constants.  Walk from the end to remove operands from the end when
00163   // possible, and to avoid invalidating "i".
00164   for (unsigned i = PN->getNumIncomingValues(); i != 0; --i) {
00165     Value *InVal = PN->getIncomingValue(i-1);
00166     if (!RevectorBlockTo(PN->getIncomingBlock(i-1), InVal, BI))
00167       continue;
00168 
00169     ++NumBrThread;
00170 
00171     // If there were two predecessors before this simplification, or if the
00172     // PHI node contained all the same value except for the one we just
00173     // substituted, the PHI node may be deleted.  Don't iterate through it the
00174     // last time.
00175     if (BI->getCondition() != PN) return;
00176   }
00177 }
00178 
00179 // SimplifyPredecessors(switch) - We know that SI is switch based on a PHI node
00180 // defined in this block.  If the phi node contains constant operands, then the
00181 // blocks corresponding to those operands can be modified to jump directly to
00182 // the destination instead of going through this block.
00183 void CondProp::SimplifyPredecessors(SwitchInst *SI) {
00184   // TODO: We currently only handle the most trival case, where the PHI node has
00185   // one use (the branch), and is the only instruction besides the branch and 
00186   // dbg intrinsics in the block.
00187   PHINode *PN = cast<PHINode>(SI->getCondition());
00188   if (!PN->hasOneUse()) return;
00189 
00190   BasicBlock *BB = SI->getParent();
00191   if (&*BB->begin() != PN)
00192     return;
00193   BasicBlock::iterator BBI = BB->begin();
00194   BasicBlock::iterator BBE = BB->end();
00195   while (BBI != BBE && isa<DbgInfoIntrinsic>(++BBI)) /* empty */;
00196   if (&*BBI != SI)
00197     return;
00198 
00199   bool RemovedPreds = false;
00200 
00201   // Ok, we have this really simple case, walk the PHI operands, looking for
00202   // constants.  Walk from the end to remove operands from the end when
00203   // possible, and to avoid invalidating "i".
00204   for (unsigned i = PN->getNumIncomingValues(); i != 0; --i)
00205     if (ConstantInt *CI = dyn_cast<ConstantInt>(PN->getIncomingValue(i-1))) {
00206       // If we have a constant, forward the edge from its current to its
00207       // ultimate destination.
00208       unsigned DestCase = SI->findCaseValue(CI);
00209       RevectorBlockTo(PN->getIncomingBlock(i-1),
00210                       SI->getSuccessor(DestCase));
00211       ++NumSwThread;
00212       RemovedPreds = true;
00213 
00214       // If there were two predecessors before this simplification, or if the
00215       // PHI node contained all the same value except for the one we just
00216       // substituted, the PHI node may be deleted.  Don't iterate through it the
00217       // last time.
00218       if (SI->getCondition() != PN) return;
00219     }
00220 }
00221 
00222 
00223 // RevectorBlockTo - Revector the unconditional branch at the end of FromBB to
00224 // the ToBB block, which is one of the successors of its current successor.
00225 void CondProp::RevectorBlockTo(BasicBlock *FromBB, BasicBlock *ToBB) {
00226   BranchInst *FromBr = cast<BranchInst>(FromBB->getTerminator());
00227   assert(FromBr->isUnconditional() && "FromBB should end with uncond br!");
00228 
00229   // Get the old block we are threading through.
00230   BasicBlock *OldSucc = FromBr->getSuccessor(0);
00231 
00232   // OldSucc had multiple successors. If ToBB has multiple predecessors, then 
00233   // the edge between them would be critical, which we already took care of.
00234   // If ToBB has single operand PHI node then take care of it here.
00235   FoldSingleEntryPHINodes(ToBB);
00236 
00237   // Update PHI nodes in OldSucc to know that FromBB no longer branches to it.
00238   OldSucc->removePredecessor(FromBB);
00239 
00240   // Change FromBr to branch to the new destination.
00241   FromBr->setSuccessor(0, ToBB);
00242 
00243   MadeChange = true;
00244 }
00245 
00246 bool CondProp::RevectorBlockTo(BasicBlock *FromBB, Value *Cond, BranchInst *BI){
00247   BranchInst *FromBr = cast<BranchInst>(FromBB->getTerminator());
00248   if (!FromBr->isUnconditional())
00249     return false;
00250 
00251   // Get the old block we are threading through.
00252   BasicBlock *OldSucc = FromBr->getSuccessor(0);
00253 
00254   // If the condition is a constant, simply revector the unconditional branch at
00255   // the end of FromBB to one of the successors of its current successor.
00256   if (ConstantInt *CB = dyn_cast<ConstantInt>(Cond)) {
00257     BasicBlock *ToBB = BI->getSuccessor(CB->isZero());
00258 
00259     // OldSucc had multiple successors. If ToBB has multiple predecessors, then 
00260     // the edge between them would be critical, which we already took care of.
00261     // If ToBB has single operand PHI node then take care of it here.
00262     FoldSingleEntryPHINodes(ToBB);
00263 
00264     // Update PHI nodes in OldSucc to know that FromBB no longer branches to it.
00265     OldSucc->removePredecessor(FromBB);
00266 
00267     // Change FromBr to branch to the new destination.
00268     FromBr->setSuccessor(0, ToBB);
00269   } else {
00270     BasicBlock *Succ0 = BI->getSuccessor(0);
00271     // Do not perform transform if the new destination has PHI nodes. The
00272     // transform will add new preds to the PHI's.
00273     if (isa<PHINode>(Succ0->begin()))
00274       return false;
00275 
00276     BasicBlock *Succ1 = BI->getSuccessor(1);
00277     if (isa<PHINode>(Succ1->begin()))
00278       return false;
00279 
00280     // Insert the new conditional branch.
00281     BranchInst::Create(Succ0, Succ1, Cond, FromBr);
00282 
00283     FoldSingleEntryPHINodes(Succ0);
00284     FoldSingleEntryPHINodes(Succ1);
00285 
00286     // Update PHI nodes in OldSucc to know that FromBB no longer branches to it.
00287     OldSucc->removePredecessor(FromBB);
00288 
00289     // Delete the old branch.
00290     FromBr->eraseFromParent();
00291   }
00292 
00293   MadeChange = true;
00294   return true;
00295 }