How to Calculate Jump Target Address and Branch Target Address?

Question

I am new to Assembly language. I was reading about MIPS architecture and I am stuck with Jump Target Address and Branch Target Address and how to calculate each of them.

Answer 1

(In the diagrams and text below, PC is the address of the branch instruction itself. PC+4 is the end of the branch instruction itself, and the start of the branch delay slot. Except in the absolute jump diagram.)

1. Branch Address Calculation

In MIPS branch instruction has only 16 bits offset to determine next instruction. We need a register added to this 16 bit value to determine next instruction and this register is actually implied by architecture. It is PC register since PC gets updated (PC+4) during the fetch cycle so that it holds the address of the next instruction.

We also limit the branch distance to -2^15 to +2^15 - 1 instruction from the (instruction after the) branch instruction. However, this is not real issue since most branches are local anyway.

So step by step :

• Sign extend the 16 bit offset value to preserve its value.
• Multiply resulting value with 4. The reason behind this is that If we are going to branch some address, and PC is already word aligned, then the immediate value has to be word-aligned as well. However, it makes no sense to make the immediate word-aligned because we would be wasting low two bits by forcing them to be 00.
• Now we have a 32 bit relative offset. Add this value to PC + 4 and that is your branch address.

---

2. Jump Address Calculation

For Jump instruction MIPS has only 26 bits to determine Jump location. Jumps are relative to PC in MIPS. Like branch, immediate jump value needs to be word-aligned; therefore, we need to multiply 26 bit address with four.

Again step by step:

• Multiply 26 bit value with 4.
• Since we are jumping relative to PC+4 value, concatenate first four bits of PC+4 value to left of our jump address.
• Resulting address is the jump value.

In other words, replace the lower 28 bits of the PC + 4 with the lower 26 bits of the fetched instruction shifted left by 2 bits.

Jumps are region-relative to the branch-delay slot, not necessarily the branch itself. In the diagram above, PC has already advanced to the branch delay slot before the jump calculation. (In a classic-RISC 5 stage pipeline, the BD was fetched in the same cycle the jump is decoded, so that PC+4 next instruction address is already available for jumps as well as branches, and calculating relative to the jump's own address would have required extra work to save that address.)

Source: Bilkent University CS 224 Course Slides

Answer 2

Usually you don't have to worry about calculating them as your assembler (or linker) will take of getting the calculations right. Let's say you have a small function:

func:
  slti $t0, $a0, 2
  beq $t0, $zero, cont
  ori $v0, $zero, 1
  jr $ra
cont:
  ...
  jal func
  ... 

When translating the above code into a binary stream of instructions the assembler (or linker if you first assembled into an object file) it will be determined where in memory the function will reside (let's ignore position independent code for now). Where in memory it will reside is usually specified in the ABI or given to you if you're using a simulator (like SPIM which loads the code at 0x400000 - note the link also contains a good explanation of the process).

Assuming we're talking about the SPIM case and our function is first in memory, the slti instruction will reside at 0x400000, the beq at 0x400004 and so on. Now we're almost there! For the beq instruction the branch target address is that of cont (0x400010) looking at a MIPS instruction reference we see that it is encoded as a 16-bit signed immediate relative to the next instruction (divided by 4 as all instructions must reside on a 4-byte aligned address anyway).

That is:

Current address of instruction + 4 = 0x400004 + 4 = 0x400008
Branch target = 0x400010
Difference = 0x400010 - 0x400008 = 0x8
To encode = Difference / 4 = 0x8 / 4 = 0x2 = 0b10

Encoding of beq $t0, $zero, cont

0001 00ss ssst tttt iiii iiii iiii iiii
---------------------------------------
0001 0001 0000 0000 0000 0000 0000 0010

As you can see you can branch to within -0x1fffc .. 0x20000 bytes. If for some reason, you need to jump further you can use a trampoline (an unconditional jump to the real target placed placed within the given limit).

Jump target addresses are, unlike branch target addresses, encoded using the absolute address (again divided by 4). Since the instruction encoding uses 6 bits for the opcode, this only leaves 26 bits for the address (effectively 28 given that the 2 last bits will be 0) therefore the 4 bits most significant bits of the PC register are used when forming the address (won't matter unless you intend to jump across 256 MB boundaries).

Returning to the above example the encoding for jal func is:

Destination address = absolute address of func = 0x400000
Divided by 4 = 0x400000 / 4 = 0x100000
Lower 26 bits = 0x100000 & 0x03ffffff = 0x100000 = 0b100000000000000000000

0000 11ii iiii iiii iiii iiii iiii iiii
---------------------------------------
0000 1100 0001 0000 0000 0000 0000 0000

You can quickly verify this, and play around with different instructions, using this online MIPS assembler i ran across (note it doesn't support all opcodes, for example slti, so I just changed that to slt here):

00400000: <func>    ; <input:0> func:
00400000: 0000002a  ; <input:1> slt $t0, $a0, 2
00400004: 11000002  ; <input:2> beq $t0, $zero, cont
00400008: 34020001  ; <input:3> ori $v0, $zero, 1
0040000c: 03e00008  ; <input:4> jr $ra
00400010: <cont>    ; <input:5> cont:
00400010: 0c100000  ; <input:7> jal func

Answer 3

For small functions like this you could just count by hand how many hops it is to the target, from the instruction under the branch instruction. If it branches backwards make that hop number negative. if that number doesn't require all 16 bits, then for every number to the left of the most significant of your hop number, make them 1's, if the hop number is positive make them all 0's Since most branches are close to they're targets, this saves you a lot of extra arithmetic for most cases.

• chris

Answer 4

I think it would be quite hard to calculate those because the branch target address is determined at run time and that prediction is done in hardware. If you explained the problem a bit more in depth and described what you are trying to do it would be a little easier to help. (: