Six conditional branches
beq and bne need two registers. Four more branches test one register
against zero, and two of them also save a return address.
The conditional branches of MIPS32
MIPS32 Vol. II; mop.py MOP_REGIMM
| Property | beq rs,rt | bne rs,rt | blez rs | bgtz rs | bltz rs | bgez rs | bltzal rs | bgezal rs (bal) |
|---|---|---|---|---|---|---|---|---|
| compares | ||||||||
| branches when | ||||||||
| writes $ra? | ||||||||
| encoded as |
Select any cell to read why — and what it costs.
Two registers only for equality. Everything ordered is against zero, or goes through slt first.
What to notice
Only beq and bne see two registers. The four in the middle read one
register’s sign bit and zero-ness. The two link forms write $ra whether or
not they branch. Four of the eight hide under one opcode, told apart by rt.
The four in the middle are the
.
beqz and bnez are not new instructions: they are beq and bne with
$zero as the second register, and objdump prints them that way.
REGIMM: a sub-opcode in the rt field
bltz and bgez need only one register, so the rt field was free.
MIPS uses it as a second opcode under opcode 1, called REGIMM:
bgez $t0,+3: opcode 1 (REGIMM) with rt = 1
Which field says bgez rather than bltz?
What to notice
Opcode 1 alone does not name the instruction. rt = 1 makes it bgez; 0
would be bltz, 16 bltzal, 17 bgezal. It is the same trick as funct
for R-types (§1.3), in a different field. rs is the register tested and
the low 16 bits are the offset, as in every branch.
The two link forms are
instructions. bal label is bgezal $zero,label: since 0 ≥ 0 always holds,
it is a call that reaches ±128 KB. Section 5.3 has the far-reaching jal.
if (a < b): slt, then branch
There is no blt $a,$b. The recipe is two instructions: compute the
comparison into a register with slt (§3.4), then branch on that register
against zero.
| C | MIPS |
|---|---|
if (a < b) … | slt t,a,b then bnez t,then (or beqz t,else) |
if (a >= b) … | slt t,a,b then beqz t,then |
if (a == b) … | beq a,b,then |
if (a > 0) … | bgtz a,then |
if (n < 3) … | slti t,n,3 then bnez t,then |
Here is the last one from fib.c, with the else path. Click a C line.
if (n < 3) return 1; — fib.c and the -O0 dump
carolyne_ref/programs/fib.c; fib_o0.dump bfc0028c–bfc002a4
1if (n < 3)2 return 1;3/* else: the recursive case */bfc0028cslti v0,v0,3bfc00290beqz v0,bfc002a4bfc00294nopbfc00298li v0,1bfc0029cb bfc002d4bfc002a0nopbfc002a4lw v0,32(s8)Click any highlighted line to see it light up in the other listing, and read what it does.
What to notice
The compiler branches on the false case: beqz jumps over the then part
when n < 3 gave 0. The then part ends with a b to the end of the
function, past the else. That is the shape of every if/else: test, branch
over, body, jump past the other body.
Before reading on, decide:
How would GCC write `if (a > b)` with a in $t0 and b in $t1, branching to L when it is true?
Loops: enter at the test, branch back from the bottom
GCC shapes a loop in a particular way. It jumps to the test, which sits
at the bottom. The test then branches back to the body while the condition
holds. Watch hello.c’s loop, with the counter in a register:
hello.c's for loop, the way GCC shapes it: enter at the test, branch back from the bottom
How does `for (i = 0; i < 3; i++)` become a test and a backward branch?
program (address · word · instruction)
| PC → | 0xbfc00000 | 0x3c191000 | _start:lui $t9,0x1000 |
| 0xbfc00004 | 0x37390ff0 | ori $t9,$t9,0xff0 | |
| 0xbfc00008 | 0x24080000 | li $t0,0 | |
| 0xbfc0000c | 0x10000006 | b 0xbfc00028 | |
| 0xbfc00010 | 0x00000000 | nop | |
| 0xbfc00014 | 0x71084802 | body:mul $t1,$t0,$t0 | |
| 0xbfc00018 | 0xaf290004 | sw $t1,4($t9) | |
| 0xbfc0001c | 0x240a000a | li $t2,10 | |
| 0xbfc00020 | 0xaf2a0000 | sw $t2,0($t9) | |
| 0xbfc00024 | 0x25080001 | addiu $t0,$t0,1 | |
| 0xbfc00028 | 0x290b0003 | test:slti $t3,$t0,3 | |
| 0xbfc0002c | 0x1560fff9 | bnez $t3,0xbfc00014 | |
| 0xbfc00030 | 0x00000000 | nop | |
| 0xbfc00034 | 0xaf200008 | sw $zero,8($t9) |
registers — read · written this tick
console (what the doors printed)
▮tick 0 of 33
Nothing has run yet. The PC (program counter) points at the first instruction.
The loop is entered with a b to its TEST at the bottom. Each turn: the body (mul, print, print), the step (addiu), then the test (slti gives 1 or 0) and bnez branches back while it is 1. When i reaches 3, slti gives 0, bnez is not taken, and the program falls out. i lives in $t0 here; at -O0 GCC keeps it on the stack.
What to notice
The first branch is a b to the test: the loop is entered from below. Each
turn is body, step, slti, bnez. The bnez is the only branch per turn.
On the fourth test slti gives 0, bnez is not taken, and the program falls
out. hello_o0.dump has this exact shape at bfc001b0–bfc001ec, with i
on the stack instead of in $t0.
Why this shape? A test at the top needs two branches per turn: one out at the
top, one back at the bottom. A test at the bottom needs one. The initial
b to the test protects the case where the loop must run zero times.
Go deeper: why MIPS chose 'against zero' branches, and what Carolyne's decoder does with REGIMM
A two-register ordered compare (blt rs,rt) needs a subtractor in the
branch path, which was the longest path in the 1985 pipeline. Comparing with
zero needs only the sign bit and a zero-detect, so the four zero branches were
cheap to decide early. Equality (beq, bne) needs only an XOR and a
NOR, also cheap. Everything else was pushed to slt, which runs in the ALU
a cycle earlier. RISC-V, with a different pipeline in mind, put the full
compare back into the branch.
Carolyne’s decoder treats REGIMM as one opcode group with a matcher on rt:
the four rows of MOP_REGIMM state opcode 1 together with rt = 0, 1, 16
or 17. That is the same shape as SPECIAL’s rows stating funct: one group,
one extra field, and a test that no word matches two rows.
Can you now explain it?
Six conditional branches: two on equality, four against zero. Any ordered comparison is slt then beqz or bnez. Loops are entered at a bottom test that branches back while the condition holds.
If you remember only three things
- Against zero is cheap; between registers costs an slt. blez, bgtz, bltz, bgez read the sign bit. if (a < b) is slt + bnez.
- REGIMM hides four instructions under opcode 1. The rt field is the sub-opcode: 0, 1, 16, 17. bal is bgezal $zero.
- The compiler branches on the false case. if/else is test, branch over, body, b past the else. A loop is b to the test, body, step, test, bnez back.
Now try to explain this one yourself: a while (x != 0) loop with x
in $t0. Write the MIPS shape GCC would use, test at the bottom. Which
instruction does the test?
Go deeper: a model answer, once you have tried
Enter with b test. Then body: … the loop body …; test: bnez $t0,body;
a nop in the slot. The test is bnez itself: x != 0 is exactly “branch
if not equal to zero”, so no slt is needed. Compare that with x < 5,
which needs slti $t1,$t0,5 before the bnez $t1. Whether a test costs one
instruction or two depends on whether it is an equality with zero.
Check your understanding
0/5 answered1.Which pair branches to L when a ≥ b (signed), with a in $t0 and b in $t1?
2.What does `bgezal $t0,L` do?
3.GCC enters a loop with a `b` to the test at the bottom, then branches back from there. Why this shape?
4.What does `bgtz $t0,L` compare $t0 against?
5.bltz and bgez share opcode 1. How does the CPU tell them apart?