UnreachableBlockElim.cpp revision 492d06efde44a4e38a6ed321ada4af5a75494df6
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/Analysis/ProfileInfo.h" 30#include "llvm/CodeGen/MachineDominators.h" 31#include "llvm/CodeGen/MachineFunctionPass.h" 32#include "llvm/CodeGen/MachineModuleInfo.h" 33#include "llvm/CodeGen/MachineLoopInfo.h" 34#include "llvm/CodeGen/MachineRegisterInfo.h" 35#include "llvm/Support/CFG.h" 36#include "llvm/Support/Compiler.h" 37#include "llvm/Target/TargetInstrInfo.h" 38#include "llvm/ADT/DepthFirstIterator.h" 39#include "llvm/ADT/SmallPtrSet.h" 40using namespace llvm; 41 42namespace { 43 class UnreachableBlockElim : public FunctionPass { 44 virtual bool runOnFunction(Function &F); 45 public: 46 static char ID; // Pass identification, replacement for typeid 47 UnreachableBlockElim() : FunctionPass(&ID) {} 48 49 virtual void getAnalysisUsage(AnalysisUsage &AU) const { 50 AU.addPreserved<ProfileInfo>(); 51 } 52 }; 53} 54char UnreachableBlockElim::ID = 0; 55static RegisterPass<UnreachableBlockElim> 56X("unreachableblockelim", "Remove unreachable blocks from the CFG"); 57 58FunctionPass *llvm::createUnreachableBlockEliminationPass() { 59 return new UnreachableBlockElim(); 60} 61 62bool UnreachableBlockElim::runOnFunction(Function &F) { 63 SmallPtrSet<BasicBlock*, 8> Reachable; 64 65 // Mark all reachable blocks. 66 for (df_ext_iterator<Function*, SmallPtrSet<BasicBlock*, 8> > I = 67 df_ext_begin(&F, Reachable), E = df_ext_end(&F, Reachable); I != E; ++I) 68 /* Mark all reachable blocks */; 69 70 // Loop over all dead blocks, remembering them and deleting all instructions 71 // in them. 72 std::vector<BasicBlock*> DeadBlocks; 73 for (Function::iterator I = F.begin(), E = F.end(); I != E; ++I) 74 if (!Reachable.count(I)) { 75 BasicBlock *BB = I; 76 DeadBlocks.push_back(BB); 77 while (PHINode *PN = dyn_cast<PHINode>(BB->begin())) { 78 PN->replaceAllUsesWith(Constant::getNullValue(PN->getType())); 79 BB->getInstList().pop_front(); 80 } 81 for (succ_iterator SI = succ_begin(BB), E = succ_end(BB); SI != E; ++SI) 82 (*SI)->removePredecessor(BB); 83 BB->dropAllReferences(); 84 } 85 86 // Actually remove the blocks now. 87 ProfileInfo *PI = getAnalysisIfAvailable<ProfileInfo>(); 88 for (unsigned i = 0, e = DeadBlocks.size(); i != e; ++i) { 89 if (PI) PI->removeBlock(DeadBlocks[i]); 90 DeadBlocks[i]->eraseFromParent(); 91 } 92 93 return DeadBlocks.size(); 94} 95 96 97namespace { 98 class UnreachableMachineBlockElim : public MachineFunctionPass { 99 virtual bool runOnMachineFunction(MachineFunction &F); 100 virtual void getAnalysisUsage(AnalysisUsage &AU) const; 101 MachineModuleInfo *MMI; 102 public: 103 static char ID; // Pass identification, replacement for typeid 104 UnreachableMachineBlockElim() : MachineFunctionPass(&ID) {} 105 }; 106} 107char UnreachableMachineBlockElim::ID = 0; 108 109static RegisterPass<UnreachableMachineBlockElim> 110Y("unreachable-mbb-elimination", 111 "Remove unreachable machine basic blocks"); 112 113const PassInfo *const llvm::UnreachableMachineBlockElimID = &Y; 114 115void UnreachableMachineBlockElim::getAnalysisUsage(AnalysisUsage &AU) const { 116 AU.addPreserved<MachineLoopInfo>(); 117 AU.addPreserved<MachineDominatorTree>(); 118 MachineFunctionPass::getAnalysisUsage(AU); 119} 120 121bool UnreachableMachineBlockElim::runOnMachineFunction(MachineFunction &F) { 122 SmallPtrSet<MachineBasicBlock*, 8> Reachable; 123 124 MMI = getAnalysisIfAvailable<MachineModuleInfo>(); 125 MachineDominatorTree *MDT = getAnalysisIfAvailable<MachineDominatorTree>(); 126 MachineLoopInfo *MLI = getAnalysisIfAvailable<MachineLoopInfo>(); 127 128 // Mark all reachable blocks. 129 for (df_ext_iterator<MachineFunction*, SmallPtrSet<MachineBasicBlock*, 8> > 130 I = df_ext_begin(&F, Reachable), E = df_ext_end(&F, Reachable); 131 I != E; ++I) 132 /* Mark all reachable blocks */; 133 134 // Loop over all dead blocks, remembering them and deleting all instructions 135 // in them. 136 std::vector<MachineBasicBlock*> DeadBlocks; 137 for (MachineFunction::iterator I = F.begin(), E = F.end(); I != E; ++I) { 138 MachineBasicBlock *BB = I; 139 140 // Test for deadness. 141 if (!Reachable.count(BB)) { 142 DeadBlocks.push_back(BB); 143 144 // Update dominator and loop info. 145 if (MLI) MLI->removeBlock(BB); 146 if (MDT && MDT->getNode(BB)) MDT->eraseNode(BB); 147 148 while (BB->succ_begin() != BB->succ_end()) { 149 MachineBasicBlock* succ = *BB->succ_begin(); 150 151 MachineBasicBlock::iterator start = succ->begin(); 152 while (start != succ->end() && 153 start->getOpcode() == TargetInstrInfo::PHI) { 154 for (unsigned i = start->getNumOperands() - 1; i >= 2; i-=2) 155 if (start->getOperand(i).isMBB() && 156 start->getOperand(i).getMBB() == BB) { 157 start->RemoveOperand(i); 158 start->RemoveOperand(i-1); 159 } 160 161 start++; 162 } 163 164 BB->removeSuccessor(BB->succ_begin()); 165 } 166 } 167 } 168 169 // Actually remove the blocks now. 170 for (unsigned i = 0, e = DeadBlocks.size(); i != e; ++i) { 171 MachineBasicBlock *MBB = DeadBlocks[i]; 172 // If there are any labels in the basic block, unregister them from 173 // MachineModuleInfo. 174 if (MMI && !MBB->empty()) { 175 for (MachineBasicBlock::iterator I = MBB->begin(), 176 E = MBB->end(); I != E; ++I) { 177 if (I->isLabel()) 178 // The label ID # is always operand #0, an immediate. 179 MMI->InvalidateLabel(I->getOperand(0).getImm()); 180 } 181 } 182 MBB->eraseFromParent(); 183 } 184 185 // Cleanup PHI nodes. 186 for (MachineFunction::iterator I = F.begin(), E = F.end(); I != E; ++I) { 187 MachineBasicBlock *BB = I; 188 // Prune unneeded PHI entries. 189 SmallPtrSet<MachineBasicBlock*, 8> preds(BB->pred_begin(), 190 BB->pred_end()); 191 MachineBasicBlock::iterator phi = BB->begin(); 192 while (phi != BB->end() && 193 phi->getOpcode() == TargetInstrInfo::PHI) { 194 for (unsigned i = phi->getNumOperands() - 1; i >= 2; i-=2) 195 if (!preds.count(phi->getOperand(i).getMBB())) { 196 phi->RemoveOperand(i); 197 phi->RemoveOperand(i-1); 198 } 199 200 if (phi->getNumOperands() == 3) { 201 unsigned Input = phi->getOperand(1).getReg(); 202 unsigned Output = phi->getOperand(0).getReg(); 203 204 MachineInstr* temp = phi; 205 ++phi; 206 temp->eraseFromParent(); 207 208 if (Input != Output) 209 F.getRegInfo().replaceRegWith(Output, Input); 210 211 continue; 212 } 213 214 ++phi; 215 } 216 } 217 218 F.RenumberBlocks(); 219 220 return DeadBlocks.size(); 221} 222