[JIT] Idea: rebalance chains of relational compares against constants (switch when guards) into a binary search #136039

I was poking at switch expressions while working on some game code and noticed the codegen for when guards is pretty different from relational patterns, even when every bound ends up being a constant.

My bounds come from the length of a static ReadOnlySpan<int>. That's effectively a constant, but not a C# constant, so it can't go in a pattern like < 10 and I'm stuck with when guards.

With relational patterns, Roslyn lowers the arms into a binary search in the IL, and the JIT turns the leaves into cmov. With when guards, Roslyn has to emit them in order. The JIT folds the bounds to constants just fine (MiscItems.Length below becomes 10), but the compares stay a linear chain. Is it worth having the JIT rebalance a chain like this once the bounds are known constants?

private static ReadOnlySpan<int> MiscItems => [0x1EB5, 0xA2A, 0xC1F, 0x1047, 0x1048, 0x1EB1, 0x1EB2, 0x1EB3, 0x1EB4];

[MethodImpl(MethodImplOptions.NoInlining)]
public static int WhenGuards(int roll)
{
    int count = MiscItems.Length + 1; // folds to 10

    return roll switch
    {
        var r when r < 1 * count => 1,
        var r when r < 2 * count => 2,
        var r when r < 3 * count => 3,
        var r when r < 4 * count => 4,
        var r when r < 5 * count => 5,
        _ => 6
    };
}

[MethodImpl(MethodImplOptions.NoInlining)]
public static int RelationalPatterns(int roll)
{
    const int count = 10;

    return roll switch
    {
        < 1 * count => 1,
        < 2 * count => 2,
        < 3 * count => 3,
        < 4 * count => 4,
        < 5 * count => 5,
        _ => 6
    };
}

.NET 10.0.13 x64, Tier1 with Dynamic PGO:

WhenGuards (same 65 bytes as writing the guards against a const):

       cmp      ecx, 10
       jl       SHORT G_M000_IG11
       cmp      ecx, 20
       jl       SHORT G_M000_IG10
       cmp      ecx, 30
       jl       SHORT G_M000_IG09
       cmp      ecx, 40
       jl       SHORT G_M000_IG08
       mov      eax, 6
       mov      edx, 5
       cmp      ecx, 50
       cmovl    eax, edx
       ret
       ; ...each early exit is mov eax, N / jmp

RelationalPatterns (63 bytes):

       cmp      ecx, 40
       jge      SHORT G_M000_IG06
       cmp      ecx, 20
       jl       SHORT G_M000_IG05
       mov      eax, 3
       mov      edx, 4
       cmp      ecx, 30
       cmovge   eax, edx
       jmp      SHORT G_M000_IG07
G_M000_IG05:
       mov      eax, 1
       mov      edx, 2
       cmp      ecx, 10
       cmovge   eax, edx
       jmp      SHORT G_M000_IG07
G_M000_IG06:
       mov      eax, 5
       mov      edx, 6
       cmp      ecx, 50
       cmovge   eax, edx
G_M000_IG07:
       ret

Roslyn can't do this for when guards since they're arbitrary expressions, so the JIT seems like the natural place for it. It's sort of the relational version of the switch recognition that turns x == 1 || x == 2 || ... chains into a jump table.

My take is that once the length is provably constant and the guards are pure, the JIT should be able to do the same rewrite Roslyn does for constant patterns. I'm not sure whether there's some internal reason that makes this hard, or whether it's better solved on the language side. Mostly curious whether this has come up before or if it's been ruled out.