Profilage de code avec LLVM

La malédiction du non-déterminisme

Ma première tentative d'écrire un passage LLVM - j'adore ces segfolty

Récemment, j'ai rencontré un problème intéressant - j'avais besoin d'une méthode déterministe et multiplateforme pour déterminer le temps d'exécution du code C ++. Par le mot «déterministe», je veux dire que le même code sera exécuté pour le même nombre d'unités de temps. Par multiplateforme, je comprends que le même code sous Windows et sous Ubuntu fonctionnera pour le même nombre d'unités de temps.

Naturellement, la mesure du temps sur le CPU ne remplit pas ces conditions. Le code machine varie en fonction de l'architecture et du système d'exploitation, et le même code prendra un temps différent à exécuter. Même sur la même machine, des facteurs tels que les échecs de cache joueront un grand rôle - suffisamment pour déformer les résultats de mesure du temps d'exécution du même code. J'avais besoin de quelque chose de plus intelligent ...

La motivation

J'ai rencontré ce problème lorsque je travaillais sur mon projet, Code Character. Code Character est un concours d'IA en ligne dans lequel les participants écrivent des robots pour contrôler une armée dans une stratégie au tour par tour. Je voulais limiter la quantité de code qu'un participant peut exécuter en un seul mouvement.

Ma première pensée a été simplement de mesurer le temps d'exécution du code, mais, comme nous le voyons, cette stratégie n'est pas déterministe, et le participant qui a envoyé le même code deux fois obtiendra des résultats complètement différents. En fait, nous avons essayé d'implémenter cette solution, et les résultats changent tellement qu'un participant peut gagner ou perdre avec le même code. Le résultat sera complètement aléatoire et nous avons abandonné l'idée de mesurer le temps.

ByLecode LLVM

Comme nous ne pouvons pas mesurer le temps, nous avons plutôt décidé de mesurer le nombre d'instructions exécutées. Par conséquent, nous devons instrumenter le code du participant. Si vous n'êtes pas familier avec ce terme, cela ajoute du code à l'application, afin de surveiller certains paramètres, par exemple, l'utilisation du processeur ou l'exécution. Naturellement, nous ne nous attendons pas à ce que les participants le fassent eux-mêmes, nous devons automatiser le processus.

Nous voulions éviter les frais généraux pour les outils d'exécution lorsque vous travaillez sur notre serveur, et donc quelque chose comme un outil PIN ne convient pas à nos fins. Au lieu de cela, nous avons décidé d'instruire directement le code des participants afin de compter le nombre d'instructions qui seraient exécutées. Au lieu d'instrumenter les binaires (code machine), nous avons décidé d'utiliser Clang pour compiler le code et le bytecode LLVM de l'instrument.

Si vous débutez avec LLVM, il s'agit d'une collection de compilateurs modulaires et réutilisables et de technologies de chaîne d'outils. L'un des principaux projets est LLVM IR et backend. En termes simples, une représentation intermédiaire a été développée dans laquelle un front-end de compilation compile du code. Ce code, LLVM IR, est ensuite compilé en code machine par le backend LLVM. Ainsi, si vous créez un nouveau langage, vous pouvez décider d'autoriser LLVM à prendre en charge la génération et l'optimisation de code machine et à écrire un frontend pour convertir votre langage en LLVM IR.


Clang convertit le code C ++ en LLVM IR, qui est ensuite converti en code machine par le backend LLVM.

Clang est l'interface de LLVM. Comme nous avons besoin d'une méthode multiplateforme pour mesurer le code, nous ne pouvons pas instrumenter de code binaire. LLVM IR, cependant, est indépendant de la plate-forme, car il ne s'agit que d'une représentation intermédiaire du code. L'instrumentation du code IR avec les bibliothèques LLVM est une solution multiplateforme simple.

Solution

Un simple compte d'instructions LLVM IR n'est évidemment pas approprié, car nous avons besoin du nombre d'instructions qui seront réellement exécutées, et pas seulement du nombre d'instructions dans le code. Au final, nous avons développé un algorithme simple basé sur le concept de blocs de code de base.

Une unité de base est un ensemble d'instructions dans lequel seule la première instruction peut être le point d'entrée et seule la dernière instruction peut être le point de sortie. ( Toutes les transitions à l'intérieur du bloc de base sont également interdites - environ la traduction ) . Pour comprendre cela, essayez de diviser le code en morceaux dans lesquels les instructions de branche (transitions, boucles et retours) ne peuvent être que les dernières de l'ensemble et l'entrée dans le bloc (première instruction dans fonction, boucle ou bloc if / else) n'est possible que sur la première instruction. Le résultat est un ensemble de blocs de base - des blocs de code séquentiel qui s'exécutent simplement séquentiellement, sans décider quelle instruction exécuter ensuite.

Pourquoi ne l'essayons-nous pas maintenant? Voici un extrait de code fourni par un contributeur de caractères de code:

// 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; } } } 

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

En utilisant le fait que l'unité de base n'a qu'un seul point d'entrée (la première instruction), nous pouvons diviser ce fragment en les unités de base suivantes:

 //-------------------------------- 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 ---------------------------------- } } } 

Lien Github
Cela nous a aidés à comprendre le fonctionnement des blocs de base, regardons maintenant cet algorithme dans LLVM IR:

 ; <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 

Lien Github

Si vous regardez attentivement, vous remarquerez que le fragment de code ci-dessus est les trois premiers blocs du fragment de code C ++ compilé dans LLVM IR (chaque ligne est le début du bloc de base).

LLVM possède des bibliothèques qui nous permettent d'écrire des «passes» - du code qui peut transformer LLVM IR. L'API LLVM nous permet de lire et d'analyser facilement LLVM IR en parcourant les modules, les fonctions et les blocs de base, et de modifier LLVM IR avant de le compiler en code machine.

Maintenant que nous avons les blocs de base et l'API LLVM, il devient simple de calculer le nombre d'instructions à exécuter à l'aide d'un algorithme aussi simple:

1. Nous écrivons la fonction IncrementCount, qui prend un entier et incrémente un entier statique avec cette valeur, chaque fois qu'elle est appelée. Il doit être lié au code membre.
2. Nous faisons des itérations sur tous les blocs de base. Pour chaque unité de base, effectuez les étapes 3 et 4.
3. Nous trouvons n - le nombre d'instructions dans cette unité de base.
4. Nous insérons l'appel à la fonction IncrementCount avant la dernière instruction de l'unité de base, avec l'argument n.
5. L'entier statique avec lequel IncrementCount fonctionne sera le compteur d'instructions après l'exécution du code. Il peut être enregistré quelque part puis vérifié.

Notre IR instrumenté fonctionne comme ceci:

 ; <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 

Lien Github

Comme nous pouvons le voir, un appel IncrementCount est effectué à la fin de chaque bloc de base, juste avant la dernière instruction. En utilisant l'int. Statique avec lequel IncrementCount fonctionne, nous pouvons obtenir le nombre d'instructions à la fin du déplacement de chaque participant. Cette méthode est déterministe et multiplateforme, comme le même code source est garanti pour générer le même IR LLVM si nous utilisons la même version du compilateur et les mêmes drapeaux.

Conclusion

Le profilage de code n'est pas une chose aussi simple que je le pensais. Dans le processus de travail sur une tâche relativement simple, je me suis familiarisé avec le fonctionnement du compilateur et comment écrire des passes LLVM. Si vous êtes intéressé à générer du code et que vous souhaitez écrire vos propres passages, LLVM a un guide pour débutants . il y a aussi un excellent article de blog que j'ai utilisé pour écrire mon propre passage. Étant donné que l'API LLVM n'est pas rétrocompatible entre les principales versions, faites attention à la version de LLVM que vous utilisez.

Vous pouvez obtenir le code source du pass ici .