Développer un 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 en termes de performances de C. Travailler avec LLVM est compliqué par le fait que ce Le système est représenté par une énorme quantité de code, doté de peu de documentation. Afin d'essayer de corriger cette lacune, l'auteur du matériel dont nous publions aujourd'hui la traduction va démontrer des exemples de code écrit en Go et montrer comment ils sont d'abord traduits en , puis dans LLVM IR en utilisant le compilateur . Le code Go SSA et LLVM IR a été légèrement modifié pour supprimer les éléments qui ne sont pas pertinents pour les explications données ici, afin de rendre les explications plus compréhensibles.
Premier exemple
La première fonction que je vais examiner 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 de plus simple. Cela se traduit par le code Go SSA suivant :
func myAdd(a int, b int) int:
entry:
t0 = a + b int
return t0Avec cette vue, les indications sur les types de données sont placées à droite et peuvent être ignorées dans la plupart des cas.
Ce petit exemple permet déjà de voir l’essence d’un aspect du SSA. À savoir, lors de la conversion du code sous forme SSA, chaque expression est décomposée dans les parties les plus élémentaires qui la composent. Dans notre cas, la commande return a + b, en fait, représente deux opérations : ajouter deux nombres et renvoyer le résultat.
De plus, vous pouvez voir ici les blocs de base du programme ; dans ce code, il n'y a qu'un seul bloc - le bloc d'entrée. Nous parlerons davantage des blocs ci-dessous.
Le code Go SSA se convertit facilement en LLVM IR :
define i64 @myAdd(i64 %a, i64 %b) {
entry:
%0 = add i64 %a, %b
ret i64 %0
}
Ce que vous pouvez remarquer, c'est que même si différentes structures syntaxiques sont utilisées ici, la structure de la fonction reste fondamentalement inchangée. Le code IR LLVM est un peu plus fort que le code Go SSA, similaire au C. Ici, dans la déclaration de la fonction, il y a d'abord une description du type de données qu'elle renvoie, le type d'argument est indiqué avant le nom de l'argument. De plus, pour simplifier l'analyse IR, les noms des entités globales sont précédés du symbole @, et avant les noms locaux il y a un symbole % (une fonction est également considérée comme une entité globale).
Une chose à noter à propos de ce code est que la décision de représentation de type de Go int, qui peut être représenté sous la forme d'une valeur 32 bits ou 64 bits, selon le compilateur et la cible de la compilation, est accepté lorsque LLVM génère le code IR. C'est l'une des nombreuses raisons pour lesquelles le code IR LLVM n'est pas, comme beaucoup le pensent, indépendant de la plate-forme. Un tel code, créé pour une plate-forme, ne peut pas simplement être pris et compilé pour une autre plate-forme (sauf si vous êtes apte à résoudre ce problème). ).
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 nombres signés et non signés. Dans le cas de la représentation de l'opération d'addition, cela n'a pas d'importance, il n'y a donc aucune différence entre travailler avec des nombres signés ou non signés. Ici, je voudrais noter que dans le langage C, le débordement d'une variable entière signée conduit à un comportement indéfini, donc l'interface Clang ajoute un indicateur à l'opération nsw (pas de wrap signé), qui indique à LLVM qu'il peut supposer que l'ajout ne déborde jamais.
Cela peut être important pour certaines optimisations. Par exemple, ajouter deux valeurs i16 sur une plateforme 32 bits (avec registres 32 bits) nécessite après ajout une opération d'expansion de signe afin de rester à portée i16. Pour cette raison, il est souvent plus efficace d’effectuer des opérations sur des nombres entiers basées sur la taille des registres machine.
Ce qui se passe ensuite avec ce code IR ne nous intéresse pas particulièrement pour le moment. Le code est optimisé (mais dans le cas d’un exemple simple comme le nôtre, rien n’est optimisé) puis converti en code machine.
Le deuxième exemple
Le prochain exemple que nous examinerons sera un peu plus compliqué. À savoir, nous parlons d’une fonction qui additionne une tranche d’entiers :
func sum(numbers []int) int {
n := 0
for i := 0; i < len(numbers); i++ {
n += numbers[i]
}
return n
}Ce code se convertit en 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 t0Ici, vous pouvez déjà voir plus de constructions typiques pour représenter le code sous la forme SSA. La caractéristique la plus évidente de ce code est peut-être le fait qu’il n’y a pas de commandes structurées de contrôle de flux. Pour contrôler le flux des calculs, il n'y a que des sauts conditionnels et inconditionnels, et, si l'on considère cette commande comme une commande de contrôle du flux, une commande de retour.
En fait, ici, vous pouvez faire attention au fait que le programme n'est pas divisé en blocs à l'aide d'accolades (comme dans la famille des langages C). Il est divisé par des étiquettes, rappelant les langages assembleurs, et présenté sous forme de blocs de base. En SSA, les blocs de base sont définis comme des séquences de code contiguës commençant par une étiquette et se terminant par des instructions d'achèvement de bloc de base, telles que - return и jump.
Un autre détail intéressant de ce code est représenté par l'instruction phi. Les instructions sont assez inhabituelles et peuvent prendre un certain temps à comprendre. souviens-toi, ça 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 se voit attribuer une valeur une seule fois. C'est idéal pour exprimer des fonctions simples comme notre fonction myAddillustré ci-dessus, mais ne convient pas aux fonctions plus complexes telles que la fonction discutée dans cette section sum. En particulier, les variables changent lors de l'exécution de la boucle i и n.
SSA contourne la restriction sur l'attribution de valeurs de variables une seule fois à l'aide d'une soi-disant instruction phi (son nom est tiré de l'alphabet grec). Le fait est que pour que la représentation SSA du code soit généré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ètres. Par exemple, considérons 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 entry (entrée), puis t0 est une constante 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 paraître assez mystérieux, mais c’est ce mécanisme qui fait fonctionner le SSA. D'un point de vue humain, tout cela rend le code difficile à comprendre, mais le fait que chaque valeur ne soit attribuée qu'une seule fois facilite grandement de nombreuses optimisations.
Notez que si vous écrivez votre propre compilateur, vous n’aurez généralement pas à gérer ce genre de choses. Même Clang ne génère pas toutes ces instructions phi, il utilise un mécanisme alloca (cela ressemble à travailler avec des variables locales ordinaires). Ensuite, lors de l'exécution d'une passe d'optimisation LLVM appelée , instructions alloca converti au format SSA. TinyGo, cependant, reçoit des informations de Go SSA, qui, commodément, sont déjà converties au format SSA.
Une autre innovation du fragment de code intermédiaire considéré est que l'accès aux éléments de tranche par index est représenté sous la forme d'une opération de calcul de l'adresse et d'une opération de déréférencement du pointeur résultant. 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 éliminé ces fonctionnalités, examinons ce que devient ce code une fois converti au format LLVM IR :
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 inclut d’autres structures syntaxiques. Par exemple, lors des appels phi valeurs et étiquettes échangées. Cependant, il y a ici quelque chose qui mérite une attention particulière.
Pour commencer, vous pouvez voir ici une signature de fonction complètement différente. LLVM ne prend pas en charge les tranches et, par conséquent, à titre 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 и cap) sous forme de structure (struct), mais les représenter comme trois entités distinctes permet certaines optimisations. D'autres compilateurs peuvent représenter la tranche d'autres manières, en fonction des conventions d'appel des fonctions de la plateforme cible.
Une autre caractéristique intéressante de ce code est l'utilisation de l'instruction getelementptr (souvent abrégé en GEP).
Cette instruction fonctionne avec des pointeurs et est utilisée pour obtenir un pointeur vers un élément slice. 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 à ceci :
int* sliceptr(int *ptr, int index) {
return ptr + index;
}
La chose la plus importante ici est que les instructions getelementptr n'effectue pas d'opérations de déréférencement. Il calcule simplement un nouveau pointeur basé sur celui existant. Il peut être pris comme instruction mul и add au niveau matériel. Vous pouvez en savoir plus sur les instructions GEP .
Une autre particularité intéressante de ce code intermédiaire est l'utilisation de l'instruction icmp. Il s'agit d'une instruction à usage général utilisée pour implémenter des comparaisons d'entiers. Le résultat de cette instruction est toujours une valeur de type i1 — valeur logique. Dans ce cas, une comparaison est effectuée à l'aide du mot-clé slt (signé inférieur à), puisque 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, et le mot-clé utilisé dans la comparaison serait ult. Pour comparer des nombres à virgule flottante, une autre instruction est utilisée, fcmp, qui fonctionne de la même manière.
Les résultats de
Je pense que dans ce document, j'ai couvert les fonctionnalités les plus importantes de LLVM IR. Bien sûr, il y en a beaucoup plus ici. En particulier, la représentation intermédiaire du code peut contenir de nombreuses annotations permettant aux passes d'optimisation de prendre en compte certaines fonctionnalités du code connues du compilateur qui ne peuvent autrement être exprimées en IR. Par exemple, c'est un drapeau inbounds Instructions GEP ou drapeaux nsw и nuw, qui peut être ajouté aux instructions add. Il en va de même pour le mot-clé private, indiquant à l'optimiseur que la fonction qu'il marque ne sera pas référencée depuis l'extérieur de l'unité de compilation actuelle. Cela permet de nombreuses optimisations interprocédurales intéressantes, comme l'élimination des arguments inutilisés.
Vous pouvez en savoir plus sur LLVM dans , auquel vous ferez souvent référence lors du développement de votre propre compilateur basé sur LLVM. Ici , qui vise à développer un 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 ?
Source: habr.com