SimplifyCFGPass.cpp revision be04929f7fd76a921540e9901f24563e51dc1219
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/ADT/SmallPtrSet.h" 27#include "llvm/ADT/SmallVector.h" 28#include "llvm/ADT/Statistic.h" 29#include "llvm/Analysis/TargetTransformInfo.h" 30#include "llvm/IR/Attributes.h" 31#include "llvm/IR/Constants.h" 32#include "llvm/IR/DataLayout.h" 33#include "llvm/IR/Instructions.h" 34#include "llvm/IR/IntrinsicInst.h" 35#include "llvm/IR/Module.h" 36#include "llvm/Pass.h" 37#include "llvm/Support/CFG.h" 38#include "llvm/Transforms/Utils/Local.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 Reachable.insert(BB); 115 bool Changed = false; 116 do { 117 BB = Worklist.pop_back_val(); 118 119 // Do a quick scan of the basic block, turning any obviously unreachable 120 // instructions into LLVM unreachable insts. The instruction combining pass 121 // canonicalizes unreachable insts into stores to null or undef. 122 for (BasicBlock::iterator BBI = BB->begin(), E = BB->end(); BBI != E;++BBI){ 123 if (CallInst *CI = dyn_cast<CallInst>(BBI)) { 124 if (CI->doesNotReturn()) { 125 // If we found a call to a no-return function, insert an unreachable 126 // instruction after it. Make sure there isn't *already* one there 127 // though. 128 ++BBI; 129 if (!isa<UnreachableInst>(BBI)) { 130 // Don't insert a call to llvm.trap right before the unreachable. 131 changeToUnreachable(BBI, false); 132 Changed = true; 133 } 134 break; 135 } 136 } 137 138 // Store to undef and store to null are undefined and used to signal that 139 // they should be changed to unreachable by passes that can't modify the 140 // CFG. 141 if (StoreInst *SI = dyn_cast<StoreInst>(BBI)) { 142 // Don't touch volatile stores. 143 if (SI->isVolatile()) continue; 144 145 Value *Ptr = SI->getOperand(1); 146 147 if (isa<UndefValue>(Ptr) || 148 (isa<ConstantPointerNull>(Ptr) && 149 SI->getPointerAddressSpace() == 0)) { 150 changeToUnreachable(SI, true); 151 Changed = true; 152 break; 153 } 154 } 155 } 156 157 // Turn invokes that call 'nounwind' functions into ordinary calls. 158 if (InvokeInst *II = dyn_cast<InvokeInst>(BB->getTerminator())) { 159 Value *Callee = II->getCalledValue(); 160 if (isa<ConstantPointerNull>(Callee) || isa<UndefValue>(Callee)) { 161 changeToUnreachable(II, true); 162 Changed = true; 163 } else if (II->doesNotThrow()) { 164 if (II->use_empty() && II->onlyReadsMemory()) { 165 // jump to the normal destination branch. 166 BranchInst::Create(II->getNormalDest(), II); 167 II->getUnwindDest()->removePredecessor(II->getParent()); 168 II->eraseFromParent(); 169 } else 170 changeToCall(II); 171 Changed = true; 172 } 173 } 174 175 Changed |= ConstantFoldTerminator(BB, true); 176 for (succ_iterator SI = succ_begin(BB), SE = succ_end(BB); SI != SE; ++SI) 177 if (Reachable.insert(*SI)) 178 Worklist.push_back(*SI); 179 } while (!Worklist.empty()); 180 return Changed; 181} 182 183/// removeUnreachableBlocksFromFn - Remove blocks that are not reachable, even 184/// if they are in a dead cycle. Return true if a change was made, false 185/// otherwise. 186static bool removeUnreachableBlocksFromFn(Function &F) { 187 SmallPtrSet<BasicBlock*, 128> Reachable; 188 bool Changed = markAliveBlocks(F.begin(), Reachable); 189 190 // If there are unreachable blocks in the CFG... 191 if (Reachable.size() == F.size()) 192 return Changed; 193 194 assert(Reachable.size() < F.size()); 195 NumSimpl += F.size()-Reachable.size(); 196 197 // Loop over all of the basic blocks that are not reachable, dropping all of 198 // their internal references... 199 for (Function::iterator BB = ++F.begin(), E = F.end(); BB != E; ++BB) { 200 if (Reachable.count(BB)) 201 continue; 202 203 for (succ_iterator SI = succ_begin(BB), SE = succ_end(BB); SI != SE; ++SI) 204 if (Reachable.count(*SI)) 205 (*SI)->removePredecessor(BB); 206 BB->dropAllReferences(); 207 } 208 209 for (Function::iterator I = ++F.begin(); I != F.end();) 210 if (!Reachable.count(I)) 211 I = F.getBasicBlockList().erase(I); 212 else 213 ++I; 214 215 return true; 216} 217 218/// mergeEmptyReturnBlocks - If we have more than one empty (other than phi 219/// node) return blocks, merge them together to promote recursive block merging. 220static bool mergeEmptyReturnBlocks(Function &F) { 221 bool Changed = false; 222 223 BasicBlock *RetBlock = 0; 224 225 // Scan all the blocks in the function, looking for empty return blocks. 226 for (Function::iterator BBI = F.begin(), E = F.end(); BBI != E; ) { 227 BasicBlock &BB = *BBI++; 228 229 // Only look at return blocks. 230 ReturnInst *Ret = dyn_cast<ReturnInst>(BB.getTerminator()); 231 if (Ret == 0) continue; 232 233 // Only look at the block if it is empty or the only other thing in it is a 234 // single PHI node that is the operand to the return. 235 if (Ret != &BB.front()) { 236 // Check for something else in the block. 237 BasicBlock::iterator I = Ret; 238 --I; 239 // Skip over debug info. 240 while (isa<DbgInfoIntrinsic>(I) && I != BB.begin()) 241 --I; 242 if (!isa<DbgInfoIntrinsic>(I) && 243 (!isa<PHINode>(I) || I != BB.begin() || 244 Ret->getNumOperands() == 0 || 245 Ret->getOperand(0) != I)) 246 continue; 247 } 248 249 // If this is the first returning block, remember it and keep going. 250 if (RetBlock == 0) { 251 RetBlock = &BB; 252 continue; 253 } 254 255 // Otherwise, we found a duplicate return block. Merge the two. 256 Changed = true; 257 258 // Case when there is no input to the return or when the returned values 259 // agree is trivial. Note that they can't agree if there are phis in the 260 // blocks. 261 if (Ret->getNumOperands() == 0 || 262 Ret->getOperand(0) == 263 cast<ReturnInst>(RetBlock->getTerminator())->getOperand(0)) { 264 BB.replaceAllUsesWith(RetBlock); 265 BB.eraseFromParent(); 266 continue; 267 } 268 269 // If the canonical return block has no PHI node, create one now. 270 PHINode *RetBlockPHI = dyn_cast<PHINode>(RetBlock->begin()); 271 if (RetBlockPHI == 0) { 272 Value *InVal = cast<ReturnInst>(RetBlock->getTerminator())->getOperand(0); 273 pred_iterator PB = pred_begin(RetBlock), PE = pred_end(RetBlock); 274 RetBlockPHI = PHINode::Create(Ret->getOperand(0)->getType(), 275 std::distance(PB, PE), "merge", 276 &RetBlock->front()); 277 278 for (pred_iterator PI = PB; PI != PE; ++PI) 279 RetBlockPHI->addIncoming(InVal, *PI); 280 RetBlock->getTerminator()->setOperand(0, RetBlockPHI); 281 } 282 283 // Turn BB into a block that just unconditionally branches to the return 284 // block. This handles the case when the two return blocks have a common 285 // predecessor but that return different things. 286 RetBlockPHI->addIncoming(Ret->getOperand(0), &BB); 287 BB.getTerminator()->eraseFromParent(); 288 BranchInst::Create(RetBlock, &BB); 289 } 290 291 return Changed; 292} 293 294/// iterativelySimplifyCFG - Call SimplifyCFG on all the blocks in the function, 295/// iterating until no more changes are made. 296static bool iterativelySimplifyCFG(Function &F, const DataLayout *TD, 297 const TargetTransformInfo *TTI) { 298 bool Changed = false; 299 bool LocalChange = true; 300 while (LocalChange) { 301 LocalChange = false; 302 303 // Loop over all of the basic blocks and remove them if they are unneeded... 304 // 305 for (Function::iterator BBIt = F.begin(); BBIt != F.end(); ) { 306 if (SimplifyCFG(BBIt++, TD, TTI)) { 307 LocalChange = true; 308 ++NumSimpl; 309 } 310 } 311 Changed |= LocalChange; 312 } 313 return Changed; 314} 315 316// It is possible that we may require multiple passes over the code to fully 317// simplify the CFG. 318// 319bool CFGSimplifyPass::runOnFunction(Function &F) { 320 const DataLayout *TD = getAnalysisIfAvailable<DataLayout>(); 321 const TargetTransformInfo *TTI = 322 getAnalysisIfAvailable<TargetTransformInfo>(); 323 bool EverChanged = removeUnreachableBlocksFromFn(F); 324 EverChanged |= mergeEmptyReturnBlocks(F); 325 EverChanged |= iterativelySimplifyCFG(F, TD, TTI); 326 327 // If neither pass changed anything, we're done. 328 if (!EverChanged) return false; 329 330 // iterativelySimplifyCFG can (rarely) make some loops dead. If this happens, 331 // removeUnreachableBlocksFromFn is needed to nuke them, which means we should 332 // iterate between the two optimizations. We structure the code like this to 333 // avoid reruning iterativelySimplifyCFG if the second pass of 334 // removeUnreachableBlocksFromFn doesn't do anything. 335 if (!removeUnreachableBlocksFromFn(F)) 336 return true; 337 338 do { 339 EverChanged = iterativelySimplifyCFG(F, TD, TTI); 340 EverChanged |= removeUnreachableBlocksFromFn(F); 341 } while (EverChanged); 342 343 return true; 344} 345