[PHIElimination] Fix the killed flag for LowerPHINode()

[ZhangKang]

Summary

In the phi-node-elimination pass, we set the killed flag incorrectly.
When we eliminate the PHI node, we replace the PHI with a copy for the incoming value.

Before this patch, we will set incoming value as killed(PHICopy). And we will remove the killed flag
from last using incoming value(OldKill). This is correct, only if the new PHICopy is after the OldKill.

Below is an example:

%35:gprc = PHI %26, %bb.2, %28, %bb.3
%36:gprc = PHI %19, %bb.2, %35, %bb.3
%37:gprc = PHI %26, %bb.2, %28, %bb.3
%38:g8rc_and_g8rc_nox0 = PHI %25, %bb.2, %34, %bb.3

After phi-node-elimination pass, we will get:

%38:g8rc_and_g8rc_nox0 = COPY killed %59
%37:gprc = COPY killed %57
%36:gprc = COPY killed %58
%35:gprc = COPY %57

It's obvious that, we have set the wrong killed flag for %57, if we enabled the verification for
phi-node-elimination pass, we will get the error Using a killed virtual register.

In fact, the right output should be this:

%38:g8rc_and_g8rc_nox0 = COPY killed %59
%37:gprc = COPY %57
%36:gprc = COPY killed %58
%35:gprc = COPY killed %57

This patch is to fix above error, it can fix below cases:

LLVM :: CodeGen/Hexagon/late_instr.ll
LLVM :: CodeGen/Hexagon/rdf-filter-defs.ll
LLVM :: CodeGen/Hexagon/swp-epilog-phi11.ll
LLVM :: CodeGen/Hexagon/swp-epilog-phi13.ll
LLVM :: CodeGen/Hexagon/swp-epilog-phi7.ll
LLVM :: CodeGen/Hexagon/swp-lots-deps.ll
LLVM :: CodeGen/Hexagon/swp-phi-def-use.ll
LLVM :: CodeGen/Hexagon/swp-phi-dep1.ll
LLVM :: CodeGen/Hexagon/swp-phi.ll
LLVM :: CodeGen/Hexagon/swp-stages5.ll
LLVM :: CodeGen/PowerPC/sms-phi-2.ll
LLVM :: CodeGen/Thumb/2009-08-12-ConstIslandAssert.ll
LLVM :: CodeGen/X86/2009-04-27-CoalescerAssert.ll
LLVM :: CodeGen/X86/avx512-masked_memop-16-8.ll
LLVM :: CodeGen/X86/crash.ll
LLVM :: CodeGen/X86/mmx-coalescing.ll
LLVM :: CodeGen/X86/statepoint-vector.ll

[bjope]

llvm/lib/CodeGen/PHIElimination.cpp

327–344

This findKill was guarded by if (reusedIncoming) in the past. I guess it won't hurt to keep it that way (to avoid any unpleasant surprises with build speeds, not that I think it will cause any big problems but OldKill is only of interest if reusedIncoming is true).

llvm/test/CodeGen/PowerPC/phi-eliminate.mir

174

Could be seen as an unrelated comment, but I've always wondered why PHIElimination swap the order of the defs when converting PHIs to COPYs. I guess it could be easier to deal with the liveness attributes such as "killed" is not reversing the order (but I guess those target hooks, that makes it impossible to know where the COPY is inserted, would still be a nuisance).

[ZhangKang]

Add guard for OldKill.

llvm/lib/CodeGen/PHIElimination.cpp

327–344

I will use reusedIncoming to guard the OldKill.

llvm/test/CodeGen/PowerPC/phi-eliminate.mir

174

In fact, for general cases without target hook, reversing the order is easier.

If it's not reversed order, you can think the IsPHICopyAfterOldKill is always true, I need remove the killed flag for OldKill and add killed for the coming reg. The killed flag added for the OldKill is not needed.

But if it's reversed order, you can think the IsPHICopyAfterOldKill is always false, I only need consider(line 362) whether I should add killed for the coming reg,

[bjope]

LGTM, but you might wanna wait a day or two before landing this, in case someone else got some opinions about it.

llvm/lib/CodeGen/PHIElimination.cpp

void PHIElimination::LowerPHINode(MachineBasicBlock &MBB,
   // Update live variable information if there is any.
   if (LV) {
     if (IncomingReg) {
       LiveVariables::VarInfo &VI = LV->getVarInfo(IncomingReg);
 
       // Increment use count of the newly created virtual register.
       LV->setPHIJoin(IncomingReg);
 
-      // When we are reusing the incoming register, it may already have been
-      // killed in this block. The old kill will also have been inserted at
-      // AfterPHIsIt, so it appears before the current PHICopy.
-      if (reusedIncoming)
-        if (MachineInstr *OldKill = VI.findKill(&MBB)) {
-          LLVM_DEBUG(dbgs() << "Remove old kill from " << *OldKill);
-          LV->removeVirtualRegisterKilled(IncomingReg, *OldKill);
-          LLVM_DEBUG(MBB.dump());
-        }
+      MachineInstr *OldKill = nullptr;
+      bool IsPHICopyAfterOldKill = false;
+
+      if (reusedIncoming && (OldKill = VI.findKill(&MBB))) {
+        // Calculate whether the PHICopy is after the OldKill.
+        // In general, the PHICopy is inserted as the first non-phi instruction
+        // by default, so it's before the OldKill. But some Target hooks for
+        // createPHIDestinationCopy() may modify the default insert position of
+        // PHICopy.
+        for (auto I = MBB.SkipPHIsAndLabels(MBB.begin()), E = MBB.end();
+             I != E; ++I) {
+          if (I == PHICopy)
+            break;
+
+          if (I == OldKill) {
+            IsPHICopyAfterOldKill = true;
+            break;
+          }
+        }
+      }
+
+      // When we are reusing the incoming register and it has been marked killed
+      // by OldKill, if the PHICopy is after the OldKill, we should remove the
+      // killed flag from OldKill.
+      if (IsPHICopyAfterOldKill) {
 
-      // Add information to LiveVariables to know that the incoming value is
-      // killed.  Note that because the value is defined in several places (once
-      // each for each incoming block), the "def" block and instruction fields
-      // for the VarInfo is not filled in.
+      // Add information to LiveVariables to know that the first used incoming
+      // value or the resued incoming value whose PHICopy is after the OldKIll
+      // is killed. Note that because the value is defined in several places
+      // (once each for each incoming block), the "def" block and instruction
+      // fields for the VarInfo is not filled in.
+      if (!OldKill || IsPHICopyAfterOldKill)
         LV->addVirtualRegisterKilled(IncomingReg, *PHICopy);
     }
 
     // Since we are going to be deleting the PHI node, if it is the last use of
     // any registers, or if the value itself is dead, we need to move this
     // information over to the new copy we just inserted.
     LV->removeVirtualRegistersKilled(*MPhi);
 
     // If the result is dead, update LV.

llvm/test/CodeGen/PowerPC/phi-eliminate.mir

+# RUN: llc -mtriple=powerpc64le-unknown-linux-gnu -mcpu=pwr9 %s -o - \
+# RUN:   -run-pass=livevars,phi-node-elimination | FileCheck %s
+
+--- |
+  define void @phi_eliminate(i32 %0, i32 %1, i8* %2) {
+    %scevgep3 = getelementptr i8, i8* %2, i64 undef
+    call void @llvm.set.loop.iterations.i64(i64 undef)
+    br label %4
+
+  4:                                                ; preds = %4, %3
+    %5 = phi i32 [ %8, %4 ], [ %0, %3 ]
+    %6 = phi i8* [ %scevgep3, %3 ], [ %7, %4 ]
+    %7 = getelementptr i8, i8* %6, i64 -1
+    %8 = sdiv i32 %5, %1
+    %9 = mul nsw i32 %8, %1
+    %10 = sub nsw i32 %5, %9
+    %11 = icmp ult i32 %10, 10
+    %12 = trunc i32 %10 to i8
+    %13 = select i1 %11, i8 48, i8 55
+    %14 = add i8 %13, %12
+    store i8 %14, i8* %7, align 1
+    %15 = call i1 @llvm.loop.decrement.i64(i64 1)
+    br i1 %15, label %4, label %16
+
+  16:                                               ; preds = %4
+    ret void
+  }
+
+  declare void @llvm.set.loop.iterations.i64(i64)
+
+  declare i1 @llvm.loop.decrement.i64(i64)
+
+  declare void @llvm.stackprotector(i8*, i8**)
+...
+---
+name:            phi_eliminate
+alignment:       16
+exposesReturnsTwice: false
+legalized:       false
+regBankSelected: false
+selected:        false
+failedISel:      false
+tracksRegLiveness: true
+hasWinCFI:       false
+registers:
+  - { id: 0, class: g8rc_and_g8rc_nox0, 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, preferred-register: '' }
+  - { id: 6, class: g8rc, preferred-register: '' }
+  - { id: 7, class: g8rc, preferred-register: '' }
+  - { id: 8, class: gprc, preferred-register: '' }
+  - { id: 9, class: gprc, preferred-register: '' }
+  - { id: 10, class: g8rc, preferred-register: '' }
+  - { id: 11, class: gprc, preferred-register: '' }
+  - { id: 12, class: gprc, preferred-register: '' }
+  - { id: 13, class: crrc, preferred-register: '' }
+  - { id: 14, class: gprc_and_gprc_nor0, preferred-register: '' }
+  - { id: 15, class: gprc_and_gprc_nor0, preferred-register: '' }
+  - { id: 16, class: gprc, preferred-register: '' }
+  - { id: 17, class: gprc, preferred-register: '' }
+  - { id: 18, class: g8rc_and_g8rc_nox0, preferred-register: '' }
+  - { id: 19, class: gprc, preferred-register: '' }
+  - { id: 20, class: gprc, preferred-register: '' }
+  - { id: 21, class: gprc, preferred-register: '' }
+  - { id: 22, class: crrc, preferred-register: '' }
+  - { id: 23, class: gprc, preferred-register: '' }
+  - { id: 24, class: gprc, preferred-register: '' }
+  - { id: 25, class: g8rc_and_g8rc_nox0, preferred-register: '' }
+  - { id: 26, class: gprc, preferred-register: '' }
+  - { id: 27, class: g8rc_and_g8rc_nox0, preferred-register: '' }
+  - { id: 28, class: gprc, preferred-register: '' }
+  - { id: 29, class: gprc, preferred-register: '' }
+  - { id: 30, class: gprc, preferred-register: '' }
+  - { id: 31, class: crrc, preferred-register: '' }
+  - { id: 32, class: gprc, preferred-register: '' }
+  - { id: 33, class: gprc, preferred-register: '' }
+  - { id: 34, class: g8rc_and_g8rc_nox0, preferred-register: '' }
+  - { id: 35, class: gprc, preferred-register: '' }
+  - { id: 36, class: gprc, preferred-register: '' }
+  - { id: 37, class: gprc, preferred-register: '' }
+  - { id: 38, class: g8rc_and_g8rc_nox0, preferred-register: '' }
+  - { id: 39, class: g8rc, preferred-register: '' }
+  - { id: 40, class: gprc, preferred-register: '' }
+  - { id: 41, class: gprc, preferred-register: '' }
+  - { id: 42, class: g8rc_and_g8rc_nox0, preferred-register: '' }
+  - { id: 43, class: gprc, preferred-register: '' }
+  - { id: 44, class: g8rc_and_g8rc_nox0, preferred-register: '' }
+  - { id: 45, class: gprc, preferred-register: '' }
+  - { id: 46, class: gprc, preferred-register: '' }
+  - { id: 47, class: crrc, preferred-register: '' }
+  - { id: 48, class: gprc, preferred-register: '' }
+  - { id: 49, class: gprc, preferred-register: '' }
+  - { id: 50, class: g8rc_and_g8rc_nox0, preferred-register: '' }
+  - { id: 51, class: g8rc, preferred-register: '' }
+  - { id: 52, class: gprc, preferred-register: '' }
+  - { id: 53, class: gprc, preferred-register: '' }
+  - { id: 54, class: g8rc_and_g8rc_nox0, preferred-register: '' }
+  - { id: 55, class: gprc, preferred-register: '' }
+  - { id: 56, class: gprc, preferred-register: '' }
+liveins:
+  - { reg: '$x3', virtual-reg: '%5' }
+  - { reg: '$x4', virtual-reg: '%6' }
+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:             |
+  ; CHECK-LABEL: name: phi_eliminate
+  ; CHECK: bb.0 (%ir-block.3):
+  ; CHECK:   successors: %bb.1(0x80000000)
+  ; CHECK:   liveins: $x3, $x4
+  ; CHECK:   %6:g8rc = COPY killed $x4
+  ; CHECK:   %5:g8rc = COPY killed $x3
+  ; CHECK:   %9:gprc = COPY killed %6.sub_32
+  ; CHECK:   %8:gprc = COPY killed %5.sub_32
+  ; CHECK:   MTCTR8loop undef %10:g8rc, implicit-def dead $ctr8
+  ; CHECK:   %14:gprc_and_gprc_nor0 = LI 55
+  ; CHECK:   %15:gprc_and_gprc_nor0 = LI 48
+
+  ; CHECK: bb.1 (%ir-block.4):
+  ; CHECK:   successors: %bb.2(0x40000000), %bb.7(0x40000000)
+  ; CHECK:   %19:gprc = DIVW %8, %9
+  ; CHECK:   BDNZ8 %bb.2, implicit-def $ctr8, implicit $ctr8
+
+  ; CHECK: bb.7:
+  ; CHECK:   successors: %bb.5(0x80000000)
+  ; CHECK:   %61:gprc = COPY killed %8
+  ; CHECK:   %62:g8rc_and_g8rc_nox0 = IMPLICIT_DEF
+  ; CHECK:   %63:gprc = COPY killed %19
+  ; CHECK:   B %bb.5
+
+  ; CHECK: bb.2 (%ir-block.4):
+  ; CHECK:   successors: %bb.3(0x40000000), %bb.4(0x40000000)
+  ; CHECK:   %20:gprc = nsw MULLW %19, %9
+  ; CHECK:   %21:gprc = SUBF killed %20, killed %8
+  ; CHECK:   %22:crrc = CMPLWI %21, 10
+  ; CHECK:   %23:gprc = ISEL %15, %14, killed %22.sub_lt
+  ; CEHCK:   %24:gprc = ADD4 killed %23, killed %21
+  ; CHECK:   %25:g8rc_and_g8rc_nox0 = STBU killed %24, -1, undef %0:g8rc_and_g8rc_nox0 :: (store 1 into %ir.7)
+  ; CHECK:   %26:gprc = DIVW %19, %9
+  ; CHECK:   %57:gprc = COPY killed %26
+  ; CHECK:   %58:gprc = COPY %19
+  ; CHECK:   %59:g8rc_and_g8rc_nox0 = COPY killed %25
+  ; CHECK:   %60:gprc = COPY killed %19
+  ; CHECK:   BDZ8 %bb.4, implicit-def $ctr8, implicit $ctr8
+  ; CHECK:   B %bb.3
+
+  ; CHECK: bb.3 (%ir-block.4):
+  ; CHECK:   successors: %bb.3(0x7c000000), %bb.4(0x04000000)
+  ; CHECK:   %38:g8rc_and_g8rc_nox0 = COPY killed %59
+  ; CHECK:   %37:gprc = COPY %57
+  ; CHECK:   %36:gprc = COPY killed %58
+  ; CHECK:   %35:gprc = COPY killed %57
+  ; CHECK:   %27:g8rc_and_g8rc_nox0 = COPY killed %38
+  ; CHECK:   %56:gprc = COPY %35
+  ; CHECK:   %28:gprc = DIVW %56, %9
+  ; CHECK:   %29:gprc = nsw MULLW killed %37, %9
+  ; CHECK:   %30:gprc = SUBF killed %29, killed %36
+  ; CHECK:   %31:crrc = CMPLWI %30, 10
+  ; CHECK:   %32:gprc = ISEL %15, %14, killed %31.sub_lt
+  ; CHECK:   %33:gprc = ADD4 killed %32, killed %30
+  ; CHECK:   %34:g8rc_and_g8rc_nox0 = STBU killed %33, -1, killed %27 :: (store unknown-size into %ir.7, align 1)
+  ; CHECK:   %57:gprc = COPY killed %28
+  ; CHECK:   %58:gprc = COPY killed %35
+  ; CHECK:   %59:g8rc_and_g8rc_nox0 = COPY killed %34
+  ; CHECK:   %60:gprc = COPY killed %56
+  ; CHECK:   BDNZ8 %bb.3, implicit-def $ctr8, implicit $ctr8
+  ; CHECK:   B %bb.4
+
+  ; CHECK: bb.4:
+  ; CHECK:   successors: %bb.5(0x80000000)
+  ; CHECK:   %44:g8rc_and_g8rc_nox0 = COPY killed %59
+  ; CHECK:   %43:gprc = COPY killed %57
+  ; CHECK:   %41:gprc = COPY killed %60
+  ; CHECK:   %39:g8rc = COPY killed %44
+  ; CHECK:   %61:gprc = COPY killed %41
+  ; CHECK:   %62:g8rc_and_g8rc_nox0 = COPY killed %39
+  ; CHECK:   %63:gprc = COPY killed %43
+
+  ; CHECK: bb.5:
+  ; CHECK:   successors: %bb.6(0x80000000)
+  ; CHECK:   %55:gprc = COPY killed %63
+  ; CHECK:   %54:g8rc_and_g8rc_nox0 = COPY killed %62
+  ; CHECK:   %53:gprc = COPY killed %61
+  ; CHECK:   %45:gprc = nsw MULLW killed %55, killed %9
+  ; CHECK:   %46:gprc = SUBF killed %45, killed %53
+  ; CHECK:   %47:crrc = CMPLWI %46, 10
+  ; CHECK:   %48:gprc = ISEL killed %15, killed %14, killed %47.sub_lt
+  ; CHECK:   %49:gprc = ADD4 killed %48, killed %46
+  ; CHECK:   dead %50:g8rc_and_g8rc_nox0 = STBU killed %49, -1, killed %54 :: (store unknown-size into %ir.7, align 1)
+  ; CHECK:   B %bb.6
+
+  ; CHECK: bb.6 (%ir-block.16):
+  ; CHECK:   BLR8 implicit $lr8, implicit $rm
+
+  bb.0 (%ir-block.3):
+    successors: %bb.1(0x80000000)
+    liveins: $x3, $x4
+
+    %6:g8rc = COPY killed $x4
+    %5:g8rc = COPY killed $x3
+    %9:gprc = COPY killed %6.sub_32
+    %8:gprc = COPY killed %5.sub_32
+    MTCTR8loop undef %10:g8rc, implicit-def dead $ctr8
+    %14:gprc_and_gprc_nor0 = LI 55
+    %15:gprc_and_gprc_nor0 = LI 48
+
+  bb.1 (%ir-block.4):
+    successors: %bb.2(0x40000000), %bb.5(0x40000000)
+
+    %19:gprc = DIVW %8, %9
+    BDZ8 %bb.5, implicit-def $ctr8, implicit $ctr8
+    B %bb.2
+
+  bb.2 (%ir-block.4):
+    successors: %bb.3(0x40000000), %bb.4(0x40000000)
+
+    %20:gprc = nsw MULLW %19, %9
+    %21:gprc = SUBF killed %20, killed %8
+    %22:crrc = CMPLWI %21, 10
+    %23:gprc = ISEL %15, %14, killed %22.sub_lt
+    %24:gprc = ADD4 killed %23, killed %21
+    %25:g8rc_and_g8rc_nox0 = STBU killed %24, -1, undef %0:g8rc_and_g8rc_nox0 :: (store 1 into %ir.7)
+    %26:gprc = DIVW %19, %9
+    BDZ8 %bb.4, implicit-def $ctr8, implicit $ctr8
+    B %bb.3
+
+  bb.3 (%ir-block.4):
+    successors: %bb.3(0x7c000000), %bb.4(0x04000000)
+
+    %35:gprc = PHI %26, %bb.2, %28, %bb.3
+    %36:gprc = PHI %19, %bb.2, %35, %bb.3
+    %37:gprc = PHI %26, %bb.2, %28, %bb.3
+    %38:g8rc_and_g8rc_nox0 = PHI %25, %bb.2, %34, %bb.3
+    %27:g8rc_and_g8rc_nox0 = COPY killed %38
+    %56:gprc = COPY %35
+    %28:gprc = DIVW %56, %9
+    %29:gprc = nsw MULLW killed %37, %9
+    %30:gprc = SUBF killed %29, killed %36
+    %31:crrc = CMPLWI %30, 10
+    %32:gprc = ISEL %15, %14, killed %31.sub_lt
+    %33:gprc = ADD4 killed %32, killed %30
+    %34:g8rc_and_g8rc_nox0 = STBU killed %33, -1, killed %27 :: (store unknown-size into %ir.7, align 1)
+    BDNZ8 %bb.3, implicit-def $ctr8, implicit $ctr8
+    B %bb.4
+
+  bb.4:
+    successors: %bb.5(0x80000000)
+
+    %41:gprc = PHI %19, %bb.2, %56, %bb.3
+    %43:gprc = PHI %26, %bb.2, %28, %bb.3
+    %44:g8rc_and_g8rc_nox0 = PHI %25, %bb.2, %34, %bb.3
+    %39:g8rc = COPY killed %44
+
+  bb.5:
+    successors: %bb.6(0x80000000)
+
+    %53:gprc = PHI %8, %bb.1, %41, %bb.4
+    %54:g8rc_and_g8rc_nox0 = PHI undef %0:g8rc_and_g8rc_nox0, %bb.1, %39, %bb.4
+    %55:gprc = PHI %19, %bb.1, %43, %bb.4
+    %45:gprc = nsw MULLW killed %55, killed %9
+    %46:gprc = SUBF killed %45, killed %53
+    %47:crrc = CMPLWI %46, 10
+    %48:gprc = ISEL killed %15, killed %14, killed %47.sub_lt
+    %49:gprc = ADD4 killed %48, killed %46
+    dead %50:g8rc_and_g8rc_nox0 = STBU killed %49, -1, killed %54 :: (store unknown-size into %ir.7, align 1)
+    B %bb.6
+
+  bb.6 (%ir-block.16):
+    BLR8 implicit $lr8, implicit $rm
+
+...