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

User · Answer

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

User · Answer

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  amp  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   lt func gt        lt input 0 gt  func  00400000  0000002a     lt input 1 gt  slt  t0   a0  2 00400004  11000002     lt input 2 gt  beq  t0   zero  cont 00400008  34020001     lt input 3 gt  ori  v0   zero  1 0040000c  03e00008     lt input 4 gt  jr  ra 00400010   lt cont gt        lt input 5 gt  cont  00400010  0c100000     lt input 7 gt  jal func

User · Answer

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

User · Answer

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

[assembly] How to Calculate Jump Target Address and Branch Target Address?

Examples related to assembly

Examples related to mips

Examples related to machine-code