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/UnreachableBlockElim.h"
24 #include "llvm/ADT/DepthFirstIterator.h"
25 #include "llvm/ADT/SmallPtrSet.h"
26 #include "llvm/CodeGen/MachineDominators.h"
27 #include "llvm/CodeGen/MachineFunctionPass.h"
28 #include "llvm/CodeGen/MachineInstrBuilder.h"
29 #include "llvm/CodeGen/MachineLoopInfo.h"
30 #include "llvm/CodeGen/MachineModuleInfo.h"
31 #include "llvm/CodeGen/MachineRegisterInfo.h"
32 #include "llvm/CodeGen/Passes.h"
33 #include "llvm/CodeGen/TargetInstrInfo.h"
34 #include "llvm/IR/CFG.h"
35 #include "llvm/IR/Constant.h"
36 #include "llvm/IR/Dominators.h"
37 #include "llvm/IR/Function.h"
38 #include "llvm/IR/Instructions.h"
39 #include "llvm/IR/Type.h"
40 #include "llvm/Pass.h"
41 using namespace llvm;
42 
43 static bool eliminateUnreachableBlock(Function &F) {
44   df_iterator_default_set<BasicBlock*> Reachable;
45 
46   // Mark all reachable blocks.
47   for (BasicBlock *BB : depth_first_ext(&F, Reachable))
48     (void)BB/* Mark all reachable blocks */;
49 
50   // Loop over all dead blocks, remembering them and deleting all instructions
51   // in them.
52   std::vector<BasicBlock*> DeadBlocks;
53   for (Function::iterator I = F.begin(), E = F.end(); I != E; ++I)
54     if (!Reachable.count(&*I)) {
55       BasicBlock *BB = &*I;
56       DeadBlocks.push_back(BB);
57       while (PHINode *PN = dyn_cast<PHINode>(BB->begin())) {
58         PN->replaceAllUsesWith(Constant::getNullValue(PN->getType()));
59         BB->getInstList().pop_front();
60       }
61       for (succ_iterator SI = succ_begin(BB), E = succ_end(BB); SI != E; ++SI)
62         (*SI)->removePredecessor(BB);
63       BB->dropAllReferences();
64     }
65 
66   // Actually remove the blocks now.
67   for (unsigned i = 0, e = DeadBlocks.size(); i != e; ++i) {
68     DeadBlocks[i]->eraseFromParent();
69   }
70 
71   return !DeadBlocks.empty();
72 }
73 
74 namespace {
75 class UnreachableBlockElimLegacyPass : public FunctionPass {
76   bool runOnFunction(Function &F) override {
77     return eliminateUnreachableBlock(F);
78   }
79 
80 public:
81   static char ID; // Pass identification, replacement for typeid
82   UnreachableBlockElimLegacyPass() : FunctionPass(ID) {
83     initializeUnreachableBlockElimLegacyPassPass(
84         *PassRegistry::getPassRegistry());
85   }
86 
87   void getAnalysisUsage(AnalysisUsage &AU) const override {
88     AU.addPreserved<DominatorTreeWrapperPass>();
89   }
90 };
91 }
92 char UnreachableBlockElimLegacyPass::ID = 0;
93 INITIALIZE_PASS(UnreachableBlockElimLegacyPass, "unreachableblockelim",
94                 "Remove unreachable blocks from the CFG", false, false)
95 
96 FunctionPass *llvm::createUnreachableBlockEliminationPass() {
97   return new UnreachableBlockElimLegacyPass();
98 }
99 
100 PreservedAnalyses UnreachableBlockElimPass::run(Function &F,
101                                                 FunctionAnalysisManager &AM) {
102   bool Changed = eliminateUnreachableBlock(F);
103   if (!Changed)
104     return PreservedAnalyses::all();
105   PreservedAnalyses PA;
106   PA.preserve<DominatorTreeAnalysis>();
107   return PA;
108 }
109 
110 namespace {
111   class UnreachableMachineBlockElim : public MachineFunctionPass {
112     bool runOnMachineFunction(MachineFunction &F) override;
113     void getAnalysisUsage(AnalysisUsage &AU) const override;
114     MachineModuleInfo *MMI;
115   public:
116     static char ID; // Pass identification, replacement for typeid
117     UnreachableMachineBlockElim() : MachineFunctionPass(ID) {}
118   };
119 }
120 char UnreachableMachineBlockElim::ID = 0;
121 
122 INITIALIZE_PASS(UnreachableMachineBlockElim, "unreachable-mbb-elimination",
123   "Remove unreachable machine basic blocks", false, false)
124 
125 char &llvm::UnreachableMachineBlockElimID = UnreachableMachineBlockElim::ID;
126 
127 void UnreachableMachineBlockElim::getAnalysisUsage(AnalysisUsage &AU) const {
128   AU.addPreserved<MachineLoopInfo>();
129   AU.addPreserved<MachineDominatorTree>();
130   MachineFunctionPass::getAnalysisUsage(AU);
131 }
132 
133 bool UnreachableMachineBlockElim::runOnMachineFunction(MachineFunction &F) {
134   df_iterator_default_set<MachineBasicBlock*> Reachable;
135   bool ModifiedPHI = false;
136 
137   MMI = getAnalysisIfAvailable<MachineModuleInfo>();
138   MachineDominatorTree *MDT = getAnalysisIfAvailable<MachineDominatorTree>();
139   MachineLoopInfo *MLI = getAnalysisIfAvailable<MachineLoopInfo>();
140 
141   // Mark all reachable blocks.
142   for (MachineBasicBlock *BB : depth_first_ext(&F, Reachable))
143     (void)BB/* Mark all reachable blocks */;
144 
145   // Loop over all dead blocks, remembering them and deleting all instructions
146   // in them.
147   std::vector<MachineBasicBlock*> DeadBlocks;
148   for (MachineFunction::iterator I = F.begin(), E = F.end(); I != E; ++I) {
149     MachineBasicBlock *BB = &*I;
150 
151     // Test for deadness.
152     if (!Reachable.count(BB)) {
153       DeadBlocks.push_back(BB);
154 
155       // Update dominator and loop info.
156       if (MLI) MLI->removeBlock(BB);
157       if (MDT && MDT->getNode(BB)) MDT->eraseNode(BB);
158 
159       while (BB->succ_begin() != BB->succ_end()) {
160         MachineBasicBlock* succ = *BB->succ_begin();
161 
162         MachineBasicBlock::iterator start = succ->begin();
163         while (start != succ->end() && start->isPHI()) {
164           for (unsigned i = start->getNumOperands() - 1; i >= 2; i-=2)
165             if (start->getOperand(i).isMBB() &&
166                 start->getOperand(i).getMBB() == BB) {
167               start->RemoveOperand(i);
168               start->RemoveOperand(i-1);
169             }
170 
171           start++;
172         }
173 
174         BB->removeSuccessor(BB->succ_begin());
175       }
176     }
177   }
178 
179   // Actually remove the blocks now.
180   for (unsigned i = 0, e = DeadBlocks.size(); i != e; ++i)
181     DeadBlocks[i]->eraseFromParent();
182 
183   // Cleanup PHI nodes.
184   for (MachineFunction::iterator I = F.begin(), E = F.end(); I != E; ++I) {
185     MachineBasicBlock *BB = &*I;
186     // Prune unneeded PHI entries.
187     SmallPtrSet<MachineBasicBlock*, 8> preds(BB->pred_begin(),
188                                              BB->pred_end());
189     MachineBasicBlock::iterator phi = BB->begin();
190     while (phi != BB->end() && phi->isPHI()) {
191       for (unsigned i = phi->getNumOperands() - 1; i >= 2; i-=2)
192         if (!preds.count(phi->getOperand(i).getMBB())) {
193           phi->RemoveOperand(i);
194           phi->RemoveOperand(i-1);
195           ModifiedPHI = true;
196         }
197 
198       if (phi->getNumOperands() == 3) {
199         const MachineOperand &Input = phi->getOperand(1);
200         const MachineOperand &Output = phi->getOperand(0);
201         unsigned InputReg = Input.getReg();
202         unsigned OutputReg = Output.getReg();
203         assert(Output.getSubReg() == 0 && "Cannot have output subregister");
204         ModifiedPHI = true;
205 
206         if (InputReg != OutputReg) {
207           MachineRegisterInfo &MRI = F.getRegInfo();
208           unsigned InputSub = Input.getSubReg();
209           if (InputSub == 0 &&
210               MRI.constrainRegClass(InputReg, MRI.getRegClass(OutputReg)) &&
211               !Input.isUndef()) {
212             MRI.replaceRegWith(OutputReg, InputReg);
213           } else {
214             // The input register to the PHI has a subregister or it can't be
215             // constrained to the proper register class or it is undef:
216             // insert a COPY instead of simply replacing the output
217             // with the input.
218             const TargetInstrInfo *TII = F.getSubtarget().getInstrInfo();
219             BuildMI(*BB, BB->getFirstNonPHI(), phi->getDebugLoc(),
220                     TII->get(TargetOpcode::COPY), OutputReg)
221                 .addReg(InputReg, getRegState(Input), InputSub);
222           }
223           phi++->eraseFromParent();
224         }
225         continue;
226       }
227 
228       ++phi;
229     }
230   }
231 
232   F.RenumberBlocks();
233 
234   return (!DeadBlocks.empty() || ModifiedPHI);
235 }
236