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