How do two-pass assemblers deal with instructions that are expanded by the assembler?

Question

Consider the following MIPS assembly (I'm using MIPS because that is what my Computer Organization and Design book uses):

beq   $s0, $s1, L1
add   $t0, $t1, $t2
...
L1: ...

Because MIPS only uses 16 bits for the PC-relative address in the beq instruction, if L1 is sufficiently far away from the beq, the assembler must replace it with two instructions (a jump has 26 bits for the address) and a new label:

bne   $s0, $s1, L2
j     L1
L2:   add $t0, $t1, $t2
...
L1: ...

If even this isn't enough, it may need multiple jumps.

The assembler doesn't know whether it needs to make this replacement until it knows the location of L1. Since it doesn't initially know the size of the beq (1 instruction or 2), how can it keep the location counter up-to-date during the first pass?

Answer 1

There are multiple approaches:

• Reserve space only for one instruction and if it's found not enough, expand it.
• Reserve enough space for the two instructions and then either fill the unused space with nop(s) or compact the code.

In either case you don't have to generate (semi-)final machine code immediately, nor do you need to rescan the source code and reassemble it, though it's possible. You can generate "intermediate" code or its representation at first and then fix it up, pretty much what the linker does.

Speaking of which [the linker], there's also another option:

• Leave this piece for the linker to handle. It's not very hard. Nowadays compilers (e.g. Microsoft Visual C++) can do link-time code optimization.