Runtime: [JIT] Bounds check not eliminated in simple for loop for span argument passed with ref / in modifier

[Zhentar]

https://github.com/Zhentar/xxHash3.NET/blob/7fb40da7d535c6d5fb024d2c5363cc2bb3c2a068/xxHash3/xxHash3_AVX2.cs#L103

for (int i = 0; i < blocks.Length; i++)
{
    ref readonly var block = ref blocks[i];

This seems like a pretty straightforward scenario (that's not covered by any of the existing issues that I see). But I'm still seeing bounds checks:

          for (int i = 0; i < blocks.Length; i++)
               ^^^^^^^^^
       xor     r9d,r9d
       mov     r10d,dword ptr [rcx+8]
       test    r10d,r10d
       jle     M10_L01
           ref readonly var block = ref blocks[i];
           ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
M10_L00:
       cmp     r9d,r10d
       jae     M10_L02
       movsxd  r11,r9d
       shl     r11,0Ah
       add     r11,qword ptr [rcx]

[mikedn]

This is very likely caused by blocks span being passed by reference. Have you tried without in?

[Zhentar]

Ah ha! Removing the in does indeed cut out the bounds check! Why does that influence it, though? And is there an existing issue for it?

Ooh, and while removing the in from accVec didn't make the length check at https://github.com/Zhentar/xxHash3.NET/blob/8e09264a0cc910ab1dc6720bf0b3d6ed1b0a111b/xxHash3/xxHash3_AVX2.cs#L83 work, it does make it so moving the var accB = accVec[1]; up first gets it down to just one bounds check anyway, and without the register restore code bloat of the early return!

[jkotas]

The JIT works better with by-value semantics. https://github.com/dotnet/corefx/issues/35679#issuecomment-474620975

[Zhentar]

Hmm, interesting, I did not realize the impact of that at all. I've updated the title to be more search-able, and I can close this if you think it's not a reasonable target.

[mikedn]

Why does that influence it, though?

Basically that JIT needs to know the value does not change. Passing a value by reference makes that difficult, there may be code outside the compiled method that can change the value and the JIT doesn't know about it.

The same is true even for "native" compilers. But those usually have the luxury of analyzing the whole program and sometimes concluding that the value can't actually change.

And is there an existing issue for it?

There may be somewhat similar issues that involve either arrays that aren't local variables or other CQ issues associated with structs passed by reference. I don't think I've seen one specifically about spans passed by reference so this one it is.

I can close this if you think it's not a reasonable target

Might worth a bit of investigation and thinking before closing. Spans are a bit special with regards to changes because they're confined to the stack. That makes it rather difficult for them to change in an arbitrary manner so perhaps the JIT could handle this a bit better.

At the same time, it's best to avoid passing spans by reference. They're small structures and the potential extra copy that's associated with passing by value is not going to be measurable in many situations.

[Zhentar]

It's generally not the copy I'm trying to avoid - it's the rep stosd stack zeroing.

[jkotas]

Yeah, I have seen everybody trying to avoid rep stosd in prolog like plaque.

@AndyAyersMS I see that https://github.com/dotnet/coreclr/issues/19076 on this was moved the future. I agree that fine tuning this would be a lot of work, but the current tuning seems to be so much off that adjusting it some should be pretty safe. What do you think?

[AndyAyersMS]

We can't easily reduce the amount of prolog zeroing (though dotnet/coreclr#22255 helps a little), but we can perhaps adjust how the jit does the zeroing.

The relevant logic is in CodeGen::genCheckUseBlockInit which decides between block init and case-by-case. Currently block init always emits rep stos. So relatively safe options here are:

• adjust threshold between block init and field-by-field to perhaps favor field-by-field more often.
• improve block init to use unroll strategy for small block sizes, say 128 bytes or less on x64 (ala CodeGen::genCodeForInitBlkUnroll and INITBLK_UNROLL_LIMIT) (4 x 16 byte xmm stores)
• When AVX2 is usable, consider using ymm stores and going up to 256 bytes?

@dotnet/jit-contrib any ideas?

[Zhentar]

adjust threshold between block init and field-by-field to perhaps favor field-by-field more often.

Just fixing the double counting of pointer containing structs (which I think would just be a continue inside the VarSetOps::IsMember(compiler, compiler->fgFirstBB->bbLiveIn, varDsc->lvVarIndex)) if block) would help a lot; as it is currently even a single Span<> on the stack pushes you most of the way to the limit.

[AndyAyersMS]

Will look into the computation we do to count the number of slots to zero. Looks like we can double count. The logic is a bit convoluted.

Might want to fork this to another issue or just reconsider taking on dotnet/runtime#10744.

[fiigii]

When AVX2 is usable, consider using ymm stores and going up to 256 bytes?

Comparing to 128-bit stores, 256-bit stores are more sensitive with address alignment and not handled by certain memory optimizations (e.g., store-forwarding) on current Intel architectures. So, I think using XMM stores is a better choice.

[AndyAyersMS]

@Zhentar can you point me at examples where the prolog zeroing was off?

[AndyAyersMS]

There's a little bit of overt double counting (that is, a given local is counted twice). But probably more relevant is that the heuristic has not changed since Jit32, and so it is really x86 centric, and assumes we can only zero 4 bytes at a time, so 64 bit pointers are "double cost".

So without introducing new codegen patterns we can alter the logic for 64 bit targets and that should improve things somewhat. If we want to use wider stores I'll have to look into what is possible on arm32/arm64.

[Zhentar]

Sounds like you figured it out, but this will zero with rep stosd:

        private byte[] bytes;
        public void StackZero() { Span<byte> a, b; a = bytes; b = bytes; Dummy(a, b); }
        [MethodImpl(MethodImplOptions.NoInlining)]
        private void Dummy(Span<byte> a, Span<byte> b) { }

[AndyAyersMS]

Bumping the 64 bit target threshold to 32 bytes (instead of current 16) gives

Total bytes of diff: -20050 (-0.05% of base)
98 total files with size differences (84 improved, 14 regressed), 31 unchanged.
4516 total methods with size differences (3603 improved, 913 regressed), 195607 unchanged.

Typical diff

; Assembly listing for method OrderedPipeliningMergeEnumerator:MoveNext():bool:this
        sub      rsp, 104
-       mov      rsi, rcx
-       lea      rdi, [rsp+48H]
-       mov      ecx, 8
        xor      rax, rax
-       rep stosd
-       mov      rcx, rsi
+       mov      qword ptr [rsp+58H], rax
+       mov      qword ptr [rsp+60H], rax
+       mov      qword ptr [rsp+48H], rax
+       mov      qword ptr [rsp+50H], rax
        mov      rsi, rcx

Note the zeroing stores are not in any particular order (they reflect the offsets assigned to the local vars). We could fix this with some extra work. There can also be gaps if we're not under initlocals.

If we go up to 64 bytes it is more or less size neutral. So presumably with XMM stores we could win on size and speed for 64 or maybe even 128 byte cases. Around that point we lose the small displacements and might want to consider a loop.

[AndyAyersMS]

Trying to a perf read on changing the threshold for x64 to 32 bytes, with general reg stores. Provisional changes here: FrameZeroAccounting.

[AndyAyersMS]

Put up a PR for the above: dotnet/coreclr#23498.

[AndyAyersMS]

dotnet/coreclr#23498's now merged, and the original issue explained, so I think we can close this.