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/ADT/Statistic.h"
14 #include "llvm/CodeGen/MachineFunctionPass.h"
15 #include "llvm/CodeGen/MachineRegisterInfo.h"
16 #include "llvm/CodeGen/Passes.h"
17 #include "llvm/CodeGen/TargetSubtargetInfo.h"
18 #include "llvm/InitializePasses.h"
19 #include "llvm/Pass.h"
20 #include "llvm/Support/Debug.h"
21 #include "llvm/Support/raw_ostream.h"
22
23 using namespace llvm;
24
25 #define DEBUG_TYPE "dead-mi-elimination"
26
27 STATISTIC(NumDeletes, "Number of dead instructions deleted");
28
29 namespace {
30 class DeadMachineInstructionElim : public MachineFunctionPass {
31 bool runOnMachineFunction(MachineFunction &MF) override;
32
33 const TargetRegisterInfo *TRI;
34 const MachineRegisterInfo *MRI;
35 const TargetInstrInfo *TII;
36 BitVector LivePhysRegs;
37
38 public:
39 static char ID; // Pass identification, replacement for typeid
DeadMachineInstructionElim()40 DeadMachineInstructionElim() : MachineFunctionPass(ID) {
41 initializeDeadMachineInstructionElimPass(*PassRegistry::getPassRegistry());
42 }
43
getAnalysisUsage(AnalysisUsage & AU) const44 void getAnalysisUsage(AnalysisUsage &AU) const override {
45 AU.setPreservesCFG();
46 MachineFunctionPass::getAnalysisUsage(AU);
47 }
48
49 private:
50 bool isDead(const MachineInstr *MI) const;
51 };
52 }
53 char DeadMachineInstructionElim::ID = 0;
54 char &llvm::DeadMachineInstructionElimID = DeadMachineInstructionElim::ID;
55
56 INITIALIZE_PASS(DeadMachineInstructionElim, DEBUG_TYPE,
57 "Remove dead machine instructions", false, false)
58
isDead(const MachineInstr * MI) const59 bool DeadMachineInstructionElim::isDead(const MachineInstr *MI) const {
60 // Technically speaking inline asm without side effects and no defs can still
61 // be deleted. But there is so much bad inline asm code out there, we should
62 // let them be.
63 if (MI->isInlineAsm())
64 return false;
65
66 // Don't delete frame allocation labels.
67 if (MI->getOpcode() == TargetOpcode::LOCAL_ESCAPE)
68 return false;
69
70 // Don't delete instructions with side effects.
71 bool SawStore = false;
72 if (!MI->isSafeToMove(nullptr, SawStore) && !MI->isPHI())
73 return false;
74
75 // Examine each operand.
76 for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
77 const MachineOperand &MO = MI->getOperand(i);
78 if (MO.isReg() && MO.isDef()) {
79 Register Reg = MO.getReg();
80 if (Register::isPhysicalRegister(Reg)) {
81 // Don't delete live physreg defs, or any reserved register defs.
82 if (LivePhysRegs.test(Reg) || MRI->isReserved(Reg))
83 return false;
84 } else {
85 if (MO.isDead()) {
86 #ifndef NDEBUG
87 // Sanity check on uses of this dead register. All of them should be
88 // 'undef'.
89 for (auto &U : MRI->use_nodbg_operands(Reg))
90 assert(U.isUndef() && "'Undef' use on a 'dead' register is found!");
91 #endif
92 continue;
93 }
94 for (const MachineInstr &Use : MRI->use_nodbg_instructions(Reg)) {
95 if (&Use != MI)
96 // This def has a non-debug use. Don't delete the instruction!
97 return false;
98 }
99 }
100 }
101 }
102
103 // If there are no defs with uses, the instruction is dead.
104 return true;
105 }
106
runOnMachineFunction(MachineFunction & MF)107 bool DeadMachineInstructionElim::runOnMachineFunction(MachineFunction &MF) {
108 if (skipFunction(MF.getFunction()))
109 return false;
110
111 bool AnyChanges = false;
112 MRI = &MF.getRegInfo();
113 TRI = MF.getSubtarget().getRegisterInfo();
114 TII = MF.getSubtarget().getInstrInfo();
115
116 // Loop over all instructions in all blocks, from bottom to top, so that it's
117 // more likely that chains of dependent but ultimately dead instructions will
118 // be cleaned up.
119 for (MachineBasicBlock &MBB : make_range(MF.rbegin(), MF.rend())) {
120 // Start out assuming that reserved registers are live out of this block.
121 LivePhysRegs = MRI->getReservedRegs();
122
123 // Add live-ins from successors to LivePhysRegs. Normally, physregs are not
124 // live across blocks, but some targets (x86) can have flags live out of a
125 // block.
126 for (MachineBasicBlock::succ_iterator S = MBB.succ_begin(),
127 E = MBB.succ_end(); S != E; S++)
128 for (const auto &LI : (*S)->liveins())
129 LivePhysRegs.set(LI.PhysReg);
130
131 // Now scan the instructions and delete dead ones, tracking physreg
132 // liveness as we go.
133 for (MachineBasicBlock::reverse_iterator MII = MBB.rbegin(),
134 MIE = MBB.rend(); MII != MIE; ) {
135 MachineInstr *MI = &*MII++;
136
137 // If the instruction is dead, delete it!
138 if (isDead(MI)) {
139 LLVM_DEBUG(dbgs() << "DeadMachineInstructionElim: DELETING: " << *MI);
140 // It is possible that some DBG_VALUE instructions refer to this
141 // instruction. They get marked as undef and will be deleted
142 // in the live debug variable analysis.
143 MI->eraseFromParentAndMarkDBGValuesForRemoval();
144 AnyChanges = true;
145 ++NumDeletes;
146 continue;
147 }
148
149 // Record the physreg defs.
150 for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
151 const MachineOperand &MO = MI->getOperand(i);
152 if (MO.isReg() && MO.isDef()) {
153 Register Reg = MO.getReg();
154 if (Register::isPhysicalRegister(Reg)) {
155 // Check the subreg set, not the alias set, because a def
156 // of a super-register may still be partially live after
157 // this def.
158 for (MCSubRegIterator SR(Reg, TRI,/*IncludeSelf=*/true);
159 SR.isValid(); ++SR)
160 LivePhysRegs.reset(*SR);
161 }
162 } else if (MO.isRegMask()) {
163 // Register mask of preserved registers. All clobbers are dead.
164 LivePhysRegs.clearBitsNotInMask(MO.getRegMask());
165 }
166 }
167 // Record the physreg uses, after the defs, in case a physreg is
168 // both defined and used in the same instruction.
169 for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
170 const MachineOperand &MO = MI->getOperand(i);
171 if (MO.isReg() && MO.isUse()) {
172 Register Reg = MO.getReg();
173 if (Register::isPhysicalRegister(Reg)) {
174 for (MCRegAliasIterator AI(Reg, TRI, true); AI.isValid(); ++AI)
175 LivePhysRegs.set(*AI);
176 }
177 }
178 }
179 }
180 }
181
182 LivePhysRegs.clear();
183 return AnyChanges;
184 }
185