Roslyn: lifted comparison codegen can be improved

[VSadov]

In the codegen of lifted comparison operators some conditional branches seem unnecessary.
They only serve to shortcircuit trivial bool operators over locals - that does not seem very profitable.

We should do something like in: https://github.com/dotnet/corefx/pull/15941
( Also check https://github.com/dotnet/corefx/pull/17535 if that is better )

Example:

We emit lifted equality for left and right as:

bool? result = (left.GetValueOrDefault() == right.GetValueOrDefault()) ?
                                                  ( left.HasValue == right.HasValue ) :
                                                   false;

A more efficient would be:

bool? result = (left.GetValueOrDefault() == right.GetValueOrDefault()) & 
                                           (left.HasValue == right.HasValue);

[gafter]

@VSadov Can you please spell out the issue (what kind of source, what IL do we generate now, and what IL would be better)?

[VSadov]

added examples to the bug

[isc30]

In case no newcomer wants this one, I can take care

[CyrusNajmabadi]

This seems interesting to me. Though it seems like it could lead to worse performance in some cases. For example. if i have:

c# SomeLargeStruct? s1, s2; //... var b = s1 == s1;

Even if these have 'null' as their value, we'll incur the costly cost of doing the == check for the underlying values.

This is also surprising to me as i would not have expected the underlying == to be called if either value was null.

--

That said, if we think the null case is the rare case, then maybe it's better to be branchless and jsut do the work then try to bail out early if either value is null.

[CyrusNajmabadi]

Hrmm. i don't repro this locally. The IL i see generated seems to be of the form:

var v = left.HasValue == right.HasValue
    ? left.HasValue ? left.GetValueOrDefault() == right.GetValueOrDefault()) : false
    : false;

Or is this only for the case of things like known primitive types? If so, then i can see how a branchless form could def make sense.

[VSadov]

only for primitives

[CyrusNajmabadi]

Gotcha. Then that makes a lot of sense!

[isc30]

How can I see the generated IL for this? I mean, where is it being generated?

[Joe4evr]

@isc30 You should check out SharpLab.

[isc30]

Thanks @Joe4evr

I'm getting this for built-in types:

left.GetValueOrDefault() == right.GetValueOrDefault()
    && left.HasValue == right.HasValue;

I wasn't able to reproduce any of your cases tho. If you could create an example in sharplab.io so we see what's the generated IL and how can be optimized would be great.

https://sharplab.io/#v2:CYLg1APgAgDABFAjAbgLACgoGYECY4DCcA3hnOXGRdnAEYD29ANnAEICuAlkwC4CSAOwAUAShJUKFTgJ4B+OJ3gBeOLjTpJASGlyFiOCoHsmTdZMkTzUAOwLlKziksBfS5ZoNmhJgEMAzn6i4hrm5EjwAMbKcABEAO70cTFmoXAAyjwATtIA5nAR+obGppYWIaE2+fb5TuVwrujOQA==

[svick]

@isc30 That's the same as the example in the original post, since a && b is the same as a ? b : false.

If you look at the IL, you will see the unnecessary conditional branch as beq.s.

Basically, this issue is about changing from && to &.

[isc30]

okay, this makes a lot of sense! thanks for the explanation

[alrz]

Seems to be fixed in master.
https://sharplab.io/#v2:EYLgtghgzgLgpgJwDQBMQGoA+ABADAAmwEYBuAWAChsBmQgJnwGF8BvS/Dw24Aex4Bt8AWQAUASwB2MAPz4xSOVNkArAJSt2nLdgDsc/AF4D+ZeQpaAvpQtA

[svick]

@alrz I still see && (and not &) in the decompiled C# (and beq.s in the IL), so I don't think this was fixed. What makes you think otherwise?

[alrz]

What makes you think otherwise?

My vision loss.

[alrz]

To be clear, the final codegen would look like this:

// We rewrite x == y as 
//
// tempx = x; 
// tempy = y;
// result = (tempx.GetValueOrDefault() == tempy.GetValueOrDefault()) &
//          (tempx.HasValue == tempy.HasValue);
//
// and x != y as
//
// tempx = x; 
// tempy = y;
// result = (tempx.GetValueOrDefault() != tempy.GetValueOrDefault()) ||
//          (tempx.HasValue != tempy.HasValue);
//
// Otherwise, we rewrite x OP y as
//
// tempx = x;
// tempy = y;
// result = (tempx.GetValueOrDefault() OP tempy.GetValueOrDefault()) &&
//          (tempx.HasValue & tempy.HasValue);
//

@VSadov can you confirm?

[isc30]

why || and not |?

[VSadov]

@alrz @isc30 - yes like that, and yes with regular | and & - to be branchless.

It also makes sense to use DeMorgan dual of the #2 to avoid != . The IL emit will have to use ceq and negate for the !=, but the following will have to negate only once, so it is a bit more compact:

// and x != y as
//
// tempx = x; 
// tempy = y;
// result = !((tempx.GetValueOrDefault() == tempy.GetValueOrDefault()) &
//          (tempx.HasValue == tempy.HasValue));