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 // Basic check on the register. All of them should be 'undef'. 89 for (auto &U : MRI->use_nodbg_operands(Reg)) 90 assert(U.isUndef() && "'Undef' use on a 'dead' register is found!"); 91 #endif 92 continue; 93 } 94 for (const MachineInstr &Use : MRI->use_nodbg_instructions(Reg)) { 95 if (&Use != MI) 96 // This def has a non-debug use. Don't delete the instruction! 97 return false; 98 } 99 } 100 } 101 } 102 103 // If there are no defs with uses, the instruction is dead. 104 return true; 105 } 106 107 bool DeadMachineInstructionElim::runOnMachineFunction(MachineFunction &MF) { 108 if (skipFunction(MF.getFunction())) 109 return false; 110 111 MRI = &MF.getRegInfo(); 112 113 const TargetSubtargetInfo &ST = MF.getSubtarget(); 114 TII = ST.getInstrInfo(); 115 LivePhysRegs.init(*ST.getRegisterInfo()); 116 117 bool AnyChanges = eliminateDeadMI(MF); 118 while (AnyChanges && eliminateDeadMI(MF)) 119 ; 120 return AnyChanges; 121 } 122 123 bool DeadMachineInstructionElim::eliminateDeadMI(MachineFunction &MF) { 124 bool AnyChanges = false; 125 126 // Loop over all instructions in all blocks, from bottom to top, so that it's 127 // more likely that chains of dependent but ultimately dead instructions will 128 // be cleaned up. 129 for (MachineBasicBlock *MBB : post_order(&MF)) { 130 LivePhysRegs.addLiveOuts(*MBB); 131 132 // Now scan the instructions and delete dead ones, tracking physreg 133 // liveness as we go. 134 for (MachineInstr &MI : make_early_inc_range(reverse(*MBB))) { 135 // If the instruction is dead, delete it! 136 if (isDead(&MI)) { 137 LLVM_DEBUG(dbgs() << "DeadMachineInstructionElim: DELETING: " << MI); 138 // It is possible that some DBG_VALUE instructions refer to this 139 // instruction. They will be deleted in the live debug variable 140 // analysis. 141 MI.eraseFromParent(); 142 AnyChanges = true; 143 ++NumDeletes; 144 continue; 145 } 146 147 LivePhysRegs.stepBackward(MI); 148 } 149 } 150 151 LivePhysRegs.clear(); 152 return AnyChanges; 153 } 154