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