Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Jump to bottom

Redundant bound check "(uint)c > 'f' ? 0xFF : CharToHexLookup[c]" #81160

Closed
EgorBo opened this issue Jan 25, 2023 · 7 comments
Closed

Redundant bound check "(uint)c > 'f' ? 0xFF : CharToHexLookup[c]" #81160

EgorBo opened this issue Jan 25, 2023 · 7 comments
Assignees
@EgorBo
Labels
area-CodeGen-coreclr CLR JIT compiler in src/coreclr/src/jit and related components such as SuperPMI
Milestone
9.0.0

Comments

@EgorBo
Copy link
Member

EgorBo commented Jan 25, 2023

Bound check is not eliminated in the following snippet (from #81146 (comment)):

static int Test(char c) => FromChar_UInt_GT(c);

static int FromChar_UInt_GT(int c) => (uint)c > 'f' ? 0xFF : CharToHexLookup[c];

static ReadOnlySpan<byte> CharToHexLookup => new byte[]
{
    0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, // 15
    0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, // 31
    0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, // 47
    0x0,  0x1,  0x2,  0x3,  0x4,  0x5,  0x6,  0x7,  0x8,  0x9,  0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, // 63
    0xFF, 0xA,  0xB,  0xC,  0xD,  0xE,  0xF,  0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, // 79
    0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, // 95
    0xFF, 0xa,  0xb,  0xc,  0xd,  0xe,  0xf,  0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, // 111
    0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, // 127
    0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, // 143
    0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, // 159
    0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, // 175
    0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, // 191
    0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, // 207
    0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, // 223
    0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, // 239
    0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF  // 255
};

Codegen for Test()

; Method C:Test(ushort):int
G_M31930_IG01:              ;; offset=0000H
       4883EC28             sub      rsp, 40
						;; size=4 bbWeight=1 PerfScore 0.25

G_M31930_IG02:              ;; offset=0004H
       0FB7C1               movzx    rax, cx
       83F866               cmp      eax, 102
       7719                 ja       SHORT G_M31930_IG04
						;; size=8 bbWeight=1 PerfScore 1.50
G_M31930_IG03:              ;; offset=000CH
       3D00010000           cmp      eax, 256
       731C                 jae      SHORT G_M31930_IG06
       8BC0                 mov      eax, eax
       48BA102C824E09020000 mov      rdx, 0x2094E822C10      ; static handle
       0FB60410             movzx    rax, byte  ptr [rax+rdx]
       EB05                 jmp      SHORT G_M31930_IG05
						;; size=25 bbWeight=0.50 PerfScore 2.88
G_M31930_IG04:              ;; offset=0025H
       B8FF000000           mov      eax, 255
						;; size=5 bbWeight=0.50 PerfScore 0.12
G_M31930_IG05:              ;; offset=002AH
       4883C428             add      rsp, 40
       C3                   ret      
						;; size=5 bbWeight=1 PerfScore 1.25
G_M31930_IG06:              ;; offset=002FH
       E8BCA8495F           call     CORINFO_HELP_RNGCHKFAIL
       CC                   int3     
						;; size=6 bbWeight=0 PerfScore 0.00
; Total bytes of code: 53
@dotnet-issue-labeler
Copy link

I couldn't figure out the best area label to add to this issue. If you have write-permissions please help me learn by adding exactly one area label.

@ghost ghost added the untriaged New issue has not been triaged by the area owner label Jan 25, 2023
@EgorBo EgorBo added area-CodeGen-coreclr CLR JIT compiler in src/coreclr/src/jit and related components such as SuperPMI and removed untriaged New issue has not been triaged by the area owner labels Jan 25, 2023
@ghost
Copy link

ghost commented Jan 25, 2023

Tagging subscribers to this area: @JulieLeeMSFT, @jakobbotsch, @kunalspathak
See info in area-owners.md if you want to be subscribed.

Issue Details

Bound check is not eliminated in the following snippet (from #81146 (comment)):

static int Test(char c) => FromChar_UInt_GT(c);

static int FromChar_UInt_GT(int c) => (uint)c > 'f' ? 0xFF : CharToHexLookup[c];

static ReadOnlySpan<byte> CharToHexLookup => new byte[]
{
    0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, // 15
    0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, // 31
    0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, // 47
    0x0,  0x1,  0x2,  0x3,  0x4,  0x5,  0x6,  0x7,  0x8,  0x9,  0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, // 63
    0xFF, 0xA,  0xB,  0xC,  0xD,  0xE,  0xF,  0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, // 79
    0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, // 95
    0xFF, 0xa,  0xb,  0xc,  0xd,  0xe,  0xf,  0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, // 111
    0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, // 127
    0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, // 143
    0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, // 159
    0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, // 175
    0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, // 191
    0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, // 207
    0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, // 223
    0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, // 239
    0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF  // 255
};

Codegen for Test()

; Method C:Test(ushort):int
G_M31930_IG01:              ;; offset=0000H
       4883EC28             sub      rsp, 40
						;; size=4 bbWeight=1 PerfScore 0.25

G_M31930_IG02:              ;; offset=0004H
       0FB7C1               movzx    rax, cx
       83F866               cmp      eax, 102
       7719                 ja       SHORT G_M31930_IG04
						;; size=8 bbWeight=1 PerfScore 1.50
G_M31930_IG03:              ;; offset=000CH
       3D00010000           cmp      eax, 256
       731C                 jae      SHORT G_M31930_IG06
       8BC0                 mov      eax, eax
       48BA102C824E09020000 mov      rdx, 0x2094E822C10      ; static handle
       0FB60410             movzx    rax, byte  ptr [rax+rdx]
       EB05                 jmp      SHORT G_M31930_IG05
						;; size=25 bbWeight=0.50 PerfScore 2.88
G_M31930_IG04:              ;; offset=0025H
       B8FF000000           mov      eax, 255
						;; size=5 bbWeight=0.50 PerfScore 0.12
G_M31930_IG05:              ;; offset=002AH
       4883C428             add      rsp, 40
       C3                   ret      
						;; size=5 bbWeight=1 PerfScore 1.25
G_M31930_IG06:              ;; offset=002FH
       E8BCA8495F           call     CORINFO_HELP_RNGCHKFAIL
       CC                   int3     
						;; size=6 bbWeight=0 PerfScore 0.00
; Total bytes of code: 53
Author: EgorBo
Assignees: -
Labels:

area-CodeGen-coreclr, untriaged
Milestone: -

@EgorBo EgorBo self-assigned this Jan 25, 2023
@EgorBo EgorBo added this to the 8.0.0 milestone Jan 25, 2023
@EgorBo EgorBo mentioned this issue Jan 25, 2023
Closed
@xtqqczze
Copy link
Contributor

@AndyAyersMS Is this #35348?

@AndyAyersMS
Copy link
Member

@AndyAyersMS Is this #35348?

Similar but not quite the same -- comparisons for bounds checks are handled specially, eg the redundant branch optimizer doesn't see them or reason about them. The issue above is probably something range prop or assertion prop should handle.

@EgorBo EgorBo mentioned this issue Jan 28, 2023
Closed
@ghost ghost added in-pr There is an active PR which will close this issue when it is merged and removed in-pr There is an active PR which will close this issue when it is merged labels Jan 28, 2023
@EgorBo EgorBo modified the milestones: 8.0.0, Future Mar 26, 2023
@chinason
Copy link

chinason commented Sep 21, 2023 •
edited
Loading

Because CharToHexLookup is a getter and will create new byte[] for each calling,
So, I think cache CharToHexLookup in FromChar method is a good choice.
Otherwise the lookup array will be allocated twice.
See the following code.

[MethodImpl(MethodImplOptions.AggressiveInlining)]
public static int FromChar(int c)
{
      // return c >= CharToHexLookup.Length ? 0xFF : CharToHexLookup[c];
      var lookup = CharToHexLookup;
      return c >= lookup.Length ? 0xFF : lookup[c];
 }

@stephentoub
Copy link
Member

Because CharToHexLookup is a getter and will create new byte[] for each calling,

It won't, actually. While this syntax looks like it's allocating an array, it gets compiled by the C# compiler into simply constructing a span that points directly into assembly data.

This was referenced Feb 2, 2024
Closed
Merged
@ghost ghost added in-pr There is an active PR which will close this issue when it is merged and removed in-pr There is an active PR which will close this issue when it is merged labels Feb 3, 2024
@EgorBo EgorBo modified the milestones: Future, 9.0.0 Feb 3, 2024
@EgorBo
Copy link
Member Author

EgorBo commented Mar 16, 2024

Fixed by #97908

@EgorBo EgorBo closed this as completed Mar 16, 2024
@github-actions github-actions bot locked and limited conversation to collaborators Apr 15, 2024
Sign up for free to subscribe to this conversation on GitHub. Already have an account? Sign in.
Assignees

@EgorBo EgorBo

Labels
area-CodeGen-coreclr CLR JIT compiler in src/coreclr/src/jit and related components such as SuperPMI
Projects
None yet
Milestone
9.0.0
Development

Successfully merging a pull request may close this issue.

Optimize some bound checks around "(uint)x < cns" pattern EgorBo/runtime-1
5 participants
@EgorBo @chinason @stephentoub @AndyAyersMS @xtqqczze