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