Arm64: Generate conditional comparison and selection instructions

[echesakov]

Arm64 provides branchless conditional selection and comparison instructions that should be utilized by RyuJIT in the code it generates.

Reference: https://eclecticlight.co/2021/07/20/code-in-arm-assembly-conditions-without-branches/

RyuJIT already has support for them as seen below:

runtime/src/coreclr/jit/instrsarm64.h

Lines 1353 to 1375 in f0b7773

	INST1(csel, "csel", 0, IF_DR_3D, 0x1A800000)
	// csel Rd,Rn,Rm,cond DR_3D X0011010100mmmmm cccc00nnnnnddddd 1A80 0000 cond
	INST1(csinc, "csinc", 0, IF_DR_3D, 0x1A800400)
	// csinc Rd,Rn,Rm,cond DR_3D X0011010100mmmmm cccc01nnnnnddddd 1A80 0400 cond
	INST1(csinv, "csinv", 0, IF_DR_3D, 0x5A800000)
	// csinv Rd,Rn,Rm,cond DR_3D X1011010100mmmmm cccc00nnnnnddddd 5A80 0000 cond
	INST1(csneg, "csneg", 0, IF_DR_3D, 0x5A800400)
	// csneg Rd,Rn,Rm,cond DR_3D X1011010100mmmmm cccc01nnnnnddddd 5A80 0400 cond
	INST1(cinc, "cinc", 0, IF_DR_2D, 0x1A800400)
	// cinc Rd,Rn,cond DR_2D X0011010100nnnnn cccc01nnnnnddddd 1A80 0400 cond
	INST1(cinv, "cinv", 0, IF_DR_2D, 0x5A800000)
	// cinv Rd,Rn,cond DR_2D X1011010100nnnnn cccc00nnnnnddddd 5A80 0000 cond
	INST1(cneg, "cneg", 0, IF_DR_2D, 0x5A800400)
	// cneg Rd,Rn,cond DR_2D X1011010100nnnnn cccc01nnnnnddddd 5A80 0400 cond
	INST1(cset, "cset", 0, IF_DR_1D, 0x1A9F07E0)
	// cset Rd,cond DR_1D X001101010011111 cccc0111111ddddd 1A9F 07E0 Rd cond

runtime/src/coreclr/jit/instrsarm64.h

Lines 633 to 639 in f0b7773

	INST2(ccmp, "ccmp", CMP, IF_EN2F, 0x7A400000, 0x7A400800)
	// ccmp Rn,Rm, nzcv,cond DR_2I X1111010010mmmmm cccc00nnnnn0nzcv 7A40 0000 nzcv, cond
	// ccmp Rn,imm5,nzcv,cond DI_1F X1111010010iiiii cccc10nnnnn0nzcv 7A40 0800 imm5, nzcv, cond
	INST2(ccmn, "ccmn", CMP, IF_EN2F, 0x3A400000, 0x3A400800)
	// ccmn Rn,Rm, nzcv,cond DR_2I X0111010010mmmmm cccc00nnnnn0nzcv 3A40 0000 nzcv, cond
	// ccmn Rn,imm5,nzcv,cond DI_1F X0111010910iiiii cccc10nnnnn0nzcv 3A40 0800 imm5, nzcv, cond

Currently, the method emitIns_R_R_R_COND and emitIns_R_I_FLAGS_COND that produces these instructions are not utilized at all. emitIns_R_R_R_COND was recently used in #66407 to generate csneg instruction. Once these instructions are used, we could produce much better code. Below are some examples:

Example# 1:

    static void Test(uint op1, uint op2) {
        if (op1 > 0 && op2 > 0) {
            op1 = 5;
        }  else {
            op1 = 10;
        }
        Consume(op1, op2);
    }

Ideal code: https://godbolt.org/z/5ov9TKx6P
Current code:

G_M2878_IG01:
            stp     fp, lr, [sp,#-16]!
            mov     fp, sp
                                                ;; bbWeight=1    PerfScore 1.50
G_M2878_IG02:
            cbz     w0, G_M2878_IG04
                                                ;; bbWeight=1    PerfScore 1.00
G_M2878_IG03:
            cbz     w1, G_M2878_IG04
            mov     w0, #5
            b       G_M2878_IG05
                                                ;; bbWeight=0.50 PerfScore 1.25
G_M2878_IG04:
            mov     w0, #10
                                                ;; bbWeight=0.50 PerfScore 0.25
G_M2878_IG05:
            bl      _12219:Consume(int,int)
                                                ;; bbWeight=1    PerfScore 1.00
G_M2878_IG06:
            ldp     fp, lr, [sp],#16
            ret     lr
                                                ;; bbWeight=1    PerfScore 2.00

Example# 2:

    static void Test(uint op1, uint op2) {
        op1 = op1 > 0 ? 5 : 6;
        Consume(op1, op2);
    }

Ideal code: https://godbolt.org/z/GTnc4jjfG
Current code:

G_M9565_IG01:
            stp     fp, lr, [sp,#-16]!
            mov     fp, sp
                                                ;; bbWeight=1    PerfScore 1.50
G_M9565_IG02:
            cmp     w0, #0
            bgt     G_M9565_IG04
                                                ;; bbWeight=1    PerfScore 1.50
G_M9565_IG03:
            mov     w0, #6
            b       G_M9565_IG05
                                                ;; bbWeight=0.50 PerfScore 0.75
G_M9565_IG04:
            mov     w0, #5
                                                ;; bbWeight=0.50 PerfScore 0.25
G_M9565_IG05:
            bl      _12219:Consume(int,int)
                                                ;; bbWeight=1    PerfScore 1.00
G_M9565_IG06:
            ldp     fp, lr, [sp],#16
            ret     lr
                                                ;; bbWeight=1    PerfScore 2.00

Example# 3:

    static void Test(uint op1, uint op2) {
        op1 = (op1 > 0) ? 0 : 1;
        Consume(op1, op2);
    }

Ideal code: https://godbolt.org/z/GoqcsM1Tf
Current code:

G_M9565_IG01:
            stp     fp, lr, [sp,#-16]!
            mov     fp, sp
                                                ;; bbWeight=1    PerfScore 1.50
G_M9565_IG02:
            cmp     w0, #0
            bgt     G_M9565_IG04
                                                ;; bbWeight=1    PerfScore 1.50
G_M9565_IG03:
            mov     w0, #1
            b       G_M9565_IG05
                                                ;; bbWeight=0.50 PerfScore 0.75
G_M9565_IG04:
            mov     w0, wzr
                                                ;; bbWeight=0.50 PerfScore 0.25
G_M9565_IG05:
            bl      _12219:Consume(int,int)
                                                ;; bbWeight=1    PerfScore 1.00
G_M9565_IG06:
            ldp     fp, lr, [sp],#16
            ret     lr
                                                ;; bbWeight=1    PerfScore 2.00

Example# 4:

    static void Test(uint op1, uint op2, uint xyz, uint def) {
        op1 = op1 > 0 ? xyz : def;
        Consume(op1, op2);
    }

Ideal code: https://godbolt.org/z/1EfxPn48q
Current code:

G_M9565_IG01:
            stp     fp, lr, [sp,#-16]!
            mov     fp, sp
                                                ;; bbWeight=1    PerfScore 1.50
G_M9565_IG02:
            cbnz    w0, G_M9565_IG04
                                                ;; bbWeight=1    PerfScore 1.00
G_M9565_IG03:
            b       G_M9565_IG05
                                                ;; bbWeight=0.50 PerfScore 0.50
G_M9565_IG04:
            mov     w3, w2
                                                ;; bbWeight=0.50 PerfScore 0.25
G_M9565_IG05:
            mov     w0, w3
            bl      _12219:Consume(int,int)
                                                ;; bbWeight=1    PerfScore 1.50
G_M9565_IG06:
            ldp     fp, lr, [sp],#16
            ret     lr
                                                ;; bbWeight=1    PerfScore 2.00

Example# 5:

    static void Test(int op1, int op2, int xyz, int def) {
        op1 = ((op1 & op2) == 0) ? 5 : def;
        Consume(op1, op2);
    }

Ideal code: https://godbolt.org/z/fc3eddPx3
Current code:

G_M9565_IG01:
            stp     fp, lr, [sp,#-16]!
            mov     fp, sp
                                                ;; bbWeight=1    PerfScore 1.50
G_M9565_IG02:
            tst     w0, w1
            beq     G_M9565_IG04
                                                ;; bbWeight=1    PerfScore 1.50
G_M9565_IG03:
            b       G_M9565_IG05
                                                ;; bbWeight=0.50 PerfScore 0.50
G_M9565_IG04:
            mov     w3, #5
                                                ;; bbWeight=0.50 PerfScore 0.25
G_M9565_IG05:
            mov     w0, w3
            bl      _12219:Consume(int,int)
                                                ;; bbWeight=1    PerfScore 1.50
G_M9565_IG06:
            ldp     fp, lr, [sp],#16
            ret     lr
                                                ;; bbWeight=1    PerfScore 2.00

@TamarChristinaArm

Some related issues:

• RyuJit: avoid conditional jumps using cmov and similar instructions #6749 RyuJit: avoid conditional jumps using cmov and similar instructions
• RyuJIT: Optimize "X / POW2_CNS" via cmovns #41549 RyuJIT: Optimize "X / POW2_CNS" via cmovns
• [RyuJIT][arm64] Optimize "x<0" and "x>=0" #43440 [RyuJIT][arm64] Optimize "x<0" and "x>=0"

Presumably, some parts of the analysis can be implemented in platform agnostic way and benefit both Arm64 and X86 platforms.

category:cq
theme:intrinsics
skill-level:expert
cost:large
impact:medium

[a74nh]

I've been taking a look at this.

Starting with:

        static void TransformsIntoCondBr(uint op1, uint op2) {
            if ((op1 & op2) == 0) {
                op1 = op2;
            } else {
                op2 = op1;
            }
            Console.WriteLine("{0}, {1}", op1, op2);
        }

Gives the CIL:

STMT00000 ( 0x000[E-] ... ??? )
               [000005] ------------              *  JTRUE     void  
               [000004] ------------              \--*  NE        int   
               [000002] ------------                 +--*  AND       int   
               [000000] ------------                 |  +--*  LCL_VAR   int    V00 arg0         
               [000001] ------------                 |  \--*  LCL_VAR   int    V01 arg1         
               [000003] ------------                 \--*  CNS_INT   int    0

Which becomes:

                                                  /--*  t2     int    
                                                  +--*  t3     int    
N005 (  9,  8) [000004] J------N----         t4 = *  NE        int   
                                                  /--*  t4     int    
N006 ( 11, 10) [000005] ------------              *  JTRUE     void  

When running tier1
It uses the code in Lowering::OptimizeConstCompare() to change NE to TEST_NE, and generates optimal code:

                                                              /--*  t0     int    
                                                              +--*  t1     int    
Generating: N009 (  5,  6) [000004] J------N----              *  TEST_NE   void   REG NA $101
IN0001:                           tst     w19, w20
Generating: N011 (  7,  8) [000005] ------------              *  JTRUE     void   REG NA $VN.Void
IN0002:                           bne     (LARGEJMP)L_M63148_BB03

When running tier0
Does not call into OptimizeConstCompare, due to MinOpts check failing.
Instead, LowerJTrue() will get called, creating a JCMP node, which generates:

                                                              /--*  t0     int    
                                                              +--*  t1     int    
Generating: N008 (  7,  5) [000002] ------------         t2 = *  AND       int    REG x0
IN0003:                           and     w0, w0, w1
Generating: N010 (  1,  2) [000003] -c----------         t3 =    CNS_INT   int    0 REG NA
                                                              /--*  t2     int    
                                                              +--*  t3     int    
Generating: N012 (  9,  8) [000004] CNE-------N----              *  JCMP      void   REG NA
IN0004:                           cbnz    (LARGEJMP)L_M63148_BB03

Delete LowerJTrue(), then run tier0
There is no lowering, and everything emits as we'd expect:

                                                              /--*  t0     int    
                                                              +--*  t1     int    
Generating: N008 (  7,  5) [000002] ------------         t2 = *  AND       int    REG x0
IN0003:                           and     w0, w0, w1
Generating: N010 (  1,  2) [000003] -c----------         t3 =    CNS_INT   int    0 REG NA
                                                              /--*  t2     int    
                                                              +--*  t3     int    
Generating: N012 (  9,  8) [000004] J------N----              *  NE        void   REG NA
IN0004:                           cmp     w0, #0
Generating: N014 ( 11, 10) [000005] ------------              *  JTRUE     void   REG NA
IN0005:                           bne     (LARGEJMP)L_M63148_BB03

At first glance, this looks correct. However, the LowerJTrue feels wrong.
OptimizeConstCompare is skipped on tier0 due to the cost of generating the nodes.
Why isn't LowerJTrue skipped on tier0 too? As far as I can tell, the cost of calling LowerJTrue is similar to OptimizeConstCompare?

Would it make sense to

1. Enable the single optimisation in OptimizeConstCompare on tier0, and remove LowerJTrue.
   This gives us optimal code in all cases
   or
2. Remove LowerJTrue.
   This simplifies tier0 at the cost of worse code

There's probably some subtleties I'm missing (I'm not sure if OptimizeConstCompare catches all the cases LowerJTrue does). And I've not run any performance testing on any of the above.

If neither the above hold, then this issue can be closed?