I am trying to write a simple multi-pass assembler.

Wikipedia states that:

Multi-pass assemblers create a table with all symbols and their values in the first passes, then use the table in later passes to generate code.


the assembler must be able to determine the size of each instruction on the initial passes in order to calculate the addresses of subsequent symbols

Now since the instruction size of the architecture I'm using is limited, it turns out that any instruction whose operand wouldn't fit in 2^12 bits require the use of a literal pool . The issue I have is that from what I understand, using a literal pool necessarily adds multiple instructions, for instance:

// pseudo assembly
load [$sp+200] $a  // Load the address stored in the pool at offset 200 from current instruction
jump $a // Jump to this address

Not only now requires two instructions instead of one, but also adds a new element to the pool at the end of the current section, so say some previous instruction used to jump to an address past the pool, say for instance address (2^12)-1 and now we add elements to the pool, not only will the address it used to jump to not be valid anymore, the new address will now be too big and require the use of the literal pool too, hence offsetting once again the position of some instructions and causing even more instructions to need to update their pointed addresses and so on.

It seems like something like this would also quickly have a pretty high algorithmic complexity as you need to run over your program once again each time you need to use the literal pool? What are the solutions for this?

I see Wikipedia also mentions that:

This means that if the size of an operation referring to an operand defined later depends on the type or distance of the operand, the assembler will make a pessimistic estimate when first encountering the operation, and if necessary, pad it with one or more "no-operation" instructions in a later pass or the errata. In an assembler with peephole optimization, addresses may be recalculated between passes to allow replacing pessimistic code with code tailored to the exact distance from the target.

So maybe that's an answer to my problem but I wonder if I'm missing something else? Should I for instance consider that all my instructions will need to use the literal pool and then remove all the instructions that don't actually need to in a later pass? Even in such a case it seems that I would still need to go over the assembly code multiple times, since removing instructions might make some addresses small enough that other instructions can now also stop using the literal pool, and so on (basically the same issue as what I mentioned above).

How should I handle this?

Thank you


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.