Runtime: Normalize X >= C to X > C-1

[EgorBo]

Let's say I have:

[MethodImpl(MethodImplOptions.AggressiveOptimization)]
bool Test1(uint a)
{
    return a >= 1;
}

[MethodImpl(MethodImplOptions.AggressiveOptimization)]
bool Test2(uint a)
{
    return a == 1 || a > 1;
}

[MethodImpl(MethodImplOptions.AggressiveOptimization)]
bool Test3(uint a)
{
    return a > 0;
}

I expect them all to generate the same asm (see godbolt), at least the 1st and the 3rd cases, but instead I get:

; Method PP:Test1(int):bool:this
G_M35066_IG02:
       cmp      edx, 1
       setae    al
       movzx    rax, al
; Total bytes of code: 10


; Method PP:Test2(int):bool:this
G_M35065_IG02:
       cmp      edx, 1
       je       SHORT G_M35065_IG04
       cmp      edx, 1
       seta     al
       movzx    rax, al
G_M35065_IG03:
       ret      
G_M35065_IG04:
       mov      eax, 1
; Total bytes of code: 21


; Method PP:Test3(int):bool:this
G_M35064_IG02:
       test     edx, edx
       setne    al
       movzx    rax, al
; Total bytes of code: 9

if we normalize X>=C to X>C-1 we can get for free bound check eliminations for cases like this (see https://github.com/dotnet/coreclr/issues/21408):

void WriteTrue1(char[] a)
{
    if ((uint)a.Length >= 4) // bounds checks are removed only if we use '> 5' here
    {
        a[0] = 'T';
        a[1] = 'r';
        a[2] = 'u';
        a[3] = 'e';
    }
}

Something similar is already done for signed comparisons, see https://github.com/dotnet/coreclr/blob/master/src/jit/morph.cpp#L12778-L12783
(but only for C=1).
so

bool Test1(int a)
{
    return a >= 1;
}

bool Test3(int a)
{
    return a > 0;
}

both generate the same asm with test edx, edx.

[ArtBlnd]

I've already implemented for this. but not by removing eq in comparison.
also removing eq is already implemented by condition reversing which is swapping X >= C to C < X in current JIT. (as far as I know)

https://github.com/dotnet/coreclr/pull/23966

[mikedn]

@EgorBo Do you have any indication that if such normalization is added then return a == 1 || a > 0; will generate the same code as the rest?

Also, why do you need to write > 5 instead of >= 4 to eliminate those range checks? Anyway the code is a bit of a hack due to the "manual" cast to uint.

Something similar is already done for signed comparisons

Yes, that one is done because in general you want to compare with 0, it generates test rather than cmp and that's slightly smaller.

[EgorBo]

@mikedn
oh, I meant return a == 1 || a > 1. (updated the description).

Also, why do you need to write > 5 instead of >= 4 to eliminate those range checks?

While I agree it's better to fix it in a different way, currently you have to preferer >5
E.g. sharplab (tested locally too)

So it could help here:
1) https://github.com/dotnet/corefx/blob/master/src/System.Net.Http/src/System/Net/Http/SocketsHttpHandler/HPack/HPackEncoder.cs#L165-L173 (despite the uint hack here it still generates bound checks due to >=`)

2) https://github.com/dotnet/coreclr/blob/master/src/System.Private.CoreLib/shared/System/IO/Path.Windows.cs#L201-L202 (however there is no hacky uint cast here)

Yes, that one is done because in general you want to compare with 0, it generates test rather than cmp and that's slightly smaller.

So we can at least save that 1 byte of instructions for uint too 🙂 (currently >= 1 for uint doesn't generate test).

@ArtBlnd oh, nice, didn't see it.

[mikedn]

So it could help here:

1. So change the code. It's a hack anyway. And sometimes I'm wondering if adding the uint hack was a good idea. Too many hacks.
2. And adding the uint hack won't work in that case so how does the proposed transform help in this case?

So we can at least save that 1 byte of instructions for uint too 🙂 (currently >= 1 for uint doesn't generate test).

Yes. But this can probably be done by modifying the existing code to handle uint. Or perhaps the whole thing should be moved to lowering where it makes more sense to perform arch specific transforms.

Anyway, it's still not clear to me why do you think that transforming x >= c to x > c - 1 is useful.

[EgorBo]

@mikedn ok I agree, let's wait for a proper fix for array.Length >|>= C for bound checks. Closing it, will try locally to extend >=1 to handle uint too.
I thought it could be a base for future peephole optimizations - e.g. GCC and LLVM do normalize >= to >.

[mikedn]

I thought it could be a base for future peephole optimizations - e.g. GCC and LLVM do normalize >= to >.

Yes, it's not unusual to perform this kind of expression normalization in compilers. The trouble is that it's not as easy to implement as it may seem. It's probably not enough to add this to morph, it likely has to be added to VN as well. And then something may have to be added to lowering to counter the ill effects of such a transform (e.g. x >= -128 becomes x > =-129 and on xarch that requires 3 additional bytes due to immediate encoding).

The fact that other compilers do it doesn't imply that the JIT should do it to.

[EgorBo]

@mikedn thanks for clarification.
Does it make sense to try to apply the following optimizations then?:
for unsigned X:

X < C   ->  false (C < 0)
X >= 1  ->  C != 0;
X >= C   ->  true (C <= 0)

[mikedn]

If I understand correctly, the ones involving 0 compares are the ones from dotnet/coreclr#20661

X >= 1 should be useful. I don't know how useful, uint is not commonly used in C#. You can try and see what happens :smile: