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