Brevet FR2828296A1 — publié le 20030207

La présente invention concerne un procédé de compression de code objet interprété par factorisation d'expressions arborescentes. D'une manière générale, on sait que les systèmes embarqués munis de ressources de traitement de données tels que, par exemple, des cartes à microprocesseur ou analogues, sont conçus de manière à exécuter des codes objets obtenus par compilation d'un programme source, habituellement écrit en un langage de haut niveau : Ces systèmes comprennent, en conséquence, un interpréteur permettant d'assurer l'interprétation logicielle des instructions du code objet en instructions en langage machine directement exécutables par le microprocesseur. Cet interpréteur se trouve par exemple implanté dans une mémoire associée au microprocesseur, en général une mémoire morte ROM ou une mémoire programmable. Il s'avère que de nombreuses applications exigent l'emploi de systèmes embarqués de taille aussi réduite que possible, ce qui implique une limitation de la taille des mémoires et, en conséquence, des programmes applicatifs utilisés. Dans le but de s'affranchir partiellement de ce problème, on a proposé d'effectuer un compactage du code source. Toutefois, cette solution présente les inconvénients de ne pas pouvoir être utilisée dans le cas où l'on ne dispose pas du code source (ce qui est le cas la plupart du temps) et d'avoir à instrumenter le générateur de code objet interprété qui est un outil hautement complexe. Par ailleurs, on a également proposé d'effectuer le compactage du code objet interprété en recherchant dans le code objet des séquences identiques d'instructions standard successives et en comptant le nombre d'occurrences de ces séquences identiques. Un test de comparaison de supériorité de ce nombre d'occurrences à une valeur de référence permet alors de décider la création d'une instruction de code spécifique à laquelle est associée la séquence. Un remplacement de chaque occurrence de la séquence par l'instruction de code spécifique est effectué dans le code objet interprété pour engendrer un code objet compacté auquel est associé un fichier d'exécution. En fait, ce procédé de compression effectue une factorisation de groupes d'instructions contiguës dans le programme en code objet interprété. L'invention a plus particulièrement pour objet d'améliorer le compactage du programme en code objet interprété en factorisant non plus des groupes d'instructions contiguës mais en identifiant et en traitant des groupes d'instructions non contiguës de manière à obtenir de nouvelles instructions exécutables grâce à l'emploi de systèmes originaux d'instrumentation de l'interpréteur. Elle s'applique tout particulièrement, mais non exclusivement, aux interpréteurs disposant d'une pile pour effectuer tous les calculs. Elle propose, à cet effet, un procédé de compression comprenant les étapes suivantes : - l'identification, dans le programme en code objet interprété, de groupes d'instructions non contiguës similaires, de structure arbitrairement complexe, - le remplacement de tout ou partie de ces groupes dans le code objet interprété du programme par des instructions spécialisées nouvellement créées, - l'instrumentation de l'interpréteur et/ou du fichier code objet interprété du programme de manière à le rendre apte à mettre en oeuvre les instructions nouvellement créées dans l'exécutable. Avantageusement, ce procédé pourra comprendre une étape de test en vue de choisir les groupes d'instructions à remplacer de manière à ce que l'on obtienne après remplacement un programme compressé de taille inférieure à celle du programme avant compression, ce choix tenant compte du surcoût lié à l'instrumentation de l'environnement d'exécution et/ou du code objet. Des modes d'exécution de l'invention seront décrits ci-après, à titre d'exemples non limitatifs, avec référence aux dessins annexés dans lesquels : La figure 1 est un organigramme illustrant le mode opératoire du procédé selon l'invention ; La figure 2 est une représentation schématique montrant les modifications de la pile d'opérandes lors de l'exécution d'un exemple de séquence de bytecode JavaCard ; La figure 3 est une représentation schématique montrant les modifications de la pile d'opérandes et de la pile interne lors de l'exécution de la séquence d'instructions illustrée figure 2 après la compression qui a introduit l'instruction spécialisée ssub-sadd baload ; La figure 4 illustre d'une façon analogue l'exécution de cette même séquence d'instructions en utilisant une seule pile. Conformément à l'organigramme représenté figure 1, la mise en oeuvre du procédé précédemment défini peut comprendre une séquence opératoire comportant les étapes suivantes : - la construction d'une représentation des calculs effectués par le programme sous la forme d'expressions arborescentes (bloc 1), - l'identification, dans ces expressions arborescentes, de séquences de sous- expressions correspondant à des motifs apparaissant le plus fréquemment (selon un critère laissé ouvert, par exemple une fonction de seuil sur les fréquences d'occurrence), ces motifs pouvant être des arbres complets ou paramétrés par des arguments (bloc 2), - la sélection d'une séquence de motifs d'arbres (MI,..., Mn) (bloc 3), - l'association, à la séquence de sous-expressions sélectionnée à l'étape précédente, d'une nouvelle instruction de l'interpréteur (bloc 4), - la reconstruction d'une forme objet interprétée à partir de la représentation sous forme d'expressions arborescentes en remplaçant dans le code objet interprété du programme les groupes d'instructions correspondant à chaque occurrence de la séquence de sous-expressions sélectionnée par l'instruction associée (bloc 5), - l'ajout, dans le fichier du code objet interprété du programme et/ou dans l'interpréteur, des définitions des instructions nouvellement créées. (Etant entendu que l'étape de sélection (bloc 3) relève de techniques appartenant à l'état de l'art). Bien entendu, cette séquence opératoire comprend ensuite un test (bloc 6) pour savoir si le jeu d'instructions est épuisé ou non ou si la compression est devenue impossible. Dans la négative, le système retourne au bloc 1 pour effectuer une nouvelle séquence d'opérations de compression. Par contre, dans l'affirmative la séquence prend fin (bloc 7). L'invention propose une technique d'identification des groupes d'instructions non contiguës qui repose sur la construction d'une représentation du programme code objet interprété sous forme d'expressions arborescentes. A cet effet, elle propose de retrouver dans le code objet des expressions calculatoires complexes (telles qu'elles pouvaient apparaître, par exemple, dans le langage de haut niveau qui a servi à écrire le programme avant compilation) et d'identifier parmi ces expressions, des séquences de sousexpressions apparaissant fréquemment dans le programme. Plus précisément, l'invention vise à représenter les groupes d'opérations calculatoires sous la forme d'expressions arborescentes, étant entendu que dans ce cas : - elle met en oeuvre un interpréteur disposant d'une pile pour effectuer ses calculs, - une opération calculatoire est une instruction qui prend des arguments sur une pile d'opérandes et retourne ou non un résultat sur cette pile, - un arbre d'expressions calculatoires peut correspondre à un groupe d'instructions séparées l'une de l'autre par des distances arbitrairement grandes dans le code objet original, - par définition, pour chaque opération calculatoire op du langage objet intermédiaire le constructeur d'arbre associé sera notre, l'arité du constructeur QJ2. est donnée par le nombre d'arguments que l'opération op lit sur la pile de l'interpréteur. Dans cet exemple, le procédé selon l'invention utilise un algorithme de calcul itératif simple qui construit une représentation sous forme d'expressions arborescentes pour chaque sous-programme du code objet interprété à partir de sa séquence d'instructions par réécritures successives. Chaque étape de réécriture est définie sur une séquence d'instructions étendues S comme suit, étant entendu qu'une expression étendue est soit une instruction standard, soit une expression arborescente : e Si 6'= (7..., J ..., E, oj9, +7,..., où QJ2 est d'arité n alors on réécrit S en : a Sinon S reste inchangée Si (Il,..., In) est la séquence d'instructions du sous-programme P, on applique itérativement cet algorithme à la séquence d'instructions étendues (I'l,..., In) où : *I'csi Ii coùcest d'aritéO e I'i = Ii sinon jusqu'à ce que toute autre réécriture soit devenue impossible. La séquence d'instructions étendue obtenue au terme de ce calcul est la représentation sous forme d'expressions arborescentes P du sous-programme P. L'invention sera illustrée ci-après, en référence aux exemples suivants donnés à titre non limitatif, dans lesquels : L'Exemple 1 illustre un mode de représentation sous forme d'expressions arborescentes d'une séquence de bytecode exprimée en code JavaCard. L'Exemple 2 montre un mode de factorisation de cette séquence à partir de sa représentation sous forme arborescente. L'Exemple 3 est un mode de définition de l'instruction spécialisée introduite dans l'Exemple 2 en utilisant une pile interne. L'Exemple 4 est un mode de définition de l'instruction spécialisée introduite dans l'Exemple 2 en utilisant une seule pile. Exemple 1 : Dans cet exemple, de même que dans tous les autres, on considère l'architecture logicielle JavaCard. JavaCard est une architecture logicielle complète (incluant un langage de programmation de haut niveau orienté objet, un code objet interprété, un interpréteur de code objet de type machine à pile, un environnement d'exécution, des bibliothèques standard et un système d'interactions sécurisé entre programmes hébergés sur une même carte) pour l'exécution de programmes sur des cartes à puce dans un contexte multiapplications. Un programme JavaCard est appelé une applet. C'est un programme réactif passif qui interagit avec le terminal auquel la carte est connectée sous la forme d'envoi de messages de type commande-réponse, les commandes étant émises par le terminal uniquement, l'applet renvoyant une réponse pour chaque commande reçue. Le langage code objet interprété ici considéré est le bytecode JavaCard. L'interpréteur de bytecode est la machine virtuelle JavaCard (JCVM) qui est embarquée sur les cartes à puce. On considère un programme JavaCard qui contient la séquence de bytecode suivante : sload 1 sload 2 sadd sload 3 ssub sload 4 sconst 2 baload sconst 1 sconst 2 invokestatic"someComputation (short, byte, short, short)" L'instruction sload n lit le contenu de la variable n et le stocke au sommet de la pile, l'instruction sadd (respectivement ssub) effectue l'addition (respectivement la soustraction) des deux entiers se trouvant au sommet de la pile et stocke le résultat dans la pile, l'instruction sconst c empile la constante entière c, l'instruction baload lit un élément dans un tableau d'octets et stocke son contenu sommet de la pile, tandis que l'instruction invokestatic effectue l'appel d'un sous-programme. Les entiers considérés sont des short, c'est-à-dire des entiers sur 16 bits, ou des byte, c'est-à-dire des entiers sur 8 bits. Les modifications de la pile d'opérandes lors de l'exécution de cette séquence d'instructions sont indiquées sur la figure 2. La représentation sous forme d'expressions arborescentes de la séquence précédente a la forme suivante : invokestatic"someComputation (short, short, short, byte)" (ssub (sadd (sload 1, sload 2), sload 3), baload (sload 4, sconst 2), sconst 1, sconst 2) On obtient une expression calculatoire complexe similaire à celle qui a pu être écrite, par exemple, dans le langage de programmation de haut niveau qui a servi à produire le code objet du programme considéré (ici JavaCard). La factorisation des expressions arborescentes conformément au procédé selon l'invention comprend une première étape qui consiste à identifier des séquences de motifs récurrentes dans les expressions arborescentes apparaissant dans la forme intermédiaire du programme. Un motif M est un terme, c'est-à-dire un arbre incomplet, dont les parties manquantes sont représentées par des variables nommées x x,..., x, etc. On notera les indices des variables dans l'ordre croissant de leur occurrence dans le parcours postfixé (c'est-à-dire en profondeur, de gauche à droite, en explorant les fils d'un noeud avant le noeud lui-même) de l'arbre auquel elles appartiennent. Pour une séquence de motifs (MI,..., Mk) les variables apparaissant dans les motifs Mil,..., Mk sont en outre numérotées dans l'ordre croissant de leur apparition dans la séquence de motifs en la parcourant de gauche à droite, comme par exemple dans la séquence suivante : (Mi (xi, X2), M2 (X3, X4, xs), M3 (x6)). Si à chaque séquence de motifs (Mi,..., Mk) sélectionnée pour la factorisation on associe une instruction spécialisée I(MI,..., Mk) alors l'opération de factorisation F (E) d'une expression arborescente E en une séquence d'instructions est définie de la manière suivante (suivant l'ordre des cas) : . F- 7,... ./... ..., . 7,..., = F (E o... 0 F (E) 0 F (El) o... o F (Eln) o... o F o... o F o (..., M) o F (Ej+l) o... o F (EJ o (c) si la séquence (Mj,..., Mk) est sélectionnée pour la factorisation . F (c), si f est d'arité 0 ; e F (c * F (c (E'/,..., En = FE') o... o F (EnJ 0 (c), si c est d'arité n Dans ces expressions, de même que dans la suite de la description, l'opérateur o dénote la concaténation des séquences d'instructions. La recherche des séquences de motifs peut se faire par énumération de termes de taille bornée et filtrage des expressions arborescentes du programme selon ces termes. La mise en oeuvre de cette recherche ainsi que la fonction de choix des termes à factoriser sont laissées ouvertes car elles relèvent des techniques classiques de l'état de l'art. Si P = (Ji, J2,..., JmJ est la représentation intermédiaire du sous-programme P sous forme de séquences d'instructions étendues, qui sont soit des instructions standard soit des expressions arborescentes, alors la factorisation de P est définie par la séquence d'instructions standard suivantes : Fact (Jj) o Fact (J2) o... o Fact (Jm) où Fact (J) = J si J est une instruction standard F (J) si J est une expression arborescente L'Exemple 2 ci-après illustre un mode de factorisation des arbres d'expressions de la séquence de bytecode de l'Exemple 1. Exemple 2 : On suppose que dans le programme contenant le code de l'Exemple 1 l'algorithme de recherche des motifs ait sélectionné comme candidat à la factorisation la séquence de motifs suivante : (ssub (sadd (xl, x2), x3), baload (x4, x)) On nomme ssub-sadd baload l'instruction spécialisée associée à cette séquence de motifs. Alors, après factorisation de la séquence de bytecode correspondante, on obtient la séquence de bytecode suivante : sload 1 sload 2 sload 3 sload 4 sconst 2 ssub sadd baload sconst 1 sconst 2 invokestatic"someComputation (short, byte, short, short)" Comme précédemment mentionné, le procédé selon l'invention comprend une étape d'instrumentation de l'interpréteur et/ou du fichier code objet interprété du programme de manière à le rendre apte à mettre en oeuvre les instructions nouvellement créées dans l'exécutable. Cette étape intervient dans le cas où chaque instruction spécialisée est définie au sein de l'interpréteur et/ou dans le fichier objet du programme par une séquence d'instructions du langage objet interprété. Le cas d'une implémentation native de ces opérations n'est pas couvert. L'exécution d'une instruction spécialisée nécessite de modifier le mode d'exécution de l'interpréteur car la factorisation rompt le lien logique entre les différents calculs intermédiaires. Ainsi, dans l'Exemple 2, lors de l'exécution de l'instruction spécialisée, l'opération d'addition doit aller chercher ses arguments profondément dans la pile. Le résultat de l'addition ne peut pas être simplement stocké au sommet de la pile car il correspond au premier argument de la soustraction qui doit nécessairement se trouver un niveau en dessous de son second argument dans la pile. Il y a deux façons possibles d'instrumenter l'interpréteur pour exécuter ces instructions, à savoir : une première façon consistant à utiliser une pile interne, et une deuxième façon consistant à effectuer un décalage de la pile d'opérandes. La première solution consiste à utiliser une pile d'opérandes interne lors de l'exécution d'une instruction spécialisée afin d'effectuer toutes les opérations qui la composent. Les arguments utilisés sont copiés de la pile d'opérandes standard vers la pile interne par une nouvelle instruction get~arg n qui prend en argument le niveau n de la pile d'opérandes standard (à partir du sommet de la pile qui correspond au niveau 0) à copier vers la pile interne. Il faut en plus associer à chaque instruction spécialisée le nombre de ses arguments afin de pouvoir les enlever de la pile standard à la fin de l'exécution de l'instruction et de copier le contenu résiduel de la pile interne vers la pile d'opérandes standard (ce qui constitue le résultat final de la séquence d'instructions associée). Si (My,..., A) est une séquence de motifs dont les variables sont xl,..., Xn, (c'est-à-dire l'ensemble des variables apparaissant dans tous les motifs de la séquence, numérotées suivant le parcours de gauche à droite de la séquence et suivant le parcours postfixé de chaque motif), alors la sémantique S (I(M1, ..., MJ) de l'instruction spécialisée I (m,,..., m,) associée, est la séquence d'instructions standard définie récursivement de la manière suivante : . S (xi) = (get~arg (n-i)) e S (c) = (c), si f est d'arité 0 e Sc,..., = S o... o S (Ek) o (c), si f est d'arité k L'Exemple 3 illustre un mode d'utilisation d'une pile d'opérandes interne dans le cas de l'instruction spécialisée ssub-sadd baload de l'Exemple 2. Exemple 3 : Le code correspondant à la définition de l'instruction spécialisée ssub~sadd~baload de l'Exemple 2 est alors le suivant : get~arg 4 get~arg 3 sadd get~arg 2 ssub get~arg 1 get~arg 0 baload Les modifications de la pile d'opérandes et de la pile interne lors de l'exécution de la séquence d'instructions factorisée de l'Exemple 2 sont indiquées sur la figure 3. La seconde solution d'instrumentation de l'interpréteur n'utilise qu'une seule pile, la pile d'opérandes standard, mais introduit des opérations de saut dans la pile qui permettent de se placer à un niveau arbitraire. Lorsqu'une opération est effectuée à l'intérieur de la pile, tous les niveaux se trouvant au-dessus se trouvent décalés (vers le haut ou vers le bas selon que l'instruction du langage objet interprété exécutée consomme des arguments et/ou empile un résultat). Une nouvelle instruction down n doit être utilisée pour permettre de se déplacer de n niveaux en dessous du niveau de pile courant, ainsi que d'une instruction up qui permet de se déplacer d'un niveau au-dessus du niveau de pile courant. Aucune autre information n'est nécessaire pour l'exécution de l'instruction spécialisée. A la fin de l'exécution de l'instruction spécialisée, la pile contient le résultat final du groupe d'instructions associé. Si (Mf,..., M, J est une séquence de motifs dont les variables sont x..., x, alors on définit une sémantique auxiliaire S'(I (,..., ) de l'instruction spécialisée I (/,..., . Cette sémantique auxiliaire consiste en la séquence d'instructions standard définie récursivement de la manière suivante : . S' (xi) = (up) e S'sud = (c), si est d'arité 0 e S' (f (E 1,..., Efd) = S' (E JJ o... 0 S' (Efd 0 (c), si c est d'arité k La sémantique S (I (m,,..., uk de l'instruction spécialisée est la séquence La sémantlque S (I (MI,..., d'instructions suivantes : S (I ,..., M) = (down n) 0 S' (I ..., ) L'instruction down n initiale permet de se placer un niveau en dessous du premier argument de l'instruction spécialisée, qui est l'argument se trouvant au niveau le plus bas dans la pile. L'ordre de numérotation des arguments étant égal à leur ordre d'évaluation par l'instruction spécialisée, chaque lecture d'un argument nécessite un seul décalage du pointeur de pile vers le haut grâce à l'instruction up. L'Exemple 4 illustre un mode d'instrumentation n'utilisant que la pile d'opérandes standard dans le cas de l'instruction spécialisée ssub~sadd~baload des Exemples 1 et 2. Exemple 4 : Le code correspondant à la définition de l'instruction spécialisée ssub sadd baload est alors le suivant : down 5 up up sadd up ssub up up baload Les modifications de la pile d'opérandes lors de l'exécution de cette séquence d'instructions sont indiquées sur la figure 4. A chaque pas d'exécution on a figuré par un pointeur en forme de flèche le niveau dans la pile où s'effectuent les calculs. Il est à noter que la séquence d'instructions down 5 up up est équivalente à l'unique instruction down 3 Cette optimisation permet de diminuer l'espace nécessaire à l'instrumentation de l'interpréteur. Revendications 1. Procédé de compression de code objet interprété dans un système comprenant un interpréteur permettant d'assurer l'interprétation logicielle des instructions du code objet en instructions en langage machine directement exécutables par un processeur, caractérisé en ce qu'il comprend les étapes suivantes : - l'identification, dans le programme en code objet interprété, de groupes d'instructions non contiguës similaires, de structure arbitrairement complexe, - le remplacement de tout ou partie de ces groupes dans le code objet interprété du programme par des instructions spécialisées nouvellement créées, - l'instrumentation de l'interpréteur et/ou du fichier code objet interprété du programme de manière à le rendre apte à mettre en oeuvre les instructions nouvellement créées dans l'exécutable. 2. Procédé selon la revendication 1, caractérisé en ce qu'il comprend en outre une étape de test en vue de choisir les groupes d'instructions à remplacer de manière à ce que l'on obtienne après remplacement un programme compressé de taille inférieure à celle du programme avant compression, ce choix tenant compte du surcoût lié à l'instrumentation de l'environnement d'exécution et/ou du code objet. 3. Procédé selon l'une des revendications 1 et 2, caractérisé en ce qu'il comprend une séquence opératoire comprenant les étapes suivantes : - la construction d'une représentation des calculs effectués par le programme sous la forme d'expressions arborescentes (bloc 1), - l'identification, dans ces expressions arborescentes, des sous-expressions correspondant à des séquences de motifs récurrentes, ces motifs pouvant être des arbres complets ou paramétrés par des arguments (bloc 2), - l'association, à chacune de ces séquences de motifs, d'une nouvelle instruction de l'interpréteur (bloc 4), - la reconstruction d'une forme objet interprétée à partir de la représentation sous forme d'expressions arborescentes en remplaçant le code correspondant aux séquences de motifs identifiées par l'instruction associée, - l'ajout, dans le fichier du code objet interprété du programme et/ou dans l'interpréteur, des définitions des instructions nouvellement créées. 4. Procédé selon la revendication 3, caractérisé en ce que la susdite identification s'effectue selon un critère consistant en une fonction de seuil sur les fréquences d'occurrence des susdites séquences de motifs. 5. Procédé selon la revendication 3, caractérisé en ce qu'il utilise un algorithme de calcul itératif qui construit une représentation sous forme d'expressions arborescentes pour chaque sousprogramme du code objet à partir de sa séquence d'instructions par réécritures successives. 6. Procédé selon la revendication 3, caractérisé en ce qu'il comprend une recherche de motifs par énumération de termes et filtrage des expressions arborescentes du programme selon ces termes. 7. Procédé selon l'une des revendications 3 à 6, caractérisé en ce que, dans le cas où il met en oeuvre un interpréteur de type machine à pile, il comprend une modification du mode d'exécution de l'interpréteur lors de l'exécution d'une instruction spécialisée, l'instrumentation de l'interpréteur pour exécuter ces instructions comportant soit l'utilisation d'une pile interne soit la réalisation d'un décalage de la pile d'opérandes. 8. Procédé selon la revendication 7, caractérisé en ce que dans le cas de l'utilisation d'une pile d'opérandes interne, les arguments utilisés sont copiés de la pile d'opérandes standard vers la pile interne par une nouvelle instruction get n qui prend en argument le niveau n de la pile d'opérandes standard à copier vers la pile interne, à chaque instruction spécialisée étant associé le nombre de ses arguments afin de les enlever de la pile standard à la fin de l'exécution de l'instruction et de copier le contenu résiduel de la pile interne vers la pile d'opérandes standard. 9. Procédé selon la revendication 7, caractérisé en ce que, dans le cas où l'on réalise un décalage de la pile d'opérandes, il comprend une nouvelle instruction down n qui permet de se déplacer de n niveaux en dessous du niveau de la pile courant, ainsi qu'une instruction up qui permet de se déplacer d'un niveau au-dessus du niveau de la pile courant.