Redundant length check when using Span<byte> => new byte[]

[benaadams]

public static bool IsHexadecimalChar(char c)
{
    var charToHex = CharToHexLookup;
    var i = (int)c;
    return (uint)i < (uint)charToHex.Length && charToHex[i] != 0xff;
}

private static ReadOnlySpan<byte> CharToHexLookup => new byte[]
{
    0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, // 15
    0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, // 31
    0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, // 47
    0x0,  0x1,  0x2,  0x3,  0x4,  0x5,  0x6,  0x7,  0x8,  0x9,  0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, // 63
    0xFF, 0xA,  0xB,  0xC,  0xD,  0xE,  0xF,  0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, // 79
    0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, // 95
    0xFF, 0xa,  0xb,  0xc,  0xd,  0xe,  0xf // 102
};

Generates

PathStringHelper.IsHexadecimalChar(Char)
    L0000: sub rsp, 0x48
    L0004: movzx eax, cx
    L0007: cmp eax, 0x67
    L000a: jae L002f
    L000c: cmp eax, 0x67   ; this check is same as above
    L000f: jae L0036           
    L0011: movsxd rax, eax
    L0014: mov rdx, 0x1a744990bc8
    L001e: add rax, rdx
    L0021: cmp byte [rax], 0xff
    L0024: setnz al
    L0027: movzx eax, al
    L002a: add rsp, 0x48
    L002e: ret
    L002f: xor eax, eax
    L0031: add rsp, 0x48
    L0035: ret
    L0036: call System.ThrowHelper.ThrowIndexOutOfRangeException()
    L003b: int3

category:cq
theme:basic-cq
skill-level:intermediate
cost:medium

[benaadams]

Used in dotnet/aspnetcore#9709 and System/Number.Parsing.cs
https://github.com/dotnet/coreclr/blob/9f285b762839d916683f08b06d450fd9969004fe/src/System.Private.CoreLib/shared/System/Number.Parsing.cs#L46-L55

[gfoidl]

cmp eax, 0x67 ; this check is same as above

The check is the same, but it jumps to CORINFO_HELP_RNGCHKFAIL, so the bounds check isn't eliminated. This may be the root-cause for this (emitting this check).

[mikedn]

Spans are kind of problematic in this regard, their length field becomes a normal local variable. Range check elimination tends to rely on recognizing the Length field of arrays which has special representation in the IR.

[ArtBlnd]

Maybe inlining issue? I'm not sure but I saw that get_Length() is not inlined on span

[Sergio0694]

Not sure if this is relevant (or if there's some other reason it hasn't been done already), but I think it'd be possible to rewrite that IsHexadecimalChar to have no bounds checks at all with no required codegen changes at all. Something like this should work:

public static bool IsHexadecimalChar(char c)
{
    const int maxLookupIndex = 103;
    int
        sign = ((maxLookupIndex - c) >> 31) & 1,
        offset = maxLookupIndex * sign + c * (sign ^ 1);

    ref byte r0 = ref MemoryMarshal.GetReference(CharToHexLookupNew);
    ref byte r1 = ref Unsafe.Add(ref r0, offset);

    return r1 != 0xFF;
}

private static ReadOnlySpan<byte> CharToHexLookup => new byte[]
{
    0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, // 15
    0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, // 31
    0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, // 47
    0x0,  0x1,  0x2,  0x3,  0x4,  0x5,  0x6,  0x7,  0x8,  0x9,  0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, // 63
    0xFF, 0xA,  0xB,  0xC,  0xD,  0xE,  0xF,  0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, // 79
    0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, // 95
    0xFF, 0xa,  0xb,  0xc,  0xd,  0xe,  0xf, 0xFF // 103
};

Which in Release x64 generates:

C.IsHexadecimalChar(Char)
    L0000: movzx eax, cx
    L0003: mov edx, eax
    L0005: neg edx
    L0007: add edx, 0x67
    L000a: sar edx, 0x1f
    L000d: and edx, 0x1
    L0010: mov ecx, edx
    L0012: xor ecx, 0x1
    L0015: imul eax, ecx
    L0018: imul edx, edx, 0x67
    L001b: add eax, edx
    L001d: movsxd rax, eax
    L0020: mov rdx, 0x21d27ed0b30
    L002a: cmp byte [rax+rdx], 0xff
    L002e: setnz al
    L0031: movzx eax, al
    L0034: ret

Which is both shorter than the asm of the first implementation, and has no branches at all.
What I'm doing here is calculating the lookup offset with no branches with some bit shifts (that's guaranteed to work if the input are positive values, which for char is always true), and I've added one last 0xFF value in the lookup table so that char mapping to higher value are simply clamped to that last offset and return false when the comparison is made.

The full comparison on sharplab.io is here.

Hope this helps! 😊

[stephentoub]

if there's some other reason it hasn't been done already

We want to be able to write safe code and have the compiler eliminate the bounds checks where it can prove they're unnecessary. Bounds checks can always be eliminated by the programmer with unsafe code (either pointers or Unsafe.Add as you suggest), but doing that opens the door to potential bugs, off-by-one errors, buffer overruns, etc., many of which can have security implications. So while we do use unsafe code in limited circumstances, this is a case where we'd really like not to, and where we want any code written using this pattern to not need to resort to such unsafe measures to achieve something the runtime could achieve automatically.

[Sergio0694]

Ah, I see, yeah that's a valid point.
Thank you for taking the time to reply and explain all that, I appreciate it! 😄

[benaadams]

@AndyAyersMS does #43811 not fix this because it crosses a block? (code from summary, asm below)

; Lcl frame size = 40

G_M58363_IG01:
       sub      rsp, 40
						
G_M58363_IG02:
       movzx    rax, cx
       cmp      eax, 103
       jae      SHORT G_M58363_IG05  ; should eliminate below

G_M58363_IG03:
       cmp      eax, 103
       jae      SHORT G_M58363_IG07  ; should be eliminated by previous
       movsxd   rax, eax
       mov      rdx, 0xD1FFAB1E
       cmp      byte  ptr [rax+rdx], 255
       setne    al
       movzx    rax, al
						
G_M58363_IG04:
       add      rsp, 40
       ret      

G_M58363_IG05:
       xor      eax, eax

G_M58363_IG06:
       add      rsp, 40
       ret      

G_M58363_IG07:
       call     CORINFO_HELP_RNGCHKFAIL
       int3     


; Total bytes of code 58, prolog size 4, PerfScore 11.43, instruction count 18 (MethodHash=45551c04) for method Program:IsHexadecimalChar(ushort):bool

[AndyAyersMS]

GT_ARR_BOUNDS_CHECK is not qualify as a relop, so this optimization doesn't kick in for that case.

We could add similar redundancy-searching logic to optAssertionProp_BndsChk I think.

I am surprised that the other bounds check centric phases don't catch this.