1 //===- DeadMachineInstructionElim.cpp - Remove dead machine instructions --===// 2 // 3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4 // See https://llvm.org/LICENSE.txt for license information. 5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 6 // 7 //===----------------------------------------------------------------------===// 8 // 9 // This is an extremely simple MachineInstr-level dead-code-elimination pass. 10 // 11 //===----------------------------------------------------------------------===// 12 13 #include "llvm/ADT/PostOrderIterator.h" 14 #include "llvm/ADT/Statistic.h" 15 #include "llvm/CodeGen/LiveRegUnits.h" 16 #include "llvm/CodeGen/MachineFunctionPass.h" 17 #include "llvm/CodeGen/MachineRegisterInfo.h" 18 #include "llvm/CodeGen/TargetSubtargetInfo.h" 19 #include "llvm/InitializePasses.h" 20 #include "llvm/Pass.h" 21 #include "llvm/Support/Debug.h" 22 #include "llvm/Support/raw_ostream.h" 23 24 using namespace llvm; 25 26 #define DEBUG_TYPE "dead-mi-elimination" 27 28 STATISTIC(NumDeletes, "Number of dead instructions deleted"); 29 30 namespace { 31 class DeadMachineInstructionElim : public MachineFunctionPass { 32 bool runOnMachineFunction(MachineFunction &MF) override; 33 34 const MachineRegisterInfo *MRI; 35 const TargetInstrInfo *TII; 36 LiveRegUnits LivePhysRegs; 37 38 public: 39 static char ID; // Pass identification, replacement for typeid 40 DeadMachineInstructionElim() : MachineFunctionPass(ID) { 41 initializeDeadMachineInstructionElimPass(*PassRegistry::getPassRegistry()); 42 } 43 44 void getAnalysisUsage(AnalysisUsage &AU) const override { 45 AU.setPreservesCFG(); 46 MachineFunctionPass::getAnalysisUsage(AU); 47 } 48 49 private: 50 bool isDead(const MachineInstr *MI) const; 51 52 bool eliminateDeadMI(MachineFunction &MF); 53 }; 54 } 55 char DeadMachineInstructionElim::ID = 0; 56 char &llvm::DeadMachineInstructionElimID = DeadMachineInstructionElim::ID; 57 58 INITIALIZE_PASS(DeadMachineInstructionElim, DEBUG_TYPE, 59 "Remove dead machine instructions", false, false) 60 61 bool DeadMachineInstructionElim::isDead(const MachineInstr *MI) const { 62 // Technically speaking inline asm without side effects and no defs can still 63 // be deleted. But there is so much bad inline asm code out there, we should 64 // let them be. 65 if (MI->isInlineAsm()) 66 return false; 67 68 // Don't delete frame allocation labels. 69 if (MI->getOpcode() == TargetOpcode::LOCAL_ESCAPE) 70 return false; 71 72 // Don't delete instructions with side effects. 73 bool SawStore = false; 74 if (!MI->isSafeToMove(nullptr, SawStore) && !MI->isPHI()) 75 return false; 76 77 // Examine each operand. 78 for (const MachineOperand &MO : MI->operands()) { 79 if (MO.isReg() && MO.isDef()) { 80 Register Reg = MO.getReg(); 81 if (Reg.isPhysical()) { 82 // Don't delete live physreg defs, or any reserved register defs. 83 if (!LivePhysRegs.available(Reg) || MRI->isReserved(Reg)) 84 return false; 85 } else { 86 if (MO.isDead()) { 87 #ifndef NDEBUG 88 // Baisc check on the register. All of them should be 89 // 'undef'. 90 for (auto &U : MRI->use_nodbg_operands(Reg)) 91 assert(U.isUndef() && "'Undef' use on a 'dead' register is found!"); 92 #endif 93 continue; 94 } 95 for (const MachineInstr &Use : MRI->use_nodbg_instructions(Reg)) { 96 if (&Use != MI) 97 // This def has a non-debug use. Don't delete the instruction! 98 return false; 99 } 100 } 101 } 102 } 103 104 // If there are no defs with uses, the instruction is dead. 105 return true; 106 } 107 108 bool DeadMachineInstructionElim::runOnMachineFunction(MachineFunction &MF) { 109 if (skipFunction(MF.getFunction())) 110 return false; 111 bool AnyChanges = eliminateDeadMI(MF); 112 while (AnyChanges && eliminateDeadMI(MF)) 113 ; 114 return AnyChanges; 115 } 116 117 bool DeadMachineInstructionElim::eliminateDeadMI(MachineFunction &MF) { 118 bool AnyChanges = false; 119 MRI = &MF.getRegInfo(); 120 TII = MF.getSubtarget().getInstrInfo(); 121 122 LivePhysRegs.init(*MF.getSubtarget().getRegisterInfo()); 123 124 // Loop over all instructions in all blocks, from bottom to top, so that it's 125 // more likely that chains of dependent but ultimately dead instructions will 126 // be cleaned up. 127 for (MachineBasicBlock *MBB : post_order(&MF)) { 128 LivePhysRegs.addLiveOuts(*MBB); 129 130 // Now scan the instructions and delete dead ones, tracking physreg 131 // liveness as we go. 132 for (MachineInstr &MI : make_early_inc_range(reverse(*MBB))) { 133 // If the instruction is dead, delete it! 134 if (isDead(&MI)) { 135 LLVM_DEBUG(dbgs() << "DeadMachineInstructionElim: DELETING: " << MI); 136 // It is possible that some DBG_VALUE instructions refer to this 137 // instruction. They will be deleted in the live debug variable 138 // analysis. 139 MI.eraseFromParent(); 140 AnyChanges = true; 141 ++NumDeletes; 142 continue; 143 } 144 145 LivePhysRegs.stepBackward(MI); 146 } 147 } 148 149 LivePhysRegs.clear(); 150 return AnyChanges; 151 } 152