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