[MachineDCE] Delete missed dead instructions after deleting PHI

[nemanjai]

Summary

Machine DCE does a linear bottom-up pass to detect dead instructions and delete them. The idea with the bottom-up traversal is to delete instructions before their inputs so that removal of a single user makes the def instruction dead.

This however does not work if the only user of an instruction is a PHI in a loop header. With this patch, DCE tracks instructions that have become dead when removing a PHI. At the end, if any of those still exist in their parent MBB, they're also deleted.

[efriedma]

In general, this pass isn't going to see uses before defs; it's not CFG-sensitive at all. This isn't specific to PHI nodes. For virtual registers, maybe we could be doing something like the IR RecursivelyDeleteTriviallyDeadInstructions, to make sure we catch everything? (Well, everything a simple DCE can catch; ADCE is probably overkill.)

That doesn't really extend to physreg defs, though; we don't currently record the information necessary. Not sure if we can do anything about that cheaply.

llvm/lib/CodeGen/DeadMachineInstructionElim.cpp

156

You can't use isDead() like this: it queries LivePhysRegs, which is only valid for the current MI.

llvm/lib/CodeGen/DeadMachineInstructionElim.cpp

 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();
+  SmallVector<MachineInstr *, 8> PotentiallyMissed;
 
   // 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();
 
for (MachineBasicBlock::reverse_iterator MII = MBB.rbegin(),
       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;
+        // If we just deleted a PHI, it is quite possible that it was an only
+        // user of a vreg defined by an instruction we already looked at. If so,
+        // delete those instructions as well.
+        if (MI->isPHI()) {
+          for (unsigned i = 1, e = MI->getNumOperands(); i != e; i += 2) {
+            Register FeedReg = MI->getOperand(i).getReg();
+            if (!Register::isVirtualRegister(FeedReg))
+              continue;
+            MachineInstr *FeedMI = MRI->getVRegDef(FeedReg);
+            if (!FeedMI || !isDead(FeedMI))
+              continue;
+            PotentiallyMissed.push_back(FeedMI);
+          }
+        }
         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();
for (MachineBasicBlock::reverse_iterator MII = MBB.rbegin(),
           if (Register::isPhysicalRegister(Reg)) {
             for (MCRegAliasIterator AI(Reg, TRI, true); AI.isValid(); ++AI)
               LivePhysRegs.set(*AI);
           }
         }
       }
     }
   }
+  for (MachineInstr *MI : PotentiallyMissed) {
+    if (!MI->getParent())
+      continue;
+    LLVM_DEBUG(dbgs() << "DeadMachineInstructionElim: DELETING: " << *MI);
+    MI->eraseFromParentAndMarkDBGValuesForRemoval();
+    AnyChanges = true;
+    ++NumDeletes;
+  }
 
   LivePhysRegs.clear();
   return AnyChanges;
 }

llvm/test/CodeGen/PowerPC/dce-phi-inputs.mir

+# RUN: llc -mtriple=powerpc64le-unknown-linux-gnu -mcpu=pwr9 %s -o - \
+# RUN:   -run-pass=dead-mi-elimination | FileCheck %s
+--- |
+  define dso_local signext i32 @test(i32* nocapture readonly %Arr) local_unnamed_addr {
+  entry:
+    %scevgep1 = getelementptr i32, i32* %Arr, i64 -1
+    %scevgep12 = bitcast i32* %scevgep1 to i8*
+    call void @llvm.set.loop.iterations.i64(i64 100)
+    br label %for.body
+
+  for.cond.cleanup:                                 ; preds = %for.body
+    ret i32 %add
+
+  for.body:                                         ; preds = %for.body, %entry
+    %Ret.06 = phi i32 [ 0, %entry ], [ %add, %for.body ]
+    %0 = phi i8* [ %scevgep12, %entry ], [ %1, %for.body ]
+    %1 = getelementptr i8, i8* %0, i64 4
+    %2 = bitcast i8* %1 to i32*
+    %3 = load i32, i32* %2, align 4
+    %add = add nsw i32 %3, %Ret.06
+    %4 = call i1 @llvm.loop.decrement.i64(i64 1)
+    br i1 %4, label %for.body, label %for.cond.cleanup
+  }
+
+  ; Function Attrs: noduplicate nounwind
+  declare void @llvm.set.loop.iterations.i64(i64)
+
+  ; Function Attrs: noduplicate nounwind
+  declare i1 @llvm.loop.decrement.i64(i64)
+...
+---
+name:            test
+alignment:       16
+exposesReturnsTwice: false
+legalized:       false
+regBankSelected: false
+selected:        false
+failedISel:      false
+tracksRegLiveness: true
+hasWinCFI:       false
+registers:
+  - { id: 0, class: g8rc, preferred-register: '' }
+  - { id: 1, class: gprc, preferred-register: '' }
+  - { id: 2, class: g8rc_and_g8rc_nox0, preferred-register: '' }
+  - { id: 3, class: g8rc, preferred-register: '' }
+  - { id: 4, class: gprc, preferred-register: '' }
+  - { id: 5, class: g8rc_and_g8rc_nox0, preferred-register: '' }
+  - { id: 6, class: gprc, preferred-register: '' }
+  - { id: 7, class: g8rc, preferred-register: '' }
+  - { id: 8, class: gprc, preferred-register: '' }
+  - { id: 9, class: g8rc_and_g8rc_nox0, preferred-register: '' }
+  - { id: 10, class: g8rc, preferred-register: '' }
+liveins:
+  - { reg: '$x3', virtual-reg: '%5' }
+frameInfo:
+  isFrameAddressTaken: false
+  isReturnAddressTaken: false
+  hasStackMap:     false
+  hasPatchPoint:   false
+  stackSize:       0
+  offsetAdjustment: 0
+  maxAlignment:    1
+  adjustsStack:    false
+  hasCalls:        false
+  stackProtector:  ''
+  maxCallFrameSize: 4294967295
+  cvBytesOfCalleeSavedRegisters: 0
+  hasOpaqueSPAdjustment: false
+  hasVAStart:      false
+  hasMustTailInVarArgFunc: false
+  localFrameSize:  0
+  savePoint:       ''
+  restorePoint:    ''
+fixedStack:      []
+stack:           []
+callSites:       []
+constants:       []
+machineFunctionInfo: {}
+body:             |
+  bb.0.entry:
+    successors: %bb.2(0x80000000)
+    liveins: $x3
+
+    %5:g8rc_and_g8rc_nox0 = COPY $x3
+    %0:g8rc = ADDI8 %5, -4
+    %7:g8rc = LI8 100
+    MTCTR8loop killed %7, implicit-def dead $ctr8
+    %6:gprc = LI 0
+    B %bb.2
+
+  bb.1.for.cond.cleanup:
+    %10:g8rc = EXTSW_32_64 %4
+    $x3 = COPY %10
+    BLR8 implicit $lr8, implicit $rm, implicit $x3
+
+  bb.2.for.body:
+    successors: %bb.2(0x7c000000), %bb.1(0x04000000)
+
+    ; CHECK: gprc = PHI
+    %1:gprc = PHI %6, %bb.0, %4, %bb.2
+    ; CHECK-NOT: g8rc_and_g8rc_nox0 = PHI
+    %2:g8rc_and_g8rc_nox0 = PHI %0, %bb.0, %3, %bb.2
+    ; CHECK: g8rc_and_g8rc_nox0 = LWZU
+    %8:gprc, %9:g8rc_and_g8rc_nox0 = LWZU 4, %5 :: (load 4 from %ir.2)
+    ; CHECK-NOT: g8rc = COPY
+    %3:g8rc = COPY %9
+    %4:gprc = nsw ADD4 killed %8, %1
+    BDNZ8 %bb.2, implicit-def dead $ctr8, implicit $ctr8
+    B %bb.1
+
+...