Skip to content

RuyJIT: Array.Length / cns can be converted to unsigned div (mod)#32368

Merged
sandreenko merged 4 commits intodotnet:masterfrom
EgorBo:arr-len-div
May 27, 2020
Merged

RuyJIT: Array.Length / cns can be converted to unsigned div (mod)#32368
sandreenko merged 4 commits intodotnet:masterfrom
EgorBo:arr-len-div

Conversation

@EgorBo
Copy link
Member

@EgorBo EgorBo commented Feb 15, 2020 •
edited
Loading

Array.Length is a signed integer but since it should not be negative we can optimize some arithmetic operations, e.g. division (which is faster for unsigned), e.g.:

static int TestDiv(int[] array) => array.Length / 4;
static int TestMod(int[] array) => array.Length % 4;

Current codegen:

; Method Foo:TestDiv(System.Int32[]):int
       8B4108               mov      eax, dword ptr [rcx+8]
       8BD0                 mov      edx, eax
       C1FA1F               sar      edx, 31
       83E203               and      edx, 3
       03C2                 add      eax, edx
       C1F802               sar      eax, 2
       C3                   ret      
; Total bytes of code: 17


; Method Foo:TestMod(System.Int32[]):int
       8B4108               mov      eax, dword ptr [rcx+8]
       8BD0                 mov      edx, eax
       C1FA1F               sar      edx, 31
       83E203               and      edx, 3
       03D0                 add      edx, eax
       83E2FC               and      edx, -4
       2BC2                 sub      eax, edx
       C3                   ret
; Total bytes of code: 19

New codegen:

; Method Foo:TestDiv(System.Int32[]):int
       8B4108               mov      eax, dword ptr [rcx+8]
       C1E802               shr      eax, 2
       C3                   ret      
; Total bytes of code: 7


; Method Foo:TestMod(System.Int32[]):int
       8B4108               mov      eax, dword ptr [rcx+8]
       83E003               and      eax, 3
       C3                   ret      
; Total bytes of code: 7

(non-power of two constants are also optimized better than for signed div)

Jit-diff (-f -pmi)

Summary of Code Size diffs:
(Lower is better)

Total bytes of diff: -558 (-0.00% of base)
    diff is an improvement.

Top file improvements (bytes):
         -98 : System.Collections.Concurrent.dasm (-0.03% of base)
         -84 : Microsoft.Diagnostics.Tracing.TraceEvent.dasm (-0.00% of base)
         -56 : Microsoft.CodeAnalysis.dasm (-0.00% of base)
         -49 : System.Private.Xml.Linq.dasm (-0.03% of base)
         -39 : System.Private.CoreLib.dasm (-0.00% of base)
         -32 : System.DirectoryServices.AccountManagement.dasm (-0.01% of base)
         -28 : System.Security.AccessControl.dasm (-0.03% of base)
         -28 : System.Security.Cryptography.Xml.dasm (-0.02% of base)
         -25 : Microsoft.CodeAnalysis.VisualBasic.dasm (-0.00% of base)
         -23 : Microsoft.CodeAnalysis.CSharp.dasm (-0.00% of base)
         -23 : System.Private.Xml.dasm (-0.00% of base)
         -17 : System.Text.Json.dasm (-0.00% of base)
         -11 : System.ComponentModel.Annotations.dasm (-0.03% of base)
         -10 : System.Private.DataContractSerialization.dasm (-0.00% of base)
          -7 : Microsoft.Diagnostics.FastSerialization.dasm (-0.01% of base)
          -7 : System.IO.Ports.dasm (-0.02% of base)
          -6 : System.Net.Http.dasm (-0.00% of base)
          -5 : System.Diagnostics.PerformanceCounter.dasm (-0.01% of base)
          -5 : System.Diagnostics.Process.dasm (-0.01% of base)
          -5 : System.Security.Cryptography.Pkcs.dasm (-0.00% of base)

20 total files with Code Size differences (20 improved, 0 regressed), 142 unchanged.

Full jit-diff: https://gist.github.com/EgorBo/4e784cb90b1222bc928b1a27ccea7efa

@Dotnet-GitSync-Bot Dotnet-GitSync-Bot added the area-CodeGen-coreclr CLR JIT compiler in src/coreclr/src/jit and related components such as SuperPMI label Feb 15, 2020
@EgorBo
Copy link
Member Author

EgorBo commented Mar 16, 2020

@dotnet/jit-contrib Please take a look, the change is pretty harmless, isn't it?

kunalspathak
kunalspathak reviewed Mar 16, 2020
View reviewed changes
src/coreclr/tests/src/JIT/opt/InstructionCombining/ArrayLengthArithmetic.cs
[MethodImpl(MethodImplOptions.NoInlining)] private static int ArrayLengthDiv_cnsMaxValue(int[] array) => array.Length / int.MaxValue;
[MethodImpl(MethodImplOptions.NoInlining)] private static int ArrayLengthDiv_cnsn1(int[] array) => array.Length / -1;
[MethodImpl(MethodImplOptions.NoInlining)] private static int ArrayLengthDiv_cnsn2(int[] array) => array.Length / -2;
[MethodImpl(MethodImplOptions.NoInlining)] private static int ArrayLengthDiv_cnsMinValue(int[] array) => array.Length / int.MinValue;
Copy link
Contributor

@kunalspathak kunalspathak Mar 16, 2020

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

consider adding few cases for long.

kunalspathak
kunalspathak reviewed Mar 16, 2020
View reviewed changes
src/coreclr/tests/src/JIT/opt/InstructionCombining/ArrayLengthArithmetic.cs
}

// Array.Length / cns
[MethodImpl(MethodImplOptions.NoInlining)] private static int ArrayLengthDiv_cns0(int[] array) => array.Length / 0;
Copy link
Contributor

@kunalspathak kunalspathak Mar 16, 2020

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

ArrayLengthDiv_cns0 [](start = 66, length = 19)

should we add cases where the operation could become CSE candidate?

 .. = array.Length / 3;
...
.. = array.Length / 3;

Copy link
Contributor

@sandreenko sandreenko May 27, 2020

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

I do not see any potential issues here, because we don't change tree->gtType, so I can't construct a test where this transformation can lead to add new CSE candidates or reject an existing.
It would be nice to improve the test even more, but I would not block the PR because of that.

sandreenko
sandreenko approved these changes May 25, 2020
View reviewed changes
Copy link
Contributor

@sandreenko sandreenko left a comment

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

LGTM, thanks @EgorBo

@sandreenko sandreenko merged commit 20a01d2 into dotnet:master May 27, 2020
@tkp1n tkp1n mentioned this pull request Jun 7, 2020
Merged
@EgorBo EgorBo mentioned this pull request Jul 31, 2020
Merged
@ghost ghost locked as resolved and limited conversation to collaborators Dec 10, 2020
Sign up for free to subscribe to this conversation on GitHub. Already have an account? Sign in.

Reviewers

3 more reviewers

@ahsonkhan ahsonkhan ahsonkhan left review comments

@kunalspathak kunalspathak kunalspathak left review comments

@sandreenko sandreenko sandreenko approved these changes

Reviewers whose approvals may not affect merge requirements

Assignees

No one assigned

Labels

area-CodeGen-coreclr CLR JIT compiler in src/coreclr/src/jit and related components such as SuperPMI

Projects

None yet

Milestone

No milestone

Development

Successfully merging this pull request may close these issues.

5 participants

@EgorBo @ahsonkhan @kunalspathak @sandreenko @Dotnet-GitSync-Bot