Ershov-Zahl

Ershov-Zahlen werden im Bereich der Informatik bei der Zuweisung von Registern benötigt. Sie sind nach dem russischen Informatiker Andrei Petrowitsch Jerschow benannt, der die Idee des Verfahrens zur Registerzuteilung publiziert hat. Das Verfahren geht auf die Hydrologen Robert Elmer Horton und Arthur Newell Strahler zurück, welche das Verfahren zur Berechnung der Flussordnungszahl eines Fließgewässerraumes entwickelten. Mit dem Verfahren kann nach Jerschow ebenfalls bestimmt werden, wie viele Register benötigt werden, um einen Ausdruck $a$ auszuwerten, und ermöglicht so die Auswertung großer Ausdrücke mit möglichst wenigen Registern.

Berechnung

Die Ershov-Zahl eines Binärbaumes berechnet sich wie folgt:

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

ershov(a_{1}\circ a_{2})={\begin{cases}max(ershov(a_{1}),ershov(a_{2}))&ershov(a_{1})\neq ershov(a_{2})\\ershov(a_{1})+1&ershov(a_{1})=ershov(a_{2})\end{cases}}

Herleitung der Berechnung

Das Verfahren spezifiziert eine Funktion der Form: $ershov:Ausdruck\rightarrow \mathbb {N}$ , die einem gegebenen arithmetischen Ausdruck $a$ die Anzahl der zur Auswertung benötigten Register angibt. Hierfür ist eine Fallunterscheidung notwendig:

Variablen und Konstanten

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

ershov(v)=1

Unäre Verknüpfung

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

$ershov(\alpha ~a)=ershov(a)$

Binäre Verknüpfung

Bei der Auswertung einer binären Verknüpfung zweier Ausdrücke der Form $a_{1}\circ a_{2}$ sind weiterhin drei Fälle zu unterscheiden:

Fall I: ershov(a₁) < ershov(a₂)

Angenommen, $a_{1}$ würde zuerst evaluiert, dann würde das Ergebnis in einem Register liegen und es wären noch $ershov(a_{2})$ weitere Register nötig, um $a_{2}$ zu evaluieren. Insgesamt wären also $ershov(a_{2})+1$ Register notwendig, um $ershov(a_{1}\circ a_{2})$ zu evaluieren.

Wird stattdessen $a_{2}$ zuerst evaluiert, so sind auch nur genau $ershov(a_{2})$ Register notwendig, um $ershov(a_{1}\circ a_{2})$ auszuwerten. Das Ergebnis von $a_{2}$ steht zwar in einem zusätzlichen Register, jedoch stehen alle anderen Register wieder für die Evaluation von $a_{1}$ zur Verfügung, weshalb zusätzlich zu diesem einen Ergebnisregister nur $ershov(a_{1})$ weitere Register notwendig sind. Da $ershov(a_{1})$ kleiner ist als $ershov(a_{2})$ , ist auch $ershov(a_{1})+1$ kleiner oder gleich $ershov(a_{2})$ , was offensichtlich auch kleiner ist als $ershov(a_{2})+1$ .

Demnach gilt:

ershov(a_{1})<ershov(a_{2})\Rightarrow ershov(a_{1}\circ a_{2})=ershov(a_{2})

Fall II: ershov(a₁) = ershov(a₂)

Es ist gleichgültig, welcher Ausdruck zuerst evaluiert wird, da beide Ausdrücke gleich viele Register benötigen. Beispielhaft kann daher zuerst der Ausdruck $a_{1}$ evaluiert werden, für den $ershov(a_{1})$ Register notwendig sind. Nach der Evaluation liegt das Ergebnis in einem Ergebnisregister und $ershov(a_{1})-1$ Register stehen nun für die Evaluation von $a_{2}$ zur Verfügung. Da die Evaluation des Ausdruckes ebenfalls $ershov(a_{1})$ beziehungsweise $ershov(a_{2})$ Register bedarf, werden, zusätzlich zum Register für das Ergebnis von $a_{1}$ , noch $ershov(a_{2})$ weitere Register, also insgesamt $ershov(a_{2})+1$ Register, für die Evaluation von $ershov(a_{1}\circ a_{2})$ benötigt.

Demnach gilt:

ershov(a_{1})=ershov(a_{2})\Rightarrow ershov(a_{1}\circ a_{2})=ershov(a_{1})+1

Fall III: ershov(a₁) > ershov(a₂)

Die Argumentation ist analog zu Fall I:

ershov(a_{1})>ershov(a_{2})\Rightarrow ershov(a_{1}\circ a_{2})=ershov(a_{1})

Verallgemeinerung auf Funktionsaufrufe

Ershov-Zahlen können auch auf Funktionsaufrufe 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 $f(a_{1},...,a_{n})$ 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:

ershov(f(a_{1},...,a_{n}))=max(ershov(a_{1}),...,ershov(a_{n}))

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 zuerst 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:

Minimum=max(ershov(a_{1}),...,ershov(a_{n}),\#ArgumenteInRegistern)

Wenn für mehr als ein Argument der Funktion 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:

Inkrement=\#\{a_{k}|ershov(a_{k})=Minimum\}

ershov(f(a_{1},...,a_{n}))={\begin{cases}Inkrement>1&Minimum+Inkrement-1\\Inkrement<2&Minimum\\\end{cases}}

Für gewöhnlich werden aber nur die ersten zum Beispiel 5 Argumente in Registern übergeben und die restlichen auf den Stack gelegt. Dann ist es sinnvoll, zuerst 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

Der Sethi-Ullman-Algorithmus, welcher nach Ravi Sethi and Jeffrey Ullman benannt ist, wandelt einen abstrakten Syntaxbaum in die Befehle einer Registermaschine wie beispielsweise Maschinencode um.^[1] 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

Die Berechnung der Ershov-Zahlen gestaltet sich je nach Befehlssatz anders. Im einfachsten Fall erlaubt der Befehlssatz nur Operationen mit Registern, womit Variablen und Konstanten erst in Register geladen werden müssen. In diesem Falle wird allen Blättern die Ershov-Zahl $ershov(a)=1$ zugewiesen. Wenn der Befehlssatz auch Operationen mit Variablen und Konstanten erlaubt, muss unterschieden werden, ob der Befehlssatz nur Befehle in der Zwei-Operanden-Form oder auch in der Drei-Operanden-Form erlaubt.

In der Zwei-Operanden-Form wird das Ergebnis in dem Register des ersten Operanden abgelegt. Ein Beispiel sei die Addition auf x86-Prozessoren:

  mov eax, a
  add eax, b ; eax + b → eax. eax ist zugleich ein Operand als auch das Ergebnisregister.

In diesem Falle kann einem rechten Blatt im abstrakten Syntaxbaum der Wert $ershov(r)=0$ zugewiesen werden, einem linken Blatt der Wert $ershov(l)=1$ . Im Beispiel ist b der rechte Operand, er muss nicht erst in ein Register geladen werden, und a der linke Operand. Dieser muss erst in ein Register eax geladen werden, damit $a+b$ berechnet und in eax abgelegt werden kann.

In der Drei-Operanden-Form ist der erste Operand das Ergebnisregister:

  add r1, a, b ; a + b → r1.

In diesem Falle wird jedem Blatt im abstrakten Syntaxbaum der Wert $ershov(a)=0$ zugewiesen.

Diese Darstellung der Berechnung ist jedoch idealisiert: Tatsächliche Prozessoren erlauben beispielsweise

nur Konstanten als direkte Operanden, aber keine Variablen oder umgekehrt.
Konstanten als Operanden nur dann, wenn sie in einem begrenzten Wertebereich, beispielsweise in $[-128,127]$ , liegen. Ansonsten müssen Konstanten erst in ein Register geladen werden, womit sich die Zahl der notwendigen Register und damit die Ershov-Zahl erhöht.
für einige Befehle die Drei-Operanden-Form, für andere jedoch nur die Zwei-Operanden-Form.
die Drei-Operanden-Form, aber der zweite Operand darf keine Konstante und/oder keine Variable sein. In diesem Fall verhält sich die Drei-Operanden-Form wie die Zwei-Operanden-Form.

Erzeugung des Codes

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, welches damit nicht mehr für die Berechnung des anderen Unterbaumes zur Verfügung steht. Bei einer begrenzten Zahl an Registern tritt unweigerlich die Situation auf, dass für die Berechnung eines Baumes nicht genügend Register zur Verfügung stehen. Die Zahl der notwendigen Register zur Berechnung eines Baumes ist nur dann größer als die Zahl der notwendigen Register der Unterbäume, wenn beide Unterbäume dieselbe Ershov-Zahl haben, beziehungsweise wenn beide Unterbäume gleich viele Register brauchen. Nur dann wird die Grenze der verfügbaren Register überschritten und das Zwischenergebnis eines Unterbaumes muss in einem Speicher, beispielsweise auf dem Stack oder in einer Red Zone, abgelegt werden, indem

erst der rechte Unterbaum ausgewertet,
ein Befehl zum Speichern des Zwischenergebnisses eingefügt,
dann der linke Unterbaum ausgewertet,
ein Befehl zum Laden des Zwischenergebnisses eingefügt und
schließlich der Befehl für die Verknüpfung der beiden Unterbäume eingefügt wird.

Die Reihenfolge ist eigentlich irrelevant, aber es kann von Vorteil sein, erst den rechten und dann den linken Unterbaum auszuwerten, wenn die Operation einen Wert im Speicher als rechten Operanden erlaubt. Dann können die letzten beiden Schritte zusammengefasst werden.

Einzelnachweise

↑ Sethi Ravi, Jeffrey D. Ullman: The Generation of Optimal Code for Arithmetic Expressions. In: Journal of the Association for Computing Machinery. Band 17, Nr. 4, 1970, S. 715–728, doi:10.1145/321607.321620.

[1] Sethi Ravi, Jeffrey D. Ullman: The Generation of Optimal Code for Arithmetic Expressions. In: Journal of the Association for Computing Machinery. Band 17, Nr. 4, 1970, S. 715–728, doi:10.1145/321607.321620.

[1]