What does fasm do when it encounters forward referenced labels?

ex: mov [rax+L2-L1],L3 ; where L1,L2,L3 are all labels appearing after this instruction

ICC, the shortest encoding of this instruction depends on whether L2-L1 is zero, a byte, or a dword and on whether L3 is a dword or qword. But the values of L1,L2,L3 all depend on how this instruction is encoded. Things look grim...

I looked at the source a bit, and it looks like fasm makes a guess - first alotting the smallest possible space to the instruction, and backtracking when something goes wrong.

But then, how does is compile somethings in so few passes?

ex:


If it uses this guessing/backtrack scheme, wouldn't need as many passes as there are mov instructions?

See here also: http://board.flatassembler.net/topic.php?t=5313

Thanks revolution! I was beginning to think that fasm was guaranteed to generate optimal code. But it looks like this is a hard problem in general (maybe NP complete?) and would lead to astronomical assembly times.

Or is the situation even worse - is the exitstence a minimal solution (using repeat, if, else ... constructions) not decidable?

It is decidable.

Consider the situation where every instruction has two possible encodings, encoding A or encoding B. All we have to do is try every possible set of A|B for the code and the smallest one wins. Obviously the run time is 2^n for n instructions. This can be generalised for more than 2 encodings.

I_1 * I_2 * ... * I_n, where 'I_x' is the number of possible encodings for the instruction x.

that is why I said "using repeat, if, else ... constructions" as these add more complications to the matter. I was wondering about this because Thomaz kept saying something to the effect that code resolution is not solvable in general. But this is clearly not the case if we stick to cpu instructions, lables and align directives.

Unsolvable: But this is not because of an instruction size difference.

Ok, the question is not whether there is unresolvable code, but rather:
Is there an algorithm that when feed an asm source, will determine if it has a resolution or not.
It is tempting to equate this to the Halting problem, but I'm not sure that code resolution is as complex as turing machines.