[PHIElimination] Lower a PHI node with only undef uses as IMPLICIT_DEF

[bjope]

Summary

The lowering of PHI nodes used to detect if all inputs originated
from IMPLICIT_DEF's. If so the PHI node was replaced by an
IMPLICIT_DEF. Now we also consider undef uses when checking the
inputs. So if all inputs are implicitly defined or undef we
lower the PHI to an IMPLICIT_DEF. This makes
PHIElimination::LowerPHINode more consistent as it checks
both implicit and undef properties at later stages.

[bjope]

This is slightly related to https://bugs.llvm.org/show_bug.cgi?id=39085, but this patch is supposed to focus on getting IMPLICIT_DEF when all PHI inputs are undefined.
The PR is about the problem with updating "killed" that is mentioned in the "bar" part of the test case.

[MatzeB]

The patch on its own makes sense to me, so LGTM (comment below).

I didn't know PHIElimination looks for IMPLICIT_DEFs, do you have an idea why that is given that we run ProcessImplicitDefs immediately before PHIElimination and it has a rule to eliminate phi-nodes with all implicit-def inputs too...

lib/CodeGen/PHIElimination.cpp

225–226 ↗

(On Diff #167152)

If we touch this function anyway, should we take the opportunity to switch to a more modern style:

static bool isSourceUndefined(const MachineInstr &MPhi,
                              const MachineRegisterInfo &MRI) {
  for (unsigned I = 1, E = MPhi->getNumOperands(); I != E; I += 2) {
    const MachineOperand &MO = MPhi->getOperand(I);
    if (!isImplicitlyDefined(MO.getReg(), MRI) && !MO.isUndef())
      return false;
  }
  return true;
}

[MatzeB]

lib/CodeGen/PHIElimination.cpp

225 ↗

(On Diff #167152)

how about naming this allPhiOperandsUndefined?

[bjope]

In D52558#1248133, @MatzeB wrote:

The patch on its own makes sense to me, so LGTM (comment below).

I didn't know PHIElimination looks for IMPLICIT_DEFs, do you have an idea why that is given that we run ProcessImplicitDefs immediately before PHIElimination and it has a rule to eliminate phi-nodes with all implicit-def inputs too...

Probably because ProcessImplicitDefs only is used for optimized regalloc (we do not add that pass in TargetPassConfig::addFastRegAlloc). So for "fast" we still have lots of IMPLICIT_DEF:s lingering around.
For "optimized" we run ProcessImplicitDefs (remove lots of IMPLICIT_DEF:s and propagate undef to uses) before PHIElimination, so this is when we can find undef instead of IMPLICIT_DEF on the PHI inputs.

ProcessImplicitDefs could be taught to also consider a PHI with only undef inputs as an IMPLICIT_DEF (and the same for COPY/INSERT_SUBREG/REG_SEQUENCE). That way we could clean up even more things already before PHIElimination in the optimized pipeline. Now the IMPLICIT_DEF inserted by PHIElimination isn't eliminated in the same way as if we had executed ProcessImplicitDefs after PHIEliminiation (which currently isn't possible since ProcessImplicitDefs requires SSA).
On the other hand, I don't know how important it is to eliminate IMPLICIT_DEF:s. The Coalescer and RegAlloc need to know about IMPLICIT_DEF:s, so isn't copies of undefined values removed anyway? So why do we run ProcessImplicitDefs at all?

[bjope]

Minor refactoring/renaming as suggested by Matze.

[MatzeB]

In D52558#1249214, @bjope wrote:

Minor refactoring/renaming as suggested by Matze.

BTW: This is still good to go, no need for further review. (I often approve patches with small issues remaining in cases where I trust the author to address the small issues correctly).

[bjope]

In D52558#1249265, @MatzeB wrote:

In D52558#1249214, @bjope wrote:

Minor refactoring/renaming as suggested by Matze.

BTW: This is still good to go, no need for further review. (I often approve patches with small issues remaining in cases where I trust the author to address the small issues correctly).

Great, I kind of imagined that it was good to go, but wanted to publish my pre-commit updates anyway (I do not have time to monitor build bots today so I'll commit this later).
Thanks for the review!

llvm/trunk/lib/CodeGen/PHIElimination.cpp

MachineBasicBlock::iterator LastPHIIt =
     std::prev(MBB.SkipPHIsAndLabels(MBB.begin()));
 
   while (MBB.front().isPHI())
     LowerPHINode(MBB, LastPHIIt);
 
   return true;
 }
 
-/// isImplicitlyDefined - Return true if all defs of VirtReg are implicit-defs.
+/// Return true if all defs of VirtReg are implicit-defs.
 /// This includes registers with no defs.
 static bool isImplicitlyDefined(unsigned VirtReg,
-                                const MachineRegisterInfo *MRI) {
-  for (MachineInstr &DI : MRI->def_instructions(VirtReg))
+                                const MachineRegisterInfo &MRI) {
+  for (MachineInstr &DI : MRI.def_instructions(VirtReg))
     if (!DI.isImplicitDef())
       return false;
   return true;
 }
 
-/// isSourceDefinedByImplicitDef - Return true if all sources of the phi node
-/// are implicit_def's.
-static bool isSourceDefinedByImplicitDef(const MachineInstr *MPhi,
-                                         const MachineRegisterInfo *MRI) {
-  for (unsigned i = 1; i != MPhi->getNumOperands(); i += 2)
-    if (!isImplicitlyDefined(MPhi->getOperand(i).getReg(), MRI))
+/// Return true if all sources of the phi node are implicit_def's, or undef's.
+static bool allPhiOperandsUndefined(const MachineInstr &MPhi,
+                                    const MachineRegisterInfo &MRI) {
+  for (unsigned I = 1, E = MPhi.getNumOperands(); I != E; I += 2) {
+    const MachineOperand &MO = MPhi.getOperand(I);
+    if (!isImplicitlyDefined(MO.getReg(), MRI) && !MO.isUndef())
       return false;
+  }
   return true;
 }
-
 /// LowerPHINode - Lower the PHI node at the top of the specified block.
 void PHIElimination::LowerPHINode(MachineBasicBlock &MBB,
                                   MachineBasicBlock::iterator LastPHIIt) {
   ++NumLowered;
 
   MachineBasicBlock::iterator AfterPHIsIt = std::next(LastPHIIt);
 
   // Unlink the PHI node from the basic block, but don't delete the PHI yet.
   MachineInstr *MPhi = MBB.remove(&*MBB.begin());
 
   unsigned NumSrcs = (MPhi->getNumOperands() - 1) / 2;
   unsigned DestReg = MPhi->getOperand(0).getReg();
   assert(MPhi->getOperand(0).getSubReg() == 0 && "Can't handle sub-reg PHIs");
   bool isDead = MPhi->getOperand(0).isDead();
 
   // Create a new register for the incoming PHI arguments.
   MachineFunction &MF = *MBB.getParent();
   unsigned IncomingReg = 0;
   bool reusedIncoming = false;  // Is IncomingReg reused from an earlier PHI?
 
   // Insert a register to register copy at the top of the current block (but
   // after any remaining phi nodes) which copies the new incoming register
   // into the phi node destination.
   const TargetInstrInfo *TII = MF.getSubtarget().getInstrInfo();
-  if (isSourceDefinedByImplicitDef(MPhi, MRI))
-    // If all sources of a PHI node are implicit_def, just emit an
+  if (allPhiOperandsUndefined(*MPhi, *MRI))
+    // If all sources of a PHI node are implicit_def or undef uses, just emit an
     // implicit_def instead of a copy.
     BuildMI(MBB, AfterPHIsIt, MPhi->getDebugLoc(),
             TII->get(TargetOpcode::IMPLICIT_DEF), DestReg);
   else {
     // Can we reuse an earlier PHI node? This only happens for critical edges,
     // typically those created by tail duplication.
     unsigned &entry = LoweredPHIs[MPhi];
     if (entry) {
void PHIElimination::LowerPHINode(MachineBasicBlock &MBB,
 
   // Now loop over all of the incoming arguments, changing them to copy into the
   // IncomingReg register in the corresponding predecessor basic block.
   SmallPtrSet<MachineBasicBlock*, 8> MBBsInsertedInto;
   for (int i = NumSrcs - 1; i >= 0; --i) {
     unsigned SrcReg = MPhi->getOperand(i*2+1).getReg();
     unsigned SrcSubReg = MPhi->getOperand(i*2+1).getSubReg();
     bool SrcUndef = MPhi->getOperand(i*2+1).isUndef() ||
-      isImplicitlyDefined(SrcReg, MRI);
+      isImplicitlyDefined(SrcReg, *MRI);
     assert(TargetRegisterInfo::isVirtualRegister(SrcReg) &&
            "Machine PHI Operands must all be virtual registers!");
 
     // Get the MachineBasicBlock equivalent of the BasicBlock that is the source
     // path the PHI.
     MachineBasicBlock &opBlock = *MPhi->getOperand(i*2+2).getMBB();
 
     // Check to make sure we haven't already emitted the copy for this block.

llvm/trunk/test/CodeGen/AMDGPU/phi-elimination-assertion.mir

+# RUN: llc -mtriple amdgcn -run-pass livevars -run-pass phi-node-elimination -o - %s | FileCheck %s
+
+################################################################################
+# This test used to hit an assert in PHIElimination:
+#  PHIElimination::LowerPHINode(llvm::MachineBasicBlock&, llvm::MachineBasicBlock::iterator): Assertion `KillInst->readsRegister(SrcReg) && "Cannot find kill instruction"'
+
+---
+name:            foo
+tracksRegLiveness: true
+body:             |
+  bb.0:
+    S_CBRANCH_SCC0 %bb.2, implicit undef $scc
+
+  bb.1:
+    %1:sreg_32_xm0 = S_MOV_B32 255
+    S_BRANCH %bb.3
+
+  bb.2:
+    %2:sreg_32_xm0 = S_MOV_B32 254
+
+  bb.3:
+    dead %3:sreg_32_xm0 = PHI undef %2, %bb.2, undef %1, %bb.1
+    %4:sreg_32_xm0 = PHI %2, %bb.2, %1, %bb.1
+    S_NOP 0, implicit %4
+...
+
+# CHECK-LABEL: name:            foo
+# CHECK:   bb.3:
+# CHECK-NEXT:     %3:sreg_32_xm0 = COPY killed %4
+# CHECK-NEXT:     dead %2:sreg_32_xm0 = IMPLICIT_DEF
+# CHECK-NEXT:     S_NOP 0, implicit killed %3
+
+
+################################################################################
+# Similar test as above, but with swapped order for the PHI nodes.
+# With this PHI node order we did not hit the assert, but we used to get
+#
+#  bb.3:
+#    dead %3:sreg_32_xm0 = COPY killed %4
+#    %2:sreg_32_xm0 = COPY %4
+#    S_NOP 0, implicit killed %2
+#
+# which looks weird regarding killed flags for %4.
+
+---
+name:            bar
+tracksRegLiveness: true
+body:             |
+  bb.0:
+    S_CBRANCH_SCC0 %bb.2, implicit undef $scc
+
+  bb.1:
+    %1:sreg_32_xm0 = S_MOV_B32 255
+    S_BRANCH %bb.3
+
+  bb.2:
+    %2:sreg_32_xm0 = S_MOV_B32 254
+
+  bb.3:
+    %4:sreg_32_xm0 = PHI %2, %bb.2, %1, %bb.1
+    dead %3:sreg_32_xm0 = PHI undef %2, %bb.2, undef %1, %bb.1
+    S_NOP 0, implicit %4
+...
+
+# CHECK-LABEL: name:            bar
+# CHECK:   bb.3:
+# CHECK-NEXT:     dead %3:sreg_32_xm0 = IMPLICIT_DEF
+# CHECK-NEXT:     %2:sreg_32_xm0 = COPY killed %4
+# CHECK-NEXT:     S_NOP 0, implicit killed %2