SimplifyCFGPass.cpp revision 04d7d13d301df66f6c232e41611145c062183bf3
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/IntrinsicInst.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/DataLayout.h" 35#include "llvm/ADT/SmallVector.h" 36#include "llvm/ADT/SmallPtrSet.h" 37#include "llvm/ADT/Statistic.h" 38#include "llvm/TargetTransformInfo.h" 39using namespace llvm; 40 41STATISTIC(NumSimpl, "Number of blocks simplified"); 42 43namespace { 44 struct CFGSimplifyPass : public FunctionPass { 45 static char ID; // Pass identification, replacement for typeid 46 CFGSimplifyPass() : FunctionPass(ID) { 47 initializeCFGSimplifyPassPass(*PassRegistry::getPassRegistry()); 48 } 49 50 virtual bool runOnFunction(Function &F); 51 }; 52} 53 54char CFGSimplifyPass::ID = 0; 55INITIALIZE_PASS(CFGSimplifyPass, "simplifycfg", 56 "Simplify the CFG", false, false) 57 58// Public interface to the CFGSimplification pass 59FunctionPass *llvm::createCFGSimplificationPass() { 60 return new CFGSimplifyPass(); 61} 62 63/// changeToUnreachable - Insert an unreachable instruction before the specified 64/// instruction, making it and the rest of the code in the block dead. 65static void changeToUnreachable(Instruction *I, bool UseLLVMTrap) { 66 BasicBlock *BB = I->getParent(); 67 // Loop over all of the successors, removing BB's entry from any PHI 68 // nodes. 69 for (succ_iterator SI = succ_begin(BB), SE = succ_end(BB); SI != SE; ++SI) 70 (*SI)->removePredecessor(BB); 71 72 // Insert a call to llvm.trap right before this. This turns the undefined 73 // behavior into a hard fail instead of falling through into random code. 74 if (UseLLVMTrap) { 75 Function *TrapFn = 76 Intrinsic::getDeclaration(BB->getParent()->getParent(), Intrinsic::trap); 77 CallInst *CallTrap = CallInst::Create(TrapFn, "", I); 78 CallTrap->setDebugLoc(I->getDebugLoc()); 79 } 80 new UnreachableInst(I->getContext(), I); 81 82 // All instructions after this are dead. 83 BasicBlock::iterator BBI = I, BBE = BB->end(); 84 while (BBI != BBE) { 85 if (!BBI->use_empty()) 86 BBI->replaceAllUsesWith(UndefValue::get(BBI->getType())); 87 BB->getInstList().erase(BBI++); 88 } 89} 90 91/// changeToCall - Convert the specified invoke into a normal call. 92static void changeToCall(InvokeInst *II) { 93 SmallVector<Value*, 8> Args(II->op_begin(), II->op_end() - 3); 94 CallInst *NewCall = CallInst::Create(II->getCalledValue(), Args, "", II); 95 NewCall->takeName(II); 96 NewCall->setCallingConv(II->getCallingConv()); 97 NewCall->setAttributes(II->getAttributes()); 98 NewCall->setDebugLoc(II->getDebugLoc()); 99 II->replaceAllUsesWith(NewCall); 100 101 // Follow the call by a branch to the normal destination. 102 BranchInst::Create(II->getNormalDest(), II); 103 104 // Update PHI nodes in the unwind destination 105 II->getUnwindDest()->removePredecessor(II->getParent()); 106 II->eraseFromParent(); 107} 108 109static bool markAliveBlocks(BasicBlock *BB, 110 SmallPtrSet<BasicBlock*, 128> &Reachable) { 111 112 SmallVector<BasicBlock*, 128> Worklist; 113 Worklist.push_back(BB); 114 bool Changed = false; 115 do { 116 BB = Worklist.pop_back_val(); 117 118 if (!Reachable.insert(BB)) 119 continue; 120 121 // Do a quick scan of the basic block, turning any obviously unreachable 122 // instructions into LLVM unreachable insts. The instruction combining pass 123 // canonicalizes unreachable insts into stores to null or undef. 124 for (BasicBlock::iterator BBI = BB->begin(), E = BB->end(); BBI != E;++BBI){ 125 if (CallInst *CI = dyn_cast<CallInst>(BBI)) { 126 if (CI->doesNotReturn()) { 127 // If we found a call to a no-return function, insert an unreachable 128 // instruction after it. Make sure there isn't *already* one there 129 // though. 130 ++BBI; 131 if (!isa<UnreachableInst>(BBI)) { 132 // Don't insert a call to llvm.trap right before the unreachable. 133 changeToUnreachable(BBI, false); 134 Changed = true; 135 } 136 break; 137 } 138 } 139 140 // Store to undef and store to null are undefined and used to signal that 141 // they should be changed to unreachable by passes that can't modify the 142 // CFG. 143 if (StoreInst *SI = dyn_cast<StoreInst>(BBI)) { 144 // Don't touch volatile stores. 145 if (SI->isVolatile()) continue; 146 147 Value *Ptr = SI->getOperand(1); 148 149 if (isa<UndefValue>(Ptr) || 150 (isa<ConstantPointerNull>(Ptr) && 151 SI->getPointerAddressSpace() == 0)) { 152 changeToUnreachable(SI, true); 153 Changed = true; 154 break; 155 } 156 } 157 } 158 159 // Turn invokes that call 'nounwind' functions into ordinary calls. 160 if (InvokeInst *II = dyn_cast<InvokeInst>(BB->getTerminator())) { 161 Value *Callee = II->getCalledValue(); 162 if (isa<ConstantPointerNull>(Callee) || isa<UndefValue>(Callee)) { 163 changeToUnreachable(II, true); 164 Changed = true; 165 } else if (II->doesNotThrow()) { 166 if (II->use_empty() && II->onlyReadsMemory()) { 167 // jump to the normal destination branch. 168 BranchInst::Create(II->getNormalDest(), II); 169 II->getUnwindDest()->removePredecessor(II->getParent()); 170 II->eraseFromParent(); 171 } else 172 changeToCall(II); 173 Changed = true; 174 } 175 } 176 177 Changed |= ConstantFoldTerminator(BB, true); 178 for (succ_iterator SI = succ_begin(BB), SE = succ_end(BB); SI != SE; ++SI) 179 Worklist.push_back(*SI); 180 } while (!Worklist.empty()); 181 return Changed; 182} 183 184/// removeUnreachableBlocksFromFn - Remove blocks that are not reachable, even 185/// if they are in a dead cycle. Return true if a change was made, false 186/// otherwise. 187static bool removeUnreachableBlocksFromFn(Function &F) { 188 SmallPtrSet<BasicBlock*, 128> Reachable; 189 bool Changed = markAliveBlocks(F.begin(), Reachable); 190 191 // If there are unreachable blocks in the CFG... 192 if (Reachable.size() == F.size()) 193 return Changed; 194 195 assert(Reachable.size() < F.size()); 196 NumSimpl += F.size()-Reachable.size(); 197 198 // Loop over all of the basic blocks that are not reachable, dropping all of 199 // their internal references... 200 for (Function::iterator BB = ++F.begin(), E = F.end(); BB != E; ++BB) { 201 if (Reachable.count(BB)) 202 continue; 203 204 for (succ_iterator SI = succ_begin(BB), SE = succ_end(BB); SI != SE; ++SI) 205 if (Reachable.count(*SI)) 206 (*SI)->removePredecessor(BB); 207 BB->dropAllReferences(); 208 } 209 210 for (Function::iterator I = ++F.begin(); I != F.end();) 211 if (!Reachable.count(I)) 212 I = F.getBasicBlockList().erase(I); 213 else 214 ++I; 215 216 return true; 217} 218 219/// mergeEmptyReturnBlocks - If we have more than one empty (other than phi 220/// node) return blocks, merge them together to promote recursive block merging. 221static bool mergeEmptyReturnBlocks(Function &F) { 222 bool Changed = false; 223 224 BasicBlock *RetBlock = 0; 225 226 // Scan all the blocks in the function, looking for empty return blocks. 227 for (Function::iterator BBI = F.begin(), E = F.end(); BBI != E; ) { 228 BasicBlock &BB = *BBI++; 229 230 // Only look at return blocks. 231 ReturnInst *Ret = dyn_cast<ReturnInst>(BB.getTerminator()); 232 if (Ret == 0) continue; 233 234 // Only look at the block if it is empty or the only other thing in it is a 235 // single PHI node that is the operand to the return. 236 if (Ret != &BB.front()) { 237 // Check for something else in the block. 238 BasicBlock::iterator I = Ret; 239 --I; 240 // Skip over debug info. 241 while (isa<DbgInfoIntrinsic>(I) && I != BB.begin()) 242 --I; 243 if (!isa<DbgInfoIntrinsic>(I) && 244 (!isa<PHINode>(I) || I != BB.begin() || 245 Ret->getNumOperands() == 0 || 246 Ret->getOperand(0) != I)) 247 continue; 248 } 249 250 // If this is the first returning block, remember it and keep going. 251 if (RetBlock == 0) { 252 RetBlock = &BB; 253 continue; 254 } 255 256 // Otherwise, we found a duplicate return block. Merge the two. 257 Changed = true; 258 259 // Case when there is no input to the return or when the returned values 260 // agree is trivial. Note that they can't agree if there are phis in the 261 // blocks. 262 if (Ret->getNumOperands() == 0 || 263 Ret->getOperand(0) == 264 cast<ReturnInst>(RetBlock->getTerminator())->getOperand(0)) { 265 BB.replaceAllUsesWith(RetBlock); 266 BB.eraseFromParent(); 267 continue; 268 } 269 270 // If the canonical return block has no PHI node, create one now. 271 PHINode *RetBlockPHI = dyn_cast<PHINode>(RetBlock->begin()); 272 if (RetBlockPHI == 0) { 273 Value *InVal = cast<ReturnInst>(RetBlock->getTerminator())->getOperand(0); 274 pred_iterator PB = pred_begin(RetBlock), PE = pred_end(RetBlock); 275 RetBlockPHI = PHINode::Create(Ret->getOperand(0)->getType(), 276 std::distance(PB, PE), "merge", 277 &RetBlock->front()); 278 279 for (pred_iterator PI = PB; PI != PE; ++PI) 280 RetBlockPHI->addIncoming(InVal, *PI); 281 RetBlock->getTerminator()->setOperand(0, RetBlockPHI); 282 } 283 284 // Turn BB into a block that just unconditionally branches to the return 285 // block. This handles the case when the two return blocks have a common 286 // predecessor but that return different things. 287 RetBlockPHI->addIncoming(Ret->getOperand(0), &BB); 288 BB.getTerminator()->eraseFromParent(); 289 BranchInst::Create(RetBlock, &BB); 290 } 291 292 return Changed; 293} 294 295/// iterativelySimplifyCFG - Call SimplifyCFG on all the blocks in the function, 296/// iterating until no more changes are made. 297static bool iterativelySimplifyCFG(Function &F, const DataLayout *TD, 298 const TargetTransformInfo *TTI) { 299 bool Changed = false; 300 bool LocalChange = true; 301 while (LocalChange) { 302 LocalChange = false; 303 304 // Loop over all of the basic blocks and remove them if they are unneeded... 305 // 306 for (Function::iterator BBIt = F.begin(); BBIt != F.end(); ) { 307 if (SimplifyCFG(BBIt++, TD, TTI)) { 308 LocalChange = true; 309 ++NumSimpl; 310 } 311 } 312 Changed |= LocalChange; 313 } 314 return Changed; 315} 316 317// It is possible that we may require multiple passes over the code to fully 318// simplify the CFG. 319// 320bool CFGSimplifyPass::runOnFunction(Function &F) { 321 const DataLayout *TD = getAnalysisIfAvailable<DataLayout>(); 322 const TargetTransformInfo *TTI = 323 getAnalysisIfAvailable<TargetTransformInfo>(); 324 bool EverChanged = removeUnreachableBlocksFromFn(F); 325 EverChanged |= mergeEmptyReturnBlocks(F); 326 EverChanged |= iterativelySimplifyCFG(F, TD, TTI); 327 328 // If neither pass changed anything, we're done. 329 if (!EverChanged) return false; 330 331 // iterativelySimplifyCFG can (rarely) make some loops dead. If this happens, 332 // removeUnreachableBlocksFromFn is needed to nuke them, which means we should 333 // iterate between the two optimizations. We structure the code like this to 334 // avoid reruning iterativelySimplifyCFG if the second pass of 335 // removeUnreachableBlocksFromFn doesn't do anything. 336 if (!removeUnreachableBlocksFromFn(F)) 337 return true; 338 339 do { 340 EverChanged = iterativelySimplifyCFG(F, TD, TTI); 341 EverChanged |= removeUnreachableBlocksFromFn(F); 342 } while (EverChanged); 343 344 return true; 345} 346