Simplify some if tests #27462

benaadams · 2019-10-26T17:47:35Z

Noticed a change for Dictionary.KeyCollection and got a bit carried away...

Total bytes of diff: -1150 (-0.04% of base)
    diff is an improvement.

Top file improvements by size (bytes):
    -1150 : System.Private.CoreLib.dasm (-0.04% of base)

1 total files with size differences (1 improved, 0 regressed), 0 unchanged.

Top method improvements by size (bytes):
     -93 (-3.87% of base) : System.Private.CoreLib.dasm - KeyCollection:CopyTo(ref,int):this (13 methods)
     -60 (-2.38% of base) : System.Private.CoreLib.dasm - ValueCollection:CopyTo(ref,int):this (13 methods)
     -48 (-5.61% of base) : System.Private.CoreLib.dasm - DateTime:TryCreate(int,int,int,int,int,int,int,byref):bool
     -35 (-7.58% of base) : System.Private.CoreLib.dasm - JulianCalendar:ToDateTime(int,int,int,int,int,int,int,int):struct:this
     -28 (-5.10% of base) : System.Private.CoreLib.dasm - Utf8Parser:TryParseInt64D(struct,byref,byref):bool
     -20 (-5.60% of base) : System.Private.CoreLib.dasm - Vector2:CopyTo(ref,int):this
     -17 (-2.84% of base) : System.Private.CoreLib.dasm - String:IndexOf(ref,int,int,int):int:this
     -17 (-5.94% of base) : System.Private.CoreLib.dasm - Calendar:TimeToTicks(int,int,int,int):long
     -17 (-6.37% of base) : System.Private.CoreLib.dasm - GregorianCalendarHelper:TimeToTicks(int,int,int,int):long
     -16 (-8.42% of base) : System.Private.CoreLib.dasm - Char:IsSurrogatePair(ref,int):bool
     -16 (-2.69% of base) : System.Private.CoreLib.dasm - Char:ConvertToUtf32(ref,int):int
     -16 (-4.15% of base) : System.Private.CoreLib.dasm - Vector3:CopyTo(ref,int):this
     -16 (-3.83% of base) : System.Private.CoreLib.dasm - Vector4:CopyTo(ref,int):this
     -16 (-1.48% of base) : System.Private.CoreLib.dasm - EncodingNLS:GetBytes(ref,int,int,ref,int):int:this (2 methods)
     -16 (-1.49% of base) : System.Private.CoreLib.dasm - UnicodeEncoding:GetBytes(ref,int,int,ref,int):int:this (2 methods)
     -16 (-1.49% of base) : System.Private.CoreLib.dasm - UTF32Encoding:GetBytes(ref,int,int,ref,int):int:this (2 methods)
     -16 (-1.49% of base) : System.Private.CoreLib.dasm - UTF7Encoding:GetBytes(ref,int,int,ref,int):int:this (2 methods)
     -16 (-3.83% of base) : System.Private.CoreLib.dasm - IListWrapper:LastIndexOf(ref,int,int):int:this
     -14 (-10.00% of base) : System.Private.CoreLib.dasm - Char:IsHighSurrogate(ref,int):bool
     -14 (-10.00% of base) : System.Private.CoreLib.dasm - Char:IsLowSurrogate(ref,int):bool
     -14 (-0.44% of base) : System.Private.CoreLib.dasm - IdnMapping:PunycodeDecode(ref):ref
     -11 (-1.16% of base) : System.Private.CoreLib.dasm - ParseNumbers:StringToLong(struct,int,int,byref):long
     -11 (-1.11% of base) : System.Private.CoreLib.dasm - ParseNumbers:StringToInt(struct,int,int,byref):int
     -10 (-4.37% of base) : System.Private.CoreLib.dasm - String:IndexOf(ref,int,int):int:this (2 methods)
     -10 (-1.34% of base) : System.Private.CoreLib.dasm - DateTime:.ctor(int,int,int,int,int,int,int,ref,int):this
     -10 (-0.99% of base) : System.Private.CoreLib.dasm - StringSerializer:GetNextStringValue():ref:this
      -9 (-3.41% of base) : System.Private.CoreLib.dasm - Array:FindIndex(ref,int,int,ref):int
      -9 (-0.63% of base) : System.Private.CoreLib.dasm - DateTime:.ctor(int,int,int,int,int,int,int):this (2 methods)
      -9 (-1.41% of base) : System.Private.CoreLib.dasm - DateTime:.ctor(int,int,int,int,int,int,int,ref):this
      -9 (-1.70% of base) : System.Private.CoreLib.dasm - DecoderNLS:GetChars(ref,int,int,ref,int,bool):int:this
      -9 (-1.68% of base) : System.Private.CoreLib.dasm - EncoderNLS:GetBytes(ref,int,int,ref,int,bool):int:this
      -9 (-1.60% of base) : System.Private.CoreLib.dasm - EncodingNLS:GetChars(ref,int,int,ref,int):int:this
      -9 (-1.60% of base) : System.Private.CoreLib.dasm - UnicodeEncoding:GetChars(ref,int,int,ref,int):int:this
      -9 (-1.60% of base) : System.Private.CoreLib.dasm - UTF32Encoding:GetChars(ref,int,int,ref,int):int:this
      -9 (-1.60% of base) : System.Private.CoreLib.dasm - UTF7Encoding:GetChars(ref,int,int,ref,int):int:this
      -8 (-1.42% of base) : System.Private.CoreLib.dasm - Array:IndexOf(ref,ref,int,int):int (2 methods)
      -8 (-2.42% of base) : System.Private.CoreLib.dasm - String:ToCharArray(int,int):ref:this
      -8 (-2.16% of base) : System.Private.CoreLib.dasm - String:Insert(int,ref):ref:this
      -8 (-1.34% of base) : System.Private.CoreLib.dasm - String:LastIndexOf(ref,int,int,int):int:this
      -8 (-1.72% of base) : System.Private.CoreLib.dasm - BitConverter:ToString(ref,int,int):ref
      -8 (-11.11% of base) : System.Private.CoreLib.dasm - DateTimeParse:AdjustHour(byref,int):bool
      -8 (-1.85% of base) : System.Private.CoreLib.dasm - StringSerializer:SkipVersionNextDataFields(int):this
      -8 (-0.77% of base) : System.Private.CoreLib.dasm - StringSerializer:GetNextAdjustmentRuleValue():ref:this
      -8 (-0.70% of base) : System.Private.CoreLib.dasm - StringSerializer:GetNextTransitionTimeValue():struct:this
      -8 (-1.36% of base) : System.Private.CoreLib.dasm - RuntimeModule:ResolveSignature(int):ref:this
      -8 (-1.83% of base) : System.Private.CoreLib.dasm - BinaryReader:FillBuffer(int):this
      -8 (-1.66% of base) : System.Private.CoreLib.dasm - CompareInfo:IndexOf(ref,ushort,int,int,int):int:this
      -8 (-1.21% of base) : System.Private.CoreLib.dasm - CompareInfo:LastIndexOf(ref,ushort,int,int,int):int:this
      -8 (-1.23% of base) : System.Private.CoreLib.dasm - CompareInfo:LastIndexOf(ref,ref,int,int,int):int:this
      -8 (-3.03% of base) : System.Private.CoreLib.dasm - HebrewCalendar:GetLunarMonthDay(int,ref):int
      
132 total methods with size differences (132 improved, 0 regressed), 19003 unchanged.

/cc @jkotas

hughbe · 2019-10-26T17:52:16Z

Can the JIT still not optimise these sorts of range checks?!

EgorBo · 2019-10-26T17:52:23Z

I think @mikedn had a fix for it in JIT (https://github.com/dotnet/coreclr/issues/12477#issuecomment-519606184)

EgorBo · 2019-10-26T18:01:11Z

However, I guess it's not always a good idea to optimize

if (startIndex < 0 || startIndex > array.Length)

into

if ((uint)startIndex > (uint)array.Length)

It makes sense to do only when the true-branch is unlikely to be taken (bb weight = 0)

jkotas · 2019-10-26T18:12:36Z

src/System.Private.CoreLib/shared/System/ArraySegment.cs

            {
                ThrowInvalidOperationIfDefault();
-                if (index < 0 || index >= _count)
+                if ((uint)index >= (uint)_count)


The JIT would not be able to optimize cases like this. It does not know that _count is not negative.

@jkotas what about array.Length? Does JIT know it can't be negative? (e.g. mono/mono#16948)

Also, clang still is able to optimize it: https://godbolt.org/z/nmC3c6

Clang's Isn't as optimized as the changed C#?

cmp edi, esi setg al shr edi, 31 or rdi, rax jne .LBB0_1

vs sharplab.io

cmp edx, r8d ja L001a

clang doesn't know our integer is actually a positive number :-)

jkotas · 2019-10-26T18:15:09Z

I agree that it would be nice for the toolchain to optimize this for you. On the other hand, this became a CoreLib idiom used in hundreds of places, so one hundred more is not a big deal.

mikedn · 2019-10-26T19:03:07Z

So when we change the JIT to recognize this pattern what do we do? Go and cleanup all the FX that has now become riddled with this hack? I almost regret adding this to the JIT.

benaadams · 2019-10-26T19:10:56Z

Go and cleanup all the FX that has now become riddled with this hack?

I'd be more than happy to do so.

EgorBo · 2019-10-26T22:50:01Z

UPD
@mikedn @benaadams
Prototype: EgorBo@351be74

Jit-diff: https://gist.github.com/EgorBo/e6bbd36a2d87975fd3c9763f7a630bc9

Total bytes of diff: -2569 (-0.01% of base)

benaadams · 2019-10-26T23:32:31Z

Need to access the array and eliminate the bounds check for >=

if (i < 0 || i >= array.Length)
{
    throw new Exception();
}
i = array[i];

benaadams · 2019-10-26T23:41:38Z

Also this pattern

if (i >= 0 && i < array.Length)
{
    i = array[i];
}

EgorBo · 2019-10-27T00:19:59Z

src/System.Private.CoreLib/shared/System/Array.cs

            }

-            if (startIndex < 0 || startIndex > array.Length)
+            if ((uint)startIndex > (uint)array.Length)


@benaadams um.. shouldn't it be >= here ?
It's currently incorrect (even before your PR)

No, >= fails for Fill(empty, default, 0, 0) (Or any Fill(arr, default, arr.Length, 0)

EgorBo · 2019-10-27T01:24:40Z

@benaadams I've updated #27462 (comment) (now the diff is -2569)

sandreenko · 2019-10-27T22:24:22Z

cc @dotnet/jit-contrib

maryamariyan · 2019-11-06T21:03:22Z

Thank you for your contribution. As announced in dotnet/coreclr#27549 this repository will be moving to dotnet/runtime on November 13. If you would like to continue working on this PR after this date, the easiest way to move the change to dotnet/runtime is:

In your coreclr repository clone, create patch by running git format-patch origin
In your runtime repository clone, apply the patch by running git apply --directory src/coreclr <path to the patch created in step 1>

GrabYourPitchforks

Only one thing that needs to be fixed, the rest are just random comments.

GrabYourPitchforks · 2019-11-07T02:07:17Z

src/System.Private.CoreLib/shared/System/Collections/ArrayList.cs

            public override int IndexOf(object? value, int startIndex, int count)
            {
-                if (startIndex < 0 || startIndex > Count) throw new ArgumentOutOfRangeException(nameof(startIndex), SR.ArgumentOutOfRange_Index);
+                if ((uint)startIndex > (uint)Count) throw new ArgumentOutOfRangeException(nameof(startIndex), SR.ArgumentOutOfRange_Index);


Technically a breaking change since the get_Count virtual method is now always called, even if startIndex is negative. Honestly I don't care, but wanted to point it out since it's an example of something the JIT wouldn't be able to optimize automatically since it'd likely pessimistically assume the get_Count virtual method might have side effects.

(This same comment applies to a few other places in this file.)

GrabYourPitchforks · 2019-11-07T02:20:37Z

src/System.Private.CoreLib/shared/System/Globalization/IdnMapping.cs


                        // Make sure n is legal
-                        if (n < 0 || n > 0x10ffff || (n >= 0xD800 && n <= 0xDFFF))
+                        if ((uint)n > 0x10ffff || (n >= 0xD800 && n <= 0xDFFF))


Hooray, a simplification! 😀
if (!Rune.IsValid(n))

Perhaps out of scope here, but there's likely some low-hanging fruit throughout the Framework that could be touched up in this manner.

GrabYourPitchforks · 2019-11-07T02:26:46Z

src/System.Private.CoreLib/shared/System/String.Searching.cs

                throw new ArgumentOutOfRangeException(nameof(startIndex), SR.ArgumentOutOfRange_Index);

-            if (count < 0 || startIndex > this.Length - count)
+            if ((uint)startIndex > (uint)(this.Length - count))


This optimization isn't valid. Still need to check count for a negative value.

benaadams · 2019-11-09T23:02:43Z

I'll follow up with this one post consolidation

maryamariyan · 2019-12-02T19:37:15Z

Thank you for your contribution. As announced in #27549 the dotnet/runtime repository will be used going forward for changes to this code base. Closing this PR as no more changes will be accepted into master for this repository. If you’d like to continue working on this change please move it to dotnet/runtime.

Simplify some if tests

df4a30e

jkotas reviewed Oct 26, 2019

View reviewed changes

EgorBo reviewed Oct 27, 2019

View reviewed changes

EgorBo mentioned this pull request Oct 27, 2019

JIT: Optimize simple range checks with uint hack #27480

Closed

sandreenko added area-CodeGen optimization labels Oct 27, 2019

GrabYourPitchforks suggested changes Nov 7, 2019

View reviewed changes

BruceForstall added the post-consolidation PRs which will be hand ported to dotnet/runtime label Nov 7, 2019

maryamariyan closed this Dec 2, 2019

Simplify some if tests #27462

Simplify some if tests #27462

Uh oh!

Conversation

benaadams commented Oct 26, 2019

Uh oh!

hughbe commented Oct 26, 2019

Uh oh!

EgorBo commented Oct 26, 2019

Uh oh!

EgorBo commented Oct 26, 2019 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

benaadams Oct 26, 2019 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

jkotas commented Oct 26, 2019

Uh oh!

mikedn commented Oct 26, 2019

Uh oh!

benaadams commented Oct 26, 2019

Uh oh!

EgorBo commented Oct 26, 2019 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

benaadams commented Oct 26, 2019

Uh oh!

benaadams commented Oct 26, 2019

Uh oh!

EgorBo Oct 27, 2019 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

EgorBo commented Oct 27, 2019

Uh oh!

sandreenko commented Oct 27, 2019

Uh oh!

maryamariyan commented Nov 6, 2019

Uh oh!

GrabYourPitchforks left a comment

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

benaadams commented Nov 9, 2019

Uh oh!

maryamariyan commented Dec 2, 2019

Uh oh!

Reviewers

Assignees

Labels

Projects

Milestone

Development

Uh oh!

10 participants

EgorBo commented Oct 26, 2019 •

edited

Loading

benaadams Oct 26, 2019 •

edited

Loading

EgorBo commented Oct 26, 2019 •

edited

Loading

EgorBo Oct 27, 2019 •

edited

Loading