Forum: Compiler & IDEs Registeroptimierung von Assemblercodes


von M. V. (bmtil)


Lesenswert?

Hallo, ich brauche etwas Klarstellung zur allgemeinen Möglichkeiten der 
Register- bzw. Variablenoptimierung beim Kompilieren von Assemblercode. 
Ich weiss, Asssembler kennt keine Variablen, sondern nur Bits und Bytes. 
Deswegen geht es ja eigentlich darum, möglichst weniger Register im Code 
zu verwenden. Nehmen wir an, wir haben eine Assemblersprache, bei der es 
keine Sprünge, Rekursionen und es werden keine zeitkritichen Quellcodes 
erstellt. -> Somit steht eine Voraussetzung für eine mögliche 
Optimierung:

Der Assemblercode wird exakt Zeile für Zeile abgearbeitet, von oben nach 
unten.

Nun, wenn ich jetzt der Compiler wäre, dem gesagt wird "optimiere die 
Register im erstellten Assemblercode", dann würde ich als aller erstes 
alle vorkommenden Register im Code nach gelesenen und geschriebenen 
Registern aufteilen -> ich gehe jede Zeile des Codes durch und schau, 
welches Register in dieser Zeile gelesen und welches geschrieben wird 
und dann erstelle ich mir zwei Listen (Read Register und Write 
Register)mit den Namen dieser Register.

Im zweiten Schritt würde ich durch den Vergleich der beiden Listen und 
der Nummer der Zeilen, wo die nur geschriebenen Register vorkommen, 
rausfinden welche Register, ab welcher Zeile ich mit neuen Werten 
beschreiben kann.

Im dritten Schritt wuerde ich alle Register-"Kandidaten", ab den 
entsprechenden Zeilen, welche nur noch gelesen werden, mit den Werten 
der Register aus der "Write Register" Liste beschreiben und übrig 
gebliebene "Write Register" Namen löschen = Ergebnis weniger verwendeter 
Register.

Ich hoffe ich liege mit meinen Ausführungen nicht arg daneben und falls 
ja, genau deswegen schreibe ich ja, damit ich hier aufgeklärt werde.

Mit besten Grüßen, bmtil.

von Arc N. (arc)


Lesenswert?

M. V. schrieb:
> Hallo, ich brauche etwas Klarstellung zur allgemeinen Möglichkeiten der
> Register- bzw. Variablenoptimierung beim Kompilieren von Assemblercode.
> Ich weiss, Asssembler kennt keine Variablen, sondern nur Bits und Bytes.
> Deswegen geht es ja eigentlich darum, möglichst weniger Register im Code
> zu verwenden. Nehmen wir an, wir haben eine Assemblersprache, bei der es
> keine Sprünge, Rekursionen und es werden keine zeitkritichen Quellcodes
> erstellt. -> Somit steht eine Voraussetzung für eine mögliche
> Optimierung:
>
> Der Assemblercode wird exakt Zeile für Zeile abgearbeitet, von oben nach
> unten.
>
> Nun, wenn ich jetzt der Compiler wäre, dem gesagt wird "optimiere die
> Register im erstellten Assemblercode", dann würde ich als aller erstes
> alle vorkommenden Register im Code nach gelesenen und geschriebenen
> Registern aufteilen -> ich gehe jede Zeile des Codes durch und schau,
> welches Register in dieser Zeile gelesen und welches geschrieben wird
> und dann erstelle ich mir zwei Listen (Read Register und Write
> Register)mit den Namen dieser Register.
>
> Im zweiten Schritt würde ich durch den Vergleich der beiden Listen und
> der Nummer der Zeilen, wo die nur geschriebenen Register vorkommen,
> rausfinden welche Register, ab welcher Zeile ich mit neuen Werten
> beschreiben kann.

Liveness-Analysis, Datenflussanalyse, CFG (Control-Flow-Graph)

> Im dritten Schritt wuerde ich alle Register-"Kandidaten", ab den
> entsprechenden Zeilen, welche nur noch gelesen werden, mit den Werten
> der Register aus der "Write Register" Liste beschreiben und übrig
> gebliebene "Write Register" Namen löschen = Ergebnis weniger verwendeter
> Register.

> Ich hoffe ich liege mit meinen Ausführungen nicht arg daneben und falls
> ja, genau deswegen schreibe ich ja, damit ich hier aufgeklärt werde.
>
> Mit besten Grüßen, bmtil.

Allgemeines Stichwort wäre Registerallokator. Wenn es optimal werden 
soll, ist das Problem NP-vollständig (da das Problem gleich zum 
Graphenfärben ist).

Für das speziellere Problem einen Ausdruck mit möglichst wenigen 
Registern zu berechnen gibt es den Sethi-Ullman-Algorithmus: 
https://en.wikipedia.org/wiki/Sethi%E2%80%93Ullman_algorithm

von (prx) A. K. (prx)


Lesenswert?

M. V. schrieb:
> Der Assemblercode wird exakt Zeile für Zeile abgearbeitet, von oben nach
> unten.

Meist geht es nicht um die Anzahl Register, sondern um die Laufzeit. 
Dann ist diese Annahme heutzutage oft nicht mehr sinnvoll. Schon 
in-order CPUs führen ggf. mehrere Operation pro Takt durch, wodurch die 
Abhängigkeiten und deren zeitlicher Abstand in den Fokus rücken.

von M. V. (bmtil)


Lesenswert?

Vielen Dank für die Antworten, das hilft mir definitiv weiter. Der Grund 
wieso ich frage ist, ich habe zwei Assemblercode Beispiele liegen, beide 
Quellcodes tun ein und das selbe. Es geht um Weißlichtinterferometrie. 
Ein Assemblerbeispiel ist vom Compiler erstellt und nicht optmiert -> 
benötigt ~1500 Variablen. Selbes Programm vom Menschen geschrieben, in 
langer Arbeit allerdings -> ~100 Variablen. Schon krasser Unterschied 
wie ich finde und ich frage mich auch, ob ein Optimierer den 
cCompilergenerierten Code auf ähnliche Anzahl Variablen bringen kann.

von Peter II (Gast)


Lesenswert?

M. V. schrieb:
> Ein Assemblerbeispiel ist vom Compiler erstellt und nicht optmiert
was meinst du mit "nicht optmiert"?

keine Optimierung im Compiler eingeschaltet oder nicht nachträglich 
optmiert?

Wenn es vorher C code war, kann man auch dort geschickt Programmieren 
(oder halt genau das Gegenteil)

von (prx) A. K. (prx)


Lesenswert?

M. V. schrieb:
> Ein Assemblerbeispiel ist vom Compiler erstellt und nicht optmiert ->
> benötigt ~1500 Variablen. Selbes Programm vom Menschen geschrieben, in
> langer Arbeit allerdings -> ~100 Variablen.

Das ist ungefähr der Unterschied zwischen dem Rindvieh auf der Weide und 
der fertigen Scheibe im Hamburger. ;-)

von M. V. (bmtil)


Lesenswert?

Mit "nicht optimiert" meine ich, der Compiler besitzt noch keine 
Optimieroption. Vorher war es ein Simulink Modell.

A. K. schrieb:
> Das ist ungefähr der Unterschied zwischen dem Rindvieh auf der Weide und
> der fertigen Scheibe im Hamburger. ;-)

Eben genau das habe ich mir auch gedacht. Jetzt brauche ich das 
theoretische Know-How um aus der Kuh eine Köstlichkeit zu zubereiten.

: Bearbeitet durch User
von (prx) A. K. (prx)


Lesenswert?

Nächste Uni-Bibliothek, Abteilung Informatik, Regal "Compilerbau". Und 
überspring alles in Deutsch, die lingua franca der Branche ist Englisch.

von Sodan (Gast)


Lesenswert?

> Und überspring alles in Deutsch, die lingua franca der Branche ist
> Englisch.

Das ist der übliche Unfug, der hier so von den Rentner verbreitet wird.

---

Das beste Buch, das zum Compilerbau gibt, dürfte das Drachenbuch sein 
und dies gibt es in einer erstklassigen Übersetzung.

https://www.amazon.de/Compiler-Prinzipien-Techniken-Werkzeuge-Pearson/dp/3827370973

von Kaj (Gast)


Lesenswert?

Sodan schrieb:
>> Und überspring alles in Deutsch, die lingua franca der Branche ist
>> Englisch.
>
> Das ist der übliche Unfug, der hier so von den Rentner verbreitet wird.
Naja, wie so oft in der Informatik ist die richtige Antwort:
Kommt drauf an!

Es gibt Buecher, z.B. Moderne Betriebsysteme (3. Auflage) von Tanenbaum, 
da kann ich auch nur sagen: Nimm bloss nicht die deutsche Ausgabe! Die 
ist so schlecht uebersetzt, dass man viele Saetze 5x lesen muss, um zu 
verstehen was gemeint ist.

Andere Buecher, wie z.B. zu C++, Python usw. kann man ruhig deutsche 
Ausgaben kaufen.

Auch die deutschen Ausgaben von Compilerbau (Teil 1 & 2) von '99 sind 
sehr gut.
https://www.amazon.de/Compilerbau-Tle-Tl-1-Alfred-Aho/dp/3486252941

Solange die Uebersetzungen gut sind, spricht nichts dagegen die deutsche 
Ausgabe zu lesen. Fachbegriffe werden nur in den allerwenigsten Faellen 
eingedeutscht.
Solange "Server" nicht mit "Servierer", "Client" nicht mit 
"Kunde/Klient", "online" und "offline" nicht mit "anschnur" und 
"abschnur", und "Youtube" nicht mit "DuRoehre" uebersetzt werden, ist 
alles okay ;)

von Arc N. (arc)


Lesenswert?

M. V. schrieb:
> Mit "nicht optimiert" meine ich, der Compiler besitzt noch keine
> Optimieroption. Vorher war es ein Simulink Modell.
>
> A. K. schrieb:
>> Das ist ungefähr der Unterschied zwischen dem Rindvieh auf der Weide und
>> der fertigen Scheibe im Hamburger. ;-)
>
> Eben genau das habe ich mir auch gedacht. Jetzt brauche ich das
> theoretische Know-How um aus der Kuh eine Köstlichkeit zu zubereiten.

Für einen realen Prozessor oder was theoretisches?
Im ersteren Fall: Compilerbau/Code-Optimierung ist zwar ein sehr schönes 
Feld, aber alles andere als einfach. Gerade das Optimieren ist alles 
andere als trivial. Angefangen mit brauchbarem IR (Intermediate 
Representation, bspw. GIMPLE beim gcc oder LLVM IR 1)), SSA, 
Control-/Data-Flow-Analysis, dann alle auf dem IR möglichen 
Optimierungen (u.a. Loop-invariant code motion, Common Subexpression 
Elimination, Constant Folding/Propagation, Pipelining usw.), dann alles 
maschinenspezifische Registerallokation, Instruction-Scheduling, 
Reordering), Interprocedural Optimization/Link-Time-Optimization usw. 
usf.

Wenn einen das Thema nicht wirklich interessiert und/oder nicht viel 
Zeit für das Vorhaben da ist, würde ich hier maximal IR für bspw. LLVM 
erzeugen oder noch früher ansetzen und einfachen C-Code erzeugen und 
diesen einem Compiler zum Optimieren überlassen.

1) http://llvm.org/docs/LangRef.html
https://gcc.gnu.org/onlinedocs/gccint/GIMPLE.html

Edit: @Drachenbuch. Das ist wie mit allen Lehrbüchern. Den einen 
schmeckts, den anderen nicht. Engineering a Compiler oder auch Crafting 
a Compiler with C kann man sich ebenso ansehen oder für den Anfang 
https://people.inf.ethz.ch/wirth/CompilerConstruction/index.html

: Bearbeitet durch User
von Peter D. (peda)


Lesenswert?

M. V. schrieb:
> Ein Assemblerbeispiel ist vom Compiler erstellt und nicht optmiert ->
> benötigt ~1500 Variablen. Selbes Programm vom Menschen geschrieben, in
> langer Arbeit allerdings -> ~100 Variablen.

Ein Compiler kann nicht in Deinen Kopf schauen. Du mußt ihm als Mensch 
schon sagen, welches minimale Format und welchen Gültigkeitsbereich die 
Variablen haben sollen. Nur dann kann er sie optimieren.

Gerne wird dem Compiler gesagt, Du mußt int benutzen, obwohl char 
ausreichen würde. Das verdoppelt schonmal den Speicherbedarf.
Und gerade Anfänger schmeißen mit globalen Variablen nur so um sich. Dem 
Compiler sagt man damit: "Finger weg, die gelten ewig".
Nur lokale Variablen darf der Compiler optimieren.

von Johann L. (gjlayde) Benutzerseite


Lesenswert?

M. V. schrieb:
> Mit "nicht optimiert" meine ich, der Compiler besitzt noch keine
> Optimieroption. Vorher war es ein Simulink Modell.

Du willst doch nicht sagen, dass die eigens einen Compiler 
implementieren willst?

von M. V. (bmtil)


Lesenswert?

> Du willst doch nicht sagen, dass die eigens einen Compiler
> implementieren willst?
Aus dem Modell wurde mit dem "Compiler" (es ist kein richtiger Compiler, 
nur ein Matlab Projekt) ein Assemblercode erzeugt. Das geht auch nur mit 
den Modellen, die mit einer dafuer vorgesehen Bibliothek erstellt 
wurden.

von Nop (Gast)


Lesenswert?

Peter D. schrieb:

> Ein Compiler kann nicht in Deinen Kopf schauen. Du mußt ihm als Mensch
> schon sagen, welches minimale Format und welchen Gültigkeitsbereich die
> Variablen haben sollen. Nur dann kann er sie optimieren.

Deswegen kann man ja in C den Scope der Variablen minimieren, und seit 
C99 sogar in einer for-Schleife die Schleifenvariable direkt 
deklarieren.

> Gerne wird dem Compiler gesagt, Du mußt int benutzen, obwohl char
> ausreichen würde. Das verdoppelt schonmal den Speicherbedarf.

Kann aber speziell auf ARM Sinn ergeben, weil int dort schneller ist. 
Wirklich sauber und portabel ist das dann natürlich mit den 
C99-Fast-Datentypen.

von holger (Gast)


Lesenswert?

>Deswegen geht es ja eigentlich darum, möglichst weniger Register im Code
>zu verwenden.

Was für ein Schwachsinn. Der Code soll besser werden wenn man
die Ressourcen der CPU NICHT möglichst vollständig ausnutzt?

Beitrag #4854104 wurde von einem Moderator gelöscht.
von (prx) A. K. (prx)


Lesenswert?

Rolf schrieb im Beitrag #4854104:
> Ansonsten sollte man schon mit seinen Ressourcen haushalten, man weiß ja
> nicht, wozu man einzelne Register womöglich noch brauchen kann.

Der Code ist bekannt. Was soll da noch kommen, wofür man Reserve 
vorhalten müsse? Mit den Ressourcen haushalten heisst im Fall eines 
Compilers, sie soweit für die Leistung sinnvoll auch vollständig zu 
nutzen. Ein Compiler betrachtet den Code nach jeder Änderung neu und 
optimiert vollständig neu.

Anders kann es sich bei einem Assembler-Programmierer verhalten. Der 
muss vielleicht damit rechnen, dass sich der Code ändert und könnte 
deshalb deine Ressourcen-Schere im Kopf haben. Denn der 
Asm-Programmierer schreibt seinen Code nicht jedesmal neu.

Genau dieser Unterschied in der Herangehensweise führt beispielsweise 
dazu, dass ein Asm-Programmer nur ungern ein "switch" Statement als 
Entscheidungsbaum implementiert. Weil der Baum bei jeder Änderung der 
Fälle neu aussieht. Dem Compiler ist das völlig egal.

: Bearbeitet durch User
von Dumdi D. (dumdidum)


Lesenswert?

Nur um zu sehen, ob Du unter 'Register' etwas anderes als der Rest hier 
verstehst: wie viele Registrr hat Deine CPU, wie viele werden vom 
Programm genutzt?

von Udo (Gast)


Lesenswert?

M. V. schrieb:
> beim Kompilieren
> von Assemblercode

Assemblercode wird assembliert,
Hochsprachencode kompiliert.

von --------------------- (Gast)


Lesenswert?

üblicherweise ist die Anzahl der Register in Prozessoren fix.
Also mehr Register als vorhanden können nicht benutzt werden und warum 
sollte man weniger verwenden?
Ach werden Register oft vom RAM in das Register und vom Register in das 
RAM benutzt. Warum sollte also eine Aufteilung in Lese und Schreibe 
Register erfolgen?
Ich denke wenn du nicht einen Compiler oder Assembler für eine 
Architektur entwickelst, dann brauchst du dir über darüber keine 
Gedanken machen.

von M. V. (bmtil)


Lesenswert?

Uff, ganz schöne Diskussion hier losgetreten, wollte ich gar nicht.

>Assemblercode wird assembliert,
>Hochsprachencode kompiliert.

Das ist natuerlich voellig korrekt, man sollte die Fachbegriffe nicht 
vertauschen.


>Nur um zu sehen, ob Du unter 'Register' etwas anderes als der Rest hier
>verstehst: wie viele Registrr hat Deine CPU, wie viele werden vom
>Programm genutzt?

Ich habe keine explizite Hardware mit der ich arbeite. Ich arbeite mit 
Simulink Modellen, von denen aus der ASM Code erstellt wird. Für welche 
Hardware genau, weiss ich leider nicht. Den ASM Code soll später ein 
"Softcore" eines FPGAs verarbeiten glaube ich. Auch eigens Entwicklung 
des Fachgebiets.

Der ganze "Simulink zu ASM Compiler" ist leider ein mehrere Jahre altes 
Brownfield Projekt in dem ich angefangen habe zu arbeiten. Und ich bin 
jetzt soweit, dass ich endlich in dem Projekt weit genug blicke, dass 
ich mit meiner Aufgabe der Variablenoptimierung (sind ja eigentlich 
Register) beginnen kann. Das Projekt liefert mir eben einen 
unoptimierten Code+Variablenliste. Mit Hilfe dieser Daten und Kenntnisse 
über die spezielle ASM_Sprache, die für das Projekt entwickelt wurde, 
habe ich in Matlab einen Textparser geschrieben, der eben die Register, 
die verwendet werden in Lese und Schreiberegister aufteilen kann.

Beste Grüße und vielen Dank für die Anregungen.

: Bearbeitet durch User
von Dr. (Gast)


Lesenswert?

M. V. schrieb:
> Ich habe keine explizite Hardware mit der ich arbeite. Ich arbeite mit
> Simulink Modellen, von denen aus der ASM Code erstellt wird. Für welche
> Hardware genau, weiss ich leider nicht. Den ASM Code soll später ein
> "Softcore" eines FPGAs verarbeiten glaube ich. Auch eigens Entwicklung
> des Fachgebiets.

D.h. du erzeugst nur eine Art Zwischencode (wie z.B. in Java oder .net) 
und keinen echten Assemblercode. Assembler ist nämlich immer hochgradig 
spezifisch für die Plattform.

Sag das doch gleich, dass das eben KEIN Assembler ist.

M. V. schrieb:
> Der ganze "Simulink zu ASM Compiler" ist leider ein mehrere Jahre altes
> Brownfield Projekt in dem ich angefangen habe zu arbeiten. Und ich bin
> jetzt soweit, dass ich endlich in dem Projekt weit genug blicke, dass
> ich mit meiner Aufgabe der Variablenoptimierung (sind ja eigentlich
> Register) beginnen kann. Das Projekt liefert mir eben einen
> unoptimierten Code+Variablenliste. Mit Hilfe dieser Daten und Kenntnisse
> über die spezielle ASM_Sprache, die für das Projekt entwickelt wurde,
> habe ich in Matlab einen Textparser geschrieben, der eben die Register,
> die verwendet werden in Lese und Schreiberegister aufteilen kann.

Ohne Wissen über die zugrunde liegende Plattform zu optimieren kann nur 
scheitern. Was, wenn euer Softcore sowieso 32 oder mehr Register haben 
wird?

Ich denke ihr solltet euch mal grundlegende Gedanken über das Projekt 
machen und was ich erreichen wollt. Optimierung nur der Optimierung 
willens macht nur Arbeit und bezweckt genau gar nichts. Man muss sich 
das schon sehr gut überlegen...

von S. R. (svenska)


Lesenswert?

Dr. schrieb:
> Optimierung nur der Optimierung
> willens macht nur Arbeit und bezweckt genau gar nichts.

Im Uni-Umfeld kriegt man damit Veröffentlichungen und damit Geld.

M. V. schrieb:
> Ich habe keine explizite Hardware mit der ich arbeite. Ich arbeite mit
> Simulink Modellen, von denen aus der ASM Code erstellt wird.

Ist das auch wirklich Assembler oder nur ein Assembler-artiger 
Zwischencode? Wie wird dieser Code später in die Hardware reinkommen, 
gibt es da noch einen Zwischenschritt?

M. V. schrieb:
> Den ASM Code soll später ein
> "Softcore" eines FPGAs verarbeiten glaube ich.

Softcores in FPGAs sind relativ langsam, insofern wird die Performance 
ohnehin nicht besonders toll sein.

Wenn ihr definitiv auf einen Prozessor hinarbeitet (und nicht auf feste 
Logik), dann ist es vielleicht sinnvoll, keinen Assemblercode zu 
erzeugen, sondern z.B. mittelprächtigen C-Code. Ein guter C-Compiler wie 
gcc oder llvm kann daraus Code für deine Zielarchitektur erzeugen, der 
deutlich besser sein wird als das, was du zu Fuß machst.

Dem gcc ist es egal, ob du 100 oder 500 Variablen hast. Wenn er 
nachweisen kann, dass du nie mehr als 12 gleichzeitig brauchst, dann 
wird er den Registerverbrauch schon passend hinoptimieren.

Arc N. schrieb:
> Allgemeines Stichwort wäre Registerallokator. Wenn es optimal werden
> soll, ist das Problem NP-vollständig (da das Problem gleich zum
> Graphenfärben ist).

Wenn man die Registerallokation innerhalb der SSA-Form erledigt, dann 
lässt sich der Graph auch in polynomialer Zeit optimal färben. SSA wird 
von allen großen Compilern genutzt, aber ob sie auch den Allokator 
benutzen, weiß ich nicht.

von Johann L. (gjlayde) Benutzerseite


Lesenswert?

S. R. schrieb:
> M. V. schrieb:
>> Den ASM Code soll später ein
>> "Softcore" eines FPGAs verarbeiten glaube ich.
>
> Softcores in FPGAs sind relativ langsam, insofern wird die Performance
> ohnehin nicht besonders toll sein.
>
> Wenn ihr definitiv auf einen Prozessor hinarbeitet (und nicht auf feste
> Logik), dann ist es vielleicht sinnvoll, keinen Assemblercode zu
> erzeugen, sondern z.B. mittelprächtigen C-Code. Ein guter C-Compiler wie
> gcc oder llvm kann daraus Code für deine Zielarchitektur erzeugen, der
> deutlich besser sein wird als das, was du zu Fuß machst.

ACK.  Allerdings zeigt die Erfahrung, dass selbst namhafte 
Hardwarehersteller bzw. deren Hardware-Designer nicht weiter denken 
(können) als bis zu Assembler-Code.  Um eine Architektur zu bekommen, um 
sinnvoll einen der führenden Compiler darauf anpassen zu können, 
beaucht's daher fast notwendig ein Co-Design von Hardware, Simulatur und 
Compiler:

Bereits bevor es Silizium gibt, gibt es einen Simulator, der das 
angestrebte Design möglichst getreu umsetzt und der einem 
Compilerhersteller zur Verfügung steht.  Die Compilerbauer können also 
bereits mit der Implementation beginnen, noch bevor es Hardware gibt, 
und idealerweise gibt es mit Release der Hardware bereits ausgereifte 
Tools (Simulator, Assembler, Linker, Compiler, Debugger, 
Standard-Bibliotheken, Board-Support (z.B. Header für SFRs, ...)). 
Falls sich bestimmte Features seitens des Compilers als schlecht, 
hinderlich, überflüssig, fehlend, fehleranfällig o.ö erweisen, gibt es 
Rückmeldung an die Hardware-Jungs, die das dann berücksichtigen.

> Arc N. schrieb:
>> Allgemeines Stichwort wäre Registerallokator. Wenn es optimal werden
>> soll, ist das Problem NP-vollständig (da das Problem gleich zum
>> Graphenfärben ist).
>
> Wenn man die Registerallokation innerhalb der SSA-Form erledigt, dann
> lässt sich der Graph auch in polynomialer Zeit optimal färben. SSA wird
> von allen großen Compilern genutzt, aber ob sie auch den Allokator
> benutzen, weiß ich nicht.

GCC nuntzt SSA, allerdings nicht mehr zur Registerallokation — das 
geschieht nach SSA auf einer hardware-näheren Darstellung (RTL).

Polynomiale Laufzeit ist übrigens nicht ausreichend:  In GCC ist z.B. 
jeglicher Algorithmus tabu, der nicht mindestens linearistische Laufzeit 
hat.  Bereits quadratische Algorithmen sind damit gestorben :-) sowohl 
was Laufzeit als auch was Speicherplatz angeht.

Und ja, auch GCC verwendet Graphenfärbung zur Registerallokation, aber 
wie bei vielen anderen "harten" Problemen auch (z.B. Scheduling) besteht 
die Kunst darin, linearistische Algorithmen abzuleiten, die zwar keine 
optimale Lösung mehr garantieren, aber immer noch saugut sind.

Und neben der reinen R-Zuordnung hat ein R-Allocator auch noch andere 
Aufgaben zu erledigen, z.B. Life-Range-Splitting: Wenn es nicht genügend 
Register gibt, werden einige in den Frame ausgelager, und die Frage ist 
dann, welche Register und zu welchem Zeitpunkt diese gesichert und 
restauriert werden.  Und dafür muss passender Spill-Code erzeugt werden, 
dito wenn noch genügend Register da sind, aber nicht die passende 
Registerklasse.  Evtl. lohnt auch Rematerialisierung, d.h. anstatt eines 
Spills wird ein bekannter Wert neu berechnet.

Der Aufwand für solche Implementierungen wird von Unbedarften i.d.R. 
drastisch unterschätzt.

von M. V. (bmtil)


Lesenswert?

Hallo,
wir haben uns auf die Bezeichnung "Model based assembly code generator" 
geeignet. Der Assembler Code, den wir verwenden ist auch 
Eigenentwicklung mit eigenen Spezifikationen. Auf höheren (oder 
unteren?) Abstraktionsebenen (auch so ein tolles Wort), quasi bei den 
Vorprojekten passiert schon jede Menge Optimierung.

Der erzeugte Zwischencode wird von einem bereits fertigem Compiler in 
Binärcode übersetzt, der Binärcode kommt dann auf die Hardware.

Da Graphenfärbung NP vollständig ist, ist es ja nicht notwendig, dass 
die Variablenreduktion optimal verlaeuft, moeglichst gut sollte sie 
sein.

Ich glaube nicht, dass man dieses Projekt mit GCC oder ähnlichen 
Compilern vergleichen kann, da die Hardware Frage nicht wirklich geklärt 
ist, und somit wichtige "Randbedinungen" fehlen.

Grüße.

Bitte melde dich an um einen Beitrag zu schreiben. Anmeldung ist kostenlos und dauert nur eine Minute.
Bestehender Account
Schon ein Account bei Google/GoogleMail? Keine Anmeldung erforderlich!
Mit Google-Account einloggen
Noch kein Account? Hier anmelden.