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);
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} // namespace
62
63PreservedAnalyses
64DeadMachineInstructionElimPass::run(MachineFunction &MF,
65 MachineFunctionAnalysisManager &) {
66 if (!DeadMachineInstructionElimImpl().runImpl(MF))
67 return PreservedAnalyses::all();
68 PreservedAnalyses PA = getMachineFunctionPassPreservedAnalyses();
69 PA.preserveSet<CFGAnalyses>();
70 return PA;
71}
72
73char DeadMachineInstructionElim::ID = 0;
74char &llvm::DeadMachineInstructionElimID = DeadMachineInstructionElim::ID;
75
76INITIALIZE_PASS(DeadMachineInstructionElim, DEBUG_TYPE,
77 "Remove dead machine instructions", false, false)
78
79bool DeadMachineInstructionElimImpl::runImpl(MachineFunction &MF) {
80 MRI = &MF.getRegInfo();
81
82 const TargetSubtargetInfo &ST = MF.getSubtarget();
83 TII = ST.getInstrInfo();
84 LivePhysRegs.init(TRI: *ST.getRegisterInfo());
85
86 bool AnyChanges = eliminateDeadMI(MF);
87 while (AnyChanges && eliminateDeadMI(MF))
88 ;
89 return AnyChanges;
90}
91
92bool DeadMachineInstructionElimImpl::eliminateDeadMI(MachineFunction &MF) {
93 bool AnyChanges = false;
94
95 // Loop over all instructions in all blocks, from bottom to top, so that it's
96 // more likely that chains of dependent but ultimately dead instructions will
97 // be cleaned up.
98 for (MachineBasicBlock *MBB : post_order(G: &MF)) {
99 LivePhysRegs.addLiveOuts(MBB: *MBB);
100
101 // Now scan the instructions and delete dead ones, tracking physreg
102 // liveness as we go.
103 for (MachineInstr &MI : make_early_inc_range(Range: reverse(C&: *MBB))) {
104 // If the instruction is dead, delete it!
105 if (MI.isDead(MRI: *MRI, LivePhysRegs: &LivePhysRegs)) {
106 LLVM_DEBUG(dbgs() << "DeadMachineInstructionElim: DELETING: " << MI);
107 // It is possible that some DBG_VALUE instructions refer to this
108 // instruction. They will be deleted in the live debug variable
109 // analysis.
110 MI.eraseFromParent();
111 AnyChanges = true;
112 ++NumDeletes;
113 continue;
114 }
115 LivePhysRegs.stepBackward(MI);
116 }
117 }
118 LivePhysRegs.clear();
119 return AnyChanges;
120}
121