LLVM API Documentation
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 }