[MachineVerifier] Handle the PHI node for verifyLiveVariables()

[ZhangKang]

Summary

When doing MachineVerifier for LiveVariables, the MachineVerifier pass will calculate the LiveVariables,
and compares the result with the result livevars pass gave. If they are different, verifyLiveVariables()
will give error.
But when we calculate the LiveVariables in MachineVerifier, we don't consider the PHI node, while livevars
considers, so we will get different result and verifyLiveVariables() will be failed.
Now, we don't enable the verificatoin for LiveVariables, so we haven't gotten the failure for verifyLiveVariables().

For below case:

48 body:             |
49   bb.0.entry:
50     successors: %bb.1(0x80000000)
51     liveins: $x3
52
53     %4:g8rc_and_g8rc_nox0 = COPY killed $x3
54     %0:g8rc = LD 0, %4 :: (dereferenceable load 8 from %ir.p)
55
56   bb.1.loop:
57     successors: %bb.1(0x20000000), %bb.2(0x60000000)
58
59     %1:g8rc_and_g8rc_nox0 = PHI %0, %bb.0, %2, %bb.1, %3, %bb.3, %2, %bb.2
60     %5:gprc = LBZ 0, %1 :: (load 1 from %ir.0)
61     %6:crrc = CMPWI killed %5, 0
62     %7:crbitrc = COPY killed %6.sub_eq
63     %2:g8rc = nuw ADDI8 %1, 1
64     STD %2, 0, %4 :: (store 8 into %ir.p)
65     %8:gprc = LBZ 1, %1 :: (load 1 from %ir.incdec.ptr)
66     BCn killed %7, %bb.1
67     B %bb.2
68
69   bb.2.loop:
70     successors: %bb.3(0x55555555), %bb.1(0x2aaaaaab)
71
72     %9:crrc = CMPWI killed %8, 0
73     %10:crbitrc = COPY killed %9.sub_eq
74     BC killed %10, %bb.1
75     B %bb.3
76
77   bb.3.if.then3:
78     successors: %bb.1(0x80000000)
79
80     %3:g8rc = nuw ADDI8 killed %1, 2
81     STD %3, 0, %4 :: (store 8 into %ir.p)
82     B %bb.1

We will get below error:

# Bad machine code: LiveVariables: Block should not be in AliveBlocks
# - function:    zext_free
# - basic block: %bb.2 loop
# Virtual register %2 is not needed live through the block.
# LLVM ERROR: Found 1 machine code errors.

But in fact, %2 is should live through the %bb.2. In the line 59 for PHI, %2 can be
from %bb.1 or %bb.2, and %2 is defined in %bb.1, so %2 is live through %bb2, not live
through %bb1.

Below is the liveVariables info for above case:

Reg: %1  Alive in blocks: 2,
  Killed by:
    #0: %3:g8rc = nuw ADDI8 killed %1:g8rc_and_g8rc_nox0, 2

Reg: %2  Alive in blocks: 2,
  Killed by: No instructions.

Reg: %4  Alive in blocks: 1, 2, 3,
  Killed by: No instructions.

This patch can fix 210 verification error for LiveVariables.

[ZhangKang]

@dexonsmith Do you have any comments for this patch?

[aprantl]

llvm/test/CodeGen/PowerPC/livevars-crash2.mir

2

A test that doesn't CHECK anything is almost entirely useless. It will succeed even if you symlink llc to /bin/true. Without a CHECK there is zero indication about what code path is supposed to be covered by it, so future maintainers will not know what aspect to preserve when updating the test. Please try to add a meaningful CHECK or delete the test.

[ZhangKang]

Add CHECK for the case.

[ZhangKang]

llvm/test/CodeGen/PowerPC/livevars-crash2.mir

2

Have added CHECK for the test case.

[ZhangKang]

ping...

[ZhangKang]

ping. @thegameg @qcolombet , do you have any comments for this patch?

[bjope]

llvm/lib/CodeGen/MachineVerifier.cpp

135–136

Add a comment here that vregsLiveIn doesn't include regs that only are used by PHI nodes.

2306

Can't you just simply loop over the PHI nodes belonging to MBB here, finding all the PHI-related <vreg, pred> pairs.
That should give you all the additional vregs that should be live in (that earlier has been left our from the vregsLiveIn map), and from which predecessors the value should be required.

That way you do not need the PHIVarFrom map (and being even more dependant on what visitMachineInstrBefore is doing). I mean the map is only caching the information stored in the PHI instructions anyway.

[bjope]

I'm a bit curious about the overall plan here. Some years ago the plan was to remove LiveVariables, and use LiveIntervals instead. And afaik PHIElimination was updated to support both LiveVariables and LiveIntervals, while TwoAddressInstructionPass only got partially updated. So for several years there have been a technical debt here, considering that the passes involved in de-SSA to some degree are supporting both LiveVaribels and LiveIntervals, while only LiveVariables is used in practise (and the support for LiveIntervals may have rotten since it is poorly tested).

Considering that work now is being done to tidy up the LiveVariables support (or at least the verification of it), maybe we should consider dropping LiveIntervals support in the de-SSA phase completely. Or maybe we should spend time on finalizing the phase-out of LiveVariables instead. Is this perhaps something that you have been thinking about?

[arsenm]

In D80274#2164158, @bjope wrote:

I'm a bit curious about the overall plan here. Some years ago the plan was to remove LiveVariables, and use LiveIntervals instead. And afaik PHIElimination was updated to support both LiveVariables and LiveIntervals, while TwoAddressInstructionPass only got partially updated. So for several years there have been a technical debt here, considering that the passes involved in de-SSA to some degree are supporting both LiveVaribels and LiveIntervals, while only LiveVariables is used in practise (and the support for LiveIntervals may have rotten since it is poorly tested).

Considering that work now is being done to tidy up the LiveVariables support (or at least the verification of it), maybe we should consider dropping LiveIntervals support in the de-SSA phase completely. Or maybe we should spend time on finalizing the phase-out of LiveVariables instead. Is this perhaps something that you have been thinking about?

The idea is to remove kill flags and LiveVariables

[ZhangKang]

Update the patch to follow reviewers' comments.

[ZhangKang]

llvm/lib/CodeGen/MachineVerifier.cpp

2306

Have updated the patch to remvoe PHIVarFrom .

[bjope]

llvm/lib/CodeGen/MachineVerifier.cpp

2309

Should be possible to use MBB.phis() on previous line, to iterate over the range of MI:s that are PHI nodes.

2319

I had expected something like this, simply dealing with the vregs being live in and used in the PHI instructions (earlier left out from vregsLiveIn since we need to care about the control flow edges).

for (unsigned i = 1, e = MI.getNumOperands(); i != e; i += 2) {
  // Skip those Operands which are undef regs or not regs.
  if (!MI.getOperand(i).isReg() || !MI.getOperand(i).readsReg())
    continue;.

  // Get register and predecessor for one PHI edge.
  unsigned Reg = MI.getOperand(i).getReg();
  const MachineBasicBlock *Pred = MI.getOperand(i + 1).getMBB();

  BBInfo &PInfo = MBBInfoMap[Pred];
  if (PInfo.addRequired(Reg))
    todo.insert(Pred);
}

Notice that addRequired will return false if Reg isn't a virtual register, or if Reg already is in the required set. So the outer if-statement here seems redundant due to that.

Another question is if you need to do the MRI->getVRegDef(Reg)->getParent() != FromMBB check or not.
That would map to something like this

bb8:
  %t = phi i32 [ ... ], [ %y, %bb8 ]
  %y = add ...
  ...
  br i1 ..., %bb8

From the LiveVariables verifications point of view we expect that vregsRequired should match AliveBlocks information. And afaict %bb8 won't be in AliveBlocks for %y (since %y is defined in %bb8), so it should not be in vregsRequired. However, since addRequired also checks regsLiveOut before adding anything to vregsRequired, that situation should be covered as well.

[ZhangKang]

Simplify the code.

[bjope]

LGTM!

llvm/lib/CodeGen/MachineVerifier.cpp

void addRegWithSubRegs(RegVector &RV, unsigned Reg) {
           RV.push_back(SubReg);
     }
 
     struct BBInfo {
       // Is this MBB reachable from the MF entry point?
       bool reachable = false;
 
       // Vregs that must be live in because they are used without being
-      // defined. Map value is the user.
+      // defined. Map value is the user. vregsLiveIn doesn't include regs
+      // that only are used by PHI nodes.
       RegMap vregsLiveIn;
 
       // Regs killed in MBB. They may be defined again, and will then be in both
       // regsKilled and regsLiveOut.
       RegSet regsKilled;
 
       // Regs defined in MBB and live out. Note that vregs passing through may
       // be live out without being mentioned here.
void MachineVerifier::calcRegsRequired() {
   SmallPtrSet<const MachineBasicBlock*, 8> todo;
   for (const auto &MBB : *MF) {
     BBInfo &MInfo = MBBInfoMap[&MBB];
     for (const MachineBasicBlock *Pred : MBB.predecessors()) {
       BBInfo &PInfo = MBBInfoMap[Pred];
       if (PInfo.addRequired(MInfo.vregsLiveIn))
         todo.insert(Pred);
     }
+
+    // Handle the PHI node.
+    for (const MachineInstr &MI : MBB.phis()) {
+      for (unsigned i = 1, e = MI.getNumOperands(); i != e; i += 2) {
+        // Skip those Operands which are undef regs or not regs.
+        if (!MI.getOperand(i).isReg() || !MI.getOperand(i).readsReg())
+          continue;
+
+        // Get register and predecessor for one PHI edge.
+        Register Reg = MI.getOperand(i).getReg();
+        const MachineBasicBlock *Pred = MI.getOperand(i + 1).getMBB();
+
+        BBInfo &PInfo = MBBInfoMap[Pred];
+        if (PInfo.addRequired(Reg))
+          todo.insert(Pred);
+      }
+    }
   }
 
   // Iteratively push vregsRequired to predecessors. This will converge to the
   // same final state regardless of DenseSet iteration order.
   while (!todo.empty()) {
     const MachineBasicBlock *MBB = *todo.begin();
     todo.erase(MBB);
     BBInfo &MInfo = MBBInfoMap[MBB];

llvm/test/CodeGen/PowerPC/livevars-crash1.mir

-# RUN: not --crash llc -mtriple powerpc64le-unknown-linux-gnu %s -o - 2>&1 \
-# RUN:   -run-pass=livevars,phi-node-elimination -verify-machineinstrs \
-# RUN:   | FileCheck %s
+# RUN: llc -mtriple powerpc64le-unknown-linux-gnu %s -o - 2>&1 \
+# RUN:   -run-pass=livevars,phi-node-elimination -verify-machineinstrs | \
+# RUN:  FileCheck %s
 
 --- |
   ; Function Attrs: noreturn nounwind
   define signext i32 @zext_free(i8** nocapture dereferenceable(8) %p) {
   entry:
     %.pre = load i8*, i8** %p, align 8
     br label %loop
   
body:             |
   
   bb.3.if.then3:
     successors: %bb.1(0x80000000)
   
     %3:g8rc = nuw ADDI8 killed %1, 2
     STD %3, 0, %4 :: (store 8 into %ir.p)
     B %bb.1
 
+  ; CHECK-LABEL: name: zext_free
+  ; CHECK: bb.0.entry:
+  ; CHECK:   successors: %bb.1(0x80000000)
+  ; CHECK:   liveins: $x3
+
+  ; CHECK:   %4:g8rc_and_g8rc_nox0 = COPY killed $x3
+  ; CHECK:   %0:g8rc = LD 0, %4 :: (dereferenceable load 8 from %ir.p)
+  ; CHECK:    %12:g8rc_and_g8rc_nox0 = COPY killed %0
+
+  ; CHECK: bb.1.loop:
+  ; CHECK:   successors: %bb.1(0x20000000), %bb.2(0x60000000)
+
+  ; CHECK:   %1:g8rc_and_g8rc_nox0 = COPY killed %12
+  ; CHECK:   %5:gprc = LBZ 0, %1 :: (load 1 from %ir.0)
+  ; CHECK:   %6:crrc = CMPWI killed %5, 0
+  ; CHEXK:   %7:crbitrc = COPY killed %6.sub_eq
+  ; CHECK:   %2:g8rc = nuw ADDI8 %1, 1
+  ; CHECK:   STD %2, 0, %4 :: (store 8 into %ir.p)
+  ; CHECK:   %8:gprc = LBZ 1, %1 :: (load 1 from %ir.incdec.ptr)
+  ; CHECK:   %12:g8rc_and_g8rc_nox0 = COPY %2
+  ; CHECK:   BCn killed %7, %bb.1
+  ; CHECK:   B %bb.2
+
+  ; CHECK: bb.2.loop:
+  ; CHECK:   successors: %bb.3(0x55555555), %bb.1(0x2aaaaaab)
+
+  ; CHECK:   %9:crrc = CMPWI killed %8, 0
+  ; CHECK:   %10:crbitrc = COPY killed %9.sub_eq
+  ; CHECK:   %12:g8rc_and_g8rc_nox0 = COPY killed %2
+  ; CHECK:   BC killed %10, %bb.1
+  ; CHECK:   B %bb.3
+
+  ; CHECK: bb.3.if.then3:
+  ; CHECK:   successors: %bb.1(0x80000000)
+
+  ; CHECK:   %3:g8rc = nuw ADDI8 killed %1, 2
+  ; CHECK:   STD %3, 0, %4 :: (store 8 into %ir.p)
+  ; CHECK:   %12:g8rc_and_g8rc_nox0 = COPY killed %3
+  ; CHECK:   B %bb.1
+
+
 ...
-# CHECK-LABEL: Bad machine code: LiveVariables: Block should not be in AliveBlocks
-# CHECK-NEXT:  - function:    zext_free
-# CHECK-NEXT:  - basic block: %bb.2 loop
-# CHECK-NEXT:  Virtual register %2 is not needed live through the block.
-# CHECK-NEXT:  LLVM ERROR: Found 1 machine code errors.
+

llvm/test/CodeGen/PowerPC/livevars-crash2.mir

-# RUN: not --crash llc -mtriple powerpc64le-unknown-linux-gnu %s -o - 2>&1 \
-# RUN:   -run-pass=livevars,phi-node-elimination -verify-machineinstrs \
-# RUN:   | FileCheck %s
+# RUN: llc -mtriple powerpc64le-unknown-linux-gnu %s -o - 2>&1 \
+# RUN:   -run-pass=livevars,phi-node-elimination -verify-machineinstrs | \
+# RUN:   FileCheck %s
 
 --- |
   define float @testfloatslt(float %c1, float %c2, float %c3, float %c4, float %a1, float %a2) {
   entry:
     %cmp1 = fcmp oeq float %c3, %c4
     %cmp3tmp = fcmp oeq float %c1, %c2
     %cmp3 = icmp slt i1 %cmp3tmp, %cmp1
     %cond = select i1 %cmp3, float %a1, float %a2
body:             |
   
   bb.3.if.then3:
     successors: %bb.1(0x80000000)
   
     %3:g8rc = nuw ADDI8 killed %1, 2
     STD %3, 0, %4 :: (store 8 into %ir.p)
     B %bb.1
 
-...
+  ; CHECK-LABEL: name: testfloatslt
+  ; CHECK: bb.0.entry:
+  ; CHECK:   successors: %bb.1(0x80000000)
+  ; CHECK:   liveins: $x3
+
+  ; CHECK:   %4:g8rc_and_g8rc_nox0 = COPY killed $x3
+  ; CHECK:   %0:g8rc = LD 0, %4 :: (dereferenceable load 8 from %ir.p)
+  ; CHECK:   %12:g8rc_and_g8rc_nox0 = COPY killed %0
+
+  ; CHECK: bb.1.loop:
+  ; CHECK:   successors: %bb.1(0x20000000), %bb.2(0x60000000)
+
+  ; CHECK:   %1:g8rc_and_g8rc_nox0 = COPY killed %12
+  ; CHECK:   %5:gprc = LBZ 0, %1 :: (load 1 from %ir.0)
+  ; CHECK:   %6:crrc = CMPWI killed %5, 0
+  ; CEHCK:   %7:crbitrc = COPY killed %6.sub_eq
+  ; CHECK:   %2:g8rc = nuw ADDI8 %1, 1
+  ; CHECK:   STD %2, 0, %4 :: (store 8 into %ir.p)
+  ; CHECK:   %8:gprc = LBZ 1, %1 :: (load 1 from %ir.incdec.ptr)
+  ; CHECK:   %12:g8rc_and_g8rc_nox0 = COPY %2
+  ; CHECK:   BCn killed %7, %bb.1
+  ; CHECK:   B %bb.2
+
+  ; CHECK: bb.2.loop:
+  ; CHECK:   successors: %bb.3(0x55555555), %bb.1(0x2aaaaaab)
+
+  ; CHECK:   %9:crrc = CMPWI killed %8, 0
+  ; CHECK:   %10:crbitrc = COPY killed %9.sub_eq
+  ; CHECK:   %12:g8rc_and_g8rc_nox0 = COPY killed %2
+  ; CHECK:   BC killed %10, %bb.1
+  ; CHECK:   B %bb.3
+
+  ; CHECK: bb.3.if.then3:
+  ; CHECK:   successors: %bb.1(0x80000000)
+
+  ; CHECK:   %3:g8rc = nuw ADDI8 killed %1, 2
+  ; CHECK:   STD %3, 0, %4 :: (store 8 into %ir.p)
+  ; CHECK:   %12:g8rc_and_g8rc_nox0 = COPY killed %3
+  ; CHECK:   B %bb.1
 
-# CHECK-LABEL: Bad machine code: LiveVariables: Block should not be in AliveBlocks
-# CHECK-NEXT:  - function:    testfloatslt
-# CHECK-NEXT:  - basic block: %bb.1 entry
-# CHECK-NEXT:  Virtual register %4 is not needed live through the block.
-
-# CHECK-LABEL: Bad machine code: LiveVariables: Block should not be in AliveBlocks
-# CHECK-NEXT:  - function:    testfloatslt
-# CHECK-NEXT:  - basic block: %bb.1 entry
-# CHECK-NEXT:  Virtual register %5 is not needed live through the block.
-
-# CHECK-LABEL: Bad machine code: LiveVariables: Block should not be in AliveBlocks
-# CHECK-NEXT:  - function:    testfloatslt
-# CHECK-NEXT:  - basic block: %bb.2 entry
-# CHECK-NEXT:  Virtual register %5 is not needed live through the block.
-# CHECK-NEXT:  LLVM ERROR: Found 3 machine code errors.
+...