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