flat assembler
Message board for the users of flat assembler.

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

Author
Thread Post new topic Reply to topic
tthsqe



Joined: 20 May 2009
Posts: 730
tthsqe
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?
Post 31 Dec 2009, 03:03
View user's profile Send private message Reply with quote
revolution
When all else fails, read the source


Joined: 24 Aug 2004
Posts: 17716
Location: In your JS exploiting you and your system
revolution
Post 31 Dec 2009, 03:59
View user's profile Send private message Visit poster's website Reply with quote
tthsqe



Joined: 20 May 2009
Posts: 730
tthsqe
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.
Post 31 Dec 2009, 04:14
View user's profile Send private message Reply with quote
tthsqe



Joined: 20 May 2009
Posts: 730
tthsqe
Or is the situation even worse - is the exitstence a minimal solution (using repeat, if, else ... constructions) not decidable?
Post 31 Dec 2009, 04:32
View user's profile Send private message Reply with quote
revolution
When all else fails, read the source


Joined: 24 Aug 2004
Posts: 17716
Location: In your JS exploiting you and your system
revolution
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.
Post 31 Dec 2009, 04:40
View user's profile Send private message Visit poster's website Reply with quote
tthsqe



Joined: 20 May 2009
Posts: 730
tthsqe
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.
Post 31 Dec 2009, 05:21
View user's profile Send private message Reply with quote
revolution
When all else fails, read the source


Joined: 24 Aug 2004
Posts: 17716
Location: In your JS exploiting you and your system
revolution
Unsolvable:
Code:
org 0
if x = 0
   nop
end if
x:    
But this is not because of an instruction size difference.
Post 31 Dec 2009, 05:34
View user's profile Send private message Visit poster's website Reply with quote
tthsqe



Joined: 20 May 2009
Posts: 730
tthsqe
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.
Post 31 Dec 2009, 05:52
View user's profile Send private message Reply with quote
Display posts from previous:
Post new topic Reply to topic

Jump to:  


< 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


Copyright © 1999-2020, Tomasz Grysztar. Also on GitHub, YouTube, Twitter.

Website powered by rwasa.