flat assembler
Message board for the users of flat assembler.
![]() |
Author |
|
revolution
See here also: http://board.flatassembler.net/topic.php?t=5313
|
|||
![]() |
|
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.
|
|||
![]() |
|
tthsqe
Or is the situation even worse - is the exitstence a minimal solution (using repeat, if, else ... constructions) not decidable?
|
|||
![]() |
|
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. |
|||
![]() |
|
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.
|
|||
![]() |
|
revolution
Unsolvable:
Code: org 0 if x = 0 nop end if x: |
|||
![]() |
|
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. |
|||
![]() |
|
< Last Thread | Next Thread > |
Forum Rules:
|
Copyright © 1999-2020, Tomasz Grysztar. Also on GitHub, YouTube, Twitter.
Website powered by rwasa.