flat assembler
Message board for the users of flat assembler.

flat assembler > Main > [fasmg] Optimal relocation

Author
Thread Post new topic Reply to topic
marste



Joined: 05 May 2015
Posts: 42
Here I’m again to see if fasmg can again exceed my expectations… Cool

In my little program I’ve some code that I can relocate. More: I need to relocate it in order to respect some constrain that I have (e.g. some label is within some address range), and depending on the parameters that I select for compilations this pieces should be relocated differently in order to respect the constraints.

I’ve seen examples in which fasmg resolve some second degree equation finding automatically values fitting a constraint, so I was thinking something as including the pieces (many little ones) of code in many places with a condition fitting just in one place, e.g.:

Code:
Relocatablecode.inc: if PIECE_1_LOC=THISLOC Relocatable code… end if mainfile.asm: …code… THISLOC=1 Include Relocatablecode.inc …more code… THISLOC=2 Include Relocatablecode.inc ..etc..


But not sure how to let fasmg calculate PIECE_1_LOC… And maybe there are different way also to have the same result!…

Additionally if possible (and I really this is difficult) there are other conditions (e.g. some label address mod 256 equal 0) that are not strictly required but if possible a nice to have (I can even add some “weights” to this conditions in order to have a value to minimize or maximize for example).

Hope I was clear enough but anyway available for any more clarification! Smile

Thank you!
Post 19 Sep 2017, 09:09
View user's profile Send private message Reply with quote
Tomasz Grysztar
Assembly Artist


Joined: 16 Jun 2003
Posts: 6876
Location: Kraków, Poland
If you use multiple conditions to place constraints on what can be assembled where, fasm[g] is going to look for a solution until it finds one. Unfortunately, even if a solution exists, there is no guarantee that fasm is going to find it (and the existence of a solution is one of the undecidable problems). You may get the "could not generate code within the allowed number of passes" error.

One of the possible obstacles is the "oscillator problem", please read about it.

What I would suggest is to write the IF blocks to place various constraints, and keep adding them until you get the "could not generate code" error. If that happens, we may look at the specific problem to see how we can guide fasmg to find the right solution with some additional flags and conditions (like in the case of the "oscillator problem").
Post 19 Sep 2017, 09:33
View user's profile Send private message Visit poster's website Reply with quote
marste



Joined: 05 May 2015
Posts: 42
Do you suggest to start with something like this?

Code:
Relocatablecode.inc: if PIECE_1_LOC = THISLOC Relocatable code… PIECE_1_LOC = THISLOC end if if PIECE_2_LOC = THISLOC Other relocatable code… PIECE_2_LOC = THISLOC end if mainfile.asm: …code… THISLOC = 1 Include Relocatablecode.inc …more code… THISLOC = 2 Include Relocatablecode.inc THISLOC = 3 Include Relocatablecode.inc …etc… assert PIECE_1_LOC assert PIECE_2_LOC …end
Post 19 Sep 2017, 13:45
View user's profile Send private message Reply with quote
Tomasz Grysztar
Assembly Artist


Joined: 16 Jun 2003
Posts: 6876
Location: Kraków, Poland
I have prepared a very simplified example that demonstrates some of the ideas. I have used numbered macros to define pieces of code that get moved around:
Code:
macro piece_1 first: db 'first',13,10 end macro macro piece_2 second: db 'second',13,10 end macro macro piece_3 third: db 'third',13,10 end macro macro piece_4 fourth: db 'fourth',13,10 end macro macro place_piece number repeat 1, n:number piece_#n macro piece_#n ; do not assemble same piece again end macro end repeat end macro repeat 4 ; if address is aligned, place piece that prefers alignment: if $ and 3 = 0 place_piece 2 end if if $ and 3 = 0 place_piece 4 end if ; otherwise keep placing pieces consecutively: place_piece % end repeat
Or:
Code:
NUMBER_OF_PIECES = 100 repeat NUMBER_OF_PIECES macro piece_#% p#%: db `%,13,10 end macro end repeat macro place_piece number repeat 1, n:number piece_#n macro piece_#n ; do not assemble same piece again end macro end repeat end macro repeat NUMBER_OF_PIECES ; if we are sufficiently near piece 30, place ones that need to be near it if p30 - 100 < $ & $ < p30 + 100 place_piece 14 end if if p30 - 100 < $ & $ < p30 + 100 place_piece 28 end if if p30 - 100 < $ & $ < p30 + 100 place_piece 49 end if if p30 - 100 < $ & $ < p30 + 100 place_piece 99 end if place_piece % end repeat ; we can use assertion to force assembly to fail when some end up too far from each other to be acceptable assert p14 - p30 < 100 | p30 - p14 < 100

The main problem here is that need to write rules that are easy to apply, like above. For any constraints that you have, you need to have an idea what kind of reordering may help. In the worst case you may actually need to test every possible order.
Post 19 Sep 2017, 15:40
View user's profile Send private message Visit poster's website Reply with quote
marste



Joined: 05 May 2015
Posts: 42
The proposed approach might be good if you have some condition that can determine “without search” the optimal solution.

I’ve a different scenario. To simplify, imagine that I should fit the more piece I can below a certain address. The if then can read something like “if $<limit then place piece”, but this is not guaranteeing an optimal solution.

As for example to simplify: imagine the address is 20 and the pieces are (in order) 8 7 6 6 long, with the proposed method 8 and 7 will fit while the 6s will not find anymore available space (5 is remaining); while an optimal solution should fit the 8 and the two 6 blocks (leaving just the 7 outside).
Post 20 Sep 2017, 08:37
View user's profile Send private message Reply with quote
Tomasz Grysztar
Assembly Artist


Joined: 16 Jun 2003
Posts: 6876
Location: Kraków, Poland
As I noted above, if you do not have at least a good heuristic to begin with, you are left with no other option than trying all permutations. This is viable when there are just few pieces, for larger numbers you would have to keep fingers crossed that it finds an acceptable solution within early tries (you could randomize generated permutations instead of using the lexicographical order).
Post 20 Sep 2017, 08:45
View user's profile Send private message Visit poster's website Reply with quote
Tomasz Grysztar
Assembly Artist


Joined: 16 Jun 2003
Posts: 6876
Location: Kraków, Poland
I have prepared an example that looks through all the permutations to find the solution in the simplified case you mentioned:
Code:
macro piece_1 db 8 dup '1' end macro macro piece_2 db 7 dup '2' end macro macro piece_3 db 6 dup '3' end macro macro piece_4 db 6 dup '4' end macro if PIECES_FITTING >= 3 ; if we found the solution, PERMUTATION = PERMUTATION ; keep the permutation else if ~ PERMUTATION PERMUTATION = 1234h ; this is the permutation we start with else ; the following code mutates the permutation to the next one lexicographically PERM = PERMUTATION BUFFER = 0 while PERM & PERM and 0Fh > BUFFER and 0Fh BUFFER = (BUFFER shl 4) or (PERM and 0Fh) PERM = PERM shr 4 end while INDEX = 0 while PERM and 0Fh < (BUFFER shr (INDEX+4)) and 0Fh INDEX = INDEX + 4 end while TMP = PERM and 0Fh PERM = (PERM and not 0Fh) or ((BUFFER shr INDEX) and 0Fh) BUFFER = (BUFFER and not (0Fh shl INDEX)) or (TMP shl INDEX) PERM = (PERM shl ((bsr BUFFER shr 2 + 1) shl 2)) or BUFFER PERMUTATION = PERM end if COUNT = 0 repeat 4 repeat 1, i:(PERMUTATION shr ((%%-%)*4)) and 0Fh ; extract digit from permutation piece_#i end repeat if $ <= 20 COUNT = COUNT + 1 ; count pieces that fit in the first 20 bytes end if end repeat PIECES_FITTING := COUNT
If the solution cannot be found, assembly is never going to finish and will abort upon reaching the limit of passes.

As I mentioned in the previous post, instead of looking through the permutations consecutively you could also try generating them in some pseudo-random order. When the space of acceptable solutions is a large set, such method could give results faster.
Post 20 Sep 2017, 09:50
View user's profile Send private message Visit poster's website Reply with quote
marste



Joined: 05 May 2015
Posts: 42
For me permutations will be good (I have a condition flexible enough), just that with 6 "mobile pieces" 720 will be the overall possiblities (I can anyway pilot more result and reduce search).

Anyway with condition that have to be explicit (and not something as max among possiblities) the solution cannot find optimal ones in general as e.g. in the given example having lists as: 8,7,6,8 (8+8 optimal) or 4,4,4,4,4,4 (4+4+4+4+4 optimal).

But I think we are already much much better than a "standard" assembler!!! Smile
Post 20 Sep 2017, 12:23
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 © 2004-2018, Tomasz Grysztar.

Powered by rwasa.