compressed.tracemonkey-pldi-09

Andreas Gal∗+, Brendan Eich∗, Mike Shaver∗, David Anderson∗, David Mandelin∗, Mohammad R. Haghighat$, Blake Kaplan∗, Graydon Hoare∗, Boris Zbarsky∗, Jason Orendorff∗, Jesse Ruderman∗, Edwin Smith#, Rick Reitmaier#, Michael Bebenita+, Mason Chang+#, Michael Franz+ Mozilla Corporation∗ 1. Introduction Spécialisation de type Juste-à-Temps basée sur les traces pour les langages dynamiques {gal,brendan,shaver,danderson,dmandelin,mrbkap,graydon,bz,jorendorff,jruderman}@mozilla.com Adobe Corporation# {edwsmith,rreitmai}@adobe.com Intel Corporation$ {mohammad.r.haghighat}@intel.com Université de Californie, Irvine+ {mbebenit,changm,franz}@uci.edu Résumé et est utilisé pour la logique applicative des applications de productivité basées sur navigateur telles que Google Mail, Google Docs et Zimbra Collaboration Suite. Dans ce domaine, afin d'offrir une expérience utilisateur fluide et de permettre une nouvelle génération d'applications, les machines virtuelles doivent fournir un faible temps de démarrage et des performances élevées. Les compilateurs pour langages typés statiquement s'appuient sur les informations de type pour générer du code machine efficace. Dans un langage de programmation typé dynamiquement comme JavaScript, les types des expressions peuvent varier à l'exécution. Cela signifie que le compilateur ne peut plus facilement transformer les opérations en instructions machine qui opèrent sur un type spécifique. Sans informations de type exactes, le compilateur doit émettre un code machine généralisé plus lent qui peut gérer toutes les combinaisons de types potentielles. Bien que l'inférence de type statique au moment de la compilation puisse être capable de rassembler des informations de type pour générer du code machine optimisé, l'analyse statique traditionnelle est très coûteuse et donc mal adaptée à l'environnement hautement interactif d'un navigateur web. Nous présentons une technique de compilation basée sur les traces pour les langages dynamiques qui concilie la vitesse de compilation avec d'excellentes performances du code machine généré. Notre système utilise une approche d'exécution en mode mixte : le système commence par exécuter JavaScript dans un interpréteur de bytecode à démarrage rapide. Au fur et à mesure que le programme s'exécute, le système identifie chaudes(fréquemment exécutées) les séquences de bytecode, les enregistre et les compile en code natif rapide. Nous appelons une telle séquence d'instructions une trace. Contrairement aux compilateurs dynamiques basés sur les méthodes, notre compilateur dynamique opère à la granularité des boucles individuelles. Ce choix de conception est basé sur l'attente que les programmes passent la plupart de leur temps dans des boucles chaudes. Même dans les langages typés dynamiquement, nous nous attendons à ce que les boucles chaudes soient principalement stables en termes de types, ce qui signifie que les types des valeurs sont invariants. (12) Par exemple, nous nous attendrions à ce que les compteurs de boucle qui commencent comme des entiers restent des entiers pour toutes les itérations. Lorsque ces deux attentes sont vérifiées, un compilateur basé sur les traces peut couvrir l'exécution du programme avec un petit nombre de traces spécialisées par type et compilées efficacement. Chaque trace compilée couvre un chemin à travers le programme avec un mappage des valeurs aux types. Lorsque la VM exécute une trace compilée, elle ne peut pas garantir que le même chemin sera suivi ou que les mêmes types se produiront dans les itérations de boucle suivantes. Les langages dynamiques comme JavaScript sont plus difficiles à compiler que les langages typés statiquement. Comme aucune information de type concrète n'est disponible, les compilateurs traditionnels doivent émettre du code générique capable de gérer toutes les combinaisons de types possibles à l'exécution. Nous présentons une technique de compilation alternative pour les langages typés dynamiquement qui identifie les traces de boucles fréquemment exécutées au moment de l'exécution, puis génère à la volée du code machine spécialisé pour les types dynamiques réels apparaissant sur chaque chemin à travers la boucle. Notre méthode offre une spécialisation de types inter-procédurale peu coûteuse, ainsi qu'une manière élégante et efficace de compiler de manière incrémentale les chemins alternatifs découverts tardivement à travers des boucles imbriquées. Nous avons implémenté un compilateur dynamique pour JavaScript basé sur notre technique et avons mesuré des accélérations de 10x et plus pour certains programmes de référence. Catégories et descripteurs de sujets D.3.4 [Langages de programmation] : Processeurs -Compilateurs incrémentaux, génération de code. Termes généraux Conception, Expérimentation, Mesure, Performance. Mots-clés JavaScript, compilation à la volée, arbres de traces. Les langages dynamiques tels que JavaScript, Python et Ruby sont populaires car ils sont expressifs, accessibles aux non-experts et facilitent le déploiement en distribuant simplement un fichier source. Ils sont utilisés pour de petits scripts ainsi que pour des applications complexes. JavaScript, par exemple, est la norme de facto pour la programmation web côté client L'autorisation de reproduire des copies numériques ou papier de tout ou partie de ce travail pour un usage personnel ou en classe est accordée sans frais, à condition que les copies ne soient pas réalisées ou distribuées à des fins de profit ou d'avantage commercial et qu'elles portent cette notice et la citation complète sur la première page. Pour toute autre reproduction, republication, mise en ligne sur des serveurs ou redistribution à des listes, une autorisation préalable spécifique et/ou des frais sont requis. PLDI'09,15-20 juin 2009, Dublin, Irlande. Copyright c2009 ACM 978-1-60558-392-1/09/06...5,00 $ 1 for (var i = 2; i < 100; ++i) { 2 if (!primes[i]) 3 continue; 4 for (var k = i + i; i < 100; k += i) 5 primes[k] = false; 6 } Ainsi,l'enregistrementetlacompilationd'unetrace spéculent quelecheminetletypageserontexactementcommeilsl'étaientpendantl'enre gistrementpourlesitérationssuivantesdelaboucle. Chaque trace compilée contient toutes les gardes(vérifications)nécessairespourvaliderlaspéculation.Sil'une desgardeséchoue(silefluxdecontrôleestdifférent,ouunevaleurd'untypediff érentestgénérée),latracesort.Siunesortiedevientchaude,laVMpeutenregist rerune trace de branche commençantàlasortiepourcouvrirlenouveauchemin.Ainsi,laVMenregistreu n arbre de traces couvranttouslescheminschaudsàtraverslaboucle. LesbouclesimbriquéespeuventêtredifficilesàoptimiserpourlesVMdetraces. Dansuneimplémentationnaïve,lesbouclesinternesdeviendraientchaudesd' abord,etlaVMcommenceraitàtraceslà.Quandlaboucleinterne sort,laVMdétecteraitqu'unebranchedifférenteaétéprise.LaVMessaieraitd'e nregistrerunetracedebranche,etdécouvriraitquelatraceatteintnonpasl'en-t êtedelaboucleinterne,maisl'en-têtedelaboucleexterne.Àcepoint,laVMpourr aitcontinueràtracesjusqu'àatteindreànouveaul'en-têtedelaboucleinterne,tr açantainsilaboucleexterneàl'intérieurd'unarbredetracespourlaboucleinter ne.Maiscelarequiertdetracerunecopiedelaboucleexternepourchaquesortie latéraleetcombinaisondetypesdanslaboucleinterne.Enessence,c'estunefor mededuplicationdequeueinvolontaire,quipeutfacilementdéborderlecache decode.Autrement,laVMpourraitsimplementarrêterdetracer,etabandonne rdetracerlesbouclesexternes. Nousrésolvonsleproblèmedesbouclesimbriquéesen enregistrant des arbres de traces imbriqués.Notresystèmetracelaboucleinterneexactementcommelaversion naïve.Lesystèmearrêted'étendrel'arbreinternequandilatteintuneboucleext erne,maisilcommencealorsunenouvelletraceàl'en-têtedelaboucleexterne. Quandlaboucleexterneatteintl'en-têtedelaboucleinterne,lesystèmeessaied 'appelerl'arbredetracespourlaboucleinterne.Sil'appelréussit,laVMenregistr el'appelàl'arbreinternecommepartiedelatraceexterneettermine latraceexternenormalement.Ainsi,notresystèmepeuttracern'importequel nombredebouclesimbriquéesàn'importequelleprofondeursanscauserded uplicationdequeueexcessive. CestechniquespermettentàuneVMdetraduiredynamiquementunprogram meenarbresdetracesimbriquésetspécialiséspartype.Comme lestracespeuventtraverserleslimitesd'appelsdefonctions,nostechniquesatt eignentégalementleseffetsd'incorporation.Comme lestracesn'ontpasdejonctionsdefluxdecontrôleinternes,ellespeuventêtreo ptimiséesentempslinéaireparuncompilateursimple(10).Ainsi,notreVMdetra ceseffectueefficacementlemêmed'optimisationsquiexigeraientuneanalysei nterprocéduraledansuncontexted'optimisationstatique.Celarendlatraceun outilattractifetefficacepourspécialiserpartypemêmelecodecomplexerichee nappelsdefonctions. Nousavonsimplémenté cestechniquespouruninterpréteurJavaScriptexistant,SpiderMonkey.Nousa ppelonslaVMdetracesrésultante TraceMonkey.TraceMonkeysupporte touteslesfonctionnalitésJavaScriptdeSpiderMonkey,avecuneaccélérationde 2xà20xpourlesprogrammestraçables. Cetarticleapportelescontributionssuivantes: •Nousexpliquonsunalgorithme pourformerdynamiquementdesarbresdetracesafindecouvrirunprogramm e,représentantlesbouclesimbriquéescommedesarbresdetracesimbriqués. •Nousexpliquonscommentgénérerspéculativementducodeefficacespéciali sépartypepourdestracesàpartirdeprogrammesenlangagedynamique. •Nousvalidonsnostechniquesdetracedansuneimplémentationbaséesurl'int erpréteurJavaScriptSpiderMonkey,réalisantdesaccélérationsde2xà20x surdenombreuxprogrammes. Lerestedecetarticleestorganisécommesuit.LaSection3estunevue d'ensembledelacompilationbaséesurlesarbresdetracesquenousutilisonspo urcaptureretcompilerlesrégionsdecodefréquemmentexécutées.DanslaSec tion4,nousdécrivonsnotreapprochepourcouvrirlesbouclesimbriquéesenuti lisantunnombre d'arbresdetracesindividuels.DanslaSection5,nousdécrivonsnotreapproche despécialisationpartypespéculativebaséesurlacompilationdetracesquenou sutilisonspourgénérercodemachineefficaceàpartirdetracesdebytecodeenr egistrées.Notreimplémentationd'uncompilateurdespécialisationdynamiqu edetypespourJavaScriptestdécritedanslaSection6.Lestravauxconnexessont discutésdanslaSection8.DanslaSection7,nousévaluonsnotrecompilateurdy namiquebasésur Figure1.Programmeexemple:cribled'Ératosthène.primes estinitialiséàuntableaude100 false valeursàl'entréedeceextraitdecode. Légende des symboles Interpréter Surcharge d'interprét ation Natif Boucle de bytecodes bord boucle/sortie froide/sur liste noire abandonner l'enregistre ment Surveiller trace compilée prête boucle/sort ie chaude Enregistrer Entrer Trace LIR Trace compilée terminer à l'en-tête de boucle bord de boucle avec mêmes types Compiler Exécuter Trace LIR Trace compilée sortie latérale, aucune trace existante sortie latérale vers trace existante Quitter Trace compilée Figure2.Machined'étatsdécrivantlesactivitésprincipalesdeTraceM onkeyetlesconditionsquiprovoquentdestransitionsversunenouvel leactivité.Danslacadresombre,TMexécuteJSsousformedetracesco mpilées.Danslescadresgrisclair,TMexécuteJSdansl'interpréteurst andard.Lescadresblancssontdesfraisgénéraux.Ainsi,pourmaximis erlesperformances,nousdevonsmaximiserletempspassédanslaca drelaplusfoncréetminimiserletempspassédanslescadresblancs.Le casidéalestuneboucleoùlestypesàlalimiteabouclesontlesmêmesq uelestypesàl'entrée-alorsTMpeutresterencodejatifjusqu'àcequela bouclesetermine. Unensemblederepèresindustriels.L'articleconclutaveclesconclusi onsdanslaSection9etuneperspectivesurtravauxfutursestprésenté edanslaSection10. 2.Aperçu : Exécution d'exemple de trace Cettesectionfournitunevued'ensembledenotresystèmeendécrivantcommen tTraceMonkeyexécuteunprogrammeexemple.Le programmeexemple,montrédanslaFigure1,calculeles100premiersnombres premiersavecdesbouclesimbriquées.LenarratifdoitêtreluaveclaFigure2,quid écritlesactivitésqueTraceMonkeyeffectueetquandiltransiteentrelesboucles. TraceMonkeycommencetoujoursàexécuterunprogrammedansl'interpré teurdebytecode.Chaque arrièredelimbedeboucleestunpointdetracepotentiel.Quandl'interpréteurfra nchitunelimite deboucle,TraceMonkeyinvoquele moniteur de trace,quipeutdéciderd'enregistreroud'exécuterunetracenative.Audébutdel' exécution,iln'yapasencoredetracescompilées,donclemoniteuredetracesco mptelenombredefoisquechaquelimite deboucleestexécutéejusqu'àcequ'uneboucledevienne chaude,actuellementaprès2franchissements.Notezquedelamanièredontno sbouclessontcompilées,lalimitedeboucleestfranchieavantd'entrerdanslabo ucle,doncledeuxièmefranchissementseproduitimmédiatementaprèslaprem ièreitération. Voicilaséquenced'événementsdécomposéeparitérationdelaboucleexter ne: v0 := ld state[748] st sp[0], v0 v1 := ld state[764] v2 := i2f(v1) st sp[8], v1 st sp[16], 0 v3 := ld v0[4] v4 := and v3, -4 v5 := eq v4, Array xf v5 v6 := js_Array_set(v0, v2, false) v7 := eq v6, 0 xt v7 mov edx, ebx(748) mov edi(0), edx mov esi, ebx(764) mov edi(8), esi mov edi(16), 0 mov eax, edx(4) and eax, -4 cmp eax, Array jne side_exit_1 sub esp, 8 push false push esi call js_Array_set add esp, 8 mov ecx, ebx test eax, eax je side_exit_2 ... side_exit_1: mov ecx, ebp(-4) mov esp, ebp jmp epilog //chargerpremiersdepuisenregistrementactivationtrace //stockerspremierspileinterpréteur //chargerkdepuisenregistrementactivationtrace //convertirkdeintendouble //stockerkpileinterpréteur //stockervraipileinterpréteur //chargermotdeclassepourobjetpremiers //masquerétiquettedeclassepourobjetpremiers //testersipremiersestuntableau //sortielatéralesiv5estfaux //appelerfonctionpourdéfinirélémenttableau //testervaleurretourappel //sortielatéralesijs_Array_setretournefaux. Figure3.ExtraitLIR pour le programme exemple.Voici le LIR enregistré pour la ligne 5 du programme exemple de la Figure 1. Le LIR encode la sémantique sous forme SSA en utilisant des variables temporaires. Le LIR encode également tous les stockages que l'interpréteur effectuerait sur sa pile de données. Parfois, ces stockages peuvent être optimisés car les emplacements de pile ne sont vivants qu'aux sorties vers l'interpréteur. Enfin, le LIR enregistre des gardes et des sorties latérales pour vérifier les hypothèses faites lors de cet enregistrement : que primes est un tableau et que l'appel pour définir ses éléments réussit. //chargerpremiersdepuisenregistrementactivationtrace //(*)stockerspremierspileinterpréteur //chargerkdepuisenregistrementactivationtrace //(*)stockerkpileinterpréteur //(*)stockervraipileinterpréteur //(*)chargermotdeclassepourobjetpremiers //(*)masquerétiquettedeclassepourobjetpremiers //(*)testersipremiersestuntableau //(*)sortielatéralesipremiersn'estpasuntableau //augmenterpilepourconventionalignementappel //pousserdernierargumentpourappel //pousserpremierargumentpourappel //appelerfonctionpourdéfinirélémenttableau //nettoyerespacesupplémentairepile //(*)crééparallocateurderegistres //(*)testervaleurretourdejs_Array_set //(*)sortielatéraleenéchecd'appel //restaurerecx //restaureresp //sauteràinstructionret Figure4.Extrait x86 pour le programme exemple.Voici le code x86 compilé à partir de l'extrait LIR de la Figure 3. La plupart des instructions LIR se compilent en une seule instruction x86. Les instructions marquées de(*)seraient omises par un compilateur idéalisé qui saurait qu'aucune des sorties latérales ne serait jamais empruntée. Les 17 instructions générées par le compilateur se comparent favorablement aux 100+ instructions que l'interpréteur exécuterait pour le même extrait de code, y compris 4 sauts indirects. i=2.Voici la première itération de la boucle externe. La boucle sur les lignes 4-5 devient chaude lors de sa deuxième itération, donc TraceMonkey entre en mode d'enregistrement à la ligne 4. En mode d'enregistrement, TraceMonkey enregistre le code le long de la trace dans une représentation intermédiaire de bas niveau que nous appelons LIR. La trace LIR encode toutes les opérations effectuées et les types de tous les opérandes. La trace LIR encode également des gardes, qui sont des vérifications qui confirment que le flux de contrôle et les types sont identiques à ceux observés lors de l'enregistrement de la trace. Ainsi, lors des exécutions ultérieures, si et seulement si toutes les gardes sont passées, la trace possède la sémantique de programme requise. TraceMonkey arrête l'enregistrement lorsque l'exécution revient à l'en-tête de la boucle ou sort de la boucle. Dans ce cas, l'exécution revient à l'en-tête de la boucle à la ligne 4. Une fois l'enregistrement terminé, TraceMonkey compile la trace en code natif en utilisant les informations de type enregistrées pour l'optimisation. Le résultat est un fragment de code natif qui peut être entré si le PC de l'interpréteur et les types des valeurs correspondent à ceux observés lors du démarrage de l'enregistrement de la trace. La première trace dans notre exemple,T 45, couvre les lignes 4 et 5. Cette trace peut être entrée si le PC est à la ligne 4,i et k sont des entiers, et primes est un objet. Après avoir compiléT 45, TraceMonkey retourne à l'interpréteur et boucle jusqu'à la ligne 1. i=3.Maintenant, l'en-tête de boucle à la ligne 1 est devenu chaud, donc TraceMonkey commence l'enregistrement. Lorsque l'enregistrement atteint la ligne 4, TraceMonkey observe qu'il a atteint un en-tête de boucle interne qui a déjà une trace compilée, donc TraceMonkey tente d'imbriquer la boucle interne dans la trace actuelle. La première étape consiste à appeler la trace interne comme une sous-routine. Cela exécute la boucle à la ligne 4 jusqu'à son terme, puis retourne à l'enregistreur. TraceMonkey vérifie que l'appel a réussi, puis enregistre l'appel à la trace interne dans le cadre de la trace actuelle. L'enregistrement continue jusqu'à ce que l'exécution atteigne la ligne 1, et à ce moment-là, TraceMonkey termine et compile une trace pour la boucle externe,T 16. 3.1 Traces i=4.À cette itération, TraceMonkey appelle T 16. Parce que i=4, le ifà la ligne 2 est pris. Cette branche n'a pas été prise dans la trace originale, donc cela fait échouer T 16à une garde et prendre une sortie latérale. La sortie n'est pas encore chaude, donc TraceMonkey retourne à l'interpréteur, qui exécute l'instruction continue. i=5.TraceMonkey appelle T 16, qui à son tour appelle la trace imbriquée T 45.T 16 boucle vers son propre en-tête, commençant l'itération suivante sans jamais retourner au moniteur. i=6.À cette itération, la sortie latérale à la ligne 2 est prise à nouveau. Cette fois, la sortie latérale devient chaude, donc une trace T 23,1 est enregistrée qui couvre la ligne 3 et retourne à l'en-tête de la boucle. Ainsi, la fin de T 23,1 saute directement au début de T 16. La sortie latérale est corrigée de sorte que lors des itérations futures, elle saute directement àT 23,1. À ce stade, TraceMonkey a compilé suffisamment de traces pour couvrir toute la structure de boucle imbriquée, donc le reste du programme s'exécute entièrement en code natif. Une trace enregistre toutes ses valeurs intermédiaires dans une petite zone d'enregistrement d'activation. Pour rendre les accès aux variables rapides sur la trace, la trace importe également les variables locales et globales en les désencapsulant et en les copiant dans son enregistrement d'activation. Ainsi, la trace peut lire et écrire ces variables avec de simples chargements et stockages à partir d'un enregistrement d'activation natif, indépendamment du mécanisme d'encapsulation utilisé par l'interpréteur. Lorsque la trace se termine, la VM encapsule les valeurs de cet emplacement de stockage natif et les recopie dans les structures de l'interpréteur. Pour chaque branche de flux de contrôle dans le programme source, l'enregistreur génère des instructions LIR de sortie conditionnelle. Ces instructions sortent de la trace si le flux de contrôle requis est différent de ce qu'il était lors de l'enregistrement de la trace, garantissant que les instructions de la trace ne sont exécutées que si elles sont censées l'être. Nous appelons ces instructions instructions de garde. La plupart de nos traces représentent des boucles et se terminent par l'instruction LIR spéciale boucle. Il s'agit simplement d'un branchement inconditionnel vers le haut de la trace. Ces traces ne retournent que via des gardes. Maintenant, nous décrivons les optimisations clés qui sont effectuées dans le cadre de l'enregistrement de la LIR. Toutes ces optimisations réduisent des constructions complexes de langage dynamique à des constructions typées simples en se spécialisant pour la trace actuelle. Chaque optimisation nécessite des instructions de garde pour vérifier leurs hypothèses sur l'état et sortir de la trace si nécessaire. 3.Arbres de traces Dans cette section, nous décrivons les traces, les arbres de traces et comment ils sont formés à l'exécution. Bien que nos techniques s'appliquent à tout interpréteur de langage dynamique, nous les décrirons en supposant un interpréteur de bytecode pour garder l'exposé simple. Spécialisation de type. Toutes les primitives LIR s'appliquent à des opérandes de types spécifiques. Ainsi, les traces LIR sont nécessairement spécialisées par type, et un compilateur peut facilement produire une traduction qui ne nécessite aucune répartition de type. Un interpréteur de bytecode typique transporte des bits d'étiquette avec chaque valeur, et pour effectuer une opération, doit vérifier les bits d'étiquette, répartir dynamiquement, masquer les bits d'étiquette pour récupérer la valeur non étiquetée, effectuer l'opération, puis réappliquer les étiquettes. La LIR omet tout sauf l'opération elle-même. Un problème potentiel est que certaines opérations peuvent produire des valeurs de types imprévisibles. Par exemple, lire une propriété d'un objet pourrait donner une valeur de n'importe quel type, pas nécessairement le type observé lors de l'enregistrement. L'enregistreur émet des instructions de garde qui sortent conditionnellement si l'opération produit une valeur d'un type différent de celui observé lors de l'enregistrement. Ces instructions de garde garantissent que tant que l'exécution est sur la trace, les types des valeurs correspondent à ceux de la trace typée. Lorsque la VM observe une sortie latérale le long d'une telle garde de type, une nouvelle trace typée est enregistrée débutant à l'emplacement de la sortie latérale, capturant le nouveau type de l'opération en question. Spécialisation de la représentation : objets.En JavaScript, la sémantique de recherche de noms est complexe et potentiellement coûteuse car elle inclut des fonctionnalités comme l'héritage d'objets et eval. Pour évaluer une expression de lecture de propriété d'objet comme o.x, l'interpréteur doit rechercher la carte des propriétés de o et de tous ses prototypes et parents. Les cartes de propriétés peuvent être implémentées avec différentes structures de données (par exemple, des tables de hachage par objet ou des tables de hachage partagées), donc le processus de recherche doit également répartir sur la représentation de chaque objet trouvé lors de la recherche. TraceMonkey peut simplement observer le résultat du processus de recherche et enregistrer la LIR la plus simple possible pour accéder à la valeur de la propriété. Par exemple, la recherche pourrait trouver la valeur de o.x dans le prototype de o, qui utilise une représentation de table de hachage partagée qui place x dans l'emplacement 2 d'un vecteur de propriétés. Alors l'enregistreur peut générer une LIR qui lit o.x avec seulement deux ou trois chargements : un pour obtenir le prototype, éventuellement un pour obtenir le vecteur de valeurs de propriétés, et un de plus pour obtenir l'emplacement 2 du vecteur. C'est une énorme simplification et accélération par rapport au code d'interpréteur original. Les relations d'héritage et les représentations d'objets peuvent changer pendant l'exécution, donc le code simplifié nécessite des instructions de garde qui garantissent que la représentation de l'objet est la même. Dans TraceMonkey, la représentation des objets Une trace est simplement un chemin de programme, qui peut traverser les limites d'appels de fonctions. TraceMonkey se concentre sur les traces de boucles, qui débutent à une arête de boucle et représentent une seule itération à travers la boucle associée. Semblable à un bloc de base étendu, une trace n'est entrée que par le haut, mais peut avoir plusieurs sorties. Contrairement à un bloc de base étendu, une trace peut contenir des nœuds de jonction. Cependant, comme une trace ne suit toujours qu'un seul chemin à travers le programme original, les nœuds de jonction ne sont pas reconnaissables en tant que tels dans une trace et ont un seul nœud prédécesseur comme les nœuds réguliers. Une trace typée est une trace annotée avec un type pour chaque variable (y compris les temporaires) sur la trace. Une trace typée a également une carte de types d'entrée donnant les types requis pour les variables utilisées sur la trace avant qu'elles ne soient définies. Par exemple, une trace pourrait avoir une carte de types (x:int, b:boolean), ce qui signifie que la trace ne peut être entrée que si la valeur de la variable x est de type int et la valeur de b est de type boolean. La carte de types d'entrée ressemble beaucoup à la signature d'une fonction. Dans cet article, nous ne discutons que des traces de boucles typées, et nous y ferons référence simplement comme des « traces ». La propriété clé des traces de boucles typées est qu'elles peuvent être compilées en code machine efficace en utilisant les mêmes techniques que celles utilisées pour les langages typés. Dans TraceMonkey, les traces sont enregistrées dans une LIR SSA de type trace LIR(représentation intermédiaire de bas niveau). Dans la SSA de type trace (ou TSSA), les nœuds phi n'apparaissent qu'au point d'entrée, qui est atteint à la fois à l'entrée et via les arêtes de boucle. Les primitives LIR importantes sont les valeurs constantes, les chargements et stockages en mémoire (par adresse et décalage), les opérateurs entiers, les opérateurs à virgule flottante, les appels de fonction et les sorties conditionnelles. Les conversions de type, comme d'entier à double, sont représentées par des appels de fonction. Cela rend la LIR utilisée par TraceMonkey indépendante du système de types concret et des règles de conversion de type du langage source. Les opérations LIR sont suffisamment génériques pour que le compilateur backend soit indépendant du langage. La figure 3 montre un exemple de trace LIR. Les interpréteurs de bytecode représentent généralement les valeurs dans diverses structures de données complexes (par exemple, des tables de hachage) dans un format encapsulé (c'est-à-dire avec des bits de type attachés). Comme une trace est destinée à représenter un code efficace qui élimine toute cette complexité, nos traces opèrent sur des valeurs non encapsulées dans des variables simples et des tableaux autant que possible. Les représentations se voient attribuer une clé entière appelée la forme de l'objet. Ainsi, la garde est une simple vérification d'égalité sur la forme de l'objet. Spécialisation des représentations : nombres.JavaScript n'a pas de type entier, seulement un type Number qui est l'ensemble des nombres à virgule flottante 64 bits IEEE-754 (« doubles »). Mais de nombreux opérateurs JavaScript, en particulier les accès aux tableaux et les opérateurs bit à bit, fonctionnent réellement sur des entiers, donc ils convertissent d'abord le nombre en un entier, puis convertissent tout résultat entier en un double.1 Clairement, une VM JavaScript qui veut être rapide doit trouver un moyen d'opérer directement sur des entiers et d'éviter ces conversions. Dans TraceMonkey, nous supportons deux représentations pour les nombres : les entiers et les doubles. L'interpréteur utilise les représentations entières autant que possible, en basculant pour les résultats qui ne peuvent être représentés que comme des doubles. Lorsqu'une trace est démarrée, certaines valeurs peuvent être importées et représentées comme des entiers. Certaines opérations sur les entiers nécessitent des gardes. Par exemple, l'addition de deux entiers peut produire une valeur trop grande pour la représentation entière. Intégration de fonctions.Les traces LIR peuvent traverser les limites des fonctions dans les deux directions, réalisant ainsi l'intégration de fonctions. Des instructions de déplacement doivent être enregistrées pour l'entrée et la sortie de la fonction afin de copier les arguments entrants et les valeurs de retour sortantes. Ces instructions de déplacement sont ensuite optimisées par le compilateur en utilisant la propagation de copies. Afin de pouvoir retourner à l'interpréteur, la trace doit également générer du LIR pour enregistrer qu'un cadre d'appel a été entré et quitté. Le LIR d'entrée et de sortie de cadre sauvegarde juste assez d'informations pour permettre de restaurer plus tard la pile d'appels de l'interpréteur et est beaucoup plus simple que le code d'appel standard de l'interpréteur. Si la fonction entrée n'est pas constante (ce qui en JavaScript inclut tout appel par nom de fonction), l'enregistreur doit également émettre du LIR pour garantir que la fonction est la même. Gardes et sorties latérales.Chaque optimisation décrite ci-dessus nécessite une ou plusieurs gardes pour vérifier les hypothèses faites lors de l'optimisation. Une garde est simplement un groupe d'instructions LIR qui effectue un test et une sortie conditionnelle. La sortie bifurque vers une sortie latérale, un petit morceau de LIR hors trace qui retourne un pointeur vers une structure décrivant la raison de la sortie ainsi que le PC de l'interpréteur au point de sortie et toute autre donnée nécessaire pour restaurer les structures d'état de l'interpréteur. Abandons.Certaines constructions sont difficiles à enregistrer dans des traces LIR. Par exemple,eval ou les appels à des fonctions externes peuvent modifier l'état du programme de manière imprévisible, rendant difficile pour le traceur de connaître la carte de types actuelle afin de continuer le traçage. Une implémentation de traçage peut également avoir un certain nombre d'autres limitations, par exemple, un appareil à faible mémoire peut limiter la longueur des traces. Lorsqu'une situation se produit qui empêche l'implémentation de continuer l'enregistrement de la trace, l'implémentation abandonne l'enregistrement de la trace et retourne au moniteur de traces. Démarrage d'un arbre.Les arbres commencent toujours aux en-têtes de boucle, car ils sont un endroit naturel pour rechercher des chemins chauds. Dans TraceMonkey, les en-têtes de boucle sont faciles à détecter - le compilateur de bytecode garantit qu'un bytecode est un en-tête de boucle s'il est la cible d'une branche arrière. TraceMonkey démarre un arbre lorsqu'un en-tête de boucle donné a été exécuté un certain nombre de fois (2 dans l'implémentation actuelle). Démarrer un arbre signifie simplement commencer à enregistrer une trace pour le point et la carte de types actuels et marquer la trace comme la racine d'un arbre. Chaque arbre est associé à un en-tête de boucle et une carte de types, donc il peut y avoir plusieurs arbres pour un en-tête de boucle donné. Fermeture de la boucle.L'enregistrement d'une trace peut se terminer de plusieurs manières. Idéalement, la trace atteint l'en-tête de boucle où elle a commencé avec la même carte de types qu'à l'entrée. C'est ce qu'on appelle une itération de boucle type-stable. Dans ce cas, la fin de la trace peut sauter directement au début, car toutes les représentations de valeurs sont exactement comme nécessaires pour entrer dans la trace. Le saut peut même ignorer le code habituel qui copierait l'état à la fin de la trace et le recopierait dans l'enregistrement d'activation de la trace pour entrer dans une trace. Dans certains cas, la trace peut atteindre l'en-tête de boucle avec une carte de types différente. Ce scénario est parfois observé pour la première itération d'une boucle. Certaines variables à l'intérieur de la boucle peuvent initialement être undefined, avant d'être définies avec un type concret pendant la première itération de la boucle. Lors de l'enregistrement d'une telle itération, l'enregistreur ne peut pas relier la trace à son propre en-tête de boucle car elle est type-instable. Au lieu de cela, l'itération est terminée avec une sortie latérale qui échouera toujours et retournera à l'interpréteur. En même temps, une nouvelle trace est enregistrée avec la nouvelle carte de types. Chaque fois qu'une trace type-instable supplémentaire est ajoutée à une région, sa carte de types de sortie est comparée à la carte d'entrée de toutes les traces existantes au cas où elles se compléteraient mutuellement. Avec cette approche, nous sommes capables de couvrir les itérations de boucle type-instables tant qu'elles forment éventuellement un équilibre stable. Enfin, la trace peut quitter la boucle avant d'atteindre l'en-tête de boucle, par exemple parce que l'exécution atteint une instruction break ou return. Dans ce cas, la VM termine simplement la trace avec une sortie vers le moniteur de traces. Comme mentionné précédemment, nous pouvons choisir spéculativement de représenter certaines valeurs de type Number comme des entiers sur la trace. Nous faisons cela lorsque nous observons que des variables de type Number contiennent une valeur entière à l'entrée de la trace. Si pendant l'enregistrement de la trace la variable reçoit de manière inattendue une valeur non entière, nous devons élargir le type de la variable en un double. En conséquence, la trace enregistrée devient intrinsèquement type-instable car elle commence avec une valeur entière mais se termine avec une valeur double. Cela représente une mauvaise spéculation, car à l'entrée de la trace nous avons spécialisé la valeur de type Number en un entier, en supposant qu'à la bordure de la boucle nous trouverions à nouveau une valeur entière dans la variable, nous permettant de fermer la boucle. Pour éviter de futures échecs spéculatifs impliquant cette variable, et pour obtenir une trace type-stable, nous notons le fait que la variable en question a été observée comme contenant parfois des valeurs non entières dans une structure de données consultative que nous appelons l'« oracle ». Lors de la compilation de boucles, nous consultons l'oracle avant de spécialiser les valeurs en entiers. La spéculation vers des entiers n'est effectuée que si aucune information défavorable n'est connue de l'oracle concernant cette variable particulière. Chaque fois que nous compilons accidentellement une boucle qui est type-instable en raison d'une mauvaise spéculation d'une variable de type Number, nous déclenchons immédiatement l'enregistrement d'une nouvelle trace, qui, basée sur les informations mises à jour de l'oracle, commencera avec une valeur double et deviendra ainsi type-stable. Extension d'un arbre.Les sorties latérales mènent à différents chemins à travers la boucle, ou à des chemins avec différents types ou représentations. Ainsi, pour couvrir complètement la boucle, la VM doit enregistrer des traces commençant à toutes les sorties latérales. Ces traces sont enregistrées de manière très similaire aux traces racines : il y a un compteur pour chaque sortie latérale, et lorsque le compteur atteint un seuil de chaleur, l'enregistrement commence. L'enregistrement s'arrête exactement comme pour la trace racine, en utilisant l'en-tête de boucle de la trace racine comme cible à atteindre. 3.2 Arbres de trace Les boucles particulièrement simples, notamment celles où le flux de contrôle, les types de valeurs, les représentations de valeurs et les fonctions intégrées sont tous invariants, peuvent être représentées par une seule trace. Mais la plupart des boucles présentent au moins une certaine variation, et le programme emprunte donc des sorties latérales depuis la trace principale. Lorsqu'une sortie latérale devient chaude, TraceMonkey démarre une nouvelle trace de brancheà partir de ce point et corrige la sortie latérale pour sauter directement vers cette trace. De cette manière, une seule trace s'étend à la demande en un arbre de tracesà entrée unique et sorties multiples. Cette section explique comment les arbres de traces sont formés pendant l'exécution. L'objectif est de former des arbres de traces pendant l'exécution qui couvrent tous les chemins chauds du programme. 1 Les tableaux sont en fait pires que cela : si la valeur d'index est un nombre, elle doit être convertie d'un double en une chaîne pour l'opérateur d'accès aux propriétés, puis en un entier en interne pour l'implémentation du tableau. T Trace
2 Trace
1 Trace
2 Trace
1 Trace
2 Trace
1 Trace
3 (a) (b) (c) Notre implémentation n'étend pas du tout les sorties latérales. Elle ne s'étend que si la sortie latérale est pour une branche de flux de contrôle, et seulement si la sortie latérale ne quitte pas la boucle. En particulier, nous ne voulons pas étendre un arbre de traces le long d'un chemin qui mène à une boucle externe, car nous voulons couvrir ces chemins dans un arbre externe via l'imbrication d'arbres. Ancre d'Arbre Tronc Trace Trace d'Ancre Branche Trace Garde Sortie Latérale 3.3Liste noire Parfois, un programme suit un chemin qui ne peut pas être compilé en une trace, généralement en raison de limitations dans l'implémentation. TraceMonkey ne prend actuellement pas en charge l'enregistrement du lancement et de la capture d'exceptions arbitraires. Ce compromis de conception a été choisi car les exceptions sont généralement rares en JavaScript. Cependant, si un programme choisit d'utiliser les exceptions de manière intensive, nous subirions soudainement une surcharge d'exécution punitive si nous essayons à plusieurs reprises d'enregistrer une trace pour ce chemin et échouons à plusieurs reprises, car nous abandonnons le traçage chaque fois que nous observons une exception levée. En conséquence, si une boucle chaude contient des traces qui échouent toujours, la VM pourrait potentiellement s'exécuter beaucoup plus lentement que l'interpréteur de base : la VM passe du temps à essayer d'enregistrer des traces, mais n'est jamais capable d'en exécuter aucune. Pour éviter ce problème, chaque fois que la VM est sur le point de commencer le traçage, elle doit essayer de prédire si elle terminera la trace. Notre algorithme de prédiction est basé sur la mise sur liste noire des traces qui ont été essayées et ont échoué. Lorsque la VM échoue à terminer une trace commençant à un point donné, la VM enregistre qu'un échec s'est produit. La VM définit également un compteur pour qu'elle n'essaie pas d'enregistrer une trace commençant à ce point avant qu'il ne soit passé quelques fois de plus (32 dans notre implémentation). Ce compteur de recul donne des conditions temporaires qui empêchent le traçage d'avoir une chance de se terminer. Par exemple, une boucle peut se comporter différemment lors du démarrage que lors de son exécution en régime permanent. Après un nombre donné d'échecs (2 dans notre implémentation), la VM marque le fragment comme mis sur liste noire, ce qui signifie que la VM ne recommencera jamais l'enregistrement à ce point. Après avoir implémenté cette stratégie de base, nous avons observé que pour les petites boucles mises sur liste noire, le système peut passer un temps notable simplement à trouver le fragment de boucle et à déterminer qu'il a été mis sur liste noire. Nous évitons maintenant ce problème en modifiant le bytecode. Nous définissons un bytecode no-op supplémentaire qui indique un en-tête de boucle. La VM appelle le moniteur de traces chaque fois que l'interpréteur exécute un no-op d'en-tête de boucle. Pour mettre un fragment sur liste noire, nous remplaçons simplement le no-op d'en-tête de boucle par un no-op régulier. Ainsi, l'interpréteur n'appellera plus jamais le moniteur de traces. Il y a un problème connexe que nous n'avons pas encore résolu, qui se produit lorsqu'une boucle remplit toutes ces conditions : •La VM peut former au moins une trace racine pour la boucle. •Il y a au moins une sortie latérale chaude pour laquelle la VM ne peut pas terminer une trace. •Le corps de la boucle est court. Dans ce cas, la VM passera à plusieurs reprises l'en-tête de boucle, cherchera une trace, la trouvera, l'exécutera et reviendra à l'interpréteur. Avec un corps de boucle court, la surcharge de recherche et d'appel de la trace est élevée et entraîne des performances encore plus lentes que l'interpréteur de base. Jusqu'à présent, dans cette situation, nous avons amélioré l'implémentation pour que la VM puisse terminer la trace de branche. Mais il est difficile de garantir que cette situation ne se produira jamais. En tant que travail futur, cette situation pourrait être évitée en détectant et en mettant sur liste noire les boucles pour lesquelles l'appel de trace moyen exécute peu de bytecodes avant de revenir à l'interpréteur. Figure5.Un arbre avec deux traces, une trace de tronc et une trace de branche. La trace de tronc contient une garde à laquelle une trace de branche a été attachée. La trace de branche contient une garde qui peut échouer et déclencher une sortie latérale. Le tronc et la trace de branche bouclent tous deux vers l'ancre de l'arbre, qui est le début de l'arbre de traces. Nombre Booléen Nombre Booléen Nombre Nombre Booléen Nombre Fermé Lié Lié Lié Nombre Booléen Chaîne Chaîne Chaîne Nombre Chaîne Chaîne Lié Lié Fermé Lié Figure6.Nous traitons les boucles à type instable en permettant aux traces de compiler qui ne peuvent pas boucler sur elles-mêmes en raison d'une incompatibilité de type. À mesure que ces traces s'accumulent, nous tentons de connecter leurs arêtes de boucle pour former des groupes d'arbres de traces qui peuvent s'exécuter sans avoir à sortir latéralement vers l'interpréteur pour couvrir les cas de type inhabituels. Ceci est particulièrement important pour les arbres de traces imbriqués où un arbre externe tente d'appeler un arbre interne (ou dans ce cas une forêt d'arbres internes), car les boucles internes ont fréquemment des valeurs initialement indéfinies qui changent de type vers une valeur concrète après la première itération.à travers la boucle interne,{i 2,i 3,i 5,α}.Leαsymbole est utilisé pour indiquer que la trace boucle vers l'ancre de l'arbre. Lorsque l'exécution quitte la boucle interne, la conception de base a deux choix. Premièrement, le système peut arrêter le traçage et abandonner la compilation de la boucle externe, une solution clairement indésirable. L'autre choix est de continuer le traçage, en compilant des traces pour la boucle externe à l'intérieur de l'arbre de traces de la boucle interne. Par exemple, le programme peut sortir ài 5 et enregistrer une trace de branche qui incorpore la boucle externe :{i 5,i 7,i 1,i 6,i 7,i 1,α}. Plus tard, le programme peut prendre l'autre branche ài 2 puis sortir, en enregistrant une autre trace de branche incorporant la boucle externe : {i 2,i 4,i 5,i 7,i 1,i 6,i 7,i 1,α}.Ainsi, la boucle externe est enregistrée et compilée deux fois, et les deux copies doivent être conservées dans le cache de traces. 4.Formation d'arborescence de traces imbriquées La figure7 montre la compilation de base d'un arbre de traces (11) appliquée à une boucle imbriquée où la boucle interne contient deux chemins. Habituellement, la boucle interne (avec l'en-tête ài 2) devient chaude en premier, et un arbre de traces est enraciné à ce point. Par exemple, la première trace enregistrée peut être un cycle i2 i3 i4 i5 i1 i6 i7 t1 t2 (a) (b) i2 i3 i1 i6 i4 i5 t2 t1 t4 Arbre externe Arbre imbriqué Appel d'arbre Arbre imbriqué Garde de sortie Garde de sortie Figure8.Graphe de flot de contrôle d'une boucle avec deux boucles imbriquées (à gauche) et sa configuration d'arbre de traces imbriqué (à droite). L'arbre externe appelle les deux arbres de traces imbriqués internes et place des gardes à leurs emplacements de sortie latérale. La boucle est entrée avec m cartes de types différentes (en moyenne géométrique), puis nous compilons O(m k)copies de la boucle la plus interne. Tant que m est proche de 1, les arbres de traces résultants seront gérables. Un détail important est que l'appel à l'arbre de traces interne doit agir comme un site d'appel de fonction : il doit retourner au même point à chaque fois. L'objectif de l'imbrication est de rendre les boucles interne et externe indépendantes ; ainsi, lorsque l'arbre interne est appelé, il doit sortir au même point dans l'arbre externe à chaque fois avec la même carte de types. Comme nous ne pouvons pas réellement garantir cette propriété, nous devons placer une garde après l'appel, et sortir latéralement si la propriété n'est pas vérifiée. Une raison courante pour laquelle l'arbre interne ne retourne pas au même point serait si l'arbre interne empruntait une nouvelle sortie latérale pour laquelle il n'avait jamais compilé de trace. À ce stade, le PC de l'interpréteur se trouve dans l'arbre interne, donc nous ne pouvons pas continuer l'enregistrement ou l'exécution de l'arbre externe. Si cela se produit pendant l'enregistrement, nous abandonnons la trace externe pour donner à l'arbre interne une chance de terminer sa croissance. Une exécution future de l'arbre externe pourrait alors se terminer correctement et enregistrer un appel à l'arbre interne. Si une sortie latérale de l'arbre interne se produit pendant l'exécution d'une trace compilée pour l'arbre externe, nous quittons simplement la trace externe et commençons à enregistrer une nouvelle branche dans l'arbre interne. Figure7.Graphe de contrôle de flux d'une boucle imbriquée avec une instruction if à l'intérieur de la boucle la plus interne (a). Un arbre interne capture la boucle interne et est imbriqué dans un arbre externe qui « appelle » l'arbre interne. L'arbre interne retourne à l'arbre externe une fois qu'il en sort par sa condition de garde de boucle (b). En général, si les boucles sont imbriquées jusqu'à une profondeur k, et que chaque boucle a n chemins (en moyenne géométrique), cette stratégie naïve produit O(n k)traces, ce qui peut facilement remplir le cache de traces. Afin d'exécuter efficacement des programmes avec des boucles imbriquées, un système de traçage a besoin d'une technique pour couvrir les boucles imbriquées avec du code natif sans duplication exponentielle de traces. 4.1 Algorithme d'imbrication L'idée clé est que si chaque boucle est représentée par son propre arbre de trace, le code de chaque boucle peut être contenu uniquement dans son propre arbre, et les chemins de la boucle externe ne seront pas dupliqués. Un autre fait essentiel est que nous ne traçons pas des bytecodes arbitraires qui pourraient avoir des graphes de flux de contrôle irréductibles, mais plutôt des bytecodes produits par un compilateur pour un langage à flux de contrôle structuré. Ainsi, étant donné deux arêtes de boucle, le système peut facilement déterminer si elles sont imbriquées et laquelle est la boucle interne. En utilisant cette connaissance, le système peut compiler les boucles interne et externe séparément, et faire en sorte que les traces de la boucle externe appellent l'arbre de trace de la boucle interne. L'algorithme pour construire des arbres de trace imbriqués est le suivant. Nous commençons à tracer aux en-têtes de boucle exactement comme dans le système de traçage de base. Lorsque nous sortons d'une boucle (détectée en comparant le PC de l'interpréteur avec la plage donnée par l'arête de boucle), nous arrêtons la trace. L'étape clé de l'algorithme se produit lorsque nous enregistrons une trace pour la boucle L R(R pour la boucle en cours d'enregistrement) et que nous atteignons l'en-tête d'une boucle différente L O(O pour l'autre boucle). Notez que L O doit être une boucle interne de L R car nous arrêtons la trace lorsque nous sortons d'une boucle. •Si L O possède un arbre de trace compilé avec correspondance de type, nous appelons L O en tant qu'arbre de trace imbriqué. Si l'appel réussit, nous enregistrons l'appel dans la trace pour L R. Lors des exécutions futures, la trace pour L R appellera directement la trace interne. 4.2 Liste noire avec imbrication L'algorithme de blacklistage nécessite une modification pour bien fonctionner avec l'imbrication. Le problème est que les traces de la boucle externe avortent souvent au démarrage (parce que l'arbre interne n'est pas disponible ou prend une sortie latérale), ce qui les ferait être rapidement blacklistées par l'algorithme de base. L'observation clé est que lorsqu'une trace externe avorte parce que l'arbre interne n'est pas prêt, il s'agit probablement d'une condition temporaire. Ainsi, nous ne devrions pas compter ces avortements vers le blacklistage tant que nous sommes capables de construire davantage de traces pour l'arbre interne. Dans notre implémentation, lorsqu'un arbre externe avorte sur l'arbre interne, nous incrémentons le compteur de blacklistage de l'arbre externe comme d'habitude et nous reculons sur sa compilation. Lorsque l'arbre interne termine une trace, nous décrémentons le compteur de blacklistage sur la boucle externe, "pardonnant" ainsi à la boucle externe d'avoir avorté précédemment. Nous annulons également les reculs afin que l'arbre externe puisse immédiatement commencer à essayer de compiler la prochaine fois que nous l'atteignons. •Si L O n'a pas encore d'arbre de trace compilé correspondant au type, nous devons l'obtenir avant de pouvoir continuer. Pour ce faire, nous abandonnons simplement l'enregistrement de la première trace. Le moniteur de trace verra l'en-tête de la boucle interne et commencera immédiatement à enregistrer la boucle interne.2 Si toutes les boucles d'un nid sont stables en termes de type, alors l'imbrication des boucles ne crée aucune duplication. Sinon, si les boucles sont imbriquées à une profondeur k, et que chaque 5. Optimisation de l'arbre de trace 2 Cette section explique comment une trace enregistrée est traduite en une trace de code machine optimisée. Le sous-système de compilation de traces, NANOJIT, est séparé de la machine virtuelle et peut être utilisé pour d'autres applications. Au lieu d'abandonner l'enregistrement externe, nous pourrions en principe simplement suspendre l'enregistrement, mais cela nécessiterait que l'implémentation soit capable d'enregistrer plusieurs traces simultanément, ce qui compliquerait l'implémentation, tout en ne sauvant que quelques itérations dans l'interpréteur. 5.1Optimisations Étiquet te JSType Description Représentation entière sur 31 bits Pointeur vers un handle d'objet JS Pointeur vers un handle de double Pointeur vers un handle de chaîne JS Énumération pour null, undefined, true, false xx1 nombre Comme les traces sont sous forme SSA et n'ont ni points de jonction niφ nœuds, certaines optimisations sont faciles à implémenter. Pour obtenir de bonnes performances de démarrage, les optimisations doivent s'exécuter rapidement, nous avons donc choisi un petit ensemble d'optimisations. Nous avons implémenté les optimisations sous forme de filtres en pipeline afin qu'ils puissent être activés et désactivés indépendamment, et pourtant tous s'exécutent en seulement deux passages de boucle sur la trace : un en avant et un en arrière. Chaque fois que l'enregistreur de trace émet une instruction LIR, l'instruction est immédiatement passée au premier filtre du pipeline avant. Ainsi, les optimisations du filtre avant sont effectuées au fur et à mesure que la trace est enregistrée. Chaque filtre peut passer chaque instruction inchangée au filtre suivant, écrire une instruction différente pour le filtre suivant, ou n'écrire aucune instruction du tout. Par exemple, le filtre de pliage de constantes peut remplacer une instruction de multiplication comme v 13:=mul 3,1000 par une instruction constante v 13=3000. Nous appliquons actuellement quatre filtres avant : •Sur les ISA sans instructions à virgule flottante, un filtre soft-float convertit les instructions LIR à virgule flottante en séquences d'instructions entières. •CSE (élimination des sous-expressions communes), •simplification d'expressions, y compris le pliage de constantes et quelques identités algébriques (par exemple,a−a=0), et •simplification d'expressions spécifiques à la sémantique du langage source, principalement des identités algébriques qui permettent DOUBLE d'être remplacé par INT. Par exemple, le LIR qui convertit un INT en DOUBLE et ensuite inversement serait supprimé par ce filtre. Lorsque l'enregistrement de la trace est terminé, nanojit exécute les filtres d'optimisation arrière. Ceux-ci sont utilisés pour les optimisations qui nécessitent une analyse de programme arrière. Lors de l'exécution des filtres arrière, nanojit lit une instruction LIR à la fois, et les lectures sont passées à travers le pipeline. Nous appliquons actuellement trois filtres arrière : •Élimination des magasins de pile de données mortes. La trace LIR encode de nombreux magasins vers des emplacements dans la pile de l'interpréteur. Mais ces valeurs ne sont jamais relues avant de quitter la trace (par l'interpréteur ou une autre trace). Ainsi, les magasins vers la pile qui sont écrasés avant la prochaine sortie sont morts. Les magasins vers des emplacements qui sont en dehors du sommet de la pile de l'interpréteur lors des sorties futures sont également morts. •Élimination des magasins de pile d'appel morts. C'est la même optimisation que ci-dessus, sauf qu'elle est appliquée à la pile d'appel de l'interpréteur utilisée pour l'inlining des appels de fonction. •Élimination de code mort. Cela élimine toute opération qui stocke une valeur qui n'est jamais utilisée. Après qu'une instruction LIR a été lue avec succès ("tirée") du pipeline de filtres arrière, le générateur de code de nanojit émet une ou plusieurs instructions machine natives pour celle-ci. 000objet 010nombre 100chaîne 110booléen null, ou undefined Figure9.Valeurs étiquetées dans l'interpréteur JS SpiderMonkey. Le test des balises, le déballage (extraction de la valeur non balisée) et le ballage (création de valeurs balisées) sont des coûts significatifs. Éviter ces coûts est un avantage clé du traçage. L'heuristique sélectionne v avec le minimum v m. La motivation est que cela libère un registre aussi longtemps que possible étant donné un seul déversement. Si nous devons déverser une valeur v sà ce point, nous générons le code de restauration juste après le code de l'instruction actuelle. Le code de déversement correspondant est généré juste après le dernier point où v s a été utilisé. Le registre qui a été assigné àv s est marqué comme libre pour le code précédent, car ce registre peut maintenant être utilisé librement sans affecter le code suivant 6.Implémentation Pour démontrer l'efficacité de notre approche, nous avons implémenté un compilateur dynamique basé sur les traces pour la machine virtuelle JavaScript SpiderMonkey (4). SpiderMonkey est la machine virtuelle JavaScript intégrée dans le navigateur web open-source Firefox de Mozilla (2), qui est utilisé par plus de 200 millions d'utilisateurs dans le monde. Le cœur de SpiderMonkey est un interpréteur de bytecode implémenté en C++. Dans SpiderMonkey, toutes les valeurs JavaScript sont représentées par le type jsval. Un jsval est un mot machine dans lequel jusqu'à 3 des bits les moins significatifs sont une balise de type, et les bits restants sont des données. Voir la Figure 6 pour les détails. Tous les pointeurs contenus dans les jsvals pointent vers des blocs contrôlés par le GC alignés sur des limites de 8 octets. Les valeurs d'objet JavaScript sont des mappages de noms de propriétés sous forme de chaînes vers des valeurs arbitraires. Elles sont représentées de l'une des deux manières suivantes dans SpiderMonkey. La plupart des objets sont représentés par une description structurelle partagée, appelée la forme d'objet, qui mappe les noms de propriétés aux index de tableau en utilisant une table de hachage. L'objet stocke un pointeur vers la forme et le tableau de ses propres valeurs de propriété. Les objets avec des ensembles de noms de propriétés grands et uniques stockent leurs propriétés directement dans une table de hachage. Le ramasse-miettes est un collecteur exact, non générationnel, stop-the-world mark-and-sweep. Dans le reste de cette section, nous discutons des domaines clés de l'implémentation de TraceMonkey. 6.1Appel de traces compilées Les traces compilées sont stockées dans un cache de traces, indexé par le PC de l'interpréteur et la carte de types. Les traces sont compilées de manière à pouvoir être appelées comme des fonctions en utilisant des conventions d'appel natives standard (par exemple, FASTCALL sur x86). L'interpréteur doit atteindre un bord de boucle et entrer dans le moniteur afin d'appeler une trace native pour la première fois. Le moniteur calcule la carte de types actuelle, vérifie le cache de traces pour une trace correspondant au PC actuel et à la carte de types, et s'il en trouve une, exécute la trace. Pour exécuter une trace, le moniteur doit construire un enregistrement d'activation de trace contenant les variables locales et globales importées, l'espace de pile temporaire et l'espace pour les arguments des appels natifs. Les valeurs locales et globales sont ensuite copiées de l'état de l'interpréteur vers l'enregistrement d'activation de trace. Ensuite, la trace est appelée comme un pointeur de fonction C normal. 5.2Allocation de registres Nous utilisons un allocateur de registres glouton simple qui effectue un seul passage arrière sur la trace (il est intégré au générateur de code). Au moment où l'allocateur a atteint une instruction comme v 3=addv 1,v 2, il a déjà assigné un registre àv 3. Si v 1 et v 2 n'ont pas encore reçu de registres, l'allocateur assigne un registre libre à chacun. S'il n'y a pas de registres libres, une valeur est sélectionnée pour le déversement. Nous utilisons une heuristique de classe qui sélectionne la valeur portée par le registre la "plus ancienne" (6). L'heuristique considère l'ensemble R des valeurs v dans les registres immédiatement après l'instruction actuelle pour le déversement. Soit v m la dernière instruction avant l'actuelle où chaque v est référencé. Alors le Lorsqu'un appel de trace retourne, le moniteur restaure l'état de l'interpréteur. D'abord, le moniteur vérifie la raison de la sortie de trace et applique le blacklisting si nécessaire. Ensuite, il dépile ou synthétise les cadres de pile d'appels JavaScript de l'interpréteur selon les besoins. Enfin, il copie les variables importées de l'enregistrement d'activation de trace vers l'état de l'interpréteur. Au moins dans l'implémentation actuelle, ces étapes ont un coût d'exécution non négligeable, donc minimiser le nombre de transitions interpréteur-à-trace et trace-à-interpréteur est essentiel pour les performances (voir aussi Section 3.3). Nos expériences (voir Figure 12) montrent que pour les programmes que nous pouvons bien tracer, ces transitions se produisent rarement et ne contribuent donc pas significativement au temps d'exécution total. Dans quelques programmes, où le système est empêché d'enregistrer des traces de branche pour les sorties latérales chaudes par des abandons, ce coût peut atteindre jusqu'à 10 % du temps d'exécution total. L'enregistrement est activé par un échange de pointeur qui configure la table de dispatch de l'interpréteur pour appeler une seule routine d'« interruption » pour chaque bytecode. La routine d'interruption appelle d'abord une routine d'enregistrement spécifique au bytecode. Ensuite, elle désactive l'enregistrement si nécessaire (par exemple, la trace s'est terminée). Enfin, elle saute à l'implémentation standard du bytecode de l'interpréteur. Certains bytecodes ont des effets sur la typemap qui ne peuvent pas être prédits avant l'exécution du bytecode (par exemple, appeler String.charCodeAt, qui retourne un entier ou NaN si l'argument d'index est hors limites). Pour ceux-ci, nous organisons pour que l'interpréteur rappelle l'enregistreur après l'exécution du bytecode. Comme ces hooks sont relativement rares, nous les intégrons directement dans l'interpréteur, avec une vérification supplémentaire à l'exécution pour voir si un enregistreur est actuellement actif. Bien que séparer l'interpréteur de l'enregistreur réduise la complexité individuelle du code, cela nécessite également une implémentation minutieuse et des tests approfondis pour atteindre l'équivalence sémantique. Dans certains cas, atteindre cette équivalence est difficile car SpiderMonkey suit une conception fat-bytecode, qui s'est avérée bénéfique pour les performances de l'interpréteur pur. Dans les conceptions fat-bytecode, des bytecodes individuels peuvent implémenter un traitement complexe (par exemple, le bytecode getprop, qui implémente l'accès complet aux valeurs des propriétés JavaScript, y compris les cas spéciaux pour l'accès aux tableaux mis en cache et denses). Les fat bytecodes ont deux avantages : moins de bytecodes signifie un coût de dispatch plus faible, et des implémentations de bytecodes plus grandes donnent au compilateur plus d'opportunités pour optimiser l'interpréteur. Les fat bytecodes sont un problème pour TraceMonkey car ils obligent l'enregistreur à réimplémenter la même logique de cas spéciaux de la même manière. De plus, les avantages sont réduits car (a) les coûts de dispatch sont entièrement éliminés dans les traces compilées, (b) les traces ne contiennent qu'un seul cas spécial, pas le gros bloc de code de l'interpréteur, et (c) TraceMonkey passe moins de temps à exécuter l'interpréteur de base. Une façon dont nous avons atténué ces problèmes est d'implémenter certains bytecodes complexes dans l'enregistreur sous forme de séquences de bytecodes simples. Exprimer la sémantique originale de cette manière n'est pas trop difficile, et enregistrer des bytecodes simples est beaucoup plus facile. Cela nous permet de conserver les avantages des fat bytecodes tout en évitant certains de leurs problèmes pour l'enregistrement de traces. Ceci est particulièrement efficace pour les fat bytecodes qui récursent dans l'interpréteur, par exemple pour convertir un objet en une valeur primitive en invoquant une méthode bien connue sur l'objet, car cela nous permet d'inliner cet appel de fonction. Il est important de noter que nous ne divisons les fat opcodes en opcodes plus fins que pendant l'enregistrement. Lors de l'exécution purement interprétative (c'est-à-dire du code qui a été blacklisté), l'interpréteur exécute directement et efficacement les fat opcodes. 6.2Assemblage de traces Les transitions d'une trace à une trace de branche à une sortie latérale évitent les coûts d'appel des traces depuis le moniteur, dans une fonctionnalité appelée trace stitching. À une sortie latérale, la trace sortante n'a besoin que d'écrire les valeurs vivantes portées par les registres dans son enregistrement d'activation de trace. Dans notre implémentation, des typemaps identiques produisent des dispositions d'enregistrement d'activation identiques, de sorte que l'enregistrement d'activation de trace peut être immédiatement réutilisé par la trace de branche. Dans les programmes avec des arbres de traces ramifiés avec de petites traces, le trace stitching a un coût notable. Bien que l'écriture en mémoire puis la relecture immédiate devraient avoir un taux de succès élevé du cache L1, pour les petites traces, le nombre d'instructions accru a un coût notable. De plus, si les écritures et les lectures sont très proches dans le flux d'instructions dynamiques, nous avons constaté que les processeurs x86 actuels subissent souvent des pénalités de 6 cycles ou plus (par exemple, si les instructions utilisent des registres de base différents avec des valeurs égales, le processeur peut ne pas être en mesure de détecter que les adresses sont les mêmes immédiatement). La solution alternative est de recompiler un arbre de traces entier, réalisant ainsi une allocation de registres inter-traces (10). L'inconvénient est que la recompilation d'arbre prend un temps quadratique par rapport au nombre de traces. Nous croyons que le coût de recompilation d'un arbre de traces chaque fois qu'une branche est ajoutée serait prohibitif. Ce problème pourrait être atténué en ne recompilant qu'à certains points, ou seulement pour des arbres très chauds et stables. À l'avenir, le matériel multicœur devrait être courant, rendant la recompilation d'arbre en arrière-plan attrayante. Dans un projet étroitement lié (13), la recompilation en arrière-plan a donné des accélérations allant jusqu'à 1,25x sur des benchmarks avec de nombreuses traces de branche. Nous prévoyons d'appliquer cette technique à TraceMonkey dans le cadre de travaux futurs. 6.3Enregistrement de traces 6.4Préemption Le travail de l'enregistreur de traces est d'émettre du LIR avec une sémantique identique à la trace de bytecode de l'interpréteur en cours d'exécution. Une bonne implémentation devrait avoir un faible impact sur les performances de l'interpréteur non-traçant et un moyen pratique pour les implémenteurs de maintenir l'équivalence sémantique. Dans notre implémentation, la seule modification directe de l'interpréteur est un appel au moniteur de trace aux bords de boucle. Dans nos résultats de benchmark (voir Figure 12), le temps total passé dans le moniteur (pour toutes les activités) est généralement inférieur à 5 %, donc nous considérons que l'exigence d'impact sur l'interpréteur est satisfaite. Incrémenter le compteur de hits de boucle est coûteux car cela nous oblige à rechercher la boucle dans le cache de traces, mais nous avons réglé nos boucles pour qu'elles deviennent chaudes et tracent très rapidement (à la deuxième itération). L'implémentation du compteur de hits pourrait être améliorée, ce qui pourrait nous donner une petite augmentation des performances globales, ainsi qu'une plus grande flexibilité dans le réglage des seuils de chaleur. Une fois qu'une boucle est blacklistée, nous n'appelons plus jamais le moniteur de trace pour cette boucle (voir Section 3.3). SpiderMonkey, comme de nombreuses machines virtuelles, doit préempter le programme utilisateur périodiquement. Les principales raisons sont d'empêcher les scripts en boucle infinie de bloquer le système hôte et de planifier le GC. Dans l'interpréteur, cela avait été implémenté en définissant un indicateur « préempter maintenant » qui était vérifié à chaque saut arrière. Cette stratégie a été reprise dans TraceMonkey : la machine virtuelle insère une garde sur l'indicateur de préemption à chaque bord de boucle. Nous avons mesuré moins de 1 % d'augmentation du temps d'exécution sur la plupart des benchmarks pour cette garde supplémentaire. En pratique, le coût n'est détectable que pour les programmes avec des boucles très courtes. Nous avons testé et rejeté une solution qui évitait les gardes en compilant le bord de boucle comme un saut inconditionnel, et en corrigeant la cible du saut vers une routine de sortie lorsque la préemption est requise. Cette solution peut rendre le cas normal légèrement plus rapide, mais la préemption devient alors très lente. L'implémentation était également très complexe, surtout pour essayer de redémarrer l'exécution après la préemption. !"# $!"# %!"# &!"# '!"# (!"# )!"# *!"# +!"# ,!"# $!!"# &-./012#3%4%56# &-.789:;#3%4,56# &-.9<=>9922?#3!4,56# 8:?.&1@>.1@>[email protected]=>2#3%(4(56# 1@>8:?.1@>[email protected]=>2#3+4*56# 1@>8:?.1@>E@?2.8:[email protected]@>?#3%4*56# /8A>98FG8E.92/09?@D2#3$4!56# /9=:>8.<2?#3$4)56# /9=:>8.7-(#3%4&56# /9=:>8.?;<$#3(4,56# -<>2.B897<>.>8H2#3$4$56# -<>2.B897<>.5:<91#3$4!56# 7<>;./89-@/#3'4,56# 7<>;.:<9I;.?:2/>9[email protected][email protected]<#3$4(56# ?>9@AJ.>[email protected]:[email protected]2.@A:0>#3$4,56# KA>29:92># L