fasm's handling of forward references

Index > Compiler Internals > fasm's handling of forward references

Author

Thread

tthsqe

Joined: 20 May 2009
Posts: 767

tthsqe 31 Dec 2009, 03:03

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:

Code:

rept 200 { mov [rax+L1],rbx }
L1: nop

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

31 Dec 2009, 03:03

revolution
When all else fails, read the source

Joined: 24 Aug 2004
Posts: 20304
Location: In your JS exploiting you and your system

revolution 31 Dec 2009, 03:59

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

31 Dec 2009, 03:59

tthsqe

Joined: 20 May 2009
Posts: 767

tthsqe 31 Dec 2009, 04:14

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.

31 Dec 2009, 04:14

tthsqe

Joined: 20 May 2009
Posts: 767

tthsqe 31 Dec 2009, 04:32

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

31 Dec 2009, 04:32

revolution
When all else fails, read the source

Joined: 24 Aug 2004
Posts: 20304
Location: In your JS exploiting you and your system

revolution 31 Dec 2009, 04:40

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.

31 Dec 2009, 04:40

tthsqe

Joined: 20 May 2009
Posts: 767

tthsqe 31 Dec 2009, 05:21

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.

31 Dec 2009, 05:21

revolution
When all else fails, read the source

Joined: 24 Aug 2004
Posts: 20304
Location: In your JS exploiting you and your system

revolution 31 Dec 2009, 05:34

Unsolvable:

Code:

org 0
if x = 0
   nop
end if
x:

But this is not because of an instruction size difference.

31 Dec 2009, 05:34

tthsqe

Joined: 20 May 2009
Posts: 767

tthsqe 31 Dec 2009, 05:52

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.

31 Dec 2009, 05:52

< Last Thread | Next Thread >

Forum Rules:

You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum
You cannot attach files in this forum
You can download files in this forum