UnreachableBlockElim.cpp revision 212904
156893Sfenner//===-- UnreachableBlockElim.cpp - Remove unreachable blocks for codegen --===// 256893Sfenner// 356893Sfenner// The LLVM Compiler Infrastructure 456893Sfenner// 556893Sfenner// This file is distributed under the University of Illinois Open Source 656893Sfenner// License. See LICENSE.TXT for details. 756893Sfenner// 856893Sfenner//===----------------------------------------------------------------------===// 956893Sfenner// 1056893Sfenner// This pass is an extremely simple version of the SimplifyCFG pass. Its sole 1156893Sfenner// job is to delete LLVM basic blocks that are not reachable from the entry 1256893Sfenner// node. To do this, it performs a simple depth first traversal of the CFG, 1356893Sfenner// then deletes any unvisited nodes. 1456893Sfenner// 1556893Sfenner// Note that this pass is really a hack. In particular, the instruction 1656893Sfenner// selectors for various targets should just not generate code for unreachable 1756893Sfenner// blocks. Until LLVM has a more systematic way of defining instruction 1856893Sfenner// selectors, however, we cannot really expect them to handle additional 1956893Sfenner// complexity. 2056893Sfenner// 2156893Sfenner//===----------------------------------------------------------------------===// 2256893Sfenner 23127668Sbms#include "llvm/CodeGen/Passes.h" 24190207Srpaulo#include "llvm/Constant.h" 2556893Sfenner#include "llvm/Instructions.h" 2656893Sfenner#include "llvm/Function.h" 2756893Sfenner#include "llvm/Pass.h" 2856893Sfenner#include "llvm/Type.h" 2956893Sfenner#include "llvm/Analysis/ProfileInfo.h" 3056893Sfenner#include "llvm/CodeGen/MachineDominators.h" 31127668Sbms#include "llvm/CodeGen/MachineFunctionPass.h" 3256893Sfenner#include "llvm/CodeGen/MachineModuleInfo.h" 3356893Sfenner#include "llvm/CodeGen/MachineLoopInfo.h" 3456893Sfenner#include "llvm/CodeGen/MachineRegisterInfo.h" 3556893Sfenner#include "llvm/Support/CFG.h" 3656893Sfenner#include "llvm/Target/TargetInstrInfo.h" 3756893Sfenner#include "llvm/ADT/DepthFirstIterator.h" 3875115Sfenner#include "llvm/ADT/SmallPtrSet.h" 3998524Sfennerusing namespace llvm; 4056893Sfenner 4175115Sfennernamespace { 4256893Sfenner class UnreachableBlockElim : public FunctionPass { 4356893Sfenner virtual bool runOnFunction(Function &F); 4456893Sfenner public: 45172683Smlaier static char ID; // Pass identification, replacement for typeid 46172683Smlaier UnreachableBlockElim() : FunctionPass(ID) {} 47172683Smlaier 48172683Smlaier virtual void getAnalysisUsage(AnalysisUsage &AU) const { 49172683Smlaier AU.addPreserved<ProfileInfo>(); 50172683Smlaier } 51172683Smlaier }; 5256893Sfenner} 53127668Sbmschar UnreachableBlockElim::ID = 0; 54127668SbmsINITIALIZE_PASS(UnreachableBlockElim, "unreachableblockelim", 5556893Sfenner "Remove unreachable blocks from the CFG", false, false); 5656893Sfenner 5756893SfennerFunctionPass *llvm::createUnreachableBlockEliminationPass() { 5898524Sfenner return new UnreachableBlockElim(); 5998524Sfenner} 6098524Sfenner 61127668Sbmsbool UnreachableBlockElim::runOnFunction(Function &F) { 6298524Sfenner SmallPtrSet<BasicBlock*, 8> Reachable; 63162017Ssam 64162017Ssam // Mark all reachable blocks. 6598524Sfenner for (df_ext_iterator<Function*, SmallPtrSet<BasicBlock*, 8> > I = 66162017Ssam df_ext_begin(&F, Reachable), E = df_ext_end(&F, Reachable); I != E; ++I) 67162017Ssam /* Mark all reachable blocks */; 68162017Ssam 69162017Ssam // Loop over all dead blocks, remembering them and deleting all instructions 7098524Sfenner // in them. 7156893Sfenner std::vector<BasicBlock*> DeadBlocks; 72172683Smlaier for (Function::iterator I = F.begin(), E = F.end(); I != E; ++I) 73172683Smlaier if (!Reachable.count(I)) { 74172683Smlaier BasicBlock *BB = I; 75172683Smlaier DeadBlocks.push_back(BB); 76172683Smlaier while (PHINode *PN = dyn_cast<PHINode>(BB->begin())) { 7756893Sfenner PN->replaceAllUsesWith(Constant::getNullValue(PN->getType())); 7856893Sfenner BB->getInstList().pop_front(); 7956893Sfenner } 80172683Smlaier for (succ_iterator SI = succ_begin(BB), E = succ_end(BB); SI != E; ++SI) 81172683Smlaier (*SI)->removePredecessor(BB); 8275115Sfenner BB->dropAllReferences(); 8356893Sfenner } 84172683Smlaier 8556893Sfenner // Actually remove the blocks now. 8656893Sfenner ProfileInfo *PI = getAnalysisIfAvailable<ProfileInfo>(); 8756893Sfenner for (unsigned i = 0, e = DeadBlocks.size(); i != e; ++i) { 88172683Smlaier if (PI) PI->removeBlock(DeadBlocks[i]); 8956893Sfenner DeadBlocks[i]->eraseFromParent(); 9056893Sfenner } 9156893Sfenner 92172683Smlaier return DeadBlocks.size(); 9356893Sfenner} 9456893Sfenner 9556893Sfenner 96172683Smlaiernamespace { 9756893Sfenner class UnreachableMachineBlockElim : public MachineFunctionPass { 9856893Sfenner virtual bool runOnMachineFunction(MachineFunction &F); 99127668Sbms virtual void getAnalysisUsage(AnalysisUsage &AU) const; 100127668Sbms MachineModuleInfo *MMI; 101172683Smlaier public: 102127668Sbms static char ID; // Pass identification, replacement for typeid 103127668Sbms UnreachableMachineBlockElim() : MachineFunctionPass(ID) {} 104127668Sbms }; 105172683Smlaier} 106172683Smlaierchar UnreachableMachineBlockElim::ID = 0; 107172683Smlaier 108172683SmlaierINITIALIZE_PASS(UnreachableMachineBlockElim, "unreachable-mbb-elimination", 109127668Sbms "Remove unreachable machine basic blocks", false, false); 110172683Smlaier 111127668Sbmschar &llvm::UnreachableMachineBlockElimID = UnreachableMachineBlockElim::ID; 112127668Sbms 113172683Smlaiervoid UnreachableMachineBlockElim::getAnalysisUsage(AnalysisUsage &AU) const { 114172683Smlaier AU.addPreserved<MachineLoopInfo>(); 115127668Sbms AU.addPreserved<MachineDominatorTree>(); 11656893Sfenner MachineFunctionPass::getAnalysisUsage(AU); 117127668Sbms} 118127668Sbms 11956893Sfennerbool UnreachableMachineBlockElim::runOnMachineFunction(MachineFunction &F) { 12056893Sfenner SmallPtrSet<MachineBasicBlock*, 8> Reachable; 121147899Ssam 122147899Ssam MMI = getAnalysisIfAvailable<MachineModuleInfo>(); 123147899Ssam MachineDominatorTree *MDT = getAnalysisIfAvailable<MachineDominatorTree>(); 12456893Sfenner MachineLoopInfo *MLI = getAnalysisIfAvailable<MachineLoopInfo>(); 125147899Ssam 12656893Sfenner // Mark all reachable blocks. 12756893Sfenner for (df_ext_iterator<MachineFunction*, SmallPtrSet<MachineBasicBlock*, 8> > 12856893Sfenner I = df_ext_begin(&F, Reachable), E = df_ext_end(&F, Reachable); 12956893Sfenner I != E; ++I) 13056893Sfenner /* Mark all reachable blocks */; 131147899Ssam 132147899Ssam // Loop over all dead blocks, remembering them and deleting all instructions 13356893Sfenner // in them. 13456893Sfenner std::vector<MachineBasicBlock*> DeadBlocks; 135147899Ssam for (MachineFunction::iterator I = F.begin(), E = F.end(); I != E; ++I) { 136147899Ssam MachineBasicBlock *BB = I; 137147899Ssam 13856893Sfenner // Test for deadness. 13956893Sfenner if (!Reachable.count(BB)) { 14056893Sfenner DeadBlocks.push_back(BB); 14156893Sfenner 142147899Ssam // Update dominator and loop info. 143147899Ssam if (MLI) MLI->removeBlock(BB); 14456893Sfenner if (MDT && MDT->getNode(BB)) MDT->eraseNode(BB); 14556893Sfenner 14656893Sfenner while (BB->succ_begin() != BB->succ_end()) { 14756893Sfenner MachineBasicBlock* succ = *BB->succ_begin(); 14898524Sfenner 149147899Ssam MachineBasicBlock::iterator start = succ->begin(); 15056893Sfenner while (start != succ->end() && start->isPHI()) { 151147899Ssam for (unsigned i = start->getNumOperands() - 1; i >= 2; i-=2) 152147899Ssam if (start->getOperand(i).isMBB() && 153127668Sbms start->getOperand(i).getMBB() == BB) { 15456893Sfenner start->RemoveOperand(i); 15598524Sfenner start->RemoveOperand(i-1); 156147899Ssam } 157127668Sbms 15856893Sfenner start++; 159127668Sbms } 160147899Ssam 161147899Ssam BB->removeSuccessor(BB->succ_begin()); 162147899Ssam } 163147899Ssam } 164147899Ssam } 165147899Ssam 166147899Ssam // Actually remove the blocks now. 167147899Ssam for (unsigned i = 0, e = DeadBlocks.size(); i != e; ++i) 168147899Ssam DeadBlocks[i]->eraseFromParent(); 16956893Sfenner 17056893Sfenner // Cleanup PHI nodes. 171127668Sbms for (MachineFunction::iterator I = F.begin(), E = F.end(); I != E; ++I) { 17256893Sfenner MachineBasicBlock *BB = I; 17356893Sfenner // Prune unneeded PHI entries. 17456893Sfenner SmallPtrSet<MachineBasicBlock*, 8> preds(BB->pred_begin(), 17556893Sfenner BB->pred_end()); 176147899Ssam MachineBasicBlock::iterator phi = BB->begin(); 177147899Ssam while (phi != BB->end() && phi->isPHI()) { 178147899Ssam for (unsigned i = phi->getNumOperands() - 1; i >= 2; i-=2) 179147899Ssam if (!preds.count(phi->getOperand(i).getMBB())) { 180147899Ssam phi->RemoveOperand(i); 181147899Ssam phi->RemoveOperand(i-1); 182147899Ssam } 183147899Ssam 184147899Ssam if (phi->getNumOperands() == 3) { 185147899Ssam unsigned Input = phi->getOperand(1).getReg(); 186147899Ssam unsigned Output = phi->getOperand(0).getReg(); 187147899Ssam 188147899Ssam MachineInstr* temp = phi; 189147899Ssam ++phi; 190147899Ssam temp->eraseFromParent(); 19156893Sfenner 19256893Sfenner if (Input != Output) 193127668Sbms F.getRegInfo().replaceRegWith(Output, Input); 194127668Sbms 195127668Sbms continue; 19656893Sfenner } 19756893Sfenner 19856893Sfenner ++phi; 199147899Ssam } 200147899Ssam } 201127668Sbms 202127668Sbms F.RenumberBlocks(); 203127668Sbms 204127668Sbms return DeadBlocks.size(); 205127668Sbms} 206127668Sbms