1//===-- UnreachableBlockElim.cpp - Remove unreachable blocks for codegen --===//
2//
3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4// See https://llvm.org/LICENSE.txt for license information.
5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6//
7//===----------------------------------------------------------------------===//
8//
9// This pass is an extremely simple version of the SimplifyCFG pass. Its sole
10// job is to delete LLVM basic blocks that are not reachable from the entry
11// node. To do this, it performs a simple depth first traversal of the CFG,
12// then deletes any unvisited nodes.
13//
14// Note that this pass is really a hack. In particular, the instruction
15// selectors for various targets should just not generate code for unreachable
16// blocks. Until LLVM has a more systematic way of defining instruction
17// selectors, however, we cannot really expect them to handle additional
18// complexity.
19//
20//===----------------------------------------------------------------------===//
21
22#include "llvm/CodeGen/UnreachableBlockElim.h"
23#include "llvm/ADT/DepthFirstIterator.h"
24#include "llvm/ADT/SmallPtrSet.h"
25#include "llvm/CodeGen/MachineBasicBlock.h"
26#include "llvm/CodeGen/MachineBlockFrequencyInfo.h"
27#include "llvm/CodeGen/MachineDominators.h"
28#include "llvm/CodeGen/MachineFunctionPass.h"
29#include "llvm/CodeGen/MachineInstrBuilder.h"
30#include "llvm/CodeGen/MachineLoopInfo.h"
31#include "llvm/CodeGen/MachinePostDominators.h"
32#include "llvm/CodeGen/MachineRegisterInfo.h"
33#include "llvm/CodeGen/Passes.h"
34#include "llvm/CodeGen/TargetInstrInfo.h"
35#include "llvm/IR/Dominators.h"
36#include "llvm/InitializePasses.h"
37#include "llvm/Pass.h"
38#include "llvm/Transforms/Utils/BasicBlockUtils.h"
39using namespace llvm;
40
41namespace {
42class UnreachableBlockElimLegacyPass : public FunctionPass {
43 bool runOnFunction(Function &F) override {
44 return llvm::EliminateUnreachableBlocks(F);
45 }
46
47public:
48 static char ID; // Pass identification, replacement for typeid
49 UnreachableBlockElimLegacyPass() : FunctionPass(ID) {}
50
51 void getAnalysisUsage(AnalysisUsage &AU) const override {
52 AU.addPreserved<DominatorTreeWrapperPass>();
53 AU.addPreserved<MachineBlockFrequencyInfoWrapperPass>();
54 }
55};
56}
57char UnreachableBlockElimLegacyPass::ID = 0;
58INITIALIZE_PASS(UnreachableBlockElimLegacyPass, "unreachableblockelim",
59 "Remove unreachable blocks from the CFG", false, false)
60
61FunctionPass *llvm::createUnreachableBlockEliminationPass() {
62 return new UnreachableBlockElimLegacyPass();
63}
64
65PreservedAnalyses UnreachableBlockElimPass::run(Function &F,
66 FunctionAnalysisManager &AM) {
67 bool Changed = llvm::EliminateUnreachableBlocks(F);
68 if (!Changed)
69 return PreservedAnalyses::all();
70 PreservedAnalyses PA;
71 PA.preserve<DominatorTreeAnalysis>();
72 PA.preserve<MachineBlockFrequencyAnalysis>();
73 return PA;
74}
75
76namespace {
77class UnreachableMachineBlockElim {
78 MachineDominatorTree *MDT;
79 MachinePostDominatorTree *MPDT;
80 MachineLoopInfo *MLI;
81
82public:
83 UnreachableMachineBlockElim(MachineDominatorTree *MDT,
84 MachinePostDominatorTree *MPDT,
85 MachineLoopInfo *MLI)
86 : MDT(MDT), MPDT(MPDT), MLI(MLI) {}
87 bool run(MachineFunction &MF);
88};
89
90class UnreachableMachineBlockElimLegacy : public MachineFunctionPass {
91 bool runOnMachineFunction(MachineFunction &F) override;
92 void getAnalysisUsage(AnalysisUsage &AU) const override;
93
94public:
95 static char ID; // Pass identification, replacement for typeid
96 UnreachableMachineBlockElimLegacy() : MachineFunctionPass(ID) {}
97};
98} // namespace
99
100char UnreachableMachineBlockElimLegacy::ID = 0;
101
102INITIALIZE_PASS(UnreachableMachineBlockElimLegacy,
103 "unreachable-mbb-elimination",
104 "Remove unreachable machine basic blocks", false, false)
105
106char &llvm::UnreachableMachineBlockElimID =
107 UnreachableMachineBlockElimLegacy::ID;
108
109void UnreachableMachineBlockElimLegacy::getAnalysisUsage(
110 AnalysisUsage &AU) const {
111 AU.addPreserved<MachineLoopInfoWrapperPass>();
112 AU.addPreserved<MachineDominatorTreeWrapperPass>();
113 AU.addPreserved<MachinePostDominatorTreeWrapperPass>();
114 AU.addPreserved<MachineBlockFrequencyInfoWrapperPass>();
115 MachineFunctionPass::getAnalysisUsage(AU);
116}
117
118PreservedAnalyses
119UnreachableMachineBlockElimPass::run(MachineFunction &MF,
120 MachineFunctionAnalysisManager &AM) {
121 auto *MDT = AM.getCachedResult<MachineDominatorTreeAnalysis>(IR&: MF);
122 auto *MPDT = AM.getCachedResult<MachinePostDominatorTreeAnalysis>(IR&: MF);
123 auto *MLI = AM.getCachedResult<MachineLoopAnalysis>(IR&: MF);
124
125 if (!UnreachableMachineBlockElim(MDT, MPDT, MLI).run(MF))
126 return PreservedAnalyses::all();
127
128 return getMachineFunctionPassPreservedAnalyses()
129 .preserve<MachineLoopAnalysis>()
130 .preserve<MachineDominatorTreeAnalysis>()
131 .preserve<MachinePostDominatorTreeAnalysis>()
132 .preserve<MachineBlockFrequencyAnalysis>();
133}
134
135bool UnreachableMachineBlockElimLegacy::runOnMachineFunction(
136 MachineFunction &MF) {
137 MachineDominatorTreeWrapperPass *MDTWrapper =
138 getAnalysisIfAvailable<MachineDominatorTreeWrapperPass>();
139 MachinePostDominatorTreeWrapperPass *MPDTWrapper =
140 getAnalysisIfAvailable<MachinePostDominatorTreeWrapperPass>();
141 MachineDominatorTree *MDT = MDTWrapper ? &MDTWrapper->getDomTree() : nullptr;
142 MachinePostDominatorTree *MPDT =
143 MPDTWrapper ? &MPDTWrapper->getPostDomTree() : nullptr;
144 MachineLoopInfoWrapperPass *MLIWrapper =
145 getAnalysisIfAvailable<MachineLoopInfoWrapperPass>();
146 MachineLoopInfo *MLI = MLIWrapper ? &MLIWrapper->getLI() : nullptr;
147
148 return UnreachableMachineBlockElim(MDT, MPDT, MLI).run(MF);
149}
150
151bool UnreachableMachineBlockElim::run(MachineFunction &F) {
152 df_iterator_default_set<MachineBasicBlock *> Reachable;
153 bool ModifiedPHI = false;
154
155 // Mark all reachable blocks.
156 for (MachineBasicBlock *BB : depth_first_ext(G: &F, S&: Reachable))
157 (void)BB/* Mark all reachable blocks */;
158
159 // Loop over all dead blocks, remembering them and deleting all instructions
160 // in them.
161 std::vector<MachineBasicBlock*> DeadBlocks;
162 for (MachineBasicBlock &BB : F) {
163 // Test for deadness.
164 if (!Reachable.count(Ptr: &BB)) {
165 DeadBlocks.push_back(x: &BB);
166
167 // Update dominator and loop info.
168 if (MLI) MLI->removeBlock(BB: &BB);
169 if (MDT && MDT->getNode(BB: &BB)) MDT->eraseNode(BB: &BB);
170 if (MPDT && MPDT->getNode(BB: &BB))
171 MPDT->eraseNode(BB: &BB);
172
173 while (!BB.succ_empty()) {
174 (*BB.succ_begin())->removePHIsIncomingValuesForPredecessor(PredMBB: BB);
175 BB.removeSuccessor(I: BB.succ_begin());
176 }
177 }
178 }
179
180 // Actually remove the blocks now.
181 for (MachineBasicBlock *BB : DeadBlocks) {
182 // Remove any call information for calls in the block.
183 for (auto &I : BB->instrs())
184 if (I.shouldUpdateAdditionalCallInfo())
185 BB->getParent()->eraseAdditionalCallInfo(MI: &I);
186
187 BB->eraseFromParent();
188 }
189
190 // Cleanup PHI nodes.
191 for (MachineBasicBlock &BB : F) {
192 // Prune unneeded PHI entries.
193 SmallPtrSet<MachineBasicBlock *, 8> preds(llvm::from_range,
194 BB.predecessors());
195 for (MachineInstr &Phi : make_early_inc_range(Range: BB.phis())) {
196 for (unsigned i = Phi.getNumOperands() - 1; i >= 2; i -= 2) {
197 if (!preds.count(Ptr: Phi.getOperand(i).getMBB())) {
198 Phi.removeOperand(OpNo: i);
199 Phi.removeOperand(OpNo: i - 1);
200 ModifiedPHI = true;
201 }
202 }
203
204 if (Phi.getNumOperands() == 3) {
205 const MachineOperand &Input = Phi.getOperand(i: 1);
206 const MachineOperand &Output = Phi.getOperand(i: 0);
207 Register InputReg = Input.getReg();
208 Register OutputReg = Output.getReg();
209 assert(Output.getSubReg() == 0 && "Cannot have output subregister");
210 ModifiedPHI = true;
211
212 if (InputReg != OutputReg) {
213 MachineRegisterInfo &MRI = F.getRegInfo();
214 unsigned InputSub = Input.getSubReg();
215 if (InputSub == 0 &&
216 MRI.constrainRegClass(Reg: InputReg, RC: MRI.getRegClass(Reg: OutputReg)) &&
217 !Input.isUndef()) {
218 MRI.replaceRegWith(FromReg: OutputReg, ToReg: InputReg);
219 } else {
220 // The input register to the PHI has a subregister or it can't be
221 // constrained to the proper register class or it is undef:
222 // insert a COPY instead of simply replacing the output
223 // with the input.
224 const TargetInstrInfo *TII = F.getSubtarget().getInstrInfo();
225 BuildMI(BB, I: BB.getFirstNonPHI(), MIMD: Phi.getDebugLoc(),
226 MCID: TII->get(Opcode: TargetOpcode::COPY), DestReg: OutputReg)
227 .addReg(RegNo: InputReg, Flags: getRegState(RegOp: Input), SubReg: InputSub);
228 }
229 Phi.eraseFromParent();
230 }
231 }
232 }
233 }
234
235 F.RenumberBlocks();
236 if (MDT)
237 MDT->updateBlockNumbers();
238
239 if (MPDT)
240 MPDT->updateBlockNumbers();
241
242 return (!DeadBlocks.empty() || ModifiedPHI);
243}
244