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