The Weird Concept of Branchless Programming

Is cmov branchless, or just branching by another name?

From my understanding branches are about conditional jump instructions. Here are some of them:

  JZ, JE - Jump if Zero, Jump if Equal
  JNZ, JNE - Jump if Not Zero, Jump if Not Equal
  JC - Jump if Carry
  JNC - Jump if No Carry
  JO - Jump if Overflow
  JNO - Jump if No Overflow
  JS - Jump if Signed (Negative)
  JNS - Jump if Not Signed (Positive or Zero)
  JP, JPE - Jump if Parity, Jump if Parity is Even
  JNP, JPO - Jump if Not Parity, Jump if Parity is Odd

The article's claim is that branchless code avoids branch-prediction, and therefore optimizes better on speculative CPUs for certain workloads. Jump instructions obviously incur branch-prediction; my question is is CMOV incurs branch prediction, also? Certainly the internal micro-ops behind the instructions will still need to make a prediction or stall?

That depends on how you define branch.

Say in Rust:

let foo = if bar { 1 } else { 2 };

And

let mut foo; if bar { foo = 1; } else { foo = 2; }

Despite they looked the same, functions the same and effectively the same, but the first one is the conditional move, and the second one would be a jump initially (until further compiler optimization kick in)

You will notice that for conditional move, you "get" a predictable expression for the result, but with branched jump, it's like you "get" a bunch of arbitrary statements, that writes to the expression. It may end up folding so both will essentially be compiled to cmov, but the way to representation of the assignment is different. You can be certain with conditional instructions, but you can't be certain with branched jump, otherwise we don't need branch prediction.

In fact, the way conditional instructions work is due to Church encoding, that you created a lambda function that calls the left or right function depending on the input evaluation, which can be seen as implicitly embedding the branch.

Lotsa detail, but not to the point: does cmov depend on branch prediction or not?

No, predicated instructions like CMOV do not depend on branch prediction.

CMOV is branchless. During all steps of its execution, the CPU doesn't have to invalidate any stage of its pipeline (well, excluding errors like accessing forbidden memory addresses, etc.).