Remix.run Logo
zzo38computer 2 days ago

MMIX instruction set specifies the branch prediction explicitly.

If you also have a "branch always" and "branch never" and the compiler can generate a code to modify that instruction during the initialization of the program, then for some programs where some of the branches are known during initialization, it might modify the code when it is initialized before it is executed.

immibis 2 days ago | parent [-]

Pretty much every CPU has a "branch always" (it's called "branch" or "jump") and a "branch never" (it's called "nop"). The language support for this is the tricky part.

eigenform 2 days ago | parent | next [-]

Think you're referring to the idea that "my compiler can know that some branch is always/never taken" and turn it into an unconditional control-flow instruction (either "always jump here", or "always continue sequentially" and don't emit anything!).

But the parent comment is talking about "hinting" for branches where the compiler cannot compute this ahead of time, and the CPU is responsible for resolving it during runtime. This is usually exposed by the ISA, ie. a bit in the branch instruction encoding that tells the machine "when you encounter this instruction for the first time, the default prediction should be 'taken'."

In practice, branches are usually predicted "not-taken" by default:

- It's advantageous to assume that control-flow is sequential because [pre-]fetching sequentially is the easy case

- It's wasteful to track the target addresses of branches in your predictor if they aren't taken at least once!

zzo38computer 10 hours ago | parent | next [-]

One of the situations I was describing is if there is a branch which, whether or not it is taken is the same each time it is reached during one execution of the program, but whether or not it will be taken will be decided during the initialization of the program, before the first time that branch is reached.

gpderetta 2 days ago | parent | prev [-]

A few ISAs have used branch prediction hints but they have gone out of fashion (those on x86 are now ignored for example).

imtringued 2 days ago | parent [-]

They are useless because the compiler can simply lay out the code so that the most likely path doesn't trigger the branch and executes the code sequentially.

The pipeline has already loaded these instructions anyway, so continuing execution costs nothing. You then only need to predict the exceptional cases that do trigger the branch.

This means the only use case for branch prediction hints is for use cases where the most likely branch is changing at runtime. That is such a niche use case that it is never worth it. If you do need this, then you are better off investing into JIT instead of changing the ISA.

eigenform a day ago | parent [-]

Yep, you typically don't see it because we learned that it's easier to just assume that the default prediction is "not-taken."

AFAICT if you're hinting that a branch is biased-taken, really the only thing you might be doing is avoiding potential latency/incorrect speculation that comes with an initial misprediction (when you discover a branch that isn't currently being tracked). I think it's basically just an injunction to "don't wait for a misprediction, just install this branch in your BTB immediately" (or something along those lines).

zzo38computer 2 days ago | parent | prev [-]

For "branch always", yes, but for "branch never", it is not necessarily the same as the "nop" in many instruction sets, because it would still have an operand of the same size and format of a branch instruction, although the operand is ignored.

(For instruction sets with fixed size instructions, the "nop" will potentially work if it has an operand which is not used for any other purpose; the SWYM instruction on MMIX is also no operation but the operand may be used for communication with debuggers or for other stuff.)

dan_hawkins 2 days ago | parent [-]

You can just use "branch always" but to the next instruction (: