[MachineDCE] Move machine DCE into using LivePhysRegs infrastructure

[kariddi]

Summary

MachineDCE adds to the live physical registers the live in registers
of the successor blocks, but it doesn't really add the subregisters
of those, which are also live, causing potentially instructions subregs
only to be deleted.
Changing MachineDCE into using LivePhysRegs that does the same thing
the pass is doing manually while at the same time not having the same bug
described above.

[arsenm]

llvm/lib/CodeGen/DeadMachineInstructionElim.cpp

123–124

RegAliasIterator? also need the super regs?

[arsenm]

llvm/lib/CodeGen/DeadMachineInstructionElim.cpp

123–124

Wait, actually why is this code here at all? There is already a LivePhysRegs class which is what I initially assumed this was

[kariddi]

llvm/lib/CodeGen/DeadMachineInstructionElim.cpp

123–124

1. I don't think the all the aliases should be considered "live". I think that if a register is not in the "live" list then it means that as a unit it is not considered live. Like, the subregisters here, if they are not in the list it means that they are not used as subregisters themselves in the block (until they are defined themselves potentially in the block). They can be live though as part of the a bigger entity

2. Yeah, this code doesn't use that. I just fixed the problems here, but its a good point, maybe we should port this code to use LivePhysReg. I'll take a stab at that.

[kariddi]

Moving to LivePhysReg

[kariddi]

use addLiveOuts()

[kariddi]

ping

[arsenm]

LGTM

[arsenm]

D124168 should replace this

llvm/lib/CodeGen/DeadMachineInstructionElim.cpp

 //===- DeadMachineInstructionElim.cpp - Remove dead machine instructions --===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 //
 // This is an extremely simple MachineInstr-level dead-code-elimination pass.
 //
 //===----------------------------------------------------------------------===//
 
 #include "llvm/ADT/Statistic.h"
+#include "llvm/CodeGen/LivePhysRegs.h"
 #include "llvm/CodeGen/MachineFunctionPass.h"
 #include "llvm/CodeGen/MachineRegisterInfo.h"
 #include "llvm/CodeGen/Passes.h"
 #include "llvm/CodeGen/TargetSubtargetInfo.h"
 #include "llvm/InitializePasses.h"
 #include "llvm/Pass.h"
 #include "llvm/Support/Debug.h"
 #include "llvm/Support/raw_ostream.h"
 
 using namespace llvm;
 
 #define DEBUG_TYPE "dead-mi-elimination"
 
 STATISTIC(NumDeletes,          "Number of dead instructions deleted");
 
 namespace {
   class DeadMachineInstructionElim : public MachineFunctionPass {
     bool runOnMachineFunction(MachineFunction &MF) override;
 
     const TargetRegisterInfo *TRI;
     const MachineRegisterInfo *MRI;
     const TargetInstrInfo *TII;
-    BitVector LivePhysRegs;
+    LivePhysRegs LiveRegs;
 
   public:
     static char ID; // Pass identification, replacement for typeid
     DeadMachineInstructionElim() : MachineFunctionPass(ID) {
      initializeDeadMachineInstructionElimPass(*PassRegistry::getPassRegistry());
     }
 
     void getAnalysisUsage(AnalysisUsage &AU) const override {
bool DeadMachineInstructionElim::isDead(const MachineInstr *MI) const {
 
   // Examine each operand.
   for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
     const MachineOperand &MO = MI->getOperand(i);
     if (MO.isReg() && MO.isDef()) {
       Register Reg = MO.getReg();
       if (Register::isPhysicalRegister(Reg)) {
         // Don't delete live physreg defs, or any reserved register defs.
-        if (LivePhysRegs.test(Reg) || MRI->isReserved(Reg))
+        if (!LiveRegs.available(*MRI, Reg) || MRI->isReserved(Reg))
           return false;
       } else {
         if (MO.isDead()) {
 #ifndef NDEBUG
           // Sanity check on uses of this dead register. All of them should be
           // 'undef'.
           for (auto &U : MRI->use_nodbg_operands(Reg))
             assert(U.isUndef() && "'Undef' use on a 'dead' register is found!");

 bool DeadMachineInstructionElim::runOnMachineFunction(MachineFunction &MF) {
   if (skipFunction(MF.getFunction()))
     return false;
 
   bool AnyChanges = false;
   MRI = &MF.getRegInfo();
   TRI = MF.getSubtarget().getRegisterInfo();
   TII = MF.getSubtarget().getInstrInfo();
+  LiveRegs.init(*TRI);
 
   // Loop over all instructions in all blocks, from bottom to top, so that it's
   // more likely that chains of dependent but ultimately dead instructions will
   // be cleaned up.
   for (MachineBasicBlock &MBB : make_range(MF.rbegin(), MF.rend())) {
-    // Start out assuming that reserved registers are live out of this block.
-    LivePhysRegs = MRI->getReservedRegs();
 
-    // Add live-ins from successors to LivePhysRegs. Normally, physregs are not
-    // live across blocks, but some targets (x86) can have flags live out of a
-    // block.
-    for (MachineBasicBlock::succ_iterator S = MBB.succ_begin(),
-           E = MBB.succ_end(); S != E; S++)
-      for (const auto &LI : (*S)->liveins())
-        LivePhysRegs.set(LI.PhysReg);
+    // Add live-ins from successors to LivePhysRegs.
+    LiveRegs.addLiveOuts(MBB);
 
     // Now scan the instructions and delete dead ones, tracking physreg
     // liveness as we go.
     for (MachineBasicBlock::reverse_iterator MII = MBB.rbegin(),
          MIE = MBB.rend(); MII != MIE; ) {
       MachineInstr *MI = &*MII++;
 
       // If the instruction is dead, delete it!
       if (isDead(MI)) {
         LLVM_DEBUG(dbgs() << "DeadMachineInstructionElim: DELETING: " << *MI);
         // It is possible that some DBG_VALUE instructions refer to this
         // instruction.  They get marked as undef and will be deleted
         // in the live debug variable analysis.
         MI->eraseFromParentAndMarkDBGValuesForRemoval();
         AnyChanges = true;
         ++NumDeletes;
         continue;
       }
 
-      // Record the physreg defs.
-      for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
-        const MachineOperand &MO = MI->getOperand(i);
-        if (MO.isReg() && MO.isDef()) {
-          Register Reg = MO.getReg();
-          if (Register::isPhysicalRegister(Reg)) {
-            // Check the subreg set, not the alias set, because a def
-            // of a super-register may still be partially live after
-            // this def.
-            for (MCSubRegIterator SR(Reg, TRI,/*IncludeSelf=*/true);
-                 SR.isValid(); ++SR)
-              LivePhysRegs.reset(*SR);
-          }
-        } else if (MO.isRegMask()) {
-          // Register mask of preserved registers. All clobbers are dead.
-          LivePhysRegs.clearBitsNotInMask(MO.getRegMask());
-        }
-      }
-      // Record the physreg uses, after the defs, in case a physreg is
-      // both defined and used in the same instruction.
-      for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
-        const MachineOperand &MO = MI->getOperand(i);
-        if (MO.isReg() && MO.isUse()) {
-          Register Reg = MO.getReg();
-          if (Register::isPhysicalRegister(Reg)) {
-            for (MCRegAliasIterator AI(Reg, TRI, true); AI.isValid(); ++AI)
-              LivePhysRegs.set(*AI);
-          }
-        }
-      }
+      // Update live-regs by passing past this instruction and recording
+      // uses/defs. in a backward fashion.
+      LiveRegs.stepBackward(*MI);
     }
   }
 
-  LivePhysRegs.clear();
+  LiveRegs.clear();
   return AnyChanges;
 }

llvm/test/CodeGen/Hexagon/dead-code-elim-sub-reg-livein.mir

+# NOTE: Assertions have been autogenerated by utils/update_mir_test_checks.py
+# RUN: llc -march=hexagon -run-pass dead-mi-elimination -verify-machineinstrs %s -o - | FileCheck %s
+
+# DeadMachineCodeElimination needs to add the subregisters of the live-ins of a block to avoid
+# deleting instructions writing to parts of a super register.
+# This test is making sure that this happens.
+
+---
+name: livein_sub_reg_not_preserved
+tracksRegLiveness: true
+
+body: |
+  ; CHECK-LABEL: name: livein_sub_reg_not_preserved
+  ; CHECK: bb.0:
+  ; CHECK:   successors: %bb.1(0x80000000)
+  ; CHECK:   liveins: $d0, $r2
+  ; CHECK: bb.1:
+  ; CHECK:   successors: %bb.1(0x80000000)
+  ; CHECK:   liveins: $d0, $r2
+  ; CHECK:   $r0 = A2_tfrsi 1
+  ; CHECK:   A2_nop implicit-def $p0
+  ; CHECK:   J2_jumpt killed $p0, %bb.1, implicit-def dead $pc
+  ; CHECK:   J2_jumpr $r31, implicit-def dead $pc
+  bb.0:
+    liveins: $d0, $r2
+    successors: %bb.1
+
+  bb.1:
+    successors: %bb.1
+    liveins: $d0, $r2
+    $r0 = A2_tfrsi 1
+    A2_nop implicit-def $p0
+    J2_jumpt killed $p0, %bb.1, implicit-def dead $pc
+    J2_jumpr $r31, implicit-def dead $pc
+...