blob: 5b2e31ab42620e80dfc035186ab1c955fa72770e [file] [log] [blame]
Dan Gohmand3ead432008-09-17 00:43:24 +00001//===- 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
Evan Cheng00a99a32010-02-06 09:07:11 +000014#define DEBUG_TYPE "codegen-dce"
Dan Gohmand3ead432008-09-17 00:43:24 +000015#include "llvm/CodeGen/Passes.h"
16#include "llvm/Pass.h"
17#include "llvm/CodeGen/MachineFunctionPass.h"
18#include "llvm/CodeGen/MachineRegisterInfo.h"
Dan Gohman723ac372008-09-25 01:06:50 +000019#include "llvm/Support/Debug.h"
Bill Wendling9311a222009-08-22 20:04:03 +000020#include "llvm/Support/raw_ostream.h"
Dan Gohmand3ead432008-09-17 00:43:24 +000021#include "llvm/Target/TargetInstrInfo.h"
22#include "llvm/Target/TargetMachine.h"
Evan Cheng00a99a32010-02-06 09:07:11 +000023#include "llvm/ADT/Statistic.h"
Dan Gohmand3ead432008-09-17 00:43:24 +000024using namespace llvm;
25
Evan Cheng00a99a32010-02-06 09:07:11 +000026STATISTIC(NumDeletes, "Number of dead instructions deleted");
27
Dan Gohmand3ead432008-09-17 00:43:24 +000028namespace {
Nick Lewycky6726b6d2009-10-25 06:33:48 +000029 class DeadMachineInstructionElim : public MachineFunctionPass {
Dan Gohmand3ead432008-09-17 00:43:24 +000030 virtual bool runOnMachineFunction(MachineFunction &MF);
Andrew Trick1df91b02012-02-08 21:22:43 +000031
Dan Gohman3d84a762008-09-24 00:27:38 +000032 const TargetRegisterInfo *TRI;
33 const MachineRegisterInfo *MRI;
34 const TargetInstrInfo *TII;
35 BitVector LivePhysRegs;
36
Dan Gohmand3ead432008-09-17 00:43:24 +000037 public:
38 static char ID; // Pass identification, replacement for typeid
Owen Anderson081c34b2010-10-19 17:21:58 +000039 DeadMachineInstructionElim() : MachineFunctionPass(ID) {
40 initializeDeadMachineInstructionElimPass(*PassRegistry::getPassRegistry());
41 }
Dan Gohman3d84a762008-09-24 00:27:38 +000042
43 private:
Dan Gohmand443ee62009-08-11 15:13:43 +000044 bool isDead(const MachineInstr *MI) const;
Dan Gohmand3ead432008-09-17 00:43:24 +000045 };
46}
47char DeadMachineInstructionElim::ID = 0;
Andrew Trick1dd8c852012-02-08 21:23:13 +000048char &llvm::DeadMachineInstructionElimID = DeadMachineInstructionElim::ID;
Dan Gohmand3ead432008-09-17 00:43:24 +000049
Owen Andersond13db2c2010-07-21 22:09:45 +000050INITIALIZE_PASS(DeadMachineInstructionElim, "dead-mi-elimination",
Owen Andersonce665bd2010-10-07 22:25:06 +000051 "Remove dead machine instructions", false, false)
Dan Gohmand3ead432008-09-17 00:43:24 +000052
Dan Gohmand443ee62009-08-11 15:13:43 +000053bool DeadMachineInstructionElim::isDead(const MachineInstr *MI) const {
Evan Chengc36b7062011-01-07 23:50:32 +000054 // Technically speaking inline asm without side effects and no defs can still
55 // be deleted. But there is so much bad inline asm code out there, we should
56 // let them be.
57 if (MI->isInlineAsm())
58 return false;
59
Dan Gohman3d84a762008-09-24 00:27:38 +000060 // Don't delete instructions with side effects.
61 bool SawStore = false;
Evan Chengac1abde2010-03-02 19:03:01 +000062 if (!MI->isSafeToMove(TII, 0, SawStore) && !MI->isPHI())
Dan Gohman3d84a762008-09-24 00:27:38 +000063 return false;
64
65 // Examine each operand.
66 for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
67 const MachineOperand &MO = MI->getOperand(i);
Dan Gohmand735b802008-10-03 15:45:36 +000068 if (MO.isReg() && MO.isDef()) {
Dan Gohman3d84a762008-09-24 00:27:38 +000069 unsigned Reg = MO.getReg();
70 if (TargetRegisterInfo::isPhysicalRegister(Reg) ?
Dale Johannesen2d1ec732010-02-12 18:40:17 +000071 LivePhysRegs[Reg] : !MRI->use_nodbg_empty(Reg)) {
72 // This def has a non-debug use. Don't delete the instruction!
Dan Gohman3d84a762008-09-24 00:27:38 +000073 return false;
74 }
75 }
76 }
77
78 // If there are no defs with uses, the instruction is dead.
79 return true;
80}
81
Dan Gohmand3ead432008-09-17 00:43:24 +000082bool DeadMachineInstructionElim::runOnMachineFunction(MachineFunction &MF) {
83 bool AnyChanges = false;
Dan Gohman3d84a762008-09-24 00:27:38 +000084 MRI = &MF.getRegInfo();
85 TRI = MF.getTarget().getRegisterInfo();
86 TII = MF.getTarget().getInstrInfo();
Dan Gohmand3ead432008-09-17 00:43:24 +000087
Jakob Stoklund Olesenf14a6482010-08-31 21:51:05 +000088 // Treat reserved registers as always live.
89 BitVector ReservedRegs = TRI->getReservedRegs(MF);
Dan Gohman8468d1a2008-09-23 21:40:44 +000090
Dan Gohmand3ead432008-09-17 00:43:24 +000091 // Loop over all instructions in all blocks, from bottom to top, so that it's
92 // more likely that chains of dependent but ultimately dead instructions will
93 // be cleaned up.
94 for (MachineFunction::reverse_iterator I = MF.rbegin(), E = MF.rend();
95 I != E; ++I) {
96 MachineBasicBlock *MBB = &*I;
Dan Gohman8468d1a2008-09-23 21:40:44 +000097
Jakob Stoklund Olesenf14a6482010-08-31 21:51:05 +000098 // Start out assuming that reserved registers are live out of this block.
99 LivePhysRegs = ReservedRegs;
Dan Gohman8468d1a2008-09-23 21:40:44 +0000100
101 // Also add any explicit live-out physregs for this block.
Evan Cheng5a96b3d2011-12-07 07:15:52 +0000102 if (!MBB->empty() && MBB->back().isReturn())
Dan Gohman3d84a762008-09-24 00:27:38 +0000103 for (MachineRegisterInfo::liveout_iterator LOI = MRI->liveout_begin(),
104 LOE = MRI->liveout_end(); LOI != LOE; ++LOI) {
Dan Gohman8468d1a2008-09-23 21:40:44 +0000105 unsigned Reg = *LOI;
106 if (TargetRegisterInfo::isPhysicalRegister(Reg))
107 LivePhysRegs.set(Reg);
108 }
109
Jakob Stoklund Olesenf27229e2011-06-27 15:00:36 +0000110 // Add live-ins from sucessors to LivePhysRegs. Normally, physregs are not
111 // live across blocks, but some targets (x86) can have flags live out of a
112 // block.
113 for (MachineBasicBlock::succ_iterator S = MBB->succ_begin(),
114 E = MBB->succ_end(); S != E; S++)
115 for (MachineBasicBlock::livein_iterator LI = (*S)->livein_begin();
116 LI != (*S)->livein_end(); LI++)
117 LivePhysRegs.set(*LI);
Jakob Stoklund Olesenf14a6482010-08-31 21:51:05 +0000118
Dan Gohman8468d1a2008-09-23 21:40:44 +0000119 // Now scan the instructions and delete dead ones, tracking physreg
120 // liveness as we go.
Dan Gohmand3ead432008-09-17 00:43:24 +0000121 for (MachineBasicBlock::reverse_iterator MII = MBB->rbegin(),
122 MIE = MBB->rend(); MII != MIE; ) {
123 MachineInstr *MI = &*MII;
124
Dan Gohman3d84a762008-09-24 00:27:38 +0000125 // If the instruction is dead, delete it!
126 if (isDead(MI)) {
David Greene26045e22010-01-04 19:10:20 +0000127 DEBUG(dbgs() << "DeadMachineInstructionElim: DELETING: " << *MI);
Dale Johannesen2d1ec732010-02-12 18:40:17 +0000128 // It is possible that some DBG_VALUE instructions refer to this
129 // instruction. Examine each def operand for such references;
130 // if found, mark the DBG_VALUE as undef (but don't delete it).
131 for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
132 const MachineOperand &MO = MI->getOperand(i);
133 if (!MO.isReg() || !MO.isDef())
134 continue;
135 unsigned Reg = MO.getReg();
136 if (!TargetRegisterInfo::isVirtualRegister(Reg))
137 continue;
138 MachineRegisterInfo::use_iterator nextI;
139 for (MachineRegisterInfo::use_iterator I = MRI->use_begin(Reg),
140 E = MRI->use_end(); I!=E; I=nextI) {
141 nextI = llvm::next(I); // I is invalidated by the setReg
142 MachineOperand& Use = I.getOperand();
143 MachineInstr *UseMI = Use.getParent();
144 if (UseMI==MI)
145 continue;
146 assert(Use.isDebug());
147 UseMI->getOperand(0).setReg(0U);
148 }
149 }
Dan Gohman3d84a762008-09-24 00:27:38 +0000150 AnyChanges = true;
151 MI->eraseFromParent();
Evan Cheng00a99a32010-02-06 09:07:11 +0000152 ++NumDeletes;
Dan Gohman3d84a762008-09-24 00:27:38 +0000153 MIE = MBB->rend();
154 // MII is now pointing to the next instruction to process,
155 // so don't increment it.
156 continue;
Dan Gohmand3ead432008-09-17 00:43:24 +0000157 }
Dan Gohman8468d1a2008-09-23 21:40:44 +0000158
159 // Record the physreg defs.
160 for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
161 const MachineOperand &MO = MI->getOperand(i);
Dan Gohmand735b802008-10-03 15:45:36 +0000162 if (MO.isReg() && MO.isDef()) {
Dan Gohman8468d1a2008-09-23 21:40:44 +0000163 unsigned Reg = MO.getReg();
Jakob Stoklund Olesenc9df0252011-01-10 02:58:51 +0000164 if (TargetRegisterInfo::isPhysicalRegister(Reg)) {
Dan Gohman8468d1a2008-09-23 21:40:44 +0000165 LivePhysRegs.reset(Reg);
Dan Gohmanb382c4d2008-10-16 00:11:23 +0000166 // Check the subreg set, not the alias set, because a def
167 // of a super-register may still be partially live after
168 // this def.
Dan Gohman131161b2008-10-16 01:06:18 +0000169 for (const unsigned *SubRegs = TRI->getSubRegisters(Reg);
170 *SubRegs; ++SubRegs)
171 LivePhysRegs.reset(*SubRegs);
Dan Gohman8468d1a2008-09-23 21:40:44 +0000172 }
Jakob Stoklund Olesen6b88c182012-01-20 22:27:09 +0000173 } else if (MO.isRegMask()) {
174 // Register mask of preserved registers. All clobbers are dead.
Jakob Stoklund Olesen478a8a02012-02-02 23:52:57 +0000175 LivePhysRegs.clearBitsNotInMask(MO.getRegMask());
Jakob Stoklund Olesen6b88c182012-01-20 22:27:09 +0000176 LivePhysRegs |= ReservedRegs;
Dan Gohman8468d1a2008-09-23 21:40:44 +0000177 }
178 }
179 // Record the physreg uses, after the defs, in case a physreg is
180 // both defined and used in the same instruction.
181 for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
182 const MachineOperand &MO = MI->getOperand(i);
Dan Gohmand735b802008-10-03 15:45:36 +0000183 if (MO.isReg() && MO.isUse()) {
Dan Gohman8468d1a2008-09-23 21:40:44 +0000184 unsigned Reg = MO.getReg();
Jakob Stoklund Olesenc9df0252011-01-10 02:58:51 +0000185 if (TargetRegisterInfo::isPhysicalRegister(Reg)) {
Dan Gohman8468d1a2008-09-23 21:40:44 +0000186 LivePhysRegs.set(Reg);
Dan Gohman3d84a762008-09-24 00:27:38 +0000187 for (const unsigned *AliasSet = TRI->getAliasSet(Reg);
Dan Gohman8468d1a2008-09-23 21:40:44 +0000188 *AliasSet; ++AliasSet)
189 LivePhysRegs.set(*AliasSet);
190 }
191 }
192 }
193
Dan Gohmand3ead432008-09-17 00:43:24 +0000194 // We didn't delete the current instruction, so increment MII to
195 // the next one.
196 ++MII;
197 }
198 }
199
Dan Gohman3d84a762008-09-24 00:27:38 +0000200 LivePhysRegs.clear();
Dan Gohmand3ead432008-09-17 00:43:24 +0000201 return AnyChanges;
202}