Array in Assembler umsetzen

04/07/2010 - 08:55 von Jens Kallup | Report spam
Hallo,

in meinen kleinen Compilerprojekt will ich Array-Support
einbauen, weiss aber nicht wie man das Assemblertechnisch
lösen könnte.

folgendes Konstrukt ist möglich:

ident = NEW ARRAY(dim1 <,dim2>...)

Für snippets und Anregungen bin ich Euch sehr dankbar
Gruß
Jens
 

Lesen sie die antworten

#1 Jan Seiffert
04/07/2010 - 16:06 | Warnen spam
Jens Kallup schrieb:
Hallo,

in meinen kleinen Compilerprojekt will ich Array-Support
einbauen, weiss aber nicht wie man das Assemblertechnisch
lösen könnte.

folgendes Konstrukt ist möglich:

ident = NEW ARRAY(dim1 <,dim2>...)

Für snippets und Anregungen bin ich Euch sehr dankbar



Hmmmmm.

Einerseits ist das einfach, andererseits schwer...

Aus Assembler sicht gibt es keine Arrays (und auch keine Strukturen, etc.). Da
sind alles ausser Registern eben Speicher (Adressen). Auf der anderen Seite hast
du deine Sprache, die vieleicht etwas "angenehmer" sein soll. Der Compiler muss
das passend runterbrechen, zusammenrechnen und entsprechende Befehle ausspucken.

Das einfachste Beispiel ist das eindimensionale Array.
Bislang benutzt du ja fuer einfache Variablen sowas:

eine_var:
dd 0

Damit hat der Platz erstellt mit dd das Symbol "eine_var". Wirklich ein
Symbol, das ist ja mehr als ein Makro mit EQU oder sowas.
Ein Array ist jetzt einfach:

eine_array_var:
times (16) dd 0

Jetzt hast du quasi 16 dd hintereinader, die alle hinter dem symbol
"eine_array_var" kommen.
Dein Compiler muss jetzt indexierung in das Array "aufloesen", aus (ich gehe
davon aus das ab 0 gezaehlt wird):
x = eine_array_var[6]
wird
mov eax, [eine_array_var + 6 * sizeof(dd)]
oder
mov ebx, eine_array_var ; array base adresse laden
shl edx, 2 ; index * 4
add ebx, edx ; index zu base adresse addieren
mov eax, [ebx]
letzteres kann man auch mit lea machen, oder direkt mit indexed load.
mov eax, [ebx + edx * 4]
(wenn ich jetzt die sch... syntax zusammen bekommen habe)

Das ist quasi klassisch, das ist erprobt, das "geht" (dafuer ist die ganze
unterstuezung mit indexed loads usw.), das kann die CPU, aber auch nicht anders.

Dynamische arrays fallen dann eben aus einem Allokator (malloc, new, getPages,
GC_gimme_mem), du hast dann nur noch den Pointer auf den start, denoch musst du
die Arithmetik selber machen.
Also:

eine_dyn_array_var:
dd 0
(davon ausgehend das dein pointer in dd passt)

dann:
push 16*sizeof(dd) ; das array soll 16 Elemente gross werden
call malloc
add esp, 4
test eax, eax
jz abort
mov [eine_dyn_array_var], eax

jetzt geht das NICHT mehr:
mov eax, [eine_dyn_array_var + 6 * sizeof(dd)]

Hierbei kommt Muell rum, da in eine_dyn_array_var nur ein pointer ist, kein
statischer Speicher (stells dir mit einem Sternchen mehr vor). Also:
mov ebx, [eine_dyn_array_var]
mov eax, [ebx + 6 * sizeof(dd)]

Du kannst solche arrays auch auf dem Stack anlegen und dann ueber ebp
adressieren, je nach dem welche "Lebenszeit" du fuer das array brauchst. Es ist
ein bischen die Frage ob du dieses Detail dem Programmierer deiner Sprache
offenbaren willst. Sonst muss es der Compiler selbststaendig erkennen ob das
geht, was manchmal gar nicht so einfach ist (pointer escape analysis). Wenn du
das array mit malloc erstellt hast, muss natuerlich ein free kommen. Das kann
der Compiler vielleicht von alleine, sonst musst du das dem Programmierer
aufbuerden. Oder garbage collection.

Bei eindimensional hab ich jetzt der einfachkeit halber die elemente
"hintereinader" in den Speicher gepackt. Das ist "uebersichtlich" und "logisch"
fuer viele Programmierer. Hat aber auch Nachteile (elemente einfuegen ist
schwer, arrays groesser machen kann eine neue adresse nach sich ziehen da der
block umziehen muss), die man aus C kennt, aber vielleicht fuer den "Anfaenger"
nicht so toll sind. Diese Nachteile werden quasi "immer" mit arrays in
Verbindung gebracht, sonst waeren es keine Arrays, sondern listen oder sowas. Es
kommt halt drauf an, wie "geschlossen" deine Sprache ist, wie viel sie
abstrahieren soll.

Das ist bisher auch sehr Low-Level, was in die Sprache "durchschlagen" kann, was
man vielleicht nicht will.
Du kannst deinen Arrays natuerlich ein wenig "fluff" geben:
In deiner Sprache sind arrays "einfach", ein typ den der Compiler kennt, aber
dahinter bestehen sie immer aus "magic". Um das zu verwalten ist dein array
erstmal ein struct.

struct lang_array {
size_t len;
enum type type;
/* irgendwelcher anderer kram... */
union {
char *cdata;
int *idata;
double *ddata;
} u;
};

Der Compiler loesst das jetzt aus der Highlevelsprache immer in den low-level
Kram dahinter auf.

dann sieht das statisch so aus:

ein_array_data:
times (16) dd 0

ein_array:
dd 16
dd 1
dd ein_array_data

bei einem zugriff:
x = ein_array[6]

macht der compiler daraus:
mov ebx, [ein_array + 2 * sizeof(dd)]
mov eax, [ebx + 6 * sizeof(dd)]

wenn der user schreibt:
FOR EACH ein_array AS i THEN

macht der compiler:
mov t, 0
schleifen_start:
mov eax, t
cmp eax, [ein_array + 0 * sizeof(dd)]
jae schleifen_ende
mov ebx, [ein_array + 2 * sizeof(dd)]
mov edx, t
mov eax, [ebx + edx * sizeof(dd)]
mov i, eax
; ...
; irgendein code
; ...
inc t
jmp schleifen_start
schleifen_ende:

(Hier wird es dann natuerlich angenehm wenn man einen Registerallokator und
Optimizer hat die dafuer sorgen das der Basepointer nur einmal vor der Schleife
geladen wird usw., nebenbei, du will keine Fliesskommazahlen als Index, das wird
sonst mit Rundungsfehlern "spassig")

Warum das jetzt?
Der user hat halt ein array, keine rohe Speicheradresse zu einem "klotz
Speicher", in einer Sprache die vieleicht keine Pointer unterstuezt.

Was soll passieren wen der user ein array einem anderen "zuweist"?
Jetzt wird bei eben sowas:
ein_anderes_array = ein_array
keine tiefe kopie gemacht (das kann man so machen, kommt halt drauf an wie man
die Sprache definiert, vielleicht soll es nach langspec eben eine erzeugen).
ein_anderes_array hat jetzt auch die Adresse des struct drum rum.
Und bei sowas:
IF NOT REDIM(ein_array, 32) THEN
ABORT
ENDIF

sind dann beide "Referenzen" "gere-dim-t", weil der Pointer zum eigentlichen
Speicher in deinem struct versteckt ist.
So muss man nicht suchen wo der Benutzer eine weitere Referenz zu dem Array
erzeugt hat (was teilweise unmoeglich sein kann...). Es sei denn man will das
anders haben (Was soll sie Sprache in dem Fall machen?).

Das hilft auch wenn du ein statisches array (eben das "ein_array") ploetzlich in
ein dynamisches umwandeln willst (eben damit ein user auch auf ein statische
array REDIM aufrufen kann, sich da keine Gedanken um obskure Regeln machen
muss). Dann wuerde sich der Typ (oder ein paar flags) aendern (+ man alloziert
Speicher, kopiert die Daten um). Oder man macht nie statische arrays.

Das macht es fuer den Sprachuser "etwas transparenter".

Man muss eben Regeln aufstellen, in die Sprachsyntax einbauen, dem Compiler
beibringen und im Hintergrund dann in ASM "passend" runterbrechen.
Nur ... ;-D

Das Problem ist ein bischen dass das eben NICHT mehr einfach "wie mache ich aus
x + y ASM" ist, sondern schon etwas involvierter ist und den Bereich der
Runtime, Syntax, Sprachdesign, Sprach-"Philosophie" (was soll das alles, was ist
das ziel, wofuer ist das gut, was ist erlaubt) beruehrt, was halt konsequent vom
Compiler umgesetzt werden muss (denn es soll irgendwann irgendwie auf Maschinen
Befehle runtergebrochen werden).

Jetzt stell dir noch vor du hast vollgendes:
ein_array = NEW_ARRAY(20)



ein_weiteres_array = SUBARRAY(ein_array, 6, 5)



REDIM(ein_array, 90)

hmmmm.
Tja. Da brauchen wir wohl mehr Magie an unserem struct lang_array...
Es ist halt hier nicht mehr die Frage "wie mach ich da ASM draus". Hier ist
schon die Frage wie man das am besten ueberhaupt umsetzt (interne Struktur der
Sprache).


So, wenn es mehrdimensional wird, hast du ein weiteres Problem.
Man kann mehrere Dimensionen auf zwei weisen darstellen.

1) Ein grosser linearer Block Speicher der eben mit Indexarithmetik passend
eingeteilt wird
2) Die letzte Dimension ist linearer Speicher, alle davor "pointer tabellen".

In C kann man beide Formen erzeugen:
double colors[16][16];
Ist vom typ 1).

double **colors;
ist vom typ 2)
Ja, pointer und arrays in C sind verwand, aber nicht das gleiche

Deshalb knallt auch sowas:

double lut_colors[16][16];

double some_func(double **colors)
{

}

some_func(lut_colors);

Der compiler kann lut_colors zu ** aufloesen, aber es passt trozdem binaer nicht
zusammen. Ich weiss nicht ob irgendein Compiler da ein warning gibt.
Richtig waere:
double some_func(double *colors[16])
{

}

Jetzt ist nur die Dimensionsgroesse fest verdrahtet...

Form 2) hat den Vorteil das der Compiler, auch im dynamischten Fall, die grade
gueltige Index-Arithmetik nicht kennen muss. Alles vor der letzten dimension
sind lineare arrays von pointern, die letzte Dimension ist ein linearer klumpen
Speicher.

Mal ein paar Bilder:

ein_mdim_array_typ_2:
++
| 0xcafebabe | -+
++ |
| 0xcafelate | + |
++ | +> 0xcafebabe:
| | | +-+
... . | datadata |
. +-+
. | datadata |
+-+



ein_mdim_array_typ_1:
+-+-+-+-+-+
| 00 | 01 | 02 | 03 | 04 | ...
+-+-+-+-+-+
| 10 | 11 | 12 | 13 | 14 | ...
+-+-+-+-+-+


fuer typ 1) ist der zugriff einfache mathmatik:
a = ein_mdim_array_typ1[y][x]

ist dann
a = ein_mdim_array_typ1 + y * dimension_size + x

mit mehr dimensionen wird das natuerlich immer laenger. Und der compiler muss
die Dimensionsgroessen immer kennen (zumindest wenn man da nicht viel Magie zur
Laufzeit reinbringt...).

fuer typ 2) sieht das dann eher so aus:
a = ein_mdim_array_typ2[y][x]
wird:
t = ein_mdim_array_typ2[y]
a = t[x]

hat nur den Nachteil das grad bei mehr Dimensionen die zugriffe wild duch den
Speicher gehen, und grade bei kleinen letzten Dimensionen (und/oder Datentypen)
die Pointertabellen teuer sind.

Richtig bloed wird es wenn man von einem Typ in den anderen muss um eine API zu
bedienen. Wenn man dann nicht genug Low-Level Magie hat (die man dem User ja gar
nicht mehr geben will, da ja Boese), wird es haesslich. Kann man natuerlich
vielleicht auch vom Compiler Magisch grade ziehen lassen.

In der eigenen Sprache, wo man arrays als "richtigen" typ macht kann man
natuerlich das ganze etwas abmildern (die Dimensionen sind im dahinterligenden
struct). Das wird dann aber natuerlich alles immer teurer.

Oder man gibt dem User die Brechstange:

FUNCTION some_func(a AS ARRAY, x AS UNSIGNED, y AS UNSIGNED) AS DOUBLE

b AS SUBARRAY(a, x, y)

FOR ...
sum += b[i][j]
ENDFOR
...
ENDFUN
REM ja, hier hoert der Spass auf...

Macht dann im Hintergrund schon das richtige. Gibt aber auch dem Nutzer genug
Strick sich selbst in den Fuss zu bohren.

Ich weiss nicht ob irgendein C Compiler folgendes zulaest:
double some_func(double *arg, size_t x, size_t y)
{
double *colors[x] = (*([x]))arg;
/* sch.. ich hab vergessen wie der array cast genau geht
man kann in C zumindest statische dimensionen "drancasten":
double *colors[16] = (*([16]))arg;
wenn die Syntax passt */
}

Sprachdesign ist halt schwer, besonders je nachdem wie nah oder fern man an der
Maschine sein will...

Wenn du was innovatives willst, auch weil dir die Nachteile von "klassisch"
nicht gefallen (vergroessern schwer, mehrdimensionale Arrays koennen auf zwei
weisen gebildet werden (und wenn das in die Sprache leaked den Pro-gamer
verwirren)), kann ich dir auf die schnelle auch nicht helfen.

Vieleicht einfach erstmal fuer alles function calls machen. Wenn man weiss wie
es aussehen soll, was gehen soll und was nicht, dann dem Compiler beibringen das
runterzubrechen.
Oder alles als dynamische Objekte machen, die dann zur Laufzeit ueber function
calls interpretiert werden?

Gruß
Jens



Gruss
Jan

If I had it all to do over again, I'd spell creat with an "e".
- Kernighan

Ähnliche fragen