[ARM64/Linux] Register allocator doesn't seem to always track liveness across basic blocks

[TamarChristinaArm]

In the following case with QuickJIT turned off

static int[] Test(int[] a)
{
  unsafe {
    fixed (int *a_ptr = a, b_ptr = b)
    {
    }
  }
  return a;
}

There are some dead stores and repeated loads of the same values

for instance the initialization code along with the next basic block which seems to do a null check:

G_M32566_IG01:
        A9BE7BFD          stp     fp, lr, [sp,#-32]!
        910003FD          mov     fp, sp
        F9000FBF          str     xzr, [fp,#24] // [V05 loc2]
        F9000BBF          str     xzr, [fp,#16] // [V06 loc3]

G_M32566_IG02:
        F9000FA0          str     x0, [fp,#24]  // [V05 loc2]
        B4000120          cbz     x0, G_M32566_IG04
        F9400FA2          ldr     x2, [fp,#24]  // [V05 loc2]
        B9800842          ldrsw   x2, [x2,#8]
        340000C2          cbz     w2, G_M32566_IG04

fp+24 is stored twice to without being read. This is probably due to an ABI requirement that all variables be initialized to 0? And the stack slots are probably used by the GC to track pinned memory?

But essentially the first store of xzr to fp+24 is dead as you always reach G_M32566_IG02 from G_M32566_IG01. I don't know how much DSE the CLR does, but for the non-QuickJIT case as this I would have expected some in this case.

But also the copying of the pointer via the stack seems unneeded.

        F9000FA0          str     x0, [fp,#24]  // [V05 loc2]
        B4000120          cbz     x0, G_M32566_IG04
        F9400FA2          ldr     x2, [fp,#24]  // [V05 loc2]
        B9800842          ldrsw   x2, [x2,#8]

is the same as, and the storing of x0 can be done in the initialization above it.

        B4000120          cbz     x0, G_M32566_IG04
        B9800842          ldrsw   x2, [x0,#8]

but saves a load and store as x2 us still live.

looking at the larger sequence:

G_M32566_IG02:
        F9000FA0          str     x0, [fp,#24]  // [V05 loc2]
        B4000120          cbz     x0, G_M32566_IG04
        F9400FA2          ldr     x2, [fp,#24]  // [V05 loc2]
        B9800842          ldrsw   x2, [x2,#8]
        340000C2          cbz     w2, G_M32566_IG04

G_M32566_IG03:
        52800002          mov     w2, #0
        F9400FA3          ldr     x3, [fp,#24]  // [V05 loc2]
        B9800863          ldrsw   x3, [x3,#8]
        6B03005F          cmp     w2, w3
        54000202          bhs     G_M32566_IG08

G_M32566_IG02 seems to be doing an initialization check on the pointer and G_M32566_IG03 a null ptr check? But you can only get to G_M32566_IG03 by falling through from G_M32566_IG02 for which it's doing the same load it did in G_M32566_IG02.

This sequence can be:

G_M32566_IG02:
        B4000120          cbz     x0, G_M32566_IG04
        B9800842          ldrsw   x2, [x0,#8]
        340000C2          cbz     w2, G_M32566_IG04

G_M32566_IG03:
        6B03005F          cmp     wzr, w2
        54000202          bhs     G_M32566_IG08

But this also shows an oddity here. Since you can only get to G_M32566_IG03 if x2 is non-zero, the check in G_M32566_IG03 is odd, it seems to be superfluous.

The failure actions performed in G_M32566_IG04 and G_M32566_IG08 are different though, in the former it seems to just skip over the range check and goes to the initialization check of b_ptr where the latter will hit the RNGCHKFAIL.

So does it actually need the first check?

This seems to be the pattern for pinning any array for use with Vector Create, which gives a lot of overhead even before you load the vector.

/CC @CarolEidt @tannergooding

category:cq
theme:pinning
skill-level:intermediate
cost:large

[mikedn]

pinning, at least in the fixed (int* p = a) form is pretty complicated and not really codegen specific. A simple

fixed (int* p = a) *p = 42;

generates the following x64 code:

G_M55886_IG01:
       4883EC28             sub      rsp, 40
       33C0                 xor      rax, rax
       4889442420           mov      qword ptr [rsp+20H], rax
G_M55886_IG02:
       48894C2420           mov      gword ptr [rsp+20H], rcx
       4885C9               test     rcx, rcx
       740B                 je       SHORT G_M55886_IG03
       488B442420           mov      rax, gword ptr [rsp+20H]
       83780800             cmp      dword ptr [rax+8], 0
       7504                 jne      SHORT G_M55886_IG04
G_M55886_IG03:
       33C0                 xor      rax, rax
       EB14                 jmp      SHORT G_M55886_IG05
G_M55886_IG04:
       488B442420           mov      rax, gword ptr [rsp+20H]
       83780800             cmp      dword ptr [rax+8], 0
       761E                 jbe      SHORT G_M55886_IG07
       488B442420           mov      rax, gword ptr [rsp+20H]
       4883C010             add      rax, 16
G_M55886_IG05:
       C7002A000000         mov      dword ptr [rax], 42
       33C0                 xor      rax, rax
       4889442420           mov      gword ptr [rsp+20H], rax
       488BC1               mov      rax, rcx
G_M55886_IG06:
       4883C428             add      rsp, 40
       C3                   ret
G_M55886_IG07:
       E8CE9D365F           call     CORINFO_HELP_RNGCHKFAIL
       CC                   int3

A lot of it is down to the semantics of fixed:

• yes, there is an explicit null check because a == null implies p == null
• there's a length check because a.Length == 0 implies p == null
• p is basically computed as &a[0] so you end up with a second length check due to the required range check (this is something that the JIT should remove since it is redundant)
• the array has to be pinned and that's done by reporting it to the GC as a special kind of variable. I'm not very familiar with the GC info but I understand that this variable cannot be enregistered.

And then of course, all GC pointer typed local variables needs to be default initialized since you cannot report garbage values to the GC.

All of this adds up to create this monster code that at the first sight it should be simply add x0, x0, dotnet/coreclr#16.

If you know that the array is neither null nor empty then there's an alternative that generates better code:

; fixed (int* p = &a[0]) // take the address of the first array element explicitly
G_M55886_IG01:
        A9BE7BFD          stp     fp, lr, [sp,#-32]!
        910003FD          mov     fp, sp
        F9000FBF          str     xzr, [fp,#24] // [V02 loc0]
G_M55886_IG02:
        B9800801          ldrsw   x1, [x0,#8]
        7100003F          cmp     w1, #0
        54000149          bls     G_M55886_IG04
        91004001          add     x1, x0, dotnet/coreclr#16
        F9000FA1          str     x1, [fp,#24]  // [V02 loc0]
        F9400FA1          ldr     x1, [fp,#24]  // [V02 loc0]
        52800542          mov     w2, dotnet/coreclr#42
        B9000022          str     w2, [x1]
        D2800001          mov     x1, #0
        F9000FA1          str     x1, [fp,#24]  // [V02 loc0]
G_M55886_IG03:
        A8C27BFD          ldp     fp, lr, [sp],#32
        D65F03C0          ret     lr
G_M55886_IG04:
        94000000          bl      CORINFO_HELP_RNGCHKFAIL
        D43E0000          bkpt

This avoids the null/empty checks. Of course, the pinning variable is still needed (though note that it works differently in this case - the is pinned, not the array).

[AndyAyersMS]

Modelling liveness of the pinned slot is complicated: it generally must remain live as long as any derived unmanaged pointer is live. Underestimating the liveness of a pinned local is catastrophic. So we choose to simply consider pinned locals as always live, and so pinned locals must be initialized in the prolog and generally can't be dead-stored.

With the advent of Span<T> and helpers for byref math, the need to pin things for performance has decreased, and it's now mainly needed for interop.

[TamarChristinaArm]

p is basically computed as &a[0] so you end up with a second length check due to the required range check (this is something that the JIT should remove since it is redundant)

Ahhh ok, now it makes sense why that sequence was generated.

If you know that the array is neither null nor empty then there's an alternative that generates better code:
; fixed (int* p = &a[0]) // take the address of the first array element explicitly

Thanks for the explanation that makes a lot of sense. The only thing I'm still wondering about though is why the load

       ...
        F9000FA1          str     x1, [fp,#24]  // [V02 loc0]
        F9400FA1          ldr     x1, [fp,#24]  // [V02 loc0]
        52800542          mov     w2, dotnet/coreclr#42
        B9000022          str     w2, [x1]
        D2800001          mov     x1, #0
        F9000FA1          str     x1, [fp,#24]  // [V02 loc0]
        ...

here of x1? Is this just an artifact of that it's doing the update of the address thats pinned by doing a reload? Or is it an actual requirement to load the value back up.

[mikedn]

Modelling liveness of the pinned slot is complicated: it generally must remain live as long as any derived unmanaged pointer is live.

Ah, so it's not that GC info has special requirements, it's just that the semantic of pinned variables and "standard" liveness do not quite match. Still, I'd argue that there is no need to remain live as long as any derived pointer is live - it's not the JIT's job to fix broken code like:

int* d;
fixed (int*p = a) d = p;
*d = 42;

Presumably we could insert some kind of fake use before every store to a pinned variable (and probably before method return to account for uses of pinned variables that do not follow the fixed pattern) that would keep the variable live appropriately. But then yes, with Span and ref arithmetic perhaps this is less of an issue.

[CarolEidt]

there is no need to remain live as long as any derived pointer is live

I agree that your example is broken, though I think the requirement is that it must remain live the shorter of:

• however long any derived pointer is live
• the end of the scope

That is, if the assignment to *d in your example above was in the scope of the fixed statement, then I think the JIT would have to keep p alive and reported, though I haven't gone back to the spec to verify. That said, I suspect that whatever rules the JIT is using, there exists code that relies on it.

[mikedn]

Is this just an artifact of that it's doing the update of the address thats pinned by doing a reload? Or is it an actual requirement to load the value back up.

That's not specific to pinned variable. Any variable that isn't "tracked"/"register candidate" for whatever reasons (e.g. being pinned, being address exposed) will produce this kind of code. For example:

[MethodImpl(MethodImplOptions.NoInlining)]
static void escape(ref int value) { }
…
        int sum = 0;
        escape(ref sum);
        foreach (int i in a)
            sum += i;
        return sum;

generates:

G_M55886_IG02:
        52800000          mov     w0, #0
        B90013A0          str     w0, [fp,#16]  // [V02 loc0]
        910043A0          add     x0, fp, dotnet/coreclr#16   // [V02 loc0]
        94000000          bl      Program:escape(byref)
        52800000          mov     w0, #0
        B9800A61          ldrsw   x1, [x19,#8]
        7100003F          cmp     w1, #0
        5400016D          ble     G_M55886_IG04
G_M55886_IG03:
        93407C02          sxtw    x2, x0
        D37EF442          lsl     x2, x2, dotnet/coreclr#2
        91004042          add     x2, x2, dotnet/coreclr#16
        B8A26A62          ldrsw   x2, [x19, x2]
        B98013A3          ldrsw   x3, [fp,#16]  // [V02 loc0]
        0B020062          add     w2, w3, w2
        B90013A2          str     w2, [fp,#16]  // [V02 loc0]
        11000400          add     w0, w0, dotnet/coreclr#1
        6B00003F          cmp     w1, w0
        54FFFEEC          bgt     G_M55886_IG03

BTW, since you're working on ARM code beware that those ldrsw are misleading. There's no requirement in the JIT that TYP_INT values are sign extended to 64 bit on load and the x64 codegen doesn't do this. It's just that ARM64 codegen is confused.

[mikedn]

That is, if the assignment to *d in your example above was in the scope of the fixed statement, then I think the JIT would have to keep p alive and reported, though I haven't gone back to the spec to verify.

Yes, of course, though in this particular case it's the array reference (a) that gets pinned. Basically pinned variables have to be kept alive until return, it's just that the JIT is more conservative than that and also prevents enregistration.

I suppose this could be blamed on the C# compiler as well. The semantics of fixed requires only 2 stores to the pinned variable - one at the beginning of the scope and one of the end. The problem is that the C# compiler also used the pinned variable as a temporary and that's we see a lot of uses of it. And a temporary variable isn't needed at all in this case since the original value comes from a method argument that won't change throughout the fixed null and empty checks.