UnreachableBlockElim.cpp revision bd3ba461eb5578a81ba09ff7bd7eb271d1130196
1fc3c82a804c9b5eda24d96c21f7e6ff66bc2c529Chris Lattner//===-- UnreachableBlockElim.cpp - Remove unreachable blocks for codegen --===// 2edf128a7fa90f2b0b7ee24741a04a7ae1ecd6f7eMisha Brukman// 3fc3c82a804c9b5eda24d96c21f7e6ff66bc2c529Chris Lattner// The LLVM Compiler Infrastructure 4fc3c82a804c9b5eda24d96c21f7e6ff66bc2c529Chris Lattner// 54ee451de366474b9c228b4e5fa573795a715216dChris Lattner// This file is distributed under the University of Illinois Open Source 64ee451de366474b9c228b4e5fa573795a715216dChris Lattner// 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" 29bd3ba461eb5578a81ba09ff7bd7eb271d1130196Owen Anderson#include "llvm/CodeGen/MachineFunctionPass.h" 30fc3c82a804c9b5eda24d96c21f7e6ff66bc2c529Chris Lattner#include "llvm/Support/CFG.h" 31a4f0b3a084d120cfc5b5bb06f64b222f5cb72740Chris Lattner#include "llvm/Support/Compiler.h" 32bd3ba461eb5578a81ba09ff7bd7eb271d1130196Owen Anderson#include "llvm/Target/TargetInstrInfo.h" 33551ccae044b0ff658fe629dd67edd5ffe75d10e8Reid Spencer#include "llvm/ADT/DepthFirstIterator.h" 34fc3c82a804c9b5eda24d96c21f7e6ff66bc2c529Chris Lattnerusing namespace llvm; 35fc3c82a804c9b5eda24d96c21f7e6ff66bc2c529Chris Lattner 36fc3c82a804c9b5eda24d96c21f7e6ff66bc2c529Chris Lattnernamespace { 379525528a7dc5462b6374d38c81ba5c07b11741feChris Lattner class VISIBILITY_HIDDEN UnreachableBlockElim : public FunctionPass { 38fc3c82a804c9b5eda24d96c21f7e6ff66bc2c529Chris Lattner virtual bool runOnFunction(Function &F); 39794fd75c67a2cdc128d67342c6d88a504d186896Devang Patel public: 40ecd94c804a563f2a86572dcf1d2e81f397e19daaNick Lewycky static char ID; // Pass identification, replacement for typeid 41794fd75c67a2cdc128d67342c6d88a504d186896Devang Patel UnreachableBlockElim() : FunctionPass((intptr_t)&ID) {} 42fc3c82a804c9b5eda24d96c21f7e6ff66bc2c529Chris Lattner }; 43fc3c82a804c9b5eda24d96c21f7e6ff66bc2c529Chris Lattner} 44844731a7f1909f55935e3514c9e713a62d67662eDan Gohmanchar UnreachableBlockElim::ID = 0; 45844731a7f1909f55935e3514c9e713a62d67662eDan Gohmanstatic RegisterPass<UnreachableBlockElim> 46844731a7f1909f55935e3514c9e713a62d67662eDan GohmanX("unreachableblockelim", "Remove unreachable blocks from the CFG"); 47fc3c82a804c9b5eda24d96c21f7e6ff66bc2c529Chris Lattner 48fc3c82a804c9b5eda24d96c21f7e6ff66bc2c529Chris LattnerFunctionPass *llvm::createUnreachableBlockEliminationPass() { 49fc3c82a804c9b5eda24d96c21f7e6ff66bc2c529Chris Lattner return new UnreachableBlockElim(); 50fc3c82a804c9b5eda24d96c21f7e6ff66bc2c529Chris Lattner} 51fc3c82a804c9b5eda24d96c21f7e6ff66bc2c529Chris Lattner 52fc3c82a804c9b5eda24d96c21f7e6ff66bc2c529Chris Lattnerbool UnreachableBlockElim::runOnFunction(Function &F) { 53fc3c82a804c9b5eda24d96c21f7e6ff66bc2c529Chris Lattner std::set<BasicBlock*> Reachable; 54fc3c82a804c9b5eda24d96c21f7e6ff66bc2c529Chris Lattner 55fc3c82a804c9b5eda24d96c21f7e6ff66bc2c529Chris Lattner // Mark all reachable blocks. 56fc3c82a804c9b5eda24d96c21f7e6ff66bc2c529Chris Lattner for (df_ext_iterator<Function*> I = df_ext_begin(&F, Reachable), 57fc3c82a804c9b5eda24d96c21f7e6ff66bc2c529Chris Lattner E = df_ext_end(&F, Reachable); I != E; ++I) 58fc3c82a804c9b5eda24d96c21f7e6ff66bc2c529Chris Lattner /* Mark all reachable blocks */; 59fc3c82a804c9b5eda24d96c21f7e6ff66bc2c529Chris Lattner 60fc3c82a804c9b5eda24d96c21f7e6ff66bc2c529Chris Lattner // Loop over all dead blocks, remembering them and deleting all instructions 61fc3c82a804c9b5eda24d96c21f7e6ff66bc2c529Chris Lattner // in them. 62fc3c82a804c9b5eda24d96c21f7e6ff66bc2c529Chris Lattner std::vector<BasicBlock*> DeadBlocks; 63fc3c82a804c9b5eda24d96c21f7e6ff66bc2c529Chris Lattner for (Function::iterator I = F.begin(), E = F.end(); I != E; ++I) 64fc3c82a804c9b5eda24d96c21f7e6ff66bc2c529Chris Lattner if (!Reachable.count(I)) { 657f0566c1233ba4378c2c5531ddbc9eb8ad1868daChris Lattner BasicBlock *BB = I; 667f0566c1233ba4378c2c5531ddbc9eb8ad1868daChris Lattner DeadBlocks.push_back(BB); 677f0566c1233ba4378c2c5531ddbc9eb8ad1868daChris Lattner while (PHINode *PN = dyn_cast<PHINode>(BB->begin())) { 687f0566c1233ba4378c2c5531ddbc9eb8ad1868daChris Lattner PN->replaceAllUsesWith(Constant::getNullValue(PN->getType())); 697f0566c1233ba4378c2c5531ddbc9eb8ad1868daChris Lattner BB->getInstList().pop_front(); 707f0566c1233ba4378c2c5531ddbc9eb8ad1868daChris Lattner } 717f0566c1233ba4378c2c5531ddbc9eb8ad1868daChris Lattner for (succ_iterator SI = succ_begin(BB), E = succ_end(BB); SI != E; ++SI) 727f0566c1233ba4378c2c5531ddbc9eb8ad1868daChris Lattner (*SI)->removePredecessor(BB); 737f0566c1233ba4378c2c5531ddbc9eb8ad1868daChris Lattner BB->dropAllReferences(); 74fc3c82a804c9b5eda24d96c21f7e6ff66bc2c529Chris Lattner } 75fc3c82a804c9b5eda24d96c21f7e6ff66bc2c529Chris Lattner 76bd3ba461eb5578a81ba09ff7bd7eb271d1130196Owen Anderson // Actually remove the blocks now. 77bd3ba461eb5578a81ba09ff7bd7eb271d1130196Owen Anderson for (unsigned i = 0, e = DeadBlocks.size(); i != e; ++i) 78bd3ba461eb5578a81ba09ff7bd7eb271d1130196Owen Anderson DeadBlocks[i]->eraseFromParent(); 79bd3ba461eb5578a81ba09ff7bd7eb271d1130196Owen Anderson 80bd3ba461eb5578a81ba09ff7bd7eb271d1130196Owen Anderson return DeadBlocks.size(); 81bd3ba461eb5578a81ba09ff7bd7eb271d1130196Owen Anderson} 82bd3ba461eb5578a81ba09ff7bd7eb271d1130196Owen Anderson 83bd3ba461eb5578a81ba09ff7bd7eb271d1130196Owen Anderson 84bd3ba461eb5578a81ba09ff7bd7eb271d1130196Owen Andersonnamespace { 85bd3ba461eb5578a81ba09ff7bd7eb271d1130196Owen Anderson class VISIBILITY_HIDDEN UnreachableMachineBlockElim : 86bd3ba461eb5578a81ba09ff7bd7eb271d1130196Owen Anderson public MachineFunctionPass { 87bd3ba461eb5578a81ba09ff7bd7eb271d1130196Owen Anderson virtual bool runOnMachineFunction(MachineFunction &F); 88bd3ba461eb5578a81ba09ff7bd7eb271d1130196Owen Anderson bool iterateOnFunction(MachineFunction& F); 89bd3ba461eb5578a81ba09ff7bd7eb271d1130196Owen Anderson 90bd3ba461eb5578a81ba09ff7bd7eb271d1130196Owen Anderson public: 91bd3ba461eb5578a81ba09ff7bd7eb271d1130196Owen Anderson static char ID; // Pass identification, replacement for typeid 92bd3ba461eb5578a81ba09ff7bd7eb271d1130196Owen Anderson UnreachableMachineBlockElim() : MachineFunctionPass((intptr_t)&ID) {} 93bd3ba461eb5578a81ba09ff7bd7eb271d1130196Owen Anderson }; 94bd3ba461eb5578a81ba09ff7bd7eb271d1130196Owen Anderson} 95bd3ba461eb5578a81ba09ff7bd7eb271d1130196Owen Andersonchar UnreachableMachineBlockElim::ID = 0; 96bd3ba461eb5578a81ba09ff7bd7eb271d1130196Owen Anderson 97bd3ba461eb5578a81ba09ff7bd7eb271d1130196Owen Andersonstatic RegisterPass<UnreachableMachineBlockElim> 98bd3ba461eb5578a81ba09ff7bd7eb271d1130196Owen AndersonY("unreachable-mbb-elimination", 99bd3ba461eb5578a81ba09ff7bd7eb271d1130196Owen Anderson "Remove unreachable machine basic blocks"); 100bd3ba461eb5578a81ba09ff7bd7eb271d1130196Owen Anderson 101bd3ba461eb5578a81ba09ff7bd7eb271d1130196Owen Andersonconst PassInfo *const llvm::UnreachableMachineBlockElimID = &Y; 102bd3ba461eb5578a81ba09ff7bd7eb271d1130196Owen Anderson 103bd3ba461eb5578a81ba09ff7bd7eb271d1130196Owen Andersonbool UnreachableMachineBlockElim::runOnMachineFunction(MachineFunction &F) { 104bd3ba461eb5578a81ba09ff7bd7eb271d1130196Owen Anderson bool changed = true; 105bd3ba461eb5578a81ba09ff7bd7eb271d1130196Owen Anderson bool result = false; 106bd3ba461eb5578a81ba09ff7bd7eb271d1130196Owen Anderson 107bd3ba461eb5578a81ba09ff7bd7eb271d1130196Owen Anderson while (changed) { 108bd3ba461eb5578a81ba09ff7bd7eb271d1130196Owen Anderson changed = iterateOnFunction(F); 109bd3ba461eb5578a81ba09ff7bd7eb271d1130196Owen Anderson result |= changed; 110bd3ba461eb5578a81ba09ff7bd7eb271d1130196Owen Anderson } 111bd3ba461eb5578a81ba09ff7bd7eb271d1130196Owen Anderson 112bd3ba461eb5578a81ba09ff7bd7eb271d1130196Owen Anderson if (result) 113bd3ba461eb5578a81ba09ff7bd7eb271d1130196Owen Anderson F.RenumberBlocks(); 114bd3ba461eb5578a81ba09ff7bd7eb271d1130196Owen Anderson 115bd3ba461eb5578a81ba09ff7bd7eb271d1130196Owen Anderson return result; 116bd3ba461eb5578a81ba09ff7bd7eb271d1130196Owen Anderson} 117bd3ba461eb5578a81ba09ff7bd7eb271d1130196Owen Anderson 118bd3ba461eb5578a81ba09ff7bd7eb271d1130196Owen Andersonbool UnreachableMachineBlockElim::iterateOnFunction(MachineFunction &F) { 119bd3ba461eb5578a81ba09ff7bd7eb271d1130196Owen Anderson std::set<MachineBasicBlock*> Reachable; 120bd3ba461eb5578a81ba09ff7bd7eb271d1130196Owen Anderson 121bd3ba461eb5578a81ba09ff7bd7eb271d1130196Owen Anderson // Mark all reachable blocks. 122bd3ba461eb5578a81ba09ff7bd7eb271d1130196Owen Anderson for (df_ext_iterator<MachineFunction*> I = df_ext_begin(&F, Reachable), 123bd3ba461eb5578a81ba09ff7bd7eb271d1130196Owen Anderson E = df_ext_end(&F, Reachable); I != E; ++I) 124bd3ba461eb5578a81ba09ff7bd7eb271d1130196Owen Anderson /* Mark all reachable blocks */; 125bd3ba461eb5578a81ba09ff7bd7eb271d1130196Owen Anderson 126bd3ba461eb5578a81ba09ff7bd7eb271d1130196Owen Anderson // Loop over all dead blocks, remembering them and deleting all instructions 127bd3ba461eb5578a81ba09ff7bd7eb271d1130196Owen Anderson // in them. 128bd3ba461eb5578a81ba09ff7bd7eb271d1130196Owen Anderson std::vector<MachineBasicBlock*> DeadBlocks; 129bd3ba461eb5578a81ba09ff7bd7eb271d1130196Owen Anderson for (MachineFunction::iterator I = F.begin(), E = F.end(); I != E; ++I) 130bd3ba461eb5578a81ba09ff7bd7eb271d1130196Owen Anderson if (!Reachable.count(I)) { 131bd3ba461eb5578a81ba09ff7bd7eb271d1130196Owen Anderson MachineBasicBlock *BB = I; 132bd3ba461eb5578a81ba09ff7bd7eb271d1130196Owen Anderson DeadBlocks.push_back(BB); 133bd3ba461eb5578a81ba09ff7bd7eb271d1130196Owen Anderson 134bd3ba461eb5578a81ba09ff7bd7eb271d1130196Owen Anderson while (BB->succ_begin() != BB->succ_end()) { 135bd3ba461eb5578a81ba09ff7bd7eb271d1130196Owen Anderson MachineBasicBlock* succ = *BB->succ_begin(); 136bd3ba461eb5578a81ba09ff7bd7eb271d1130196Owen Anderson 137bd3ba461eb5578a81ba09ff7bd7eb271d1130196Owen Anderson MachineBasicBlock::iterator start = succ->begin(); 138bd3ba461eb5578a81ba09ff7bd7eb271d1130196Owen Anderson while (start != succ->end() && 139bd3ba461eb5578a81ba09ff7bd7eb271d1130196Owen Anderson start->getOpcode() == TargetInstrInfo::PHI) { 140bd3ba461eb5578a81ba09ff7bd7eb271d1130196Owen Anderson for (unsigned i = start->getNumOperands() - 1; i >= 2; i-=2) 141bd3ba461eb5578a81ba09ff7bd7eb271d1130196Owen Anderson if (start->getOperand(i).isMBB() && 142bd3ba461eb5578a81ba09ff7bd7eb271d1130196Owen Anderson start->getOperand(i).getMBB() == BB) { 143bd3ba461eb5578a81ba09ff7bd7eb271d1130196Owen Anderson start->RemoveOperand(i); 144bd3ba461eb5578a81ba09ff7bd7eb271d1130196Owen Anderson start->RemoveOperand(i-1); 145bd3ba461eb5578a81ba09ff7bd7eb271d1130196Owen Anderson } 146bd3ba461eb5578a81ba09ff7bd7eb271d1130196Owen Anderson 147bd3ba461eb5578a81ba09ff7bd7eb271d1130196Owen Anderson if (start->getNumOperands() == 1) { 148bd3ba461eb5578a81ba09ff7bd7eb271d1130196Owen Anderson MachineInstr* phi = start; 149bd3ba461eb5578a81ba09ff7bd7eb271d1130196Owen Anderson start++; 150bd3ba461eb5578a81ba09ff7bd7eb271d1130196Owen Anderson phi->eraseFromParent(); 151bd3ba461eb5578a81ba09ff7bd7eb271d1130196Owen Anderson } else 152bd3ba461eb5578a81ba09ff7bd7eb271d1130196Owen Anderson start++; 153bd3ba461eb5578a81ba09ff7bd7eb271d1130196Owen Anderson } 154bd3ba461eb5578a81ba09ff7bd7eb271d1130196Owen Anderson 155bd3ba461eb5578a81ba09ff7bd7eb271d1130196Owen Anderson BB->removeSuccessor(BB->succ_begin()); 156bd3ba461eb5578a81ba09ff7bd7eb271d1130196Owen Anderson } 157bd3ba461eb5578a81ba09ff7bd7eb271d1130196Owen Anderson } 158fc3c82a804c9b5eda24d96c21f7e6ff66bc2c529Chris Lattner 159fc3c82a804c9b5eda24d96c21f7e6ff66bc2c529Chris Lattner // Actually remove the blocks now. 160fc3c82a804c9b5eda24d96c21f7e6ff66bc2c529Chris Lattner for (unsigned i = 0, e = DeadBlocks.size(); i != e; ++i) 161bd3ba461eb5578a81ba09ff7bd7eb271d1130196Owen Anderson DeadBlocks[i]->eraseFromParent(); 162fc3c82a804c9b5eda24d96c21f7e6ff66bc2c529Chris Lattner 163bd3ba461eb5578a81ba09ff7bd7eb271d1130196Owen Anderson return DeadBlocks.size(); 164fc3c82a804c9b5eda24d96c21f7e6ff66bc2c529Chris Lattner} 165bd3ba461eb5578a81ba09ff7bd7eb271d1130196Owen Anderson 166