LLVM  14.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"
17 #include "llvm/CodeGen/Passes.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 TargetRegisterInfo *TRI;
35  const MachineRegisterInfo *MRI;
36  const TargetInstrInfo *TII;
38 
39  public:
40  static char ID; // Pass identification, replacement for typeid
41  DeadMachineInstructionElim() : MachineFunctionPass(ID) {
43  }
44 
45  void getAnalysisUsage(AnalysisUsage &AU) const override {
46  AU.setPreservesCFG();
48  }
49 
50  private:
51  bool isDead(const MachineInstr *MI) const;
52 
53  bool eliminateDeadMI(MachineFunction &MF);
54  };
55 }
58 
59 INITIALIZE_PASS(DeadMachineInstructionElim, DEBUG_TYPE,
60  "Remove dead machine instructions", false, false)
61 
62 bool DeadMachineInstructionElim::isDead(const MachineInstr *MI) const {
63  // Technically speaking inline asm without side effects and no defs can still
64  // be deleted. But there is so much bad inline asm code out there, we should
65  // let them be.
66  if (MI->isInlineAsm())
67  return false;
68 
69  // Don't delete frame allocation labels.
70  if (MI->getOpcode() == TargetOpcode::LOCAL_ESCAPE)
71  return false;
72 
73  // Don't delete instructions with side effects.
74  bool SawStore = false;
75  if (!MI->isSafeToMove(nullptr, SawStore) && !MI->isPHI())
76  return false;
77 
78  // Examine each operand.
79  for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
80  const MachineOperand &MO = MI->getOperand(i);
81  if (MO.isReg() && MO.isDef()) {
82  Register Reg = MO.getReg();
84  // Don't delete live physreg defs, or any reserved register defs.
85  if (LivePhysRegs.test(Reg) || MRI->isReserved(Reg))
86  return false;
87  } else {
88  if (MO.isDead()) {
89 #ifndef NDEBUG
90  // Sanity check on uses of this dead register. All of them should be
91  // 'undef'.
92  for (auto &U : MRI->use_nodbg_operands(Reg))
93  assert(U.isUndef() && "'Undef' use on a 'dead' register is found!");
94 #endif
95  continue;
96  }
97  for (const MachineInstr &Use : MRI->use_nodbg_instructions(Reg)) {
98  if (&Use != MI)
99  // This def has a non-debug use. Don't delete the instruction!
100  return false;
101  }
102  }
103  }
104  }
105 
106  // If there are no defs with uses, the instruction is dead.
107  return true;
108 }
109 
110 bool DeadMachineInstructionElim::runOnMachineFunction(MachineFunction &MF) {
111  if (skipFunction(MF.getFunction()))
112  return false;
113  bool AnyChanges = eliminateDeadMI(MF);
114  while (AnyChanges && eliminateDeadMI(MF))
115  ;
116  return AnyChanges;
117 }
118 
119 bool DeadMachineInstructionElim::eliminateDeadMI(MachineFunction &MF) {
120  bool AnyChanges = false;
121  MRI = &MF.getRegInfo();
123  TII = MF.getSubtarget().getInstrInfo();
124 
125  // Loop over all instructions in all blocks, from bottom to top, so that it's
126  // more likely that chains of dependent but ultimately dead instructions will
127  // be cleaned up.
128  for (MachineBasicBlock *MBB : post_order(&MF)) {
129  // Start out assuming that reserved registers are live out of this block.
131 
132  // Add live-ins from successors to LivePhysRegs. Normally, physregs are not
133  // live across blocks, but some targets (x86) can have flags live out of a
134  // block.
135  for (const MachineBasicBlock *Succ : MBB->successors())
136  for (const auto &LI : Succ->liveins())
137  LivePhysRegs.set(LI.PhysReg);
138 
139  // Now scan the instructions and delete dead ones, tracking physreg
140  // liveness as we go.
142  MIE = MBB->rend();
143  MII != MIE;) {
144  MachineInstr *MI = &*MII++;
145 
146  // If the instruction is dead, delete it!
147  if (isDead(MI)) {
148  LLVM_DEBUG(dbgs() << "DeadMachineInstructionElim: DELETING: " << *MI);
149  // It is possible that some DBG_VALUE instructions refer to this
150  // instruction. They get marked as undef and will be deleted
151  // in the live debug variable analysis.
152  MI->eraseFromParentAndMarkDBGValuesForRemoval();
153  AnyChanges = true;
154  ++NumDeletes;
155  continue;
156  }
157 
158  // Record the physreg defs.
159  for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
160  const MachineOperand &MO = MI->getOperand(i);
161  if (MO.isReg() && MO.isDef()) {
162  Register Reg = MO.getReg();
164  // Check the subreg set, not the alias set, because a def
165  // of a super-register may still be partially live after
166  // this def.
167  for (MCSubRegIterator SR(Reg, TRI,/*IncludeSelf=*/true);
168  SR.isValid(); ++SR)
169  LivePhysRegs.reset(*SR);
170  }
171  } else if (MO.isRegMask()) {
172  // Register mask of preserved registers. All clobbers are dead.
173  LivePhysRegs.clearBitsNotInMask(MO.getRegMask());
174  }
175  }
176  // Record the physreg uses, after the defs, in case a physreg is
177  // both defined and used in the same instruction.
178  for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
179  const MachineOperand &MO = MI->getOperand(i);
180  if (MO.isReg() && MO.isUse()) {
181  Register Reg = MO.getReg();
183  for (MCRegAliasIterator AI(Reg, TRI, true); AI.isValid(); ++AI)
184  LivePhysRegs.set(*AI);
185  }
186  }
187  }
188  }
189  }
190 
192  return AnyChanges;
193 }
i
i
Definition: README.txt:29
MI
IRTranslator LLVM IR MI
Definition: IRTranslator.cpp:105
llvm
This file implements support for optimizing divisions by a constant.
Definition: AllocatorList.h:23
Reg
unsigned Reg
Definition: MachineSink.cpp:1566
llvm::initializeDeadMachineInstructionElimPass
void initializeDeadMachineInstructionElimPass(PassRegistry &)
llvm::MachineRegisterInfo
MachineRegisterInfo - Keep track of information for virtual and physical registers,...
Definition: MachineRegisterInfo.h:52
Pass.h
llvm::TargetSubtargetInfo::getInstrInfo
virtual const TargetInstrInfo * getInstrInfo() const
Definition: TargetSubtargetInfo.h:92
Statistic.h
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:48
llvm::TargetSubtargetInfo::getRegisterInfo
virtual const TargetRegisterInfo * getRegisterInfo() const
getRegisterInfo - If register information is available, return it.
Definition: TargetSubtargetInfo.h:124
llvm::MachineRegisterInfo::use_nodbg_instructions
iterator_range< use_instr_nodbg_iterator > use_nodbg_instructions(Register Reg) const
Definition: MachineRegisterInfo.h:543
llvm::TargetRegisterInfo
TargetRegisterInfo base class - We assume that the target defines a static array of TargetRegisterDes...
Definition: TargetRegisterInfo.h:233
TRI
unsigned const TargetRegisterInfo * TRI
Definition: MachineSink.cpp:1567
llvm::MachineFunctionPass::getAnalysisUsage
void getAnalysisUsage(AnalysisUsage &AU) const override
getAnalysisUsage - Subclasses that override getAnalysisUsage must call this.
Definition: MachineFunctionPass.cpp:102
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:640
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:526
llvm::PassRegistry::getPassRegistry
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
Definition: PassRegistry.cpp:31
llvm::MachineOperand::isUse
bool isUse() const
Definition: MachineOperand.h:370
llvm::MachineRegisterInfo::isReserved
bool isReserved(MCRegister PhysReg) const
isReserved - Returns true when PhysReg is a reserved register.
Definition: MachineRegisterInfo.h:928
llvm::MachineOperand::getRegMask
const uint32_t * getRegMask() const
getRegMask - Returns a bit mask of registers preserved by this RegMask operand.
Definition: MachineOperand.h:630
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:129
llvm::MachineOperand
MachineOperand class - Representation of each machine instruction operand.
Definition: MachineOperand.h:49
llvm::MachineBasicBlock::rend
reverse_iterator rend()
Definition: MachineBasicBlock.h:278
llvm::STATISTIC
STATISTIC(NumFunctions, "Total number of functions")
llvm::BitVector
Definition: BitVector.h:74
llvm::MachineBasicBlock
Definition: MachineBasicBlock.h:95
Passes.h
llvm::MachineFunction::getSubtarget
const TargetSubtargetInfo & getSubtarget() const
getSubtarget - Return the subtarget for which this machine code is being compiled.
Definition: MachineFunction.h:630
llvm::MachineOperand::isReg
bool isReg() const
isReg - Tests if this is a MO_Register operand.
Definition: MachineOperand.h:321
llvm::MachineInstr
Representation of each machine instruction.
Definition: MachineInstr.h:64
const
aarch64 promote const
Definition: AArch64PromoteConstant.cpp:232
llvm::numbers::e
constexpr double e
Definition: MathExtras.h:57
llvm::MachineOperand::isDead
bool isDead() const
Definition: MachineOperand.h:385
MachineFunctionPass.h
assert
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
llvm::MachineOperand::isRegMask
bool isRegMask() const
isRegMask - Tests if this is a MO_RegisterMask operand.
Definition: MachineOperand.h:345
llvm::MachineOperand::getReg
Register getReg() const
getReg - Returns the register number.
Definition: MachineOperand.h:360
llvm::MachineFunction
Definition: MachineFunction.h:234
llvm::MachineBasicBlock::successors
iterator_range< succ_iterator > successors()
Definition: MachineBasicBlock.h:355
llvm::AnalysisUsage::setPreservesCFG
void setPreservesCFG()
This function should be called by the pass, iff they do not:
Definition: Pass.cpp:253
llvm::MachineBasicBlock::rbegin
reverse_iterator rbegin()
Definition: MachineBasicBlock.h:272
DEBUG_TYPE
#define DEBUG_TYPE
Definition: DeadMachineInstructionElim.cpp:26
TargetSubtargetInfo.h
llvm::MachineOperand::isDef
bool isDef() const
Definition: MachineOperand.h:375
llvm::MachineRegisterInfo::getReservedRegs
const BitVector & getReservedRegs() const
getReservedRegs - Returns a reference to the frozen set of reserved registers.
Definition: MachineRegisterInfo.h:917
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:596
llvm::post_order
iterator_range< po_iterator< T > > post_order(const T &G)
Definition: PostOrderIterator.h:188
llvm::DeadMachineInstructionElimID
char & DeadMachineInstructionElimID
DeadMachineInstructionElim - This pass removes dead machine instructions.
Definition: DeadMachineInstructionElim.cpp:57
llvm::MCSubRegIterator
MCSubRegIterator enumerates all sub-registers of Reg.
Definition: MCRegisterInfo.h:594
llvm::MCRegAliasIterator::isValid
bool isValid() const
Definition: MCRegisterInfo.h:805
PostOrderIterator.h
llvm::LivePhysRegs::clear
void clear()
Clears the set.
Definition: LivePhysRegs.h:73
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:59
raw_ostream.h
llvm::MachineInstrBundleIterator
MachineBasicBlock iterator that automatically skips over MIs that are inside bundles (i....
Definition: MachineInstrBundleIterator.h:108
InitializePasses.h
Debug.h
llvm::MCRegAliasIterator
MCRegAliasIterator enumerates all registers aliasing Reg.
Definition: MCRegisterInfo.h:780
llvm::Use
A Use represents the edge between a Value definition and its users.
Definition: Use.h:44
llvm::Intrinsic::ID
unsigned ID
Definition: TargetTransformInfo.h:37