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 = nullptr; 35 const TargetInstrInfo *TII = nullptr; 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->all_defs()) { 79 Register Reg = MO.getReg(); 80 if (Reg.isPhysical()) { 81 // Don't delete live physreg defs, or any reserved register defs. 82 if (!LivePhysRegs.available(Reg) || MRI->isReserved(Reg)) 83 return false; 84 } else { 85 if (MO.isDead()) { 86 #ifndef NDEBUG 87 // Basic check on the register. All of them should be 'undef'. 88 for (auto &U : MRI->use_nodbg_operands(Reg)) 89 assert(U.isUndef() && "'Undef' use on a 'dead' register is found!"); 90 #endif 91 continue; 92 } 93 for (const MachineInstr &Use : MRI->use_nodbg_instructions(Reg)) { 94 if (&Use != MI) 95 // This def has a non-debug use. Don't delete the instruction! 96 return false; 97 } 98 } 99 } 100 101 // If there are no defs with uses, the instruction is dead. 102 return true; 103 } 104 105 bool DeadMachineInstructionElim::runOnMachineFunction(MachineFunction &MF) { 106 if (skipFunction(MF.getFunction())) 107 return false; 108 109 MRI = &MF.getRegInfo(); 110 111 const TargetSubtargetInfo &ST = MF.getSubtarget(); 112 TII = ST.getInstrInfo(); 113 LivePhysRegs.init(*ST.getRegisterInfo()); 114 115 bool AnyChanges = eliminateDeadMI(MF); 116 while (AnyChanges && eliminateDeadMI(MF)) 117 ; 118 return AnyChanges; 119 } 120 121 bool DeadMachineInstructionElim::eliminateDeadMI(MachineFunction &MF) { 122 bool AnyChanges = false; 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