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