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

1
votes

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?

1
assemblymipsrelative-addressing
the assembler doesnt have to compute the offset on the first pass. It can parse the code, keep internal tables, and go through those tables many times trying to optimize for shorter instructions. if global then it will likely place a dataword near by and the linker will later fill that with the destination. – old_timer
If you dont have the resources and have to generate the instructions on the fly then you have to go for the longer reach solution by default, then patch with nop if you didnt really need to reach that far. – old_timer
This isn't MIPS-specific, btw. – Alexey Frunze

1 Answers

1
votes

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.