UnreachableBlockElim.cpp revision 551ccae044b0ff658fe629dd67edd5ffe75d10e8
1fc3c82a804c9b5eda24d96c21f7e6ff66bc2c529Chris Lattner//===-- UnreachableBlockElim.cpp - Remove unreachable blocks for codegen --===// 2fc3c82a804c9b5eda24d96c21f7e6ff66bc2c529Chris Lattner// 3fc3c82a804c9b5eda24d96c21f7e6ff66bc2c529Chris Lattner// The LLVM Compiler Infrastructure 4fc3c82a804c9b5eda24d96c21f7e6ff66bc2c529Chris Lattner// 5fc3c82a804c9b5eda24d96c21f7e6ff66bc2c529Chris Lattner// This file was developed by the LLVM research group and is distributed under 6fc3c82a804c9b5eda24d96c21f7e6ff66bc2c529Chris Lattner// the University of Illinois Open Source License. See LICENSE.TXT for details. 7fc3c82a804c9b5eda24d96c21f7e6ff66bc2c529Chris Lattner// 8fc3c82a804c9b5eda24d96c21f7e6ff66bc2c529Chris Lattner//===----------------------------------------------------------------------===// 9fc3c82a804c9b5eda24d96c21f7e6ff66bc2c529Chris Lattner// 10fc3c82a804c9b5eda24d96c21f7e6ff66bc2c529Chris Lattner// This pass is an extremely simple version of the SimplifyCFG pass. Its sole 11fc3c82a804c9b5eda24d96c21f7e6ff66bc2c529Chris Lattner// job is to delete LLVM basic blocks that are not reachable from the entry 12fc3c82a804c9b5eda24d96c21f7e6ff66bc2c529Chris Lattner// node. To do this, it performs a simple depth first traversal of the CFG, 13fc3c82a804c9b5eda24d96c21f7e6ff66bc2c529Chris Lattner// then deletes any unvisited nodes. 14fc3c82a804c9b5eda24d96c21f7e6ff66bc2c529Chris Lattner// 15fc3c82a804c9b5eda24d96c21f7e6ff66bc2c529Chris Lattner// Note that this pass is really a hack. In particular, the instruction 16fc3c82a804c9b5eda24d96c21f7e6ff66bc2c529Chris Lattner// selectors for various targets should just not generate code for unreachable 17fc3c82a804c9b5eda24d96c21f7e6ff66bc2c529Chris Lattner// blocks. Until LLVM has a more systematic way of defining instruction 18fc3c82a804c9b5eda24d96c21f7e6ff66bc2c529Chris Lattner// selectors, however, we cannot really expect them to handle additional 19fc3c82a804c9b5eda24d96c21f7e6ff66bc2c529Chris Lattner// complexity. 20fc3c82a804c9b5eda24d96c21f7e6ff66bc2c529Chris Lattner// 21fc3c82a804c9b5eda24d96c21f7e6ff66bc2c529Chris Lattner//===----------------------------------------------------------------------===// 22fc3c82a804c9b5eda24d96c21f7e6ff66bc2c529Chris Lattner 23fc3c82a804c9b5eda24d96c21f7e6ff66bc2c529Chris Lattner#include "llvm/CodeGen/Passes.h" 247f0566c1233ba4378c2c5531ddbc9eb8ad1868daChris Lattner#include "llvm/Constant.h" 25879313ae3aa2052cc40ba6f0f25c17e7a5a6f0daChris Lattner#include "llvm/Instructions.h" 26fc3c82a804c9b5eda24d96c21f7e6ff66bc2c529Chris Lattner#include "llvm/Function.h" 27fc3c82a804c9b5eda24d96c21f7e6ff66bc2c529Chris Lattner#include "llvm/Pass.h" 28fc3c82a804c9b5eda24d96c21f7e6ff66bc2c529Chris Lattner#include "llvm/Support/CFG.h" 29551ccae044b0ff658fe629dd67edd5ffe75d10e8Reid Spencer#include "llvm/ADT/DepthFirstIterator.h" 30fc3c82a804c9b5eda24d96c21f7e6ff66bc2c529Chris Lattnerusing namespace llvm; 31fc3c82a804c9b5eda24d96c21f7e6ff66bc2c529Chris Lattner 32fc3c82a804c9b5eda24d96c21f7e6ff66bc2c529Chris Lattnernamespace { 33fc3c82a804c9b5eda24d96c21f7e6ff66bc2c529Chris Lattner class UnreachableBlockElim : public FunctionPass { 34fc3c82a804c9b5eda24d96c21f7e6ff66bc2c529Chris Lattner virtual bool runOnFunction(Function &F); 35fc3c82a804c9b5eda24d96c21f7e6ff66bc2c529Chris Lattner }; 36fc3c82a804c9b5eda24d96c21f7e6ff66bc2c529Chris Lattner RegisterOpt<UnreachableBlockElim> 37fc3c82a804c9b5eda24d96c21f7e6ff66bc2c529Chris Lattner X("unreachableblockelim", "Remove unreachable blocks from the CFG"); 38fc3c82a804c9b5eda24d96c21f7e6ff66bc2c529Chris Lattner} 39fc3c82a804c9b5eda24d96c21f7e6ff66bc2c529Chris Lattner 40fc3c82a804c9b5eda24d96c21f7e6ff66bc2c529Chris LattnerFunctionPass *llvm::createUnreachableBlockEliminationPass() { 41fc3c82a804c9b5eda24d96c21f7e6ff66bc2c529Chris Lattner return new UnreachableBlockElim(); 42fc3c82a804c9b5eda24d96c21f7e6ff66bc2c529Chris Lattner} 43fc3c82a804c9b5eda24d96c21f7e6ff66bc2c529Chris Lattner 44fc3c82a804c9b5eda24d96c21f7e6ff66bc2c529Chris Lattnerbool UnreachableBlockElim::runOnFunction(Function &F) { 45fc3c82a804c9b5eda24d96c21f7e6ff66bc2c529Chris Lattner std::set<BasicBlock*> Reachable; 46fc3c82a804c9b5eda24d96c21f7e6ff66bc2c529Chris Lattner 47fc3c82a804c9b5eda24d96c21f7e6ff66bc2c529Chris Lattner // Mark all reachable blocks. 48fc3c82a804c9b5eda24d96c21f7e6ff66bc2c529Chris Lattner for (df_ext_iterator<Function*> I = df_ext_begin(&F, Reachable), 49fc3c82a804c9b5eda24d96c21f7e6ff66bc2c529Chris Lattner E = df_ext_end(&F, Reachable); I != E; ++I) 50fc3c82a804c9b5eda24d96c21f7e6ff66bc2c529Chris Lattner /* Mark all reachable blocks */; 51fc3c82a804c9b5eda24d96c21f7e6ff66bc2c529Chris Lattner 52fc3c82a804c9b5eda24d96c21f7e6ff66bc2c529Chris Lattner // Loop over all dead blocks, remembering them and deleting all instructions 53fc3c82a804c9b5eda24d96c21f7e6ff66bc2c529Chris Lattner // in them. 54fc3c82a804c9b5eda24d96c21f7e6ff66bc2c529Chris Lattner std::vector<BasicBlock*> DeadBlocks; 55fc3c82a804c9b5eda24d96c21f7e6ff66bc2c529Chris Lattner for (Function::iterator I = F.begin(), E = F.end(); I != E; ++I) 56fc3c82a804c9b5eda24d96c21f7e6ff66bc2c529Chris Lattner if (!Reachable.count(I)) { 577f0566c1233ba4378c2c5531ddbc9eb8ad1868daChris Lattner BasicBlock *BB = I; 587f0566c1233ba4378c2c5531ddbc9eb8ad1868daChris Lattner DeadBlocks.push_back(BB); 597f0566c1233ba4378c2c5531ddbc9eb8ad1868daChris Lattner while (PHINode *PN = dyn_cast<PHINode>(BB->begin())) { 607f0566c1233ba4378c2c5531ddbc9eb8ad1868daChris Lattner PN->replaceAllUsesWith(Constant::getNullValue(PN->getType())); 617f0566c1233ba4378c2c5531ddbc9eb8ad1868daChris Lattner BB->getInstList().pop_front(); 627f0566c1233ba4378c2c5531ddbc9eb8ad1868daChris Lattner } 637f0566c1233ba4378c2c5531ddbc9eb8ad1868daChris Lattner for (succ_iterator SI = succ_begin(BB), E = succ_end(BB); SI != E; ++SI) 647f0566c1233ba4378c2c5531ddbc9eb8ad1868daChris Lattner (*SI)->removePredecessor(BB); 657f0566c1233ba4378c2c5531ddbc9eb8ad1868daChris Lattner BB->dropAllReferences(); 66fc3c82a804c9b5eda24d96c21f7e6ff66bc2c529Chris Lattner } 67fc3c82a804c9b5eda24d96c21f7e6ff66bc2c529Chris Lattner 68fc3c82a804c9b5eda24d96c21f7e6ff66bc2c529Chris Lattner if (DeadBlocks.empty()) return false; 69fc3c82a804c9b5eda24d96c21f7e6ff66bc2c529Chris Lattner 70fc3c82a804c9b5eda24d96c21f7e6ff66bc2c529Chris Lattner // Actually remove the blocks now. 71fc3c82a804c9b5eda24d96c21f7e6ff66bc2c529Chris Lattner for (unsigned i = 0, e = DeadBlocks.size(); i != e; ++i) 72fc3c82a804c9b5eda24d96c21f7e6ff66bc2c529Chris Lattner F.getBasicBlockList().erase(DeadBlocks[i]); 73fc3c82a804c9b5eda24d96c21f7e6ff66bc2c529Chris Lattner 74fc3c82a804c9b5eda24d96c21f7e6ff66bc2c529Chris Lattner return true; 75fc3c82a804c9b5eda24d96c21f7e6ff66bc2c529Chris Lattner} 76