SSA-Darstellung des Aktualisierens einer Variablen im umschließenden Gültigkeitsbereich

Question

Wenn ein Compiler das SSA-Formular zum Darstellen von Code verwendet, werden Updates für lokale Variablen zu neuen Variablen. Dies funktioniert jedoch nicht immer dann, wenn die Variable in einem umschließenden Bereich vorliegt, z. (Unter Verwendung von JavaScript-Syntax für Illustration, könnte die Situation in vielen Sprachen auftreten):

function f() { 
    var x = 1; 
    function g() { 
     x++; 
    } 
    ... 
} 

Was ist der üblicher Weg, dies zu vertreten?

Answer 1

Eine veränderbare freie Variable, die in einem Closure verwendet wird (in Ihrem Beispiel x), muss implizit "eingerahmt" werden.

Es gibt zwei Punkte zu beachten. Erstens, Lebensdauer: Die Variable könnte den Gültigkeitsbereich überschreiten, in dem sie erstellt wurde. (f könnte g zurückgeben oder in einem persistenten Container speichern.) Zweitens, Freigabe: Die Variable kann durch f, g oder jede andere von f erstellte Funktion geändert werden.

Die einfachste Lösung besteht darin, die Variable in eine "Box" (einen Container mit einem Objekt, der den Wert der Variablen darstellt) zu ändern. Die Box selbst ist unveränderlich (dh der Name bezieht sich immer auf die gleiche Box). Änderung von und Referenz auf den Wert der Variablen werden Container-Setter-und Getter-Methoden. Natürlich muss der Speicher für den Wert dynamisch zugewiesen und zurückgewonnen werden, wenn er nicht mehr benötigt wird (wie bei jedem Container).

In einigen Fällen gibt es Optimierungen - möglicherweise sogar in den meisten Fällen.

Erstens, wenn die Variable nie geändert wird, kann es möglich sein, jedem Abschluss eine Kopie des Werts zu geben, anstatt den Wert einzubetten.

Zweitens, wenn die Variable unshared ist - es nicht von einer anderen Funktion erstellt durch die Ausführung von f geschlossen ist, und es ist nicht von f nach der Gründung von g verwiesen - die Variable einfach in g bewegt werden kann " s Schließung.

Tatsächlich wird in beiden Fällen der Verschluss selbst zur Box, aber dies hat den Vorteil, dass keine separate dynamische Zuordnung erforderlich ist.

Das Überprüfen der Gültigkeit dieser Optimierungen in einem bestimmten Programm erfordert eine gute statische Analyse. Die erste ist einfach, da die Modifikation syntaktisch leicht zu erkennen ist, aber die zweite erfordert eine Flussanalyse (zumindest).

In den obigen, habe ich eine konservative Beschreibung der Umstände verwendet, in denen die Optimierung angewendet werden könnte, die nur einfache Flussanalyse erfordert; das Erkennen anderer möglicher Anwendungen ist komplizierter.