Ershov-Zahl

aus Wikipedia, der freien Enzyklopädie
Wechseln zu: Navigation, Suche

Ershov-Zahlen werden im Bereich der Informatik bei der Zuweisung von Registern benötigt. Sie sind nach dem russischen Informatiker A.P. Ershov benannt, der die Idee des Verfahrens publiziert hat und geben an, wie viele Register benötigt werden um einen Ausdruck auszuwerten. Die Ershov-Zahl eines Binärbaumes berechnet sich wie folgt:

  1. Jedes Blatt hat den Wert (Konstanten oder Variablen).
  2. Jeder Knoten mit nur einem Unterknoten hat denselben Wert wie der Unterknoten (Unäre Operatoren).
  3. Für jeden anderen Knoten gilt

Herleitung der Berechnung[Bearbeiten | Quelltext bearbeiten]

Das Verfahren spezifiziert eine Funktion der Form: , die einem gegebenen arithmetischen Ausdruck die Anzahl der zur Auswertung benötigten Register angibt. Hierfür ist eine Fallunterscheidung notwendig:

Variablen und Konstanten[Bearbeiten | Quelltext bearbeiten]

Um eine Variable oder Konstante auszuwerten wird genau ein Register benötigt. Demnach gilt:

Unärer Verknüpfung[Bearbeiten | Quelltext bearbeiten]

Zur Auswertung eines unären Operators auf einen Ausdruck wird lediglich die Anzahl der Register benötigt, die braucht, denn das Ergebnisregister von kann einfach überschrieben werden.

Binärer Verknüpfung[Bearbeiten | Quelltext bearbeiten]

Bei der Auswertung einer binären Verknüpfung zweier Ausdrücke der Form sind weiterhin drei Fälle zu unterscheiden:

Fall I: [Bearbeiten | Quelltext bearbeiten]

In diesem Fall wird evaluiert, wobei Register benötigt werden. Das Ergebnis kann nun in einem Register gespeichert werden. Die restlichen Register werden nun nicht mehr für benötigt, wodurch sie für die Berechnung von zur Verfügung stehen. Demnach gilt:

Fall II: [Bearbeiten | Quelltext bearbeiten]

Für die Berechnung von werden in diesem Fall Register benötigt. Angenommen, hierfür wurden Register benötigt, dann steht in Register das Ergebnis von . Für die Berechnung von stehen nun nicht mehr benötigte Register zur Verfügung. Da aber für die Berechnung von ebenfalls Register benötigt werden, gilt:

Fall III: [Bearbeiten | Quelltext bearbeiten]

Die Argumentation ist analog zu Fall I:

Verallgemeinerung auf Funktionsaufrufe[Bearbeiten | Quelltext bearbeiten]

Ershov-Zahlen können auch auf Funktionsaufrufen ausgeweitet werden. Die Berechnungen für unäre und binäre Verknüpfungen können sogar als Spezialfälle von Funktionsaufrufen gesehen werden.

Wenn die Argumente eines Funktionsaufrufes auf den Stack geschrieben werden, ist es nicht notwendig, das Ergebnis auch noch in einem Register abzuspeichern. Aus derselben Argumentation wie in Fall I für binäre Ausdrücke folgt:

Es gibt aber auch Aufrufkonventionen, bei denen Argumente über bestimmte Register übergeben werden, was die Geschwindigkeit von Funktionen verbessern kann. Hier gilt wie für binäre Operatoren, welche ein Spezialfall von Funktionsaufrufen mit zwei Argumenten in Registern sind, dass die Argumente mit der höchsten Ershov-Zahl zu erst berechnet werden, damit für diese möglichst viele Register zur Verfügung stehen. Da alle Argumente schließlich in Register geschrieben werden müssen, ist die Ershov-Zahl des Funktionsaufrufes mindestens so groß wie die Anzahl der Argumente in Registern:

Wenn mehr als für ein Argument die Ershov-Zahl gleich diesem Minimum ist, dann gilt, ebenfalls analog zu binären Operatoren, dass sich die Ershov-Zahl des Funktionsaufrufes für jedes weitere solche Argument um Eins erhöht:

Für gewöhnlich werden aber nur die ersten z. B. 5 Argumente in Registern übergeben und die restlichen auf dem Stack gelegt. Dann ist es sinnvoll zu erst die letzten Argumente zu berechnen und auf den Stack zu legen, damit für die Berechnung der ersten Argumente alle Register verwendet werden können. Während die Argumente in Registern in beliebiger Reihenfolge berechnet werden können, müssen die Argumente auf dem Stack in der logischen Reihenfolge liegen.

Sethi–Ullman-Algorithmus[Bearbeiten | Quelltext bearbeiten]

Der Sethi–Ullman-Algorithmus, welcher nach Ravi Sethi and Jeffrey Ullman benannt ist, wandelt einen abstrakten Synthaxbaum in die Befehle einer Registermaschine wie beispielsweise Maschinencode um. Der Algorithmus ist im Prinzip derselbe wie zur Berechnung der Ershov-Zahlen, berücksichtigt aber einige Eigenschaften von Befehlen realer Registermaschinen. So erlaubt der Befehlssatz von x86-Prozessoren die direkte Verwendung von Konstanten und Werten im Speicher als Argumente. Es sind jedoch nicht alle Kombinationen erlaubt. Erlaubt sind:

  add dword [ a ], 0x1337      ; Konstanten können direkt zu Variablen im RAM addiert werden.
  add eax,         0x2342      ; Konstanten können direkt zu Registern addiert werden.
  mov eax,         dword [ a ]
  add dword [ b ], eax         ; Register können direkt zu Variablen addiert werden.
  add eax,         dword [ c ] ; Variablen können direkt zu Registern addiert werden.

Berechnung der Ershov-Zahlen[Bearbeiten | Quelltext bearbeiten]

Ein rechtes Blatt im abstrakten Syntaxbaum hat damit immer den Wert . Ein linkes Blatt hat den Wert für eine Variable und für eine Konstante. Der Wert für Knoten errechnet sich wie die Ershov-Zahl von Knoten:

Erzeugung des Codes[Bearbeiten | Quelltext bearbeiten]

Anschließend wird der Baum in Nebenreihenfolge traversiert, wobei erst der Unterbaum mit der höchsten Ershov-Zahl ausgewertet wird. Würde stattdessen der Unterbaum mit der niedrigsten Ershov-Zahl ausgewertet, so muss das Ergebnis in einem Register gespeichert werden und steht damit nicht mehr für die Berechnung des anderen Unterbaumes zur Verfügung. Wenn nicht genügen Register für die vollständige Auswertung des Baumes zur Verfügung stehen wird

  1. erst der Unterbaum mit der höchsten Ershov-Zahl ausgewertet,
  2. ein Befehl zum Speichern des Zwischenergebnisses eingefügt,
  3. dann der zweite Unterbaum ausgewertet,
  4. ein Befehl zum Laden des Zwischenergebnisses eingefügt und
  5. schließlich der Befehl für die Verknüpfung der beiden Unterbäume eingefügt.