Line data Source code
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 436635 : static bool eliminateUnreachableBlock(Function &F) {
44 : df_iterator_default_set<BasicBlock*> Reachable;
45 :
46 : // Mark all reachable blocks.
47 4565637 : 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 3828438 : for (Function::iterator I = F.begin(), E = F.end(); I != E; ++I)
54 3391803 : if (!Reachable.count(&*I)) {
55 136071 : BasicBlock *BB = &*I;
56 136071 : DeadBlocks.push_back(BB);
57 136072 : while (PHINode *PN = dyn_cast<PHINode>(BB->begin())) {
58 1 : PN->replaceAllUsesWith(Constant::getNullValue(PN->getType()));
59 1 : BB->getInstList().pop_front();
60 1 : }
61 260538 : for (succ_iterator SI = succ_begin(BB), E = succ_end(BB); SI != E; ++SI)
62 124467 : (*SI)->removePredecessor(BB);
63 136071 : BB->dropAllReferences();
64 : }
65 :
66 : // Actually remove the blocks now.
67 1009341 : for (unsigned i = 0, e = DeadBlocks.size(); i != e; ++i) {
68 272142 : DeadBlocks[i]->eraseFromParent();
69 : }
70 :
71 436635 : return !DeadBlocks.empty();
72 : }
73 :
74 : namespace {
75 : class UnreachableBlockElimLegacyPass : public FunctionPass {
76 436634 : bool runOnFunction(Function &F) override {
77 436634 : return eliminateUnreachableBlock(F);
78 : }
79 :
80 : public:
81 : static char ID; // Pass identification, replacement for typeid
82 30692 : UnreachableBlockElimLegacyPass() : FunctionPass(ID) {
83 30692 : initializeUnreachableBlockElimLegacyPassPass(
84 30692 : *PassRegistry::getPassRegistry());
85 : }
86 :
87 30537 : void getAnalysisUsage(AnalysisUsage &AU) const override {
88 : AU.addPreserved<DominatorTreeWrapperPass>();
89 30537 : }
90 : };
91 : }
92 : char UnreachableBlockElimLegacyPass::ID = 0;
93 155144 : INITIALIZE_PASS(UnreachableBlockElimLegacyPass, "unreachableblockelim",
94 : "Remove unreachable blocks from the CFG", false, false)
95 :
96 30691 : FunctionPass *llvm::createUnreachableBlockEliminationPass() {
97 30691 : return new UnreachableBlockElimLegacyPass();
98 : }
99 :
100 1 : PreservedAnalyses UnreachableBlockElimPass::run(Function &F,
101 : FunctionAnalysisManager &AM) {
102 1 : bool Changed = eliminateUnreachableBlock(F);
103 1 : if (!Changed)
104 : return PreservedAnalyses::all();
105 1 : PreservedAnalyses PA;
106 : PA.preserve<DominatorTreeAnalysis>();
107 1 : 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 22052 : UnreachableMachineBlockElim() : MachineFunctionPass(ID) {}
118 : };
119 : }
120 : char UnreachableMachineBlockElim::ID = 0;
121 :
122 116927 : INITIALIZE_PASS(UnreachableMachineBlockElim, "unreachable-mbb-elimination",
123 : "Remove unreachable machine basic blocks", false, false)
124 :
125 : char &llvm::UnreachableMachineBlockElimID = UnreachableMachineBlockElim::ID;
126 :
127 22045 : void UnreachableMachineBlockElim::getAnalysisUsage(AnalysisUsage &AU) const {
128 : AU.addPreserved<MachineLoopInfo>();
129 : AU.addPreserved<MachineDominatorTree>();
130 22045 : MachineFunctionPass::getAnalysisUsage(AU);
131 22045 : }
132 :
133 209251 : bool UnreachableMachineBlockElim::runOnMachineFunction(MachineFunction &F) {
134 : df_iterator_default_set<MachineBasicBlock*> Reachable;
135 : bool ModifiedPHI = false;
136 :
137 209251 : MMI = getAnalysisIfAvailable<MachineModuleInfo>();
138 209251 : MachineDominatorTree *MDT = getAnalysisIfAvailable<MachineDominatorTree>();
139 209251 : MachineLoopInfo *MLI = getAnalysisIfAvailable<MachineLoopInfo>();
140 :
141 : // Mark all reachable blocks.
142 1103145 : 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 684798 : for (MachineFunction::iterator I = F.begin(), E = F.end(); I != E; ++I) {
149 475548 : MachineBasicBlock *BB = &*I;
150 :
151 : // Test for deadness.
152 475548 : if (!Reachable.count(BB)) {
153 156 : DeadBlocks.push_back(BB);
154 :
155 : // Update dominator and loop info.
156 156 : if (MLI) MLI->removeBlock(BB);
157 156 : if (MDT && MDT->getNode(BB)) MDT->eraseNode(BB);
158 :
159 315 : while (BB->succ_begin() != BB->succ_end()) {
160 3 : MachineBasicBlock* succ = *BB->succ_begin();
161 :
162 : MachineBasicBlock::iterator start = succ->begin();
163 5 : while (start != succ->end() && start->isPHI()) {
164 6 : for (unsigned i = start->getNumOperands() - 1; i >= 2; i-=2)
165 8 : if (start->getOperand(i).isMBB() &&
166 4 : start->getOperand(i).getMBB() == BB) {
167 2 : start->RemoveOperand(i);
168 2 : start->RemoveOperand(i-1);
169 : }
170 :
171 : start++;
172 : }
173 :
174 6 : BB->removeSuccessor(BB->succ_begin());
175 : }
176 : }
177 : }
178 :
179 : // Actually remove the blocks now.
180 418657 : for (unsigned i = 0, e = DeadBlocks.size(); i != e; ++i)
181 312 : DeadBlocks[i]->eraseFromParent();
182 :
183 : // Cleanup PHI nodes.
184 684644 : 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 475393 : BB->pred_end());
189 : MachineBasicBlock::iterator phi = BB->begin();
190 563678 : while (phi != BB->end() && phi->isPHI()) {
191 288220 : for (unsigned i = phi->getNumOperands() - 1; i >= 2; i-=2)
192 399868 : if (!preds.count(phi->getOperand(i).getMBB())) {
193 0 : phi->RemoveOperand(i);
194 0 : phi->RemoveOperand(i-1);
195 : ModifiedPHI = true;
196 : }
197 :
198 88286 : if (phi->getNumOperands() == 3) {
199 144 : const MachineOperand &Input = phi->getOperand(1);
200 : const MachineOperand &Output = phi->getOperand(0);
201 144 : unsigned InputReg = Input.getReg();
202 144 : unsigned OutputReg = Output.getReg();
203 : assert(Output.getSubReg() == 0 && "Cannot have output subregister");
204 : ModifiedPHI = true;
205 :
206 144 : if (InputReg != OutputReg) {
207 144 : MachineRegisterInfo &MRI = F.getRegInfo();
208 : unsigned InputSub = Input.getSubReg();
209 143 : if (InputSub == 0 &&
210 287 : MRI.constrainRegClass(InputReg, MRI.getRegClass(OutputReg)) &&
211 : !Input.isUndef()) {
212 142 : 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 2 : const TargetInstrInfo *TII = F.getSubtarget().getInstrInfo();
219 2 : BuildMI(*BB, BB->getFirstNonPHI(), phi->getDebugLoc(),
220 4 : TII->get(TargetOpcode::COPY), OutputReg)
221 2 : .addReg(InputReg, getRegState(Input), InputSub);
222 : }
223 144 : phi++->eraseFromParent();
224 : }
225 144 : continue;
226 : }
227 :
228 : ++phi;
229 : }
230 : }
231 :
232 209251 : F.RenumberBlocks();
233 :
234 209251 : return (!DeadBlocks.empty() || ModifiedPHI);
235 : }
|
