LLVM API Documentation
00001 //===- SimplifyCFGPass.cpp - CFG Simplification Pass ----------------------===// 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 file implements dead code elimination and basic block merging, along 00011 // with a collection of other peephole control flow optimizations. For example: 00012 // 00013 // * Removes basic blocks with no predecessors. 00014 // * Merges a basic block into its predecessor if there is only one and the 00015 // predecessor only has one successor. 00016 // * Eliminates PHI nodes for basic blocks with a single predecessor. 00017 // * Eliminates a basic block that only contains an unconditional branch. 00018 // * Changes invoke instructions to nounwind functions to be calls. 00019 // * Change things like "if (x) if (y)" into "if (x&y)". 00020 // * etc.. 00021 // 00022 //===----------------------------------------------------------------------===// 00023 00024 #define DEBUG_TYPE "simplifycfg" 00025 #include "llvm/Transforms/Scalar.h" 00026 #include "llvm/Transforms/Utils/Local.h" 00027 #include "llvm/Constants.h" 00028 #include "llvm/Instructions.h" 00029 #include "llvm/LLVMContext.h" 00030 #include "llvm/Module.h" 00031 #include "llvm/Attributes.h" 00032 #include "llvm/Support/CFG.h" 00033 #include "llvm/Support/Compiler.h" 00034 #include "llvm/Pass.h" 00035 #include "llvm/ADT/SmallVector.h" 00036 #include "llvm/ADT/SmallPtrSet.h" 00037 #include "llvm/ADT/Statistic.h" 00038 using namespace llvm; 00039 00040 STATISTIC(NumSimpl, "Number of blocks simplified"); 00041 00042 namespace { 00043 struct VISIBILITY_HIDDEN CFGSimplifyPass : public FunctionPass { 00044 static char ID; // Pass identification, replacement for typeid 00045 CFGSimplifyPass() : FunctionPass(&ID) {} 00046 00047 virtual bool runOnFunction(Function &F); 00048 }; 00049 } 00050 00051 char CFGSimplifyPass::ID = 0; 00052 static RegisterPass<CFGSimplifyPass> X("simplifycfg", "Simplify the CFG"); 00053 00054 // Public interface to the CFGSimplification pass 00055 FunctionPass *llvm::createCFGSimplificationPass() { 00056 return new CFGSimplifyPass(); 00057 } 00058 00059 /// ChangeToUnreachable - Insert an unreachable instruction before the specified 00060 /// instruction, making it and the rest of the code in the block dead. 00061 static void ChangeToUnreachable(Instruction *I, LLVMContext &Context) { 00062 BasicBlock *BB = I->getParent(); 00063 // Loop over all of the successors, removing BB's entry from any PHI 00064 // nodes. 00065 for (succ_iterator SI = succ_begin(BB), SE = succ_end(BB); SI != SE; ++SI) 00066 (*SI)->removePredecessor(BB); 00067 00068 new UnreachableInst(I->getContext(), I); 00069 00070 // All instructions after this are dead. 00071 BasicBlock::iterator BBI = I, BBE = BB->end(); 00072 while (BBI != BBE) { 00073 if (!BBI->use_empty()) 00074 BBI->replaceAllUsesWith(UndefValue::get(BBI->getType())); 00075 BB->getInstList().erase(BBI++); 00076 } 00077 } 00078 00079 /// ChangeToCall - Convert the specified invoke into a normal call. 00080 static void ChangeToCall(InvokeInst *II) { 00081 BasicBlock *BB = II->getParent(); 00082 SmallVector<Value*, 8> Args(II->op_begin()+3, II->op_end()); 00083 CallInst *NewCall = CallInst::Create(II->getCalledValue(), Args.begin(), 00084 Args.end(), "", II); 00085 NewCall->takeName(II); 00086 NewCall->setCallingConv(II->getCallingConv()); 00087 NewCall->setAttributes(II->getAttributes()); 00088 II->replaceAllUsesWith(NewCall); 00089 00090 // Follow the call by a branch to the normal destination. 00091 BranchInst::Create(II->getNormalDest(), II); 00092 00093 // Update PHI nodes in the unwind destination 00094 II->getUnwindDest()->removePredecessor(BB); 00095 BB->getInstList().erase(II); 00096 } 00097 00098 static bool MarkAliveBlocks(BasicBlock *BB, 00099 SmallPtrSet<BasicBlock*, 128> &Reachable, 00100 LLVMContext &Context) { 00101 00102 SmallVector<BasicBlock*, 128> Worklist; 00103 Worklist.push_back(BB); 00104 bool Changed = false; 00105 while (!Worklist.empty()) { 00106 BB = Worklist.back(); 00107 Worklist.pop_back(); 00108 00109 if (!Reachable.insert(BB)) 00110 continue; 00111 00112 // Do a quick scan of the basic block, turning any obviously unreachable 00113 // instructions into LLVM unreachable insts. The instruction combining pass 00114 // canonicalizes unreachable insts into stores to null or undef. 00115 for (BasicBlock::iterator BBI = BB->begin(), E = BB->end(); BBI != E;++BBI){ 00116 if (CallInst *CI = dyn_cast<CallInst>(BBI)) { 00117 if (CI->doesNotReturn()) { 00118 // If we found a call to a no-return function, insert an unreachable 00119 // instruction after it. Make sure there isn't *already* one there 00120 // though. 00121 ++BBI; 00122 if (!isa<UnreachableInst>(BBI)) { 00123 ChangeToUnreachable(BBI, Context); 00124 Changed = true; 00125 } 00126 break; 00127 } 00128 } 00129 00130 if (StoreInst *SI = dyn_cast<StoreInst>(BBI)) { 00131 Value *Ptr = SI->getOperand(1); 00132 00133 if (isa<UndefValue>(Ptr) || 00134 (isa<ConstantPointerNull>(Ptr) && 00135 cast<PointerType>(Ptr->getType())->getAddressSpace() == 0)) { 00136 ChangeToUnreachable(SI, Context); 00137 Changed = true; 00138 break; 00139 } 00140 } 00141 } 00142 00143 // Turn invokes that call 'nounwind' functions into ordinary calls. 00144 if (InvokeInst *II = dyn_cast<InvokeInst>(BB->getTerminator())) 00145 if (II->doesNotThrow()) { 00146 ChangeToCall(II); 00147 Changed = true; 00148 } 00149 00150 Changed |= ConstantFoldTerminator(BB); 00151 for (succ_iterator SI = succ_begin(BB), SE = succ_end(BB); SI != SE; ++SI) 00152 Worklist.push_back(*SI); 00153 } 00154 return Changed; 00155 } 00156 00157 /// RemoveUnreachableBlocksFromFn - Remove blocks that are not reachable, even 00158 /// if they are in a dead cycle. Return true if a change was made, false 00159 /// otherwise. 00160 static bool RemoveUnreachableBlocksFromFn(Function &F) { 00161 SmallPtrSet<BasicBlock*, 128> Reachable; 00162 bool Changed = MarkAliveBlocks(F.begin(), Reachable, F.getContext()); 00163 00164 // If there are unreachable blocks in the CFG... 00165 if (Reachable.size() == F.size()) 00166 return Changed; 00167 00168 assert(Reachable.size() < F.size()); 00169 NumSimpl += F.size()-Reachable.size(); 00170 00171 // Loop over all of the basic blocks that are not reachable, dropping all of 00172 // their internal references... 00173 for (Function::iterator BB = ++F.begin(), E = F.end(); BB != E; ++BB) { 00174 if (Reachable.count(BB)) 00175 continue; 00176 00177 for (succ_iterator SI = succ_begin(BB), SE = succ_end(BB); SI != SE; ++SI) 00178 if (Reachable.count(*SI)) 00179 (*SI)->removePredecessor(BB); 00180 BB->dropAllReferences(); 00181 } 00182 00183 for (Function::iterator I = ++F.begin(); I != F.end();) 00184 if (!Reachable.count(I)) 00185 I = F.getBasicBlockList().erase(I); 00186 else 00187 ++I; 00188 00189 return true; 00190 } 00191 00192 /// IterativeSimplifyCFG - Call SimplifyCFG on all the blocks in the function, 00193 /// iterating until no more changes are made. 00194 static bool IterativeSimplifyCFG(Function &F) { 00195 bool Changed = false; 00196 bool LocalChange = true; 00197 while (LocalChange) { 00198 LocalChange = false; 00199 00200 // Loop over all of the basic blocks (except the first one) and remove them 00201 // if they are unneeded... 00202 // 00203 for (Function::iterator BBIt = ++F.begin(); BBIt != F.end(); ) { 00204 if (SimplifyCFG(BBIt++)) { 00205 LocalChange = true; 00206 ++NumSimpl; 00207 } 00208 } 00209 Changed |= LocalChange; 00210 } 00211 return Changed; 00212 } 00213 00214 // It is possible that we may require multiple passes over the code to fully 00215 // simplify the CFG. 00216 // 00217 bool CFGSimplifyPass::runOnFunction(Function &F) { 00218 bool EverChanged = RemoveUnreachableBlocksFromFn(F); 00219 EverChanged |= IterativeSimplifyCFG(F); 00220 00221 // If neither pass changed anything, we're done. 00222 if (!EverChanged) return false; 00223 00224 // IterativeSimplifyCFG can (rarely) make some loops dead. If this happens, 00225 // RemoveUnreachableBlocksFromFn is needed to nuke them, which means we should 00226 // iterate between the two optimizations. We structure the code like this to 00227 // avoid reruning IterativeSimplifyCFG if the second pass of 00228 // RemoveUnreachableBlocksFromFn doesn't do anything. 00229 if (!RemoveUnreachableBlocksFromFn(F)) 00230 return true; 00231 00232 do { 00233 EverChanged = IterativeSimplifyCFG(F); 00234 EverChanged |= RemoveUnreachableBlocksFromFn(F); 00235 } while (EverChanged); 00236 00237 return true; 00238 }