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
25using namespace llvm;
26
27#define DEBUG_TYPE "dead-mi-elimination"
28
29STATISTIC(NumDeletes, "Number of dead instructions deleted");
30
31namespace {
32class DeadMachineInstructionElimImpl {
33 const MachineRegisterInfo *MRI = nullptr;
34 const TargetInstrInfo *TII = nullptr;
35 LiveRegUnits LivePhysRegs;
36
37public:
38 bool runImpl(MachineFunction &MF);
39
40private:
41 bool eliminateDeadMI(MachineFunction &MF, bool &NeedAnotherIteration);
42};
43
44class DeadMachineInstructionElim : public MachineFunctionPass {
45public:
46 static char ID; // Pass identification, replacement for typeid
47
48 DeadMachineInstructionElim() : MachineFunctionPass(ID) {}
49
50 bool runOnMachineFunction(MachineFunction &MF) override {
51 if (skipFunction(F: MF.getFunction()))
52 return false;
53 return DeadMachineInstructionElimImpl().runImpl(MF);
54 }
55
56 void getAnalysisUsage(AnalysisUsage &AU) const override {
57 AU.setPreservesCFG();
58 MachineFunctionPass::getAnalysisUsage(AU);
59 }
60
61 MachineFunctionProperties getRequiredProperties() const override {
62 return MachineFunctionProperties().setIsSSA();
63 }
64};
65} // namespace
66
67PreservedAnalyses
68DeadMachineInstructionElimPass::run(MachineFunction &MF,
69 MachineFunctionAnalysisManager &) {
70 MFPropsModifier _(*this, MF);
71
72 if (!DeadMachineInstructionElimImpl().runImpl(MF))
73 return PreservedAnalyses::all();
74 PreservedAnalyses PA = getMachineFunctionPassPreservedAnalyses();
75 PA.preserveSet<CFGAnalyses>();
76 return PA;
77}
78
79char DeadMachineInstructionElim::ID = 0;
80char &llvm::DeadMachineInstructionElimID = DeadMachineInstructionElim::ID;
81
82INITIALIZE_PASS(DeadMachineInstructionElim, DEBUG_TYPE,
83 "Remove dead machine instructions", false, false)
84
85bool DeadMachineInstructionElimImpl::runImpl(MachineFunction &MF) {
86 MRI = &MF.getRegInfo();
87
88 const TargetSubtargetInfo &ST = MF.getSubtarget();
89 TII = ST.getInstrInfo();
90 LivePhysRegs.init(TRI: *ST.getRegisterInfo());
91
92 bool NeedAnotherIteration;
93 bool AnyChanges = eliminateDeadMI(MF, NeedAnotherIteration);
94 while (NeedAnotherIteration)
95 eliminateDeadMI(MF, NeedAnotherIteration);
96 return AnyChanges;
97}
98
99bool DeadMachineInstructionElimImpl::eliminateDeadMI(
100 MachineFunction &MF, bool &NeedAnotherIteration) {
101 bool AnyChanges = false;
102 SmallPtrSet<MachineBasicBlock *, 4> NeedsProcessing;
103
104 // Loop over all instructions in all blocks, from bottom to top, so that it's
105 // more likely that chains of dependent but ultimately dead instructions will
106 // be cleaned up.
107 for (MachineBasicBlock *MBB : post_order(G: &MF)) {
108 LivePhysRegs.addLiveOuts(MBB: *MBB);
109 NeedsProcessing.erase(Ptr: MBB);
110
111 // Now scan the instructions and delete dead ones, tracking physreg
112 // liveness as we go.
113 for (MachineInstr &MI : make_early_inc_range(Range: reverse(C&: *MBB))) {
114 if (MI.isDebugInstr())
115 continue;
116 // If the instruction is dead, delete it!
117 if (MI.isDead(MRI: *MRI, LivePhysRegs: &LivePhysRegs)) {
118 if (MI.isPHI()) {
119 for (MachineBasicBlock *P : MBB->predecessors())
120 NeedsProcessing.insert(Ptr: P);
121 }
122 LLVM_DEBUG(dbgs() << "DeadMachineInstructionElim: DELETING: " << MI);
123 // It is possible that some DBG_VALUE instructions refer to this
124 // instruction. They will be deleted in the live debug variable
125 // analysis.
126 MI.eraseFromParent();
127 AnyChanges = true;
128 ++NumDeletes;
129 continue;
130 }
131
132 for (MachineOperand &MO : MI.all_defs()) {
133 Register Reg = MO.getReg();
134 if (Reg.isPhysical() && !MO.isDead() && !MRI->isReserved(PhysReg: Reg) &&
135 LivePhysRegs.available(Reg))
136 MO.setIsDead();
137 }
138
139 LivePhysRegs.stepBackward(MI);
140 }
141 }
142 LivePhysRegs.clear();
143 NeedAnotherIteration = !NeedsProcessing.empty();
144 return AnyChanges;
145}
146