LLVM API Documentation
00001 //===- SimplifyCFG.cpp - CFG Simplification Pass --------------------------===// 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 file implements dead code elimination and basic block merging. 00011 // 00012 // Specifically, this: 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 // 00019 //===----------------------------------------------------------------------===// 00020 00021 #include "llvm/Transforms/Scalar.h" 00022 #include "llvm/Transforms/Utils/Local.h" 00023 #include "llvm/Constants.h" 00024 #include "llvm/Instructions.h" 00025 #include "llvm/Module.h" 00026 #include "llvm/Support/CFG.h" 00027 #include "llvm/Pass.h" 00028 #include "llvm/ADT/Statistic.h" 00029 #include <set> 00030 using namespace llvm; 00031 00032 namespace { 00033 Statistic<> NumSimpl("cfgsimplify", "Number of blocks simplified"); 00034 00035 struct CFGSimplifyPass : public FunctionPass { 00036 virtual bool runOnFunction(Function &F); 00037 }; 00038 RegisterOpt<CFGSimplifyPass> X("simplifycfg", "Simplify the CFG"); 00039 } 00040 00041 // Public interface to the CFGSimplification pass 00042 FunctionPass *llvm::createCFGSimplificationPass() { 00043 return new CFGSimplifyPass(); 00044 } 00045 00046 static bool MarkAliveBlocks(BasicBlock *BB, std::set<BasicBlock*> &Reachable) { 00047 if (Reachable.count(BB)) return false; 00048 Reachable.insert(BB); 00049 00050 // Do a quick scan of the basic block, turning any obviously unreachable 00051 // instructions into LLVM unreachable insts. The instruction combining pass 00052 // canonnicalizes unreachable insts into stores to null or undef. 00053 for (BasicBlock::iterator BBI = BB->begin(), E = BB->end(); BBI != E; ++BBI) 00054 if (StoreInst *SI = dyn_cast<StoreInst>(BBI)) 00055 if (isa<ConstantPointerNull>(SI->getOperand(1)) || 00056 isa<UndefValue>(SI->getOperand(1))) { 00057 // Loop over all of the successors, removing BB's entry from any PHI 00058 // nodes. 00059 for (succ_iterator I = succ_begin(BB), SE = succ_end(BB); I != SE; ++I) 00060 (*I)->removePredecessor(BB); 00061 00062 new UnreachableInst(SI); 00063 00064 // All instructions after this are dead. 00065 for (; BBI != E; ) { 00066 if (!BBI->use_empty()) 00067 BBI->replaceAllUsesWith(UndefValue::get(BBI->getType())); 00068 BB->getInstList().erase(BBI++); 00069 } 00070 break; 00071 } 00072 00073 00074 bool Changed = ConstantFoldTerminator(BB); 00075 for (succ_iterator SI = succ_begin(BB), SE = succ_end(BB); SI != SE; ++SI) 00076 MarkAliveBlocks(*SI, Reachable); 00077 00078 return Changed; 00079 } 00080 00081 00082 // It is possible that we may require multiple passes over the code to fully 00083 // simplify the CFG. 00084 // 00085 bool CFGSimplifyPass::runOnFunction(Function &F) { 00086 std::set<BasicBlock*> Reachable; 00087 bool Changed = MarkAliveBlocks(F.begin(), Reachable); 00088 00089 // If there are unreachable blocks in the CFG... 00090 if (Reachable.size() != F.size()) { 00091 assert(Reachable.size() < F.size()); 00092 NumSimpl += F.size()-Reachable.size(); 00093 00094 // Loop over all of the basic blocks that are not reachable, dropping all of 00095 // their internal references... 00096 for (Function::iterator BB = ++F.begin(), E = F.end(); BB != E; ++BB) 00097 if (!Reachable.count(BB)) { 00098 for (succ_iterator SI = succ_begin(BB), SE = succ_end(BB); SI!=SE; ++SI) 00099 if (Reachable.count(*SI)) 00100 (*SI)->removePredecessor(BB); 00101 BB->dropAllReferences(); 00102 } 00103 00104 for (Function::iterator I = ++F.begin(); I != F.end();) 00105 if (!Reachable.count(I)) 00106 I = F.getBasicBlockList().erase(I); 00107 else 00108 ++I; 00109 00110 Changed = true; 00111 } 00112 00113 bool LocalChange = true; 00114 while (LocalChange) { 00115 LocalChange = false; 00116 00117 // Loop over all of the basic blocks (except the first one) and remove them 00118 // if they are unneeded... 00119 // 00120 for (Function::iterator BBIt = ++F.begin(); BBIt != F.end(); ) { 00121 if (SimplifyCFG(BBIt++)) { 00122 LocalChange = true; 00123 ++NumSimpl; 00124 } 00125 } 00126 Changed |= LocalChange; 00127 } 00128 00129 return Changed; 00130 }