Repository navigation
Arm64: Generate conditional comparison and selection instructions #55364
Description
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
runtime/src/coreclr/jit/instrsarm64.h
Lines 633 to 639 in f0b7773
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.00Example# 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.00Example# 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.00Example# 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.00Some 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
Metadata
Metadata
Assignees
Labels
Type
Projects
- Status
Activity
a74nh commentedon Mar 16, 2022
I've been taking a look at this.
Starting with:
Gives the CIL:
Which becomes:
When running tier1
It uses the code in Lowering::OptimizeConstCompare() to change NE to TEST_NE, and generates optimal code:
When running tier0
Does not call into OptimizeConstCompare, due to MinOpts check failing.
Instead, LowerJTrue() will get called, creating a JCMP node, which generates:
Delete LowerJTrue(), then run tier0
There is no lowering, and everything emits as we'd expect:
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
This gives us optimal code in all cases
or
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?
[-]Conditional instructions/branch elimination[/-][+]Arm64: Generate conditional comparison and selection instructions[/+]kunalspathak commentedon Mar 16, 2022
That's correct, we do generate optimized code, so I have updated the PR description to reflect the current problem.
We try to do minimum optimization in tier0 for speedup and simplicity, so we mostly focus on improving the tier1 code.
a74nh commentedon Mar 18, 2022
Ok, so trying to break this down into a first step:
Ends up as two basic blocks:
That needs optimising optimising to:
If done correctly, then that should hopefully get rid of all the branches in all the examples above, which should get a large portion of the performance. We can then look at generating the other conditionals and combining instructions in the other examples.
3 remaining items
JulieLeeMSFT commentedon Aug 11, 2022
Moved to .NET 8 to finish the remaining work.
a74nh commentedon Dec 14, 2022
With the merging of #77728, some of the examples are now looking much better. There are still missing bits.
The op2 check should generate to a CMP and CSEL.
The op1 check will still be a CMP and branch.
This should be fully fixed by #79283
It won't catch when the else case is a different target to the if case, eg:
This now will do:
To make this ideal, we'd have to detect the 6 is 1 greater than the 5:
Should be a fairly straightforward to do via lowering/containing.
We'll generate:
Switching the CSEL to a CSET would get rid of the MOV. Suspect this would need changes in If Conversion pass
This is ideal now. CMP followed by CSEL.
Looking good here.
a74nh commentedon Mar 23, 2023
With #79283 now merged, example 1 will produce ideal code.
#82031 is in progress to fix example 2.
JulieLeeMSFT commentedon Mar 27, 2023
@a74nh are we going to address example 3-5 as well in the upcoming months?
a74nh commentedon Mar 28, 2023
Example 3 - Needs work
Example 4 - Fixed by #77728
Example 5 - Fixed by #77728
Having a quick look at example 3, it only saves a single mov, but it should be fairly easy to implement as it can fit into the existing csel work. I'll get @SwapnilGaikwad to look at this in Q2 so that we can close this issue.
There is also the option of using CINV for the equivalent of:
I suspect instances of this are low. Currently it generates
mvn, cmp, cselwhich can be optimised tocmp, cinv, so again just a single instruction. I'll add this as a low priority item on our list.kunalspathak commentedon May 26, 2023
I verified all the examples and they generate expected code. Thank you @a74nh , @SwapnilGaikwad and @jakobbotsch !
C# examples
Assembly code