Code-Optimierer für CP/M-80 Turbo 3.0

'Bringt der Turbo nichts mehr, dann muß der Kompressor her'. Ein Code-Optimierer für Turbo-Pascal 3.0 soll hier vorgestellt werden.

Eins vorweg: dieses Programm eignet sich ausschließlich nur für den Z80-Mikroprozessor, also nicht für den IBM-PC und zu diesem funktionsgleiche Rechner.

So, nach dem die Z80-Fans unter sich sind, stellen sich so alles entscheidene Fragen wie: Optimieren ? Was ? Wie ? -und überhaupt- warum ?

Die letzte Frage ist schnell geklärt. Da wäre der Grund zu nennen, daß einem das Programm zu langsam ist, oder das Programm ist einem viel zu lang. Der letztere Grund tritt allerdings in Zeiten, in denen man im Kaufhaus gleich nebenan einen Computer mit 1 Megabyte erstehen kann, zunehmend im Hintergrund, aber davon können Z80 Benutzer nur träumen.

Kommt die Frage nach dem Was. Als klassisches Beispiel wird meistens das Beispiel von der Wertzuweisung einer Variablen vor bzw. in einer Schleife gebracht, so auch hier. Zum Beispiel WHILE Irgendwas DO K:=Wert ... (K bleibt unverändert). Hier sollte der Ausdruck K:=Wert eben vor WHILE stehen.

Oder noch so ein tolles Beispiel: IF (A=B) AND (A<>B) THEN WRITE('Künstliche Intelligenz'). Ist die erste Aussage vor AND bereits falsch, dann sollte man meinen, der zweite würde nicht mehr behandelt. Denkste, Turbo machts doch. Warum, das wissen nur die Macher von Mr. Borland (Macher bezieht die Macherinnen natürlich mit ein). Ferner erwartet man doch eigentlich, daß bei einem so unlogischen Ausdruck der Intelligenzverstärker oder wie man die Rechner heute sonst noch so nennt (übringens sollen wissenschaftliche Untersuchungen ergeben haben, daß dem Computerbenutzter eine gewisse Intelligenz nicht abzuerkennen ist, was natürlich Blödsinn ist und darum vom Großteil der Computerindustrie heftig dementiert wird) jede Menge Warnungen an den Kopf knallt. Derjenige, der das programmiert hat, ist letztlich nicht doof; er hat in der Hektik lediglich einen Tippfehler gemacht. Ungezählt sind die Stunden der Fehlersuche nach solchen Bugs.

Turbo Pascal und auch dieser Code-Optimierer können solche feine Sachen nicht machen. Man muß allerdings gerechterweise dazu sagen, daß für solche Optimierungen mehrere Duchläufe erforderlich sind, und Turbo Pascal ist nun mal ein 1-Pass-Compiler.

Wie nicht schwer zu erraten ist, wird hier der Maschinencode optimiert, wozu heißt schließlich der Code-Optimierer auch so. Bei der Betrachtung des Pascalprogramms Unsinn und den dazu gehörigen Code läuft es einem kalt den Rücken hinunter und heiß den Bauch wieder rauf. Hat man doch früher als Assembler-Programmierer seinen ganzen Bekanntenkreis mit Freudesausstössen zum Wahnsinn getrieben, bloß weil man einen Trick erforscht hat, der ein Byte spart- und was macht Turbo ? Der generiert seinen Maschinencode so, wie es gerade kommt. Abhilfe soll eben dieser Optimierer schaffen.

Ist das GOTO in Pascal verpönt, so macht die CPU um so mehr wilde SprUnge im erzeugten Maschinencode. Wird nun dieser Code optimiert, das heißt, der Umfang reduziert, dann können unmöglich die Adressen noch stimmen, zu denen das Originalprogramm springen wollte. Aus eben diesem guten und einen weiteren wichtigen Grund wird, bevor überhaupt irgendwas verändert wird, zunächst eine Liste der Ansprungstellen angelegt, dies ist der Pass 1, gesteuert mit der Variablen PASS. Die Marken oder Labels, je nach Geschmack, werden dabei, um die Ausführungszeit nicht total in den Keller abrutschen zu lassen, in einem Binärbaum abgelegt, wobei der Zeiger SPRUNGTAB auf den Anfang dieser Liste zeigt, genannt auch Wurzel des Binärbaums.

Der Optimierer macht nun folgendes: Einlesen des Original-Maschinencodes, diesen ein bißchen untersuchen und das Ergebnis all dieser Bemühungen auf eine andere Datei namens 'OPT.COM' bzw. 'OPT.CHN' schreiben. Damit gehört das Programm in die Kategorie der Filterprogramme (warum diese Dinger so heißen ist mir ein Rätsel: schüttet man in eine Kaffeemaschine oben Kaffee hinein, dann kommt unten Kaffee heraus, obwohl doch Tee gesünder sein soll). Bevor über das 'Wie geht das denn ?' hergefallen wird, einige Worte zur Codegenerierung von Turbo Pascal:

Turbo-Pascal ist wie andere Pascal-Compiler auch, wie zum Beispiel der MT+ Compiler, wortorientiert, will heißen, 16-Bit Daten und Adressen sind der Normalfall.

Arithmetische Operationen werden über den Stack ausgeführt. Dabei stellt das Registerpaar HL sozusagen den Schwanz des Stacks dar, in dem immer der letzte Faktor seinen Platz findet. Das ist in etwa das gleiche Verfahren, das Hewlett-Packard bei seinen Taschenrechnern anwendet. Dummerweise kann die Z80-Cpu keine Operationen direkt auf dem Stack ausführen. Also wird der zweite Faktor via POP DE ins DE-Registerpaar geladen.

Anhand der letzten Befehle wird untersucht, ob eine Anweisung oder gar mehrere überflüssig sind oder zumindest einer Änderung bedürfen.

Um eben diese Untersuchung überhaupt erst zu ermöglichen, werden alle Bytes, die an die optimierte Datei gehen, erst mal zwischengespeichert. Im Programm sind das die Variablen OPTBUFFER und BUF. 'Was soll der Unsinn mit zwei verschiedenen Buffern ', fragen da Ungeduldige. OPTBUFFER enthält nur den Maschinencode, der, droht ein Überlaufen desselben, auf Diskette geschrieben wird, mit Ausnahme der letzten 128 Bytes, denn diese werden ja eventuell noch geändert.

Man kann sehr schlecht direkt Informationen aus diesen Buffer gewinnen, da die Cpu-Befehle unterschiedlich lang sind (von 1 bis 4 Bytes), es werden jedoch sehr oft Informationen über die letzten CPU-Befehle und ihre Parameter benötigt. Diese (die Informationen) werden darum in BUF niedergelegt.

Die Hierarchie sieht bei diesen Buffern so aus: alle Prozeduren dürfen den Inhalt von BUF lesen und auswerten, aber auf keinen Fall verändern. Manipulationen der letzten Befehle wie zum Beispiel Löschen dürfen nur die Prozeduren PUTCODE, DELCODE und INSCODE vornehmen, da in BUF noch andere Informationen wie die genaue Lage der Daten im OPTBUFFER enthalten sind. Auf den OPTBUFFER dürfen nur die drei letzt genannten Prozeduren zugreifen.

Mit diesen Prozeduren steht bereits so ziemlich alles zur Verfügung, was zum Untersuchen und Manipulieren nötigt ist. Mit den beiden Buffern wird wie in Georg Orwell's Roman >1984< dauernd die Vergangenheit an die Gegenwart angepasst, der Code-Optimierer übernimmt hier eifrig die Rolle des 'Wahrheitsministeriums'.

Die Kontrolle des ganzen Ablaufs obliegt der Procedure OPTIMIERER, die je nach anliegen des Original-Maschinencodes die entsprechenden Prozeduren aufruft.

Es soll einmal diese Anweisungsfolge untersucht werden:
I:=0; REPEAT K:=I; ... UNTIL ...
Mal angenommen, es wird die Anweisung K:=I untersucht, Turbo macht daraus LD HL,(I) und LD (K),HL, völlig korrekt. Eine Untersuchung von BUF zeigt, daß als letzter Befehl LD (I),HL gespeichert wurde, was ebenfalls korrekt ist. Also kann doch das LD HL,(I) aus dem Buffer wieder entfernt werden. Mitnichten, denn diese Anweisung steht Ja innerhalb einer Schleife. Da war doch irgendwas mit einem weiteren wichtigen Grund bei den Aufstellen der Tabelle mit den Sprungmarken. Eben, diese Liste braucht nur durchgeforstet zu werden, ob nicht die zu untersuchende Ladeanweisung eine Sprungmarke ist. Ist dies der Fall, wie bei diesem Beispiel, dann darf die Anweisung nicht entfernt werden. Das erledigt die Funktion MARKE, sie liefert einen Zeiger auf den Eintrag der Sprungmarke, der NIL ist, wenn die an dieser Funktion übergebene Adresse nicht in der Liste enthalten ist.

Geklärt werden muß noch, was denn überhaupt einer näheren Untersuchung wert ist. Ich möchte das in vier Gruppen einteilen:

Wenn sich der entsprechende Wert noch im Register befindet, dann diesen Befehl ersatzlos streichen. Bei POP DE prüfen, ob nicht das DE-Registerpaar ohne Umweg über den Stack geladen werden kann. Entweder mit LD DE,(Variable) oder mit EX DE,HL.

Untersucht werden nur Operationen mit Integerausdrücken.

Man glaubt es kaum, aber es ist wahr, Turbo berechnet einen Ausdruck like this (damit sind meine Englischkenntnisse erschöpft) I:=5+3 erst während der Programmausführung. So etwas wird natürlich nicht geduldet, also wird dieser Ausdruck flugs berechnet und das Ergebnis ins HL-Register gepackt.

Falls die Konstante innerhalb eines Wertebereichs liegt, dann werden die Operationen durch einfachere ersetzt. Wie zum Beispiel I:=K+1, hier wird die Addition durch ein schlichtes INC HL ersetzt, was Speicher und jede Menge Rechenzeit spart.

Das klappt aber nur dann, wenn diese Operationen nicht zu Vergleichszwecken mißbraucht werden. Das ist bei der CASE-Anweisung der Fall. Im Register HL befindet sich dann, ich sags mal wie die Leute von Heimsoeth (das Handbuch aus deren Feder ist spitze), der Sortierer, und im Register DE der Wert des Case-Labels, der ja eine Konstante ist. Diese beiden Register werden voneinander subtrahiert, zwecks Feststellung, ob der Sortierer den Wert vom Case-Label besitzt. Wenn nein, dann werden die folgenden Anweisungen schnell übersprungen und mit ADD HL,DE der ursprüngliche Wert des Sortierers wieder hergestellt.

Logisch, daß der Code-Optimierer da seine Pfoten von lassen soll, was er dann auch untertänigst tut.

Eigentlich gehören sie ja noch zu den letzt genannten, aber sie werden trotzdem extra behandelt.

Es soll mit Wonne folgender Ausdruck betrachtet werden: IF (A=B) AND (A<C) THEN MacheWas.. Turbo untersucht den ersten Term (A=B) und packt ihn erst mal auf den Stack, um dann den zweiten Term durchzunudeln, und als letzte Anweisungen als Maschinencode findet man dann dies vor: AND A; LD L,A; BIT 0,L. Findige Assembler-Freaks stellen da mit Begeisterung fest, daß die beiden letzten Anweisungen total überflüssig sind, weshalb sie (die letzten Anweisungen) dann auch aus dem ewig knappen Arbeitsspeicher hinaus geworfen werden.

Tests auf Gleich-und Ungleichheit: Wird im Anschluß dieser Vergleichsoperationen verzweigt, dann ersetzt der Optimierer den entsprechenden Unterprogrammaufruf mit OR A; SBC HL,DE, was nicht nur zwei Bytes spart, sondern vor allem die so kostbare Rechenzeit. Mit solchen Ausdrücken wie IF A=10 THEN ... klappt das ganz prima, aber man darf sich nicht den Optimierungsrausch hingeben und meinen, diese tolle Vereinfachung könne man dann ja auch bei IF A<10 machen. Ist nicht, denn hierbei legt sich das Vorzeichen mächtig quer.

Als letzte Gruppe kommt das, womit begonnen wurde, nämlich die Sprünge und die Calls. Hierbei gibt es drei verschiedene Arten von Verzweigungen:

• Sprung außerhalb des betrachteten Bereichs, wie Aufrufe des Laufzeitsystems. Diese brauchen, wie praktisch, nicht behandelt zu werden.
• Sprung nach hinten, will heißen zu kleineren Adressen als der momentane Programmzähler. Hierbei wird die neue Zieladresse aus dem anfangs angelegten Binärbaum gepflückt.
• Sprung nach vorne. So einfach wie bei den obigen Sprüngen geht es hier nicht mehr zu, denn die Zieladresse ist ja noch gar nicht bekannt, da sich die ursprüngliche Adresse im Zuge der weiteren Untersuchungen ja hoffentlich noch ändert. Macht nichts, der Optimierer merkt sich diese Stelle einfach. Dazu wird der aktuelle Programmzähler mit einen Verweis auf den entsprechenden Eintrag zur Sprungliste in die Liste mit den Zeiger SPRUNGVORTAB eingetragen. Weil diese Adressen sequentiell anfallen, hat diese Liste eine FIFO (First-In First-Out) Struktur. Nach Abschluß der Optimierung werden diese Adressen in die optimierte Datei eingetragen.

Bei den beiden letzten Arten wird außerdem untersucht, ob sich nicht der absolute Sprung (Turbo verwendet nur absolute Sprünge) durch einen relativen Sprung ersetzen läßt (Noch'n Byte abgeknapst).

Der Optimierer versucht das Beste aus den vorliegenden Maschinencode zu machen, abe ohne den Zusammenhang mit den Quelltext des Pascalprogramms zu kennen. Ist weiter auch nicht schlimm, gäbe es nicht da einige schöne Sachen, mit denen Turbo aufzuwarten hat, insbesondere die typisierten Konstanten und den INLINE-Maschinencode.

Der Codegenerator von Turbo verwendet nur einen Teil des Z80-Befehlssatzes, und eben dieser wird auch nur vom Code-Optimierer untersucht. Ebenfalls erwartet der Optimierer eine bestimmte Art des Maschinencodes. Bei den typisierten Konstanten liegen die Anfangswerte dieser eigentlichen Variablen mitten im Programmcode, der Optimierer kann daher nicht zwischen diesen Werten und den tatsächlichen Maschinencode unterscheiden, außerdem wird sich die Adressenlage dieser Variablen ändern.

Typisierte Konstanten und Prozeduren/Funktionen mit INLINE-Maschinencode sollten deshalb am Anfang des Pascalprogramms placiert werden. Durch Angabe der Adresse der ersten Prozedur oder Funktion des zu optimierenden Programms wird der Optimierungsvorgang erst an dieser Stelle begonnen, womit die Schwierigkeiten beseitigt wären.

An dieser Adresse kommt man durch das folgende und lästige Verfahren:

Hinter dem ersten BEGIN im Hauptprogramm des zu optimierenden Programms einfügen: WRITE(ADDR(Procedure)); HALT;. Nachdem das so verunstaltete Programm gestartet und die Adresse notiert wurde, füttert man dann damit den Optimierer. Bitte nicht vergessen, vorher den Com-Modus im O-Menü von Turbo Pascal zu wählen. Danach wirft man diese Anweisungen wieder aus dem Programm hinaus.

Wahnsinnig umständlich, aber mir ist keine andere Lösung eingefallen.

Die größten Einsparungen an Maschinencode und Rechenzeit werden bei solchen Programmen erzielt, in denen viele kleinere Schleifen, eindimensionale Felder und vorwiegend Integerausdrucke auftreten. Bei dem Programm Prime, das besonders oft als Testprogramm zur Ausführungszeitermittlung von Compilern verwendet wird, schlägt der Code-Optimierer demzufolge voll zu. Was auch beweist, daß solche Testprogramme völlig ungeeignet zur Leistungsbeurteilung von Compilern sind. Hingegen lohnt es sich kaum, eine Optimierung bei Programmen vorzunehmen, die vorwiegend Realzahlen verwenden oder häufig auf Massenspeichern zugreifen.

'Ein fehlerfrei laufendes Programm muß schwerwiegende Fehler enthalten', wußte schon Murphy zu berichten (Das ist der mit den Gesetzen).

Zunächst zu den harmlosen Fehlermeldungen. Der Originalcode darf nie größer sein als 32 KBytes. Aufheben kann man diese Beschränkung, indem alle Vergleiche wie '<' und '>' durch entsprechende Funktionen ersetzt werden, die die Argumente vorzeichenlos vergleichen.

Overlays und Quelldateien mit einer anderen Dateigruppenbezeichnung als 'Com' beziehungsweise 'Chn' weist der Optimierer mit einer frechen Fehlermeldung zurück.

Wie gesagt, der Code-Optimierer untersucht nur die auch vom Codegenerator erzeugten Maschinenbefehle. Bei Auftreten eines unbekannten Codes folgt die Meldung 'Unbekannter OpCode' zusammen mit zwei Programmzählern. Mit Turbo und der Option 'Find Run-Time Error' kann nach Eingabe des ersten Programmzählers die Stelle im Programmtext aufgesucht werden, die diesen Fehler verursacht hat. Den zweiten Programmzähler kann man zusammen mit einem Debugger verwenden.

Da gibt es noch die Fehlermeldung 'Fehler im Optimierer...'. Hier gilt gleiche wie vorhin.

Normalerweise sollte der entsprechende Fehler entweder an einer typisierten Konstante oder im INLINE-Code liegen. Wenn nicht, dann arbeitet der Code-Optimierer fehlerhaft.

Der Super-GAF (größter anzunehmender Fehler) tritt allerdings dann auf, wenn sich der Optimierer mit einem Happy-End verabschiedet hat, daß Produkt der Bemühungen aber nicht korrekt ist.

In den beiden letzten Fällen (bitte auch nur dann) kann, wer will, mir den Teil des zu optimierenden Programms zusenden, in dem der Fehler auftrat.

Auch ohne diesen Optimierer können durch entsprechende Maßnahmen Verbesserungen der Effizienz erzielt werden.

• Den Indextyp eines Feldes möglichst mit null beginnen lassen, auch wenn dieses Element nicht benötigt wird. Beispiel: Feld : Array[0..10] of Irgendwas ist günstiger als ..Array [1..10] ..
• Verzichten auf Variablen vom Type Byte. Diese sparen lediglich ein Byte im Variablenbereich, erzeugen aber zusätzlichen Code im Programmbereich, der um ein vielfaches höher ist als ein Byte.
• Beim CASE-Statement die Reihenfolge der Case-Marken nach der Wahrscheinlichkeit ihres Zutreffens ordnen.

Mit Versuchen und Probieren findet man vielleicht noch weitere lohnende Maßnahmen heraus.

Ausführungszeiten einiger Beispielprogramme: