LLVM  15.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"
18 #include "llvm/InitializePasses.h"
19 #include "llvm/Pass.h"
20 #include "llvm/Support/Debug.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;
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();
82  // Don't delete live physreg defs, or any reserved register defs.
83  if (LivePhysRegs.test(Reg) || MRI->isReserved(Reg))
84  return false;
85  } else {
86  if (MO.isDead()) {
87 #ifndef NDEBUG
88  // Baisc check on the register. All of them should be
89  // 'undef'.
90  for (auto &U : MRI->use_nodbg_operands(Reg))
91  assert(U.isUndef() && "'Undef' use on a 'dead' register is found!");
92 #endif
93  continue;
94  }
95  for (const MachineInstr &Use : MRI->use_nodbg_instructions(Reg)) {
96  if (&Use != MI)
97  // This def has a non-debug use. Don't delete the instruction!
98  return false;
99  }
100  }
101  }
102  }
103 
104  // If there are no defs with uses, the instruction is dead.
105  return true;
106 }
107 
108 bool DeadMachineInstructionElim::runOnMachineFunction(MachineFunction &MF) {
109  if (skipFunction(MF.getFunction()))
110  return false;
111  bool AnyChanges = eliminateDeadMI(MF);
112  while (AnyChanges && eliminateDeadMI(MF))
113  ;
114  return AnyChanges;
115 }
116 
117 bool DeadMachineInstructionElim::eliminateDeadMI(MachineFunction &MF) {
118  bool AnyChanges = false;
119  MRI = &MF.getRegInfo();
121  TII = MF.getSubtarget().getInstrInfo();
122 
123  // Loop over all instructions in all blocks, from bottom to top, so that it's
124  // more likely that chains of dependent but ultimately dead instructions will
125  // be cleaned up.
126  for (MachineBasicBlock *MBB : post_order(&MF)) {
127  // Start out assuming that reserved registers are live out of this block.
129 
130  // Add live-ins from successors to LivePhysRegs. Normally, physregs are not
131  // live across blocks, but some targets (x86) can have flags live out of a
132  // block.
133  for (const MachineBasicBlock *Succ : MBB->successors())
134  for (const auto &LI : Succ->liveins())
135  LivePhysRegs.set(LI.PhysReg);
136 
137  // Now scan the instructions and delete dead ones, tracking physreg
138  // liveness as we go.
140  // If the instruction is dead, delete it!
141  if (isDead(&MI)) {
142  LLVM_DEBUG(dbgs() << "DeadMachineInstructionElim: DELETING: " << MI);
143  // It is possible that some DBG_VALUE instructions refer to this
144  // instruction. They will be deleted in the live debug variable
145  // analysis.
146  MI.eraseFromParent();
147  AnyChanges = true;
148  ++NumDeletes;
149  continue;
150  }
151 
152  // Record the physreg defs.
153  for (const MachineOperand &MO : MI.operands()) {
154  if (MO.isReg() && MO.isDef()) {
155  Register Reg = MO.getReg();
157  // Check the subreg set, not the alias set, because a def
158  // of a super-register may still be partially live after
159  // this def.
160  for (MCSubRegIterator SR(Reg, TRI,/*IncludeSelf=*/true);
161  SR.isValid(); ++SR)
162  LivePhysRegs.reset(*SR);
163  }
164  } else if (MO.isRegMask()) {
165  // Register mask of preserved registers. All clobbers are dead.
166  LivePhysRegs.clearBitsNotInMask(MO.getRegMask());
167  }
168  }
169  // Record the physreg uses, after the defs, in case a physreg is
170  // both defined and used in the same instruction.
171  for (const MachineOperand &MO : MI.operands()) {
172  if (MO.isReg() && MO.isUse()) {
173  Register Reg = MO.getReg();
175  for (MCRegAliasIterator AI(Reg, TRI, true); AI.isValid(); ++AI)
176  LivePhysRegs.set(*AI);
177  }
178  }
179  }
180  }
181  }
182 
184  return AnyChanges;
185 }
MI
IRTranslator LLVM IR MI
Definition: IRTranslator.cpp:104
llvm
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:17
llvm::initializeDeadMachineInstructionElimPass
void initializeDeadMachineInstructionElimPass(PassRegistry &)
llvm::MachineRegisterInfo
MachineRegisterInfo - Keep track of information for virtual and physical registers,...
Definition: MachineRegisterInfo.h:50
Pass.h
llvm::TargetSubtargetInfo::getInstrInfo
virtual const TargetInstrInfo * getInstrInfo() const
Definition: TargetSubtargetInfo.h:93
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::TargetSubtargetInfo::getRegisterInfo
virtual const TargetRegisterInfo * getRegisterInfo() const
getRegisterInfo - If register information is available, return it.
Definition: TargetSubtargetInfo.h:125
llvm::MachineRegisterInfo::use_nodbg_instructions
iterator_range< use_instr_nodbg_iterator > use_nodbg_instructions(Register Reg) const
Definition: MachineRegisterInfo.h:551
llvm::TargetRegisterInfo
TargetRegisterInfo base class - We assume that the target defines a static array of TargetRegisterDes...
Definition: TargetRegisterInfo.h:234
llvm::reverse
auto reverse(ContainerTy &&C, std::enable_if_t< has_rbegin< ContainerTy >::value > *=nullptr)
Definition: STLExtras.h:380
TRI
unsigned const TargetRegisterInfo * TRI
Definition: MachineSink.cpp:1628
llvm::MachineFunctionPass::getAnalysisUsage
void getAnalysisUsage(AnalysisUsage &AU) const override
getAnalysisUsage - Subclasses that override getAnalysisUsage must call this.
Definition: MachineFunctionPass.cpp:103
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:666
llvm::TargetInstrInfo
TargetInstrInfo - Interface to description of machine instruction set.
Definition: TargetInstrInfo.h:97
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:31
llvm::MachineRegisterInfo::isReserved
bool isReserved(MCRegister PhysReg) const
isReserved - Returns true when PhysReg is a reserved register.
Definition: MachineRegisterInfo.h:925
llvm::Register::isPhysicalRegister
static bool isPhysicalRegister(unsigned Reg)
Return true if the specified register number is in the physical register namespace.
Definition: Register.h:65
llvm::AnalysisUsage
Represent the analysis usage information of a pass.
Definition: PassAnalysisSupport.h:47
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::BitVector
Definition: BitVector.h:75
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:656
llvm::MachineInstr
Representation of each machine instruction.
Definition: MachineInstr.h:66
const
aarch64 promote const
Definition: AArch64PromoteConstant.cpp:232
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:618
MachineFunctionPass.h
assert
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
llvm::MachineFunction
Definition: MachineFunction.h:257
llvm::MachineBasicBlock::successors
iterator_range< succ_iterator > successors()
Definition: MachineBasicBlock.h:365
llvm::AnalysisUsage::setPreservesCFG
void setPreservesCFG()
This function should be called by the pass, iff they do not:
Definition: Pass.cpp:263
DEBUG_TYPE
#define DEBUG_TYPE
Definition: DeadMachineInstructionElim.cpp:25
TargetSubtargetInfo.h
llvm::MachineRegisterInfo::getReservedRegs
const BitVector & getReservedRegs() const
getReservedRegs - Returns a reference to the frozen set of reserved registers.
Definition: MachineRegisterInfo.h:914
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:622
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
llvm::MCSubRegIterator
MCSubRegIterator enumerates all sub-registers of Reg.
Definition: MCRegisterInfo.h:597
llvm::MCRegAliasIterator::isValid
bool isValid() const
Definition: MCRegisterInfo.h:813
PostOrderIterator.h
llvm::LivePhysRegs::clear
void clear()
Clears the set.
Definition: LivePhysRegs.h:75
llvm::MCRegisterInfo::DiffListIterator::isValid
bool isValid() const
isValid - returns true if this iterator is not yet at the end.
Definition: MCRegisterInfo.h:224
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::MCRegAliasIterator
MCRegAliasIterator enumerates all registers aliasing Reg.
Definition: MCRegisterInfo.h:788
llvm::Use
A Use represents the edge between a Value definition and its users.
Definition: Use.h:43
llvm::Intrinsic::ID
unsigned ID
Definition: TargetTransformInfo.h:38