1193323Sed//===-- UnreachableBlockElim.cpp - Remove unreachable blocks for codegen --===// 2193323Sed// 3193323Sed// The LLVM Compiler Infrastructure 4193323Sed// 5193323Sed// This file is distributed under the University of Illinois Open Source 6193323Sed// License. See LICENSE.TXT for details. 7193323Sed// 8193323Sed//===----------------------------------------------------------------------===// 9193323Sed// 10193323Sed// This pass is an extremely simple version of the SimplifyCFG pass. Its sole 11193323Sed// job is to delete LLVM basic blocks that are not reachable from the entry 12193323Sed// node. To do this, it performs a simple depth first traversal of the CFG, 13193323Sed// then deletes any unvisited nodes. 14193323Sed// 15193323Sed// Note that this pass is really a hack. In particular, the instruction 16193323Sed// selectors for various targets should just not generate code for unreachable 17193323Sed// blocks. Until LLVM has a more systematic way of defining instruction 18193323Sed// selectors, however, we cannot really expect them to handle additional 19193323Sed// complexity. 20193323Sed// 21193323Sed//===----------------------------------------------------------------------===// 22193323Sed 23193323Sed#include "llvm/CodeGen/Passes.h" 24249423Sdim#include "llvm/ADT/DepthFirstIterator.h" 25249423Sdim#include "llvm/ADT/SmallPtrSet.h" 26218893Sdim#include "llvm/Analysis/Dominators.h" 27198090Srdivacky#include "llvm/CodeGen/MachineDominators.h" 28193323Sed#include "llvm/CodeGen/MachineFunctionPass.h" 29249423Sdim#include "llvm/CodeGen/MachineLoopInfo.h" 30193323Sed#include "llvm/CodeGen/MachineModuleInfo.h" 31193323Sed#include "llvm/CodeGen/MachineRegisterInfo.h" 32249423Sdim#include "llvm/IR/Constant.h" 33249423Sdim#include "llvm/IR/Function.h" 34249423Sdim#include "llvm/IR/Instructions.h" 35249423Sdim#include "llvm/IR/Type.h" 36249423Sdim#include "llvm/Pass.h" 37193323Sed#include "llvm/Support/CFG.h" 38193323Sed#include "llvm/Target/TargetInstrInfo.h" 39193323Sedusing namespace llvm; 40193323Sed 41193323Sednamespace { 42198892Srdivacky class UnreachableBlockElim : public FunctionPass { 43193323Sed virtual bool runOnFunction(Function &F); 44193323Sed public: 45193323Sed static char ID; // Pass identification, replacement for typeid 46218893Sdim UnreachableBlockElim() : FunctionPass(ID) { 47218893Sdim initializeUnreachableBlockElimPass(*PassRegistry::getPassRegistry()); 48218893Sdim } 49198090Srdivacky 50198090Srdivacky virtual void getAnalysisUsage(AnalysisUsage &AU) const { 51218893Sdim AU.addPreserved<DominatorTree>(); 52198090Srdivacky } 53193323Sed }; 54193323Sed} 55193323Sedchar UnreachableBlockElim::ID = 0; 56212904SdimINITIALIZE_PASS(UnreachableBlockElim, "unreachableblockelim", 57218893Sdim "Remove unreachable blocks from the CFG", false, false) 58193323Sed 59193323SedFunctionPass *llvm::createUnreachableBlockEliminationPass() { 60193323Sed return new UnreachableBlockElim(); 61193323Sed} 62193323Sed 63193323Sedbool UnreachableBlockElim::runOnFunction(Function &F) { 64193323Sed SmallPtrSet<BasicBlock*, 8> Reachable; 65193323Sed 66193323Sed // Mark all reachable blocks. 67193323Sed for (df_ext_iterator<Function*, SmallPtrSet<BasicBlock*, 8> > I = 68193323Sed df_ext_begin(&F, Reachable), E = df_ext_end(&F, Reachable); I != E; ++I) 69193323Sed /* Mark all reachable blocks */; 70193323Sed 71193323Sed // Loop over all dead blocks, remembering them and deleting all instructions 72193323Sed // in them. 73193323Sed std::vector<BasicBlock*> DeadBlocks; 74193323Sed for (Function::iterator I = F.begin(), E = F.end(); I != E; ++I) 75193323Sed if (!Reachable.count(I)) { 76193323Sed BasicBlock *BB = I; 77193323Sed DeadBlocks.push_back(BB); 78193323Sed while (PHINode *PN = dyn_cast<PHINode>(BB->begin())) { 79193323Sed PN->replaceAllUsesWith(Constant::getNullValue(PN->getType())); 80193323Sed BB->getInstList().pop_front(); 81193323Sed } 82193323Sed for (succ_iterator SI = succ_begin(BB), E = succ_end(BB); SI != E; ++SI) 83193323Sed (*SI)->removePredecessor(BB); 84193323Sed BB->dropAllReferences(); 85193323Sed } 86193323Sed 87193323Sed // Actually remove the blocks now. 88198090Srdivacky for (unsigned i = 0, e = DeadBlocks.size(); i != e; ++i) { 89193323Sed DeadBlocks[i]->eraseFromParent(); 90198090Srdivacky } 91193323Sed 92193323Sed return DeadBlocks.size(); 93193323Sed} 94193323Sed 95193323Sed 96193323Sednamespace { 97198892Srdivacky class UnreachableMachineBlockElim : public MachineFunctionPass { 98193323Sed virtual bool runOnMachineFunction(MachineFunction &F); 99198090Srdivacky virtual void getAnalysisUsage(AnalysisUsage &AU) const; 100193323Sed MachineModuleInfo *MMI; 101193323Sed public: 102193323Sed static char ID; // Pass identification, replacement for typeid 103212904Sdim UnreachableMachineBlockElim() : MachineFunctionPass(ID) {} 104193323Sed }; 105193323Sed} 106193323Sedchar UnreachableMachineBlockElim::ID = 0; 107193323Sed 108212904SdimINITIALIZE_PASS(UnreachableMachineBlockElim, "unreachable-mbb-elimination", 109218893Sdim "Remove unreachable machine basic blocks", false, false) 110193323Sed 111212904Sdimchar &llvm::UnreachableMachineBlockElimID = UnreachableMachineBlockElim::ID; 112193323Sed 113198090Srdivackyvoid UnreachableMachineBlockElim::getAnalysisUsage(AnalysisUsage &AU) const { 114198090Srdivacky AU.addPreserved<MachineLoopInfo>(); 115198090Srdivacky AU.addPreserved<MachineDominatorTree>(); 116198090Srdivacky MachineFunctionPass::getAnalysisUsage(AU); 117198090Srdivacky} 118198090Srdivacky 119193323Sedbool UnreachableMachineBlockElim::runOnMachineFunction(MachineFunction &F) { 120193323Sed SmallPtrSet<MachineBasicBlock*, 8> Reachable; 121218893Sdim bool ModifiedPHI = false; 122193323Sed 123193323Sed MMI = getAnalysisIfAvailable<MachineModuleInfo>(); 124198090Srdivacky MachineDominatorTree *MDT = getAnalysisIfAvailable<MachineDominatorTree>(); 125198090Srdivacky MachineLoopInfo *MLI = getAnalysisIfAvailable<MachineLoopInfo>(); 126193323Sed 127193323Sed // Mark all reachable blocks. 128193323Sed for (df_ext_iterator<MachineFunction*, SmallPtrSet<MachineBasicBlock*, 8> > 129193323Sed I = df_ext_begin(&F, Reachable), E = df_ext_end(&F, Reachable); 130193323Sed I != E; ++I) 131193323Sed /* Mark all reachable blocks */; 132193323Sed 133193323Sed // Loop over all dead blocks, remembering them and deleting all instructions 134193323Sed // in them. 135193323Sed std::vector<MachineBasicBlock*> DeadBlocks; 136193323Sed for (MachineFunction::iterator I = F.begin(), E = F.end(); I != E; ++I) { 137193323Sed MachineBasicBlock *BB = I; 138193323Sed 139193323Sed // Test for deadness. 140193323Sed if (!Reachable.count(BB)) { 141193323Sed DeadBlocks.push_back(BB); 142193323Sed 143198090Srdivacky // Update dominator and loop info. 144198090Srdivacky if (MLI) MLI->removeBlock(BB); 145198090Srdivacky if (MDT && MDT->getNode(BB)) MDT->eraseNode(BB); 146198090Srdivacky 147193323Sed while (BB->succ_begin() != BB->succ_end()) { 148193323Sed MachineBasicBlock* succ = *BB->succ_begin(); 149193323Sed 150193323Sed MachineBasicBlock::iterator start = succ->begin(); 151203954Srdivacky while (start != succ->end() && start->isPHI()) { 152193323Sed for (unsigned i = start->getNumOperands() - 1; i >= 2; i-=2) 153193323Sed if (start->getOperand(i).isMBB() && 154193323Sed start->getOperand(i).getMBB() == BB) { 155193323Sed start->RemoveOperand(i); 156193323Sed start->RemoveOperand(i-1); 157193323Sed } 158193323Sed 159193323Sed start++; 160193323Sed } 161193323Sed 162193323Sed BB->removeSuccessor(BB->succ_begin()); 163193323Sed } 164193323Sed } 165193323Sed } 166193323Sed 167193323Sed // Actually remove the blocks now. 168205218Srdivacky for (unsigned i = 0, e = DeadBlocks.size(); i != e; ++i) 169205218Srdivacky DeadBlocks[i]->eraseFromParent(); 170193323Sed 171193323Sed // Cleanup PHI nodes. 172193323Sed for (MachineFunction::iterator I = F.begin(), E = F.end(); I != E; ++I) { 173193323Sed MachineBasicBlock *BB = I; 174193323Sed // Prune unneeded PHI entries. 175193323Sed SmallPtrSet<MachineBasicBlock*, 8> preds(BB->pred_begin(), 176193323Sed BB->pred_end()); 177193323Sed MachineBasicBlock::iterator phi = BB->begin(); 178203954Srdivacky while (phi != BB->end() && phi->isPHI()) { 179193323Sed for (unsigned i = phi->getNumOperands() - 1; i >= 2; i-=2) 180193323Sed if (!preds.count(phi->getOperand(i).getMBB())) { 181193323Sed phi->RemoveOperand(i); 182193323Sed phi->RemoveOperand(i-1); 183218893Sdim ModifiedPHI = true; 184193323Sed } 185193323Sed 186193323Sed if (phi->getNumOperands() == 3) { 187193323Sed unsigned Input = phi->getOperand(1).getReg(); 188193323Sed unsigned Output = phi->getOperand(0).getReg(); 189193323Sed 190193323Sed MachineInstr* temp = phi; 191193323Sed ++phi; 192193323Sed temp->eraseFromParent(); 193218893Sdim ModifiedPHI = true; 194193323Sed 195223017Sdim if (Input != Output) { 196223017Sdim MachineRegisterInfo &MRI = F.getRegInfo(); 197223017Sdim MRI.constrainRegClass(Input, MRI.getRegClass(Output)); 198223017Sdim MRI.replaceRegWith(Output, Input); 199223017Sdim } 200193323Sed 201193323Sed continue; 202193323Sed } 203193323Sed 204193323Sed ++phi; 205193323Sed } 206193323Sed } 207193323Sed 208193323Sed F.RenumberBlocks(); 209193323Sed 210218893Sdim return (DeadBlocks.size() || ModifiedPHI); 211193323Sed} 212