flat assembler
Message board for the users of flat assembler.

Index > Compiler Internals > [minor bug]Code resolving not minimal

Goto page 1, 2  Next
Author
Thread Post new topic Reply to topic
revolution
When all else fails, read the source


Joined: 24 Aug 2004
Posts: 17248
Location: In your JS exploiting you and your system
revolution
I noticed the following behaviour:

Consider the following code:
Code:
use32
a: mov eax,[edx+c-a-5] ;8B 42 01
   mov esi,[edx+c-a-7] ;8B 72 FF
c:
    

In the above, the first instruction has an offset of +1 on the coding.


But it is possible to code this smaller:
Code:
use32
a: mov eax,[edx+c-a-5] ;8B 02
   mov esi,[edx+c-a-7] ;8B 72 FE
c:
    



Below is what happens when we change only the second instruction:
Code:
use32
a: mov eax,[edx+c-a-5] ;8B 02
   mov esi,[edx+c-a-6] ;8B 72 FF
c:
    

Now FASM can generate minimal code.

Note: I'm using v1.66 dated 19-May-2006

PS: I think for ease of identification the versions with even numbers should also have a third number to show sub-versions. Much less confusing. v1.66.01 would be more easily noticed than a date change on the download page.

PPS: Hehe, I think I give the author too many headaches by finding bugs Smile
Post 24 May 2006, 14:36
View user's profile Send private message Visit poster's website Reply with quote
revolution
When all else fails, read the source


Joined: 24 Aug 2004
Posts: 17248
Location: In your JS exploiting you and your system
revolution
One more thing that may help is this:

Code:
use32
a: mov eax,[edx+c-a-5]
   mov esi,[edx+c-a-5]
c:
    

Gives an error that code cannot be generated, but it can be resolved like this:
Code:
use32
a: mov eax,[edx+c-a-5] ;8B 42 01
   mov esi,[edx+c-a-5] ;8B 72 01
c:
    
Post 24 May 2006, 14:47
View user's profile Send private message Visit poster's website Reply with quote
LocoDelAssembly
Your code has a bug


Joined: 06 May 2005
Posts: 4633
Location: Argentina
LocoDelAssembly
The last one works for me. I'm using 1.66 which I downloaded before your previous bug was fixed, I forgot to download the fixed version Razz
Post 24 May 2006, 17:07
View user's profile Send private message Reply with quote
Tomasz Grysztar
Assembly Artist


Joined: 16 Jun 2003
Posts: 7712
Location: Kraków, Poland
Tomasz Grysztar
As you can conclude from the "Code Resolving" section of Understanding fasm article, the only thing that you can be sure with it (unless there are some bugs, of course Wink) is the correctness of generated code if assembler succeeds to find such solution. Neither the minimal size nor the ability to find the solution can be guaranteed in general case.
Post 24 May 2006, 18:04
View user's profile Send private message Visit poster's website Reply with quote
LocoDelAssembly
Your code has a bug


Joined: 06 May 2005
Posts: 4633
Location: Argentina
LocoDelAssembly
revolution, now I also tested your last code with the 19-May-2006 version and works fine too :S
Post 24 May 2006, 18:25
View user's profile Send private message Reply with quote
vid
Verbosity in development


Joined: 05 Sep 2003
Posts: 7105
Location: Slovakia
vid
anyway, revolution, thanks for idea. I am sure Tomasz spent more time over this than he revelealed Wink
Post 24 May 2006, 21:10
View user's profile Send private message Visit poster's website AIM Address MSN Messenger ICQ Number Reply with quote
Tomasz Grysztar
Assembly Artist


Joined: 16 Jun 2003
Posts: 7712
Location: Kraków, Poland
Tomasz Grysztar
Not really - at least yet - as I had no time for this.
However my answer above I could base even solely on the title of this topic. Wink

PS. However I forgot to mention the section 2.2.6 of manual, which is also important here (perhaps even more than the link in my above post).
Post 24 May 2006, 21:47
View user's profile Send private message Visit poster's website Reply with quote
revolution
When all else fails, read the source


Joined: 24 Aug 2004
Posts: 17248
Location: In your JS exploiting you and your system
revolution
Quote:
The last one works for me

Hmm, you are right. I actually had this below but edited out the unused label b, I thought it would make no difference.
Code:
use32
a: mov     eax,[edx+c-a-5]
b: mov     esi,[edx+c-a-5]
c:    
So there is an interesting side effect. By placing the unused label b now the code cannot be generated. By removing the label b the code can be generated. Weird eh.
Quote:
Neither the minimal size nor the ability to find the solution can be guaranteed in general case.
I was aware of this but thought that with an example of such a thing happening that it may help you if you wanted to update the resolving algorithm. Like I mentioned in the title, it is a minor bug, so it is a low priority. For the real code I have that failed to generate I simply got around the bug by inserting a nop to force the extra byte and thus get code to resolve. That is when I noticed the non-minimal offset of +1. It didn't bother me at all because I knew it would still work, but it did make me curious to learn what exactly was causing it.
Post 25 May 2006, 01:49
View user's profile Send private message Visit poster's website Reply with quote
Tomasz Grysztar
Assembly Artist


Joined: 16 Jun 2003
Posts: 7712
Location: Kraków, Poland
Tomasz Grysztar
Any update of resolving algorithm would have to be extremely careful, since it's very easy to make some new code to resolve nice for a price of loosing already-existing good resolving of some other code.
I'll see however, if I can do anything about it without breaking what's already achieved.
Post 25 May 2006, 09:38
View user's profile Send private message Visit poster's website Reply with quote
Tomasz Grysztar
Assembly Artist


Joined: 16 Jun 2003
Posts: 7712
Location: Kraków, Poland
Tomasz Grysztar
I forgot about this thread, but perhaps I should add at least some more detailed explanation.

When assembler encounters in a numerical expression a symbol, whose value it haven't yet seen at all (this occurs only in the very first pass for the forward-referenced symbols; in later passes the value from previous pass is used for predictions), the whole expression is predicted to have zero value (this helps to pre-generate the shortest possible opcodes). So, in case of this code sample, both instructions are in first pass generated as short ones (with displacement 0). This causes "c-a" to have value 4 predicted in the next pass and therefore both instruction are now generated as longer. Therefore fasm can never hit the "right" 5 bytes solution.

Anyway, you can use some ugly trick to help fasm with this puzzle:
Code:
use32
L = c-a-5
a: mov eax,[edx+L]
   mov esi,[edx+L-2]
c:    

Now in first pass L gets value of 0 (because it contains unknown value c), so the first instruction is generated as short, but the second one as long. So in the next pass "c-a" is predicted to be 5, and thus L again gets predicted value of 0, everything fits and assembler happily finishes with this solution.
Post 30 Mar 2009, 07:26
View user's profile Send private message Visit poster's website Reply with quote
Tomasz Grysztar
Assembly Artist


Joined: 16 Jun 2003
Posts: 7712
Location: Kraków, Poland
Tomasz Grysztar
As for the second, it is caused by the "optimization adjustments" mechanism (defining additional label inbetween causes the adjustments to be updated, in this case with a poor consequences for the assembly process). I may forge some detailed explanation later.

As I explained above, I don't consider these a bugs, really - it is not possible to make an algorithm that would work for all cases, so such things must happen with some pieces of code. If we call them bugs, then fasm is going to be inevitabily bugged with no possible fix in any future.


Last edited by Tomasz Grysztar on 30 Mar 2009, 07:38; edited 1 time in total
Post 30 Mar 2009, 07:37
View user's profile Send private message Visit poster's website Reply with quote
revolution
When all else fails, read the source


Joined: 24 Aug 2004
Posts: 17248
Location: In your JS exploiting you and your system
revolution
Your trick if fine IF we know the values at the time of writing. But often these values are symbolic constants or generated by expressions further down the code (and many other ways of obscuring the values from the programmer). But it does serve a nice little example of how to help fasm with some aspects of code generation.
Post 30 Mar 2009, 07:38
View user's profile Send private message Visit poster's website Reply with quote
Tomasz Grysztar
Assembly Artist


Joined: 16 Jun 2003
Posts: 7712
Location: Kraków, Poland
Tomasz Grysztar
You may land at the trick with the experimenting - when with large code you get "cannot be generated" and don't know what's going on inside, you may as well play with some constants and get the right solution, without even knowing what is going on inside there. The only thing fasm guarantees to you is that when it says the code has been generated, it is going to be the correct solution.

As I said - I could perhaps modify the optimization algorithms to deal correctly with the above samples, however this way I would break them for the cases of more usual code, for which they were designed. That's not the way to go.
Post 30 Mar 2009, 07:42
View user's profile Send private message Visit poster's website Reply with quote
revolution
When all else fails, read the source


Joined: 24 Aug 2004
Posts: 17248
Location: In your JS exploiting you and your system
revolution
Tomasz Grysztar wrote:
As I said - I could perhaps modify the optimization algorithms to deal correctly with the above samples, however this way I would break them for the cases of more usual code, for which they were designed. That's not the way to go.
Agree, not the way to go. I think we are moving into NP type areas of solution finding here. If you can solve the optimisation issue perfectly without huge execution overhead then I think you will have also found a way show that P=NP Wink
Post 30 Mar 2009, 07:46
View user's profile Send private message Visit poster's website Reply with quote
Madis731



Joined: 25 Sep 2003
Posts: 2141
Location: Estonia
Madis731
@revolution: Smile
Post 30 Mar 2009, 12:44
View user's profile Send private message Visit poster's website Yahoo Messenger MSN Messenger Reply with quote
Luc Van de Velde



Joined: 28 Mar 2009
Posts: 8
Luc Van de Velde
sorry to disappoint u revolution... but rasm uses the same basic optimizing principles as fasm (which are perfect and cannot be improved)
its true that u can design code samples that are not optimized perfectly
i am not bothered with this, coz as thomas said 'it works in normal cases'
thomas would be right not to bother trying to improve fasm in this regard
a solution would require too much math... and thats not good for assembly speed... u should try to introduce more usfull functionallity
Post 30 Mar 2009, 17:36
View user's profile Send private message Send e-mail Reply with quote
revolution
When all else fails, read the source


Joined: 24 Aug 2004
Posts: 17248
Location: In your JS exploiting you and your system
revolution
Luc Van de Velde wrote:
sorry to disappoint u revolution... but rasm uses the same basic optimizing principles as fasm (which are perfect and cannot be improved)
its true that u can design code samples that are not optimized perfectly
i am not bothered with this, coz as thomas said 'it works in normal cases'
thomas would be right not to bother trying to improve fasm in this regard
a solution would require too much math... and thats not good for assembly speed... u should try to introduce more usfull functionallity
Hehe, hardly perfect if there is a flaw, but regardless, if Tomasz does decide to solve it (like I know he is capable of, if he gets time) then the proving of P=NP would be of great importance outside of the fasm project.Razz
Post 30 Mar 2009, 17:40
View user's profile Send private message Visit poster's website Reply with quote
Tomasz Grysztar
Assembly Artist


Joined: 16 Jun 2003
Posts: 7712
Location: Kraków, Poland
Tomasz Grysztar
Luc Van de Velde wrote:
(...) the same basic optimizing principles as fasm (which are perfect and cannot be improved)

I think that's a little exagerration. Wink
Post 30 Mar 2009, 17:42
View user's profile Send private message Visit poster's website Reply with quote
Madis731



Joined: 25 Sep 2003
Posts: 2141
Location: Estonia
Madis731
Tomasz Grysztar wrote:
Luc Van de Velde wrote:
(...) the same basic optimizing principles as fasm (which are perfect and cannot be improved)

I think that's a little exagerration. Wink

...but still a nice pat on the shoulder Very Happy

PS. Actually I do believe P=NP (I've been dreaming about TSP-problem) and I will tell you if I find a proof Wink

_________________
My updated idol Very Happy http://www.agner.org/optimize/
Post 31 Mar 2009, 09:34
View user's profile Send private message Visit poster's website Yahoo Messenger MSN Messenger Reply with quote
Luc Van de Velde



Joined: 28 Mar 2009
Posts: 8
Luc Van de Velde
what u mean by quote 'outside of the fasm project' are there more important things in computer sceince than developing a good computer language (assembler based offcourse) and teaching others how to solve often very complex problems with it?
an assembler is not an equation solver... if thats what u are after revolution... mathlab can do that just fine... i wonder if an assembler should have an equation solver... what do u think about this tomasz?
personaly... i dont deal with that kinda complex equations (yet)
I use rasm to develop circuits for my own x86-compatible cpu... i really need that
Post 01 Apr 2009, 19:33
View user's profile Send private message Send e-mail Reply with quote
Display posts from previous:
Post new topic Reply to topic

Jump to:  
Goto page 1, 2  Next

< 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.

Powered by rwasa.