LLVM  10.0.0svn
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 
13 #include "llvm/ADT/Statistic.h"
16 #include "llvm/CodeGen/Passes.h"
18 #include "llvm/Pass.h"
19 #include "llvm/Support/Debug.h"
21 
22 using namespace llvm;
23 
24 #define DEBUG_TYPE "dead-mi-elimination"
25 
26 STATISTIC(NumDeletes, "Number of dead instructions deleted");
27 
28 namespace {
29  class DeadMachineInstructionElim : public MachineFunctionPass {
30  bool runOnMachineFunction(MachineFunction &MF) override;
31 
32  const TargetRegisterInfo *TRI;
33  const MachineRegisterInfo *MRI;
34  const TargetInstrInfo *TII;
36 
37  public:
38  static char ID; // Pass identification, replacement for typeid
39  DeadMachineInstructionElim() : MachineFunctionPass(ID) {
41  }
42 
43  void getAnalysisUsage(AnalysisUsage &AU) const override {
44  AU.setPreservesCFG();
46  }
47 
48  private:
49  bool isDead(const MachineInstr *MI) const;
50  };
51 }
54 
55 INITIALIZE_PASS(DeadMachineInstructionElim, DEBUG_TYPE,
56  "Remove dead machine instructions", false, false)
57 
58 bool DeadMachineInstructionElim::isDead(const MachineInstr *MI) const {
59  // Technically speaking inline asm without side effects and no defs can still
60  // be deleted. But there is so much bad inline asm code out there, we should
61  // let them be.
62  if (MI->isInlineAsm())
63  return false;
64 
65  // Don't delete frame allocation labels.
66  if (MI->getOpcode() == TargetOpcode::LOCAL_ESCAPE)
67  return false;
68 
69  // Don't delete instructions with side effects.
70  bool SawStore = false;
71  if (!MI->isSafeToMove(nullptr, SawStore) && !MI->isPHI())
72  return false;
73 
74  // Examine each operand.
75  for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
76  const MachineOperand &MO = MI->getOperand(i);
77  if (MO.isReg() && MO.isDef()) {
78  unsigned Reg = MO.getReg();
80  // Don't delete live physreg defs, or any reserved register defs.
81  if (LivePhysRegs.test(Reg) || MRI->isReserved(Reg))
82  return false;
83  } else {
84  for (const MachineInstr &Use : MRI->use_nodbg_instructions(Reg)) {
85  if (&Use != MI)
86  // This def has a non-debug use. Don't delete the instruction!
87  return false;
88  }
89  }
90  }
91  }
92 
93  // If there are no defs with uses, the instruction is dead.
94  return true;
95 }
96 
97 bool DeadMachineInstructionElim::runOnMachineFunction(MachineFunction &MF) {
98  if (skipFunction(MF.getFunction()))
99  return false;
100 
101  bool AnyChanges = false;
102  MRI = &MF.getRegInfo();
103  TRI = MF.getSubtarget().getRegisterInfo();
104  TII = MF.getSubtarget().getInstrInfo();
105 
106  // Loop over all instructions in all blocks, from bottom to top, so that it's
107  // more likely that chains of dependent but ultimately dead instructions will
108  // be cleaned up.
109  for (MachineBasicBlock &MBB : make_range(MF.rbegin(), MF.rend())) {
110  // Start out assuming that reserved registers are live out of this block.
111  LivePhysRegs = MRI->getReservedRegs();
112 
113  // Add live-ins from successors to LivePhysRegs. Normally, physregs are not
114  // live across blocks, but some targets (x86) can have flags live out of a
115  // block.
116  for (MachineBasicBlock::succ_iterator S = MBB.succ_begin(),
117  E = MBB.succ_end(); S != E; S++)
118  for (const auto &LI : (*S)->liveins())
119  LivePhysRegs.set(LI.PhysReg);
120 
121  // Now scan the instructions and delete dead ones, tracking physreg
122  // liveness as we go.
123  for (MachineBasicBlock::reverse_iterator MII = MBB.rbegin(),
124  MIE = MBB.rend(); MII != MIE; ) {
125  MachineInstr *MI = &*MII++;
126 
127  // If the instruction is dead, delete it!
128  if (isDead(MI)) {
129  LLVM_DEBUG(dbgs() << "DeadMachineInstructionElim: DELETING: " << *MI);
130  // It is possible that some DBG_VALUE instructions refer to this
131  // instruction. They get marked as undef and will be deleted
132  // in the live debug variable analysis.
134  AnyChanges = true;
135  ++NumDeletes;
136  continue;
137  }
138 
139  // Record the physreg defs.
140  for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
141  const MachineOperand &MO = MI->getOperand(i);
142  if (MO.isReg() && MO.isDef()) {
143  unsigned Reg = MO.getReg();
145  // Check the subreg set, not the alias set, because a def
146  // of a super-register may still be partially live after
147  // this def.
148  for (MCSubRegIterator SR(Reg, TRI,/*IncludeSelf=*/true);
149  SR.isValid(); ++SR)
150  LivePhysRegs.reset(*SR);
151  }
152  } else if (MO.isRegMask()) {
153  // Register mask of preserved registers. All clobbers are dead.
154  LivePhysRegs.clearBitsNotInMask(MO.getRegMask());
155  }
156  }
157  // Record the physreg uses, after the defs, in case a physreg is
158  // both defined and used in the same instruction.
159  for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
160  const MachineOperand &MO = MI->getOperand(i);
161  if (MO.isReg() && MO.isUse()) {
162  unsigned Reg = MO.getReg();
164  for (MCRegAliasIterator AI(Reg, TRI, true); AI.isValid(); ++AI)
165  LivePhysRegs.set(*AI);
166  }
167  }
168  }
169  }
170  }
171 
172  LivePhysRegs.clear();
173  return AnyChanges;
174 }
bool isRegMask() const
isRegMask - Tests if this is a MO_RegisterMask operand.
BitVector & set()
Definition: BitVector.h:397
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
This class represents lattice values for constants.
Definition: AllocatorList.h:23
virtual const TargetRegisterInfo * getRegisterInfo() const
getRegisterInfo - If register information is available, return it.
unsigned Reg
bool test(unsigned Idx) const
Definition: BitVector.h:501
STATISTIC(NumFunctions, "Total number of functions")
unsigned const TargetRegisterInfo * TRI
#define DEBUG_TYPE
void clear()
clear - Removes all bits from the bitvector. Does not change capacity.
Definition: BitVector.h:366
MachineFunctionPass - This class adapts the FunctionPass interface to allow convenient creation of pa...
const HexagonInstrInfo * TII
unsigned getNumOperands() const
Retuns the total number of operands.
Definition: MachineInstr.h:414
A Use represents the edge between a Value definition and its users.
Definition: Use.h:55
MachineBasicBlock iterator that automatically skips over MIs that are inside bundles (i...
void eraseFromParentAndMarkDBGValuesForRemoval()
Unlink &#39;this&#39; from the containing basic block and delete it.
char & DeadMachineInstructionElimID
DeadMachineInstructionElim - This pass removes dead machine instructions.
virtual const TargetInstrInfo * getInstrInfo() const
TargetInstrInfo - Interface to description of machine instruction set.
void clearBitsNotInMask(const uint32_t *Mask, unsigned MaskWords=~0u)
clearBitsNotInMask - Clear a bit in this vector for every &#39;0&#39; bit in Mask.
Definition: BitVector.h:793
unsigned const MachineRegisterInfo * MRI
const TargetSubtargetInfo & getSubtarget() const
getSubtarget - Return the subtarget for which this machine code is being compiled.
void getAnalysisUsage(AnalysisUsage &AU) const override
getAnalysisUsage - Subclasses that override getAnalysisUsage must call this.
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
void initializeDeadMachineInstructionElimPass(PassRegistry &)
MCRegAliasIterator enumerates all registers aliasing Reg.
Represent the analysis usage information of a pass.
BitVector & reset()
Definition: BitVector.h:438
TargetRegisterInfo base class - We assume that the target defines a static array of TargetRegisterDes...
MCSubRegIterator enumerates all sub-registers of Reg.
iterator_range< T > make_range(T x, T y)
Convenience function for iterating over sub-ranges.
MachineOperand class - Representation of each machine instruction operand.
void setPreservesCFG()
This function should be called by the pass, iff they do not:
Definition: Pass.cpp:301
const Function & getFunction() const
Return the LLVM function that this machine code represents.
reverse_iterator rend()
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:132
const uint32_t * getRegMask() const
getRegMask - Returns a bit mask of registers preserved by this RegMask operand.
bool isValid() const
isValid - returns true if this iterator is not yet at the end.
const BitVector & getReservedRegs() const
getReservedRegs - Returns a reference to the frozen set of reserved registers.
MachineRegisterInfo - Keep track of information for virtual and physical registers, including vreg register classes, use/def chains for registers, etc.
Representation of each machine instruction.
Definition: MachineInstr.h:64
static bool isPhysicalRegister(unsigned Reg)
Return true if the specified register number is in the physical register namespace.
MachineRegisterInfo & getRegInfo()
getRegInfo - Return information about the registers currently in use.
A set of physical registers with utility functions to track liveness when walking backward/forward th...
Definition: LivePhysRegs.h:48
bool isReg() const
isReg - Tests if this is a MO_Register operand.
aarch64 promote const
IRTranslator LLVM IR MI
Register getReg() const
getReg - Returns the register number.
#define LLVM_DEBUG(X)
Definition: Debug.h:122
const MachineOperand & getOperand(unsigned i) const
Definition: MachineInstr.h:416
iterator_range< use_instr_nodbg_iterator > use_nodbg_instructions(unsigned Reg) const
reverse_iterator rbegin()
std::vector< MachineBasicBlock * >::iterator succ_iterator
INITIALIZE_PASS(DeadMachineInstructionElim, DEBUG_TYPE, "Remove dead machine instructions", false, false) bool DeadMachineInstructionElim
bool isReserved(unsigned PhysReg) const
isReserved - Returns true when PhysReg is a reserved register.