[RegAllocFast] Handle case where operand of copy cannot be assigned.

[fhahn]

Summary

This patch adds special handling to detect the case where we try to
assign a register to the VReg use of a copy, but all registers in the
required class are pre-assigned. We cannot assign such registers and
error out later.

Instead, we can try to move the use right after the definition, in the
hope that one of the registers in the class gets freed up.

This scenario can happen when assigning registers to copies to physical
registers for a function call, so initially this is limited to copies to
physical registers.

The only extra cost in practice should be the scan of the register
class. Finding the defining MI should only be needed in cases where we
would run out of registers otherwise.

I am planning to convert the test case into a MIR test case, but I'd
like to make sure the patch is on the right track first.

[arsenm]

My first thoughts is there should be no scan or instruction moving necessary. Why can't you just spill registers to satisfy this? The MIR test would help understand this

llvm/lib/CodeGen/RegAllocFast.cpp

1083–1086

I don't see why copies specifically would be special for this problem

1089

Both operands are required to be a register for COPY, you can drop the isReg checks

1094–1101

Moving this to a separate function would be worthwhile

1103–1113

What about partial defs?

llvm/test/CodeGen/X86/regallocfast-need-to-move-copy.ll

3 ↗

(On Diff #321382)

Should add a comment explaining the test

[fhahn]

In D96015#2541829, @arsenm wrote:

My first thoughts is there should be no scan or instruction moving necessary. Why can't you just spill registers to satisfy this? The MIR test would help understand this

The problem is all registers in the required class are pre-assigned and cannot be spilled (according to RegAllocFast::calcSpillCost https://github.com/llvm/llvm-project/blob/main/llvm/lib/CodeGen/RegAllocFast.cpp#L598)

The MIR for the problematic block is below. It cannot find a register for %8 in $al = COPY %8, because all register in the class for %8 are defined between $al = COPY %8 and %8:gr8 = MOV8ri 2

bb.3.bb5:
  successors: %bb.4(0x40000000), %bb.5(0x40000000)

  %5:gr8_norex = COPY %4.sub_8bit_hi
  %6:gr32_norex = MOVZX32rr8_NOREX killed %5
  EH_LABEL <mcsymbol >
  ADJCALLSTACKDOWN64 0, 0, 0, implicit-def dead $rsp, implicit-def dead $eflags, implicit-def dead $ssp, implicit $rsp, implicit $ssp
  %7:gr32 = MOV32ri 3427
  %8:gr8 = MOV8ri 2
  %9:gr64 = IMPLICIT_DEF
  $rdi = COPY %9
  $esi = COPY %7
  %10:gr64 = IMPLICIT_DEF
  $rdx = COPY %10
  %11:fr64 = IMPLICIT_DEF
  $xmm0 = COPY %11
  %12:fr64 = IMPLICIT_DEF
  $xmm1 = COPY %12
  %13:gr32 = IMPLICIT_DEF
  $ecx = COPY %13
  $r8d = COPY %6
  $al = COPY %8
  CALL64pcrel32 target-flags(x86-plt) @baz, csr_64, implicit $rsp, implicit $ssp, implicit $rdi, implicit $esi, implicit $rdx, implicit $xmm0, implicit $xmm1, implicit $ecx, implicit $r8d, implicit $al, implicit-def $rsp, implicit-def $ssp
  ADJCALLSTACKUP64 0, 0, implicit-def dead $rsp, implicit-def dead $eflags, implicit-def dead $ssp, implicit $rsp, implicit $ssp
  EH_LABEL <mcsymbol >
  JMP_1 %bb.4

[fhahn]

llvm/lib/CodeGen/RegAllocFast.cpp

1083–1086

I don't think they are special, I just thought it might be worth initially limiting it to copies, as the most likely case is probably during moving values to physical registers for calls.

We can remove it, we just have to do a bit more scanning.

1103–1113

I'll update this, if the direction is the right approach to pursue.

[fhahn]

Add mir test, remove isReg checks.

[qcolombet]

Is it something we could fix in the scheduler instead?

I think it is fair to end up with a "run out of registers" error here. Without changing the schedule, the allocation is not possible.

The expectation is the scheduler is supposed to keep the physical registers live-ranges as small as possible.

Basically, I am mildly against having the fast allocator doing some sort of rescheduling. This opens the door of all of crazy thing :). (Like you realized, copy are not special here, the same problem could happen with any instruction.)

[fhahn]

In D96015#2543375, @qcolombet wrote:

Is it something we could fix in the scheduler instead?

I think it is fair to end up with a "run out of registers" error here. Without changing the schedule, the allocation is not possible.

The expectation is the scheduler is supposed to keep the physical registers live-ranges as small as possible.

Unfortunately this is only a problem with -O0 and the MachineScheduler does not run and the list scheduler has register pressure tracking disabled I think.

[qcolombet]

How was this test working before?

Again I am not very keen on this approach because technically we could have this problem with any instruction and:

1. It doesn't make sense to support only COPY then
2. We really are doing the job of the scheduler here

Note that SDISel does some scheduling, maybe the problem is there?

[qcolombet]

the list scheduler has register pressure tracking disabled I think.

That's not really a problem with register pressure tracking, this is mainly a matter of keeping the physical live-ranges as small as possible.

[aemerson]

In D96015#2549761, @qcolombet wrote:

How was this test working before?

Again I am not very keen on this approach because technically we could have this problem with any instruction and:

1. It doesn't make sense to support only COPY then
2. We really are doing the job of the scheduler here

Note that SDISel does some scheduling, maybe the problem is there?

I'm not an expert in this area, but why is it any more job of the scheduler to keep the live ranges small for the sake of the allocator? Shouldn't the allocator be able to deal with any valid input (within computational reason)?

[qcolombet]

I'm not an expert in this area, but why is it any more job of the scheduler to keep the live ranges small for the sake of the allocator? Shouldn't the allocator be able to deal with any valid input (within computational reason)?

Because the input is not valid: if you don't reschedule, the code is not colorable.

[qcolombet]

To elaborate on the answer:

why is it any more job of the scheduler to keep the live ranges small for the sake of the allocator?

Because:

1. the allocator assumes a fixed schedule, it keeps the live ranges small by splitting/spilling them (only spilling for the fast allocator)
2. the live-ranges that are causing problems in that example are physical registers, which the allocator cannot touch, so we cannot split or spill them

Therefore, the only way to make this input colorable is by changing the schedule, which by #1 is not what the allocator does and knows to handle to be fair.

This patch adds some mechanics to teach the allocator how to do some re-scheduling in a very specific case, and I argue that we are setting a dangerous path. E.g., what if instead of a copy we have physreg = add %v, #1, then the allocator would fail exactly the same way.

Long story short, with today's capabilities and intended design, the input is invalid.

[aemerson]

In D96015#2555938, @qcolombet wrote:

To elaborate on the answer:

why is it any more job of the scheduler to keep the live ranges small for the sake of the allocator?

Because:

1. the allocator assumes a fixed schedule, it keeps the live ranges small by splitting/spilling them (only spilling for the fast allocator)
2. the live-ranges that are causing problems in that example are physical registers, which the allocator cannot touch, so we cannot split or spill them

Ok, with 2. it's clearer now why this is a problem.

Therefore, the only way to make this input colorable is by changing the schedule, which by #1 is not what the allocator does and knows to handle to be fair.

This patch adds some mechanics to teach the allocator how to do some re-scheduling in a very specific case, and I argue that we are setting a dangerous path. E.g., what if instead of a copy we have physreg = add %v, #1, then the allocator would fail exactly the same way.

Long story short, with today's capabilities and intended design, the input is invalid.

It sounds like we need to have the fast-RA be able to defer to the more sophisticated allocators in certain cases, but I don't think it's possible to do with the existing pass manager.

[qcolombet]

It sounds like we need to have the fast-RA be able to defer to the more sophisticated allocators in certain cases.

That's a good idea! We could do something similar to what we do with GISel: set some function attributes to inform the other allocators whether or not they have something to do.

Now, ideally, I wish we had one performant allocator that works fast enough for O0.

[arsenm]

In D96015#2573571, @qcolombet wrote:

It sounds like we need to have the fast-RA be able to defer to the more sophisticated allocators in certain cases.

That's a good idea! We could do something similar to what we do with GISel: set some function attributes to inform the other allocators whether or not they have something to do.

I think this is actually a problem GlobalISel does have since it doesn't have the DAG scheduler/linearizer to minimize physical register live ranges. We need an MI equivalent pass to do this

[qcolombet]

I think this is actually a problem GlobalISel does have since it doesn't have the DAG scheduler/linearizer to minimize physical register live ranges. We need an MI equivalent pass to do this

That's a good point. I've been advocating for this for years, if not publicly at least internally. Without a sort of scheduler in the pipeline, on targets like x86, we would generate awful code whenever we carry around flags, since so many instructions would clobber them. Currently, I believe we would just spill the flags!

[pengfei]

llvm/lib/CodeGen/RegAllocFast.cpp

1094–1099

nit: this can be a any_of.

[arsenm]

This very special case handling is probably not the right place for this

llvm/lib/CodeGen/RegAllocFast.cpp

void RegAllocFast::allocateInstruction(MachineInstr &MI) {
   //   operands are processed to avoid the allocation heuristics clashing with
   //   the pre-assignment.
   // - The "free def operands" step has to come last instead of first for tied
   //   operands and early-clobbers.
 
   UsedInInstr.clear();
   BundleVirtRegsMap.clear();
 
-  // Scan for special cases; Apply pre-assigned register defs to state.
+  // Scan for special cases;
+  //
+  // Check for copies with a VReg use in a reg-class with all registers
+  // pre-assigned. In that case, hoist the instruction up to the definition of
+  // the VReg in the hope that some pre-assigned registers have been freed up.
+  if (MI.isCopy()) {
+    MachineOperand &Op0 = MI.getOperand(0);
+    MachineOperand &Op1 = MI.getOperand(1);
+    if (Op0.getReg().isPhysical() && Op1.getReg().isVirtual()) {
+      Register Reg = Op1.getReg();
+      const TargetRegisterClass &RC = *MRI->getRegClass(Reg);
+      ArrayRef<MCPhysReg> AllocationOrder = RegClassInfo.getOrder(&RC);
+      if (all_of(AllocationOrder, [&](MCPhysReg PhysReg) {
+            for (MCRegUnitIterator UI(PhysReg, TRI); UI.isValid(); ++UI) {
+              if (RegUnitStates[*UI] == regPreAssigned) {
+                return true;
+              }
+            }
+            return false;
+          })) {
+
+        // If we find the definition of Reg, move MI just after it and exit
+        // the function.
+        for (auto &MI2 : reverse(make_range(
+                 MI.getParent()->begin()->getIterator(), MI.getIterator()))) {
+          bool DefinesReg = MI2.getOperand(0).isReg() &&
+                            MI2.getOperand(0).isDef() &&
+                            MI2.getOperand(0).getReg() == Reg;
+
+          bool UsesReg = any_of(MI2.operands(), [Reg](MachineOperand &MO) {
+            return MO.isReg() && MO.getReg() == Reg;
+          });
+
+          // If MI2 defines or uses Reg, move MI just after MI2.
+          // we can only move just after this instruction.
+          if (DefinesReg || UsesReg) {
+            MI.moveBefore(&*std::next(MI2.getIterator()));
+            return;
+          }
+        }
+      }
+    }
+  }
+
+  // Apply pre-assigned register defs to state.
   bool HasPhysRegUse = false;
   bool HasRegMask = false;
   bool HasVRegDef = false;
   bool HasDef = false;
   bool HasEarlyClobber = false;
   bool NeedToAssignLiveThroughs = false;
   for (MachineOperand &MO : MI.operands()) {
     if (MO.isReg()) {
void RegAllocFast::allocateBasicBlock(MachineBasicBlock &MBB) {
   for (MachineBasicBlock *Succ : MBB.successors()) {
     for (const MachineBasicBlock::RegisterMaskPair &LI : Succ->liveins())
       setPhysRegState(LI.PhysReg, regPreAssigned);
   }
 
   Coalesced.clear();
 
   // Traverse block in reverse order allocating instructions one by one.
-  for (MachineInstr &MI : reverse(MBB)) {
+  for (MachineInstr &MI : make_early_inc_range(reverse(MBB))) {
     LLVM_DEBUG(
       dbgs() << "\n>> " << MI << "Regs:";
       dumpState()
     );
 
     // Special handling for debug values. Note that they are not allowed to
     // affect codegen of the other instructions in any way.
     if (MI.isDebugValue()) {

llvm/test/CodeGen/X86/regallocfast-need-to-move-copy.mir

+# RUN: llc -o - -run-pass=regallocfast -verify-machineinstrs %s | FileCheck %s
+
+--- |
+  target datalayout = "e-m:e-p270:32:32-p271:32:32-p272:64:64-i64:64-f80:128-n8:16:32:64-S128"
+  target triple = "x86_64-unknown-linux"
+
+  define void @test1() {
+    %tmp = alloca i8, i64 6144, align 32
+    ret void
+  }
+
+  define void @test2() {
+    %tmp = alloca i8, i64 6144, align 32
+    ret void
+  }
+
+  declare void @baz(i8*, i32, i8*, ...)
+
+...
+---
+# Test to make sure we do not run out of registers if a VReg operand of a copy
+# cannot be assigned a register, because all registers in the class are
+# pre-assigned. In this case, the copy ($al = COPY %8) can be moved closer to
+# the def.
+
+# CHECK-LABEL: name:{{.*}}test1
+# CHECK:      bb.0:
+# CHECK:       renamable $ecx = MOV32rm killed renamable $rdi, 1, $noreg, 0, $noreg :: (load 4)
+# CHECK-NEXT:  renamable $al = COPY renamable $ch, implicit killed $ecx
+# CHECK-NEXT:  renamable $ecx = MOVZX32rr8_NOREX killed renamable $al
+# CHECK-NEXT:  $r8d = COPY killed renamable $ecx
+# CHECK-NEXT:  renamable $esi = MOV32ri 3427
+# CHECK-NEXT:  renamable $al = MOV8ri 2
+# CHECK-NEXT:  renamable $rdi = IMPLICIT_DEF
+# CHECK-NEXT:  renamable $rdx = IMPLICIT_DEF
+# CHECK-NEXT:  renamable $xmm0 = IMPLICIT_DEF
+# CHECK-NEXT:  renamable $xmm1 = IMPLICIT_DEF
+# CHECK-NEXT:  renamable $ecx = IMPLICIT_DEF
+# CHECK-NEXT:  CALL64pcrel32 target-flags(x86-plt) @baz, csr_64, implicit $rsp, implicit $ssp, implicit killed $rdi, implicit killed $esi, implicit $rdx, implicit killed $xmm0, implicit killed $xmm1, implicit killed $ecx, implicit killed $r8d, implicit $al, implicit-def $rsp, implicit-def $ssp
+#
+name:            test1
+alignment:       16
+tracksRegLiveness: true
+registers:
+  - { id: 0, class: gr32 }
+  - { id: 1, class: gr64 }
+  - { id: 2, class: gr32 }
+  - { id: 3, class: gr8 }
+  - { id: 4, class: gr32_abcd }
+  - { id: 5, class: gr8_norex }
+  - { id: 6, class: gr32_norex }
+  - { id: 7, class: gr32 }
+  - { id: 8, class: gr8 }
+  - { id: 9, class: gr64 }
+  - { id: 10, class: gr64 }
+  - { id: 11, class: fr64 }
+  - { id: 12, class: fr64 }
+  - { id: 13, class: gr32 }
+  - { id: 14, class: gr64 }
+  - { id: 15, class: gr64 }
+liveins:
+  - { reg: '$rdi', virtual-reg: '%1' }
+  - { reg: '$esi', virtual-reg: '%2' }
+frameInfo:
+  maxAlignment:    32
+  hasCalls:        true
+stack:
+  - { id: 0, name: tmp, type: variable-sized, alignment: 32 }
+machineFunctionInfo: {}
+body:             |
+  bb.0:
+    liveins: $rdi, $esi
+    successors: %bb.4, %bb.5
+
+    %1:gr64 = COPY $rdi
+    %4:gr32_abcd = MOV32rm %1, 1, $noreg, 0, $noreg :: (load 4)
+    %5:gr8_norex = COPY %4.sub_8bit_hi
+    %6:gr32_norex = MOVZX32rr8_NOREX killed %5
+    %7:gr32 = MOV32ri 3427
+    %8:gr8 = MOV8ri 2
+    %9:gr64 = IMPLICIT_DEF
+    $rdi = COPY %9
+    $esi = COPY %7
+    %10:gr64 = IMPLICIT_DEF
+    $rdx = COPY %10
+    %11:fr64 = IMPLICIT_DEF
+    $xmm0 = COPY %11
+    %12:fr64 = IMPLICIT_DEF
+    $xmm1 = COPY %12
+    %13:gr32 = IMPLICIT_DEF
+    $ecx = COPY %13
+    $r8d = COPY %6
+    $al = COPY %8
+    CALL64pcrel32 target-flags(x86-plt) @baz, csr_64, implicit $rsp, implicit $ssp, implicit $rdi, implicit $esi, implicit $rdx, implicit $xmm0, implicit $xmm1, implicit $ecx, implicit $r8d, implicit $al, implicit-def $rsp, implicit-def $ssp
+    JMP_1 %bb.4
+
+  bb.4:
+    RETQ
+
+  bb.5 (landing-pad):
+    liveins: $rax, $rdx
+
+    %15:gr64 = COPY killed $rdx
+    %14:gr64 = COPY killed $rax
+    RETQ
+
+...
+---
+# A variant of test1, with another use of %8 between the def and the call.
+# CHECK-LABEL: name:{{.*}}test2
+# CHECK:      bb.0:
+# CHECK:       renamable $ecx = MOV32rm killed renamable $rdi, 1, $noreg, 0, $noreg :: (load 4)
+# CHECK-NEXT:  renamable $al = COPY renamable $ch, implicit killed $ecx
+# CHECK-NEXT:  renamable $ecx = MOVZX32rr8_NOREX killed renamable $al
+# CHECK-NEXT:  $r8d = COPY killed renamable $ecx
+# CHECK-NEXT:  renamable $esi = MOV32ri 3427
+# CHECK-NEXT:  renamable $al = MOV8ri 2
+# CHECK-NEXT:  renamable $rdi = IMPLICIT_DEF
+# CHECK-NEXT:  $ah = COPY renamable $al
+# CHECK-NEXT:  renamable $rdx = IMPLICIT_DEF
+# CHECK-NEXT:  renamable $xmm0 = IMPLICIT_DEF
+# CHECK-NEXT:  renamable $xmm1 = IMPLICIT_DEF
+# CHECK-NEXT:  renamable $ecx = IMPLICIT_DEF
+# CHECK-NEXT:  CALL64pcrel32 target-flags(x86-plt) @baz, csr_64, implicit $rsp, implicit $ssp, implicit killed $rdi, implicit killed $esi, implicit $rdx, implicit killed $xmm0, implicit killed $xmm1, implicit killed $ecx, implicit killed $r8d, implicit $al, implicit-def $rsp, implicit-def $ssp
+#
+name:            test2
+alignment:       16
+tracksRegLiveness: true
+registers:
+  - { id: 0, class: gr32 }
+  - { id: 1, class: gr64 }
+  - { id: 2, class: gr32 }
+  - { id: 3, class: gr8 }
+  - { id: 4, class: gr32_abcd }
+  - { id: 5, class: gr8_norex }
+  - { id: 6, class: gr32_norex }
+  - { id: 7, class: gr32 }
+  - { id: 8, class: gr8 }
+  - { id: 9, class: gr64 }
+  - { id: 10, class: gr64 }
+  - { id: 11, class: fr64 }
+  - { id: 12, class: fr64 }
+  - { id: 13, class: gr32 }
+  - { id: 14, class: gr64 }
+  - { id: 15, class: gr64 }
+liveins:
+  - { reg: '$rdi', virtual-reg: '%1' }
+  - { reg: '$esi', virtual-reg: '%2' }
+frameInfo:
+  maxAlignment:    32
+  hasCalls:        true
+stack:
+  - { id: 0, name: tmp, type: variable-sized, alignment: 32 }
+machineFunctionInfo: {}
+body:             |
+
+  bb.0:
+    liveins: $rdi, $esi
+    successors: %bb.4, %bb.5
+
+    %1:gr64 = COPY $rdi
+    %4:gr32_abcd = MOV32rm %1, 1, $noreg, 0, $noreg :: (load 4)
+    %5:gr8_norex = COPY %4.sub_8bit_hi
+    %6:gr32_norex = MOVZX32rr8_NOREX killed %5
+    %7:gr32 = MOV32ri 3427
+    %8:gr8 = MOV8ri 2
+    %9:gr64 = IMPLICIT_DEF
+    $rdi = COPY %9
+    $esi = COPY %7
+    $ah = COPY %8
+    %10:gr64 = IMPLICIT_DEF
+    $rdx = COPY %10
+    %11:fr64 = IMPLICIT_DEF
+    $xmm0 = COPY %11
+    %12:fr64 = IMPLICIT_DEF
+    $xmm1 = COPY %12
+    %13:gr32 = IMPLICIT_DEF
+    $ecx = COPY %13
+    $r8d = COPY %6
+    $al = COPY %8
+    CALL64pcrel32 target-flags(x86-plt) @baz, csr_64, implicit $rsp, implicit $ssp, implicit $rdi, implicit $esi, implicit $rdx, implicit $xmm0, implicit $xmm1, implicit $ecx, implicit $r8d, implicit $al, implicit-def $rsp, implicit-def $ssp
+    JMP_1 %bb.4
+
+  bb.4:
+    RETQ
+
+  bb.5 (landing-pad):
+    liveins: $rax, $rdx
+
+    %15:gr64 = COPY killed $rdx
+    %14:gr64 = COPY killed $rax
+    RETQ
+
+...