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