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