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