6 ms·

Not always - https://www.godbolt.org/z/zYxeahf3T https://www.godbolt.org/z/zYxeahf3T. And for any modern (as in, made in the last two decades) x86 processor the

by dzaima 2y ago

Not always - https://www.godbolt.org/z/zYxeahf3T https://www.godbolt.org/z/zYxeahf3T. And for any modern (as in, made in the last two decades) x86 processor the branchless version will be hilariously better if the condition is unpredictable (which is a thing the compiler can't know by itself, hence wanting to have an explicit way to request a conditional move instr) and the per-branch code takes less than like multiple dozens of cycles.

dzaima 2y ago
Worse, doing one of the idioms for a conditional move ends up getting gcc to actually produce a conditional move, but clang doesn't, even with its __builtin_unpredictable: https://www.godbolt.org/z/bq9axzvjG https://www.godbolt.org/z/bq9axzvjG
- ryao 2y ago
  You want to pass -mllvm -x86-cmov-converter=false. I assume LLVM has a pass to undo conditional moves on x86 whenever a heuristic determines skipping a calculation by branching is cheaper than doing the calculation and using a conditional move. Unfortunately, the heuristic that calculates the expense often gets things wrong. That is why OpenZFS passes -mllvm -x86-cmov-converter=false to Clang for certain files where the LLVM heuristic was found to do the wrong thing: https://github.com/openzfs/zfs/commit/677c6f8457943fe5b56d7aa8807010a104563e4a https://github.com/openzfs/zfs/commit/677c6f8457943fe5b56d7a... There is an open LLVM issue regarding this: https://github.com/llvm/llvm-project/issues/62790 https://github.com/llvm/llvm-project/issues/62790 The issue explains why __builtin_unpredictable() does not address the problem. In short, the metadata is dropped when an intermediate representation is generated inside clang since the IR does not have a way to preserve the information.
  - dzaima 2y ago
    Yeah, the need of the "-mllvm -x86-cmov-converter=false" hack is stupid; forgot to check with it. In my mind I guess I equivocated that being fixed with https://reviews.llvm.org/D118118 https://reviews.llvm.org/D118118 (and indeed __builtin_unpredictable does work with ?:), but, no, that flag still improves things today for the rest of the cases.
    - deleted 2y ago
      [deleted]
    - ryao 2y ago
      It just occurred to me that Clang and GCC did not necessarily fail to use conditional moves in your examples. While they failed to use explicit cmov instructions, cmp/jmp 1 instruction/mov is actually an idiom for an implicit cmov. Some CPU instruction decoders are able to turn it into a cmov without an explicit cmov instruction. In the case of RISC-V, the designers are philosophically opposed to explicit cmov instructions and expect compilers to generate this idiom for CPUs that support cmov. I asked them to implement cmov virtual instructions to be nice to people reading RISC-V assembly, but I am not sure if anything will come of it: https://github.com/riscv/riscv-bitmanip/issues/185 https://github.com/riscv/riscv-bitmanip/issues/185 I do not know if any x86 CPUs recognize the implicit cmov idiom offhand, but if any do, then while an extra instruction was used, the conditional move would still be done on those that recognize the idiom. By the way, I just noticed a case where you really don’t want the compiler to generate a cmov, explicit or otherwise since it would risk division by zero: https://github.com/openzfs/zfs/commit/f47f6a055d0c282593fe701bcaa968225ba9d1fc#diff-0057ec872a12408eee800afa012f7ebb702620e055c9e537765b1ca1dac6533f https://github.com/openzfs/zfs/commit/f47f6a055d0c282593fe70... Here is a godbolt link showing some output: https://www.godbolt.org/z/4daKTKqfr https://www.godbolt.org/z/4daKTKqfr Interestingly, Clang correctly does not generate a cmov (implicit or explicit) for the outer ternary operation, while it does generate an explicit cmov for the inner ternary operator in MIN() without -mllvm -x86-cmov-converter=false. Passing -mllvm -x86-cmov-converter=false to Clang does not change the output, which makes Clang’s behavior correct. GCC will not generate cmov for either ternary operator, which while also technically correct, is slow. This could still have been an implicit conditional move had GCC not avoided the implicit cmov idiom. Using GCC’s __builtin_expect_with_probability() in MIN() does not cause GCC to change its output. If we remove the outer ternary, GCC will happily generate a cmov instruction. Given that GCC generally assumes that undefined behavior is not invoked to make code faster and will happily generate the cmov when there is a division by 0 bug, it is odd that upon seeing a check that verifies the assumption GCC made is true, GCC decides to stop generating a cmov. I am sure the way GCC does things is much more complicated than my interpretation of the output, but the behavior is odd enough to merit a comment.

by dzaima 2y ago

dzaima 2y ago

Worse, doing one of the idioms for a conditional move ends up getting gcc to actually produce a conditional move, but clang doesn't, even with its __builtin_unpredictable: https://www.godbolt.org/z/bq9axzvjG https://www.godbolt.org/z/bq9axzvjG

ryao 2y ago
You want to pass -mllvm -x86-cmov-converter=false. I assume LLVM has a pass to undo conditional moves on x86 whenever a heuristic determines skipping a calculation by branching is cheaper than doing the calculation and using a conditional move. Unfortunately, the heuristic that calculates the expense often gets things wrong. That is why OpenZFS passes -mllvm -x86-cmov-converter=false to Clang for certain files where the LLVM heuristic was found to do the wrong thing: https://github.com/openzfs/zfs/commit/677c6f8457943fe5b56d7aa8807010a104563e4a https://github.com/openzfs/zfs/commit/677c6f8457943fe5b56d7a... There is an open LLVM issue regarding this: https://github.com/llvm/llvm-project/issues/62790 https://github.com/llvm/llvm-project/issues/62790 The issue explains why __builtin_unpredictable() does not address the problem. In short, the metadata is dropped when an intermediate representation is generated inside clang since the IR does not have a way to preserve the information.
- dzaima 2y ago
  Yeah, the need of the "-mllvm -x86-cmov-converter=false" hack is stupid; forgot to check with it. In my mind I guess I equivocated that being fixed with https://reviews.llvm.org/D118118 https://reviews.llvm.org/D118118 (and indeed __builtin_unpredictable does work with ?:), but, no, that flag still improves things today for the rest of the cases.
  - deleted 2y ago
    [deleted]
  - ryao 2y ago
    It just occurred to me that Clang and GCC did not necessarily fail to use conditional moves in your examples. While they failed to use explicit cmov instructions, cmp/jmp 1 instruction/mov is actually an idiom for an implicit cmov. Some CPU instruction decoders are able to turn it into a cmov without an explicit cmov instruction. In the case of RISC-V, the designers are philosophically opposed to explicit cmov instructions and expect compilers to generate this idiom for CPUs that support cmov. I asked them to implement cmov virtual instructions to be nice to people reading RISC-V assembly, but I am not sure if anything will come of it: https://github.com/riscv/riscv-bitmanip/issues/185 https://github.com/riscv/riscv-bitmanip/issues/185 I do not know if any x86 CPUs recognize the implicit cmov idiom offhand, but if any do, then while an extra instruction was used, the conditional move would still be done on those that recognize the idiom. By the way, I just noticed a case where you really don’t want the compiler to generate a cmov, explicit or otherwise since it would risk division by zero: https://github.com/openzfs/zfs/commit/f47f6a055d0c282593fe701bcaa968225ba9d1fc#diff-0057ec872a12408eee800afa012f7ebb702620e055c9e537765b1ca1dac6533f https://github.com/openzfs/zfs/commit/f47f6a055d0c282593fe70... Here is a godbolt link showing some output: https://www.godbolt.org/z/4daKTKqfr https://www.godbolt.org/z/4daKTKqfr Interestingly, Clang correctly does not generate a cmov (implicit or explicit) for the outer ternary operation, while it does generate an explicit cmov for the inner ternary operator in MIN() without -mllvm -x86-cmov-converter=false. Passing -mllvm -x86-cmov-converter=false to Clang does not change the output, which makes Clang’s behavior correct. GCC will not generate cmov for either ternary operator, which while also technically correct, is slow. This could still have been an implicit conditional move had GCC not avoided the implicit cmov idiom. Using GCC’s __builtin_expect_with_probability() in MIN() does not cause GCC to change its output. If we remove the outer ternary, GCC will happily generate a cmov instruction. Given that GCC generally assumes that undefined behavior is not invoked to make code faster and will happily generate the cmov when there is a division by 0 bug, it is odd that upon seeing a check that verifies the assumption GCC made is true, GCC decides to stop generating a cmov. I am sure the way GCC does things is much more complicated than my interpretation of the output, but the behavior is odd enough to merit a comment.