Consider detecting and optimizing common range check patterns

It is very common to see code such as:
(num >= '0' && num <= '9')

The efficient way to emit such checks is:
(uint)(num - '0') <= ('9' '- '0')

That often comes up in code reviews (see:dotnet/corefxlab#1616 )

It should not be too hard to handle this kind of strength reduction in th ecompiler.

Or do this in the dedicated IL optimizer: dotnet/roslyn#15929

If you have gaps in the range but the total span can fit in a mask for the integer type, you can use this (showing the case for [0-46-9]):

((1 << (num - '0')) & 0x3DF) != 0

We used this in antlr/antlr4#89.

If you have gaps in the range but the total span can fit in a mask for the integer type

And of course, it works well if it fits in a long and you're running on 64 bit. The trouble with doing IL optimizations is that you can't be sure what CPU the code will end up running on.

Is this really going to be in the compiler or we should regex the heck out of the source?

we should regex the heck out of the source?

LOL. IMO it should be in the JIT compiler.

It's interesting that gcc does this no matter how you write it,

bool f(char c) {
   switch (c) { case '0': case '1': return true; }
   return false;
}
bool f(char c) {
   return c == '0' || c == '1';
}

try on https://godbolt.org.

@sharwell

It's interesting that gcc does this no matter how you write it,

Yes, and all other C/C++ compilers. These optimizations (range check, the sparse range check mentioned by @sharwell and some forms of switches like the one in your example) work together. The compiler is supposed to recognize all these is var x in set of constants/ranges patterns and generate efficient code.

We are considering adding a range pattern, e.g. (num is '0'..'9'). If we do that, we would generate "optimized" code for the range pattern from the start.

MSVC can emit a bit test x86 instruction for this. That would be available to the JIT or as an intrinsic to the C# compiler (assuming that it is OK to take a dependency on something like that).

FWIW the JIT already emits BT for certain switch instructions:

            switch (i)
            {
            case 3:
            case 5:
            case 8:
            case 9:
            case 12:
            case 13:
                Console.WriteLine("BT was here!");
                break;
            default:
                Console.WriteLine("BT was not here!");
                break;
            }

generates:

G_M15779_IG02:
       83C1FD               add      ecx, -3
       83F90A               cmp      ecx, 10
       7722                 ja       SHORT G_M15779_IG05
       B865060000           mov      eax, 0x665
       0FA3C8               bt       eax, ecx
       7318                 jae      SHORT G_M15779_IG05
G_M15779_IG03:
       48B99831FA1D62020000 mov      rcx, 0x2621DFA3198
       488B09               mov      rcx, gword ptr [rcx]
       E85FFCFFFF           call     System.Console:WriteLine(ref)
       90                   nop
G_M15779_IG04:
       4883C428             add      rsp, 40
       C3                   ret
G_M15779_IG05:
       48B9A031FA1D62020000 mov      rcx, 0x2621DFA31A0
       488B09               mov      rcx, gword ptr [rcx]
       E847FCFFFF           call     System.Console:WriteLine(ref)
       90                   nop
G_M15779_IG06:

Moving to the coreclr so it can be done for all languages.

Duplicate of #8418

Closing as dup

@gafter

@gafter @BruceForstall actually it makes sense to do in Roslyn too

static bool Foo1(char num) => (num >= '0' && num <= '9');

RyuJIT imports it as 3 basic-blocks:

*  JTRUE     void  
\--*  LT        int   
   +--*  LCL_VAR   ushort V00 arg0         
   \--*  CNS_INT   int    48


*  RETURN    int   
\--*  CNS_INT   int    0


*  RETURN    int   
\--*  EQ        int   
   +--*  GT        int   
   |  +--*  LCL_VAR   ushort V00 arg0         
   |  \--*  CNS_INT   int    57
   \--*  CNS_INT   int    0

And if you optimize it in roslyn it will be a single-bb during RyuJIT import phase, e.g.:

static bool Foo2(char num) => (uint)(num - '0') <= ('9' - '0');

*  RETURN    int   
\--*  EQ        int   
   +--*  GT        int   
   |  +--*  SUB       int   
   |  |  +--*  LCL_VAR   ushort V00 arg0         
   |  |  \--*  CNS_INT   int    48
   |  \--*  CNS_INT   int    9
   \--*  CNS_INT   int    0

RyuJIT's inliner simply gives up if a method has more than 5 basic-blocks.

Just check this example: EgorBo@b7f15b7

Also it'd make IL code (= dll size) smaller as a bonus.

Navigation Menu

Repository navigation

Consider detecting and optimizing common range check patterns #13347

Metadata

Assignees

Labels

Type

Projects

Milestone

Relationships

Development

Consider detecting and optimizing common range check patterns #13347

Description

Activity

jkotas commented on Jun 21, 2017

sharwell commented on Jun 21, 2017

mikedn commented on Jun 22, 2017

alrz commented on Jun 24, 2017

mikedn commented on Jun 24, 2017

alrz commented on Jun 25, 2017

mikedn commented on Jun 25, 2017

gafter commented on Nov 19, 2017

GSPP commented on Aug 30, 2019

mikedn commented on Aug 30, 2019

gafter commented on Aug 31, 2019

mikedn commented on Sep 2, 2019

BruceForstall commented on Sep 4, 2019

EgorBo commented on Apr 4, 2020

Metadata

Metadata

Assignees

Labels

Type

Projects

Milestone

Relationships

Development

Issue actions