DeadMachineInstructionElim.cpp revision 36b56886974eae4f9c5ebc96befd3e7bfe5de338
1116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch//===- DeadMachineInstructionElim.cpp - Remove dead machine instructions --===// 25f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles)// 3116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch// The LLVM Compiler Infrastructure 4116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch// 5116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch// This file is distributed under the University of Illinois Open Source 6116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch// License. See LICENSE.TXT for details. 7116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch// 8116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch//===----------------------------------------------------------------------===// 9116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch// 10116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch// This is an extremely simple MachineInstr-level dead-code-elimination pass. 11116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch// 12116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch//===----------------------------------------------------------------------===// 13116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch 14116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch#define DEBUG_TYPE "codegen-dce" 15116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch#include "llvm/CodeGen/Passes.h" 16116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch#include "llvm/ADT/Statistic.h" 17116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch#include "llvm/CodeGen/MachineFunctionPass.h" 18116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch#include "llvm/CodeGen/MachineRegisterInfo.h" 19116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch#include "llvm/Pass.h" 20116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch#include "llvm/Support/Debug.h" 21116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch#include "llvm/Support/raw_ostream.h" 22116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch#include "llvm/Target/TargetInstrInfo.h" 23116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch#include "llvm/Target/TargetMachine.h" 24116680a4aac90f2aa7413d9095a592090648e557Ben Murdochusing namespace llvm; 25116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch 26116680a4aac90f2aa7413d9095a592090648e557Ben MurdochSTATISTIC(NumDeletes, "Number of dead instructions deleted"); 27116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch 28116680a4aac90f2aa7413d9095a592090648e557Ben Murdochnamespace { 29116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch class DeadMachineInstructionElim : public MachineFunctionPass { 30116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch bool runOnMachineFunction(MachineFunction &MF) override; 31116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch 32116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch const TargetRegisterInfo *TRI; 33116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch const MachineRegisterInfo *MRI; 34116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch const TargetInstrInfo *TII; 35116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch BitVector LivePhysRegs; 36116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch 37116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch public: 38116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch static char ID; // Pass identification, replacement for typeid 39116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch DeadMachineInstructionElim() : MachineFunctionPass(ID) { 40116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch initializeDeadMachineInstructionElimPass(*PassRegistry::getPassRegistry()); 41116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch } 42116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch 43116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch private: 44116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch bool isDead(const MachineInstr *MI) const; 45116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch }; 46116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch} 47116680a4aac90f2aa7413d9095a592090648e557Ben Murdochchar DeadMachineInstructionElim::ID = 0; 48116680a4aac90f2aa7413d9095a592090648e557Ben Murdochchar &llvm::DeadMachineInstructionElimID = DeadMachineInstructionElim::ID; 49116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch 50116680a4aac90f2aa7413d9095a592090648e557Ben MurdochINITIALIZE_PASS(DeadMachineInstructionElim, "dead-mi-elimination", 51116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch "Remove dead machine instructions", false, false) 52116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch 53116680a4aac90f2aa7413d9095a592090648e557Ben Murdochbool DeadMachineInstructionElim::isDead(const MachineInstr *MI) const { 54116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch // Technically speaking inline asm without side effects and no defs can still 55116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch // be deleted. But there is so much bad inline asm code out there, we should 56116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch // let them be. 57116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch if (MI->isInlineAsm()) 58116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch return false; 59116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch 60116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch // Don't delete instructions with side effects. 61116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch bool SawStore = false; 62116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch if (!MI->isSafeToMove(TII, 0, SawStore) && !MI->isPHI()) 63116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch return false; 64116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch 65116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch // Examine each operand. 66116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 67116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch const MachineOperand &MO = MI->getOperand(i); 68116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch if (MO.isReg() && MO.isDef()) { 69116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch unsigned Reg = MO.getReg(); 70116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch if (TargetRegisterInfo::isPhysicalRegister(Reg)) { 71116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch // Don't delete live physreg defs, or any reserved register defs. 72116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch if (LivePhysRegs.test(Reg) || MRI->isReserved(Reg)) 73116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch return false; 74116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch } else { 75116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch if (!MRI->use_nodbg_empty(Reg)) 76116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch // This def has a non-debug use. Don't delete the instruction! 77116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch return false; 78116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch } 79116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch } 80116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch } 81116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch 82116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch // If there are no defs with uses, the instruction is dead. 83116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch return true; 84116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch} 85116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch 86116680a4aac90f2aa7413d9095a592090648e557Ben Murdochbool DeadMachineInstructionElim::runOnMachineFunction(MachineFunction &MF) { 87116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch if (skipOptnoneFunction(*MF.getFunction())) 88116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch return false; 89116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch 90116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch bool AnyChanges = false; 91116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch MRI = &MF.getRegInfo(); 92116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch TRI = MF.getTarget().getRegisterInfo(); 93116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch TII = MF.getTarget().getInstrInfo(); 94116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch 95116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch // Loop over all instructions in all blocks, from bottom to top, so that it's 96116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch // more likely that chains of dependent but ultimately dead instructions will 97116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch // be cleaned up. 98116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch for (MachineFunction::reverse_iterator I = MF.rbegin(), E = MF.rend(); 99116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch I != E; ++I) { 100116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch MachineBasicBlock *MBB = &*I; 101116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch 102116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch // Start out assuming that reserved registers are live out of this block. 103116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch LivePhysRegs = MRI->getReservedRegs(); 104116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch 105116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch // Add live-ins from sucessors to LivePhysRegs. Normally, physregs are not 106116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch // live across blocks, but some targets (x86) can have flags live out of a 107116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch // block. 108116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch for (MachineBasicBlock::succ_iterator S = MBB->succ_begin(), 109116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch E = MBB->succ_end(); S != E; S++) 110116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch for (MachineBasicBlock::livein_iterator LI = (*S)->livein_begin(); 111116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch LI != (*S)->livein_end(); LI++) 112116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch LivePhysRegs.set(*LI); 113116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch 114116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch // Now scan the instructions and delete dead ones, tracking physreg 115116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch // liveness as we go. 116116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch for (MachineBasicBlock::reverse_iterator MII = MBB->rbegin(), 117116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch MIE = MBB->rend(); MII != MIE; ) { 118116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch MachineInstr *MI = &*MII; 119116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch 120116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch // If the instruction is dead, delete it! 121116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch if (isDead(MI)) { 122116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch DEBUG(dbgs() << "DeadMachineInstructionElim: DELETING: " << *MI); 123116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch // It is possible that some DBG_VALUE instructions refer to this 124116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch // instruction. Examine each def operand for such references; 125116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch // if found, mark the DBG_VALUE as undef (but don't delete it). 126116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 127116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch const MachineOperand &MO = MI->getOperand(i); 128116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch if (!MO.isReg() || !MO.isDef()) 129116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch continue; 130116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch unsigned Reg = MO.getReg(); 131116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch if (!TargetRegisterInfo::isVirtualRegister(Reg)) 132116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch continue; 133116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch MRI->markUsesInDebugValueAsUndef(Reg); 134116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch } 135116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch AnyChanges = true; 136116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch MI->eraseFromParent(); 137116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch ++NumDeletes; 138116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch MIE = MBB->rend(); 139116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch // MII is now pointing to the next instruction to process, 140116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch // so don't increment it. 141116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch continue; 142116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch } 143116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch 144116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch // Record the physreg defs. 145116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 146116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch const MachineOperand &MO = MI->getOperand(i); 147116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch if (MO.isReg() && MO.isDef()) { 148116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch unsigned Reg = MO.getReg(); 149116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch if (TargetRegisterInfo::isPhysicalRegister(Reg)) { 150116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch // Check the subreg set, not the alias set, because a def 151116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch // of a super-register may still be partially live after 152116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch // this def. 153116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch for (MCSubRegIterator SR(Reg, TRI,/*IncludeSelf=*/true); 154116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch SR.isValid(); ++SR) 155116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch LivePhysRegs.reset(*SR); 156116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch } 157116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch } else if (MO.isRegMask()) { 158116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch // Register mask of preserved registers. All clobbers are dead. 159116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch LivePhysRegs.clearBitsNotInMask(MO.getRegMask()); 160116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch } 161116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch } 162116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch // Record the physreg uses, after the defs, in case a physreg is 163116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch // both defined and used in the same instruction. 164116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 165116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch const MachineOperand &MO = MI->getOperand(i); 166116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch if (MO.isReg() && MO.isUse()) { 167116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch unsigned Reg = MO.getReg(); 168116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch if (TargetRegisterInfo::isPhysicalRegister(Reg)) { 169116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch for (MCRegAliasIterator AI(Reg, TRI, true); AI.isValid(); ++AI) 170116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch LivePhysRegs.set(*AI); 171116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch } 172116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch } 173116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch } 174116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch 175116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch // We didn't delete the current instruction, so increment MII to 176116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch // the next one. 177116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch ++MII; 178116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch } 179116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch } 180116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch 181116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch LivePhysRegs.clear(); 182116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch return AnyChanges; 183116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch} 184116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch