UnreachableBlockElim.cpp revision ecd94c804a563f2a86572dcf1d2e81f397e19daa
1fc3c82a804c9b5eda24d96c21f7e6ff66bc2c529Chris Lattner//===-- UnreachableBlockElim.cpp - Remove unreachable blocks for codegen --===// 2edf128a7fa90f2b0b7ee24741a04a7ae1ecd6f7eMisha Brukman// 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. 7edf128a7fa90f2b0b7ee24741a04a7ae1ecd6f7eMisha Brukman// 8fc3c82a804c9b5eda24d96c21f7e6ff66bc2c529Chris Lattner//===----------------------------------------------------------------------===// 9edf128a7fa90f2b0b7ee24741a04a7ae1ecd6f7eMisha Brukman// 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" 285b3a4553c1da7e417a240379e2f510c77532c5c1Chris Lattner#include "llvm/Type.h" 29fc3c82a804c9b5eda24d96c21f7e6ff66bc2c529Chris Lattner#include "llvm/Support/CFG.h" 30a4f0b3a084d120cfc5b5bb06f64b222f5cb72740Chris Lattner#include "llvm/Support/Compiler.h" 31551ccae044b0ff658fe629dd67edd5ffe75d10e8Reid Spencer#include "llvm/ADT/DepthFirstIterator.h" 32fc3c82a804c9b5eda24d96c21f7e6ff66bc2c529Chris Lattnerusing namespace llvm; 33fc3c82a804c9b5eda24d96c21f7e6ff66bc2c529Chris Lattner 34fc3c82a804c9b5eda24d96c21f7e6ff66bc2c529Chris Lattnernamespace { 359525528a7dc5462b6374d38c81ba5c07b11741feChris Lattner class VISIBILITY_HIDDEN UnreachableBlockElim : public FunctionPass { 36fc3c82a804c9b5eda24d96c21f7e6ff66bc2c529Chris Lattner virtual bool runOnFunction(Function &F); 37794fd75c67a2cdc128d67342c6d88a504d186896Devang Patel public: 38ecd94c804a563f2a86572dcf1d2e81f397e19daaNick Lewycky static char ID; // Pass identification, replacement for typeid 39794fd75c67a2cdc128d67342c6d88a504d186896Devang Patel UnreachableBlockElim() : FunctionPass((intptr_t)&ID) {} 40fc3c82a804c9b5eda24d96c21f7e6ff66bc2c529Chris Lattner }; 411997473cf72957d0e70322e2fe6fe2ab141c58a6Devang Patel char UnreachableBlockElim::ID = 0; 427f8897f22e88271cfa114998a4d6088e7c8e8e11Chris Lattner RegisterPass<UnreachableBlockElim> 43fc3c82a804c9b5eda24d96c21f7e6ff66bc2c529Chris Lattner X("unreachableblockelim", "Remove unreachable blocks from the CFG"); 44fc3c82a804c9b5eda24d96c21f7e6ff66bc2c529Chris Lattner} 45fc3c82a804c9b5eda24d96c21f7e6ff66bc2c529Chris Lattner 46fc3c82a804c9b5eda24d96c21f7e6ff66bc2c529Chris LattnerFunctionPass *llvm::createUnreachableBlockEliminationPass() { 47fc3c82a804c9b5eda24d96c21f7e6ff66bc2c529Chris Lattner return new UnreachableBlockElim(); 48fc3c82a804c9b5eda24d96c21f7e6ff66bc2c529Chris Lattner} 49fc3c82a804c9b5eda24d96c21f7e6ff66bc2c529Chris Lattner 50fc3c82a804c9b5eda24d96c21f7e6ff66bc2c529Chris Lattnerbool UnreachableBlockElim::runOnFunction(Function &F) { 51fc3c82a804c9b5eda24d96c21f7e6ff66bc2c529Chris Lattner std::set<BasicBlock*> Reachable; 52fc3c82a804c9b5eda24d96c21f7e6ff66bc2c529Chris Lattner 53fc3c82a804c9b5eda24d96c21f7e6ff66bc2c529Chris Lattner // Mark all reachable blocks. 54fc3c82a804c9b5eda24d96c21f7e6ff66bc2c529Chris Lattner for (df_ext_iterator<Function*> I = df_ext_begin(&F, Reachable), 55fc3c82a804c9b5eda24d96c21f7e6ff66bc2c529Chris Lattner E = df_ext_end(&F, Reachable); I != E; ++I) 56fc3c82a804c9b5eda24d96c21f7e6ff66bc2c529Chris Lattner /* Mark all reachable blocks */; 57fc3c82a804c9b5eda24d96c21f7e6ff66bc2c529Chris Lattner 58fc3c82a804c9b5eda24d96c21f7e6ff66bc2c529Chris Lattner // Loop over all dead blocks, remembering them and deleting all instructions 59fc3c82a804c9b5eda24d96c21f7e6ff66bc2c529Chris Lattner // in them. 60fc3c82a804c9b5eda24d96c21f7e6ff66bc2c529Chris Lattner std::vector<BasicBlock*> DeadBlocks; 61fc3c82a804c9b5eda24d96c21f7e6ff66bc2c529Chris Lattner for (Function::iterator I = F.begin(), E = F.end(); I != E; ++I) 62fc3c82a804c9b5eda24d96c21f7e6ff66bc2c529Chris Lattner if (!Reachable.count(I)) { 637f0566c1233ba4378c2c5531ddbc9eb8ad1868daChris Lattner BasicBlock *BB = I; 647f0566c1233ba4378c2c5531ddbc9eb8ad1868daChris Lattner DeadBlocks.push_back(BB); 657f0566c1233ba4378c2c5531ddbc9eb8ad1868daChris Lattner while (PHINode *PN = dyn_cast<PHINode>(BB->begin())) { 667f0566c1233ba4378c2c5531ddbc9eb8ad1868daChris Lattner PN->replaceAllUsesWith(Constant::getNullValue(PN->getType())); 677f0566c1233ba4378c2c5531ddbc9eb8ad1868daChris Lattner BB->getInstList().pop_front(); 687f0566c1233ba4378c2c5531ddbc9eb8ad1868daChris Lattner } 697f0566c1233ba4378c2c5531ddbc9eb8ad1868daChris Lattner for (succ_iterator SI = succ_begin(BB), E = succ_end(BB); SI != E; ++SI) 707f0566c1233ba4378c2c5531ddbc9eb8ad1868daChris Lattner (*SI)->removePredecessor(BB); 717f0566c1233ba4378c2c5531ddbc9eb8ad1868daChris Lattner BB->dropAllReferences(); 72fc3c82a804c9b5eda24d96c21f7e6ff66bc2c529Chris Lattner } 73fc3c82a804c9b5eda24d96c21f7e6ff66bc2c529Chris Lattner 74fc3c82a804c9b5eda24d96c21f7e6ff66bc2c529Chris Lattner if (DeadBlocks.empty()) return false; 75fc3c82a804c9b5eda24d96c21f7e6ff66bc2c529Chris Lattner 76fc3c82a804c9b5eda24d96c21f7e6ff66bc2c529Chris Lattner // Actually remove the blocks now. 77fc3c82a804c9b5eda24d96c21f7e6ff66bc2c529Chris Lattner for (unsigned i = 0, e = DeadBlocks.size(); i != e; ++i) 78fc3c82a804c9b5eda24d96c21f7e6ff66bc2c529Chris Lattner F.getBasicBlockList().erase(DeadBlocks[i]); 79fc3c82a804c9b5eda24d96c21f7e6ff66bc2c529Chris Lattner 80fc3c82a804c9b5eda24d96c21f7e6ff66bc2c529Chris Lattner return true; 81fc3c82a804c9b5eda24d96c21f7e6ff66bc2c529Chris Lattner} 82