Nachverfolgung der Just-in-Time-Zusammenstellung - Tracing just-in-time compilation

Die Verfolgung der Just-in-Time-Kompilierung ist eine Technik, die von virtuellen Maschinen verwendet wird , um die Ausführung eines Programms zur Laufzeit zu optimieren . Dies geschieht, indem eine lineare Abfolge häufig ausgeführter Operationen aufgezeichnet , zu nativem Maschinencode kompiliert und ausgeführt wird. Dies steht im Gegensatz zu herkömmlichen Just-in-Time (JIT)-Compilern, die pro Methode arbeiten.

Überblick

Die Just-in-Time-Kompilierung ist eine Technik, um die Ausführungsgeschwindigkeit von Programmen zu erhöhen, indem Teile eines Programms zur Laufzeit in Maschinencode kompiliert werden. Eine Möglichkeit, verschiedene JIT-Compiler zu kategorisieren, besteht in ihrem Kompilierungsumfang. Während methodenbasierte JIT-Compiler jeweils eine Methode in Maschinencode übersetzen, verwenden Tracing-JITs häufig ausgeführte Schleifen als Kompilierungseinheit. Tracing JITs auf den Annahmen , dass die Programme die meiste Zeit in einigen verbringen Schleifen des Programms ( „hot loops“) und nachfolgende Schleifendurchläufe nehmen oft ähnliche Wege. Virtuelle Maschinen mit Ablaufverfolgungs-JIT sind häufig Ausführungsumgebungen im gemischten Modus, was bedeutet, dass sie zusätzlich zum Ablaufverfolgungs-JIT entweder über einen Interpreter oder einen Methodencompiler verfügen.

Technische Details

Ein Tracing-JIT-Compiler durchläuft zur Laufzeit verschiedene Phasen. Zuerst werden Profiling- Informationen für Schleifen gesammelt. Nachdem eine heiße Schleife identifiziert wurde, wird eine spezielle Ablaufverfolgungsphase eingeleitet, die alle ausgeführten Operationen dieser Schleife aufzeichnet. Diese Folge von Operationen wird als Trace bezeichnet. Anschließend wird der Trace optimiert und zu Maschinencode übersetzt (Trace). Wenn diese Schleife erneut ausgeführt wird, wird anstelle des Programm-Gegenstücks der kompilierte Trace aufgerufen.

Diese Schritte werden im Folgenden im Detail erklärt:

Profiling-Phase

Das Ziel des Profilings besteht darin, Hot Loops zu identifizieren. Dies geschieht häufig durch Zählen der Anzahl der Iterationen für jede Schleife. Nachdem die Zählung einer Schleife einen bestimmten Schwellenwert überschreitet, wird die Schleife als heiß betrachtet und die Verfolgungsphase wird eingeleitet.

Tracing-Phase

In der Tracing-Phase läuft die Ausführung der Schleife normal ab, aber zusätzlich wird jede ausgeführte Operation in einem Trace aufgezeichnet. Die aufgezeichneten Operationen werden typischerweise im Trace-Tree gespeichert , oft in einer Zwischendarstellung (IR). Das Tracing folgt auf Funktionsaufrufe, was dazu führt, dass sie in den Trace eingebunden werden. Die Verfolgung wird fortgesetzt, bis die Schleife ihr Ende erreicht und zum Anfang zurückspringt.

Da die Ablaufverfolgung aufgezeichnet wird, indem einem konkreten Ausführungspfad der Schleife gefolgt wird, können spätere Ausführungen dieser Ablaufverfolgung von diesem Pfad abweichen. Um die Stellen zu identifizieren, an denen das passieren kann, werden spezielle Guard- Anweisungen in den Trace eingefügt. Ein Beispiel für einen solchen Ort sind if-Anweisungen. Die Wache ist eine schnelle Überprüfung, um festzustellen, ob der ursprüngliche Zustand noch zutrifft. Wenn ein Guard fehlschlägt, wird die Ausführung des Trace abgebrochen.

Da die Ablaufverfolgung während der Ausführung erfolgt, kann die Ablaufverfolgung so ausgeführt werden, dass sie Laufzeitinformationen enthält (zB Typinformationen ). Diese Informationen können später in der Optimierungsphase verwendet werden, um die Codeeffizienz zu erhöhen.

Optimierungs- und Codegenerierungsphase

Traces sind leicht zu optimieren, da sie nur einen Ausführungspfad darstellen, dh kein Kontrollfluss existiert und keine Behandlung benötigt wird. Typische Optimierungen umfassen Konstant subexpression Eliminierung , Beseitigung von totem Code , Registerzuweisung , invariant-Code Bewegung , konstantes Falten , und Escape - Analyse .

Nach der Optimierung wird der Trace in Maschinencode umgewandelt. Ähnlich wie bei der Optimierung ist dies aufgrund der linearen Natur der Spuren einfach.

Ausführung

Nachdem der Trace in Maschinencode kompiliert wurde, kann er in nachfolgenden Iterationen der Schleife ausgeführt werden. Die Traceausführung wird fortgesetzt, bis ein Guard fehlschlägt.

Geschichte

Während die Idee von JITs bis in die 1960er Jahre zurückreicht, werden Tracing-JITs erst in jüngerer Zeit häufiger verwendet. Die erste Erwähnung einer Idee, die der heutigen Idee der Verfolgung von JITs ähnelt, war 1970. Es wurde beobachtet, dass kompilierter Code zur Laufzeit von einem Interpreter abgeleitet werden konnte, indem einfach die während der Interpretation durchgeführten Aktionen gespeichert wurden.

Die erste Implementierung von Tracing ist Dynamo, "ein dynamisches Softwareoptimierungssystem, das in der Lage ist, die Leistung eines nativen Befehlsstroms transparent zu verbessern, während er auf dem Prozessor ausgeführt wird". Dazu wird der native Befehlsstrom interpretiert, bis eine "heiße" Befehlsfolge gefunden wird. Für diese Sequenz wird eine optimierte Version generiert, zwischengespeichert und ausgeführt.

Dynamo wurde später zu DynamoRIO erweitert . Ein auf DynamoRIO basierendes Projekt war ein Framework für die Interpreterkonstruktion, das Tracing und partielle Auswertung kombiniert. Es wurde verwendet, um "Interpreter-Overhead von Sprachimplementierungen dynamisch zu entfernen".

2006 wurde mit HotpathVM der erste Tracing-JIT-Compiler für eine Hochsprache entwickelt. Diese VM war in der Lage, häufig ausgeführte Bytecode-Anweisungen dynamisch zu identifizieren, die verfolgt und dann mithilfe von statischer Einzelzuweisung (SSA) in Maschinencode kompiliert werden . Die Motivation für HotpathVM war eine effiziente JVM für mobile Geräte mit eingeschränkten Ressourcen.

Ein weiteres Beispiel für ein Tracing-JIT ist TraceMonkey , eine von Mozillas JavaScript-Implementierungen für Firefox (2009). TraceMonkey kompiliert zur Laufzeit häufig ausgeführte Schleifenverfolgungen in der dynamischen Sprache JavaScript und spezialisiert den generierten Code für die tatsächlichen dynamischen Typen, die auf jedem Pfad vorkommen.

Ein weiteres Projekt, das Tracing-JITs verwendet, ist PyPy . Es ermöglicht die Verwendung von Tracing-JITs für Sprachimplementierungen, die mit der Übersetzungs-Toolchain von PyPy geschrieben wurden, und verbessert so die Leistung jedes Programms, das mit diesem Interpreter ausgeführt wird. Dies ist möglich, indem der Interpreter selbst verfolgt wird, anstatt das Programm, das vom Interpreter ausgeführt wird.

Tracing JITs wurden auch von Microsoft im SPUR-Projekt für ihre Common Intermediate Language (CIL) untersucht. SPUR ist ein generischer Tracer für CIL, der auch zum Tracen durch eine JavaScript-Implementierung verwendet werden kann.

Beispiel für eine Spur

Betrachten Sie das folgende Python-Programm, das eine Summe von Quadraten aufeinanderfolgender ganzer Zahlen berechnet, bis diese Summe 100000 überschreitet:

def square(x):
    return x * x

i = 0
y = 0
while True:
    y += square(i)
    if y > 100000:
        break
    i = i + 1

Ein Trace für dieses Programm könnte etwa so aussehen:

 loopstart(i1, y1)
 i2 = int_mul(i1, i1)		# x*x
 y2 = int_add(y1, i2)		# y += i*i
 b1 = int_gt(y2, 100000)
 guard_false(b1)
 i3 = int_add(i1, 1)		# i = i+1
 jump(i3, y2)

Beachten Sie, wie der Funktionsaufruf von squarein den Trace eingebunden wird und wie die if-Anweisung in eine guard_false.

Siehe auch

Verweise

Externe Links

Offizielle Website von LuaJIT

Languages

In other projects