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