DeadMachineInstructionElim.cpp revision cddc3e03e4ec99c0268c03a126195173e519ed58 
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/CodeGen/Passes.h"
15#include "llvm/ADT/Statistic.h"
16#include "llvm/CodeGen/MachineFunctionPass.h"
17#include "llvm/CodeGen/MachineRegisterInfo.h"
18#include "llvm/Pass.h"
19#include "llvm/Support/Debug.h"
20#include "llvm/Support/raw_ostream.h"
21#include "llvm/Target/TargetInstrInfo.h"
22#include "llvm/Target/TargetSubtargetInfo.h"
23
24using namespace llvm;
25
26#define DEBUG_TYPE "codegen-dce"
27
28STATISTIC(NumDeletes,          "Number of dead instructions deleted");
29
30namespace {
31  class DeadMachineInstructionElim : public MachineFunctionPass {
32    bool runOnMachineFunction(MachineFunction &MF) override;
33
34    const TargetRegisterInfo *TRI;
35    const MachineRegisterInfo *MRI;
36    const TargetInstrInfo *TII;
37    BitVector LivePhysRegs;
38
39  public:
40    static char ID; // Pass identification, replacement for typeid
41    DeadMachineInstructionElim() : MachineFunctionPass(ID) {
42     initializeDeadMachineInstructionElimPass(*PassRegistry::getPassRegistry());
43    }
44
45  private:
46    bool isDead(const MachineInstr *MI) const;
47  };
48}
49char DeadMachineInstructionElim::ID = 0;
50char &llvm::DeadMachineInstructionElimID = DeadMachineInstructionElim::ID;
51
52INITIALIZE_PASS(DeadMachineInstructionElim, "dead-mi-elimination",
53                "Remove dead machine instructions", false, false)
54
55bool DeadMachineInstructionElim::isDead(const MachineInstr *MI) const {
56  // Technically speaking inline asm without side effects and no defs can still
57  // be deleted. But there is so much bad inline asm code out there, we should
58  // let them be.
59  if (MI->isInlineAsm())
60    return false;
61
62  // Don't delete frame allocation labels.
63  if (MI->getOpcode() == TargetOpcode::LOCAL_ESCAPE)
64    return false;
65
66  // Don't delete instructions with side effects.
67  bool SawStore = false;
68  if (!MI->isSafeToMove(nullptr, SawStore) && !MI->isPHI())
69    return false;
70
71  // Examine each operand.
72  for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
73    const MachineOperand &MO = MI->getOperand(i);
74    if (MO.isReg() && MO.isDef()) {
75      unsigned Reg = MO.getReg();
76      if (TargetRegisterInfo::isPhysicalRegister(Reg)) {
77        // Don't delete live physreg defs, or any reserved register defs.
78        if (LivePhysRegs.test(Reg) || MRI->isReserved(Reg))
79          return false;
80      } else {
81        if (!MRI->use_nodbg_empty(Reg))
82          // This def has a non-debug use. Don't delete the instruction!
83          return false;
84      }
85    }
86  }
87
88  // If there are no defs with uses, the instruction is dead.
89  return true;
90}
91
92bool DeadMachineInstructionElim::runOnMachineFunction(MachineFunction &MF) {
93  if (skipOptnoneFunction(*MF.getFunction()))
94    return false;
95
96  bool AnyChanges = false;
97  MRI = &MF.getRegInfo();
98  TRI = MF.getSubtarget().getRegisterInfo();
99  TII = MF.getSubtarget().getInstrInfo();
100
101  // Loop over all instructions in all blocks, from bottom to top, so that it's
102  // more likely that chains of dependent but ultimately dead instructions will
103  // be cleaned up.
104  for (MachineBasicBlock &MBB : make_range(MF.rbegin(), MF.rend())) {
105    // Start out assuming that reserved registers are live out of this block.
106    LivePhysRegs = MRI->getReservedRegs();
107
108    // Add live-ins from sucessors to LivePhysRegs. Normally, physregs are not
109    // live across blocks, but some targets (x86) can have flags live out of a
110    // block.
111    for (MachineBasicBlock::succ_iterator S = MBB.succ_begin(),
112           E = MBB.succ_end(); S != E; S++)
113      for (const auto &LI : (*S)->liveins())
114        LivePhysRegs.set(LI.PhysReg);
115
116    // Now scan the instructions and delete dead ones, tracking physreg
117    // liveness as we go.
118    for (MachineBasicBlock::reverse_iterator MII = MBB.rbegin(),
119         MIE = MBB.rend(); MII != MIE; ) {
120      MachineInstr *MI = &*MII;
121
122      // If the instruction is dead, delete it!
123      if (isDead(MI)) {
124        DEBUG(dbgs() << "DeadMachineInstructionElim: DELETING: " << *MI);
125        // It is possible that some DBG_VALUE instructions refer to this
126        // instruction.  They get marked as undef and will be deleted
127        // in the live debug variable analysis.
128        MI->eraseFromParentAndMarkDBGValuesForRemoval();
129        AnyChanges = true;
130        ++NumDeletes;
131        MIE = MBB.rend();
132        // MII is now pointing to the next instruction to process,
133        // so don't increment it.
134        continue;
135      }
136
137      // Record the physreg defs.
138      for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
139        const MachineOperand &MO = MI->getOperand(i);
140        if (MO.isReg() && MO.isDef()) {
141          unsigned Reg = MO.getReg();
142          if (TargetRegisterInfo::isPhysicalRegister(Reg)) {
143            // Check the subreg set, not the alias set, because a def
144            // of a super-register may still be partially live after
145            // this def.
146            for (MCSubRegIterator SR(Reg, TRI,/*IncludeSelf=*/true);
147                 SR.isValid(); ++SR)
148              LivePhysRegs.reset(*SR);
149          }
150        } else if (MO.isRegMask()) {
151          // Register mask of preserved registers. All clobbers are dead.
152          LivePhysRegs.clearBitsNotInMask(MO.getRegMask());
153        }
154      }
155      // Record the physreg uses, after the defs, in case a physreg is
156      // both defined and used in the same instruction.
157      for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
158        const MachineOperand &MO = MI->getOperand(i);
159        if (MO.isReg() && MO.isUse()) {
160          unsigned Reg = MO.getReg();
161          if (TargetRegisterInfo::isPhysicalRegister(Reg)) {
162            for (MCRegAliasIterator AI(Reg, TRI, true); AI.isValid(); ++AI)
163              LivePhysRegs.set(*AI);
164          }
165        }
166      }
167
168      // We didn't delete the current instruction, so increment MII to
169      // the next one.
170      ++MII;
171    }
172  }
173
174  LivePhysRegs.clear();
175  return AnyChanges;
176}
177