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   private:
     46     bool isDead(const MachineInstr *MI) const;
     47   };
     48 }
     49 char DeadMachineInstructionElim::ID = 0;
     50 char &llvm::DeadMachineInstructionElimID = DeadMachineInstructionElim::ID;
     51 
     52 INITIALIZE_PASS(DeadMachineInstructionElim, "dead-mi-elimination",
     53                 "Remove dead machine instructions", false, false)
     54 
     55 bool DeadMachineInstructionElim::isDead(const MachineInstr *MI) const {
     56   // Technically speaking inline asm without side effects and no defs can still
     57   // be deleted. But there is so much bad inline asm code out there, we should
     58   // let them be.
     59   if (MI->isInlineAsm())
     60     return false;
     61 
     62   // Don't delete frame allocation labels.
     63   if (MI->getOpcode() == TargetOpcode::LOCAL_ESCAPE)
     64     return false;
     65 
     66   // Don't delete instructions with side effects.
     67   bool SawStore = false;
     68   if (!MI->isSafeToMove(nullptr, SawStore) && !MI->isPHI())
     69     return false;
     70 
     71   // Examine each operand.
     72   for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
     73     const MachineOperand &MO = MI->getOperand(i);
     74     if (MO.isReg() && MO.isDef()) {
     75       unsigned Reg = MO.getReg();
     76       if (TargetRegisterInfo::isPhysicalRegister(Reg)) {
     77         // Don't delete live physreg defs, or any reserved register defs.
     78         if (LivePhysRegs.test(Reg) || MRI->isReserved(Reg))
     79           return false;
     80       } else {
     81         if (!MRI->use_nodbg_empty(Reg))
     82           // This def has a non-debug use. Don't delete the instruction!
     83           return false;
     84       }
     85     }
     86   }
     87 
     88   // If there are no defs with uses, the instruction is dead.
     89   return true;
     90 }
     91 
     92 bool DeadMachineInstructionElim::runOnMachineFunction(MachineFunction &MF) {
     93   if (skipOptnoneFunction(*MF.getFunction()))
     94     return false;
     95 
     96   bool AnyChanges = false;
     97   MRI = &MF.getRegInfo();
     98   TRI = MF.getSubtarget().getRegisterInfo();
     99   TII = MF.getSubtarget().getInstrInfo();
    100 
    101   // Loop over all instructions in all blocks, from bottom to top, so that it's
    102   // more likely that chains of dependent but ultimately dead instructions will
    103   // be cleaned up.
    104   for (MachineBasicBlock &MBB : make_range(MF.rbegin(), MF.rend())) {
    105     // Start out assuming that reserved registers are live out of this block.
    106     LivePhysRegs = MRI->getReservedRegs();
    107 
    108     // Add live-ins from sucessors to LivePhysRegs. Normally, physregs are not
    109     // live across blocks, but some targets (x86) can have flags live out of a
    110     // block.
    111     for (MachineBasicBlock::succ_iterator S = MBB.succ_begin(),
    112            E = MBB.succ_end(); S != E; S++)
    113       for (const auto &LI : (*S)->liveins())
    114         LivePhysRegs.set(LI.PhysReg);
    115 
    116     // Now scan the instructions and delete dead ones, tracking physreg
    117     // liveness as we go.
    118     for (MachineBasicBlock::reverse_iterator MII = MBB.rbegin(),
    119          MIE = MBB.rend(); MII != MIE; ) {
    120       MachineInstr *MI = &*MII;
    121 
    122       // If the instruction is dead, delete it!
    123       if (isDead(MI)) {
    124         DEBUG(dbgs() << "DeadMachineInstructionElim: DELETING: " << *MI);
    125         // It is possible that some DBG_VALUE instructions refer to this
    126         // instruction.  They get marked as undef and will be deleted
    127         // in the live debug variable analysis.
    128         MI->eraseFromParentAndMarkDBGValuesForRemoval();
    129         AnyChanges = true;
    130         ++NumDeletes;
    131         MIE = MBB.rend();
    132         // MII is now pointing to the next instruction to process,
    133         // so don't increment it.
    134         continue;
    135       }
    136 
    137       // Record the physreg defs.
    138       for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
    139         const MachineOperand &MO = MI->getOperand(i);
    140         if (MO.isReg() && MO.isDef()) {
    141           unsigned Reg = MO.getReg();
    142           if (TargetRegisterInfo::isPhysicalRegister(Reg)) {
    143             // Check the subreg set, not the alias set, because a def
    144             // of a super-register may still be partially live after
    145             // this def.
    146             for (MCSubRegIterator SR(Reg, TRI,/*IncludeSelf=*/true);
    147                  SR.isValid(); ++SR)
    148               LivePhysRegs.reset(*SR);
    149           }
    150         } else if (MO.isRegMask()) {
    151           // Register mask of preserved registers. All clobbers are dead.
    152           LivePhysRegs.clearBitsNotInMask(MO.getRegMask());
    153         }
    154       }
    155       // Record the physreg uses, after the defs, in case a physreg is
    156       // both defined and used in the same instruction.
    157       for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
    158         const MachineOperand &MO = MI->getOperand(i);
    159         if (MO.isReg() && MO.isUse()) {
    160           unsigned Reg = MO.getReg();
    161           if (TargetRegisterInfo::isPhysicalRegister(Reg)) {
    162             for (MCRegAliasIterator AI(Reg, TRI, true); AI.isValid(); ++AI)
    163               LivePhysRegs.set(*AI);
    164           }
    165         }
    166       }
    167 
    168       // We didn't delete the current instruction, so increment MII to
    169       // the next one.
    170       ++MII;
    171     }
    172   }
    173 
    174   LivePhysRegs.clear();
    175   return AnyChanges;
    176 }
    177