Conditional Branches - CS 61C Course Notes

1Learning Outcomes¶

Write conditional statements in RISC-V.
Use bne instructions for if-conditions that compare on equality.

🎥 Lecture Video

Until 8:50

In the past few chapters, we have learned how to use RISC-V as a calculator. We have learned arithmetic and bitwise operations and data transfers instructions for accessing memory. To support modern programming languages, however, we need to support decision-making–meaning, the computer should be able to conditionally execute certain instructions based on the results of other instructions.

2Review: Control Flow¶

In C and higher-level languages, we specify decision-making with control flow syntax. Recall that in C, typically we execute statements sequentially. Control flow syntax creates structures that “jump” to other lines of code:

if statements (and if-else, if-else-elif, etc.)
for and while loops
Function calls^[1]

If we consider the processor as a central component, we transfer control to subsequent statements for their execution. Control flow can specify conditional or unconditional transfer to out-of-order statements. Consider the C code in Figure 2:

"TODO" — Figure 2:Illustration of unconditional and conditional control flow transfer.

The conditional if statement conditionally executes Line 4 only if n > 5; otherwise, it executes the next statement, on Line 6. By contrast, the call to foo in Line 11 unconditionally transfers control to the first statement in foo on Line 2; then, when foo returns on Line 6, control unconditionally transfers back to Line 12.

3Branches and Jumps¶

RISC-V implements control flow by changing the order of execution in the code. Specifically, such instructions transfer control by updating the program counter not to the next instruction as is the default, but another instruction. There are two types^[2] of such instructions in RV32I: unconditional jumps and conditional branches.

Unconditional jump. Always set PC to a different instruction. We introduce the primary jump instruction here:

j Label

When run, this instruction will unconditionally Jump to the instruction labeled Label.

Conditional branch. Condition on the comparison of two register values. If the condition is met, set PC to a different instruction. Otherwise, the condition is not met, so set PC to the next instruction. The general format for branch instructions is bxx rs1 rs2 Label, where “xx” specifies the type of comparison to make.

3.1Branch Example¶

How do we use branch instructions? Let’s check out beq and bne in Table 1:

Table 1:Two RV32I conditional branch instructions.

Instruction	`beq rs1 rs2 Label`	`bne rs1 rs2 Label`
Mnemonic	Branch if equal	Branch if not eual
Comparison condition	Register values are equal: `R[rs1] == R[rs2]`	Register values are not equal: `R[rs1] != R[rs2]`
Condition is met	`PC = <addr of Label>`	`PC = <addr of Label>`
Condition is not met	`PC = PC + 4`	`PC = PC + 4`

Consider the two examples below, which assume the following mapping of C integer variables to registers:

x    y    z    i    j
x10  x11  x12  x13  x14

Example 1

1
2
3
4
5
6
if (i == j) {
  x = y + z;
} else {
  x = y - z;
}
// …

Two reasonable translations of this code to RISC-V assembly are below and leverage two instruction labels, If and End.

# Choice A
       beq x13 x14 If
       sub x10 x11 x12
       j End
If:    add x10 x11 x12
End:   # …

Choice A uses beq. If i and j are equal, jump to the If label to execute the conditional add instruction. Otherwise, the processor naturally moves to the “else” condition, which is the sub instruction, after which it unconditionally jumps with j End to skip over the If-labeled instruction.

# Choice B
       bne x13 x14 Else
       add x10 x11 x12
       j End
Else:  sub x10 x11 x12
End:   # …

Choice B uses bne to invert the inequality condition in Line 1 of the C code. If i and j are not equal, skip the conditional add instruction, and go to the Else label to execute the sub instruction. If the branch is not taken (i and j are equal), then the processor naturally moves into the next instruction—the add, which is exactly what we want–and unconditionally jumps with j End to skip over the Else-labeled instruction.

Example 2

1
2
3
4
if (i == j)	{
	x = y + z;
}
// …

# Choice A
       beq x13 x14 If
       j End
If:    add x10 x11 x12
End:   # …

# Choice B
       bne x13 x14 End
       add x10 x11 x12
End:   # …

Again, both choices are valid. Again, Choice B uses bne and more closely represents the original C structure. Choice B also produces fewer instructions and will be better for performance in the long run.

4Branch Instructions Summary¶

Table 2 lists the conditional branch instructions from the RISC-V green card Control table:

Table 2:RV32I conditional branch instructions.

Instruction	Name/Description
`beq rs1 rs2 Label`	Branch if Equal
`bne rs1 rs2 Label`	Branch if Not Equal
`blt rs1 rs2 Label`	Branch if Less Than (signed) (rs1 < rs2)
`bge rs1 rs2 Label`	Branch if Greater or Equal (signed) (rs1 >= rs2)
`bltu rs1 rs2 Label`	Branch if Less Than (unsigned)
`bgeu rs1 rs2 Label`	Branch if Greater Than or Equal (unsigned)

This set^[4] is sufficient to describe the C comparators: ==, !=, >, <, >=, <= for signed and unsigned integers. From the RV32I Specification:

Note, BGT, BGTU, BLE, and BLEU can be synthesized by reversing the operands to BLT, BLTU, BGE, and BGEU, respectively.

In other words, bgt, bgtu, ble, bleu are pseudoinstructions! We leave their translation as an exercise to you :-)

We have also discussed one jump pseudoinstruction in Table 3. We will explain this pseudoinstruction in more detail in a future section.

Table 3:RV32I unconditional jump pseudoinstruction

Instruction	Name/Description
`j Label`	Unconditional jump

Footnotes¶

More later!
↩
If jumps are defined as unconditional, are there conditional jumps? What about unconditional branches? Both of these can probably be defined using the other, and you will see this overlap in terminology in lecture, in conversation, and in the literature. The RISC-V ISA is careful to refer to both “control transfer instructions” and, in almost all cases, associates the adjectives “unconditional” and “conditional” solely with “jump” and “branch,” respectively.
↩
More later.
↩
Here is Professor Bora Nikolic’s tip for remembering which branch instructions are supported: “There exists a BLT sandwich (Bacon, Lettuce, Tomato), but I have never seen a BGT sandwich.”
↩