J'ai prévu d'écrire un article sur la façon dont LLVM optimise une fonction, mais vous devez d'abord écrire comment Clang traduit C ou C ++ en LLVM.
Considérez les aspects de haut niveau sans plonger dans les profondeurs de Clang. Je veux faire attention à la façon dont la sortie Clang est liée à l'entrée, alors que nous ne considérerons pas les fonctionnalités non triviales de C ++. Nous utilisons cette petite fonction, que j'ai empruntée à d'excellentes
conférences sur les optimisations cycliques :
bool is_sorted(int *a, int n) { for (int i = 0; i < n - 1; i++) if (a[i] > a[i + 1]) return false; return true; }
Étant donné que Clang ne fait aucune optimisation et que LLVM IR a été initialement conçu pour fonctionner avec C et C ++, la conversion est relativement facile. J'utiliserai Clang 6.0.1 (ou une version proche, car celle-ci n'a pas encore été publiée) sur x86-64.
La ligne de commande est la suivante:
clang++ is_sorted.cpp -O0 -S -emit-llvm
En d'autres termes: nous compilons le fichier is_sorted.cpp en C ++ et indiquons ensuite à la chaîne d'outils LLVM ce qui suit: n'optimisez pas, affichez l'assembleur en tant que représentation textuelle de LLVM IR. LLVM IR est volumineux et ne peut pas être affiché ou analysé rapidement; un format de code binaire binaire est toujours préférable si une personne n'a pas besoin de regarder ce code.
Voici l'intégralité du LLVM IR, nous allons le revoir en partie.
Commençons par le haut du fichier:
; ModuleID = 'is_sorted.cpp' source_filename = "is_sorted.cpp" target datalayout = "em:e-i64:64-f80:128-n8:16:32:64-S128" target triple = "x86_64-unknown-linux-gnu"
Le texte entier entre le point-virgule et la fin de la ligne est un commentaire, ce qui signifie que la première ligne ne fait rien, mais, si vous êtes intéressé, dans LLVM un «module» est une unité de compilation, un conteneur pour le code et les données. La deuxième ligne ne devrait pas non plus nous déranger. La troisième ligne décrit certaines hypothèses émises par le compilateur, elles ne jouent aucun rôle dans cet article, mais vous pouvez en lire plus
ici .
La cible trois est l'héritage de gcc et n'a plus besoin de nous.
La fonction LLVM possède des attributs facultatifs:
; Function Attrs: noinline nounwind optnone uwtable
Certains d'entre eux (comme ceux-ci) sont pris en charge par le front-end, d'autres sont ajoutés plus tard par des passes d'optimisation. Ces attributs n'ont rien à voir avec la signification du code, je ne les discuterai pas ici, mais vous pouvez les lire
ici si vous êtes intéressé.
Et enfin, notre fonction:
define zeroext i1 @_Z9is_sortedPii(i32* %a, i32 %n)
«Zeroext» signifie que la valeur de retour de la fonction (i1, un entier sur un seul bit) doit être étendue avec des zéros dans le backend à la largeur requise par l'ABI. Vient ensuite le nom de la fonction «mutilé», puis la liste des paramètres, essentiellement les mêmes que dans le code C ++, sauf que i32 définit une variable 32 bits. # 0 connecte la fonction au
groupe d'attributs à la fin du fichier.
Voici la première unité de base:
entry: %retval = alloca i1, align 1 %a.addr = alloca i32*, align 8 %n.addr = alloca i32, align 4 %i = alloca i32, align 4 store i32* %a, i32** %a.addr, align 8 store i32 %n, i32* %n.addr, align 4 store i32 0, i32* %i, align 4 br label %for.cond
Chaque instruction LLVM doit être située à l'intérieur de l'unité de base: un ensemble d'instructions qui a une entrée au début et une sortie à la fin. La dernière instruction de l'unité de base doit être une
instruction de terminaison : "échouer" dans l'unité de base suivante est inacceptable. Chaque fonction doit avoir un bloc d'entrée qui n'a pas de prédécesseurs qui effectuent la transition vers ce bloc. Ces
propriétés et d'
autres sont vérifiées lors de l'analyse infrarouge, ces vérifications peuvent également être appelées plusieurs fois au cours du processus de compilation par le «vérificateur de module». Le vérificateur est utile pour le débogage lorsqu'une passe génère un IR non valide.
Les quatre premières instructions de ce bloc de base sont «alloca»: allocation de mémoire de pile. Les trois premiers créent des variables implicitement créées lors de la compilation, le quatrième - une variable de boucle. Les variables ainsi allouées ne sont accessibles que via les instructions de chargement et de stockage. Les trois instructions suivantes initialisent les trois emplacements de pile, a.addr et n.addr sont initialisés à l'aide des valeurs transmises à la fonction en tant que paramètres et i est initialisé à zéro. La valeur de retour n'a pas besoin d'être initialisée, tout code qui n'est pas indéfini en C et C ++ devra s'en occuper. La dernière instruction est une transition inconditionnelle vers l'unité de base suivante (nous ne sommes pas encore inquiets à ce sujet, la plupart des transitions inutiles seront supprimées par le backend LLVM).
Vous pouvez vous demander: pourquoi Clang alloue-t-il des emplacements de pile pour a et n? Pourquoi n'utilise-t-il pas simplement ces valeurs directement? Dans cette fonction, comme a et n ne changent pas, une telle stratégie fonctionnera, mais ce cas sera pris en compte par l'optimiseur, et est en dehors de la compétence de Calng. Si a et n peuvent être modifiés, ils doivent être en mémoire et ne doivent pas être des valeurs SSA, qui, par définition, ne peuvent prendre de valeur qu’à un point du programme. Les cellules de mémoire sont en dehors du monde SSA et peuvent être modifiées à tout moment. Cela peut sembler étrange, mais une telle solution vous permet d'organiser le travail de toutes les parties du compilateur de manière naturelle et efficace.
Je pense à Clang comme un générateur de code SSA dégénéré qui satisfait toutes les exigences de SSA, mais uniquement parce que l'échange d'informations entre les unités de base se fait par la mémoire. La génération de code non dégénéré nécessite une certaine attention et une certaine analyse, et les développeurs de Clang ont refusé de le faire afin de séparer les responsabilités de génération et d'optimisation du code. Je n'ai pas vu les résultats de mesure, mais à ma connaissance, de nombreuses opérations de mémoire sont générées, puis, presque immédiatement, la plupart d'entre elles sont supprimées par l'optimiseur, sans entraîner de gros frais généraux de temps de compilation,
Considérez comment la boucle for se traduit. En termes généraux, cela ressemble à ceci:
for (initializer; condition; modifier) { body }
Cela se traduit par quelque chose comme ceci:
initializer goto COND COND: if (condition) goto BODY else goto EXIT BODY: body modifier goto COND EXIT:
Bien sûr, une telle traduction n'est pas spécifique à Clang, tout compilateur C et C ++ fait de même.
Dans notre exemple, l'initialiseur de boucle s'effondre dans le bloc de base d'entrée. L'unité de base suivante est une vérification de l'état de la boucle:
for.cond: ; preds = %for.inc, %entry %0 = load i32, i32* %i, align 4 %1 = load i32, i32* %n.addr, align 4 %sub = sub nsw i32 %1, 1 %cmp = icmp slt i32 %0, %sub br i1 %cmp, label %for.body, label %for.end
Clang fait également un commentaire utile que ce bloc de base peut être atteint à partir de for.inc ou du bloc de base d'entrée. Ce bloc charge i et n à partir de la mémoire, réduit n (l'indicateur nsw reflète la propriété du langage C que le débordement de signe n'est pas défini; sans cet indicateur LLVM utilise la sémantique du code supplémentaire), compare la valeur réduite avec i en utilisant le slt (signé moins que, signe moins que), puis finalement branchez-vous dans le bloc de base for.body ou for.end.
L'entrée dans le corps de la boucle n'est possible qu'à partir du bloc for.cond:
for.body: %2 = load i32*, i32** %a.addr, align 8 %3 = load i32, i32* %i, align 4 %idxprom = sext i32 %3 to i64 %arrayidx = getelementptr inbounds i32, i32* %2, i64 %idxprom %4 = load i32, i32* %arrayidx, align 4 %5 = load i32*, i32** %a.addr, align 8 %6 = load i32, i32* %i, align 4 %add = add nsw i32 %6, 1 %idxprom1 = sext i32 %add to i64 %arrayidx2 = getelementptr inbounds i32, i32* %5, i64 %idxprom1 %7 = load i32, i32* %arrayidx2, align 4 %cmp3 = icmp sgt i32 %4, %7 br i1 %cmp3, label %if.then, label %if.end
Les deux premières lignes chargent a et i dans les registres SSA; i s'étend ensuite à 64 bits et peut participer au calcul de l'adresse. La commande
getelementptr (ou gep pour faire court) est la commande LLVM connue pour sa prétention; elle a même sa propre
section d'aide . Contrairement au langage machine, LLVM ne traite pas les pointeurs comme des entiers. Cela facilite l'analyse d'alias et d'autres optimisations de mémoire. Ce code charge un [i] et un [i + 1], les compare et effectue des branchements en fonction du résultat.
Le bloc if.then enregistre 0 dans l'emplacement de pile pour la valeur de retour de la fonction et saute inconditionnellement au bloc de sortie de la fonction:
if.then: store i1 false, i1* %retval, align 1 br label %return
Le bloc else est trivial:
if.end: br label %for.inc
Et le bloc pour en ajouter un à la variable de boucle est également très simple:
for.inc: %8 = load i32, i32* %i, align 4 %inc = add nsw i32 %8, 1 store i32 %inc, i32* %i, align 4 br label %for.cond
Ce code revient en arrière pour vérifier les conditions de boucle.
Si la boucle se termine normalement, nous retournons vrai:
for.end: store i1 true, i1* %retval, align 1 br label %return
Et enfin, ce que nous avons chargé dans l'emplacement de pile de la valeur de retour est chargé et retourné:
return: %9 = load i1, i1* %retval, align 1 ret i1 %9
Il n'y a rien de spécial à la fin de la fonction. Le message s'est avéré plus long que je ne le pensais, dans le prochain article, nous envisagerons d'optimiser le niveau IR pour cette fonction.
(Merci à Xi Wang et Alex Rosenberg pour les corrections envoyées)