Conditional Branching In Instruction Set Architecture

Instruction Sets use an if-goto style for conditional branching.  I've written several posts on how to logically transform structured statements like loops and if-then-else statement into this if-goto style.

In this post, I'm going to speak to the translation of the if-condition-then-goto statement into instruction sets of several different machine architectures.

Let's take a look at a basic if-goto statement:

    if ( i >= n ) goto exitLoop;

This one statement has 4 operands that the hardware has to consider:

The issue here is that, generally speaking, there are too many operands, and they would add up to one of the largest instructions in the machine.  The last operand, the branch target, in particular, is fairly large operand typically 8 or more bits.

Rather than implement all the above capabilities within a single instruction with lots of operands and options, most instruction sets break this set of functionality into several instructions.  Common cases may be optimized to one instruction, while others take more.

MIPS

MIPS chooses to provide and if-goto for == and != operators directly in one instruction:
    beq $r1, $r2, target, and,
    bne $r1, $r2, target.

These allow comparing two registers for equality or inequality and branching to a target conditionally.  Note that the special constant 0 can be also used in one of the register positions (by referencing the MIPS-always-zero-valued register $0), which provides a handy way to branch on zero or non-zero of a single register's value in one instruction.

Note that the magnitude checking operators: <, <=, >, >= are left out, as well as all comparisons involving constants, except zero (e.g if ( n >= 100 ) goto stop;).

In order to do the other relational operators, there are four additional instructions, the first two for register-to-register:
    slt $r1, $r2, $r3 — outputs a boolean in $r1 for $r2 < $r3, and,
    sltu $r1, $r2, $r3 — outputs a boolean in $r1 for $r2 < $r3 (unsigned)
And the next two for register-to-immediate:
    slti $r1, $r2, #imm — outputs a boolean in $r1 for $r2 < #imm, and,
    sltiu $r1, $r2, #imm — outputs a boolean in $r1 for $r2 < #imm (unsigned)

If an immediate to compare with cannot be represented a larger immediate is loaded into a scratch register and the register-to-register form is used.  (This is also the approach for equality and inequality testing against (non-zero) constants using beq and bne.)

Sequences of instructions (slt, beq — or — li, beq) accomplish the if-goto; like most code sequences, these instructions in these sequences are interconnected via one or more of the standard registers in the instruction set.

MIPS allows for a 16-bit number for the branch target, giving it a rather larger range.

RISC V

RISC V uses a comare and branch with branch target width of 12 bits wide, as compared with MIPS' 16 bits wide — this reduction in range allows room to express all of the relational operators within a single branch instruction.  Like MIPS, RISC V compare and branch supports only register-to-register.  RISC V also shares the idea of the always-zero register $0, and also requires constants/immediates to be loaded into a register in order to use the register-to-register compare & branch instruction.

Condition Codes

An alternate approach used by many other processors (e.g. x86, 6502, MC68000, etc..) is that of condition codes, which are a set of (usually) 4 1-bit registers known also as "flags".  These special registers hold the state that interconnects instructions: typically, one for specifying the operands to compare (setting the flags), and the next to identify the desired comparison operator (testing the flags) and the branch target.  As an extra efficiency on code size, many instructions also set the condition codes, which means a dedicated comparison operation is sometimes not needed.  The 4 bits capture the notion of equal, not equal, and the signed and unsigned magnitude relations.