LLVM API Documentation
00001 //===-- UnreachableBlockElim.cpp - Remove unreachable blocks for codegen --===// 00002 // 00003 // The LLVM Compiler Infrastructure 00004 // 00005 // This file is distributed under the University of Illinois Open Source 00006 // License. See LICENSE.TXT for details. 00007 // 00008 //===----------------------------------------------------------------------===// 00009 // 00010 // This pass is an extremely simple version of the SimplifyCFG pass. Its sole 00011 // job is to delete LLVM basic blocks that are not reachable from the entry 00012 // node. To do this, it performs a simple depth first traversal of the CFG, 00013 // then deletes any unvisited nodes. 00014 // 00015 // Note that this pass is really a hack. In particular, the instruction 00016 // selectors for various targets should just not generate code for unreachable 00017 // blocks. Until LLVM has a more systematic way of defining instruction 00018 // selectors, however, we cannot really expect them to handle additional 00019 // complexity. 00020 // 00021 //===----------------------------------------------------------------------===// 00022 00023 #include "llvm/CodeGen/Passes.h" 00024 #include "llvm/Constant.h" 00025 #include "llvm/Instructions.h" 00026 #include "llvm/Function.h" 00027 #include "llvm/Pass.h" 00028 #include "llvm/Type.h" 00029 #include "llvm/CodeGen/MachineDominators.h" 00030 #include "llvm/CodeGen/MachineFunctionPass.h" 00031 #include "llvm/CodeGen/MachineModuleInfo.h" 00032 #include "llvm/CodeGen/MachineLoopInfo.h" 00033 #include "llvm/CodeGen/MachineRegisterInfo.h" 00034 #include "llvm/Support/CFG.h" 00035 #include "llvm/Support/Compiler.h" 00036 #include "llvm/Target/TargetInstrInfo.h" 00037 #include "llvm/ADT/DepthFirstIterator.h" 00038 #include "llvm/ADT/SmallPtrSet.h" 00039 using namespace llvm; 00040 00041 namespace { 00042 class VISIBILITY_HIDDEN UnreachableBlockElim : public FunctionPass { 00043 virtual bool runOnFunction(Function &F); 00044 public: 00045 static char ID; // Pass identification, replacement for typeid 00046 UnreachableBlockElim() : FunctionPass(&ID) {} 00047 }; 00048 } 00049 char UnreachableBlockElim::ID = 0; 00050 static RegisterPass<UnreachableBlockElim> 00051 X("unreachableblockelim", "Remove unreachable blocks from the CFG"); 00052 00053 FunctionPass *llvm::createUnreachableBlockEliminationPass() { 00054 return new UnreachableBlockElim(); 00055 } 00056 00057 bool UnreachableBlockElim::runOnFunction(Function &F) { 00058 SmallPtrSet<BasicBlock*, 8> Reachable; 00059 00060 // Mark all reachable blocks. 00061 for (df_ext_iterator<Function*, SmallPtrSet<BasicBlock*, 8> > I = 00062 df_ext_begin(&F, Reachable), E = df_ext_end(&F, Reachable); I != E; ++I) 00063 /* Mark all reachable blocks */; 00064 00065 // Loop over all dead blocks, remembering them and deleting all instructions 00066 // in them. 00067 std::vector<BasicBlock*> DeadBlocks; 00068 for (Function::iterator I = F.begin(), E = F.end(); I != E; ++I) 00069 if (!Reachable.count(I)) { 00070 BasicBlock *BB = I; 00071 DeadBlocks.push_back(BB); 00072 while (PHINode *PN = dyn_cast<PHINode>(BB->begin())) { 00073 PN->replaceAllUsesWith(Constant::getNullValue(PN->getType())); 00074 BB->getInstList().pop_front(); 00075 } 00076 for (succ_iterator SI = succ_begin(BB), E = succ_end(BB); SI != E; ++SI) 00077 (*SI)->removePredecessor(BB); 00078 BB->dropAllReferences(); 00079 } 00080 00081 // Actually remove the blocks now. 00082 for (unsigned i = 0, e = DeadBlocks.size(); i != e; ++i) 00083 DeadBlocks[i]->eraseFromParent(); 00084 00085 return DeadBlocks.size(); 00086 } 00087 00088 00089 namespace { 00090 class VISIBILITY_HIDDEN UnreachableMachineBlockElim : 00091 public MachineFunctionPass { 00092 virtual bool runOnMachineFunction(MachineFunction &F); 00093 virtual void getAnalysisUsage(AnalysisUsage &AU) const; 00094 MachineModuleInfo *MMI; 00095 public: 00096 static char ID; // Pass identification, replacement for typeid 00097 UnreachableMachineBlockElim() : MachineFunctionPass(&ID) {} 00098 }; 00099 } 00100 char UnreachableMachineBlockElim::ID = 0; 00101 00102 static RegisterPass<UnreachableMachineBlockElim> 00103 Y("unreachable-mbb-elimination", 00104 "Remove unreachable machine basic blocks"); 00105 00106 const PassInfo *const llvm::UnreachableMachineBlockElimID = &Y; 00107 00108 void UnreachableMachineBlockElim::getAnalysisUsage(AnalysisUsage &AU) const { 00109 AU.addPreserved<MachineLoopInfo>(); 00110 AU.addPreserved<MachineDominatorTree>(); 00111 MachineFunctionPass::getAnalysisUsage(AU); 00112 } 00113 00114 bool UnreachableMachineBlockElim::runOnMachineFunction(MachineFunction &F) { 00115 SmallPtrSet<MachineBasicBlock*, 8> Reachable; 00116 00117 MMI = getAnalysisIfAvailable<MachineModuleInfo>(); 00118 MachineDominatorTree *MDT = getAnalysisIfAvailable<MachineDominatorTree>(); 00119 MachineLoopInfo *MLI = getAnalysisIfAvailable<MachineLoopInfo>(); 00120 00121 // Mark all reachable blocks. 00122 for (df_ext_iterator<MachineFunction*, SmallPtrSet<MachineBasicBlock*, 8> > 00123 I = df_ext_begin(&F, Reachable), E = df_ext_end(&F, Reachable); 00124 I != E; ++I) 00125 /* Mark all reachable blocks */; 00126 00127 // Loop over all dead blocks, remembering them and deleting all instructions 00128 // in them. 00129 std::vector<MachineBasicBlock*> DeadBlocks; 00130 for (MachineFunction::iterator I = F.begin(), E = F.end(); I != E; ++I) { 00131 MachineBasicBlock *BB = I; 00132 00133 // Test for deadness. 00134 if (!Reachable.count(BB)) { 00135 DeadBlocks.push_back(BB); 00136 00137 // Update dominator and loop info. 00138 if (MLI) MLI->removeBlock(BB); 00139 if (MDT && MDT->getNode(BB)) MDT->eraseNode(BB); 00140 00141 while (BB->succ_begin() != BB->succ_end()) { 00142 MachineBasicBlock* succ = *BB->succ_begin(); 00143 00144 MachineBasicBlock::iterator start = succ->begin(); 00145 while (start != succ->end() && 00146 start->getOpcode() == TargetInstrInfo::PHI) { 00147 for (unsigned i = start->getNumOperands() - 1; i >= 2; i-=2) 00148 if (start->getOperand(i).isMBB() && 00149 start->getOperand(i).getMBB() == BB) { 00150 start->RemoveOperand(i); 00151 start->RemoveOperand(i-1); 00152 } 00153 00154 start++; 00155 } 00156 00157 BB->removeSuccessor(BB->succ_begin()); 00158 } 00159 } 00160 } 00161 00162 // Actually remove the blocks now. 00163 for (unsigned i = 0, e = DeadBlocks.size(); i != e; ++i) { 00164 MachineBasicBlock *MBB = DeadBlocks[i]; 00165 // If there are any labels in the basic block, unregister them from 00166 // MachineModuleInfo. 00167 if (MMI && !MBB->empty()) { 00168 for (MachineBasicBlock::iterator I = MBB->begin(), 00169 E = MBB->end(); I != E; ++I) { 00170 if (I->isLabel()) 00171 // The label ID # is always operand #0, an immediate. 00172 MMI->InvalidateLabel(I->getOperand(0).getImm()); 00173 } 00174 } 00175 MBB->eraseFromParent(); 00176 } 00177 00178 // Cleanup PHI nodes. 00179 for (MachineFunction::iterator I = F.begin(), E = F.end(); I != E; ++I) { 00180 MachineBasicBlock *BB = I; 00181 // Prune unneeded PHI entries. 00182 SmallPtrSet<MachineBasicBlock*, 8> preds(BB->pred_begin(), 00183 BB->pred_end()); 00184 MachineBasicBlock::iterator phi = BB->begin(); 00185 while (phi != BB->end() && 00186 phi->getOpcode() == TargetInstrInfo::PHI) { 00187 for (unsigned i = phi->getNumOperands() - 1; i >= 2; i-=2) 00188 if (!preds.count(phi->getOperand(i).getMBB())) { 00189 phi->RemoveOperand(i); 00190 phi->RemoveOperand(i-1); 00191 } 00192 00193 if (phi->getNumOperands() == 3) { 00194 unsigned Input = phi->getOperand(1).getReg(); 00195 unsigned Output = phi->getOperand(0).getReg(); 00196 00197 MachineInstr* temp = phi; 00198 ++phi; 00199 temp->eraseFromParent(); 00200 00201 if (Input != Output) 00202 F.getRegInfo().replaceRegWith(Output, Input); 00203 00204 continue; 00205 } 00206 00207 ++phi; 00208 } 00209 } 00210 00211 F.RenumberBlocks(); 00212 00213 return DeadBlocks.size(); 00214 }