1 //===- SimplifyCFGPass.cpp - CFG Simplification Pass ----------------------===// 2 // 3 // The LLVM Compiler Infrastructure 4 // 5 // This file is distributed under the University of Illinois Open Source 6 // License. See LICENSE.TXT for details. 7 // 8 //===----------------------------------------------------------------------===// 9 // 10 // This file implements dead code elimination and basic block merging, along 11 // with a collection of other peephole control flow optimizations. For example: 12 // 13 // * Removes basic blocks with no predecessors. 14 // * Merges a basic block into its predecessor if there is only one and the 15 // predecessor only has one successor. 16 // * Eliminates PHI nodes for basic blocks with a single predecessor. 17 // * Eliminates a basic block that only contains an unconditional branch. 18 // * Changes invoke instructions to nounwind functions to be calls. 19 // * Change things like "if (x) if (y)" into "if (x&y)". 20 // * etc.. 21 // 22 //===----------------------------------------------------------------------===// 23 24 #define DEBUG_TYPE "simplifycfg" 25 #include "llvm/Transforms/Scalar.h" 26 #include "llvm/Transforms/Utils/Local.h" 27 #include "llvm/Constants.h" 28 #include "llvm/Instructions.h" 29 #include "llvm/LLVMContext.h" 30 #include "llvm/Module.h" 31 #include "llvm/Attributes.h" 32 #include "llvm/Support/CFG.h" 33 #include "llvm/Support/Compiler.h" 34 #include "llvm/Pass.h" 35 #include "llvm/ADT/SmallVector.h" 36 #include "llvm/ADT/SmallPtrSet.h" 37 #include "llvm/ADT/Statistic.h" 38 using namespace llvm; 39 40 STATISTIC(NumSimpl, "Number of blocks simplified"); 41 42 namespace { 43 struct VISIBILITY_HIDDEN CFGSimplifyPass : public FunctionPass { 44 static char ID; // Pass identification, replacement for typeid 45 CFGSimplifyPass() : FunctionPass(&ID) {} 46 47 virtual bool runOnFunction(Function &F); 48 }; 49 } 50 51 char CFGSimplifyPass::ID = 0; 52 static RegisterPass<CFGSimplifyPass> X("simplifycfg", "Simplify the CFG"); 53 54 // Public interface to the CFGSimplification pass 55 FunctionPass *llvm::createCFGSimplificationPass() { 56 return new CFGSimplifyPass(); 57 } 58 59 /// ChangeToUnreachable - Insert an unreachable instruction before the specified 60 /// instruction, making it and the rest of the code in the block dead. 61 static void ChangeToUnreachable(Instruction *I, LLVMContext &Context) { 62 BasicBlock *BB = I->getParent(); 63 // Loop over all of the successors, removing BB's entry from any PHI 64 // nodes. 65 for (succ_iterator SI = succ_begin(BB), SE = succ_end(BB); SI != SE; ++SI) 66 (*SI)->removePredecessor(BB); 67 68 new UnreachableInst(I->getContext(), I); 69 70 // All instructions after this are dead. 71 BasicBlock::iterator BBI = I, BBE = BB->end(); 72 while (BBI != BBE) { 73 if (!BBI->use_empty()) 74 BBI->replaceAllUsesWith(UndefValue::get(BBI->getType())); 75 BB->getInstList().erase(BBI++); 76 } 77 } 78 79 /// ChangeToCall - Convert the specified invoke into a normal call. 80 static void ChangeToCall(InvokeInst *II) { 81 BasicBlock *BB = II->getParent(); 82 SmallVector<Value*, 8> Args(II->op_begin()+3, II->op_end()); 83 CallInst *NewCall = CallInst::Create(II->getCalledValue(), Args.begin(), 84 Args.end(), "", II); 85 NewCall->takeName(II); 86 NewCall->setCallingConv(II->getCallingConv()); 87 NewCall->setAttributes(II->getAttributes()); 88 II->replaceAllUsesWith(NewCall); 89 90 // Follow the call by a branch to the normal destination. 91 BranchInst::Create(II->getNormalDest(), II); 92 93 // Update PHI nodes in the unwind destination 94 II->getUnwindDest()->removePredecessor(BB); 95 BB->getInstList().erase(II); 96 } 97 98 static bool MarkAliveBlocks(BasicBlock *BB, 99 SmallPtrSet<BasicBlock*, 128> &Reachable, 100 LLVMContext &Context) { 101 102 SmallVector<BasicBlock*, 128> Worklist; 103 Worklist.push_back(BB); 104 bool Changed = false; 105 while (!Worklist.empty()) { 106 BB = Worklist.back(); 107 Worklist.pop_back(); 108 109 if (!Reachable.insert(BB)) 110 continue; 111 112 // Do a quick scan of the basic block, turning any obviously unreachable 113 // instructions into LLVM unreachable insts. The instruction combining pass 114 // canonicalizes unreachable insts into stores to null or undef. 115 for (BasicBlock::iterator BBI = BB->begin(), E = BB->end(); BBI != E;++BBI){ 116 if (CallInst *CI = dyn_cast<CallInst>(BBI)) { 117 if (CI->doesNotReturn()) { 118 // If we found a call to a no-return function, insert an unreachable 119 // instruction after it. Make sure there isn't *already* one there 120 // though. 121 ++BBI; 122 if (!isa<UnreachableInst>(BBI)) { 123 ChangeToUnreachable(BBI, Context); 124 Changed = true; 125 } 126 break; 127 } 128 } 129 130 if (StoreInst *SI = dyn_cast<StoreInst>(BBI)) { 131 Value *Ptr = SI->getOperand(1); 132 133 if (isa<UndefValue>(Ptr) || 134 (isa<ConstantPointerNull>(Ptr) && 135 cast<PointerType>(Ptr->getType())->getAddressSpace() == 0)) { 136 ChangeToUnreachable(SI, Context); 137 Changed = true; 138 break; 139 } 140 } 141 } 142 143 // Turn invokes that call 'nounwind' functions into ordinary calls. 144 if (InvokeInst *II = dyn_cast<InvokeInst>(BB->getTerminator())) 145 if (II->doesNotThrow()) { 146 ChangeToCall(II); 147 Changed = true; 148 } 149 150 Changed |= ConstantFoldTerminator(BB); 151 for (succ_iterator SI = succ_begin(BB), SE = succ_end(BB); SI != SE; ++SI) 152 Worklist.push_back(*SI); 153 } 154 return Changed; 155 } 156 157 /// RemoveUnreachableBlocksFromFn - Remove blocks that are not reachable, even 158 /// if they are in a dead cycle. Return true if a change was made, false 159 /// otherwise. 160 static bool RemoveUnreachableBlocksFromFn(Function &F) { 161 SmallPtrSet<BasicBlock*, 128> Reachable; 162 bool Changed = MarkAliveBlocks(F.begin(), Reachable, F.getContext()); 163 164 // If there are unreachable blocks in the CFG... 165 if (Reachable.size() == F.size()) 166 return Changed; 167 168 assert(Reachable.size() < F.size()); 169 NumSimpl += F.size()-Reachable.size(); 170 171 // Loop over all of the basic blocks that are not reachable, dropping all of 172 // their internal references... 173 for (Function::iterator BB = ++F.begin(), E = F.end(); BB != E; ++BB) { 174 if (Reachable.count(BB)) 175 continue; 176 177 for (succ_iterator SI = succ_begin(BB), SE = succ_end(BB); SI != SE; ++SI) 178 if (Reachable.count(*SI)) 179 (*SI)->removePredecessor(BB); 180 BB->dropAllReferences(); 181 } 182 183 for (Function::iterator I = ++F.begin(); I != F.end();) 184 if (!Reachable.count(I)) 185 I = F.getBasicBlockList().erase(I); 186 else 187 ++I; 188 189 return true; 190 } 191 192 /// IterativeSimplifyCFG - Call SimplifyCFG on all the blocks in the function, 193 /// iterating until no more changes are made. 194 static bool IterativeSimplifyCFG(Function &F) { 195 bool Changed = false; 196 bool LocalChange = true; 197 while (LocalChange) { 198 LocalChange = false; 199 200 // Loop over all of the basic blocks (except the first one) and remove them 201 // if they are unneeded... 202 // 203 for (Function::iterator BBIt = ++F.begin(); BBIt != F.end(); ) { 204 if (SimplifyCFG(BBIt++)) { 205 LocalChange = true; 206 ++NumSimpl; 207 } 208 } 209 Changed |= LocalChange; 210 } 211 return Changed; 212 } 213 214 // It is possible that we may require multiple passes over the code to fully 215 // simplify the CFG. 216 // 217 bool CFGSimplifyPass::runOnFunction(Function &F) { 218 bool EverChanged = RemoveUnreachableBlocksFromFn(F); 219 EverChanged |= IterativeSimplifyCFG(F); 220 221 // If neither pass changed anything, we're done. 222 if (!EverChanged) return false; 223 224 // IterativeSimplifyCFG can (rarely) make some loops dead. If this happens, 225 // RemoveUnreachableBlocksFromFn is needed to nuke them, which means we should 226 // iterate between the two optimizations. We structure the code like this to 227 // avoid reruning IterativeSimplifyCFG if the second pass of 228 // RemoveUnreachableBlocksFromFn doesn't do anything. 229 if (!RemoveUnreachableBlocksFromFn(F)) 230 return true; 231 232 do { 233 EverChanged = IterativeSimplifyCFG(F); 234 EverChanged |= RemoveUnreachableBlocksFromFn(F); 235 } while (EverChanged); 236 237 return true; 238 } 239