How is it possible for a program to exceed 2^16 bytes?

Question

In Assembly (MIPS), the immediate instructions have the following format:

+----------+------+------+-------+
|  opcode  |  rs  |  rt  |  IMM  |
+----------+------+------+-------+

Where,

Opcode = 6 bits
Source register (rs) = 5 bits
Destination register (rt) = 5 bits
Immediate value (IMM) = 16 bits

That said, you just can jump to another instruction 2^16 bytes = 64 kb of code far from the current instruction (branch instructions). How is it possible for a program (in C, Java, etc) to exceed 2^16 bytes of code?

Edit:

As @trashgod pointed out, the compilers can use J instructions instead. But it is still limited to 26 bits of address, which means that program cannot straddle a 256MB. So, how is it possible?

Answer 1

I am not a MIPS expert, but the maximal offset of the relative jumps has nothing to do with the size of the program itself.

The jumps can be serialized by the compiler or manually in the assembly code. This way, one can jump on any distance up or down without problems.

;it is pseudo code, not mips
start:
        jmp  to_the_limit
        .....
        .... 256MB bloated code
        ....
to_the_limit:
        jmp  even_further
        ....
        .... another 256MB of even more bloated code.
        ....
even_further:
        jmp  this_code

Answer 2

As noted in MIPS Assembly/MIPS Details, "There are 3 different types of instructions: R Instructions, I Instructions, and J Instructions." The last, Jump instructions, allow a 26 bit destination address. See J Instructions on how a full 32-bit address can be inferred.

Addedum: Regarding an effective 32-bit address, the lowest two bits are always zero, and the other four are "borrowed from the address of the current instruction, so we cannot let a program straddle a 256MB boundary."

Answer 3

I don't work with mips but just wondering can gcc relax the I jump for MIPS? PowerPC can jump to 26bit offset so if the .text size exceeds that limitation, i need gcc --relax option to add one more redirection...

Answer 4

Load the destination address into a 32-bit register and use the JR command.