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