4 ms·

It's replacing rc_bit not rc_direct (rc_direct is a fixed .5 probability), which just uses rc_bit_last, so original code is: #define rc_bit_last(prob, acti

It's replacing rc_bit not rc_direct (rc_direct is a fixed .5 probability), which just uses rc_bit_last, so original code is: #define rc_bit_last(prob, action0, action1, seq) \ do { \ rc_if_0(prob, seq) { \ rc_update_0(prob); \ action0; \ } else { \ rc_update_1(prob); \ action1; \ } \ } while (0) So it's merging the two sides of rc_update and cmov/sbb handle the difference. action0/action1 are generally blank, but rc_bit_matched makes the common action branchless as well.

dragontamer 5y ago
Thanks for the info. Realizing that the two sides of the "if" statement are effectively stored as a 1-bit of information, and then using instructions to store that 1-bit into the carry flag, and then using cmovcc / sbbl instructions to manipulate that 1-bit of information is pretty advanced. I could imagine a compiler making use of all that information, but only maybe with some programmer assistance (IE: code in the right format for easier optimizing). Or you know... an assembly programmer who just outright explicitly writes that kind of assembly language.
- brigade 5y ago
  Yeah, this sort of conversion is pretty common for the core of arithmetic/range decoders, and I definitely don't expect a compiler to be capable of the sort of transformations needed to convert the branchy form to branchless. Though I'd expect compilers to be at least 90% as good with the ternary equivalent to the asm, e.g.: tmp = code < bound ? ~0 : 0; range = code < bound ? bound : range; compiles tmp to xor -> setl -> neg (clang) or setge -> movzx -> sub (gcc) instead of sbb, but on arm64 they use just one csetm (clang) or csinv (gcc) which is basically optimal, and in all cases the comparison is reused for the cmov. https://godbolt.org/z/jPbo3qc1Y https://godbolt.org/z/jPbo3qc1Y

dragontamer 5y ago

Thanks for the info. Realizing that the two sides of the "if" statement are effectively stored as a 1-bit of information, and then using instructions to store that 1-bit into the carry flag, and then using cmovcc / sbbl instructions to manipulate that 1-bit of information is pretty advanced. I could imagine a compiler making use of all that information, but only maybe with some programmer assistance (IE: code in the right format for easier optimizing). Or you know... an assembly programmer who just outright explicitly writes that kind of assembly language.

brigade 5y ago
Yeah, this sort of conversion is pretty common for the core of arithmetic/range decoders, and I definitely don't expect a compiler to be capable of the sort of transformations needed to convert the branchy form to branchless. Though I'd expect compilers to be at least 90% as good with the ternary equivalent to the asm, e.g.: tmp = code < bound ? ~0 : 0; range = code < bound ? bound : range; compiles tmp to xor -> setl -> neg (clang) or setge -> movzx -> sub (gcc) instead of sbb, but on arm64 they use just one csetm (clang) or csinv (gcc) which is basically optimal, and in all cases the comparison is reused for the cmov. https://godbolt.org/z/jPbo3qc1Y https://godbolt.org/z/jPbo3qc1Y