RyuJit: avoid conditional jumps using cmov and similar instructions

[svick]

Conditional jumps, especially those that are hard to predict, are fairly expensive, so they should be avoided if possible. One way to avoid them is to use conditional moves and similar instructions (like sete). As far as I can tell, RuyJit never does this and I think it should.

For example, take these two methods:

[MethodImpl(MethodImplOptions.NoInlining)]
static long sete_or_mov(bool cond) {
 return cond ? 4 : 0;
}

[MethodImpl(MethodImplOptions.NoInlining)]
static long cmov(long longValue) {
 long tmp1 = longValue & 0x00000000ffffffff;
 return tmp1 == 0 ? longValue : tmp1;
}

For both of them, RyuJit generates a conditional jump:

; Assembly listing for method Program:sete_or_mov(bool):long
; Emitting BLENDED_CODE for X64 CPU with SSE2
; optimized code
; rsp based frame
; partially interruptible
; Final local variable assignments
;
; V00 arg0 [V00,T00] ( 3, 3 ) bool -> rcx
; V01 tmp0 [V01,T01] ( 3, 2 ) int -> rax
;# V02 OutArgs [V02 ] ( 1, 1 ) lclBlk ( 0) [rsp+0x00]
;
; Lcl frame size = 0

G_M60330_IG01:

G_M60330_IG02:
 84C9 test cl, cl
 7504 jne SHORT G_M60330_IG03
 33C0 xor eax, eax
 EB05 jmp SHORT G_M60330_IG04

G_M60330_IG03:
 B804000000 mov eax, 4

G_M60330_IG04:
 4863C0 movsxd rax, eax

G_M60330_IG05:
 C3 ret

; Total bytes of code 17, prolog size 0 for method Program:sete_or_mov(bool):long
; ============================================================
; Assembly listing for method Program:cmov(long):long
; Emitting BLENDED_CODE for X64 CPU with SSE2
; optimized code
; rsp based frame
; partially interruptible
; Final local variable assignments
;
; V00 arg0 [V00,T00] ( 4, 3.5) long -> rcx
; V01 loc0 [V01,T01] ( 3, 2.5) long -> rax
;# V02 OutArgs [V02 ] ( 1, 1 ) lclBlk ( 0) [rsp+0x00]
;
; Lcl frame size = 0

G_M53075_IG01:

G_M53075_IG02:
 B8FFFFFFFF mov eax, 0xFFFFFFFF
 4823C1 and rax, rcx
 4885C0 test rax, rax
 7401 je SHORT G_M53075_IG04

G_M53075_IG03:
 C3 ret

G_M53075_IG04:
 488BC1 mov rax, rcx

G_M53075_IG05:
 C3 ret

; Total bytes of code 18, prolog size 0 for method Program:cmov(long):long
; ============================================================

For comparison, here are the same methods compiled using Clang and GCC with -O1 (by Compiler Explorer):

GCC 6.2:

sete_or_mov(bool):
 test dil, dil
 setne al
 movzx eax, al
 sal rax, 2
 ret
cmov(unsigned long):
 mov eax, edi
 test rax, rax
 cmove rax, rdi
 ret

Clang 3.9.0:

sete_or_mov(bool): # @sete_or_mov(bool)
 movzx eax, dil
 shl rax, 2
 ret

cmov(unsigned long): # @cmov(unsigned long)
 mov eax, edi
 mov ecx, 4294967295
 and rcx, rdi
 cmove rax, rdi
 ret

category:cq
theme:basic-cq
skill-level:expert
cost:large
impact:small

[benaadams]

There is code for it I think but @jamesqo noticed it was never getting executed in dotnet/coreclr#6647 (comment)

Function called CodeGen::genCodeForQmarkWithCMOV

[svick]

@benaadams That code is in codegenlegacy.cpp, which, as far as I can tell, is the pre-RuyJit codegen and does not even support x64. So I'm not sure how relevant is that for RuyJit on x64.

[benaadams]

Might be why its not called then 😆

[jamesqo]

@benaadams I believe I tested it with x86 builds, without the x86 RyuJIT (which is disabled by default) enabled. Feel free to check for yourself, though, in case I messed something up.

[benaadams]

There does seem to be a lot of stuff for cmov in the code, have never seen it output though

[cmckinsey]

We used to generate CMOV/SETCC from our internal QMark operator, however we ended up expanding QMark after importer to short-circuit flow to simplify handling in downstream phases. As I recall the plan was to enable a more general if-conversion phase to identify simple cmov/setcc patterns before lowering to reconstitute them. /cc @dotnet/jit-contrib @russellhadley

I believe JIT32 (used today on x86) does generate at least SETCC, if not CMOV.

Regardless of the current state, I think we all agree with the previous comments both are pretty powerful features of the IA architecture and worth generating. Often result in smaller and faster code without the possibility of expensive mis-prediction penalties.

[russellhadley]

I agree, it's pretty important to handle both of these cases. In terms of priority @svick where is this coming from? Is it in a particular workload or benchmark? What's the opportunity here?

[svick]

@russellhadley I noticed this when I tried to modify this code in Kestrel to use cmov and failed.

But that was just "Hey, this code could be faster! No? Too bad.", I don't know if it would actually have measurable impact on the overall performance of Kestrel. So I don't think you should prioritize this based on me.

[russellhadley]

@svick It's still Kestrel and it's in one of the methods we want to get inlined into the MemoryAllocatorIterator::Seek routine and optimized - so it had some priority. Thanks for the heads up. :)

[choikwa]

@svick, that code is probably faster with bsf/tzcnt(count trailing zeroes) and lshl(logical shift left) instead of cmov/condIf's. Whether JIT knows to generate them is another question.

[benaadams]

@choikwa but ternary operators, for example, are probably a much more common pattern across the ecosystem as a first step to improve; and likely more simple to recognise - since its a language construct.

Have an improvement for that particular section of code in Kestrel in a PR aspnet/KestrelHttpServer#1138

[mikedn]

@cmckinsey @russellhadley Anyone working on this? FYI I'm trying to add support for CMOV to RyuJIT's codegen for a different issue. Maybe I can take a look at this one after that.

[pgavlin]

AFAIK nobody is looking into this at the moment. Feel free to dive in :)

[russellhadley]

@mikedn I think @benaadams has provided a branchless version of the code that motivated this in Kestrel, but getting to the point where we can generate CMOVs is still interesting. @sivarv has been working on some ideas around how to improve this kind of instruction selection. It would be good to make sure this effort dovetails.