Skip to content

JIT could further optimize "== 0" checks in Boolean logic #13573

Closed
#49548
Closed
JIT could further optimize "== 0" checks in Boolean logic#13573
#49548
Assignees
JulieLeeMSFT
Labels
area-CodeGen-coreclrCLR JIT compiler in src/coreclr/src/jit and related components such as SuperPMIoptimization
Milestone
6.0.0

Description

@GrabYourPitchforks
GrabYourPitchforks
opened on Oct 11, 2019

There are some well-known bit manipulation patterns that the JIT doesn't currently optimize. For instance:

public static bool AreZero(int x, int y) {
    return x == 0 && y == 0;
}

Produces this codegen:

AreZero(Int32, Int32)
    L0000: test ecx, ecx
    L0002: jnz L000d
    L0004: test edx, edx
    L0006: setz al
    L0009: movzx eax, al
    L000c: ret
    L000d: xor eax, eax
    L000f: ret

But it could produce this more optimal codegen, folding the two comparisons together into a single or and zero check:

AreZero(Int32, Int32)
    L0000: or edx, ecx
    L0002: setz al
    L0005: movzx eax, al
    L0008: ret

category:cq
theme:basic-cq
skill-level:beginner
cost:small

Activity

  1. EgorBo commented on Oct 11, 2019

    @EgorBo
    EgorBo
    on Oct 11, 2019
    Member

    Interesting, 3 (and more) arguments in AreZero actually use this optimization:

    private static bool AreZero(int x, int y, int z)
{
    return x == 0 && y == 0 && z == 0;
}

    Codegen:

    ; Method ConsoleApp2.Program:AreZero(int,int,int):bool
G_M22205_IG01:
G_M22205_IG02:
       or       edx, ecx
       jne      SHORT G_M22205_IG05
G_M22205_IG03:		;; bbWeight=0.50
       test     r8d, r8d
       sete     al
       movzx    rax, al
G_M22205_IG04:		;; bbWeight=0.50
       ret      
G_M22205_IG05:		;; bbWeight=0.50
       xor      eax, eax
G_M22205_IG06:		;; bbWeight=0.50
       ret      
; Total bytes of code: 17

    (I suspect it happens in Compiler::optOptimizeBools)

  2. EgorBo commented on Oct 11, 2019

    @EgorBo
    EgorBo
    on Oct 11, 2019
    Member

    Hack:

    private static bool AreZero(int x, int y)
{
    return x == 0 && y == 0 && BitConverter.IsLittleEndian;
}

    where BitConverter.IsLittleEndian is a runtime true constant so Roslyn won't remove it.

    Codegen:

    ; Method ConsoleApp2.Program:AreZero(int,int):bool
G_M22205_IG01:
G_M22205_IG02:
       or       edx, ecx
       jne      SHORT G_M22205_IG05
G_M22205_IG03:		;; bbWeight=0.50
       mov      eax, 1
G_M22205_IG04:		;; bbWeight=0.50
       ret      
G_M22205_IG05:		;; bbWeight=0.50
       xor      eax, eax
G_M22205_IG06:		;; bbWeight=0.50
       ret      
; Total bytes of code: 13

    😄 sharplab.io

  3. GrabYourPitchforks commented on Oct 20, 2019

    @GrabYourPitchforks
    GrabYourPitchforks
    on Oct 20, 2019
    MemberAuthor

    Similarly:

    [MethodImpl(MethodImplOptions.AggressiveInlining)]
private static bool IsEitherNegative(int a, int b)
{
    return a < 0 || b < 0;
}

    Current codegen:

        L0000: test ecx, ecx
    L0002: jl L000d
    L0004: test edx, edx
    L0006: setl al
    L0009: movzx eax, al
    L000c: ret
    L000d: mov eax, 0x1
    L0012: ret

    Possible optimal codegen below, using the fact that the or instruction sets SF:

    or ecx, edx
sets al   ; or setl, if you prefer, since "or" is known to clear OF
movzx eax, al
ret
  4. msftgits
    transferred this issue fromdotnet/coreclron Jan 31, 2020
  5. msftgits
    added this to the Future milestone on Jan 31, 2020
  6. BruceForstall
    added
    JitUntriagedCLR JIT issues needing additional triage
    on Oct 28, 2020
  7. JulieLeeMSFT
    self-assigned this
    on Jan 8, 2021
  8. JulieLeeMSFT
    modified the milestones: Future, 6.0.0 on Jan 12, 2021
  9. JulieLeeMSFT
    removed
    JitUntriagedCLR JIT issues needing additional triage
    on Jan 12, 2021

  10. JulieLeeMSFT commented on Jan 13, 2021

    @JulieLeeMSFT
    JulieLeeMSFT
    on Jan 13, 2021
    Member

    Reproduced

    • AreZero(int x, int y)
    • AreZero(int x, int y, int z), and
    • AreZero(int x, int y) with the 3rd operand, BitConverter.IsLittleEndian.

    will check where the optimization happens.

  11. JulieLeeMSFT commented on Jan 26, 2021

    @JulieLeeMSFT
    JulieLeeMSFT
    on Jan 26, 2021
    Member
    • Compiler::optOptimizeBools optimizes to OR only if both the 1st basic block (BB) and the 2nd BB are conditional jump (BBJ_COND).
    • For the two argument case, the 2nb BB is RETURN statement with comparison, thus it is not optimized.
    STMT00002 (IL 0x003...  ???)
               [000009] ------------              *  RETURN    int   
               [000008] ------------              \--*  EQ        int   
               [000006] ------------                 +--*  LCL_VAR   int    V01 arg1         
               [000007] ------------                 \--*  CNS_INT   int    0

    Plan:

    • Modify the method to add pattern matches for different cases.

  12. JulieLeeMSFT commented on Feb 13, 2021

    @JulieLeeMSFT
    JulieLeeMSFT
    on Feb 13, 2021
    Member

    I was able to modify the code to generate the optimized code for the two argument case.

    G_M56891_IG01:
G_M56891_IG02:
       or       edx, ecx
       sete     al
       movzx    rax, al
G_M56891_IG03:
       ret

; Total bytes of code 9, prolog size 0, PerfScore 3.40, instruction count 4, allocated bytes for code 9 (MethodHash=d88b21c4) for method Test:AreZero(int,int):bool

    will run diffs and tests.

  13. JulieLeeMSFT commented on Feb 17, 2021

    @JulieLeeMSFT
    JulieLeeMSFT
    on Feb 17, 2021
    Member

    jit-diff shows 1440 methods improvement.

    Top file improvements (bytes):
     -360652 : System.Net.Http.dasm (-52.74% of base)
         -18 : Microsoft.CSharp.dasm (-0.00% of base)
         -18 : System.ComponentModel.TypeConverter.dasm (-0.01% of base)
         -16 : System.Private.Xml.Linq.dasm (-0.01% of base)
         -15 : Microsoft.Extensions.Primitives.dasm (-0.06% of base)

5 total files with Code Size differences (5 improved, 0 regressed), 266 unchanged.

Top method improvements (bytes):
      -17401 (-100.00% of base) : System.Net.Http.dasm - QPackStaticTable:.cctor() (1 base, 0 diff methods)
      -16753 (-100.00% of base) : System.Net.Http.dasm - KnownHeaders:.cctor() (1 base, 0 diff methods)
       -6654 (-100.00% of base) : System.Net.Http.dasm - <GetHttp2ConnectionAsync>d__68:MoveNext():this (1 base, 0 diff methods)
       -5796 (-100.00% of base) : System.Net.Http.dasm - <SendAsync>d__27:MoveNext():this (1 base, 0 diff methods)
       -5211 (-100.00% of base) : System.Net.Http.dasm - H2StaticTable:.cctor() (1 base, 0 diff methods)
       -4775 (-100.00% of base) : System.Net.Http.dasm - <ProcessServerStreamAsync>d__49:MoveNext():this (1 base, 0 diff methods)
       -4427 (-100.00% of base) : System.Net.Http.dasm - <ProcessServerControlStreamAsync>d__50:MoveNext():this (1 base, 0 diff methods)
       -4013 (-100.00% of base) : System.Net.Http.dasm - <ProcessIncomingFramesAsync>d__49:MoveNext():this (1 base, 0 diff methods)
       -3989 (-100.00% of base) : System.Net.Http.dasm - <SendWithRetryAsync>d__72:MoveNext():this (1 base, 0 diff methods)
       -3585 (-100.00% of base) : System.Net.Http.dasm - <ConnectAsync>d__82:MoveNext():this (1 base, 0 diff methods)
       -3584 (-100.00% of base) : System.Net.Http.dasm - <SendHeadersAsync>d__83:MoveNext():this (1 base, 0 diff methods)
       -3128 (-100.00% of base) : System.Net.Http.dasm - <SendRequestBodyAsync>d__37:MoveNext():this (1 base, 0 diff methods)
       -3118 (-100.00% of base) : System.Net.Http.dasm - <SendAsync>d__4:MoveNext():this (1 base, 0 diff methods)
       -3037 (-100.00% of base) : System.Net.Http.dasm - <SendAsync>d__37:MoveNext():this (1 base, 0 diff methods)
       -2893 (-100.00% of base) : System.Net.Http.dasm - GenericHeaderParser:.cctor() (1 base, 0 diff methods)
       -2809 (-100.00% of base) : System.Net.Http.dasm - <SendContentAsync>d__29:MoveNext():this (1 base, 0 diff methods)
       -2685 (-100.00% of base) : System.Net.Http.dasm - <SendAsyncCore>d__5:MoveNext():this (1 base, 0 diff methods)
       -2618 (-100.00% of base) : System.Net.Http.dasm - <ConnectToTcpHostAsync>d__83:MoveNext():this (1 base, 0 diff methods)
       -2605 (-100.00% of base) : System.Net.Http.dasm - <ReadFrameEnvelopeAsync>d__42:MoveNext():this (1 base, 0 diff methods)
       -2588 (-100.00% of base) : System.Net.Http.dasm - <GetHttp3ConnectionAsync>d__71:MoveNext():this (1 base, 0 diff methods)

Top method improvements (percentages):
         -32 (-100.00% of base) : System.Net.Http.dasm - Http2WriteStream:Dispose(bool):this (1 base, 0 diff methods)
          -3 (-100.00% of base) : System.Net.Http.dasm - Http2WriteStream:get_CanRead():bool:this (1 base, 0 diff methods)
         -12 (-100.00% of base) : System.Net.Http.dasm - Http2WriteStream:get_CanWrite():bool:this (1 base, 0 diff methods)
         -40 (-100.00% of base) : System.Net.Http.dasm - Http2WriteStream:Read(Span`1):int:this (1 base, 0 diff methods)
         -40 (-100.00% of base) : System.Net.Http.dasm - Http2WriteStream:ReadAsync(Memory`1,CancellationToken):ValueTask`1:this (1 base, 0 diff methods)
        -239 (-100.00% of base) : System.Net.Http.dasm - Http2WriteStream:WriteAsync(ReadOnlyMemory`1,CancellationToken):ValueTask:this (1 base, 0 diff methods)
         -81 (-100.00% of base) : System.Net.Http.dasm - Http2WriteStream:FlushAsync(CancellationToken):Task:this (1 base, 0 diff methods)
         -11 (-100.00% of base) : System.Net.Http.dasm - Http2WriteStream:.ctor(Http2Stream):this (1 base, 0 diff methods)
       -3128 (-100.00% of base) : System.Net.Http.dasm - <SendRequestBodyAsync>d__37:MoveNext():this (1 base, 0 diff methods)
         -27 (-100.00% of base) : System.Net.Http.dasm - <SendRequestBodyAsync>d__37:SetStateMachine(IAsyncStateMachine):this (1 base, 0 diff methods)
         -71 (-100.00% of base) : System.Net.Http.dasm - <>c:<WaitFor100ContinueAsync>b__38_0(Object):this (1 base, 0 diff methods)
        -171 (-100.00% of base) : System.Net.Http.dasm - <>c:<WaitFor100ContinueAsync>b__38_1(Object):this (1 base, 0 diff methods)
         -61 (-100.00% of base) : System.Net.Http.dasm - <>c:<RegisterRequestBodyCancellation>b__74_0(Object):this (1 base, 0 diff methods)
        -325 (-100.00% of base) : System.Net.Http.dasm - <>c:<WaitForDataAsync>b__79_0(Object,CancellationToken):this (1 base, 0 diff methods)
       -1979 (-100.00% of base) : System.Net.Http.dasm - <WaitFor100ContinueAsync>d__38:MoveNext():this (1 base, 0 diff methods)
         -27 (-100.00% of base) : System.Net.Http.dasm - <WaitFor100ContinueAsync>d__38:SetStateMachine(IAsyncStateMachine):this (1 base, 0 diff methods)
       -1112 (-100.00% of base) : System.Net.Http.dasm - <ReadResponseHeadersAsync>d__64:MoveNext():this (1 base, 0 diff methods)
         -27 (-100.00% of base) : System.Net.Http.dasm - <ReadResponseHeadersAsync>d__64:SetStateMachine(IAsyncStateMachine):this (1 base, 0 diff methods)
       -1069 (-100.00% of base) : System.Net.Http.dasm - <ReadDataAsync>d__68:MoveNext():this (1 base, 0 diff methods)
         -27 (-100.00% of base) : System.Net.Http.dasm - <ReadDataAsync>d__68:SetStateMachine(IAsyncStateMachine):this (1 base, 0 diff methods)

1440 total methods with Code Size differences (1440 improved, 0 regressed), 258579 unchanged.

  14. AndyAyersMS commented on Feb 17, 2021

    @AndyAyersMS
    AndyAyersMS
    on Feb 17, 2021
    Member

    Unfortunately I think this may be telling you something has gone wrong -- for a change like this we would expect baseline and new jit to process the exact same number of methods.

    Output like this means the new jit did not jit (or failed while trying to jit) some methods.

          -17401 (-100.00% of base) : System.Net.Http.dasm - QPackStaticTable:.cctor() (1 base, 0 diff methods)

    Was there a message printed before he output you show above about "reconciling"?

  15. JulieLeeMSFT commented on Feb 17, 2021

    @JulieLeeMSFT
    JulieLeeMSFT
    on Feb 17, 2021
    Member

    @AndyAyersMS you are right. There were 2 base and 3 diff error messages before this, and I was looking into it. Will ping you.

  16. JulieLeeMSFT commented on Feb 17, 2021

    @JulieLeeMSFT
    JulieLeeMSFT
    on Feb 17, 2021
    Member

    jit-diff error message

    Beginning PMI CodeSize Diffs for System.Private.CoreLib.dll, framework assemblies
- Finished 201/271 Base 0/271 Diff [200.0 sec]Error running C:\runtime\artifacts\tests\coreclr\Windows.x64.Release\Tests\Core_Root\corerun.exe on C:\runtime\artifacts\tests\coreclr\Windows.x64.Release\Tests\Core_Root\System.Private.CoreLib.dll
1 errors compiling set.
Dasm command "jit-dasm-pmi --platform C:\runtime\artifacts\tests\coreclr\Windows.x64.Release\Tests\Core_Root --corerun C:\runtime\artifacts\tests\coreclr\Windows.x64.Release\Tests\Core_Root\corerun.exe --jit C:\runtime2\artifacts\bin\coreclr\Windows.x64.Checked\clrjit.dll --nocopy --output c:\diffs\dasmset_13\base C:\runtime\artifacts\tests\coreclr\Windows.x64.Release\Tests\Core_Root\System.Private.CoreLib.dll" returned with 1 failures
\ Finished 270/271 Base 0/271 Diff [281.7 sec]Error running C:\runtime\artifacts\tests\coreclr\Windows.x64.Release\Tests\Core_Root\corerun.exe on C:\runtime\artifacts\tests\coreclr\Windows.x64.Release\Tests\Core_Root\mscorlib.dll
1 errors compiling set.
Dasm command "jit-dasm-pmi --platform C:\runtime\artifacts\tests\coreclr\Windows.x64.Release\Tests\Core_Root --corerun C:\runtime\artifacts\tests\coreclr\Windows.x64.Release\Tests\Core_Root\corerun.exe --jit C:\runtime2\artifacts\bin\coreclr\Windows.x64.Checked\clrjit.dll --nocopy --output c:\diffs\dasmset_13\base C:\runtime\artifacts\tests\coreclr\Windows.x64.Release\Tests\Core_Root\mscorlib.dll" returned with 1 failures
\ Finished 271/271 Base 2/271 Diff [295.3 sec]Error running C:\runtime\artifacts\tests\coreclr\Windows.x64.Release\Tests\Core_Root\corerun.exe on C:\runtime\artifacts\tests\coreclr\Windows.x64.Release\Tests\Core_Root\System.Net.Http.dll
1 errors compiling set.
Dasm command "jit-dasm-pmi --platform C:\runtime\artifacts\tests\coreclr\Windows.x64.Release\Tests\Core_Root --corerun C:\runtime\artifacts\tests\coreclr\Windows.x64.Release\Tests\Core_Root\corerun.exe --jit C:\runtime\artifacts\bin\coreclr\Windows.x64.Checked\clrjit.dll --nocopy --output c:\diffs\dasmset_13\diff C:\runtime\artifacts\tests\coreclr\Windows.x64.Release\Tests\Core_Root\System.Net.Http.dll" returned with 1 failures
\ Finished 271/271 Base 195/271 Diff [479.7 sec]Error running C:\runtime\artifacts\tests\coreclr\Windows.x64.Release\Tests\Core_Root\corerun.exe on C:\runtime\artifacts\tests\coreclr\Windows.x64.Release\Tests\Core_Root\System.Private.CoreLib.dll
1 errors compiling set.
Dasm command "jit-dasm-pmi --platform C:\runtime\artifacts\tests\coreclr\Windows.x64.Release\Tests\Core_Root --corerun C:\runtime\artifacts\tests\coreclr\Windows.x64.Release\Tests\Core_Root\corerun.exe --jit C:\runtime\artifacts\bin\coreclr\Windows.x64.Checked\clrjit.dll --nocopy --output c:\diffs\dasmset_13\diff C:\runtime\artifacts\tests\coreclr\Windows.x64.Release\Tests\Core_Root\System.Private.CoreLib.dll" returned with 1 failures
/ Finished 271/271 Base 270/271 Diff [562.0 sec]Error running C:\runtime\artifacts\tests\coreclr\Windows.x64.Release\Tests\Core_Root\corerun.exe on C:\runtime\artifacts\tests\coreclr\Windows.x64.Release\Tests\Core_Root\mscorlib.dll
1 errors compiling set.
Dasm command "jit-dasm-pmi --platform C:\runtime\artifacts\te| Finished 271/271 Base 270/271 Diff [562.1 sec]sts\coreclr\Windows.x64.Release\Tests\Core_Root --corerun C:\runtime\artifacts\tests\coreclr\Windows.x64.Release\Tests\Core_Root\corerun.exe --jit C:\runtime\artifacts\bin\coreclr\Windows.x64.Checked\clrjit.dll --nocopy --output c:\diffs\dasmset_13\diff C:\runtime\artifacts\tests\coreclr\Windows.x64.Release\Tests\Core_Root\mscorlib.dll" returned with 1 failures
\ Finished 271/271 Base 271/271 Diff [562.1 sec]
Dasm commands returned 2 base failures, 3 diff failures.
Completed PMI CodeSize Diffs for System.Private.CoreLib.dll, framework assemblies in 566.93s

    This is the error message when running one of them, but I cannot relate it with my code change.

    c:\JitBench\jitutils>C:\runtime\artifacts\tests\coreclr\Windows.x64.Release\Tests\Core_Root\corerun.exe C:\runtime\artifacts\tests\coreclr\Windows.x64.Release\Tests\Core_Root\System.Private.CoreLib.dll
Unhandled exception. System.MissingMethodException: Entry point not found in assembly 'System.Private.CoreLib, Version=6.0.0.0, Culture=neutral, PublicKeyToken=7cec85d7bea7798e'.

  17. JulieLeeMSFT commented on Feb 20, 2021

    @JulieLeeMSFT
    JulieLeeMSFT
    on Feb 20, 2021
    Member

    Reproduced the issue. Debugging.

    In Compiler::optIsBoolComp the tree gtType was incorrectly set to TYP_VOID.

  18. ghost added
    in-prThere is an active PR which will close this issue when it is merged
    on Mar 12, 2021
  19. JulieLeeMSFT
    closed this as completedin #49548on Jul 14, 2021
  20. JulieLeeMSFT
    added a commit that references this issue on Jul 14, 2021

    "==0" optimization in Boolean logic #13573 (#49548)

    8a34e76
  21. ghost removed
    in-prThere is an active PR which will close this issue when it is merged
    on Jul 14, 2021
  22. ghost locked as resolved and limited conversation to collaborators on Aug 21, 2021
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Metadata

Metadata

Assignees

Labels

area-CodeGen-coreclrCLR JIT compiler in src/coreclr/src/jit and related components such as SuperPMIoptimization

Type

No type

Projects

No projects

    Milestone

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions