MIPS jump and branch instructions range

Question

I just started learning MIPS and I am having troubles understanding the ranges of jump and branch instructions. I know that there are limits on how "far" PC can jump and branch, but I don't get the reason why.

And 2 specific questions, if current value of the PC is 0x00000000, is it possible to do 1 JUMP to a random address? if current value of the PC is 0x00000600, is it possible to do 1 BRANCH to a random address?

Windbroken

Related: How to Calculate Jump Target Address and Branch Target Address? shows the jump / branch encodings and their ranges. – Thompkins

Answer 1

MIPS processors uses fixed-sized size instructions, where each instruction word is, well, a word (i.e. 4 bytes == 32 bits). So there's only so much information that can be crammed into those 4 bytes.

The J and JAL instructions use 6 of the 32 bits to specify the opcode. This leaves 26 bits to specify the target address. The target address isn't specified directly in the instruction though (there aren't enough bits for that) - instead, what happens is this:

• The low 28 bits of the target address are shifted right 2 bits, and then the 26 least significant bits are stored in the instruction word. Since all instructions must be word-aligned the two bits that we shifted out will always be zeroes, so we don't lose any information that we can't recreate.
• When the jump occurs, those 26 bits are shifted left 2 bits to get the original 28 bits, and then they are combined with the 4 most significant bits of the address of the instruction following the J/JAL to form a 32-bit address.

This makes it possible to jump to any instruction in the same 256MB-range (2^28) that the jump instruction is located in (or if delayed branching is enabled; to any instruction in the same 256MB-range as the instruction in the delay slot).

---

For the branch instructions there are 16 bits available to specify the target address. These are stored as signed offsets relative to the instruction following the branch instruction (again with two bits of shifting applied, because it's unnecessary to store something that we know will always be 0). So the actual offset after restoring the 2 least significant bits is 18 bits, which then is sign-extended to 32 bits and added to the address of the instruction following the branch instruction. This makes is possible to branch to +/-128kB within the branch instruction.

---

Consider the following code loaded at address 0x00400024:

main:
j foo
nop
foo:
b main
nop

The j foo instruction is encoded as 0x0810000b. The 26 least significant bits have the value 0x10000b, which after shifting 2 bits to the left become 0x40002c. The 4 most significant bits of the address of the instruction following j are zero, so the target address becomes (0 << 28) | 0x40002c, which equals 0x40002c, which happens to be the address of foo.

The b main instruction is encoded as 0x0401fffd. The 16 least significant bits have the value 0xfffd, which after shifting 2 bits to the left becomes 0x3fff4. Sign-extending that to 32 bits gives us 0xfffffff4. And when adding that to the address of the instruction following the b we get 0x400030 + 0xfffffff4, which (when truncated to 32 bits) equals 0x400024, which happens to be the address of main.

---

If you want to jump to some arbitrary address, load the address into a register and use the jr or jalr instruction to jump.

Heptastich

Why do we add 4 most significant bits of the address of the instruction i.e. PC to the jump address of (26 bits). Like what do these 4 sig bits signify? And why only first 4 bits. – Marienbad

@hsnsd: See my answer: "When the jump occurs, those 26 bits are shifted left 2 bits to get the original 28 bits, and then they are combined with the 4 most significant bits of the address of the instruction following the J/JAL to form a 32-bit address". That's just how the instruction works. – Heptastich

question on your last sentence about jr. would that mean that the highest memory address expressed in hex that JR can jump to be 7FFFFFFF16 since we could in theory just jump to anything that is in the register specified by the instruction? – Sop

@curiousX: The highest address you can jump to with jr/jalr is the highest value that can be stored in a register, which on MIPS32 is 0xFFFFFFFF. There's no shifting taking place with jr; the value is used as-is. Of course, the address must still be word-aligned (unless you have a CPU that supports MIPS16 and you're switching to MIPS16 code), so it's up to the programmer/compiler to make sure that only properly aligned addresses are used. – Heptastich