Le développement du compilateur est une tâche très difficile. Mais, heureusement, avec le développement de projets comme LLVM, la solution à ce problème est grandement simplifiée, ce qui permet même à un seul programmeur de créer un nouveau langage proche des performances en C. Travailler avec LLVM est compliqué par le fait que ce système est représenté par une énorme quantité de code, équipé d'une petite documentation. Afin d'essayer de corriger cette faille, l'auteur du matériel que nous publions aujourd'hui va montrer des exemples de code écrit en Go et montrer comment ils sont transmis d'abord à
Go SSA puis à LLVM IR en utilisant le compilateur
TinyGO . Le code Go SSA et LLVM IR a été légèrement modifié, quelque chose qui n'appartient pas aux explications données ici a été supprimé afin de rendre ces explications plus compréhensibles.
Premier exemple
La première fonction que je vais analyser ici est un mécanisme simple pour ajouter des nombres:
func myAdd(a, b int) int{ return a + b }
Cette fonction est très simple, et, peut-être, rien n'est plus facile à ne pas proposer. Il se traduit par le code Go SSA suivant:
func myAdd(a int, b int) int: entry: t0 = a + b int return t0
Avec cette représentation de la fonction, des conseils sur les types de données sont placés à droite, dans la plupart des cas, vous pouvez les ignorer.
Ce petit exemple vous permet déjà de voir l'essentiel d'un aspect de SSA. À savoir, lors de la conversion de code sous forme SSA, chaque expression est divisée en parties les plus élémentaires dont elle se compose. Dans notre cas, la commande
return a + b , en fait, représente deux opérations: ajouter deux nombres et retourner le résultat.
De plus, ici vous pouvez voir les blocs de base du programme, dans ce code, il n'y a qu'un seul bloc - l'entrée (bloc d'entrée). Nous parlerons plus en détail des blocs ci-dessous.
Le code Go SSA peut être facilement converti en LLVM IR:
define i64 @myAdd(i64 %a, i64 %b) { entry: %0 = add i64 %a, %b ret i64 %0 }
Vous pouvez remarquer que bien que d'autres constructions syntaxiques soient utilisées ici, la structure de la fonction n'a fondamentalement pas changé. Le code IR LLVM est légèrement plus fort que le code Go SSA, similaire à C. Ici, dans la déclaration de fonction, vient d'abord une description du type de données qui lui est retourné, le type de l'argument est indiqué avant le nom de l'argument. De plus, pour simplifier l'analyse infrarouge, les noms des entités globales sont précédés du symbole
@ , et avant les noms des entités locales par le caractère
% (la fonction est également considérée comme une entité globale).
L'une des caractéristiques de ce code à laquelle vous devez faire attention est que la décision de représenter le type Go
int , qui peut être représenté par une valeur 32 bits ou 64 bits, selon le compilateur et le but de la compilation, est prise lors de la création de LLVM Code IR. C'est l'une des nombreuses raisons pour lesquelles le code IR LLVM n'est pas indépendant de la plate-forme. Un tel code créé pour une plate-forme ne peut pas être simplement pris et compilé pour une autre plate-forme (sauf si vous abordez cette tâche
avec une extrême prudence ).
Un autre point intéressant à noter est que le type
i64 n'est pas un entier signé: il est neutre en termes de représentation du signe du nombre. Selon l'instruction, il peut représenter à la fois des numéros signés et des numéros non signés. Dans le cas de la représentation de l'opération d'addition, cela ne joue aucun rôle, il n'y a donc pas de différence dans le travail avec des nombres avec ou sans signe. Ici, je voudrais noter qu'en C, le débordement d'une variable entière signée conduit à un comportement indéfini, par conséquent, le frontend Clang ajoute le drapeau
nsw (pas de retour à la ligne signé) à l'opération, ce qui indique à LLVM qu'il peut partir de l'hypothèse qu'avec il n'y a jamais de débordement.
Cela peut être important pour certaines optimisations. Par exemple, l'ajout de deux valeurs
i16 sur une plate-forme 32 bits (avec registres 32 bits) nécessite, une fois l'ajout terminé, que l'opération d'extension de signe reste dans la plage
i16 . Pour cette raison, il est souvent plus efficace d'effectuer des opérations entières en tenant compte de la taille de la machine du registre.
Ce qui se passe à l'avenir avec ce code IR n'est pas particulièrement intéressant pour nous maintenant. Le code est optimisé (mais dans le cas d'un exemple aussi simple que le nôtre, rien n'est déjà optimisé), puis il est converti en code machine.
Deuxième exemple
L'exemple suivant, que nous allons examiner, sera un peu plus compliqué. À savoir, nous parlons d'une fonction qui résume la tranche d'entiers:
func sum(numbers []int) int { n := 0 for i := 0; i < len(numbers); i++ { n += numbers[i] } return n }
Ce code est converti en le code Go SSA suivant:
func sum(numbers []int) int: entry: jump for.loop for.loop: t0 = phi [entry: 0:int, for.body: t6] #n int t1 = phi [entry: 0:int, for.body: t7] #i int t2 = len(numbers) int t3 = t1 < t2 bool if t3 goto for.body else for.done for.body: t4 = &numbers[t1] *int t5 = *t4 int t6 = t0 + t5 int t7 = t1 + 1:int int jump for.loop for.done: return t0
Ici, vous pouvez déjà voir plus de constructions spécifiques à la présentation de code sous forme de SSA. La caractéristique la plus évidente de ce code est probablement le fait qu'il n'y a pas de commandes de contrôle de flux structurées. Pour contrôler le flux des calculs, il n'y a que des sauts conditionnels et inconditionnels, et si nous considérons cette commande comme une commande pour contrôler le flux, une commande de retour.
En fait, ici, vous pouvez faire attention au fait que le programme n'est pas divisé en blocs utilisant des accolades (comme dans les langages de la famille C). Il est divisé par des étiquettes, qui ressemble aux langages d'assemblage, et est présenté sous la forme de blocs de base. Dans SSA, les blocs de base sont des séquences contiguës de code commençant par une étiquette et se terminant par des instructions pour terminer le bloc de base, par exemple,
return et
jump .
Un autre détail intéressant de ce code est l'instruction
phi . L'instruction est assez inhabituelle, cela peut prendre un certain temps pour la comprendre. N'oubliez pas que
SSA est l'abréviation de Static Single Assignment. Il s'agit d'une représentation intermédiaire du code utilisé par les compilateurs, dans laquelle chaque variable n'est affectée qu'une seule fois. Ceci est idéal pour exprimer des fonctions simples comme notre fonction
myAdd illustrée ci-dessus, mais pas pour des fonctions plus complexes comme la fonction
sum discutée dans cette section. En particulier, lors de l'exécution de la boucle, les variables
i et
n changent.
SSA contourne la restriction sur une seule affectation de valeurs variables en utilisant la soi-disant instruction
phi (son nom est tiré de l'alphabet grec). Le fait est que pour que la représentation SSA du code puisse être formée pour des langages comme C, vous devez recourir à quelques astuces. Le résultat de l'appel de cette instruction est la valeur actuelle de la variable (
i ou
n ), et une liste de blocs de base est utilisée comme paramètre. Par exemple, considérez cette instruction:
t0 = phi [entry: 0:int, for.body: t6] #n
Sa signification est la suivante: si le bloc de base précédent était un bloc d'
entry (entrée), alors
t0 est constant
0 , et si le bloc de base précédent était
for.body , alors vous devez prendre la valeur
t6 de ce bloc. Tout cela peut sembler assez mystérieux, mais grâce à ce mécanisme, la SSA est assurée. D'un point de vue humain, tout cela complique la compréhension du code, mais le fait que chaque valeur ne soit attribuée qu'une seule fois simplifie grandement de nombreuses optimisations.
Notez que si vous écrivez votre propre compilateur, vous n'avez généralement pas à faire face à de telles choses. Même Clang ne génère pas toutes ces instructions
phi , il utilise le mécanisme
alloca (il ressemble à travailler avec des variables locales ordinaires). Ensuite, lors de l'exécution d'une passe d'optimisation LLVM, appelée
mem2reg , les instructions
alloca sont converties au
format SSA. TinyGo, cependant, reçoit des données de Go SSA, qui, commodément, a déjà été converti sous forme SSA.
Une autre innovation de ce morceau de code intermédiaire est que l'accès aux éléments de tranche par index se présente sous la forme de l'opération de calcul de l'adresse et de l'opération de déréférencement du pointeur obtenu. Ici, vous pouvez voir l'ajout direct de constantes au code IR (par exemple -
1:int ). Dans l'exemple avec la fonction
myAdd cela n'a pas été utilisé. Maintenant que nous avons compris ces fonctionnalités, nous allons voir ce que ce code transformera en le convertissant en forme IR LLVM:
define i64 @sum(i64* %ptr, i64 %len, i64 %cap) { entry: br label %for.loop for.loop: ; preds = %for.body, %entry %0 = phi i64 [ 0, %entry ], [ %5, %deref.next ] %1 = phi i64 [ 0, %entry ], [ %6, %deref.next ] %2 = icmp slt i64 %1, %len br i1 %2, label %for.body, label %for.done for.body: ; preds = %for.loop %3 = getelementptr i64, i64* %ptr, i64 %1 %4 = load i64, i64* %3 %5 = add i64 %0, %4 %6 = add i64 %1, 1 br label %for.loop for.done: ; preds = %for.loop ret i64 %0 }
Ici, comme précédemment, nous pouvons voir la même structure, qui comprend d'autres constructions syntaxiques. Par exemple, dans les appels
phi , les valeurs et les étiquettes sont échangées. Cependant, il y a aussi quelque chose qui mérite une attention particulière.
Pour commencer, vous pouvez voir ici une signature complètement différente de la fonction. LLVM ne prend pas en charge les tranches, par conséquent, sous forme d'optimisation, le compilateur TinyGo, qui a généré ce code intermédiaire, a divisé la description de cette structure de données en parties. Il pourrait représenter trois éléments de tranche (
ptr ,
len et
cap ) en tant que structure (struct), mais les présenter comme trois entités distinctes permet certaines optimisations. D'autres compilateurs peuvent présenter la tranche d'une autre manière, cela dépend des conventions d'appel des fonctions de la plate-forme cible.
Une autre caractéristique intéressante de ce code est l'utilisation de l'
getelementptr (souvent appelée GEP pour faire court).
Cette instruction fonctionne avec des pointeurs et est utilisée pour obtenir un pointeur sur un élément de tranche. Par exemple, comparons-le avec le code suivant écrit en C:
int* sliceptr(int *ptr, int index) { return &ptr[index]; }
Ou avec l'équivalent suivant:
int* sliceptr(int *ptr, int index) { return ptr + index; }
La chose la plus importante ici est que l'instruction
getelementptr pas d'opérations de déréférencement. Il calcule uniquement un nouveau pointeur sur la base de celui existant. Il peut être interprété comme
mul et
add au niveau matériel. Les détails sur les instructions GEP peuvent être trouvés
ici .
Une autre caractéristique intéressante de ce code intermédiaire est l'utilisation de l'instruction
icmp . Il s'agit d'une instruction générale utilisée pour implémenter des comparaisons entières. Le résultat de cette instruction est toujours une valeur de type
i1 - une valeur logique. Dans ce cas, une comparaison est effectuée à l'aide du mot clé
slt (signé moins que), car nous comparons deux nombres précédemment représentés par le type
int . Si nous comparions deux entiers non signés, nous utiliserions
icmp comme instruction et le mot-clé utilisé dans la comparaison serait
ult . Pour comparer les nombres à virgule flottante, une autre instruction est utilisée,
fcmp , qui fonctionne de manière similaire.
Résumé
Je crois que dans cet article, j'ai examiné les caractéristiques les plus importantes de LLVM IR. Bien sûr, il y a encore beaucoup de choses. En particulier, dans la représentation intermédiaire du code, il peut y avoir de nombreuses annotations qui permettent de prendre en compte certaines fonctionnalités du code connues du compilateur lors des passes d'optimisation qui ne peuvent pas être exprimées d'une autre manière en IR. Par exemple, ce sont l'indicateur
inbounds de l'instruction
inbounds , ou les
nuw nsw et
nuw , qui peuvent être ajoutés à l'instruction
add . Il en va de même pour le mot-clé
private , qui indique à l'optimiseur que la fonction marquée par lui ne sera pas référencée de l'extérieur de l'unité de compilation actuelle. Cela vous permet d'effectuer de nombreuses optimisations interprocédurales intéressantes, telles que l'élimination des arguments inutilisés.
Vous pouvez en savoir plus sur LLVM dans la
documentation , à laquelle vous vous référerez souvent lors du développement de votre propre compilateur basé sur LLVM. Voici un
guide qui discute du développement du compilateur pour un langage très simple. Ces deux sources d'informations vous seront utiles lors de la création de votre propre compilateur.
Chers lecteurs! Utilisez-vous LLVM?