Emit cgt, likewise clt, for comparisons

[dsyme]

I'm not sure of the right repo for this as it is a suggestion for C# optimization, not language.

I was talking with @tannergooding about the implementation of CompareTo in the BCL, which today is this: (likewise for Int64 etc.)

public int CompareTo(int value) {
            // Need to use compare because subtraction will wrap
            // to positive for very large neg numbers, etc.
            if m_value < value) return -1;
            if m_value > value) return 1;
            return 0;
        }

He suggested that the following would be faster as long as the (x > y) ? 1 : 0 and (x < y) ? 1 : 0 are emitted as the .NET instructions cgt and clt.

int tmp1 = (x > y) ? 1 : 0;
int tmp2 = (x < y) ? 1 : 0;
return tmp1 - tmp2;

We think it is reasonable for the C# compiler to emit these sequences like this when optimization is on.

Context: dotnet/fsharp#13187

[tannergooding]

Removing the branches here will simplify the JIT work and some local tests shows it is generating better IL, IR, and native assembly. The JIT could likewise optimize the cmp ? 1 : 0 pattern itself, but it seems generally beneficial for the compiler to emit the smaller IL.

It would be beneficial to generate SuperPMI diffs against the prototype compiler if this was felt worthwhile.

[AlekseyTs]

@Tanner Could you clarify the suggestion? Specific C# construct, current IL, proposed IL, etc.

[tannergooding]

@AlekseyTs, the suggestion is for the compiler to recognize the (a op b) ? 1 : 0 pattern for a few specific op and to emit better IL.

Namely, certain comparison IL instructions already guarantee a value of 1 or 0 is pushed onto the stack and so it is beneficial to emit them instead. These instructions are:

• ceq - compare equal
• cgt - compare greater than
• cgt.un - compare greater than, unsigned
• clt - compare less than
• clt.un - compare less than, unsigned

For (a > b) ? 1 : 0 the compiler currently emits the following IL:

IL_0000: ldarg.1
IL_0001: ldarg.2
IL_0002: bgt.s IL_0006

IL_0004: ldc.i4.0
IL_0005: ret

IL_0006: ldc.i4.1
IL_0007: ret

This involves a comparison, a branch, and requires the JIT to do quite a bit more work to recognize the pattern and "do the right thing".

Alternatively, the compiler could emit simply:

IL_0000: ldarg.1
IL_0001: ldarg.2
IL_0002: cgt
IL_0003: ret

This is a much simpler sequence that does the same thing. It then also allows branch-free algorithms to more easily be built which in turn would allow a more optimized implementation of int.CompareTo(int)

[omariom]

Codegen comparison

[CyrusNajmabadi]

Can this not be done with some sort of IL prepass or just in the JIT? If the C# compiler has to do this, then so do the VB/F# compilers (and any other IL emitted out there). If we had a prepass tool that could perform these optimizations, they would all benefit, instead of each compiler having to reinvent these optimizations. e.g. something more akin to an LLVM where you can do the work once and everyone can benefit since htey go to the same IR.

[tannergooding]

Can this not be done with some sort of IL prepass or just in the JIT? If the C# compiler has to do this, then so do the VB/F# compilers (and any other IL emitted out there). If we had a prepass tool that could perform these optimizations, they would all benefit, instead of each compiler having to reinvent these optimizations. e.g. something more akin to an LLVM where you can do the work once and everyone can benefit since htey go to the same IR.

Doing some IL pre-optimization isn't tenable most of the time (it requires integration another tool into the pipeline, and it gets complicated due to needing to also touch PDBs and all the other relevant metadata). The JIT can do it, but it requires more processing of IL and handling of complex branches in a time/resource constrained environment.

F# is already doing a small optimization like this, as per the attached PR.

[dsyme]

@CyrusNajmabadi I think the problem is more that there's no direct way of generating an expression-based "cgt" etc. in C#, even though these are present in the underlying IL. It seems there should always be a way of generating each primitive instruction on primitive types.

[tannergooding]

Just leaving a note requested by @jaredpar that x ? 1 : 0 (that is given a bool x and not a separate comparison) can itself be handled via:

push x
push 0
cgt.un

cgt should also work for this case since bool should be considered unsigned and therefore zero extend up. But cgt.un is more accurate.

[tannergooding]

The JIT is adding support for x ? 1 : 0 becoming just x for some relops (e.g. cgt) here: dotnet/runtime#81880