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/Target/TargetData.h" 35#include "llvm/ADT/SmallVector.h" 36#include "llvm/ADT/SmallPtrSet.h" 37#include "llvm/ADT/Statistic.h" 38using namespace llvm; 39 40STATISTIC(NumSimpl, "Number of blocks simplified"); 41 42namespace { 43 struct CFGSimplifyPass : public FunctionPass { 44 static char ID; // Pass identification, replacement for typeid 45 CFGSimplifyPass() : FunctionPass(ID) { 46 initializeCFGSimplifyPassPass(*PassRegistry::getPassRegistry()); 47 } 48 49 virtual bool runOnFunction(Function &F); 50 }; 51} 52 53char CFGSimplifyPass::ID = 0; 54INITIALIZE_PASS(CFGSimplifyPass, "simplifycfg", 55 "Simplify the CFG", false, false) 56 57// Public interface to the CFGSimplification pass 58FunctionPass *llvm::createCFGSimplificationPass() { 59 return new CFGSimplifyPass(); 60} 61 62/// changeToUnreachable - Insert an unreachable instruction before the specified 63/// instruction, making it and the rest of the code in the block dead. 64static void changeToUnreachable(Instruction *I, bool UseLLVMTrap) { 65 BasicBlock *BB = I->getParent(); 66 // Loop over all of the successors, removing BB's entry from any PHI 67 // nodes. 68 for (succ_iterator SI = succ_begin(BB), SE = succ_end(BB); SI != SE; ++SI) 69 (*SI)->removePredecessor(BB); 70 71 // Insert a call to llvm.trap right before this. This turns the undefined 72 // behavior into a hard fail instead of falling through into random code. 73 if (UseLLVMTrap) { 74 Function *TrapFn = 75 Intrinsic::getDeclaration(BB->getParent()->getParent(), Intrinsic::trap); 76 CallInst *CallTrap = CallInst::Create(TrapFn, "", I); 77 CallTrap->setDebugLoc(I->getDebugLoc()); 78 } 79 new UnreachableInst(I->getContext(), I); 80 81 // All instructions after this are dead. 82 BasicBlock::iterator BBI = I, BBE = BB->end(); 83 while (BBI != BBE) { 84 if (!BBI->use_empty()) 85 BBI->replaceAllUsesWith(UndefValue::get(BBI->getType())); 86 BB->getInstList().erase(BBI++); 87 } 88} 89 90/// changeToCall - Convert the specified invoke into a normal call. 91static void changeToCall(InvokeInst *II) { 92 SmallVector<Value*, 8> Args(II->op_begin(), II->op_end() - 3); 93 CallInst *NewCall = CallInst::Create(II->getCalledValue(), Args, "", II); 94 NewCall->takeName(II); 95 NewCall->setCallingConv(II->getCallingConv()); 96 NewCall->setAttributes(II->getAttributes()); 97 NewCall->setDebugLoc(II->getDebugLoc()); 98 II->replaceAllUsesWith(NewCall); 99 100 // Follow the call by a branch to the normal destination. 101 BranchInst::Create(II->getNormalDest(), II); 102 103 // Update PHI nodes in the unwind destination 104 II->getUnwindDest()->removePredecessor(II->getParent()); 105 II->eraseFromParent(); 106} 107 108static bool markAliveBlocks(BasicBlock *BB, 109 SmallPtrSet<BasicBlock*, 128> &Reachable) { 110 111 SmallVector<BasicBlock*, 128> Worklist; 112 Worklist.push_back(BB); 113 bool Changed = false; 114 do { 115 BB = Worklist.pop_back_val(); 116 117 if (!Reachable.insert(BB)) 118 continue; 119 120 // Do a quick scan of the basic block, turning any obviously unreachable 121 // instructions into LLVM unreachable insts. The instruction combining pass 122 // canonicalizes unreachable insts into stores to null or undef. 123 for (BasicBlock::iterator BBI = BB->begin(), E = BB->end(); BBI != E;++BBI){ 124 if (CallInst *CI = dyn_cast<CallInst>(BBI)) { 125 if (CI->doesNotReturn()) { 126 // If we found a call to a no-return function, insert an unreachable 127 // instruction after it. Make sure there isn't *already* one there 128 // though. 129 ++BBI; 130 if (!isa<UnreachableInst>(BBI)) { 131 // Don't insert a call to llvm.trap right before the unreachable. 132 changeToUnreachable(BBI, false); 133 Changed = true; 134 } 135 break; 136 } 137 } 138 139 // Store to undef and store to null are undefined and used to signal that 140 // they should be changed to unreachable by passes that can't modify the 141 // CFG. 142 if (StoreInst *SI = dyn_cast<StoreInst>(BBI)) { 143 // Don't touch volatile stores. 144 if (SI->isVolatile()) continue; 145 146 Value *Ptr = SI->getOperand(1); 147 148 if (isa<UndefValue>(Ptr) || 149 (isa<ConstantPointerNull>(Ptr) && 150 SI->getPointerAddressSpace() == 0)) { 151 changeToUnreachable(SI, true); 152 Changed = true; 153 break; 154 } 155 } 156 } 157 158 // Turn invokes that call 'nounwind' functions into ordinary calls. 159 if (InvokeInst *II = dyn_cast<InvokeInst>(BB->getTerminator())) { 160 Value *Callee = II->getCalledValue(); 161 if (isa<ConstantPointerNull>(Callee) || isa<UndefValue>(Callee)) { 162 changeToUnreachable(II, true); 163 Changed = true; 164 } else if (II->doesNotThrow()) { 165 if (II->use_empty() && II->onlyReadsMemory()) { 166 // jump to the normal destination branch. 167 BranchInst::Create(II->getNormalDest(), II); 168 II->getUnwindDest()->removePredecessor(II->getParent()); 169 II->eraseFromParent(); 170 } else 171 changeToCall(II); 172 Changed = true; 173 } 174 } 175 176 Changed |= ConstantFoldTerminator(BB, true); 177 for (succ_iterator SI = succ_begin(BB), SE = succ_end(BB); SI != SE; ++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 TargetData *TD) { 297 bool Changed = false; 298 bool LocalChange = true; 299 while (LocalChange) { 300 LocalChange = false; 301 302 // Loop over all of the basic blocks and remove them if they are unneeded... 303 // 304 for (Function::iterator BBIt = F.begin(); BBIt != F.end(); ) { 305 if (SimplifyCFG(BBIt++, TD)) { 306 LocalChange = true; 307 ++NumSimpl; 308 } 309 } 310 Changed |= LocalChange; 311 } 312 return Changed; 313} 314 315// It is possible that we may require multiple passes over the code to fully 316// simplify the CFG. 317// 318bool CFGSimplifyPass::runOnFunction(Function &F) { 319 const TargetData *TD = getAnalysisIfAvailable<TargetData>(); 320 bool EverChanged = removeUnreachableBlocksFromFn(F); 321 EverChanged |= mergeEmptyReturnBlocks(F); 322 EverChanged |= iterativelySimplifyCFG(F, TD); 323 324 // If neither pass changed anything, we're done. 325 if (!EverChanged) return false; 326 327 // iterativelySimplifyCFG can (rarely) make some loops dead. If this happens, 328 // removeUnreachableBlocksFromFn is needed to nuke them, which means we should 329 // iterate between the two optimizations. We structure the code like this to 330 // avoid reruning iterativelySimplifyCFG if the second pass of 331 // removeUnreachableBlocksFromFn doesn't do anything. 332 if (!removeUnreachableBlocksFromFn(F)) 333 return true; 334 335 do { 336 EverChanged = iterativelySimplifyCFG(F, TD); 337 EverChanged |= removeUnreachableBlocksFromFn(F); 338 } while (EverChanged); 339 340 return true; 341} 342