DeadMachineInstructionElim.cpp revision d9e1fc71d8d656e3eb8aa1cc4765ba09d5392fd2
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
37  public:
38    static char ID; // Pass identification, replacement for typeid
39    DeadMachineInstructionElim() : MachineFunctionPass(ID) {}
40
41  private:
42    bool isDead(const MachineInstr *MI) const;
43  };
44}
45char DeadMachineInstructionElim::ID = 0;
46
47INITIALIZE_PASS(DeadMachineInstructionElim, "dead-mi-elimination",
48                "Remove dead machine instructions", false, false);
49
50FunctionPass *llvm::createDeadMachineInstructionElimPass() {
51  return new DeadMachineInstructionElim();
52}
53
54bool DeadMachineInstructionElim::isDead(const MachineInstr *MI) const {
55  // Don't delete instructions with side effects.
56  bool SawStore = false;
57  if (!MI->isSafeToMove(TII, 0, SawStore) && !MI->isPHI())
58    return false;
59
60  // Examine each operand.
61  for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
62    const MachineOperand &MO = MI->getOperand(i);
63    if (MO.isReg() && MO.isDef()) {
64      unsigned Reg = MO.getReg();
65      if (TargetRegisterInfo::isPhysicalRegister(Reg) ?
66          LivePhysRegs[Reg] : !MRI->use_nodbg_empty(Reg)) {
67        // This def has a non-debug use. Don't delete the instruction!
68        return false;
69      }
70    }
71  }
72
73  // If there are no defs with uses, the instruction is dead.
74  return true;
75}
76
77bool DeadMachineInstructionElim::runOnMachineFunction(MachineFunction &MF) {
78  bool AnyChanges = false;
79  MRI = &MF.getRegInfo();
80  TRI = MF.getTarget().getRegisterInfo();
81  TII = MF.getTarget().getInstrInfo();
82
83  // Treat reserved registers as always live.
84  BitVector ReservedRegs = TRI->getReservedRegs(MF);
85
86  // Loop over all instructions in all blocks, from bottom to top, so that it's
87  // more likely that chains of dependent but ultimately dead instructions will
88  // be cleaned up.
89  for (MachineFunction::reverse_iterator I = MF.rbegin(), E = MF.rend();
90       I != E; ++I) {
91    MachineBasicBlock *MBB = &*I;
92
93    // Start out assuming that reserved registers are live out of this block.
94    LivePhysRegs = ReservedRegs;
95
96    // Also add any explicit live-out physregs for this block.
97    if (!MBB->empty() && MBB->back().getDesc().isReturn())
98      for (MachineRegisterInfo::liveout_iterator LOI = MRI->liveout_begin(),
99           LOE = MRI->liveout_end(); LOI != LOE; ++LOI) {
100        unsigned Reg = *LOI;
101        if (TargetRegisterInfo::isPhysicalRegister(Reg))
102          LivePhysRegs.set(Reg);
103      }
104
105    // FIXME: Add live-ins from sucessors to LivePhysRegs. Normally, physregs
106    // are not live across blocks, but some targets (x86) can have flags live
107    // out of a block.
108
109    // Now scan the instructions and delete dead ones, tracking physreg
110    // liveness as we go.
111    for (MachineBasicBlock::reverse_iterator MII = MBB->rbegin(),
112         MIE = MBB->rend(); MII != MIE; ) {
113      MachineInstr *MI = &*MII;
114
115      // If the instruction is dead, delete it!
116      if (isDead(MI)) {
117        DEBUG(dbgs() << "DeadMachineInstructionElim: DELETING: " << *MI);
118        // It is possible that some DBG_VALUE instructions refer to this
119        // instruction.  Examine each def operand for such references;
120        // if found, mark the DBG_VALUE as undef (but don't delete it).
121        for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
122          const MachineOperand &MO = MI->getOperand(i);
123          if (!MO.isReg() || !MO.isDef())
124            continue;
125          unsigned Reg = MO.getReg();
126          if (!TargetRegisterInfo::isVirtualRegister(Reg))
127            continue;
128          MachineRegisterInfo::use_iterator nextI;
129          for (MachineRegisterInfo::use_iterator I = MRI->use_begin(Reg),
130               E = MRI->use_end(); I!=E; I=nextI) {
131            nextI = llvm::next(I);  // I is invalidated by the setReg
132            MachineOperand& Use = I.getOperand();
133            MachineInstr *UseMI = Use.getParent();
134            if (UseMI==MI)
135              continue;
136            assert(Use.isDebug());
137            UseMI->getOperand(0).setReg(0U);
138          }
139        }
140        AnyChanges = true;
141        MI->eraseFromParent();
142        ++NumDeletes;
143        MIE = MBB->rend();
144        // MII is now pointing to the next instruction to process,
145        // so don't increment it.
146        continue;
147      }
148
149      // Record the physreg defs.
150      for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
151        const MachineOperand &MO = MI->getOperand(i);
152        if (MO.isReg() && MO.isDef()) {
153          unsigned Reg = MO.getReg();
154          if (Reg != 0 && TargetRegisterInfo::isPhysicalRegister(Reg)) {
155            LivePhysRegs.reset(Reg);
156            // Check the subreg set, not the alias set, because a def
157            // of a super-register may still be partially live after
158            // this def.
159            for (const unsigned *SubRegs = TRI->getSubRegisters(Reg);
160                 *SubRegs; ++SubRegs)
161              LivePhysRegs.reset(*SubRegs);
162          }
163        }
164      }
165      // Record the physreg uses, after the defs, in case a physreg is
166      // both defined and used in the same instruction.
167      for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
168        const MachineOperand &MO = MI->getOperand(i);
169        if (MO.isReg() && MO.isUse()) {
170          unsigned Reg = MO.getReg();
171          if (Reg != 0 && TargetRegisterInfo::isPhysicalRegister(Reg)) {
172            LivePhysRegs.set(Reg);
173            for (const unsigned *AliasSet = TRI->getAliasSet(Reg);
174                 *AliasSet; ++AliasSet)
175              LivePhysRegs.set(*AliasSet);
176          }
177        }
178      }
179
180      // We didn't delete the current instruction, so increment MII to
181      // the next one.
182      ++MII;
183    }
184  }
185
186  LivePhysRegs.clear();
187  return AnyChanges;
188}
189