Turbo Toolbox

home *** CD-ROM | disk | FTP | other *** search

/ Turbo Toolbox / Turbo_Toolbox.iso / spezial / 02 / texte / pascomp.7 < prev next >

Wrap

Text File | 1980-01-03 | 15.4 KB | 369 lines

PASCOMP PASCAL baut einen Pascal-Compiler Teil 8: Optimierung von Johannes Velmans Nachdem wir die Synthesephase eines Compilers mit dem Thema "Co- deerzeugung" eingeleitet haben, fahren wir nun mit dem Kapitel Optimierung fort. Was ist eigentlich das Ziel der Optimierung? Natürlich eine Verbesserung des Programmlaufes unter diversen Gesichtspunkten, wie zum Beispiel Speicherplatzbedarf, Register- bedarf, Ausführungszeit, Codegröße und vieles mehr. Dabei ist jedoch zu beachten, daß ein absolutes Optimum bezüglich aller genannten Gesichtspunkte nicht realisierbar ist, da die meisten Optimierungstechniken in einer derartigen Wechselwirkung zueinander stehen, daß im Grunde genommen der vollständige Opti- mierungsprozeß so lange in seiner Gesamtheit wiederholt werden müßte, bis sich zu guter Letzt keine Änderungen mehr ergeben. Da dieses in der Praxis wegen des zu großen Rechenaufwandes nicht durchführbar ist, beschränken wir uns auf eine feste Anzahl und Reihenfolge von Verfahren, um insgesamt eine relativ gute Opti- mierung zu erreichen. Unser Hauptaugenmerk ist nun darauf gerich- tet, die durch die Eigenschaften der Programmiersprache selbst zwangsläufig entstehenden Probleme in Bezug auf Effizient so gut es geht zu komprimieren und somit eine Verbesserung herbeizufüh- ren - und nicht Probleme, die durch schlechten Progammierstil entstanden sind, zu beseitigen. Die Grundlage einer jeden Optimierung bilden sogenannte Kosten- Funktionen. Die allgemein üblichen Bewertungskriterien solcher Kosten sind zum Beispiel die Code-Größe, die Ausführungszeit und der Speicherplatzbedarf von Daten. Aber auch eine Menge von Be- ziehungen zwischen den einzelnen Komponenten eines Programms sind hier von Bedeutung. Gute Optimierung hat zwangsläufig die Imple- mentierung verschiedener Datenzugriffsoperationen zur Folge. Man kann sogar weitergehend sagen, daß unterschiedliche Optimierungs- formen auch unterschiedliche Ausführungsreihenfolgen der verwen- deten Optimierungsschritte zur Folge haben. Auf die einzelnen Optimierungsschritte gehen wir später noch ein. Aufgrund dieser unterschiedlichen Ausführungsreihenfolgen der Optimierungsschritte stellt der in der semantischen Analyse er- zeugte attributierte Strukturbaum keinen Ausgangspunkt für eine Optimierung dar. Der Grund dafür: Der attributierte Strukturbaum spiegelt in erster Linie die verwendete Syntax und Semantik eines Programms wieder. Für die Optimierung ist er viel zu umfangreich, da hier hauptsächlich nur der Berechnungsablauf von Bedeutung ist. Zu diesem Zweck wird jede für die Optimierung nicht benötig- te Information aus dem Strukturbaum gestrichen. Eine weitere zu umgehende Schwierigkeit bei der Optimierung besteht darin, daß bei vielen Maschinen eine Reihe von Berechnungsoperationen nicht in Form einer einzigen Berechnung dargestellt werden können, son- dern ein "Anweisungspaket" erfordern. Ein Beispiel hierfür stellt die Addition von Real-Zahlen auf dem M68000-Prozessor dar, bei dem für eine derartige Addition mehrere Befehle notwendig sind. Eine Einflußnahme der Optimierung auf solche Pakete ist erfah- rungsgemäß recht schwierig. Abhilfe schafft hier eine Bibliothek, in der solche Routinen untergebracht werden. Das entsprechende Code-Stück wird dann einfach durch einen Verweis in diese Biblio- thek ersetzt. Der aus dem attributierten Strukturbaum durch Weglassen verschie- dener Teile entstehende Baum wird als Berechnungsgraph bezeich- net. Er stellt eine Schnittstelle zwischen der semantischen Ana- lyse und der Code-Optimierung bzw. Code-Erzeugung dar. Dieses von uns nun neu eingeführte Hilfsmittel soll folgende Eigenschaften besitzen: - Alle Operationen des Quelltextes sind durch Operationssequenzen ersetzt worden, die dem Befehlssatz der Zielmaschine entsprechen. Eventuelle Anpassungen werden jedoch nur dann mitberücksichtigt, wenn sie auch ihre Entsprechung in dem zugehörigen Code finden. -Jede Operation steht für sich alleine mit einer geeigneten An- zahl von Operanden. (Also kein "Versteckspielen" in Anweisungspa- keten mehr.) -Adreßrechnungen sind explizit. -Zuweisungen an Programmvariable werden getrennt von anderen Ope- rationen behandelt. -Kontrollfluß wird mit Hilfe von bedingten und unbedingten Sprün- gen dargestellt. Obwohl die Grundlage unseres Berechnungsgraphen der Befehlssatz der Zielmaschine ist, kann man hier doch von Maschinenunabhängig- keit sprechen, da das Grundkonzept dieses Berechnungsgraphen eng an die Arbeitsweise eines Von-Neumann-Rechners angelehnt ist, der in seiner Grundstruktur die Ausgangsbasis vieler realer Maschinen bildet. Darstellen läßt sich nun dieser Berechnungsgraph durch eine Ver- kettung von Knoten. In Pascal zum Beispiel haben derartige Knoten das definierte Aussehen, wie in Tabelle 1 gezeigt. Um uns einen Einblick in den Aufbau eines Berechnungsgraphen zu verschaffen, betrachten wir den Berechnungsgraphen für das folgende Pascal- Programmstück: ..... (* der Speicherumfang für INTEGER sei 2 Bytes, der für REAL 4 Bytes *) VAR i,a : INTEGER; x : REAL; ..... a := i; WHILE a < 10 DO BEGIN a := a+1; x := a; END; Betrachtet man nun diesen Graphen, so läßt sich abschließend als Faustregel zu seiner Konstruktion sagen: -nimm den attributierten Strukturbaum -vereinfache seine Struktur -lasse die deklarativen Teile weg -vergiß alle nicht benötigten Attribute -füge die Ausführungsreihenfolge neu hinzu. Eine weitere notwendige Voraussetzung zur Optimierung ist neben der Erstellung des oben erwähnten Berechnungsgraphen auch die Kenntnis über gewisse Eigenschaften realer Maschinen, wobei die hier angegebenen Beispiele sich auf den Mikroprozessor M68000 beziehen. Zunächst ein paar Sätze zu Speicherklassen: Bei diesen unter- scheidet man zwischen Hauptspeicher, Register, Spezialregister und Registerkeller. Der Hauptspeicher besteht aus direkt adres- sierbaren Speicherzellen. Je nachdem, ob Gruppen von ein, zwei oder vier Bytes zusammengefaßt werden, spricht man von einer Ein- teilung in Byte (oder Halbwort), Wort oder Langwort. Entsprechend heißt ein Hauptspeicher Byte-orientiert, wenn seine kleinste adressierbare Zelle ein Byte um faßt und Wort-orientiert, falls die kleinste adressierbare Einheit der Größe von zwei oder vier Bytes entspricht. Verwendet wird der Hauptspeicher als Programm-, Daten- oder Kellerspeicher. Bei Registern handelt es sich um Speicher für Befehlsoperanden. Sie werden in allgemeine Register aufgeteilt: Datenregister für Ganzzahl-Operanden (D0 bis D7), Register für Gleitpunkt-Operan- den, Indexregister zur Verknüpfung mit Adressen und den Adreßre- gistern (A0 bis A7). Spezialregister umfassen zum Beispiel den Befehlszähler, den Condition-Code (er enthält das Ergebnis von Vergleichen) und den Kellerpegel (A7). Je nach Anzahl der Operanden in Maschinenbefehlen unterscheidet man zwischen 0-, 1-, 2- und 3-Adressbefehlen. Allgemein lassen sie sich in folgender Form schreiben: 3-Adressbefehl : A3 := A1 op A2 2-Adressbefehl : A1 := A1 op A2 1-Adressbefehl : Akkumulator := Akkumulator op A1 0-Adressbefehl : op Betrachtet man nun die Operanden an sich, so läßt sich auch hier eine Einteilung vornehmen, die als Grundlage für die jeweiligen Adressierungsarten dient: c konstanter Wert im Befehl Ri Registerinhalt Ri + c Registerinhalt verknüpft mit einem konstanten Wert Ri + Rj Verknüpfung zweier Registerinhalte -Ri Prädekrement Ri+ Postinkrement Unterteilungskri- terium Knotenname zugehörige Operanden Ausdrücke Operator lg t-lop t_rop t_seq Literal lg wert t_seq Variable lg adresse t_seq Anweisungen Zuweisung lg t_ziel t_quelle t_seq if1 t_bed t_then t_seq if2 t_bed t_then_else t_seq while t_bed t_rumpf t_seq sprung t_ziel t_seq Erläuterung: - t_ steht für Referenzen auf Nummern von entsprechenden Knoten - t?seq bezeichnet den nächsten Knoten in der Ausführungsreihenfolge. - stellt die Speichergröße des bezeichneten Knotennames dar. Tabelle 1: Verkettung von Knoten in Pascal Derartige Kenntnisse sind dann sehr hilfreich, wenn es zum Bei- spiel um eine sinnvolle und registersparende Auswertung arithme- tischer Ausdrücke geht. Dies soll hier näher anhand eines Bei- spiels erläutert werden. Nehmen wir folgenden arithmetischen Aus- druck: (a + b) * c +((a + b) c-(a + b)) Stellt man diesen Ausdruck in Baumform dar, aus dem sich dann sehr einfach eine 3-Adress-Form konstruieren läßt, um dann an- schließend die entsprechenden Register zuzuteilen, so erhält man einen Ausdrucksbaum mit einer möglichen Registerzuteilung. Der zugehörige Code hätte dann die folgende Gestalt: move a,D1 add D3,D2 move b,D2 sub D2,D1 add D2,D1 move a,D2 move c,D2 move b,D3 mul D2,D1 add D3,D2 move a,D2 add D2,D1 move b,D3 Insgesamt also ein ziemlich langes Codestück für diesen Ausdruck. Deshalb erhebt sich die Frage, ob sich dieses Code-Stück nicht verkürzen läßt. Schreiben wir uns noch einmal zur besseren Über- sicht den Ausdruck auf und betrachten ihn näher: (a+ b) * + c +((a + b) * c - (a + b)) Was wiederholt vorkommt, ist zum einen der Teilausdruck (a+b) und zum anderen der Teilausdruck (a+b)*c. Berücksichtigt man dies bei der Konstruktion des Baumes. Wird Register D3 eingespart. Aber auch das entsprechende Code- Stück wurde kürzer: move a,D1 move b,D2 add D2,D1 move c,D2 mul D1,D2 sub D2,D1 add D2,D1 Lokale Optimierung Der Vollständigkeit halber sei hier erwähnt, daß es neben der lokalen Optimierung auch eine globale Optimierung gibt, deren nähere Ausführung jedoch den Rahmen dieses Artikels sprengen wür- de. Die lokale Optimierung ist das einfachste Mittel, um eine Verbes- serung des ausführbaren Codes zu erreichen. Die Grundidee besteht darin, sogenannte Basisblöcke zu definieren und jeden derartigen Basisblock als eine von seiner Umgebung losgelösten Einheit zu betrachten und ihn völlig unabhängig von seiner Umgebung zu opti- mieren. Dabei definiert man einen Basisblock als eine maximale Folge von Operationen, so daß jede Operation genau einmal ausge- führt wird, wenn die erste ausgeführt wird. Für jeden einzelnen Basisblock wird ein Berechnungsgraph konstru- iert, transformiert und anschließend als Grundlage zur Konstruk- tion des endgültigen Maschinencodes benutzt. Um nun die jeweils einzelnen Basisblöcke zu optimieren, verwendet man folgende Stra- tegie in der angegebenen Reihenfolge: 1. Schritt: Hier wird der betrachtete Block mit Hilfe symbolischer Werte ab- gearbeitet. Das Ziel ist, überflüssige Berechnungen zu entdecken, um diese dann anschließend zu eliminieren. Beispiel einer über- flüssigen Anweisung: : move b,D1 : add c,D1 a := b+c move D1,a x := a-d move a,D1 ^ überflüssige Anweisung, kann eliminiert werden : sub d,D1 : move D1,x Hier wird an den Grenzen zusammengesetzter Code-Stücke deutlich, daß überflüssige Anweisungen vorkommenmen können, die man dann im Laufe des Optimierungsprozesses entfernen kann. Ein weiteres Bei- spiel ist das Auffinden von derartigen Code-Stücken, die aufgrund der sie umgebenden Anweisungen eigentlich nie erreicht und ausge- führt werden können - und somit auch als toter Code bezeichnet werden. Beispiel eines "toten" Code-Stückes: : : goto m ? : Z- toter Code, dieser Teil kann : niemals durchlaufen werden und : kann daher bei der Optimierung - entfernt werden l:... m:... : Wie findet man nun derartige überflüssige Berechnungen, toten Code oder andere überflüssige und somit zu eliminierende Anwei- sungen? Dazu erstellt man aus dem gegebenen Berechnungsgraphen zunächst einen Ablaufgraphen. Dieser stellt zur besseren Über- sicht eine Vereinfachung des Berechnungsgraphen dar. Seine Knoten bilden Basisblöcke und seine Kanten kennzeichnen mögliche Abfol- gen (analog zu t _seq im Berechnungsgraphen). Hat man nun diesen Ablaufgraphen aus dem Berechnungsgraphen konstruiert, so betreibt man nun ein wenig Datenflußanalyse. Das Ziel dieser Datenflußana- lyse ist es, zum einen überflüssige Berechnungen zu finden und zu eliminieren und zum anderen eine Konstantenweitergabe z u gewähr- leisten. Das bedeutet, man versucht, konkrete Werte von Variablen an Programmstellen zu bestimmen, die zur Übersetzungszeit bere- chenbar sind. 2. Schritt: Nachdem man die Eliminierung überflüssiger und toter Teilstücke beendet hat, wendet man sich nun der Schleifenoptimierung zu, da gerade hier die Probleme einer uneffizienten Programmausführung besonders schwer ins Gewicht fallen können. Was für Probleme kön- nen nun solche Schleifendurchläufe mit sich bringen? Als erstes wäre da der Fall zu nennen, daß innerhalb einer Programmschleife Codestücke existieren, die bei jedem Schleifendurchlauf die glei- che Wirkung haben. Daher wäre es sinnvoller, derartige Codestücke vor die Schleife zu verschieben. Deshalb spricht man bei diesem Vorgang auch von Code-Verschiebung. Einen weiteren Ansatzpunkt zur Optimierung bieten die zu einer Schleife gehörigen Induk- tionsvariablen (Laufvariablen). Bei Variablen, die sich linear von einem Durchlauf zum nächsten verändern, ist auf eine effi- ziente Fortschaltung zu achten. Bei FOR-Schleifen ist es zum Bei- spiel sinnvoller, Laufvariable durch entsprechende Inkre- ment-/Dekrement-Befehle linear fortzuschalten, anstatt Additions- -/Subtraktions-Befehle zu verwenden. Nachdem man nun die Durch- führung dieser beiden Schritte beendet und einen schon ziemlich optimalen Code erzeugt hat, wendet man sich nun im nächsten Schritt der sogenannten Nachoptimierung ("peephole"-Optimierung) zu. 3. Schritt: Ziel dieser "peephole"-Optimierung ist es, im Maschinencode kurze Folgen von Befehlen durch einzelne Befehle (zum Beispiel Spezial- befehle) zu ersetzen. Bei dieser Nachoptimierung bedient man sich eines "Fensters", das man über den Code schiebt und dabei nach bekannten Ersetzungsmustern sucht, bei denen ganze Befehlsgruppen zu - im Extremfall - einem einzigen Befehl zusammengefaßt werden können. Hat man derartige Muster gefunden, so wird eine Ersetzung durchgeführt. Beispiele für Ersetzungsmuster bei der "peephole"- Optimierung: Ersetzungsmuster neu eingesetztes Codestück 1. move Ri,a move a,Ri move Ri,a 2. move a,b add #c,b move b,a add #c,a 3. muls #2,a asl #1,a 4. move #0,a clr a Mit der nächsten Folge beenden wir unser Projekt PASCOMP. Die letzte Folge wird sich mit Erweiterungen zu unserem Compiler be- schäftigen und dem Leser an Beispielen zeigen, wie er eigene Pro- zeduren, Funktionen und Typen in die Compiler-Source einbauen kann. Weiterhin wird ein Programm vorgestellt werden, mit dessen Hilfe man in der Lage sein wird, P-Code in Assembler-Code des M68000-Prozessors zu übersetzen, um somit auch "Stand-alo- ne"-Programme zu erzeugen.