1 //===- SimplifyCFG.cpp - CFG Simplification Pass --------------------------===//
3 // The LLVM Compiler Infrastructure
5 // This file was developed by the LLVM research group and is distributed under
6 // the University of Illinois Open Source License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 // This file implements dead code elimination and basic block merging.
12 // Specifically, this:
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
19 //===----------------------------------------------------------------------===//
21 #define DEBUG_TYPE "simplifycfg"
22 #include "llvm/Transforms/Scalar.h"
23 #include "llvm/Transforms/Utils/Local.h"
24 #include "llvm/Constants.h"
25 #include "llvm/Instructions.h"
26 #include "llvm/Module.h"
27 #include "llvm/Support/CFG.h"
28 #include "llvm/Support/Compiler.h"
29 #include "llvm/Pass.h"
30 #include "llvm/ADT/SmallPtrSet.h"
31 #include "llvm/ADT/Statistic.h"
34 STATISTIC(NumSimpl, "Number of blocks simplified");
37 struct VISIBILITY_HIDDEN CFGSimplifyPass : public FunctionPass {
38 static char ID; // Pass identification, replacement for typeid
39 CFGSimplifyPass() : FunctionPass((intptr_t)&ID) {}
41 virtual bool runOnFunction(Function &F);
43 char CFGSimplifyPass::ID = 0;
44 RegisterPass<CFGSimplifyPass> X("simplifycfg", "Simplify the CFG");
47 // Public interface to the CFGSimplification pass
48 FunctionPass *llvm::createCFGSimplificationPass() {
49 return new CFGSimplifyPass();
52 static bool MarkAliveBlocks(BasicBlock *BB,
53 SmallPtrSet<BasicBlock*, 16> &Reachable) {
55 std::vector<BasicBlock*> Worklist;
56 Worklist.push_back(BB);
58 while (!Worklist.empty()) {
62 if (!Reachable.insert(BB))
65 // Do a quick scan of the basic block, turning any obviously unreachable
66 // instructions into LLVM unreachable insts. The instruction combining pass
67 // canonnicalizes unreachable insts into stores to null or undef.
68 for (BasicBlock::iterator BBI = BB->begin(), E = BB->end(); BBI != E; ++BBI)
69 if (StoreInst *SI = dyn_cast<StoreInst>(BBI))
70 if (isa<ConstantPointerNull>(SI->getOperand(1)) ||
71 isa<UndefValue>(SI->getOperand(1))) {
72 // Loop over all of the successors, removing BB's entry from any PHI
74 for (succ_iterator I = succ_begin(BB), SE = succ_end(BB); I != SE;++I)
75 (*I)->removePredecessor(BB);
77 new UnreachableInst(SI);
79 // All instructions after this are dead.
81 if (!BBI->use_empty())
82 BBI->replaceAllUsesWith(UndefValue::get(BBI->getType()));
83 BB->getInstList().erase(BBI++);
89 Changed |= ConstantFoldTerminator(BB);
90 for (succ_iterator SI = succ_begin(BB), SE = succ_end(BB); SI != SE; ++SI)
91 Worklist.push_back(*SI);
97 // It is possible that we may require multiple passes over the code to fully
100 bool CFGSimplifyPass::runOnFunction(Function &F) {
101 SmallPtrSet<BasicBlock*, 16> Reachable;
102 bool Changed = MarkAliveBlocks(F.begin(), Reachable);
104 // If there are unreachable blocks in the CFG...
105 if (Reachable.size() != F.size()) {
106 assert(Reachable.size() < F.size());
107 NumSimpl += F.size()-Reachable.size();
109 // Loop over all of the basic blocks that are not reachable, dropping all of
110 // their internal references...
111 for (Function::iterator BB = ++F.begin(), E = F.end(); BB != E; ++BB)
112 if (!Reachable.count(BB)) {
113 for (succ_iterator SI = succ_begin(BB), SE = succ_end(BB); SI!=SE; ++SI)
114 if (Reachable.count(*SI))
115 (*SI)->removePredecessor(BB);
116 BB->dropAllReferences();
119 for (Function::iterator I = ++F.begin(); I != F.end();)
120 if (!Reachable.count(I))
121 I = F.getBasicBlockList().erase(I);
128 bool LocalChange = true;
129 while (LocalChange) {
132 // Loop over all of the basic blocks (except the first one) and remove them
133 // if they are unneeded...
135 for (Function::iterator BBIt = ++F.begin(); BBIt != F.end(); ) {
136 if (SimplifyCFG(BBIt++)) {
141 Changed |= LocalChange;