\section{Analyse du Dataflow} \subsection{But de l'analyse du \emph{dataflow}} Le but de l'analyse du \emph{dataflow} est de passer du niveau assembleur à un langage possédant des structures de contrôle. Pour cela, nous allons analyser le Dataflow, contruire un \emph{graphe de contrôle}, puis, analyser ce graphe de controle. Nous nous sommes fortement inspiré des algorithme présentés par A.~Appel~\cite{App98}, de la thèse de Cristina Cifentes~\cite{Cif95} et de nos connaissances acquise lors du projet Tiger pour écrire cette partie. \subsection{Elimination des registres} En éliminant les registres, nous allons avoir une représentation à peu près équivalente au LIR du compilateur Tiger de A.~Appel~\cite{App98}. On veut transformer les registres en temporaires dont la durée de vie sera la plus courte possible. Effectivement, plus la durée de vie est courte, plus facile seront les manipulations et meilleurs seront les resultats des algorithmes suivants. On commence par transformer le dataflow en graphe orienté. Chaque noeud de ce graphe correspond à une instruction et un arc indique la possibilité de passer d'une instruction à l'autre. %% Un exemple serait le bienvenu A chaque instruction, on associe l'ensemble des temporaires utilisées (\emph{``use''}) et définie (\emph{``def''}). Par exemple, dans l'instruction \verb+add ax, bx+, \verb+ax+ et \verb+bx+ sont utilisés et \verb+ax+ est definie. On rappelle que les temporaires sont, soit des registres, soit des variables sur la pile. C'est à dire que \verb+ax+, \verb-[sp + 2]- et \verb-[sp + 6]- sont trois temporaires. On associe ensuite un ensemble de temporaires \emph{``liveIn''} et \emph{``liveOut''} initiallement vides. On parcourt ensuite, le graphe en appliquant à chaque noeud $n$ les équations suivantes: \begin{align*} \mathrm{liveIn}(n) &= \mathrm{use}(n) \cup (\mathrm{liveOut}(n) - \mathrm{def}(n)) \\ \mathrm{liveOut}(n) &= \bigcup_{s \in \mathrm{successeurs}(n)} \mathrm{liveIn}(s) \end{align*} On parcourt le graphe jusqu'à ce qu'il n'y est plus de changements. On peut ainsi connaître la durée de vie de chaque variable. %% exemple: %% add ax, cx live: cx %% mov ax, bx live: ax %% mov [sp + 8], ax live: On commence alors à renommer les temporaires. La durée de vie des temporaires doit être la plus courte possible. On commence donc par la première instruction et on donne le même nom à la temporaire tant que celle si est vivante et qu'elle n'est pas utilisée et définie dans la même instruction. Sinon, on change de nom. On en profitera pour modifier l'écriture de l'assembleur pour une syntaxe plus proche d'un language haut niveau. Par exemple: \begin{verbatim} add cx, ax def: cx use: cx, ax livein: bx, ax, cx liveout: bx, cx mov ax, bx def: ax use: bx livein: bx, cx liveout: cx mov [sp + 8], cx def: [sp + 8] use: ax livein: cx liveout: \end{verbatim} donne \begin{verbatim} t3 = t2 + t1 t5 = t4 t6 = t3 \end{verbatim} On remarque que cette méthode peut avoir des problèmes avec certaines architectures, gestion de la pile ou optimisation du processeur. Effectivement, on considere que lorsque le compilateur n'a pas de assez de registre, il stocke ses temporaires sur la pile. Sur certaines architectures n'ayant pas de mode d'adressage indexé ou bien par soucis d'optimisation, on peut gerer la pile autrement (en utilisant \verb+push+ et \verb+pop+ par exemple). Notre méthode peut alors devenir moins satisfaisante.\\ Nous nous sommes ainsi débarrassé de la notion de registres. Il existe d'autres méthodes pour calculer les durées de vie des variables. Nous avons montré ici une méthode dérivée de A.~Appel~\cite{App98}. Dans sa thèse Cristina Cifentes~\cite{Cif95} utilise une méthode plus complexe que Appel, mais, elle n'apporte pas grand intérêt. Vous pouvez trouver une implémentation de cet algo dans le compilateur Tiger de A.~Appel~\cite{App98} dont une implémentation est faite par le LRDE \footnote{Laboratoire de Recherche et Dévelloppement d'EPITA} \subsection{Les temporaires mortes} Avant de continuer l'analyse du Graphe de Controle, nous pouvons éliminer les temporaires dont la vie est nulle (c'est à dire, une temporaire définie, mais, jamais utilisé). Cette optimisation est normallement faite par le compilateur. Elle est tout de même utile dans le décompilateur, car, après plusieurs transformations, des temporaires mortes peuvent apparaitrent. Cette optimisation simplifira les étapes suivantes. \subsection{Repérage des saut conditionnels} On aimerait maintenant avoir des instructions de sauts conditionnels sous une forme pour humaine(ie: \verb+jcond (t1 > t2) l1+). Sur la plupart des processeurs, les sauts conditionnels dépendent de l'état du registre de 'flags'. Nous devons donc repérer les sauts conditionnels puis repérer quel instruction met à jour le flag utilisé. Pour cela, on calcule la durée de vie du flag grace au même algorithme que pour la durée de vie des registres. Par exemple: \begin{verbatim} t2 = t1 - 2 push t2 jnz l1 \end{verbatim} En calculant la durée de vie du flag Z\footnote{Le flag Z signifie ``Est ce que le resultat est Zéro''}, on remarque que c'est l'instruction \verb+t2 = t1 - 2+ qui a modifié ce flag. On peut alors écrire \verb+jcond (t2 != 0) l1+ %(thesis p107) \section{Traitement des Fonctions} \subsection{Repérage des \emph{Basic Blocks} et des \emph{Function Blocks}} Pour les étapes suivantes, nous avons besoin de repérer les Basic Blocks et les Function Blocks. Un Function Blocks commence par un label et fini par un \verb+return+. Un Basic Block commence par un label et fini par un \verb+return+, un saut, un label ou un appel de fonction. On commence par construire les Basic Blocks. \subsubsection{Construction des Basic Blocks} Au début, on considère l'ensemble du code comme un seul Block. On parcourt le code, puis, à chaque saut, return, ou appel de fonction, on coupe le block en deux. On vérifie ensuite que l'adresse à laquelle on saute est bien le début d'un Basic Block, sinon, on coupe en deux Basic Blocks. Enfin, on met à jour les arcs entre les Basic Blocks que l'on vient de créer. Considérons l'exemple suivant: \begin{verbatim} t1 = t2 fun1: t3 = t1 call fun1 t4 = t3 + t1 l1: t5 = t1 + 5 jcond (t1 < t3) l1 ret t6 = t2 \end{verbatim} on parcourt le code, puis, lorsque l'on arrive l'instruction \verb+call+, on divise le Basic Block en deux: \begin{verbatim} t1 = t2 block 1 fun1: t3 = t1 block 2 call fun1 block 2 t4 = t3 + t1 block 3 l1: t5 = t1 + 5 block 3 jcond (t1 < t3) l1 block 3 ret block 3 t6 = t2 block 3 \end{verbatim} On continue de parcourir le code, puis, on arrive sur l'instruction \verb+jcond+: \begin{verbatim} t1 = t2 block 1 fun1: t3 = t1 block 2 call fun1 block 2 t4 = t3 + t1 block 3 l1: t5 = t1 + 5 block 4 jcond (t1 < t3) l1 block 4 ret block 5 t6 = t2 block 5 \end{verbatim} Enfin, on arrive sur l'instruction \verb+ret+: \begin{verbatim} t1 = t2 block 1 fun1: t3 = t1 block 2 call fun1 block 2 t4 = t3 + t1 block 3 l1: t5 = t1 + 5 block 4 jcond (t1 < t3) l1 block 4 ret block 5 t6 = t2 block 6 \end{verbatim} Le résultat est un graphe ressemblant au graphe construit pour le calcul de la durée de vie des temporaire mais, avec beaucoup moins de noeuds. Avec les Basic Blocks, le graphe garde les informations sur la structure du programme, mais, nous savons qu'il n'y a pas d'arc à l'intérieur des Basic Block et ainsi, chaque Basic Block peut être considéré comme une instruction. \subsubsection{Création du Call Graph} On peut maintenant regrouper les Basic Blocks en Function Blocks. On utilise la même méthode que pour les Basic Blocks, mais, cette fois, on ne repère que des appels de fonctions et les instructions \verb+return+. Pour l'exemple précédant, nous obtenons: \begin{verbatim} t1 = t2 block 1 fun1: t3 = t1 block 2 call fun1 block 2 t4 = t3 + t1 block 2 l1: t5 = t1 + 5 block 2 jcond (t1 < t3) l1 block 2 ret block 2 t6 = t2 block 3 \end{verbatim} \subsection{Repérage des signature des fonctions} Nous voulons maintenant transformer les instructions \verb+call+ en appels de fonctions plus facile à lire. Nous devons tout d'abord retrouver la signature de chaque fonction. \subsubsection{Fonctions prédéfinies} Dans le cas des fonctions appartennant à des bibliothèquess standards ou des built-ins, on possède déjà le code source et les signatures de celles-ci. Il suffit de retrouver le code de la fonction pour savoir son emplacement et trouver les endroits où elle est appellée. De même, on peut utiliser la table des symboles des bibliotèques dynamiques utilisée pour nommer les fonctions. \subsubsection{Les autres fonctions} Nous voulons maintenant connaître quels registres servent d'arguments à un Function Block. Pour reprérer un argument passé par les registres, on regarde simplement les temporaires utilisées dans un Function Block mais jamais définies dans le Function Block. Ces temporaires sont forcement des arguments de la fonction. On repère ensuite les registres qui sont définis dans la fonction et utilisés dans le code suivant l'appel de la fonction. Lorsque nous avons la signature de nos fonctions, nous pouvons remplacer les instructions \verb+call+ par la signature des fonctions. Nos fonctions sont maintenant bien independantes du reste du code. \subsection{Problèmes sur le repérage des fonctions} Dans un code généré par un compilateur courant, les algorithmes précédants ne doivent pas poser de problèmes. Néanmoins, le langage machine permet certaine pratiques qui ne passerai pas avec nos algorithmes. On peut par exemple trouver des Basic Block appellés quelques fois avec call et d'autres fois avec jump. Nous ne pouvons alors pas décider si le Basic Block est une fonction ou non. Il est aussi possible qu'un saut arrive sur un Block interne à une fonction ou bien qu'une fonction sorte sans l'instruction \verb+return+. Il peut aussi y avoir des fonctions retournant deux registres. Ce sont des pratiques qu'on ne devrait pas trouver dans un code généré, mais, en théorie, elles sont faisables. \section{Inlining des instructions} \subsection{Propagation de copie des temporaire} Nous voulons maintenant 'inliner' les instructions. C'est à dire passer de \begin{verbatim} t4 = t2 + t3 t1 = fun1(t4) t5 = t4 - t1 \end{verbatim} à \begin{verbatim} t4 = (t2 + t3) t5 = t4 - fun1(t4) \end{verbatim} On regarde pour cela la durée de vie des temporaires. Lorsqu'une temporaire est utilisée qu'une fois, on peut alors, la substituer à sa définition. Reprennons l'exemple précédant: \begin{verbatim} t4 = t2 + t3 ; def = t4 use = t2, t3 t1 = fun1(t4) ; def = t1 use = t4 t5 = t4 - t1 ; def = t5 use = t4, t1 \end{verbatim} On remarque que \verb+t1+ n'est utilisé qu'une fois, on peut donc la substituer à sa définition: \begin{verbatim} t4 = (t2 + t3) t5 = t4 - fun1(t4) \end{verbatim} \subsection{Elimination des temporaire inutile} Nous avons, lors de l'élimination des registres, ajouter beaucoup de temporaires pour que la durée de vie des temporaires soit la plus courte possible. Cela nous a permis de faire beaucoup d'optimisations sur le code. Nous devons maintenant faire l'étape inverse et supprimer les temporaires inutiles. Par exemple: \begin{verbatim} t4 = (t2 + t3) t5 = t4 - fun1(t4) \end{verbatim} donne \begin{verbatim} t4 = (t2 + t3) t4 = t4 - fun1(t4) \end{verbatim} car \verb+t5+ et \verb+t4+ peuvent être dans la même temporaire sans gêner le fonctionnement du programme. Dans sa thèse Cristina Cifentes garde la notion de registres pendant toute la phase d'analyse du Dataflow et évite cette phase d'elimination des temporaires inutiles, mais, cela complexifie l'analyse du Dataflow. \subsection{Variables locales} Après tous ces traitements, les registres utilisés pour stocker des résultats intermédiaires ont normallement été supprimés. On peut donc dire que les registres restant sont des variables locales. On change alors les noms des registres. On crée des nouveaux noms en fonction de la vie de la donnée. Par exemple: \begin{verbatim} t4 = (t2 + t3) t4 = t4 - fun1(t4) \end{verbatim} donne \begin{verbatim} loc1 = (t2 + t3) loc1 = loc1 - fun1(loc1) \end{verbatim} \section{Reconnaissance des structures de controles} C'est sûrement l'une des parties les plus difficiles d'un décompilateur. Nous avons maintenant du code lisible mais, mais, il est encore difficile de comprendre la structure de l'algorithme utilisé car il n'y a pas pas encore de structures de controle\footnote{On appelle une structure de controle un mot clef du language servant à orienter le code (par contradiction aux fonctions/procédures qui servent à faire une action). Typiquement, ce sont les boucles et les conditions}. On doit donc retrouver la structure de l'algorithme utilisé. \subsection{Repérage des boucles} D'après la thèse de Cristina Cifentes~\cite{Cif95}, nous commencons tout d'abord par repérer les structures de boucle (ex: \verb+while+, \verb+for+, \verb+repeat...until+). Pour cela, on repère les arcs en arrière\footnote{On peut facilement calculer la nature d'un arc en fesant un parcours profondeur du graphe}. Un arc en arrière est typique d'une boucle. On regarde ensuite, si aucun arc arrive à l'intérieur de la boucle. Si c'est le cas, nous ne sommes pas en présence d'une boucle. Effectivement, à part avec un goto, on ne peut pas rentrer au milieu d'une bouclde. On regarde ensuite si il y une condition juste avant l'arc en arrière ou bien à l'arrivée de l'arc en arrière. Le premier cas est synonyme d'un \verb+repeat...until+ et le second d'un \verb+while+. Si il n'y a pas de condition ni avant, ni après l'arc en arrière, on se trouve surement en présence d'une boucle sans condition d'arrêt (qui se finit surement avec un break). Les arc partant de l'intérieur de la boucle et sortant de la boucle peuvent être représentés avec des \verb+break+ ou des \verb+goto+. \subsection{Repérage des structures conditionnelles} Pour repérérer les structures conditionnelles, on repère les arcs en avant pour trouver des structures \verb+if...then+ et les arcs croisés pour repérer les structure \verb+if...then...else+. %% un exmple, ici, ca aurait de la bombe... On trouve ensuite les conditions imbriquées. On élimine alors l'imbrication en transformant la condition à l'aide de OU ou de ET logiques. Les conditions sont généralement optimisées par le compilateur. Il peut alors être intéressant d'utiliser un programme de transformation d'expression logique\footnote{Projet Ovide fait dans le cadre pédagogique d'EPITA fait ca très bien, par exemple} pour rendre la condition plus lisible. \subsection{Finalisation} On applique ainsi plusieurs fois les repérages précedants. Cela nous permet de fusionner les Basic Blocks en intégrant les structures de contrôle et ainsi de simplifier le graphe. Si nous ne trouvons plus de structure de controle dans le graphe, nous utilisons \verb+goto+ sur l'un des arcs pour débloquer la situation. L'algorithme s'arrête quand tous les Basic Blocks sont fusionnés. Nous obtenons alors un code ne possédant plus de \verb+jcond+, dont l'appel des fonctions est lisible et dont les expressions sont inlinées. Néanmoins, ce code ne contient aucun typage!