Home | History | Annotate | Download | only in CodeGen 
      1 //===- DeadMachineInstructionElim.cpp - Remove dead machine instructions --===//
      2 //
      3 //                     The LLVM Compiler Infrastructure
      4 //
      5 // This file is distributed under the University of Illinois Open Source
      6 // License. See LICENSE.TXT for details.
      7 //
      8 //===----------------------------------------------------------------------===//
      9 //
     10 // This is an extremely simple MachineInstr-level dead-code-elimination pass.
     11 //
     12 //===----------------------------------------------------------------------===//
     13 
     14 #include "llvm/CodeGen/Passes.h"
     15 #include "llvm/ADT/Statistic.h"
     16 #include "llvm/CodeGen/MachineFunctionPass.h"
     17 #include "llvm/CodeGen/MachineRegisterInfo.h"
     18 #include "llvm/Pass.h"
     19 #include "llvm/Support/Debug.h"
     20 #include "llvm/Support/raw_ostream.h"
     21 #include "llvm/Target/TargetInstrInfo.h"
     22 #include "llvm/Target/TargetSubtargetInfo.h"
     23 
     24 using namespace llvm;
     25 
     26 #define DEBUG_TYPE "codegen-dce"
     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 TargetRegisterInfo *TRI;
     35     const MachineRegisterInfo *MRI;
     36     const TargetInstrInfo *TII;
     37     BitVector LivePhysRegs;
     38 
     39   public:
     40     static char ID; // Pass identification, replacement for typeid
     41     DeadMachineInstructionElim() : MachineFunctionPass(ID) {
     42      initializeDeadMachineInstructionElimPass(*PassRegistry::getPassRegistry());
     43     }
     44 
     45     void getAnalysisUsage(AnalysisUsage &AU) const override {
     46       AU.setPreservesCFG();
     47       MachineFunctionPass::getAnalysisUsage(AU);
     48     }
     49 
     50   private:
     51     bool isDead(const MachineInstr *MI) const;
     52   };
     53 }
     54 char DeadMachineInstructionElim::ID = 0;
     55 char &llvm::DeadMachineInstructionElimID = DeadMachineInstructionElim::ID;
     56 
     57 INITIALIZE_PASS(DeadMachineInstructionElim, "dead-mi-elimination",
     58                 "Remove dead machine instructions", false, false)
     59 
     60 bool DeadMachineInstructionElim::isDead(const MachineInstr *MI) const {
     61   // Technically speaking inline asm without side effects and no defs can still
     62   // be deleted. But there is so much bad inline asm code out there, we should
     63   // let them be.
     64   if (MI->isInlineAsm())
     65     return false;
     66 
     67   // Don't delete frame allocation labels.
     68   if (MI->getOpcode() == TargetOpcode::LOCAL_ESCAPE)
     69     return false;
     70 
     71   // Don't delete instructions with side effects.
     72   bool SawStore = false;
     73   if (!MI->isSafeToMove(nullptr, SawStore) && !MI->isPHI())
     74     return false;
     75 
     76   // Examine each operand.
     77   for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
     78     const MachineOperand &MO = MI->getOperand(i);
     79     if (MO.isReg() && MO.isDef()) {
     80       unsigned Reg = MO.getReg();
     81       if (TargetRegisterInfo::isPhysicalRegister(Reg)) {
     82         // Don't delete live physreg defs, or any reserved register defs.
     83         if (LivePhysRegs.test(Reg) || MRI->isReserved(Reg))
     84           return false;
     85       } else {
     86         if (!MRI->use_nodbg_empty(Reg))
     87           // This def has a non-debug use. Don't delete the instruction!
     88           return false;
     89       }
     90     }
     91   }
     92 
     93   // If there are no defs with uses, the instruction is dead.
     94   return true;
     95 }
     96 
     97 bool DeadMachineInstructionElim::runOnMachineFunction(MachineFunction &MF) {
     98   if (skipFunction(*MF.getFunction()))
     99     return false;
    100 
    101   bool AnyChanges = false;
    102   MRI = &MF.getRegInfo();
    103   TRI = MF.getSubtarget().getRegisterInfo();
    104   TII = MF.getSubtarget().getInstrInfo();
    105 
    106   // Loop over all instructions in all blocks, from bottom to top, so that it's
    107   // more likely that chains of dependent but ultimately dead instructions will
    108   // be cleaned up.
    109   for (MachineBasicBlock &MBB : make_range(MF.rbegin(), MF.rend())) {
    110     // Start out assuming that reserved registers are live out of this block.
    111     LivePhysRegs = MRI->getReservedRegs();
    112 
    113     // Add live-ins from sucessors to LivePhysRegs. Normally, physregs are not
    114     // live across blocks, but some targets (x86) can have flags live out of a
    115     // block.
    116     for (MachineBasicBlock::succ_iterator S = MBB.succ_begin(),
    117            E = MBB.succ_end(); S != E; S++)
    118       for (const auto &LI : (*S)->liveins())
    119         LivePhysRegs.set(LI.PhysReg);
    120 
    121     // Now scan the instructions and delete dead ones, tracking physreg
    122     // liveness as we go.
    123     for (MachineBasicBlock::reverse_iterator MII = MBB.rbegin(),
    124          MIE = MBB.rend(); MII != MIE; ) {
    125       MachineInstr *MI = &*MII;
    126 
    127       // If the instruction is dead, delete it!
    128       if (isDead(MI)) {
    129         DEBUG(dbgs() << "DeadMachineInstructionElim: DELETING: " << *MI);
    130         // It is possible that some DBG_VALUE instructions refer to this
    131         // instruction.  They get marked as undef and will be deleted
    132         // in the live debug variable analysis.
    133         MI->eraseFromParentAndMarkDBGValuesForRemoval();
    134         AnyChanges = true;
    135         ++NumDeletes;
    136         MIE = MBB.rend();
    137         // MII is now pointing to the next instruction to process,
    138         // so don't increment it.
    139         continue;
    140       }
    141 
    142       // Record the physreg defs.
    143       for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
    144         const MachineOperand &MO = MI->getOperand(i);
    145         if (MO.isReg() && MO.isDef()) {
    146           unsigned Reg = MO.getReg();
    147           if (TargetRegisterInfo::isPhysicalRegister(Reg)) {
    148             // Check the subreg set, not the alias set, because a def
    149             // of a super-register may still be partially live after
    150             // this def.
    151             for (MCSubRegIterator SR(Reg, TRI,/*IncludeSelf=*/true);
    152                  SR.isValid(); ++SR)
    153               LivePhysRegs.reset(*SR);
    154           }
    155         } else if (MO.isRegMask()) {
    156           // Register mask of preserved registers. All clobbers are dead.
    157           LivePhysRegs.clearBitsNotInMask(MO.getRegMask());
    158         }
    159       }
    160       // Record the physreg uses, after the defs, in case a physreg is
    161       // both defined and used in the same instruction.
    162       for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
    163         const MachineOperand &MO = MI->getOperand(i);
    164         if (MO.isReg() && MO.isUse()) {
    165           unsigned Reg = MO.getReg();
    166           if (TargetRegisterInfo::isPhysicalRegister(Reg)) {
    167             for (MCRegAliasIterator AI(Reg, TRI, true); AI.isValid(); ++AI)
    168               LivePhysRegs.set(*AI);
    169           }
    170         }
    171       }
    172 
    173       // We didn't delete the current instruction, so increment MII to
    174       // the next one.
    175       ++MII;
    176     }
    177   }
    178 
    179   LivePhysRegs.clear();
    180   return AnyChanges;
    181 }
    182