[PHIElimination] Fix accounting for undef uses when updating LiveVariables

[foad]

Summary

PHI elimination updates LiveVariables info as described here:

// We only need to update the LiveVariables kill of SrcReg if this was the
// last PHI use of SrcReg to be lowered on this CFG edge and it is not live
// out of the predecessor. We can also ignore undef sources.

Unfortunately if the last use also happened to be an undef use then it
would fail to update the LiveVariables at all. Fix this by not counting
undef uses in the VRegPHIUse map.

Thanks to Mikael Holmén for the test case!

[MatzeB]

LGTM

llvm/lib/CodeGen/PHIElimination.cpp

private:
     // These functions are temporary abstractions around LiveVariables and
     // LiveIntervals, so they can go away when LiveVariables does.
     bool isLiveIn(Register Reg, const MachineBasicBlock *MBB);
     bool isLiveOutPastPHIs(Register Reg, const MachineBasicBlock *MBB);
 
     using BBVRegPair = std::pair<unsigned, Register>;
     using VRegPHIUse = DenseMap<BBVRegPair, unsigned>;
 
+    // Count the number of non-undef PHI uses of each register in each BB.
     VRegPHIUse VRegPHIUseCount;
 
     // Defs of PHI sources which are implicit_def.
     SmallPtrSet<MachineInstr*, 4> ImpDefs;
 
     // Map reusable lowered PHI node -> incoming join register.
     using LoweredPHIMap =
         DenseMap<MachineInstr*, unsigned, MachineInstrExpressionTrait>;
if (DestLI.endIndex().isDead()) {
       DestLI.removeSegment(MBBStartIndex, DestCopyIndex.getRegSlot());
       VNInfo *DestVNI = DestLI.getVNInfoAt(DestCopyIndex.getRegSlot());
       assert(DestVNI && "PHI destination should be live at its definition.");
       DestVNI->def = DestCopyIndex.getRegSlot();
     }
   }
 
   // Adjust the VRegPHIUseCount map to account for the removal of this PHI node.
-  for (unsigned i = 1; i != MPhi->getNumOperands(); i += 2)
-    --VRegPHIUseCount[BBVRegPair(MPhi->getOperand(i+1).getMBB()->getNumber(),
-                                 MPhi->getOperand(i).getReg())];
+  for (unsigned i = 1; i != MPhi->getNumOperands(); i += 2) {
+    if (!MPhi->getOperand(i).isUndef()) {
+      --VRegPHIUseCount[BBVRegPair(
+          MPhi->getOperand(i + 1).getMBB()->getNumber(),
+    }
+  }
 
   // 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) {
     Register SrcReg = MPhi->getOperand(i * 2 + 1).getReg();
     unsigned SrcSubReg = MPhi->getOperand(i*2+1).getSubReg();
     bool SrcUndef = MPhi->getOperand(i*2+1).isUndef() ||
void PHIElimination::LowerPHINode(MachineBasicBlock &MBB,
   }
 }
 
 /// analyzePHINodes - Gather information about the PHI nodes in here. In
 /// particular, we want to map the number of uses of a virtual register which is
 /// used in a PHI node. We map that to the BB the vreg is coming from. This is
 /// used later to determine when the vreg is killed in the BB.
 void PHIElimination::analyzePHINodes(const MachineFunction& MF) {
-  for (const auto &MBB : MF)
+  for (const auto &MBB : MF) {
     for (const auto &BBI : MBB) {
       if (!BBI.isPHI())
         break;
-      for (unsigned i = 1, e = BBI.getNumOperands(); i != e; i += 2)
-        ++VRegPHIUseCount[BBVRegPair(BBI.getOperand(i+1).getMBB()->getNumber(),
-                                     BBI.getOperand(i).getReg())];
+      for (unsigned i = 1, e = BBI.getNumOperands(); i != e; i += 2) {
+        if (!BBI.getOperand(i).isUndef()) {
+          ++VRegPHIUseCount[BBVRegPair(
+              BBI.getOperand(i + 1).getMBB()->getNumber(),
         }
       }
+    }
+  }
+}
 
 bool PHIElimination::SplitPHIEdges(MachineFunction &MF,
                                    MachineBasicBlock &MBB,
                                    MachineLoopInfo *MLI,
                                    std::vector<SparseBitVector<>> *LiveInSets) {
   if (MBB.empty() || !MBB.front().isPHI() || MBB.isEHPad())
     return false;   // Quick exit for basic blocks without PHIs.
 

llvm/test/CodeGen/X86/phielim-undef.mir

+# NOTE: Assertions have been autogenerated by utils/update_mir_test_checks.py
+# RUN: llc -mtriple=x86_64-- -verify-machineinstrs -o - %s -run-pass=livevars,phi-node-elimination,twoaddressinstruction | FileCheck %s
+
+--- |
+  @b114 = external global i16, align 1
+
+  define void @f245() {
+  entry:
+    unreachable
+  }
+...
+---
+name: f245
+tracksRegLiveness: true
+body: |
+  ; CHECK-LABEL: name: f245
+  ; CHECK: bb.0:
+  ; CHECK-NEXT:   successors: %bb.5(0x40000000), %bb.1(0x40000000)
+  ; CHECK-NEXT: {{  $}}
+  ; CHECK-NEXT:   [[MOV64rm:%[0-9]+]]:gr64 = MOV64rm $rip, 1, $noreg, target-flags(x86-gotpcrel) @b114, $noreg
+  ; CHECK-NEXT:   [[MOV16rm:%[0-9]+]]:gr16 = MOV16rm killed [[MOV64rm]], 1, $noreg, 0, $noreg :: (load (s16) from @b114, align 1)
+  ; CHECK-NEXT:   TEST8ri undef %2:gr8, 1, implicit-def $eflags
+  ; CHECK-NEXT:   JCC_1 %bb.5, 5, implicit killed $eflags
+  ; CHECK-NEXT: {{  $}}
+  ; CHECK-NEXT: bb.1:
+  ; CHECK-NEXT:   successors: %bb.2(0x80000000)
+  ; CHECK-NEXT: {{  $}}
+  ; CHECK-NEXT:   [[COPY:%[0-9]+]]:gr16 = COPY killed [[MOV16rm]]
+  ; CHECK-NEXT:   JMP_1 %bb.2
+  ; CHECK-NEXT: {{  $}}
+  ; CHECK-NEXT: bb.2:
+  ; CHECK-NEXT:   successors: %bb.4(0x40000000), %bb.3(0x40000000)
+  ; CHECK-NEXT: {{  $}}
+  ; CHECK-NEXT:   dead %5:gr16 = IMPLICIT_DEF
+  ; CHECK-NEXT:   [[COPY1:%[0-9]+]]:gr16 = COPY killed [[COPY]]
+  ; CHECK-NEXT:   TEST8ri undef %7:gr8, 1, implicit-def $eflags
+  ; CHECK-NEXT:   JCC_1 %bb.4, 5, implicit killed $eflags
+  ; CHECK-NEXT:   JMP_1 %bb.3
+  ; CHECK-NEXT: {{  $}}
+  ; CHECK-NEXT: bb.3:
+  ; CHECK-NEXT:   successors: %bb.6(0x40000000), %bb.4(0x40000000)
+  ; CHECK-NEXT: {{  $}}
+  ; CHECK-NEXT:   [[MOV32r0_:%[0-9]+]]:gr32 = MOV32r0 implicit-def dead $eflags
+  ; CHECK-NEXT:   dead %9:gr16 = COPY killed [[MOV32r0_]].sub_16bit
+  ; CHECK-NEXT:   CMP16ri8 killed [[COPY1]], 0, implicit-def $eflags
+  ; CHECK-NEXT:   JCC_1 %bb.6, 5, implicit killed $eflags
+  ; CHECK-NEXT: {{  $}}
+  ; CHECK-NEXT: bb.4:
+  ; CHECK-NEXT:   successors: %bb.2(0x80000000)
+  ; CHECK-NEXT: {{  $}}
+  ; CHECK-NEXT:   [[DEF:%[0-9]+]]:gr16 = IMPLICIT_DEF
+  ; CHECK-NEXT:   JMP_1 %bb.2
+  ; CHECK-NEXT: {{  $}}
+  ; CHECK-NEXT: bb.5:
+  ; CHECK-NEXT:   RETQ
+  ; CHECK-NEXT: {{  $}}
+  ; CHECK-NEXT: bb.6:
+  bb.0:
+    successors: %bb.6(0x40000000), %bb.1(0x40000000)
+
+    %5:gr64 = MOV64rm $rip, 1, $noreg, target-flags(x86-gotpcrel) @b114, $noreg
+    %6:gr16 = MOV16rm killed %5, 1, $noreg, 0, $noreg :: (load (s16) from @b114, align 1)
+    TEST8ri undef %4:gr8, 1, implicit-def $eflags
+    JCC_1 %bb.6, 5, implicit killed $eflags
+
+  bb.1:
+    successors: %bb.2(0x80000000)
+
+    JMP_1 %bb.2
+
+  bb.2:
+    successors: %bb.5(0x40000000), %bb.4(0x40000000)
+
+    %1:gr16 = PHI %6, %bb.1, undef %10:gr16, %bb.5
+    dead %2:gr16 = PHI undef %6, %bb.1, undef %3:gr16, %bb.5
+    TEST8ri undef %7:gr8, 1, implicit-def $eflags
+    JCC_1 %bb.5, 5, implicit killed $eflags
+    JMP_1 %bb.4
+
+  bb.4:
+    successors: %bb.7(0x40000000), %bb.5(0x40000000)
+
+    %8:gr32 = MOV32r0 implicit-def dead $eflags
+    %9:gr16 = COPY killed %8.sub_16bit
+    CMP16ri8 killed %1, 0, implicit-def $eflags
+    JCC_1 %bb.7, 5, implicit killed $eflags
+
+  bb.5:
+    successors: %bb.2(0x80000000)
+
+    JMP_1 %bb.2
+
+  bb.6:
+    RETQ
+
+  bb.7:
+...