Branch instructions perform a test by evaluating a logical condition and depending on the outcome of the condition modify the program counter to take the branch or continue to the next instruction.
Branch instructions are always relative to the current program counter. That is, the next instruction is obtained by adding a signed offset to current program counter:
PC += (int)offsetBranches are inherently relocatable. That is, the program can be moved to any other block of memory and still execute correctly. Jump instructions, by contrast, specify an absolute memory reference. If the underlying program is moved in memory, those jump memory references pointing to the interior of the moved block must be changed.
The table below lists the branch instructions of the MIPS computer.
| Instruction | Description | Function | |||||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| B | Unconditional Branch (Assembler idiom for: BEQ r0, r0, offset) | PC += (int)offset | |||||||||||||||
| BEQ | Branch On Equal |
if Rs == Rt PC += (int)offset |
Note that the unconditional branch (B) instruction is actually a pseudo-instruction, derived from a simple variation of the BEQ instruction.
Note also that there are actually only three different conditions calculated, and there are separate branch instructions associated with whether the condition is true or false. This is summarized in the table below.
| condition | true | false |
|---|---|---|
| Rs == Rt | BEQ | BNE |
| Rs[31] | BLT | BGEZ |
| Rs[31] || Rs==0 | BLEZ | BGTZ |
Branches are used in controlling the order in which instructions are executed. The disassembly for the branch routine illustrates several if statements.
The example program includes a for loop. The disassembly listing groups code according to C statement - but the addresses are out of order. Here is the disassembly ordered by address:
25: for (i=0; i<10; i++) {
9D00007C AFC00010 sw zero,16(s8) M[s8+16] = i = 0
9D000080 8FC20010 lw v0,16(s8) v0 = i
9D000084 2842000A slti v0,v0,10 v0 = (i<10)
9D000088 1040000A beq v0,zero,0x9d0000b4 branch to finish
9D00008C 00000000 nop if condition is not satisified
26: sum += i;
9D000090 8FC30014 lw v1,20(s8) v1 = M[s8+20] = sum
9D000094 8FC20010 lw v0,16(s8) v0 = M[s8+16] = i
9D000098 00621021 addu v0,v1,v0 v0 = sum + i
9D00009C AFC20014 sw v0,20(s8) M[s8+20] = sum = v0
25 (continued): this does i++
9D0000A0 8FC20010 lw v0,16(s8) v0 = M[s8+16] = i
9D0000A4 24420001 addiu v0,v0,1 v0 = v0 + 1
9D0000A8 AFC20010 sw v0,16(s8) M[s8+16] = i = v0
9D0000AC 1000FFF4 beq zero,zero,0x9d000080 branch unconditionally (backward)
9D0000B0 00000000 nop
27: }
32: return 0;
for loop finishes here:
9D0000B4 00001021 addu v0,zero,zero v0 = zero
33: }
9D0000B8 03C0E821 addu sp,s8,zero
9D0000BC 8FBF002C lw ra,44(sp)
9D0000C0 8FBE0028 lw s8,40(sp)
9D0000C4 27BD0030 addiu sp,sp,48
9D0000C8 03E00008 jr ra
9D0000CC 00000000 nop
Example 1:
9D000088 1040000A beq v0,zero,0x9d0000b4 branch to finish
immed = 0xA is the signed word offset. Multiply by four to get the byte offset: 4 * 0xA = 0x28. Add the offset to the incremented PC:
newPC = oldPC + 4 + offset
0x9d0000b4 = 0x9D000088 + 4 + 0x28
Example 2:
9D0000AC 1000FFF4 beq zero,zero,0x9d000080 branch unconditionally (backward)immed = 0xFFF4 = -12 (decimal)
newPC = oldPC + 4 + offset
0x9d000080 = 0x9D0000AC + 4 - 0x30
C Source
Results (Microsoft C)
Disassembly Listing
Download: branch.zip.
01: // comment the following line to enable Microsoft C
02: #define PIC32
03: #if defined(PIC32)
04: #include <p32xxxx.h>
05: // comment the following line to enable debug output
06: #define UART2_IO
07: #include "db_utils.h"
08: #else // Microsoft C
09: #include <stdio.h>
10: #define DBPRINTF printf
11: #define DBPUTS(s)
12: #endif
13:
14: int branch(int a, int b);
15:
16: int main()
17: {
18: int i, sum;
19: int n1,n2,n3,n4;
20: n1 = branch(5,3);
21: n2 = branch(-2,7);
22: n3 = branch(3,3);
23: n4 = branch(-3,-5);
24: sum = 0;
25: for (i=0; i<10; i++) {
26: sum += i;
27: }
28:
29: DBPRINTF("%d %d %d %d\n",n1,n2,n3,n4);
30: DBPRINTF("sum = %d\n",sum);
31: DBPUTS("Program terminated. Click HALT and then RESET to stop the microcontroller. \n");
32: return 0;
33: }
34:
35: int branch(int a, int b)
36: {
37: if (a==b) {
38: return 0;
39: }
40: if (a<b) {
41: return 1;
42: }
43: if (a<=0) {
44: return 2;
45: }
46: if (a>=0) {
47: return 3;
48: }
49: return -1;
50: }
The equivalent assembly language is of more interest than the results, but here are the results as run under Microsoft C.
3 1 0 2 sum = 45
--- C:\pic32\test\branch.c ---------------------------------------------------------------------
1: // comment the following line to enable Microsoft C
2: #define PIC32
3: #if defined(PIC32)
4: #include <p32xxxx.h>
5: // comment the following line to enable debug output
6: #define UART2_IO
7: #include "db_utils.h"
8: #else // Microsoft C
9: #include <stdio.h>
10: #define DBPRINTF printf
11: #define DBPUTS(s)
12: #endif
13:
14: int branch(int a, int b);
15:
16: int main()
17: {
9D000018 27BDFFD0 addiu sp,sp,-48
9D00001C AFBF002C sw ra,44(sp)
9D000020 AFBE0028 sw s8,40(sp)
9D000024 03A0F021 addu s8,sp,zero
18: int i, sum;
19: int n1,n2,n3,n4;
20: n1 = branch(5,3);
9D000028 24040005 addiu a0,zero,5
9D00002C 24050003 addiu a1,zero,3
9D000030 0F400034 jal 0x9d0000d0
9D000034 00000000 nop
9D000038 AFC20018 sw v0,24(s8)
21: n2 = branch(-2,7);
9D00003C 2404FFFE addiu a0,zero,-2
9D000040 24050007 addiu a1,zero,7
9D000044 0F400034 jal 0x9d0000d0
9D000048 00000000 nop
9D00004C AFC2001C sw v0,28(s8)
22: n3 = branch(3,3);
9D000050 24040003 addiu a0,zero,3
9D000054 24050003 addiu a1,zero,3
9D000058 0F400034 jal 0x9d0000d0
9D00005C 00000000 nop
9D000060 AFC20020 sw v0,32(s8)
23: n4 = branch(-3,-5);
9D000064 2404FFFD addiu a0,zero,-3
9D000068 2405FFFB addiu a1,zero,-5
9D00006C 0F400034 jal 0x9d0000d0
9D000070 00000000 nop
9D000074 AFC20024 sw v0,36(s8)
24: sum = 0;
9D000078 AFC00014 sw zero,20(s8)
Note that in the for loop below, the assembly is grouped according to the C statement - but the addresses are out of order. Some of the operation of the for occurs after the body of the loop.
25: for (i=0; i<10; i++) {
9D00007C AFC00010 sw zero,16(s8)
9D000080 8FC20010 lw v0,16(s8)
9D000084 2842000A slti v0,v0,10
9D000088 1040000A beq v0,zero,0x9d0000b4
9D00008C 00000000 nop
9D0000A0 8FC20010 lw v0,16(s8)
9D0000A4 24420001 addiu v0,v0,1
9D0000A8 AFC20010 sw v0,16(s8)
9D0000AC 1000FFF4 beq zero,zero,0x9d000080
9D0000B0 00000000 nop
26: sum += i;
9D000090 8FC30014 lw v1,20(s8)
9D000094 8FC20010 lw v0,16(s8)
9D000098 00621021 addu v0,v1,v0
9D00009C AFC20014 sw v0,20(s8)
27: }
28:
29: DBPRINTF("%d %d %d %d\n",n1,n2,n3,n4);
30: DBPRINTF("sum = %d\n",sum);
31: DBPUTS("Program terminated. Click HALT and then RESET to stop the microcontroller. \n");
32: return 0;
9D0000B4 00001021 addu v0,zero,zero
33: }
9D0000B8 03C0E821 addu sp,s8,zero
9D0000BC 8FBF002C lw ra,44(sp)
9D0000C0 8FBE0028 lw s8,40(sp)
9D0000C4 27BD0030 addiu sp,sp,48
9D0000C8 03E00008 jr ra
9D0000CC 00000000 nop
The function below
illustrates the use of branching in if statements.
Maintained by John Loomis,
updated Mon Aug 11 23:50:07 2008
35: int branch(int a, int b)
36: {
9D0000D0 27BDFFF0 addiu sp,sp,-16
9D0000D4 AFBE0008 sw s8,8(sp)
9D0000D8 03A0F021 addu s8,sp,zero
9D0000DC AFC40010 sw a0,16(s8) M[s8+16] = a0 = a
9D0000E0 AFC50014 sw a1,20(s8) M[s8+20] = a1 = b
37: if (a==b) {
9D0000E4 8FC30010 lw v1,16(s8) v1 = a
9D0000E8 8FC20014 lw v0,20(s8) v0 = b
9D0000EC 14620004 bne v1,v0,0x9d000100 bne skips ahead
9D0000F0 00000000 nop
38: return 0;
9D0000F4 AFC00000 sw zero,0(s8) M[s8] = 0 (return value)
9D0000F8 1000001A beq zero,zero,0x9d000164 goto exit
9D0000FC 00000000 nop
39: }
40: if (a<b) {
9D000100 8FC20010 lw v0,16(s8) v0 = a
9D000104 8FC30014 lw v1,20(s8) v1 = b
9D000108 0043102A slt v0,v0,v1 v0 = (a<b)
9D00010C 10400005 beq v0,zero,0x9d000124 branch is v0 not set
9D000110 00000000 nop
41: return 1;
9D000114 24020001 addiu v0,zero,1
9D000118 AFC20000 sw v0,0(s8)
9D00011C 10000011 beq zero,zero,0x9d000164 goto exit
9D000120 00000000 nop
42: }
43: if (a<=0) {
9D000124 8FC20010 lw v0,16(s8) v0 = a
9D000128 1C400005 bgtz v0,0x9d000140 branch if a > 0
9D00012C 00000000 nop
44: return 2;
9D000130 24020002 addiu v0,zero,2
9D000134 AFC20000 sw v0,0(s8)
9D000138 1000000A beq zero,zero,0x9d000164 goto exit
9D00013C 00000000 nop
45: }
46: if (a>=0) {
9D000140 8FC20010 lw v0,16(s8) v0 = a
9D000144 04400005 bltz v0,0x9d00015c branch if a < 0
9D000148 00000000 nop
47: return 3;
9D00014C 24020003 addiu v0,zero,3
9D000150 AFC20000 sw v0,0(s8)
9D000154 10000003 beq zero,zero,0x9d000164 goto exit
9D000158 00000000 nop
48: }
49: return -1;
9D00015C 2402FFFF addiu v0,zero,-1 v0 = -1
9D000160 AFC20000 sw v0,0(s8) M[s8] = v0
50: }
9D000164 8FC20000 lw v0,0(s8) exit: v0 = M[s8]
9D000168 03C0E821 addu sp,s8,zero restore stack and return
9D00016C 8FBE0008 lw s8,8(sp)
9D000170 27BD0010 addiu sp,sp,16
9D000174 03E00008 jr ra
9D000178 00000000 nop