Lors de la sance prcdente, nous avons vu comment mettre le code sous une forme canonique appele SSA

B. Monsuez

Informations

• Publié par: Onfo
• Nombre de lectures: 22
• Langue: Français

Extrait

Cours de « concepts avancés de compilation »

Travaux pratiques

Séance du 5 décembre 2005

Auteur : B. Monsuez

Utilisation de la forme SSA Lors de la séance précédente, nous avons vu comment mettre le code sous une forme canonique appelée SSA. Dans le cadre de cette séance, nous allons étudier quelques optimisations qui peuvent être réalisées à partir de cette représentation particulière. Les transformations sont aux nombres de deux, la première consiste à une méthode de propagation de la constante (c’est une méthode distincte de celle vue dans la séance sur l’élimination des redondances), la seconde consiste à déterminer le code véritablement utile et le code inutile (c’est une méthode complémentaire de celle vue lors de l’étude du contrôle de flot de données).

Propagation de la constante La méthode de propagation de la constante consiste à déterminer si une expression est « constante ». Une expression est dite constantesi et seulement si pour toute exécution, cette expression prend une même et unique valeur. Si une expression est dite constante, il est dès lors possible de remplacer l’expression par la valeur résultat de l’expression. Question 1.1 Expliquer pourquoi la méthode de la propagation de la constante est une optimisation intéressante ? Pour mémoire, une optimisation pour être intéressante doit vérifiée trois critères : elle doit être sûre, elle doit apporter un gain quantifiable ( compacité, temps d’exécution,…), elle est doit être opportune. Pour déterminer si une valeur est constante, nous utilisons un treillis à 3 niveaux. Dans une première approche, nous considérons : •ψs’agit d’une valeur qui varie, mais pas d’une constante, il • c s’agit d’une constante, il i •ζinformation n’est disponible quant à cette valeur. aucune L’idée de l’analyse, c’est d’initialiser toutes les valeurs au départ àζet ensuite d’évaluer formellement le programme en commençant par la première instruction et en terminant par la

dernière instruction, en considérant que chaque valeur du programme ne peut prendre comme valeur queζ, c etψ. i Si lors du calcul, une valeur peut avoir admettre une valeur abstraitea 1 et une autre valeur abstraitealors la valeur prend le plus petit élément supérieur à la fois àa 1 et àa 2 que l’on notea 1 ≤a 2 . Question 1.2 i←12 1 Pour le code cicontre, déterminer par la méthode précédente les constantes ? x←i*17 1 j←i Expliquer sur l’exemple précédent l’intérêt de la forme SSA pour la 1 propagation de la constante ? (Remarque : pour répondre à cette question, il i←i* 2 2 1 est possible de regarder le cas de la variable i qui accepte sous la forme SSA deux instances i et i et plus particulièrement ce qui se passerait si on ne ferait aucune 1 2 distinction entre les deux instances i et i ). 1 2 Dans l’exemple précédent, nous avions uniquement une évaluation séquentielle du programme. De fait il suffisait d’évaluer formellement le programme en commençant par la première instruction et en terminant par la dernière instruction. Si nous sommes en présence de boucles, il est nécessaire de recommencer cette évaluation formelle en commençant par la première instruction et en terminant par la dernière instruction tant qu’une solution stable n’est pas trouvée. Question 1.3 i←12 0 Pour le code cicontre, déterminer par la méthode précédente les constantes ? while(...) i←φ(i,i) 1 03 Combien de fois au plus estil nécessaire d’évaluer formellement le x←i*17 1 programme en commençant par la première instruction et en j←i terminant par la dernière instruction ? (Remarque : on réfléchira 1 sur la hauteur du treillis qui est fini et on remarquera qu’à chaque i←... 2 évaluation, on ne peut conserver que la valeur courante (stabilité) ... ou monter à une valeur supérieure). i←j 3

Détermination du code exécuté La détermination du code exécuté consisté à marquer le code exécuté et à supprimer le code qui n’est pas marqué comme pouvant être exécuter. (Remarque : ce concept est le même que celui d’un ramassemiette – garbage collector – basé sur l’algorithme Mark & Sweep). L’idée consiste tout d’abord à définir les actions critiques : •Instruction d’entrées/sorties •Point d’entrées et de retours d’un bloc •Valeurs de retours •Appels procéduraux. A partir des blocs correspondant à des actions critiques, il est nécessaire de parcourir le code mis sous forme de SSA pour trouver les antécédents.

En fait, les actions à conserver sont celles qui ont un impact sur l'exécution du code futur. Les actions critiques sont les actions à conserver impérativement parce qu'elles peuvent avoir un impact bien plus tard (leur zone d'impact ne peut être déterminé par une forme particulière comme la SSA). Les autres actions à conserver sont alors les actions ayant un impact sur les actions critiques. Elles sont progressivement déterminées. Les actions à éliminer sont les actions non marquées comme étant à conserver et sont celles qui n'ont aucun impact sur le code futur. C'est cet algorithme de détermination qui est plus particulièrement étudié. On supposera que les instructions restantes après une transformation SSA sont : instruction =  | begin bloc  | end bloc  | if (...) goto label  | label : instruction  | x1 < f(...)  | x1 < y op z  | printf, scanf instructions = instruction | instruction instructions Remarques: •les entrées/sorties sont à conserver car elles ont une incidence directe avec l'extérieur, •les points d'entrée et de retour d'un bloc sont à conserver car ils ont une incidence directe sur la pile. Ils pourront être supprimés par un algorithme à base de propagation de constante. •es valeurs de retour sont à conserver car elles ont un impact externe (une fois que la fonction à retourné). •les appels procéduraux sont à conserver car les fonctions peuvent avoir des effets de bord. Pour l’écriture de l’algorithme, nous supposons queWorkListcorrespond à l’ensemble de tous les blocs correspondant à des sections critiques. Nous définissons les opérationsadd i to WorkListqui ajoute un bloc à l’ensembleWorkList,remove i from WorkListqui retire un bloc de l’ensembleWorkList, l’opérationmark imarque le bloc de codeicomme utile, l’opérationi is not markedqui teste si le bloc le blociest marqué comme utile. Question 2.1 –Initialisation Ecrire l’algorithme qui initialement remplitWorkListavec les blocs correspondant à des actions critiques. Nous considérons une action sous la forme ←yopz . Le bloc de code correspondant à l’initialisation d’une valeur y est noté def(y) . Question 2.2– Analyse d’une instruction Ecrire la seconde phase consistant à ajouter les antécédents utiles au calcul des composantes d’une instruction SSA.

Dans la séance sur la SSA, il a été introduit la notion de frontière de domination. DF(n) est défini comme le plus grand élément x dominé par n tel que ∀y,ndominey ⇒ (ydominex ou xdominey) . Il est possible de définir lanotion de frontière de domination inverse, c’est à dire en partant du bloc et remontant vers la première instruction. RDF(n) est défini comme le plus petit élément x dominant n tel que ∀y,ydominen ⇒ (ydominex ou xdominey) . De fait, RDF(n) définit le point d’entrée dans le superbloc qui permet d’accéder au bloc n . Question 2.3 –Point d’entrée dans les blocs Expliquer pourquoi les blocs d’entrées doivent être marqués comme utiles ?Compléter l’algorithme précédent pour ajouter aussi les blocs d’entrées. Question 2.4 –Algorithme de marquage Terminer l’algorithme précédant afin de procéder itérativement au marquage de tous les blocs. Question 2.4 –Algorithme de marquage Terminer l’algorithme précédant afin de procéder itérativement au marquage de tous les blocs. Question 25 –Algorithme de suppression des blocs non marqués Déterminer les opérations nécessaires afin de supprimer les blocs non marqués. (Conseil : se concentrer sur les branchements). Question 2.6 –Justification de la SSA Pourquoi fautil que le code soit sous forme de SSA pour que cet algorithme fonctionne ?