Code Profiling mit LLVM

Der Fluch des Nichtdeterminismus

Mein erster Versuch, eine LLVM-Passage zu schreiben - ich liebe diese Segfolty

Kürzlich stieß ich auf ein interessantes Problem: Ich brauchte eine deterministische und plattformübergreifende Methode, um die Laufzeit von C ++ - Code zu bestimmen. Mit dem Wort "deterministisch" meine ich, dass derselbe Code für die gleiche Anzahl von Zeiteinheiten ausgeführt wird. Unter plattformübergreifend verstehe ich, dass derselbe Code unter Windows und unter Ubuntu für die gleiche Anzahl von Zeiteinheiten ausgeführt wird.

Das Messen der Zeit auf der CPU erfüllt diese Bedingungen natürlich nicht. Der Maschinencode variiert je nach Architektur und Betriebssystem, und die Ausführung desselben Codes dauert unterschiedlich lange. Selbst auf demselben Computer spielen Faktoren wie Cache-Fehler eine große Rolle - genug, um die Messergebnisse der Ausführungszeit desselben Codes zu verzerren. Ich brauchte etwas Klügeres ...

Motivation

Ich bin auf dieses Problem gestoßen, als ich an meinem Projekt Code Character gearbeitet habe. Code Character ist ein Online-KI-Wettbewerb, bei dem die Teilnehmer Bots schreiben, um eine Armee in einer rundenbasierten Strategie zu kontrollieren. Ich wollte die Menge an Code begrenzen, die ein Teilnehmer in einem Zug ausführen kann.

Mein erster Gedanke war einfach, die Ausführungszeit des Codes zu messen, aber wie wir sehen können, ist diese Strategie nicht deterministisch, und der Teilnehmer, der denselben Code zweimal gesendet hat, erhält völlig unterschiedliche Ergebnisse. Tatsächlich haben wir versucht, diese Lösung zu implementieren, und die Ergebnisse ändern sich so stark, dass ein Teilnehmer mit demselben Code gewinnen oder verlieren kann. Das Ergebnis wird völlig zufällig sein, und wir haben die Idee der Zeitmessung verworfen.

LLVM-Bytecode

Da wir die Zeit nicht messen können, haben wir uns stattdessen entschieden, die Anzahl der ausgeführten Anweisungen zu messen. Daher müssen wir den Teilnehmercode instrumentieren. Wenn Sie mit diesem Begriff nicht vertraut sind, wird der Anwendung Code hinzugefügt, um einige Parameter zu überwachen, z. B. die CPU-Auslastung oder die Laufzeit. Wir erwarten natürlich nicht, dass die Teilnehmer dies selbst tun, wir müssen den Prozess automatisieren.

Wir wollten Overhead-Kosten für Laufzeit-Tools vermeiden, wenn wir auf unserem Server arbeiten. Daher ist so etwas wie ein PIN- Tool für unsere Zwecke nicht geeignet. Stattdessen haben wir beschlossen, den Teilnehmercode direkt anzuweisen, um die Anzahl der ausgeführten Anweisungen zu zählen. Anstatt Binärdateien (Maschinencode) zu instrumentieren, haben wir uns entschieden, Clang zum Kompilieren des Codes und des Instrumenten-LLVM-Bytecodes zu verwenden.

Wenn Sie LLVM noch nicht kennen, handelt es sich um eine Sammlung modularer und wiederverwendbarer Compiler- und Toolchain-Technologien. Eines der Hauptprojekte ist LLVM IR und Backend. In einfachen Worten wurde eine Zwischenrepräsentation entwickelt, in die ein kompilierendes Frontend Code kompiliert. Dieser Code, LLVM IR, wird dann vom LLVM-Backend in Maschinencode kompiliert. Wenn Sie also eine neue Sprache erstellen, können Sie festlegen, dass LLVM die Generierung und Optimierung von Maschinencode unterstützt, und ein Frontend schreiben, um Ihre Sprache in LLVM IR zu konvertieren.


Clang konvertiert C ++ - Code in LLVM-IR, das dann vom LLVM-Backend in Maschinencode konvertiert wird.

Clang ist das Frontend von LLVM. Da wir eine plattformübergreifende Methode zum Messen von Code benötigen, können wir keinen Binärcode instrumentieren. LLVM IR ist jedoch plattformunabhängig, da es sich nur um eine Zwischendarstellung des Codes handelt. Das Instrumentieren von IR-Code mit LLVM-Bibliotheken ist eine einfache plattformübergreifende Lösung.

Lösung

Eine einfache Anzahl von LLVM-IR-Befehlen ist offensichtlich nicht geeignet, da wir die Anzahl der Befehle benötigen, die tatsächlich ausgeführt werden, und nicht nur die Anzahl der Befehle im Code. Am Ende haben wir einen einfachen Algorithmus entwickelt, der auf dem Konzept der grundlegenden Codeblöcke basiert.

Eine Basiseinheit ist ein Befehlssatz, bei dem nur der erste Befehl der Eingabepunkt und nur der letzte Befehl der Ausgabepunkt sein kann. ( Übergänge innerhalb des Basisblocks sind ebenfalls verboten - ungefähr übersetzt. ) Um dies zu verstehen, versuchen Sie, den Code in Teile zu unterteilen, in denen Verzweigungsbefehle (Übergänge, Schleifen und Rückgaben) nur die letzten im Satz und die Eingabe in den Block (erste Anweisung in) sein können Funktion, Schleife oder if / else-Block) ist nur bei der ersten Anweisung möglich. Das Ergebnis ist eine Reihe von Basisblöcken - Blöcke aus sequentiellem Code, die einfach sequentiell ausgeführt werden, ohne zu entscheiden, welche Anweisung als nächstes ausgeführt werden soll.

Warum versuchen wir es jetzt nicht? Dies ist ein Codeausschnitt, der von einem Codezeichen-Mitwirkenden bereitgestellt wird:

// Make the soldiers who aren't patrolling attack the enemy for (int i = NUM_SOLDIERS / 2; i < NUM_SOLDIERS; ++i) { auto &soldier = state.soldiers[i]; if (soldier.hp == 0) // If this soldier is dead, skip it continue; for (auto enemy_soldier : state.enemy_soldiers) { if (enemy_soldier.hp != 0) { // Ensure your prospective target has // not already been slain soldier.soldier_target = enemy_soldier.id; break; } } } 

Github-Link: https://gist.github.com/JHurricane96/8c9c3a45ec5e969de4d9fecb47ebef69#file-player_code-cpp

Unter Verwendung der Tatsache, dass die Basiseinheit nur einen Eingabepunkt hat (die erste Anweisung), können wir dieses Fragment in die folgenden Basiseinheiten unterteilen:

 //-------------------------------- BB 1 ---------------------------------- for (int i = NUM_SOLDIERS / 2; i < NUM_SOLDIERS; ++i) { //-------------------------------- BB 2 ---------------------------------- auto &soldier = state.soldiers[i]; if (soldier.hp == 0) //-------------------------------- BB 3 ---------------------------------- continue; //-------------------------------- BB 4 ---------------------------------- for (auto enemy_soldier : state.enemy_soldiers) { //-------------------------------- BB 5 ---------------------------------- if (enemy_soldier.hp != 0) { //-------------------------------- BB 6 ---------------------------------- soldier.soldier_target = enemy_soldier.id; break; //-------------------------------- BB 7 ---------------------------------- } } } 

Github Link
Dies hat uns geholfen zu verstehen, wie die Grundblöcke funktionieren. Schauen wir uns nun diesen Algorithmus in LLVM IR an:

 ; <label>:140: ; preds = %181, %139 %141 = load i32, i32* %19, align 4 %142 = sext i32 %141 to i64 %143 = icmp slt i64 %142, 20 br i1 %143, label %144, label %184 ; <label>:144: ; preds = %140 %145 = getelementptr inbounds %"struct.player_state::State", %"struct.player_state::State"* %2, i32 0, i32 1 %146 = load i32, i32* %19, align 4 %147 = sext i32 %146 to i64 %148 = call dereferenceable(72) %"struct.player_state::Soldier"* @_ZNSt5arrayIN12player_state7SoldierELm20EEixEm( %"struct.std::array.10"* %145, i64 %147) #3 store %"struct.player_state::Soldier"* %148, %"struct.player_state::Soldier"** %20, align 8 %149 = load %"struct.player_state::Soldier"*, %"struct.player_state::Soldier"** %20, align 8 %150 = getelementptr inbounds %"struct.player_state::Soldier", %"struct.player_state::Soldier"* %149, i32 0, i32 2 %151 = load i64, i64* %150, align 8 %152 = icmp eq i64 %151, 0 br i1 %152, label %153, label %154 ; <label>:153: ; preds = %144 br label %181 

Github Link

Wenn Sie genau hinschauen, werden Sie feststellen, dass das obige Codefragment die ersten drei Blöcke des in LLVM IR kompilierten C ++ - Codefragments sind (jede Zeile ist der Anfang des Basisblocks).

LLVM verfügt über Bibliotheken, mit denen wir "Durchläufe" schreiben können - Code, der LLVM-IR transformieren kann. Mit der LLVM-API können wir LLVM-IR einfach lesen und analysieren, indem wir Module, Funktionen und Basisblöcke durchlaufen und LLVM-IR ändern, bevor es in Maschinencode kompiliert wird.

Nachdem wir nun die Basisblöcke und die LLVM-API haben, wird es einfach, die Anzahl der auszuführenden Anweisungen mit einem so einfachen Algorithmus zu berechnen:

1. Wir schreiben die Funktion IncrementCount, die bei jedem Aufruf eine Ganzzahl verwendet und eine statische Ganzzahl mit diesem Wert inkrementiert. Es muss mit dem Mitgliedscode verknüpft sein.
2. Wir führen Iterationen über alle Basisblöcke durch. Führen Sie für jede Basiseinheit die Schritte 3 und 4 aus.
3. Wir finden n - die Anzahl der Anweisungen in dieser Basiseinheit.
4. Wir fügen den Aufruf der IncrementCount-Funktion vor dem letzten Befehl der Basiseinheit mit dem Argument n ein.
5. Die statische Ganzzahl, mit der IncrementCount arbeitet, ist der Befehlszähler, nachdem der Code ausgeführt wurde. Es kann irgendwo gespeichert und dann überprüft werden.

Unser instrumentiertes IR funktioniert folgendermaßen:

 ; <label>:140: ; preds = %181, %139 %141 = load i32, i32* %19, align 4 %142 = sext i32 %141 to i64 %143 = icmp slt i64 %142, 20 call void @_Z14IncrementCountm(i32 4) br i1 %143, label %144, label %184 ; <label>:144: ; preds = %140 %145 = getelementptr inbounds %"struct.player_state::State", %"struct.player_state::State"* %2, i32 0, i32 1 %146 = load i32, i32* %19, align 4 %147 = sext i32 %146 to i64 %148 = call dereferenceable(72) %"struct.player_state::Soldier"* @_ZNSt5arrayIN12player_state7SoldierELm20EEixEm( %"struct.std::array.10"* %145, i64 %147) #3 store %"struct.player_state::Soldier"* %148, %"struct.player_state::Soldier"** %20, align 8 %149 = load %"struct.player_state::Soldier"*, %"struct.player_state::Soldier"** %20, align 8 %150 = getelementptr inbounds %"struct.player_state::Soldier", %"struct.player_state::Soldier"* %149, i32 0, i32 2 %151 = load i64, i64* %150, align 8 %152 = icmp eq i64 %151, 0 call void @_Z14IncrementCountm(i32 10) br i1 %152, label %153, label %154 ; <label>:153: ; preds = %144 call void @_Z14IncrementCountm(i32 1) br label %181 

Github Link

Wie wir sehen können, wird am Ende jedes Basisblocks unmittelbar vor der letzten Anweisung ein IncrementCount-Aufruf ausgeführt. Mit dem statischen int, mit dem IncrementCount arbeitet, können wir die Anzahl der Anweisungen am Ende des Umzugs jedes Teilnehmers abrufen. Diese Methode ist deterministisch und plattformübergreifend Es wird garantiert, dass derselbe Quellcode dieselbe LLVM-IR generiert, wenn wir dieselbe Version des Compilers und dieselben Flags verwenden.

Fazit

Code-Profiling ist nicht so einfach, wie ich einst dachte. Während ich an einer so relativ einfachen Aufgabe arbeitete, lernte ich, wie der Compiler funktioniert und wie man LLVM-Pässe schreibt. Wenn Sie an der Generierung von Code interessiert sind und Ihre eigenen Passagen schreiben möchten, bietet LLVM einen Leitfaden für Anfänger . Es gibt auch einen großartigen Blog- Artikel, in dem ich meine eigene Passage geschrieben habe. Da die LLVM-API zwischen Hauptversionen nicht abwärtskompatibel ist, achten Sie darauf, welche Version von LLVM Sie verwenden.

Den Quellcode des Passes erhalten Sie hier .