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 eliminateDeadMI(MachineFunction &MF); 42 }; 43 44 class DeadMachineInstructionElim : public MachineFunctionPass { 45 public: 46 static char ID; // Pass identification, replacement for typeid 47 48 DeadMachineInstructionElim() : MachineFunctionPass(ID) { 49 initializeDeadMachineInstructionElimPass(*PassRegistry::getPassRegistry()); 50 } 51 52 bool runOnMachineFunction(MachineFunction &MF) override { 53 if (skipFunction(MF.getFunction())) 54 return false; 55 return DeadMachineInstructionElimImpl().runImpl(MF); 56 } 57 58 void getAnalysisUsage(AnalysisUsage &AU) const override { 59 AU.setPreservesCFG(); 60 MachineFunctionPass::getAnalysisUsage(AU); 61 } 62 }; 63 } // namespace 64 65 PreservedAnalyses 66 DeadMachineInstructionElimPass::run(MachineFunction &MF, 67 MachineFunctionAnalysisManager &) { 68 if (!DeadMachineInstructionElimImpl().runImpl(MF)) 69 return PreservedAnalyses::all(); 70 PreservedAnalyses PA = getMachineFunctionPassPreservedAnalyses(); 71 PA.preserveSet<CFGAnalyses>(); 72 return PA; 73 } 74 75 char DeadMachineInstructionElim::ID = 0; 76 char &llvm::DeadMachineInstructionElimID = DeadMachineInstructionElim::ID; 77 78 INITIALIZE_PASS(DeadMachineInstructionElim, DEBUG_TYPE, 79 "Remove dead machine instructions", false, false) 80 81 bool DeadMachineInstructionElimImpl::runImpl(MachineFunction &MF) { 82 MRI = &MF.getRegInfo(); 83 84 const TargetSubtargetInfo &ST = MF.getSubtarget(); 85 TII = ST.getInstrInfo(); 86 LivePhysRegs.init(*ST.getRegisterInfo()); 87 88 bool AnyChanges = eliminateDeadMI(MF); 89 while (AnyChanges && eliminateDeadMI(MF)) 90 ; 91 return AnyChanges; 92 } 93 94 bool DeadMachineInstructionElimImpl::eliminateDeadMI(MachineFunction &MF) { 95 bool AnyChanges = false; 96 97 // Loop over all instructions in all blocks, from bottom to top, so that it's 98 // more likely that chains of dependent but ultimately dead instructions will 99 // be cleaned up. 100 for (MachineBasicBlock *MBB : post_order(&MF)) { 101 LivePhysRegs.addLiveOuts(*MBB); 102 103 // Now scan the instructions and delete dead ones, tracking physreg 104 // liveness as we go. 105 for (MachineInstr &MI : make_early_inc_range(reverse(*MBB))) { 106 // If the instruction is dead, delete it! 107 if (MI.isDead(*MRI, &LivePhysRegs)) { 108 LLVM_DEBUG(dbgs() << "DeadMachineInstructionElim: DELETING: " << MI); 109 // It is possible that some DBG_VALUE instructions refer to this 110 // instruction. They will be deleted in the live debug variable 111 // analysis. 112 MI.eraseFromParent(); 113 AnyChanges = true; 114 ++NumDeletes; 115 continue; 116 } 117 LivePhysRegs.stepBackward(MI); 118 } 119 } 120 LivePhysRegs.clear(); 121 return AnyChanges; 122 } 123