LLVM  6.0.0svn
DeadMachineInstructionElim.cpp
Go to the documentation of this file.
1 //===- DeadMachineInstructionElim.cpp - Remove dead machine instructions --===//
2 //
3 // The LLVM Compiler Infrastructure
4 //
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
7 //
8 //===----------------------------------------------------------------------===//
9 //
10 // This is an extremely simple MachineInstr-level dead-code-elimination pass.
11 //
12 //===----------------------------------------------------------------------===//
13 
14 #include "llvm/ADT/Statistic.h"
17 #include "llvm/CodeGen/Passes.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 }
56 
57 INITIALIZE_PASS(DeadMachineInstructionElim, DEBUG_TYPE,
58  "Remove dead machine instructions", false, false)
59 
60 bool DeadMachineInstructionElim::isDead(const MachineInstr *MI) const {
61  // Technically speaking inline asm without side effects and no defs can still
62  // be deleted. But there is so much bad inline asm code out there, we should
63  // let them be.
64  if (MI->isInlineAsm())
65  return false;
66 
67  // Don't delete frame allocation labels.
68  if (MI->getOpcode() == TargetOpcode::LOCAL_ESCAPE)
69  return false;
70 
71  // Don't delete instructions with side effects.
72  bool SawStore = false;
73  if (!MI->isSafeToMove(nullptr, SawStore) && !MI->isPHI())
74  return false;
75 
76  // Examine each operand.
77  for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
78  const MachineOperand &MO = MI->getOperand(i);
79  if (MO.isReg() && MO.isDef()) {
80  unsigned 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 (!MRI->use_nodbg_empty(Reg))
87  // This def has a non-debug use. Don't delete the instruction!
88  return false;
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  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:398
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
bool use_nodbg_empty(unsigned RegNo) const
use_nodbg_empty - Return true if there are no non-Debug instructions using the specified register...
Compute iterated dominance frontiers using a linear time algorithm.
Definition: AllocatorList.h:24
virtual const TargetRegisterInfo * getRegisterInfo() const
getRegisterInfo - If register information is available, return it.
unsigned getReg() const
getReg - Returns the register number.
bool test(unsigned Idx) const
Definition: BitVector.h:502
STATISTIC(NumFunctions, "Total number of functions")
#define DEBUG_TYPE
void clear()
clear - Removes all bits from the bitvector. Does not change capacity.
Definition: BitVector.h:367
MachineFunctionPass - This class adapts the FunctionPass interface to allow convenient creation of pa...
const HexagonInstrInfo * TII
unsigned getNumOperands() const
Access to explicit operands of the instruction.
Definition: MachineInstr.h:293
MachineBasicBlock iterator that automatically skips over MIs that are inside bundles (i...
Reg
All possible values of the reg field in the ModR/M byte.
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:777
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:439
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:285
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:59
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:49
bool isReg() const
isReg - Tests if this is a MO_Register operand.
const Function * getFunction() const
getFunction - Return the LLVM function that this machine code represents
aarch64 promote const
#define DEBUG(X)
Definition: Debug.h:118
IRTranslator LLVM IR MI
const MachineOperand & getOperand(unsigned i) const
Definition: MachineInstr.h:295
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.