DeadMachineInstructionElim.cpp revision 202375
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/Pass.h" 16#include "llvm/CodeGen/MachineFunctionPass.h" 17#include "llvm/CodeGen/MachineRegisterInfo.h" 18#include "llvm/Support/Debug.h" 19#include "llvm/Support/raw_ostream.h" 20#include "llvm/Target/TargetInstrInfo.h" 21#include "llvm/Target/TargetMachine.h" 22using namespace llvm; 23 24namespace { 25 class DeadMachineInstructionElim : public MachineFunctionPass { 26 virtual bool runOnMachineFunction(MachineFunction &MF); 27 28 const TargetRegisterInfo *TRI; 29 const MachineRegisterInfo *MRI; 30 const TargetInstrInfo *TII; 31 BitVector LivePhysRegs; 32 33 public: 34 static char ID; // Pass identification, replacement for typeid 35 DeadMachineInstructionElim() : MachineFunctionPass(&ID) {} 36 37 private: 38 bool isDead(const MachineInstr *MI) const; 39 }; 40} 41char DeadMachineInstructionElim::ID = 0; 42 43static RegisterPass<DeadMachineInstructionElim> 44Y("dead-mi-elimination", 45 "Remove dead machine instructions"); 46 47FunctionPass *llvm::createDeadMachineInstructionElimPass() { 48 return new DeadMachineInstructionElim(); 49} 50 51bool DeadMachineInstructionElim::isDead(const MachineInstr *MI) const { 52 // Don't delete instructions with side effects. 53 bool SawStore = false; 54 if (!MI->isSafeToMove(TII, SawStore, 0)) 55 return false; 56 57 // Examine each operand. 58 for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 59 const MachineOperand &MO = MI->getOperand(i); 60 if (MO.isReg() && MO.isDef()) { 61 unsigned Reg = MO.getReg(); 62 if (TargetRegisterInfo::isPhysicalRegister(Reg) ? 63 LivePhysRegs[Reg] : !MRI->use_empty(Reg)) { 64 // This def has a use. Don't delete the instruction! 65 return false; 66 } 67 } 68 } 69 70 // If there are no defs with uses, the instruction is dead. 71 return true; 72} 73 74bool DeadMachineInstructionElim::runOnMachineFunction(MachineFunction &MF) { 75 bool AnyChanges = false; 76 MRI = &MF.getRegInfo(); 77 TRI = MF.getTarget().getRegisterInfo(); 78 TII = MF.getTarget().getInstrInfo(); 79 80 // Compute a bitvector to represent all non-allocatable physregs. 81 BitVector NonAllocatableRegs = TRI->getAllocatableSet(MF); 82 NonAllocatableRegs.flip(); 83 84 // Loop over all instructions in all blocks, from bottom to top, so that it's 85 // more likely that chains of dependent but ultimately dead instructions will 86 // be cleaned up. 87 for (MachineFunction::reverse_iterator I = MF.rbegin(), E = MF.rend(); 88 I != E; ++I) { 89 MachineBasicBlock *MBB = &*I; 90 91 // Start out assuming that all non-allocatable registers are live 92 // out of this block. 93 LivePhysRegs = NonAllocatableRegs; 94 95 // Also add any explicit live-out physregs for this block. 96 if (!MBB->empty() && MBB->back().getDesc().isReturn()) 97 for (MachineRegisterInfo::liveout_iterator LOI = MRI->liveout_begin(), 98 LOE = MRI->liveout_end(); LOI != LOE; ++LOI) { 99 unsigned Reg = *LOI; 100 if (TargetRegisterInfo::isPhysicalRegister(Reg)) 101 LivePhysRegs.set(Reg); 102 } 103 104 // Now scan the instructions and delete dead ones, tracking physreg 105 // liveness as we go. 106 for (MachineBasicBlock::reverse_iterator MII = MBB->rbegin(), 107 MIE = MBB->rend(); MII != MIE; ) { 108 MachineInstr *MI = &*MII; 109 110 // If the instruction is dead, delete it! 111 if (isDead(MI)) { 112 DEBUG(dbgs() << "DeadMachineInstructionElim: DELETING: " << *MI); 113 AnyChanges = true; 114 MI->eraseFromParent(); 115 MIE = MBB->rend(); 116 // MII is now pointing to the next instruction to process, 117 // so don't increment it. 118 continue; 119 } 120 121 // Record the physreg defs. 122 for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 123 const MachineOperand &MO = MI->getOperand(i); 124 if (MO.isReg() && MO.isDef()) { 125 unsigned Reg = MO.getReg(); 126 if (Reg != 0 && TargetRegisterInfo::isPhysicalRegister(Reg)) { 127 LivePhysRegs.reset(Reg); 128 // Check the subreg set, not the alias set, because a def 129 // of a super-register may still be partially live after 130 // this def. 131 for (const unsigned *SubRegs = TRI->getSubRegisters(Reg); 132 *SubRegs; ++SubRegs) 133 LivePhysRegs.reset(*SubRegs); 134 } 135 } 136 } 137 // Record the physreg uses, after the defs, in case a physreg is 138 // both defined and used in the same instruction. 139 for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 140 const MachineOperand &MO = MI->getOperand(i); 141 if (MO.isReg() && MO.isUse()) { 142 unsigned Reg = MO.getReg(); 143 if (Reg != 0 && TargetRegisterInfo::isPhysicalRegister(Reg)) { 144 LivePhysRegs.set(Reg); 145 for (const unsigned *AliasSet = TRI->getAliasSet(Reg); 146 *AliasSet; ++AliasSet) 147 LivePhysRegs.set(*AliasSet); 148 } 149 } 150 } 151 152 // We didn't delete the current instruction, so increment MII to 153 // the next one. 154 ++MII; 155 } 156 } 157 158 LivePhysRegs.clear(); 159 return AnyChanges; 160} 161