Kara (karaardalan.delete@this.gmail.com) on August 24, 2022 2:07 pm wrote:
>
> Since like my second year programming I stopped writing branched code totally,
> few tens of thousands lines of code in, I haven't encounter anything that
> intrinsically requires speculative branch prediction, like logically.
>
> But I write only numes.
>
> Is there any program that can't be written without a branching that can't
> be rephrased (literally, all that is is rephrasing) into branchless?
>
> Mind risc-v don't offer BPU, there's extensions but not in the requirements.

The answer to the query whether it is possible to translate _any_ code whatsoever into branchless code is: Yes, it is possible.

Not only it is possible - it is actually a very simple procedure (assuming you do not care about the efficiency nor about the non-redundancy of the result produced by the simple procedure).

A Universal Turing Machine (UTM) can be implemented using just loads, stores and basic arithmetic operations (integer addition, multiplications/shifts), without any apparent conditional branches:

LOOP:
var l = &lines[state * tape[pos]]
state = l.state
tape[pos] = l.symbol
pos += l.delta
goto LOOP // Note: This is an unconditional branch

But in many cases, if a code containing conditional branches is translated into branchless code, the branchless version runs slower. However, in many other cases, the converse is true (i.e: the branchless version is faster).

Or, if you like quantum mechanics: The above UTM loop is both branchless and branchy at the same time ---- the existence or non-existence of conditional branches in that code solely depends on how you measure it.

Or, in other words: Branch prediction and value prediction are two different manifestations of the same underlying phenomenon.

-atom