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