The Branch Instruction (without the times-4 trick; we'll do it later)

Here's a picture of a branch instruction. We'll use it to present some terminology.

• This is an I-format instruction
• The opcode and register fields (colors) are old hat. We won't pay much attention to them.
• The immediate field (white) is the one we're interested in here. We'll call it the branch offset.
• The actual address that we need to branch to is called the branch target.

There are two different aspects of this that we need to study:

1. What does the CPU do to execute a branch instruction?
2. What does the assembler do to assemble a branch instruction?

Let's tackle the first one first (with no tricks yet). Here's some code (with addresses):

  0x124:   add  $5  $10  $15
  0x128:   add  $6  $11  $16
  0x12C:   beq  $7  $12  0x138  <-- HERE'S THE BRANCH
  0x130:   add  $5  $10  $15    <-- PC is here by the time the CPU is ready to execute the branch
  0x134:   add  $6  $11  $16
  0x138:   add  $7  $12  $17    <-- this is the branch target
  0x13C:   add  $5  $10  $15
  0x140:   add  $6  $11  $16
      

• The branch instruction is at address 0x12C
• Part of fetching an instruction is to change the PC so that it points to the next instruction in line
• What that means is that we add 4 to the PC
• In this case, the PC will point to address 0x130 while the CPU is executing the instruction at 0x12C
• The branch target is 0x138
• Branches use PC-relative mode to compute the branch target
• The computation is simple: branch_target = PC + branch_offset
• In this instance the offset will be 0x8 (we'll see why in just a bit)
• That is, branch_target = PC + branch_offset = 0x130 + 0x8 = 0x138
• The last thing the CPU does for the branch is to copy the computed target address into the PC
• So the next instruction to be fetched will be the one at 0x138
• That is, the execution order for this code is: 0x124, 0x128, 0x12C, 0x138, 0x13C, 0x140
• So the effect of the branch is to skip the instructions at 0x130 and 0x134
• We can use this to make if statements
• "if condition do stuff" will be implemented as "if not condition skip over stuff"
• Here is the instruction in our pictorial representation: (the 0x8 is 0000-0000-0000-1000 in binary)

Now let's tackle the second one (still with no tricks); how did the assembler come up with 0x8 for the offset?

• The assembler is just assembling away, having a glorious time with all those easy add instructions
• Then it hits the branch; this is different; we need to think
• We can play what we just did backwards in our minds to figure out what the assembler needs to do
• In particular, we rewrite the equation as branch_offset = branch_target - PC
• branch-target = 0x138; that's right there in the instruction, but what about PC?
• The instruction will be placed into address 0x12C, so the PC will be 0x12C + 4 = 0x130 while the CPU is calculating the branch target
• So branch_offset = branch_target - PC = 0x138 - 0x130 = 0x8
• Or just do this -- start at the incremented PC and count forward to the target; 2 in this case; now multiply by 4 (you just counted words, and each word is 4 bytes), and there you are: 8
• One more note here, suppose we keep all the instructions the same but move them en bloc to 0x200, 0x204, 0x208, etc.
• The distance between the branch instruction and its target remains the same, so the branch offset also remains the same, so the entire branch instruction remains the same
• Branches are an example of what is called position-independent code
• When this code is relocated by the linker, the branch does not need to be adjusted; it stays the same.

And now for something slightly different: branching backwards

  0x124:   add  $5  $10  $15
  0x128:   add  $6  $11  $16
  0x12C:   add  $7  $12  $17    <-- this is the branch target
  0x130:   add  $5  $10  $15
  0x134:   beq  $6  $11  0x12C  <-- HERE'S THE BRANCH
  0x138:   add  $7  $12  $17    <-- PC is here by the time the CPU is ready to execute the branch
  0x13C:   add  $5  $10  $15
  0x140:   add  $6  $11  $16
      

• the assembler uses the same equation: branch_offset = branch_target - PC
• branch_offset = 0x12C - 0x138 = -0xC = 1111-1111-1111-0100 in binary
• Or just count backwards: 1,2,3 times 4 is -12 = -0xC
• That looks like this: