LLVM  16.0.0git
DeadMachineInstructionElim.cpp
Go to the documentation of this file.
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 
14 #include "llvm/ADT/Statistic.h"
19 #include "llvm/InitializePasses.h"
20 #include "llvm/Pass.h"
21 #include "llvm/Support/Debug.h"
23 
24 using namespace llvm;
25 
26 #define DEBUG_TYPE "dead-mi-elimination"
27 
28 STATISTIC(NumDeletes, "Number of dead instructions deleted");
29 
30 namespace {
31  class DeadMachineInstructionElim : public MachineFunctionPass {
32  bool runOnMachineFunction(MachineFunction &MF) override;
33 
34  const MachineRegisterInfo *MRI;
35  const TargetInstrInfo *TII;
37 
38  public:
39  static char ID; // Pass identification, replacement for typeid
40  DeadMachineInstructionElim() : MachineFunctionPass(ID) {
42  }
43 
44  void getAnalysisUsage(AnalysisUsage &AU) const override {
45  AU.setPreservesCFG();
47  }
48 
49  private:
50  bool isDead(const MachineInstr *MI) const;
51 
52  bool eliminateDeadMI(MachineFunction &MF);
53  };
54 }
57 
58 INITIALIZE_PASS(DeadMachineInstructionElim, DEBUG_TYPE,
59  "Remove dead machine instructions", false, false)
60 
61 bool DeadMachineInstructionElim::isDead(const MachineInstr *MI) const {
62  // Technically speaking inline asm without side effects and no defs can still
63  // be deleted. But there is so much bad inline asm code out there, we should
64  // let them be.
65  if (MI->isInlineAsm())
66  return false;
67 
68  // Don't delete frame allocation labels.
69  if (MI->getOpcode() == TargetOpcode::LOCAL_ESCAPE)
70  return false;
71 
72  // Don't delete instructions with side effects.
73  bool SawStore = false;
74  if (!MI->isSafeToMove(nullptr, SawStore) && !MI->isPHI())
75  return false;
76 
77  // Examine each operand.
78  for (const MachineOperand &MO : MI->operands()) {
79  if (MO.isReg() && MO.isDef()) {
80  Register Reg = MO.getReg();
81  if (Reg.isPhysical()) {
82  // Don't delete live physreg defs, or any reserved register defs.
84  return false;
85  } else {
86  if (MO.isDead()) {
87 #ifndef NDEBUG
88  // Basic check on the register. All of them should be '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 
107 bool DeadMachineInstructionElim::runOnMachineFunction(MachineFunction &MF) {
108  if (skipFunction(MF.getFunction()))
109  return false;
110 
111  MRI = &MF.getRegInfo();
112 
113  const TargetSubtargetInfo &ST = MF.getSubtarget();
114  TII = ST.getInstrInfo();
115  LivePhysRegs.init(*ST.getRegisterInfo());
116 
117  bool AnyChanges = eliminateDeadMI(MF);
118  while (AnyChanges && eliminateDeadMI(MF))
119  ;
120  return AnyChanges;
121 }
122 
123 bool DeadMachineInstructionElim::eliminateDeadMI(MachineFunction &MF) {
124  bool AnyChanges = false;
125 
126  // Loop over all instructions in all blocks, from bottom to top, so that it's
127  // more likely that chains of dependent but ultimately dead instructions will
128  // be cleaned up.
129  for (MachineBasicBlock *MBB : post_order(&MF)) {
131 
132  // Now scan the instructions and delete dead ones, tracking physreg
133  // liveness as we go.
135  // If the instruction is dead, delete it!
136  if (isDead(&MI)) {
137  LLVM_DEBUG(dbgs() << "DeadMachineInstructionElim: DELETING: " << MI);
138  // It is possible that some DBG_VALUE instructions refer to this
139  // instruction. They will be deleted in the live debug variable
140  // analysis.
141  MI.eraseFromParent();
142  AnyChanges = true;
143  ++NumDeletes;
144  continue;
145  }
146 
148  }
149  }
150 
152  return AnyChanges;
153 }
MI
IRTranslator LLVM IR MI
Definition: IRTranslator.cpp:109
llvm
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
llvm::initializeDeadMachineInstructionElimPass
void initializeDeadMachineInstructionElimPass(PassRegistry &)
llvm::AArch64PACKey::ID
ID
Definition: AArch64BaseInfo.h:818
llvm::MachineRegisterInfo
MachineRegisterInfo - Keep track of information for virtual and physical registers,...
Definition: MachineRegisterInfo.h:50
Pass.h
Statistic.h
llvm::X86Disassembler::Reg
Reg
All possible values of the reg field in the ModR/M byte.
Definition: X86DisassemblerDecoder.h:462
llvm::MachineFunctionPass
MachineFunctionPass - This class adapts the FunctionPass interface to allow convenient creation of pa...
Definition: MachineFunctionPass.h:30
llvm::LivePhysRegs
A set of physical registers with utility functions to track liveness when walking backward/forward th...
Definition: LivePhysRegs.h:50
llvm::MachineRegisterInfo::use_nodbg_instructions
iterator_range< use_instr_nodbg_iterator > use_nodbg_instructions(Register Reg) const
Definition: MachineRegisterInfo.h:551
llvm::MachineFunctionPass::getAnalysisUsage
void getAnalysisUsage(AnalysisUsage &AU) const override
getAnalysisUsage - Subclasses that override getAnalysisUsage must call this.
Definition: MachineFunctionPass.cpp:167
LLVM_DEBUG
#define LLVM_DEBUG(X)
Definition: Debug.h:101
MachineRegisterInfo.h
llvm::dbgs
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:163
llvm::MachineFunction::getRegInfo
MachineRegisterInfo & getRegInfo()
getRegInfo - Return information about the registers currently in use.
Definition: MachineFunction.h:670
llvm::TargetInstrInfo
TargetInstrInfo - Interface to description of machine instruction set.
Definition: TargetInstrInfo.h:98
llvm::MachineRegisterInfo::use_nodbg_operands
iterator_range< use_nodbg_iterator > use_nodbg_operands(Register Reg) const
Definition: MachineRegisterInfo.h:534
llvm::PassRegistry::getPassRegistry
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
Definition: PassRegistry.cpp:24
llvm::MachineRegisterInfo::isReserved
bool isReserved(MCRegister PhysReg) const
isReserved - Returns true when PhysReg is a reserved register.
Definition: MachineRegisterInfo.h:930
llvm::AnalysisUsage
Represent the analysis usage information of a pass.
Definition: PassAnalysisSupport.h:47
llvm::LivePhysRegs::addLiveOuts
void addLiveOuts(const MachineBasicBlock &MBB)
Adds all live-out registers of basic block MBB.
Definition: LivePhysRegs.cpp:232
TII
const HexagonInstrInfo * TII
Definition: HexagonCopyToCombine.cpp:125
llvm::MachineOperand
MachineOperand class - Representation of each machine instruction operand.
Definition: MachineOperand.h:48
llvm::STATISTIC
STATISTIC(NumFunctions, "Total number of functions")
llvm::LiveRegUnits
A set of register units used to track register liveness.
Definition: LiveRegUnits.h:30
llvm::CallingConv::ID
unsigned ID
LLVM IR allows to use arbitrary numbers as calling convention identifiers.
Definition: CallingConv.h:24
llvm::MachineBasicBlock
Definition: MachineBasicBlock.h:94
llvm::MachineFunction::getSubtarget
const TargetSubtargetInfo & getSubtarget() const
getSubtarget - Return the subtarget for which this machine code is being compiled.
Definition: MachineFunction.h:660
llvm::LivePhysRegs::stepBackward
void stepBackward(const MachineInstr &MI)
Simulates liveness when stepping backwards over an instruction(bundle).
Definition: LivePhysRegs.cpp:68
llvm::MachineInstr
Representation of each machine instruction.
Definition: MachineInstr.h:66
const
aarch64 promote const
Definition: AArch64PromoteConstant.cpp:232
llvm::ARM_MB::ST
@ ST
Definition: ARMBaseInfo.h:73
llvm::LivePhysRegs::available
bool available(const MachineRegisterInfo &MRI, MCPhysReg Reg) const
Returns true if register Reg and no aliasing register is in the set.
Definition: LivePhysRegs.cpp:141
llvm::make_early_inc_range
iterator_range< early_inc_iterator_impl< detail::IterOfRange< RangeT > > > make_early_inc_range(RangeT &&Range)
Make a range that does early increment to allow mutation of the underlying range without disrupting i...
Definition: STLExtras.h:716
MachineFunctionPass.h
assert
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
llvm::MachineFunction
Definition: MachineFunction.h:257
llvm::AnalysisUsage::setPreservesCFG
void setPreservesCFG()
This function should be called by the pass, iff they do not:
Definition: Pass.cpp:265
llvm::LivePhysRegs::init
void init(const TargetRegisterInfo &TRI)
(re-)initializes and clears the set.
Definition: LivePhysRegs.h:68
DEBUG_TYPE
#define DEBUG_TYPE
Definition: DeadMachineInstructionElim.cpp:26
TargetSubtargetInfo.h
LiveRegUnits.h
llvm::TargetSubtargetInfo
TargetSubtargetInfo - Generic base class for all target subtargets.
Definition: TargetSubtargetInfo.h:62
MRI
unsigned const MachineRegisterInfo * MRI
Definition: AArch64AdvSIMDScalarPass.cpp:105
llvm::Register
Wrapper class representing virtual and physical registers.
Definition: Register.h:19
MBB
MachineBasicBlock & MBB
Definition: AArch64SLSHardening.cpp:74
llvm::MachineFunction::getFunction
Function & getFunction()
Return the LLVM function that this machine code represents.
Definition: MachineFunction.h:626
llvm::post_order
iterator_range< po_iterator< T > > post_order(const T &G)
Definition: PostOrderIterator.h:189
llvm::DeadMachineInstructionElimID
char & DeadMachineInstructionElimID
DeadMachineInstructionElim - This pass removes dead machine instructions.
Definition: DeadMachineInstructionElim.cpp:56
PostOrderIterator.h
llvm::LivePhysRegs::clear
void clear()
Clears the set.
Definition: LivePhysRegs.h:75
llvm::reverse
auto reverse(ContainerTy &&C)
Definition: STLExtras.h:485
INITIALIZE_PASS
INITIALIZE_PASS(DeadMachineInstructionElim, DEBUG_TYPE, "Remove dead machine instructions", false, false) bool DeadMachineInstructionElim
Definition: DeadMachineInstructionElim.cpp:58
raw_ostream.h
InitializePasses.h
Debug.h
llvm::Use
A Use represents the edge between a Value definition and its users.
Definition: Use.h:43