Branches and Jumps

Without branches and jumps, a processor could only run instructions in a straight line, one after another, and every program would end after a fixed number of steps. Branches make decisions possible: if statements, loops, comparisons. Jumps make functions possible: a call goes somewhere else and comes back. RV32I has six conditional branches and two jumps, and from them the compiler builds every control structure of C. This article explains each instruction and its range, shows how real if statements, loops and function calls are compiled, and shows how often programs branch, how often branches are taken, and what each taken branch costs a pipelined processor.

13 min read | Beginner

What You'll Learn

• Use the six RV32I conditional branches and their pseudo-instruction forms
• Explain PC-relative offsets and the reach of branches and jumps
• Trace how if statements, loops and function calls become branches and jumps
• Calculate the cycles taken branches cost a pipeline from branch counts

Changing the Program Counter

Normally the program counter advances by 4 after each instruction, to the next one in memory. A control transfer instruction sets it to some other address instead. RISC-V has two kinds. A branch is conditional: it compares two registers and goes to its target only if the condition is true; otherwise execution continues with the next instruction. A branch whose condition is true is taken, otherwise it is not taken. A jump is unconditional: it always goes to its target, and it also saves a return address. The Instruction Cycle shows how the next PC is chosen each cycle.

The Six Branches

Each RV32I branch compares rs1 with rs2 and branches if the comparison holds:

Six instructions cover every comparison. "Greater than" is "less than" with the operands swapped, and "less or equal" is "greater or equal" swapped, so the assembler offers bgt a, b as blt b, a, ble a, b as bge b, a, and their unsigned forms the same way. Comparisons against zero use register x0: beqz a5 is beq a5, x0, bnez, bltz, bgez, blez and bgtz work alike. Listings are full of these pseudo-instructions, but the processor only ever sees the six real ones.

A branch compares two registers directly, without condition flags. Many ISAs split this into two instructions, a compare that sets flags and a branch that tests them. RISC-V does the test and the decision in one instruction, which saves an instruction in almost every loop and keeps instructions independent of each other. Arithmetic, Logic and Immediates explains why RISC-V has no flags.

Signed or Unsigned?

The same 32 bits compare differently as signed and unsigned numbers. 0xFFFF_FFFF is -1 when signed, which is less than 1, but 4,294,967,295 when unsigned, which is greater. The compiler picks blt/bge for C's signed types (int) and bltu/bgeu for unsigned types and pointers. Code written with unsigned types, such as the u32 in the listings here, therefore shows bltu and bgeu.

Where a Branch Can Go

The target of a branch is encoded as an offset from the branch's own address: target = PC + offset. This is PC-relative addressing. The offset is a 13-bit signed number with its lowest bit always 0, so a branch can reach any even address from 4,096 bytes before it to 4,094 bytes after it. That covers nearly every loop and if statement, which are short. PC-relative targets also make code position-independent: a function can be loaded at any address and its branches still land in the right places. RISC-V Instruction Formats and Encoding shows how the offset is stored in the B format.

Compiling an if Statement

An if statement runs a block only when a condition holds. The compiler turns that into a branch that skips the block when the condition does not hold, so it branches on the opposite condition. The bubble sort's if (a[j] > a[j + 1]) { swap } becomes:

  64:  0007a703   lw    a4,0(a5)        # a4 = a[j]
  68:  0047a683   lw    a3,4(a5)        # a3 = a[j+1]
  6c:  00e6f663   bgeu  a3,a4,78        # if a[j+1] >= a[j], the pair is in order: skip the swap
  70:  00d7a023   sw    a3,0(a5)        # swap: a[j] = old a[j+1]
  74:  00e7a223   sw    a4,4(a5)        #       a[j+1] = old a[j]
  78:  00478793   addi  a5,a5,4         # continue here either way

"a[j] > a[j+1]" is false exactly when "a[j+1] >= a[j]", which is one bgeu with the operands in that order. The swap needs no temporary variable in memory: both values are already in registers, so storing them back crosswise swaps them. An if-else adds a second jump: the then-block ends with a j over the else-block.

Compiling a Loop

A loop is a block that runs again and again, with a branch back to its start. Compilers place the test at the bottom of the loop, so each iteration needs only one branch, taken every time except the last:

The bubble sort's two nested loops show the pattern twice. The inner loop advances the pointer a5 by 4 and branches back with bne a5, a2, 64 while there are pairs left; the outer loop moves the end pointer a2 back by 4 and branches back with bne a2, a1, 60 until a pass would be empty. The C loop counters i and j have become pointer comparisons, as Loads, Stores and Addressing explains for array loops.

Bottom-tested loops explain a striking result: in simple array loops, about 99.9 percent of branches are taken. Each loop of 1,024 iterations has 1,023 taken branches back to the top and a single not-taken branch at the end.

Jumps: jal and jalr

RISC-V has two jump instructions, and both save a return address in rd:

• jal rd, offset (jump and link) jumps to PC + offset and writes PC + 4 into rd. Its 21-bit offset reaches about 1 MB in either direction.
• jalr rd, offset(rs1) (jump and link register) jumps to rs1 + offset, with the lowest bit cleared, and writes PC + 4 into rd. Because the target comes from a register, it can be anywhere, and it can be computed at run time.

With rd = x0 the return address is simply thrown away, which gives the common pseudo-instructions:

A Function Call and Return

A matrix multiplication computes s += A[i][k] * B[k][j]. Without a multiply instruction, each product is a call to the library routine __mulsi3:

 100:  00000097   auipc ra,0x0          # ra = 0x100
 104:  098080e7   jalr  ra,152(ra)      # jump to 0x100 + 152 = 0x198, ra = 0x108
 108:  00a90933   add   s2,s2,a0        # after the return: s += the product in a0
 ...
 198:  <__mulsi3>                       # multiply a0 by a1 into a0
 ...
 1b8:  00008067   ret                   # jump to ra = 0x108

The auipc and jalr pair is the expanded call: together they can reach any address, and the jalr saves 0x108, the address of the instruction after the call, in ra. __mulsi3 finishes with ret, a jump to whatever ra holds. Because the return address is in a register, the same routine can be called from anywhere and always returns to its caller. The processor has no idea that this is a "function"; it just follows jumps. How a Program Runs: Loops, Calls and the Stack explains what happens when a function calls another and ra must be saved.

Indirect Jumps

Because jalr takes its target from a register, it also implements everything whose destination is only known at run time: calls through C function pointers, virtual methods in C++, and switch statements, which compilers often turn into a jump table, an array of addresses indexed by the switch value, followed by a load and a jr. Such indirect jumps are the hardest kind of control transfer for a processor to predict, because the target can change from one execution to the next.

How Often Programs Branch

In one test of six small programs, between one in seven and more than one in three executed instructions was a branch, and most branches were taken. Simple loops took almost every branch. Programs whose decisions depend on the data are less regular: in a sort, whether a pair is swapped depends on the values, and about three quarters of branches were taken. In a linked-list program it was about two thirds.

What a Taken Branch Costs

In a pipeline, the processor fetches the next instructions before it knows whether a branch is taken. A simple five-stage pipeline decides a branch in its execute stage, the third of five, and simply keeps fetching the instructions after it. If the branch is taken, the two instructions fetched in the meantime are wrong: they are discarded, which is called a flush, and fetching restarts at the target. Each taken branch or jump therefore costs 2 extra cycles; a not-taken branch costs nothing.

That small cost adds up. In one test, flushes took 20 percent of all cycles in a checksum program and a third of all cycles in a tight array loop. A longer pipeline would lose more on each taken branch, and a processor that predicts branches well would lose far less. Reducing this cost, by deciding branches earlier or predicting them, is the subject of the Branch Prediction chapter.

Common Mistakes

        li    t0, 10
        bge   a0, t0, else      # not (x < 10): go to else
        li    a1, 1
        j     done
else:   li    a1, 2
done: