UnreachableBlockElim.cpp revision 9525528a7dc5462b6374d38c81ba5c07b11741fe
141826e77311db718135ef6517b846933dfd275f3ager@chromium.org//===-- UnreachableBlockElim.cpp - Remove unreachable blocks for codegen --===// 25a8ca6c70c6fc9716f18f6223c98d1fef5752cf6kasperl@chromium.org// 35a8ca6c70c6fc9716f18f6223c98d1fef5752cf6kasperl@chromium.org// The LLVM Compiler Infrastructure 45a8ca6c70c6fc9716f18f6223c98d1fef5752cf6kasperl@chromium.org// 55a8ca6c70c6fc9716f18f6223c98d1fef5752cf6kasperl@chromium.org// This file was developed by the LLVM research group and is distributed under 65a8ca6c70c6fc9716f18f6223c98d1fef5752cf6kasperl@chromium.org// the University of Illinois Open Source License. See LICENSE.TXT for details. 75a8ca6c70c6fc9716f18f6223c98d1fef5752cf6kasperl@chromium.org// 85a8ca6c70c6fc9716f18f6223c98d1fef5752cf6kasperl@chromium.org//===----------------------------------------------------------------------===// 95a8ca6c70c6fc9716f18f6223c98d1fef5752cf6kasperl@chromium.org// 105a8ca6c70c6fc9716f18f6223c98d1fef5752cf6kasperl@chromium.org// This pass is an extremely simple version of the SimplifyCFG pass. Its sole 115a8ca6c70c6fc9716f18f6223c98d1fef5752cf6kasperl@chromium.org// job is to delete LLVM basic blocks that are not reachable from the entry 125a8ca6c70c6fc9716f18f6223c98d1fef5752cf6kasperl@chromium.org// node. To do this, it performs a simple depth first traversal of the CFG, 135a8ca6c70c6fc9716f18f6223c98d1fef5752cf6kasperl@chromium.org// then deletes any unvisited nodes. 145a8ca6c70c6fc9716f18f6223c98d1fef5752cf6kasperl@chromium.org// 155a8ca6c70c6fc9716f18f6223c98d1fef5752cf6kasperl@chromium.org// Note that this pass is really a hack. In particular, the instruction 165a8ca6c70c6fc9716f18f6223c98d1fef5752cf6kasperl@chromium.org// selectors for various targets should just not generate code for unreachable 175a8ca6c70c6fc9716f18f6223c98d1fef5752cf6kasperl@chromium.org// blocks. Until LLVM has a more systematic way of defining instruction 185a8ca6c70c6fc9716f18f6223c98d1fef5752cf6kasperl@chromium.org// selectors, however, we cannot really expect them to handle additional 195a8ca6c70c6fc9716f18f6223c98d1fef5752cf6kasperl@chromium.org// complexity. 205a8ca6c70c6fc9716f18f6223c98d1fef5752cf6kasperl@chromium.org// 215a8ca6c70c6fc9716f18f6223c98d1fef5752cf6kasperl@chromium.org//===----------------------------------------------------------------------===// 225a8ca6c70c6fc9716f18f6223c98d1fef5752cf6kasperl@chromium.org 235a8ca6c70c6fc9716f18f6223c98d1fef5752cf6kasperl@chromium.org#include "llvm/CodeGen/Passes.h" 245a8ca6c70c6fc9716f18f6223c98d1fef5752cf6kasperl@chromium.org#include "llvm/Constant.h" 255a8ca6c70c6fc9716f18f6223c98d1fef5752cf6kasperl@chromium.org#include "llvm/Instructions.h" 265a8ca6c70c6fc9716f18f6223c98d1fef5752cf6kasperl@chromium.org#include "llvm/Function.h" 275a8ca6c70c6fc9716f18f6223c98d1fef5752cf6kasperl@chromium.org#include "llvm/Pass.h" 285a8ca6c70c6fc9716f18f6223c98d1fef5752cf6kasperl@chromium.org#include "llvm/Type.h" 29a74f0daeb278665869b4b6a3bc2739e88fed93b1ager@chromium.org#include "llvm/Support/CFG.h" 30bb29dc9819bb6f495ab6eddd2543965eb97a8e43ager@chromium.org#include "llvm/Support/Visibility.h" 31a74f0daeb278665869b4b6a3bc2739e88fed93b1ager@chromium.org#include "llvm/ADT/DepthFirstIterator.h" 32ea88ce93dcb41a9200ec8747ae7642a5db1f4ce7sgjesse@chromium.orgusing namespace llvm; 33ea88ce93dcb41a9200ec8747ae7642a5db1f4ce7sgjesse@chromium.org 345a8ca6c70c6fc9716f18f6223c98d1fef5752cf6kasperl@chromium.orgnamespace { 3537abdec9cad6edeba05b5c7a9ff73c25f5df2b70christian.plesner.hansen@gmail.com class VISIBILITY_HIDDEN UnreachableBlockElim : public FunctionPass { 365a8ca6c70c6fc9716f18f6223c98d1fef5752cf6kasperl@chromium.org virtual bool runOnFunction(Function &F); 375a8ca6c70c6fc9716f18f6223c98d1fef5752cf6kasperl@chromium.org }; 385a8ca6c70c6fc9716f18f6223c98d1fef5752cf6kasperl@chromium.org RegisterOpt<UnreachableBlockElim> 39ddb913d619a6e602f53dd17b0fe71158ce66888dager@chromium.org X("unreachableblockelim", "Remove unreachable blocks from the CFG"); 405a8ca6c70c6fc9716f18f6223c98d1fef5752cf6kasperl@chromium.org} 415a8ca6c70c6fc9716f18f6223c98d1fef5752cf6kasperl@chromium.org 425a8ca6c70c6fc9716f18f6223c98d1fef5752cf6kasperl@chromium.orgFunctionPass *llvm::createUnreachableBlockEliminationPass() { 435a8ca6c70c6fc9716f18f6223c98d1fef5752cf6kasperl@chromium.org return new UnreachableBlockElim(); 445a8ca6c70c6fc9716f18f6223c98d1fef5752cf6kasperl@chromium.org} 455a8ca6c70c6fc9716f18f6223c98d1fef5752cf6kasperl@chromium.org 465a8ca6c70c6fc9716f18f6223c98d1fef5752cf6kasperl@chromium.orgbool UnreachableBlockElim::runOnFunction(Function &F) { 475a8ca6c70c6fc9716f18f6223c98d1fef5752cf6kasperl@chromium.org std::set<BasicBlock*> Reachable; 485a8ca6c70c6fc9716f18f6223c98d1fef5752cf6kasperl@chromium.org 495a8ca6c70c6fc9716f18f6223c98d1fef5752cf6kasperl@chromium.org // Mark all reachable blocks. 505a8ca6c70c6fc9716f18f6223c98d1fef5752cf6kasperl@chromium.org for (df_ext_iterator<Function*> I = df_ext_begin(&F, Reachable), 515a8ca6c70c6fc9716f18f6223c98d1fef5752cf6kasperl@chromium.org E = df_ext_end(&F, Reachable); I != E; ++I) 525a8ca6c70c6fc9716f18f6223c98d1fef5752cf6kasperl@chromium.org /* Mark all reachable blocks */; 535a8ca6c70c6fc9716f18f6223c98d1fef5752cf6kasperl@chromium.org 545a8ca6c70c6fc9716f18f6223c98d1fef5752cf6kasperl@chromium.org // Loop over all dead blocks, remembering them and deleting all instructions 555a8ca6c70c6fc9716f18f6223c98d1fef5752cf6kasperl@chromium.org // in them. 565a8ca6c70c6fc9716f18f6223c98d1fef5752cf6kasperl@chromium.org std::vector<BasicBlock*> DeadBlocks; 575a8ca6c70c6fc9716f18f6223c98d1fef5752cf6kasperl@chromium.org for (Function::iterator I = F.begin(), E = F.end(); I != E; ++I) 585a8ca6c70c6fc9716f18f6223c98d1fef5752cf6kasperl@chromium.org if (!Reachable.count(I)) { 595a8ca6c70c6fc9716f18f6223c98d1fef5752cf6kasperl@chromium.org BasicBlock *BB = I; 605a8ca6c70c6fc9716f18f6223c98d1fef5752cf6kasperl@chromium.org DeadBlocks.push_back(BB); 615a8ca6c70c6fc9716f18f6223c98d1fef5752cf6kasperl@chromium.org while (PHINode *PN = dyn_cast<PHINode>(BB->begin())) { 625a8ca6c70c6fc9716f18f6223c98d1fef5752cf6kasperl@chromium.org PN->replaceAllUsesWith(Constant::getNullValue(PN->getType())); 635a8ca6c70c6fc9716f18f6223c98d1fef5752cf6kasperl@chromium.org BB->getInstList().pop_front(); 645a8ca6c70c6fc9716f18f6223c98d1fef5752cf6kasperl@chromium.org } 655a8ca6c70c6fc9716f18f6223c98d1fef5752cf6kasperl@chromium.org for (succ_iterator SI = succ_begin(BB), E = succ_end(BB); SI != E; ++SI) 665a8ca6c70c6fc9716f18f6223c98d1fef5752cf6kasperl@chromium.org (*SI)->removePredecessor(BB); 675a8ca6c70c6fc9716f18f6223c98d1fef5752cf6kasperl@chromium.org BB->dropAllReferences(); 685a8ca6c70c6fc9716f18f6223c98d1fef5752cf6kasperl@chromium.org } 695a8ca6c70c6fc9716f18f6223c98d1fef5752cf6kasperl@chromium.org 705a8ca6c70c6fc9716f18f6223c98d1fef5752cf6kasperl@chromium.org if (DeadBlocks.empty()) return false; 715a8ca6c70c6fc9716f18f6223c98d1fef5752cf6kasperl@chromium.org 725a8ca6c70c6fc9716f18f6223c98d1fef5752cf6kasperl@chromium.org // Actually remove the blocks now. 735a8ca6c70c6fc9716f18f6223c98d1fef5752cf6kasperl@chromium.org for (unsigned i = 0, e = DeadBlocks.size(); i != e; ++i) 745a8ca6c70c6fc9716f18f6223c98d1fef5752cf6kasperl@chromium.org F.getBasicBlockList().erase(DeadBlocks[i]); 755a8ca6c70c6fc9716f18f6223c98d1fef5752cf6kasperl@chromium.org 765a8ca6c70c6fc9716f18f6223c98d1fef5752cf6kasperl@chromium.org return true; 775a8ca6c70c6fc9716f18f6223c98d1fef5752cf6kasperl@chromium.org} 785a8ca6c70c6fc9716f18f6223c98d1fef5752cf6kasperl@chromium.org