Ceci est mon deuxième article sur mon travail en tant que mentoré pour le compilateur Solang. Si vous n’avez pas vu mon premier article, veuillez le vérifier ici. Pour une brève introduction, en juin 2021, j’ai postulé pour le mentorat de la Linux Foundation et j’ai été accepté pour mettre en œuvre la détection des variables non définies, l’élimination des variables inutilisées et l’élimination des sous-expressions communes. Dans cet article, je vais expliquer mon algorithme pour supprimer les expressions répétées de la représentation intermédiaire de Solang.
L’élimination utilise deux passes sur le graphe de flux de contrôle (CFG) de Solang. Dans le premier, nous détectons les expressions répétées à l’aide d’une structure de données de graphe et, dans le second, nous les supprimons. La première passe suit les expressions disponibles à chaque instruction CFG. Solang enregistre des expressions à l’intérieur de chaque expression. Par exemple, le Ensemble L’instruction ci-dessous contient son emplacement (où se trouve l’instruction dans le fichier Solidity), un nombre qui indique l’index de la variable dans la table des symboles de la fonction et une expression, qui est le côté droit d’une affectation.
Dans la représentation intermédiaire de Solang, l’ordre de ses opérations équivaut à un parcours dans l’ordre de l’arbre qui représente chaque expression d’une instruction. Une façon de suivre facilement une expression que nous avons déjà calculée est de créer une représentation modifiée de l’arbre, dans laquelle nous ajoutons toutes les expressions que nous avons traitées, en prenant soin d’éviter les doublons. Cette représentation contient toutes les opérations possibles calculées jusqu’à présent. Nous fusionnons essentiellement tous les arbres d’expression que nous avons traités dans un graphique. À titre d’exemple, considérons le code suivant :
x = a+b-(54-f);
int d = f*x*(a+b);
Lorsque nous analysons la première ligne, qui contient l’expression ‘a+b-54‘, on a le graphe suivant :
Les variables et les constantes ont en degré zéro, car elles ne proviennent d’aucune opération. La structure de données du graphique nous montre quelles expressions sont disponibles pour l’instruction suivante et nous permet d’identifier rapidement les expressions répétées. Lorsque nous traitons x*f*(a+b), le graphique devient le suivant :
Le nœud e1=a+b a un degré de sortie de deux, ce qui signifie l’expression a+b a été utilisé deux fois dans le code. Les variables peuvent changer de valeur lorsqu’elles sont réaffectées. Si cela se produit, toutes les expressions qui contiennent une telle variable doivent devenir indisponibles. Pour notre graphe, cette opération se traduit par la suppression du nœud variable et de tous ses descendants. Lorsque nous attribuons une autre valeur à x , le graphique devient le suivant :
Notez que non seulement toutes les expressions qui dépendent de x ont été supprimés du graphe, mais aussi le nœud x=e1-e2 a changé pour e4=e1-e2 , comme x ne représente pas l’expression e1-e2 plus.
Il convient de mentionner que la structure de date que nous avons créée nous permet également de suivre les expressions partielles. Dans l’exemple donné, nous avons pu suivre a+b , qui n’est qu’une expression dans une autre.
Maintenant que nous avons montré comment identifier les expressions disponibles à l’aide de notre graphe, il y a un nouveau problème que nous devons aborder : les branches. Considérons la fonction Solidité suivante :
L’expression a-b devient disponible sur les deux branches et est utilisé dans l’instruction return. Notre algorithme devrait être capable de détecter que a-b est disponible après la succursale. Pour résoudre ce problème, nous créons une copie du graphique pour chaque branche (le si et le autre), de sorte qu’une nouvelle expression sera insérée indépendamment dans chaque copie. Après la branche, nous devons croiser les deux graphiques, mais il doit y avoir un moyen de différencier les expressions disponibles avant la branche, les expressions communes créées à l’intérieur des deux branches et les expressions créées à l’intérieur de la branche qui ne sont pas communes.
Nous attribuons un identifiant unique (ID) à chaque nœud du graphe. De cette façon, les expressions disponibles avant la branche ont le même ID sur les deux branches. Chaque nouvelle expression ajoutée au graphique, quelle que soit la copie, aura un nouvel ID unique. Nous pouvons identifier que a-b est disponible après la branche car les identifiants de a et b et l’opération de soustraction coïncide sur les graphiques des deux branches lorsque nous les intersectons. Nous identifions chaque nœud du graphe par un hachage de l’ID de ses opérandes et de son fonctionnement (un hachage de TypeExpression indiqué ci-dessous). En utilisant une telle logique, nous pouvons rapidement identifier si une opération est disponible dans le graphique. L’extrait de code suivant montre comment nous stockons le graphique dans Rust.
Le raisonnement que nous avons décrit ne fonctionne que pour les expressions constituées d’opérandes disponibles avant la branche. Si nous avons la situation suivante :
Notre code n’est pas capable de savoir que e-1 est disponible sur les deux branches, car ses opérandes ont des identifiants différents. Nous avons également supposé que les développeurs seraient capables de se rendre compte qu’ils utilisaient deux opérations équivalentes sur toutes les branches et essaieraient de modifier leur code pour une meilleure lisibilité. Nous montrons ci-dessous à quoi ressemblerait le graphique pour les deux branches. Bien que a-b a un identifiant différent sur chaque copie, nous détectons qu’il s’agit de la même expression car les identifiants des opérandes coïncident, ainsi que l’opération de soustraction.
Nous avons défini une série de règles pour croiser les graphiques de manière transparente. Les nœuds ayant le même identifiant sont conservés, ainsi que ceux dont l’identifiant global diffère, mais dont TypeExpression est le même (c’est le a-b cas de l’exemple). Dans ce cas, nous devons supprimer de la mémoire tous les enfants d’un tel nœud, car nous ne suivons pas les expressions dont les opérandes n’étaient pas disponibles avant la branche.
Jusqu’à présent, nous avons expliqué comment nous avons mené une analyse des expressions disponibles. Nous allons maintenant expliquer comment nous avons exploité la structure de données du graphique pour éliminer les sous-expressions courantes. Lors du premier passage, nous pouvons utiliser le graphique pour identifier les expressions répétées, comme nous l’avons déjà expliqué. Nous avons créé une nouvelle structure pour suivre les sous-expressions courantes. Dès que nous en trouvons une répétée, nous sauvegardons une telle expression dans une table de hachage (le tracker lui-même). La clé de la table de hachage est la Type d’expression, qui se compose de l’ID des opérandes et de l’opération.
Le tracker enregistre non seulement l’expression répétée elle-même, mais aussi le bloc que cette expression doit être instanciée, et s’il existe déjà une variable locale qui porte la valeur de l’expression. Nous devons connaître le bloc où l’expression doit être instanciée car, si nous avons affaire à des expressions rendues disponibles à l’intérieur des branches et utilisées après celles-ci, l’expression doit être résolue après la commande de branche. Un exemple de ce cas est présenté ci-dessous :
Expression a-b doit être résolu avant la si condition, de sorte qu’il y ait une variable portant sa valeur aux deux branches et à l’instruction de retour. Le CFG optimisé ressemble à ceci :
block0: # entry
ty:int256 %a = (arg #0)
ty:int256 %b = (arg #1)
ty:int256 %x = undef
ty:int256 %1.cse_temp = ((arg #0) + (arg #1))
ty:int256 %x = (%1.cse_temp - int256 54)
ty:int256 %d = (%x * %1.cse_temp)
ty:int256 %2.cse_temp = ((arg #0) - (arg #1))
branchcond ((%x + %d) > int256 0), block1, block2
block1: # then
# cc1 and e1 are removed because they are unused
ty:int256 %e = %2.cse_temp
branch block3
block2: # else
# cc2 and e2 are removed because they are unused
ty:int256 %e.8 = %2.cse_temp
branch block3
block3: # endif
return ((%x - %d) + %2.cse_temp)
Nous suivons également les variables auxquelles une expression a été affectée, afin d’éviter de créer des temporaires inutiles. Dans l’exemple ci-dessus, si x*(a+b) réapparu après la mission, nous l’échangerions par d .
Lorsque notre tracker a toutes les expressions répétées, nous effectuons un deuxième passage sur le CFG. Nous reconstituons la structure de données du graphe et, comme elle est déterministe, elle préserve l’identifiant unique du nœud dès la première passe. Lors du traitement d’une expression qui se trouve dans notre tracker, nous l’identifions par un hachage de son TypeExpression et, s’il existe une variable disponible contenant la valeur de l’expression résolue, nous pouvons échanger l’expression entière par cette variable. Il peut s’agir d’une variable locale temporaire ou existante.
Chaque instruction dans Solang contient les expressions qui doivent être évaluées pour que les instructions puissent être exécutées. Par exemple, si l’instruction est un appel de fonction, nous devons évaluer ses arguments avant d’appeler la fonction. Par conséquent, pour effectuer l’élimination des sous-expressions communes lors de la deuxième passe, nous parcourons l’arbre d’expression de chaque instruction. Notre parcours régénère récursivement chaque nœud si aucune variable n’est disponible et échange le nœud par un nœud variable, s’il y en a un disponible.
Les temporaires sont instanciés dans les instructions précédant la première utilisation des expressions qu’ils représentent. Dans le cas des temporaires qui doivent être disponibles à l’intérieur des branches, ils sont créés dans le premier bloc ancêtre commun des blocs des branches.
La définition d’atteinte de Solang ne fonctionne pas encore pour les variables de contrat, les membres de structure et les tableaux, donc notre élimination de sous-expression commune est limitée aux variables locales. L’atteinte des définitions est très importante pour l’algorithme dans son ensemble. Prenons l’exemple suivant :
Expression x+d est clairement disponible à la boucle. Cependant, comme la valeur de x continue de changer, nous ne pouvons pas échanger x+d par la variable locale p . L’atteinte des définitions nous indique qu’une définition d’un bloc descendant est disponible au début de la tandis que bloquer. Cela signifie que nous devons tuer x avant de poursuivre notre analyse, même si nous n’avons pas traité de mission à x . Malgré cela, l’algorithme détecte que x+d est calculé deux fois dans la boucle avant x reçoit une nouvelle valeur, donc l’expression est optimisée, comme indiqué ci-dessous :
block0: # entry
ty:int256 %a = (arg #0)
ty:int256 %b = (arg #1)
ty:int256 %x = undef
ty:int256 %1.cse_temp = ((arg #0) + (arg #1))
ty:int256 %x = (%1.cse_temp - int256 54)
ty:int256 %d = (%x * %1.cse_temp)
ty:int256 %p = (%x + %d)
branch block1
block1: # cond
ty:int256 %2.cse_temp = (%x + %d)
branchcond (%2.cse_temp > int256 0), block2, block3
block2: # body
ty:int256 %t = ((arg #0) - (arg #1))
ty:int256 %x = %2.cse_temp
branch block1
block3: # endwhile
return (((%x - %d) + ((arg #0) - (arg #1))) - %p)
L’algorithme s’est avéré fonctionner correctement pour nos cas d’utilisation. Vous trouverez ci-dessous un bon exemple de fonction et son CFG optimisé.
block0: # entry
ty:int256 %a = (arg #0)
ty:int256 %b = (arg #1)
ty:int256 %ret = int256 0
ty:int256 %x = (((arg #0) + (arg #1)) + int256 5)
branchcond ((%x + int256 5) < int256 0), block1, block2
block1: # then
ty:uint256 %p = uint256(%x)
branch block2
block2: # endif
ty:uint256 %p2 = uint256(%x)
ty:int256 %1.cse_temp = int256((%p2 + uint256 9))
ty:int256 %r1 = (%1.cse_temp - int256 4)
ty:int256 %r2 = (%1.cse_temp - int256 9)
ty:int256 %ret = -%r1
ty:int256 %ret = (%ret + %r2)
return %ret
À partir du CFG généré, nous remarquons quelques aspects intéressants de l’algorithme. Premièrement, cela n’a pas créé de temporaire pour (((arg #0) + (arg #1)) + int256 5) car x était déjà disponible pour cela. Deuxièmement, à int(p2+9) il n’a pas créé de créer une variable pour p2+9 , car nous n’avions besoin que int(p2+9) plus tard.
L’élimination de la sous-expression commune était une toute nouvelle passe pour Solang. Après avoir fait quelques recherches en ligne, je n’ai trouvé aucune documentation sur sa mise en œuvre, à part des explications théoriques, j’ai donc conçu ma propre approche pour résoudre le problème. Le Linux Mentorhsip a été une expérience enrichissante, dans laquelle j’ai plongé profondément dans les compilateurs et fait de nouvelles connexions.
Rejoignez Coinmonks Telegram Channel et Youtube Channel pour en savoir plus sur le trading et l’investissement crypto