12
$\begingroup$

After reading the question I'm still not sure how CPU does branching.

I understand that we have an instruction counter which points to the current instruction. And after performing conditional jump it either stays the same (increments as usual) or increases (jumps) and points to another branch, that's clear.

The problem: to define conditional jump we need a conditional jump? I mean in order to evaluate an IF the processor has to evaluate condition and IF it's true, then jump, otherwise not. It's an endless recursion.

So how does the conditional jump work on the lowest level?

$\endgroup$
8
  • 1
    $\begingroup$ The processor performs the comparison, and if it succeeds, it updates the instruction pointer with the new value. No recursion there. $\endgroup$
    – Yuval Filmus
    Apr 6, 2021 at 9:38
  • $\begingroup$ @YuvalFilmus, you said "and if it succeeds". So we have another "if" here and that's the question. To check if it succeeds we need another comparison and check if it succeeds? But to check that we need another one... And so on. You can't use "if" while you're defining "if". $\endgroup$
    – LNK
    Apr 6, 2021 at 11:14
  • 1
    $\begingroup$ Presuming you are not asking about things like branch prediction, etc? Because that adds a whole other level of complexity... $\endgroup$
    – J...
    Apr 6, 2021 at 17:56
  • 1
    $\begingroup$ Interesting question -- it reminds me a little of Carroll's Paradox about logical implication. $\endgroup$
    – John Coleman
    Apr 6, 2021 at 22:56
  • 4
    $\begingroup$ Also highly instructive : Ben Eater - Conditional jump instructions $\endgroup$
    – J...
    Apr 7, 2021 at 0:21

2 Answers 2

Reset to default
29
$\begingroup$

The problem: to define conditional jump we need a conditional jump? I mean in order to evaluate an IF the processor has to evaluate condition and IF it's true, then jump, otherwise not. It's an endless recursion.

Processors have some level of code that is directly executed, by hardware circuits. That might not be the same level that they expose as their ISA, processors may translate ISA-level instructions into some other form before really executing them or even treat ISA-level instructions as small subroutines that are implemented in micro-code, but there is still some level is not interpreted in terms of something else and built into the physical structure of the hardware.

Below is a diagram of a simple processor. The "if" in the logic of "if we need to branch then take PC+offset as next PC, otherwise take PC+4" is implemented by the top left multiplexer (labeled Mux). A multiplexer does not actually "do one thing or the other", it combines two signals and a control signal via the formula: (~condition & a) | (condition & b). That's just a boolean formula that can be implemented easily as a physical circuit.

diagram

$\endgroup$
2
  • 1
    $\begingroup$ Think of the multiplexer as a two-in one-out switch. Kinda like a mechanical switch that connects the output to either of the inputs. And instead of the switch being pushed physically by a human, it is "pushed" by a control line. So first the expression of the condition is evaluated and returns true or false (or rather high or low). And high will correspond to one input setting, while low corresponds to the other input setting. $\endgroup$
    – Dakkaron
    Apr 7, 2021 at 12:02
  • 1
    $\begingroup$ At a higher level, the C-like equivalent of this would be: mask = condition - 1; instructionCounter = (jumpTargetIf & ~mask) | (jumpTargetElse & mask); (Assuming 2s complement and condition is either 1 or 0). $\endgroup$
    – Levi
    Apr 8, 2021 at 9:44
5
$\begingroup$

The problem: to define conditional jump we need a conditional jump? I mean in order to evaluate an IF the processor has to evaluate condition and IF it's true, then jump, otherwise not. It's an endless recursion.

We can define a conditional jump in terms of a conditional move. For example, a conditional jump can be:

  1. Increment the program counter to point to the next instruction.
  2. Test the condition.
  3. Conditionally load the program counter with the jump target if the condition tested true in step 2.
  4. Go to the instruction the program counter refers to.

Notice that step 3 is executed unconditionally. It is a conditional move, but we always execute the conditional move. No jump capability of any kind is required here.

So conditional jumps are built out of conditional moves which are not implemented using any kind of jump at all. The conditional move always takes place, it just doesn't always have the semantic affect of moving anything.

It is important to understand that conditional moves can be built out of unconditional moves. If we do some math that results in the value we unconditionally move being the same as the previous value we are moving on top of, the effect is the same as if the move never occurred. So we can build the semantic effect of a conditional move entirely out of unconditional code.

Here's an example of a way to implement a conditional move that doesn't involve any conditions:

  1. Multiply the current value of the program counter by the condition.
  2. Invert the condition.
  3. Multiply the current value of the jump target by the condition.
  4. Add the result of step 3 to the program counter.

You can see that this leaves the value of the program counter unchanged if the condition is zero and loads the program counter with the jump target if the condition is one. This code is a straight-through flow with no conditional code at all.

Because a conditional move can easily be built out of unconditional operations, reducing a conditional branch to a conditional move is sufficient to implement conditional branches.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.