UnreachableBlockElim.cpp revision 223017
1181834Sroberto//===-- UnreachableBlockElim.cpp - Remove unreachable blocks for codegen --===// 2181834Sroberto// 3181834Sroberto// The LLVM Compiler Infrastructure 4181834Sroberto// 5181834Sroberto// This file is distributed under the University of Illinois Open Source 6181834Sroberto// License. See LICENSE.TXT for details. 7181834Sroberto// 8181834Sroberto//===----------------------------------------------------------------------===// 9181834Sroberto// 10181834Sroberto// This pass is an extremely simple version of the SimplifyCFG pass. Its sole 11181834Sroberto// job is to delete LLVM basic blocks that are not reachable from the entry 12181834Sroberto// node. To do this, it performs a simple depth first traversal of the CFG, 13181834Sroberto// then deletes any unvisited nodes. 14181834Sroberto// 15181834Sroberto// Note that this pass is really a hack. In particular, the instruction 16181834Sroberto// selectors for various targets should just not generate code for unreachable 17285612Sdelphij// blocks. Until LLVM has a more systematic way of defining instruction 18285612Sdelphij// selectors, however, we cannot really expect them to handle additional 19285612Sdelphij// complexity. 20285612Sdelphij// 21285612Sdelphij//===----------------------------------------------------------------------===// 22285612Sdelphij 23285612Sdelphij#include "llvm/CodeGen/Passes.h" 24285612Sdelphij#include "llvm/Constant.h" 25285612Sdelphij#include "llvm/Instructions.h" 26285612Sdelphij#include "llvm/Function.h" 27285612Sdelphij#include "llvm/Pass.h" 28285612Sdelphij#include "llvm/Type.h" 29285612Sdelphij#include "llvm/Analysis/Dominators.h" 30285612Sdelphij#include "llvm/Analysis/ProfileInfo.h" 31181834Sroberto#include "llvm/CodeGen/MachineDominators.h" 32181834Sroberto#include "llvm/CodeGen/MachineFunctionPass.h" 33181834Sroberto#include "llvm/CodeGen/MachineModuleInfo.h" 34285612Sdelphij#include "llvm/CodeGen/MachineLoopInfo.h" 35181834Sroberto#include "llvm/CodeGen/MachineRegisterInfo.h" 36181834Sroberto#include "llvm/Support/CFG.h" 37285612Sdelphij#include "llvm/Target/TargetInstrInfo.h" 38330567Sgordon#include "llvm/ADT/DepthFirstIterator.h" 39285612Sdelphij#include "llvm/ADT/SmallPtrSet.h" 40285612Sdelphijusing namespace llvm; 41330567Sgordon 42285612Sdelphijnamespace { 43285612Sdelphij class UnreachableBlockElim : public FunctionPass { 44285612Sdelphij virtual bool runOnFunction(Function &F); 45181834Sroberto public: 46181834Sroberto static char ID; // Pass identification, replacement for typeid 47181834Sroberto UnreachableBlockElim() : FunctionPass(ID) { 48285612Sdelphij initializeUnreachableBlockElimPass(*PassRegistry::getPassRegistry()); 49285612Sdelphij } 50285612Sdelphij 51285612Sdelphij virtual void getAnalysisUsage(AnalysisUsage &AU) const { 52285612Sdelphij AU.addPreserved<DominatorTree>(); 53285612Sdelphij AU.addPreserved<ProfileInfo>(); 54285612Sdelphij } 55285612Sdelphij }; 56285612Sdelphij} 57285612Sdelphijchar UnreachableBlockElim::ID = 0; 58330567SgordonINITIALIZE_PASS(UnreachableBlockElim, "unreachableblockelim", 59285612Sdelphij "Remove unreachable blocks from the CFG", false, false) 60285612Sdelphij 61285612SdelphijFunctionPass *llvm::createUnreachableBlockEliminationPass() { 62285612Sdelphij return new UnreachableBlockElim(); 63181834Sroberto} 64181834Sroberto 65181834Srobertobool UnreachableBlockElim::runOnFunction(Function &F) { 66285612Sdelphij SmallPtrSet<BasicBlock*, 8> Reachable; 67181834Sroberto 68285612Sdelphij // Mark all reachable blocks. 69285612Sdelphij for (df_ext_iterator<Function*, SmallPtrSet<BasicBlock*, 8> > I = 70181834Sroberto df_ext_begin(&F, Reachable), E = df_ext_end(&F, Reachable); I != E; ++I) 71330567Sgordon /* Mark all reachable blocks */; 72330567Sgordon 73330567Sgordon // Loop over all dead blocks, remembering them and deleting all instructions 74181834Sroberto // in them. 75181834Sroberto std::vector<BasicBlock*> DeadBlocks; 76181834Sroberto for (Function::iterator I = F.begin(), E = F.end(); I != E; ++I) 77181834Sroberto if (!Reachable.count(I)) { 78285612Sdelphij BasicBlock *BB = I; 79181834Sroberto DeadBlocks.push_back(BB); 80285612Sdelphij while (PHINode *PN = dyn_cast<PHINode>(BB->begin())) { 81181834Sroberto PN->replaceAllUsesWith(Constant::getNullValue(PN->getType())); 82181834Sroberto BB->getInstList().pop_front(); 83285612Sdelphij } 84285612Sdelphij for (succ_iterator SI = succ_begin(BB), E = succ_end(BB); SI != E; ++SI) 85181834Sroberto (*SI)->removePredecessor(BB); 86181834Sroberto BB->dropAllReferences(); 87181834Sroberto } 88181834Sroberto 89285612Sdelphij // Actually remove the blocks now. 90181834Sroberto ProfileInfo *PI = getAnalysisIfAvailable<ProfileInfo>(); 91285612Sdelphij for (unsigned i = 0, e = DeadBlocks.size(); i != e; ++i) { 92181834Sroberto if (PI) PI->removeBlock(DeadBlocks[i]); 93181834Sroberto DeadBlocks[i]->eraseFromParent(); 94285612Sdelphij } 95181834Sroberto 96181834Sroberto return DeadBlocks.size(); 97181834Sroberto} 98181834Sroberto 99285612Sdelphij 100181834Srobertonamespace { 101285612Sdelphij class UnreachableMachineBlockElim : public MachineFunctionPass { 102181834Sroberto virtual bool runOnMachineFunction(MachineFunction &F); 103181834Sroberto virtual void getAnalysisUsage(AnalysisUsage &AU) const; 104285612Sdelphij MachineModuleInfo *MMI; 105285612Sdelphij public: 106181834Sroberto static char ID; // Pass identification, replacement for typeid 107181834Sroberto UnreachableMachineBlockElim() : MachineFunctionPass(ID) {} 108181834Sroberto }; 109181834Sroberto} 110181834Srobertochar UnreachableMachineBlockElim::ID = 0; 111285612Sdelphij 112285612SdelphijINITIALIZE_PASS(UnreachableMachineBlockElim, "unreachable-mbb-elimination", 113285612Sdelphij "Remove unreachable machine basic blocks", false, false) 114285612Sdelphij 115285612Sdelphijchar &llvm::UnreachableMachineBlockElimID = UnreachableMachineBlockElim::ID; 116181834Sroberto 117285612Sdelphijvoid UnreachableMachineBlockElim::getAnalysisUsage(AnalysisUsage &AU) const { 118285612Sdelphij AU.addPreserved<MachineLoopInfo>(); 119285612Sdelphij AU.addPreserved<MachineDominatorTree>(); 120285612Sdelphij MachineFunctionPass::getAnalysisUsage(AU); 121330567Sgordon} 122330567Sgordon 123330567Sgordonbool UnreachableMachineBlockElim::runOnMachineFunction(MachineFunction &F) { 124330567Sgordon SmallPtrSet<MachineBasicBlock*, 8> Reachable; 125330567Sgordon bool ModifiedPHI = false; 126181834Sroberto 127181834Sroberto MMI = getAnalysisIfAvailable<MachineModuleInfo>(); 128181834Sroberto MachineDominatorTree *MDT = getAnalysisIfAvailable<MachineDominatorTree>(); 129181834Sroberto MachineLoopInfo *MLI = getAnalysisIfAvailable<MachineLoopInfo>(); 130285612Sdelphij 131285612Sdelphij // Mark all reachable blocks. 132285612Sdelphij for (df_ext_iterator<MachineFunction*, SmallPtrSet<MachineBasicBlock*, 8> > 133285612Sdelphij I = df_ext_begin(&F, Reachable), E = df_ext_end(&F, Reachable); 134285612Sdelphij I != E; ++I) 135285612Sdelphij /* Mark all reachable blocks */; 136285612Sdelphij 137285612Sdelphij // Loop over all dead blocks, remembering them and deleting all instructions 138285612Sdelphij // in them. 139285612Sdelphij std::vector<MachineBasicBlock*> DeadBlocks; 140285612Sdelphij for (MachineFunction::iterator I = F.begin(), E = F.end(); I != E; ++I) { 141285612Sdelphij MachineBasicBlock *BB = I; 142285612Sdelphij 143181834Sroberto // Test for deadness. 144181834Sroberto if (!Reachable.count(BB)) { 145181834Sroberto DeadBlocks.push_back(BB); 146181834Sroberto 147285612Sdelphij // Update dominator and loop info. 148330567Sgordon if (MLI) MLI->removeBlock(BB); 149181834Sroberto if (MDT && MDT->getNode(BB)) MDT->eraseNode(BB); 150285612Sdelphij 151181834Sroberto while (BB->succ_begin() != BB->succ_end()) { 152181834Sroberto MachineBasicBlock* succ = *BB->succ_begin(); 153181834Sroberto 154181834Sroberto MachineBasicBlock::iterator start = succ->begin(); 155330567Sgordon while (start != succ->end() && start->isPHI()) { 156330567Sgordon for (unsigned i = start->getNumOperands() - 1; i >= 2; i-=2) 157330567Sgordon if (start->getOperand(i).isMBB() && 158330567Sgordon start->getOperand(i).getMBB() == BB) { 159330567Sgordon start->RemoveOperand(i); 160330567Sgordon start->RemoveOperand(i-1); 161330567Sgordon } 162330567Sgordon 163330567Sgordon start++; 164285612Sdelphij } 165181834Sroberto 166285612Sdelphij BB->removeSuccessor(BB->succ_begin()); 167181834Sroberto } 168181834Sroberto } 169285612Sdelphij } 170285612Sdelphij 171181834Sroberto // Actually remove the blocks now. 172181834Sroberto for (unsigned i = 0, e = DeadBlocks.size(); i != e; ++i) 173181834Sroberto DeadBlocks[i]->eraseFromParent(); 174181834Sroberto 175181834Sroberto // Cleanup PHI nodes. 176285612Sdelphij for (MachineFunction::iterator I = F.begin(), E = F.end(); I != E; ++I) { 177285612Sdelphij MachineBasicBlock *BB = I; 178181834Sroberto // Prune unneeded PHI entries. 179181834Sroberto SmallPtrSet<MachineBasicBlock*, 8> preds(BB->pred_begin(), 180285612Sdelphij BB->pred_end()); 181181834Sroberto MachineBasicBlock::iterator phi = BB->begin(); 182285612Sdelphij while (phi != BB->end() && phi->isPHI()) { 183285612Sdelphij for (unsigned i = phi->getNumOperands() - 1; i >= 2; i-=2) 184285612Sdelphij if (!preds.count(phi->getOperand(i).getMBB())) { 185285612Sdelphij phi->RemoveOperand(i); 186285612Sdelphij phi->RemoveOperand(i-1); 187181834Sroberto ModifiedPHI = true; 188181834Sroberto } 189181834Sroberto 190181834Sroberto if (phi->getNumOperands() == 3) { 191181834Sroberto unsigned Input = phi->getOperand(1).getReg(); 192285612Sdelphij unsigned Output = phi->getOperand(0).getReg(); 193285612Sdelphij 194181834Sroberto MachineInstr* temp = phi; 195181834Sroberto ++phi; 196285612Sdelphij temp->eraseFromParent(); 197181834Sroberto ModifiedPHI = true; 198285612Sdelphij 199285612Sdelphij if (Input != Output) { 200285612Sdelphij MachineRegisterInfo &MRI = F.getRegInfo(); 201285612Sdelphij MRI.constrainRegClass(Input, MRI.getRegClass(Output)); 202285612Sdelphij MRI.replaceRegWith(Output, Input); 203181834Sroberto } 204181834Sroberto 205181834Sroberto continue; 206181834Sroberto } 207285612Sdelphij 208181834Sroberto ++phi; 209181834Sroberto } 210285612Sdelphij } 211285612Sdelphij 212285612Sdelphij F.RenumberBlocks(); 213181834Sroberto 214285612Sdelphij return (DeadBlocks.size() || ModifiedPHI); 215330567Sgordon} 216285612Sdelphij