JIT: Improve rangecheck for certain binops

[EgorBo]

The following method currently emits bound checks:

static byte Foo(uint index) // Extracted from CountDigits()
{
    ReadOnlySpan<byte> table = new byte[]
        {
            0x00, 0x00, 0x00, 0x00, 0x01, 0x00, 0x00, 0x00, // 4294967296
            0xF6, 0xFF, 0xFF, 0xFF, 0x01, 0x00, 0x00, 0x00, // 8589934582
            0xF6, 0xFF, 0xFF, 0xFF, 0x01, 0x00, 0x00, 0x00, // 8589934582
            0xF6, 0xFF, 0xFF, 0xFF, 0x01, 0x00, 0x00, 0x00, // 8589934582
            0x9C, 0xFF, 0xFF, 0xFF, 0x02, 0x00, 0x00, 0x00, // 12884901788
            0x9C, 0xFF, 0xFF, 0xFF, 0x02, 0x00, 0x00, 0x00, // 12884901788
            0x9C, 0xFF, 0xFF, 0xFF, 0x02, 0x00, 0x00, 0x00, // 12884901788
            0x18, 0xFC, 0xFF, 0xFF, 0x03, 0x00, 0x00, 0x00, // 17179868184
            0x18, 0xFC, 0xFF, 0xFF, 0x03, 0x00, 0x00, 0x00, // 17179868184
            0x18, 0xFC, 0xFF, 0xFF, 0x03, 0x00, 0x00, 0x00, // 17179868184
            0xF0, 0xD8, 0xFF, 0xFF, 0x04, 0x00, 0x00, 0x00, // 21474826480
            0xF0, 0xD8, 0xFF, 0xFF, 0x04, 0x00, 0x00, 0x00, // 21474826480
            0xF0, 0xD8, 0xFF, 0xFF, 0x04, 0x00, 0x00, 0x00, // 21474826480
            0xF0, 0xD8, 0xFF, 0xFF, 0x04, 0x00, 0x00, 0x00, // 21474826480
            0x60, 0x79, 0xFE, 0xFF, 0x05, 0x00, 0x00, 0x00, // 25769703776
            0x60, 0x79, 0xFE, 0xFF, 0x05, 0x00, 0x00, 0x00, // 25769703776
            0x60, 0x79, 0xFE, 0xFF, 0x05, 0x00, 0x00, 0x00, // 25769703776
            0xC0, 0xBD, 0xF0, 0xFF, 0x06, 0x00, 0x00, 0x00, // 30063771072
            0xC0, 0xBD, 0xF0, 0xFF, 0x06, 0x00, 0x00, 0x00, // 30063771072
            0xC0, 0xBD, 0xF0, 0xFF, 0x06, 0x00, 0x00, 0x00, // 30063771072
            0x80, 0x69, 0x67, 0xFF, 0x07, 0x00, 0x00, 0x00, // 34349738368
            0x80, 0x69, 0x67, 0xFF, 0x07, 0x00, 0x00, 0x00, // 34349738368
            0x80, 0x69, 0x67, 0xFF, 0x07, 0x00, 0x00, 0x00, // 34349738368
            0x80, 0x69, 0x67, 0xFF, 0x07, 0x00, 0x00, 0x00, // 34349738368
            0x00, 0x1F, 0x0A, 0xFA, 0x08, 0x00, 0x00, 0x00, // 38554705664
            0x00, 0x1F, 0x0A, 0xFA, 0x08, 0x00, 0x00, 0x00, // 38554705664
            0x00, 0x1F, 0x0A, 0xFA, 0x08, 0x00, 0x00, 0x00, // 38554705664
            0x00, 0x36, 0x65, 0xC4, 0x09, 0x00, 0x00, 0x00, // 41949672960
            0x00, 0x36, 0x65, 0xC4, 0x09, 0x00, 0x00, 0x00, // 41949672960
            0x00, 0x36, 0x65, 0xC4, 0x09, 0x00, 0x00, 0x00, // 41949672960
            0x00, 0x00, 0x00, 0x00, 0x0A, 0x00, 0x00, 0x00, // 42949672960
            0x00, 0x00, 0x00, 0x00, 0x0A, 0x00, 0x00, 0x00, // 42949672960
        };
    return table[(int)(uint.Log2(index))];
}

While it looks to be quite niche, it showcases multiple ways we can improve bound check elimination for a general case, so basically this is lowered to:

array[Lzcnt.LeadingZeroCount(index | 1) ^ 31]

We should handle:

1. OR index | CNS, e.g. X | 1 means lower bound is at least 1.

2. XOR index ^ CNS, e.g. X ^ 31 means that we should merge X's range with 0-b11111 range

3. HWINTRINSIC - we know that certain intrinsics such as LeadingZeroCount return value in a range of 0..64 + merged with its argument's range

OR and XOR should be handled here + "does overflow" part.

Each of these separately might find uses in the wild.

I couldn't figure out the best area label to add to this issue. If you have write-permissions please help me learn by adding exactly one area label.

Tagging subscribers to this area: @JulieLeeMSFT, @jakobbotsch
See info in area-owners.md if you want to be subscribed.

Issue Details

---

The following method currently emits bound checks:

static byte Foo(uint index) // Extracted from CountDigits()
{
    ReadOnlySpan<byte> table = new byte[]
        {
            0x00, 0x00, 0x00, 0x00, 0x01, 0x00, 0x00, 0x00, // 4294967296
            0xF6, 0xFF, 0xFF, 0xFF, 0x01, 0x00, 0x00, 0x00, // 8589934582
            0xF6, 0xFF, 0xFF, 0xFF, 0x01, 0x00, 0x00, 0x00, // 8589934582
            0xF6, 0xFF, 0xFF, 0xFF, 0x01, 0x00, 0x00, 0x00, // 8589934582
            0x9C, 0xFF, 0xFF, 0xFF, 0x02, 0x00, 0x00, 0x00, // 12884901788
            0x9C, 0xFF, 0xFF, 0xFF, 0x02, 0x00, 0x00, 0x00, // 12884901788
            0x9C, 0xFF, 0xFF, 0xFF, 0x02, 0x00, 0x00, 0x00, // 12884901788
            0x18, 0xFC, 0xFF, 0xFF, 0x03, 0x00, 0x00, 0x00, // 17179868184
            0x18, 0xFC, 0xFF, 0xFF, 0x03, 0x00, 0x00, 0x00, // 17179868184
            0x18, 0xFC, 0xFF, 0xFF, 0x03, 0x00, 0x00, 0x00, // 17179868184
            0xF0, 0xD8, 0xFF, 0xFF, 0x04, 0x00, 0x00, 0x00, // 21474826480
            0xF0, 0xD8, 0xFF, 0xFF, 0x04, 0x00, 0x00, 0x00, // 21474826480
            0xF0, 0xD8, 0xFF, 0xFF, 0x04, 0x00, 0x00, 0x00, // 21474826480
            0xF0, 0xD8, 0xFF, 0xFF, 0x04, 0x00, 0x00, 0x00, // 21474826480
            0x60, 0x79, 0xFE, 0xFF, 0x05, 0x00, 0x00, 0x00, // 25769703776
            0x60, 0x79, 0xFE, 0xFF, 0x05, 0x00, 0x00, 0x00, // 25769703776
            0x60, 0x79, 0xFE, 0xFF, 0x05, 0x00, 0x00, 0x00, // 25769703776
            0xC0, 0xBD, 0xF0, 0xFF, 0x06, 0x00, 0x00, 0x00, // 30063771072
            0xC0, 0xBD, 0xF0, 0xFF, 0x06, 0x00, 0x00, 0x00, // 30063771072
            0xC0, 0xBD, 0xF0, 0xFF, 0x06, 0x00, 0x00, 0x00, // 30063771072
            0x80, 0x69, 0x67, 0xFF, 0x07, 0x00, 0x00, 0x00, // 34349738368
            0x80, 0x69, 0x67, 0xFF, 0x07, 0x00, 0x00, 0x00, // 34349738368
            0x80, 0x69, 0x67, 0xFF, 0x07, 0x00, 0x00, 0x00, // 34349738368
            0x80, 0x69, 0x67, 0xFF, 0x07, 0x00, 0x00, 0x00, // 34349738368
            0x00, 0x1F, 0x0A, 0xFA, 0x08, 0x00, 0x00, 0x00, // 38554705664
            0x00, 0x1F, 0x0A, 0xFA, 0x08, 0x00, 0x00, 0x00, // 38554705664
            0x00, 0x1F, 0x0A, 0xFA, 0x08, 0x00, 0x00, 0x00, // 38554705664
            0x00, 0x36, 0x65, 0xC4, 0x09, 0x00, 0x00, 0x00, // 41949672960
            0x00, 0x36, 0x65, 0xC4, 0x09, 0x00, 0x00, 0x00, // 41949672960
            0x00, 0x36, 0x65, 0xC4, 0x09, 0x00, 0x00, 0x00, // 41949672960
            0x00, 0x00, 0x00, 0x00, 0x0A, 0x00, 0x00, 0x00, // 42949672960
            0x00, 0x00, 0x00, 0x00, 0x0A, 0x00, 0x00, 0x00, // 42949672960
        };
    return table[(int)(uint.Log2(index))];
}

While it looks to be quite niche, it showcases multiple ways we can improve bound check elimination for a general case, so basically this is lowered to:

array[Lzcnt.LeadingZeroCount(index | 1) ^ 31]

We should handle:

1. OR index | CNS, e.g. X | 1 means lower bound is at least 1.

2. XOR index ^ CNS, e.g. X ^ 31 means that we should merge X's range with 0-b11111 range

3. HWINTRINSIC - we know that certain intrinsics such as LeadingZeroCount return value in a range of 0..64 + merged with its argument's range

Each of these separately might find uses in the wild.

Author:	EgorBo
Assignees:	-
Labels:	help wanted, area-CodeGen-coreclr, untriaged
Milestone:	-

[jakobbotsch]

Related issue that could be fixed at the same time: #65550

[drieseng]

When fixed, the following code can be updated:

runtime/src/libraries/System.Private.CoreLib/src/System/Buffers/Text/FormattingHelpers.CountDigits.cs

Lines 147 to 149 in 1555786

	// TODO: Replace with table[uint.Log2(value)] once https://github.com/dotnet/runtime/issues/79257 is fixed
	long tableValue = Unsafe.Add(ref MemoryMarshal.GetReference(table), uint.Log2(value));
	return (int)((value + tableValue) >> 32);

Just trying to be helpful, let me know if it's not.

[aromaa]

Wrote something to catch this b04892f5f1cef198e3d4c9aa41188d4fbe271954.

Its quite a bit of LOC for no hits in CoreLib other than the potential use case in FormattingHelpers.CountDigits.

[EgorBo]

Wrote something to catch this b04892f5f1cef198e3d4c9aa41188d4fbe271954.

Its quite a bit of LOC for no hits in CoreLib other than the potential use case in FormattingHelpers.CountDigits.

I didn't expect a lot of hits, but it's a good JIT exercise 🙂 with a good test coverage can be merged (haven't looked deeply your branch yet)

[xakep139]

Once fixed, this file needs to be updated as well:

runtime/src/libraries/System.Private.CoreLib/src/System/Buffers/Text/FormattingHelpers.CountDigits.cs

Lines 69 to 70 in 6887fc4

	// TODO: Replace with log2ToPow10[BitOperations.Log2(value)] once https://github.com/dotnet/runtime/issues/79257 is fixed
	uint index = Unsafe.Add(ref MemoryMarshal.GetReference(log2ToPow10), BitOperations.Log2(value));