UnreachableBlockElim.cpp revision 0e67df6283f6fd31c13d09a94a84a7afbc27ba0e
1//===-- UnreachableBlockElim.cpp - Remove unreachable blocks for codegen --===// 2// 3// The LLVM Compiler Infrastructure 4// 5// This file is distributed under the University of Illinois Open Source 6// License. See LICENSE.TXT for details. 7// 8//===----------------------------------------------------------------------===// 9// 10// This pass is an extremely simple version of the SimplifyCFG pass. Its sole 11// job is to delete LLVM basic blocks that are not reachable from the entry 12// node. To do this, it performs a simple depth first traversal of the CFG, 13// then deletes any unvisited nodes. 14// 15// Note that this pass is really a hack. In particular, the instruction 16// selectors for various targets should just not generate code for unreachable 17// blocks. Until LLVM has a more systematic way of defining instruction 18// selectors, however, we cannot really expect them to handle additional 19// complexity. 20// 21//===----------------------------------------------------------------------===// 22 23#include "llvm/CodeGen/Passes.h" 24#include "llvm/Constant.h" 25#include "llvm/Instructions.h" 26#include "llvm/Function.h" 27#include "llvm/Pass.h" 28#include "llvm/Type.h" 29#include "llvm/CodeGen/MachineFunctionPass.h" 30#include "llvm/CodeGen/MachineRegisterInfo.h" 31#include "llvm/Support/CFG.h" 32#include "llvm/Support/Compiler.h" 33#include "llvm/Target/TargetInstrInfo.h" 34#include "llvm/ADT/DepthFirstIterator.h" 35using namespace llvm; 36 37namespace { 38 class VISIBILITY_HIDDEN UnreachableBlockElim : public FunctionPass { 39 virtual bool runOnFunction(Function &F); 40 public: 41 static char ID; // Pass identification, replacement for typeid 42 UnreachableBlockElim() : FunctionPass((intptr_t)&ID) {} 43 }; 44} 45char UnreachableBlockElim::ID = 0; 46static RegisterPass<UnreachableBlockElim> 47X("unreachableblockelim", "Remove unreachable blocks from the CFG"); 48 49FunctionPass *llvm::createUnreachableBlockEliminationPass() { 50 return new UnreachableBlockElim(); 51} 52 53bool UnreachableBlockElim::runOnFunction(Function &F) { 54 std::set<BasicBlock*> Reachable; 55 56 // Mark all reachable blocks. 57 for (df_ext_iterator<Function*> I = df_ext_begin(&F, Reachable), 58 E = df_ext_end(&F, Reachable); I != E; ++I) 59 /* Mark all reachable blocks */; 60 61 // Loop over all dead blocks, remembering them and deleting all instructions 62 // in them. 63 std::vector<BasicBlock*> DeadBlocks; 64 for (Function::iterator I = F.begin(), E = F.end(); I != E; ++I) 65 if (!Reachable.count(I)) { 66 BasicBlock *BB = I; 67 DeadBlocks.push_back(BB); 68 while (PHINode *PN = dyn_cast<PHINode>(BB->begin())) { 69 PN->replaceAllUsesWith(Constant::getNullValue(PN->getType())); 70 BB->getInstList().pop_front(); 71 } 72 for (succ_iterator SI = succ_begin(BB), E = succ_end(BB); SI != E; ++SI) 73 (*SI)->removePredecessor(BB); 74 BB->dropAllReferences(); 75 } 76 77 // Actually remove the blocks now. 78 for (unsigned i = 0, e = DeadBlocks.size(); i != e; ++i) 79 DeadBlocks[i]->eraseFromParent(); 80 81 return DeadBlocks.size(); 82} 83 84 85namespace { 86 class VISIBILITY_HIDDEN UnreachableMachineBlockElim : 87 public MachineFunctionPass { 88 virtual bool runOnMachineFunction(MachineFunction &F); 89 90 public: 91 static char ID; // Pass identification, replacement for typeid 92 UnreachableMachineBlockElim() : MachineFunctionPass((intptr_t)&ID) {} 93 }; 94} 95char UnreachableMachineBlockElim::ID = 0; 96 97static RegisterPass<UnreachableMachineBlockElim> 98Y("unreachable-mbb-elimination", 99 "Remove unreachable machine basic blocks"); 100 101const PassInfo *const llvm::UnreachableMachineBlockElimID = &Y; 102 103bool UnreachableMachineBlockElim::runOnMachineFunction(MachineFunction &F) { 104 std::set<MachineBasicBlock*> Reachable; 105 106 // Mark all reachable blocks. 107 for (df_ext_iterator<MachineFunction*> I = df_ext_begin(&F, Reachable), 108 E = df_ext_end(&F, Reachable); I != E; ++I) 109 /* Mark all reachable blocks */; 110 111 // Loop over all dead blocks, remembering them and deleting all instructions 112 // in them. 113 std::vector<MachineBasicBlock*> DeadBlocks; 114 for (MachineFunction::iterator I = F.begin(), E = F.end(); I != E; ++I) 115 if (!Reachable.count(I)) { 116 MachineBasicBlock *BB = I; 117 DeadBlocks.push_back(BB); 118 119 while (BB->succ_begin() != BB->succ_end()) { 120 MachineBasicBlock* succ = *BB->succ_begin(); 121 122 MachineBasicBlock::iterator start = succ->begin(); 123 while (start != succ->end() && 124 start->getOpcode() == TargetInstrInfo::PHI) { 125 for (unsigned i = start->getNumOperands() - 1; i >= 2; i-=2) 126 if (start->getOperand(i).isMBB() && 127 start->getOperand(i).getMBB() == BB) { 128 start->RemoveOperand(i); 129 start->RemoveOperand(i-1); 130 } 131 132 if (start->getNumOperands() == 3) { 133 MachineInstr* phi = start; 134 unsigned Input = phi->getOperand(1).getReg(); 135 unsigned Output = phi->getOperand(0).getReg(); 136 137 start++; 138 phi->eraseFromParent(); 139 140 if (Input != Output) 141 F.getRegInfo().replaceRegWith(Output, Input); 142 } else 143 start++; 144 } 145 146 BB->removeSuccessor(BB->succ_begin()); 147 } 148 } 149 150 // Actually remove the blocks now. 151 for (unsigned i = 0, e = DeadBlocks.size(); i != e; ++i) 152 DeadBlocks[i]->eraseFromParent(); 153 154 F.RenumberBlocks(); 155 156 return DeadBlocks.size(); 157} 158 159