1 | //===- DeadMachineInstructionElim.cpp - Remove dead machine instructions --===// |
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 is an extremely simple MachineInstr-level dead-code-elimination pass. |
10 | // |
11 | //===----------------------------------------------------------------------===// |
12 | |
13 | #include "llvm/CodeGen/DeadMachineInstructionElim.h" |
14 | #include "llvm/ADT/PostOrderIterator.h" |
15 | #include "llvm/ADT/Statistic.h" |
16 | #include "llvm/CodeGen/LiveRegUnits.h" |
17 | #include "llvm/CodeGen/MachineFunctionPass.h" |
18 | #include "llvm/CodeGen/MachineRegisterInfo.h" |
19 | #include "llvm/CodeGen/TargetSubtargetInfo.h" |
20 | #include "llvm/InitializePasses.h" |
21 | #include "llvm/Pass.h" |
22 | #include "llvm/Support/Debug.h" |
23 | #include "llvm/Support/raw_ostream.h" |
24 | |
25 | using namespace llvm; |
26 | |
27 | #define DEBUG_TYPE "dead-mi-elimination" |
28 | |
29 | STATISTIC(NumDeletes, "Number of dead instructions deleted" ); |
30 | |
31 | namespace { |
32 | class DeadMachineInstructionElimImpl { |
33 | const MachineRegisterInfo *MRI = nullptr; |
34 | const TargetInstrInfo *TII = nullptr; |
35 | LiveRegUnits LivePhysRegs; |
36 | |
37 | public: |
38 | bool runImpl(MachineFunction &MF); |
39 | |
40 | private: |
41 | bool isDead(const MachineInstr *MI) const; |
42 | bool eliminateDeadMI(MachineFunction &MF); |
43 | }; |
44 | |
45 | class DeadMachineInstructionElim : public MachineFunctionPass { |
46 | public: |
47 | static char ID; // Pass identification, replacement for typeid |
48 | |
49 | DeadMachineInstructionElim() : MachineFunctionPass(ID) { |
50 | initializeDeadMachineInstructionElimPass(*PassRegistry::getPassRegistry()); |
51 | } |
52 | |
53 | bool runOnMachineFunction(MachineFunction &MF) override { |
54 | if (skipFunction(F: MF.getFunction())) |
55 | return false; |
56 | return DeadMachineInstructionElimImpl().runImpl(MF); |
57 | } |
58 | |
59 | void getAnalysisUsage(AnalysisUsage &AU) const override { |
60 | AU.setPreservesCFG(); |
61 | MachineFunctionPass::getAnalysisUsage(AU); |
62 | } |
63 | }; |
64 | } // namespace |
65 | |
66 | PreservedAnalyses |
67 | DeadMachineInstructionElimPass::run(MachineFunction &MF, |
68 | MachineFunctionAnalysisManager &) { |
69 | if (!DeadMachineInstructionElimImpl().runImpl(MF)) |
70 | return PreservedAnalyses::all(); |
71 | PreservedAnalyses PA = getMachineFunctionPassPreservedAnalyses(); |
72 | PA.preserveSet<CFGAnalyses>(); |
73 | return PA; |
74 | } |
75 | |
76 | char DeadMachineInstructionElim::ID = 0; |
77 | char &llvm::DeadMachineInstructionElimID = DeadMachineInstructionElim::ID; |
78 | |
79 | INITIALIZE_PASS(DeadMachineInstructionElim, DEBUG_TYPE, |
80 | "Remove dead machine instructions" , false, false) |
81 | |
82 | bool DeadMachineInstructionElimImpl::isDead(const MachineInstr *MI) const { |
83 | // Technically speaking inline asm without side effects and no defs can still |
84 | // be deleted. But there is so much bad inline asm code out there, we should |
85 | // let them be. |
86 | if (MI->isInlineAsm()) |
87 | return false; |
88 | |
89 | // Don't delete frame allocation labels. |
90 | if (MI->getOpcode() == TargetOpcode::LOCAL_ESCAPE) |
91 | return false; |
92 | |
93 | // Don't delete instructions with side effects. |
94 | bool SawStore = false; |
95 | if (!MI->isSafeToMove(AA: nullptr, SawStore) && !MI->isPHI()) |
96 | return false; |
97 | |
98 | // Examine each operand. |
99 | for (const MachineOperand &MO : MI->all_defs()) { |
100 | Register Reg = MO.getReg(); |
101 | if (Reg.isPhysical()) { |
102 | // Don't delete live physreg defs, or any reserved register defs. |
103 | if (!LivePhysRegs.available(Reg) || MRI->isReserved(PhysReg: Reg)) |
104 | return false; |
105 | } else { |
106 | if (MO.isDead()) { |
107 | #ifndef NDEBUG |
108 | // Basic check on the register. All of them should be 'undef'. |
109 | for (auto &U : MRI->use_nodbg_operands(Reg)) |
110 | assert(U.isUndef() && "'Undef' use on a 'dead' register is found!" ); |
111 | #endif |
112 | continue; |
113 | } |
114 | for (const MachineInstr &Use : MRI->use_nodbg_instructions(Reg)) { |
115 | if (&Use != MI) |
116 | // This def has a non-debug use. Don't delete the instruction! |
117 | return false; |
118 | } |
119 | } |
120 | } |
121 | |
122 | // If there are no defs with uses, the instruction is dead. |
123 | return true; |
124 | } |
125 | |
126 | bool DeadMachineInstructionElimImpl::runImpl(MachineFunction &MF) { |
127 | MRI = &MF.getRegInfo(); |
128 | |
129 | const TargetSubtargetInfo &ST = MF.getSubtarget(); |
130 | TII = ST.getInstrInfo(); |
131 | LivePhysRegs.init(TRI: *ST.getRegisterInfo()); |
132 | |
133 | bool AnyChanges = eliminateDeadMI(MF); |
134 | while (AnyChanges && eliminateDeadMI(MF)) |
135 | ; |
136 | return AnyChanges; |
137 | } |
138 | |
139 | bool DeadMachineInstructionElimImpl::eliminateDeadMI(MachineFunction &MF) { |
140 | bool AnyChanges = false; |
141 | |
142 | // Loop over all instructions in all blocks, from bottom to top, so that it's |
143 | // more likely that chains of dependent but ultimately dead instructions will |
144 | // be cleaned up. |
145 | for (MachineBasicBlock *MBB : post_order(G: &MF)) { |
146 | LivePhysRegs.addLiveOuts(MBB: *MBB); |
147 | |
148 | // Now scan the instructions and delete dead ones, tracking physreg |
149 | // liveness as we go. |
150 | for (MachineInstr &MI : make_early_inc_range(Range: reverse(C&: *MBB))) { |
151 | // If the instruction is dead, delete it! |
152 | if (isDead(MI: &MI)) { |
153 | LLVM_DEBUG(dbgs() << "DeadMachineInstructionElim: DELETING: " << MI); |
154 | // It is possible that some DBG_VALUE instructions refer to this |
155 | // instruction. They will be deleted in the live debug variable |
156 | // analysis. |
157 | MI.eraseFromParent(); |
158 | AnyChanges = true; |
159 | ++NumDeletes; |
160 | continue; |
161 | } |
162 | |
163 | LivePhysRegs.stepBackward(MI); |
164 | } |
165 | } |
166 | |
167 | LivePhysRegs.clear(); |
168 | return AnyChanges; |
169 | } |
170 | |