Message board for the users of flat assembler.
> Assembly > Types of multi-pass assembly
As any user of fasm probably knows, it is a multi-pass assembler and the basic function of the multiple passes is to optimize generated code so that uses short forms of the instructions whenever possible (fasm's multi-pass with its unrestricted forward-referencing can do much more, but that is a story for a different day).
What might be less commonly known is that there are actually different kinds of multi-pass assembly and the one that fasm is using is not the same as the one usually described when talking about this topic.
The initial pass of multi-pass assembly is done to get at least a rough idea of the sizes/positions of all instructions. When fasm does it, it uses the optimistic assumption that all instructions should have their shortest possible form. In the next pass, assembler already has a first draft of all the values that may affect sizes of generated instruction, and it may turn out that the optimistic assumption was too optimistic, and some parts of the code must be enlarged. This in turn changes some of the addresses and assembler needs another pass to find out if even more instructions have to be larger than initially assumed. It repeats this process until all the values are stable and only then generated code is valid. Because if during the last pass all the addresses stayed the same as they were in the pass before it, the instructions generated from the values from the previous pass turn out correct.
A more traditional approach was to use pessimistic assumptions instead of fasm's optimistic ones. That is, every instruction is at first generated large and is shrunk only if in the later pass it turns out that the range of addresses allows it to be shorter.
An advantage of pessimistic multi-pass is that it usually can be ended after any of the intermediate passes and all the instructions can be updated with the addresses collected during the last of these passes to create the correct code. The instructions were generated pessimistically, so every one of them should be large enough to hold the correct values.
The optimistic variant has the intermediate passes where some instructions are too small to hold the right values and this code cannot be fixed in such a simple way. The assembler has to continue with further passes until it reaches the solution.
Note that both the pessimistic and optimistic multi-pass may fail to find the solution in specific circumstances, like what I call the oscillator problem (a pessimistic assembler would usually fail in a different manner, by completely disallowing some types of use of forward-referenced values). But this does not happen when optimizing things like jumps in x86 architecture, where shrinking one instruction never forces any other instruction to be enlarged or vice versa.
An advantage of optimistic multi-pass is that is able to find solutions that are smaller. This can be demonstrated on a very simple example:
When a pessimistic assembler at first generates the larger form of jump, the distance to the "start" label becomes larger than 128 bytes and assembler no longer sees that this jump could be a short one. An optimistic assembler first tries the short jump and notices that it is enough.
start db 126 dup 90h jmp start
But we can do more, it is in fact possible to use fasm to test and compare both approaches to multi-pass assembly.
First, we need some code for testing. I'm going to generate an artificial one, consisting only of jump instructions, with help of fasmg. I put the following code into TEST.ASM:
and assemble it with fasmg to get TEST.INC that looks like this:
format binary as 'inc' xorshift = 11111111h struc rand32 . = xorshift shr 96 . = . xor . shl 11 xor . shr 8 xor xorshift xor xorshift shr 19 and 0FFFFFFFFh xorshift = . or xorshift shl 32 and 0FFFFFFFF_FFFFFFFF_FFFFFFFFh end struc struc rand limit while 1 . rand32 . = . and 1 shl bsr limit + 1 - 1 if . <= limit break end if end while end struc NUMBER_OF_JUMPS = 10000 repeat NUMBER_OF_JUMPS db 'position',`%,' ' R rand 100 repeat 1, target % + R mod NUMBER_OF_JUMPS + 1 db 'jmp position',`target,10 end repeat end repeat
The jumps are randomized, but mostly stay within a distance of 100 instructions, this should result in a mix of short and near jumps and a sufficient challenge for an assembler. I set the initial seed for the PRNG to a constant, so that the same test would be generated every time. It can be changed to some other value (even %t) to generate different tests.
position1 jmp position53 position2 jmp position20 position3 jmp position97 position4 jmp position56 position5 jmp position6 position6 jmp position83 position7 jmp position42 position8 jmp position60 ...
Now, to test optimistic multi-pass we could try just assembling it with fasm. But to get a better view of what is happening, we are going to implement the jump instruction as a macro. This is something that should work the same with fasm 1 and fasmg, only the basic macro syntax (braces for fasm 1, "end macro" for fasmg) needs to be changed accordingly. I'm going to use the fasm 1 syntax here:
macro jmp target if ~ defined target | target-