Le développement d'un compilateur est une tâche très difficile. Mais, heureusement, avec l'avancement de projets comme LLVM, la solution à ce problème est considérablement simplifiée, permettant même à un programmeur solitaire de créer un nouveau langage, comparable en performance au C. Travailler avec LLVM est compliqué car ce système est constitué d'une énorme quantité de code, accompagnée de peu de documentation. Afin d'essayer de corriger ce défaut, l'auteur du matériel, dont la traduction que nous publions aujourd'hui, vise à démontrer des exemples de code écrits en Go et à montrer comment ils sont d'abord traduits en , puis en LLVM IR en utilisant le compilateur . Le code Go SSA et LLVM IR a été légèrement modifié, en supprimant ce qui n'est pas lié aux explications fournies ici, afin que ces explications soient plus compréhensibles.
Le premier exemple
La première fonction que je vais examiner ici constitue un mécanisme simple pour additionner des nombres :
func myAdd(a, b int) int{
return a + b
}Cette fonction est très simple, et il n'est peut-être rien de plus simple. Elle se traduit par le code Go SSA suivant :
func myAdd(a int, b int) int:
entry:
t0 = a + b int
return t0Dans cette représentation de la fonction, les indications sur les types de données sont placées à droite, et dans la plupart des cas, elles peuvent être ignorées.
Cet exemple simple permet déjà de voir l'essence d'un des aspects de SSA. En effet, lors de la transformation du code en forme SSA, chaque expression est décomposée en ses parties les plus élémentaires. Dans notre cas, l'instruction return a + b, représente en réalité deux opérations : l'addition de deux nombres et le retour du résultat.
De plus, il est possible de voir les blocs élémentaires du programme, dans ce code il n'y a qu'un seul bloc — le bloc d'entrée (entry block). Nous parlerons plus en détail des blocs ci-dessous.
Le code Go SSA se traduit facilement en LLVM IR :
define i64 @myAdd(i64 %a, i64 %b) {
entry:
%0 = add i64 %a, %b
ret i64 %0
} On peut remarquer que, bien que d'autres constructions syntaxiques soient utilisées ici, la structure de la fonction, dans l'ensemble, n'a pas changé. Le code LLVM IR est légèrement plus puissant que le code Go SSA et ressemble à du C. Ici, dans la déclaration de fonction, la description du type de données retourné vient en premier, le type de l'argument étant précisé avant le nom de l'argument. De plus, pour simplifier l'analyse IR, un symbole précède les noms des entités globales. @, alors qu'un symbole précède les noms des entités locales. % (une fonction est également considérée comme une entité globale).
Une des caractéristiques de ce code à noter est que la décision sur la représentation du type Go int, qui peut être représenté par une valeur de 32 bits ou de 64 bits, en fonction du compilateur et de l'objectif de compilation, est prise lors de la création du code LLVM IR. C'est une des nombreuses raisons pour lesquelles le code LLVM IR n'est pas, comme beaucoup le pensent, indépendant de la plateforme. Un tel code, créé pour une plateforme, ne peut pas simplement être pris et compilé pour une autre plateforme (à moins de s'attaquer à cette tâche ).
Un autre point intéressant à noter est que le type i64 n'est pas un entier signé : il est neutre en matière de représentation du signe d'un nombre. Selon l'instruction, il peut représenter à la fois des nombres signés et des nombres non signés. Dans le cas de la représentation de l'opération d'addition, cela n'a pas d'importance, c'est pourquoi il n'y a pas de différence dans le traitement des nombres signés ou non signés. Il convient de noter qu'en langage C, le débordement d'une variable entière signée entraîne un comportement indéfini, c'est pourquoi le frontend Clang ajoute un drapeau à l'opération. nsw (no signed wrap), qui indique à LLVM qu'il peut partir du principe qu'il n'y a jamais de débordement lors de l'addition.
Cela peut être important pour certaines optimisations. Par exemple, l'addition de deux valeurs i16 sur une plateforme 32 bits (avec des registres 32 bits) nécessite, après l'addition, une opération d'extension du signe pour rester dans la plage i16. C'est pourquoi il s'avère souvent plus efficace d'exécuter des opérations entières en tenant compte des tailles de registre de la machine.
Ce qui se passe ensuite avec ce code IR ne nous intéresse pas particulièrement. 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 transformé en code machine.
Deuxième exemple
Le prochain exemple que nous allons examiner sera un peu plus complexe. Plus précisément, il s'agit d'une fonction qui somme un tableau d'entiers :
func sum(numbers []int) int {
n := 0
for i := 0; i < len(numbers); i++ {
n += numbers[i]
}
return n
}Ce code se transforme en le code SSA Go 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, on peut déjà voir plus de constructions caractéristiques de la représentation du code sous la forme SSA. Probablement, la caractéristique la plus évidente de ce code est 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 l'on considère cette commande comme une commande de contrôle de flux, il s'agit de la commande de retour.
En réalité, on peut noter que le programme n'est pas divisé en blocs avec des accolades (comme dans les langages de la famille C). Il est divisé par des étiquettes, ce qui rappelle les langages d'assemblage et est présenté sous forme de blocs de base. Dans le SSA, les blocs de base sont des séquences continues de code qui commencent par une étiquette et se terminent par des instructions de fin de bloc de base, par exemple — retourner et jump.
Un autre détail intéressant de ce code est l'instruction phi. Cette instruction est assez inhabituelle, et il peut falloir un certain temps pour s'y habituer. Rappelez-vous que — c'est l'abréviation de Static Single Assignment. C'est une représentation intermédiaire du code utilisée par les compilateurs, où chaque variable se voit attribuer une valeur une seule fois. Cela convient parfaitement pour représenter des fonctions simples, comme notre fonction myAdd, montrée ci-dessus, mais n'est pas adaptée aux fonctions plus complexes — comme celle discutée dans cette section sum. En particulier, lors de l'exécution d'une boucle, les variables changent i et n.
SSA contourne la contrainte d'attribution unique des valeurs des variables grâce à ce qu'on appelle une instruction phi (son nom provient de l'alphabet grec). En effet, pour que la représentation SSA puisse être générée pour des langages comme C, il faut recourir à certaines astuces. Le résultat de l'appel de cette instruction est la valeur actuelle de la variable (i ou n), et comme paramètres, une liste de blocs de base est utilisée. Par exemple, considérons l'instruction suivante :
t0 = phi [entry: 0:int, for.body: t6] #n Son sens est le suivant : si le bloc de base précédent était le bloc entry (entrée), alors t0 est une constante 0, et si le bloc de base précédent était for.body, il faut prendre la valeur t6 de ce bloc. Tout cela peut paraître assez mystérieux, mais grâce à ce mécanisme, le SSA fonctionne. Du point de vue humain, cela complique la compréhension du code, mais le fait que chaque valeur n'est attribuée qu'une seule fois simplifie considérablement de nombreuses optimisations.
Notez que si vous écrivez votre propre compilateur, vous n'avez généralement pas à traiter de telles choses. Même Clang ne génère pas toutes ces instructions phi, il utilise le mécanisme alloca (il ressemble à la gestion des variables locales standard). Ensuite, lors du passage d'optimisation LLVM, appelé , les instructions alloca sont converties en forme SSA. TinyGo, cependant, reçoit ses entrées de Go SSA, qui, c'est pratique, sont déjà converties en forme SSA.
Une autre nouveauté de ce fragment de code intermédiaire est que l'accès aux éléments d'un slice par index est présenté sous la forme d'une opération de calcul d'adresse et d'une opération de déférencement du pointeur obtenu. On peut voir l'ajout direct de constantes dans le code IR (par exemple — 1:int). Dans l'exemple de la fonction myAdd Cela n'a pas été utilisé. Maintenant, en tenant compte de ces particularités, examinons à quoi ce code se transformera lors de sa conversion en LLVM IR :
define i64 @sum(i64* %ptr, i64 %len, i64 p) {
entry:
br label %for.loop
for.loop: ; preds = %for.body, %entry
%0 = phi i64 [ 0, %entry ], [ %5, ref.next ]
%1 = phi i64 [ 0, %entry ], [ %6, ref.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 auparavant, nous pouvons voir la même structure, incluant d'autres constructions syntaxiques. Par exemple, dans les appels phi les valeurs et les étiquettes ont changé de place. Cependant, il y a aussi quelque chose qui mérite une attention particulière.
Tout d'abord, nous pouvons voir une signature de fonction complètement différente. LLVM ne supporte pas les slices, du coup, en tant qu'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 aurait pu représenter trois éléments de slice (ptr, len et cap) sous la forme d'une structure (struct), mais les représenter comme trois entités distinctes permet d'effectuer certaines optimisations. D'autres compilateurs pourraient représenter le slice d'une manière différente, cela dépend des conventions d'appel de fonctions de la plateforme cible.
Une autre caractéristique intéressante de ce code est l'utilisation de l'instruction getelementptr (souvent abrégée en GEP).
Cette instruction fonctionne avec des pointeurs et est utilisée pour obtenir un pointeur vers un élément de slice. Par exemple, comparons-la avec le code suivant écrit en C :
int* sliceptr(int *ptr, int index) {
return &ptr[index];
}Ou avec le suivant, équivalent à cela :
int* sliceptr(int *ptr, int index) {
return ptr + index;
} L'essentiel ici est que l'instruction getelementptr ne réalise pas d'opérations de déréférencement. Elle ne fait que calculer un nouveau pointeur basé sur l'existant. On peut la considérer comme une instruction mul et add au niveau matériel. Des détails sur l'instruction GEP peuvent être consultés dans .
Une autre caractéristique intéressante de ce code intermédiaire est l'utilisation de l'instruction icmp. Ceci est une instruction générale utilisée pour la comparaison d'entiers. Le résultat de l'exécution de cette instruction est toujours une valeur de type i1 — valeur booléenne. Dans ce cas, la comparaison est effectuée en utilisant le mot-clé slt (signed less than), car nous comparons deux nombres précédemment représentés par le type int. Si nous comparions deux entiers non signés, nous aurions utilisé icmp, tandis que le mot-clé utilisé pour la comparaison serait ult. Pour comparer des nombres à virgule flottante, une autre instruction est utilisée, fcmp, qui fonctionne de manière similaire.
Résultats
Je pense avoir couvert les caractéristiques les plus importantes de LLVM IR dans ce document. Bien sûr, il y a encore beaucoup d'autres choses. En particulier, dans la représentation intermédiaire du code, il peut exister de nombreuses annotations permettant de prendre en compte certaines caractéristiques du code lors des passes d'optimisation, qui sont connues du compilateur et ne peuvent pas être exprimées autrement dans l'IR. Par exemple, il y a le drapeau inbounds de l'instruction GEP, ou les drapeaux 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 ne sera pas référencée en dehors de l'unité de compilation actuelle. Cela permet d'effectuer de nombreuses optimisations interprocédurales intéressantes, comme l'élimination des arguments inutilisés.
Vous pouvez lire des détails sur LLVM dans , auquel vous vous référerez souvent lors du développement de votre propre compilateur basé sur LLVM. Voici , qui traite du développement d'un compilateur pour un langage très simple. Ces deux sources d'informations seront utiles lors de la création de votre propre compilateur.
Chers lecteurs ! Utilisez-vous LLVM ?
Source : habr.com
