DeadMachineInstructionElim.cpp revision b9f4fa7b400836808bc3beab96482418f418f246
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/Target/TargetInstrInfo.h" 21#include "llvm/Target/TargetMachine.h" 22using namespace llvm; 23 24namespace { 25 class VISIBILITY_HIDDEN DeadMachineInstructionElim : 26 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(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(MachineInstr *MI) const { 53 // Don't delete instructions with side effects. 54 bool SawStore = false; 55 if (!MI->isSafeToMove(TII, SawStore)) 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 DOUT << "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 for (const unsigned *AliasSet = TRI->getAliasSet(Reg); 130 *AliasSet; ++AliasSet) 131 LivePhysRegs.reset(*AliasSet); 132 } 133 } 134 } 135 // Record the physreg uses, after the defs, in case a physreg is 136 // both defined and used in the same instruction. 137 for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 138 const MachineOperand &MO = MI->getOperand(i); 139 if (MO.isReg() && MO.isUse()) { 140 unsigned Reg = MO.getReg(); 141 if (Reg != 0 && TargetRegisterInfo::isPhysicalRegister(Reg)) { 142 LivePhysRegs.set(Reg); 143 for (const unsigned *AliasSet = TRI->getAliasSet(Reg); 144 *AliasSet; ++AliasSet) 145 LivePhysRegs.set(*AliasSet); 146 } 147 } 148 } 149 150 // We didn't delete the current instruction, so increment MII to 151 // the next one. 152 ++MII; 153 } 154 } 155 156 LivePhysRegs.clear(); 157 return AnyChanges; 158} 159