[CodeGen] Fix the bug of machine sink

[LuoYuanke]

Summary

The use operand may be undefined. In that case we can just continue to
check the next operand since it won't increase register pressure.

[shchenz]

LGTM with one nit. Thanks for fixing this.

llvm/lib/CodeGen/MachineSink.cpp

802

Maybe better to exclude the undef case at the very beginning?

[LuoYuanke]

llvm/lib/CodeGen/MachineSink.cpp

802

So do we also ingore undef value for physical register?

[LuoYuanke]

Thanks @shchenz for review. Let me land this patch first and we can improve the code later.

[MatzeB]

Please choose a better title!

[MatzeB]

I'm also not sure right now if vregs without definitions are even legal MIR while we are still in MachineSSA... Checking that now

[shchenz]

llvm/lib/CodeGen/MachineSink.cpp

802

Do we have undef physical register? I don't see such usage and sounds weird to me, it is a physical register but it is undef....

[LuoYuanke]

In D127848#3585696, @MatzeB wrote:

I'm also not sure right now if vregs without definitions are even legal MIR while we are still in MachineSSA... Checking that now

Sorry, I merged it in a rush. We can revert it and add assert for nullptr if undef value is illegal in MIR.

[MatzeB]

llvm/lib/CodeGen/MachineSink.cpp

802

Yes the definition of a physical register may not be visible in the MIR (could be a parameter, a side effect of a call or exception unwinding etc...)

And physreg uses can be undef just like VRegs.

[MatzeB]

I see this code in the MachineVerifier:

} else if (MRI->def_empty(Reg)) {
  report("Reading virtual register without a def", MO, MONum);

Which reads to me that we do not allow virtual registers without a definition if there is at least 1 read of the register. But I guess that means you can indeed have a vreg without a def if all the uses are marked undef or are debug operands or similar situations where MO.readsReg() is false.

[LuoYuanke]

In D127848#3585723, @MatzeB wrote:

I see this code in the MachineVerifier:

} else if (MRI->def_empty(Reg)) {
  report("Reading virtual register without a def", MO, MONum);

Which reads to me that we do not allow virtual registers without a definition if there is at least 1 read of the register. But I guess that means you can indeed have a vreg without a def if all the uses are marked undef or are debug operands or similar situations where MO.readsReg() is false.

We can add undef flag to tell verifier it is undef register, e.g., %2:gr32 = MOV32rr undef %3:gr32.

[MatzeB]

Yes that's what I wrote. It seems there is an exception that if for all operands you get readReg() == false (that includes undef) then it is indeed allowed to have a VReg without a definition.

In D127848#3585733, @LuoYuanke wrote:

In D127848#3585723, @MatzeB wrote:

I see this code in the MachineVerifier:

} else if (MRI->def_empty(Reg)) {
  report("Reading virtual register without a def", MO, MONum);

Which reads to me that we do not allow virtual registers without a definition if there is at least 1 read of the register. But I guess that means you can indeed have a vreg without a def if all the uses are marked undef or are debug operands or similar situations where MO.readsReg() is false.

We can add undef flag to tell verifier it is undef register, e.g., %2:gr32 = MOV32rr undef %3:gr32.

llvm/lib/CodeGen/MachineSink.cpp

for (; *PS != -1; PS++)
         return true;
     return false;
   };
 
   // If this instruction is inside a Cycle and sinking this instruction can make
   // more registers live range shorten, it is still prifitable.
   for (const MachineOperand &MO : MI.operands()) {
     // Ignore non-register operands.
     if (!MO.isReg())
       continue;
     Register Reg = MO.getReg();
     if (Reg == 0)
       continue;
 
     if (Register::isPhysicalRegister(Reg)) {
       if (MO.isUse() &&
           (MRI->isConstantPhysReg(Reg) || TII->isIgnorableUse(MO)))
         continue;
 
       // Don't handle non-constant and non-ignorable physical register.
       return false;
     }
 
     // Users for the defs are all dominated by SuccToSinkTo.
     if (MO.isDef()) {
       // This def register's live range is shortened after sinking.
       bool LocalUse = false;
       if (!AllUsesDominatedByBlock(Reg, SuccToSinkTo, MBB, BreakPHIEdge,
                                    LocalUse))
         return false;
     } else {
       MachineInstr *DefMI = MRI->getVRegDef(Reg);
+      if (!DefMI)
+        continue;
       MachineCycle *Cycle = CI->getCycle(DefMI->getParent());
       // DefMI is defined outside of cycle. There should be no live range
       // impact for this operand. Defination outside of cycle means:
       // 1: defination is outside of cycle.
       // 2: defination is in this cycle, but it is a PHI in the cycle header.
       if (Cycle != MCycle || (DefMI->isPHI() && Cycle && Cycle->isReducible() &&
                               Cycle->getHeader() == DefMI->getParent()))
         continue;

llvm/test/CodeGen/X86/sink-down-undef-use.mir

+# NOTE: Assertions have been autogenerated by utils/update_mir_test_checks.py
+# RUN: llc -mtriple=x86_64-- -run-pass=machine-sink -o - %s | FileCheck %s
+
+---
+name:            foo
+alignment:       16
+tracksRegLiveness: true
+registers:
+  - { id: 0, class: gr32 }
+  - { id: 1, class: gr32 }
+  - { id: 2, class: gr32 }
+  - { id: 3, class: gr32 }
+frameInfo:
+  maxAlignment:    4
+machineFunctionInfo: {}
+body:             |
+  ; CHECK-LABEL: name: foo
+  ; CHECK: bb.0.entry:
+  ; CHECK-NEXT:   successors: %bb.2(0x80000000)
+  ; CHECK-NEXT:   liveins: $edi, $esi
+  ; CHECK-NEXT: {{  $}}
+  ; CHECK-NEXT:   JMP_1 %bb.2
+  ; CHECK-NEXT: {{  $}}
+  ; CHECK-NEXT: bb.1:
+  ; CHECK-NEXT:   successors: %bb.2(0x80000000)
+  ; CHECK-NEXT: {{  $}}
+  ; CHECK-NEXT:   [[MOV32rr:%[0-9]+]]:gr32 = MOV32rr undef %1:gr32
+  ; CHECK-NEXT: {{  $}}
+  ; CHECK-NEXT: bb.2:
+  ; CHECK-NEXT:   successors: %bb.1(0x40000000), %bb.3(0x40000000)
+  ; CHECK-NEXT: {{  $}}
+  ; CHECK-NEXT:   [[MOV32rr1:%[0-9]+]]:gr32 = MOV32rr undef %3:gr32
+  ; CHECK-NEXT:   JCC_1 %bb.1, 15, implicit undef $eflags
+  ; CHECK-NEXT:   JMP_1 %bb.3
+  ; CHECK-NEXT: {{  $}}
+  ; CHECK-NEXT: bb.3:
+  ; CHECK-NEXT:   successors: %bb.3(0x40000000), %bb.4(0x40000000)
+  ; CHECK-NEXT: {{  $}}
+  ; CHECK-NEXT:   MOV32mr $rip, 1, $noreg, 12, $noreg, [[MOV32rr1]]
+  ; CHECK-NEXT:   JCC_1 %bb.3, 15, implicit undef $eflags
+  ; CHECK-NEXT:   JMP_1 %bb.4
+  ; CHECK-NEXT: {{  $}}
+  ; CHECK-NEXT: bb.4:
+  ; CHECK-NEXT:   RET 0, undef $eax
+  bb.0.entry:
+    liveins: $edi, $esi
+    JMP_1 %bb.2
+  bb.1:
+    %0:gr32 = MOV32rr undef %1:gr32
+  bb.2:
+    %2:gr32 = MOV32rr undef %3:gr32
+    JCC_1 %bb.1, 15, undef implicit $eflags
+    JMP_1 %bb.3
+
+  bb.3:
+    MOV32mr $rip, 1, $noreg, 12, $noreg, %2
+    JCC_1 %bb.3, 15, undef implicit $eflags
+    JMP_1 %bb.4
+
+  bb.4:
+    RET 0, undef $eax
+
+...