UnreachableBlockElim.cpp revision b12ab97bbdb86e978bbaba62f3dbb402b53010da
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 MachineBasicBlock *BB = I; 116 117 // Test for deadness. 118 if (!Reachable.count(BB)) { 119 DeadBlocks.push_back(BB); 120 121 while (BB->succ_begin() != BB->succ_end()) { 122 MachineBasicBlock* succ = *BB->succ_begin(); 123 124 MachineBasicBlock::iterator start = succ->begin(); 125 while (start != succ->end() && 126 start->getOpcode() == TargetInstrInfo::PHI) { 127 for (unsigned i = start->getNumOperands() - 1; i >= 2; i-=2) 128 if (start->getOperand(i).isMBB() && 129 start->getOperand(i).getMBB() == BB) { 130 start->RemoveOperand(i); 131 start->RemoveOperand(i-1); 132 } 133 134 start++; 135 } 136 137 BB->removeSuccessor(BB->succ_begin()); 138 } 139 } 140 } 141 142 // Actually remove the blocks now. 143 for (unsigned i = 0, e = DeadBlocks.size(); i != e; ++i) 144 DeadBlocks[i]->eraseFromParent(); 145 146 // Cleanup PHI nodes. 147 for (MachineFunction::iterator I = F.begin(), E = F.end(); I != E; ++I) { 148 MachineBasicBlock *BB = I; 149 // Prune unneeded PHI entries. 150 SmallPtrSet<MachineBasicBlock*, 8> preds(BB->pred_begin(), 151 BB->pred_end()); 152 MachineBasicBlock::iterator phi = BB->begin(); 153 while (phi != BB->end() && 154 phi->getOpcode() == TargetInstrInfo::PHI) { 155 for (unsigned i = phi->getNumOperands() - 1; i >= 2; i-=2) 156 if (!preds.count(phi->getOperand(i).getMBB())) { 157 phi->RemoveOperand(i); 158 phi->RemoveOperand(i-1); 159 } 160 161 if (phi->getNumOperands() == 3) { 162 unsigned Input = phi->getOperand(1).getReg(); 163 unsigned Output = phi->getOperand(0).getReg(); 164 165 MachineInstr* temp = phi; 166 ++phi; 167 temp->eraseFromParent(); 168 169 if (Input != Output) 170 F.getRegInfo().replaceRegWith(Output, Input); 171 172 continue; 173 } 174 175 ++phi; 176 } 177 } 178 179 F.RenumberBlocks(); 180 181 return DeadBlocks.size(); 182} 183 184