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