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

De
Publié par

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 constante si 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,…), ...
Publié le : samedi 24 septembre 2011
Lecture(s) : 21
Nombre de pages : 4
Voir plus Voir moins
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 cs’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ζ,cetψ. i Si lors du calcul, une valeur peut avoir admettre une valeur abstraitea1et une autre valeur abstraitealors la valeur prend le plus petit élément supérieur à la fois àa1et àa2que l’on notea1a2. Question 1.2i12 1 Pour le code cicontre, déterminer par la méthode précédente les constantes ? xi*17 1 ji Expliquer sur l’exemple précédent l’intérêt de la forme SSA pour la1 propagation de la constante ? (Remarque : pour répondre à cette question, ilii* 2 2 1 est possible de regarder le cas de la variableiqui accepte sous la forme SSA deux instancesietiet plus particulièrement ce qui se passerait si on ne ferait aucune 1 2 distinction entre les deux instancesieti). 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 i12 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 xi*17 1 programme en commençant par la première instruction et en ji terminant par la dernière instruction ? (Remarque : on réfléchira1 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). ij 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 –InitialisationEcrire l’algorithme qui initialement remplitWorkListavec les blocs correspondant à des actions critiques. Nous considérons une action sous la formeyopz. Le bloc de code correspondant à l’initialisation d’une valeuryest 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émentxdominé parntel quey,ndominey(ydominexou 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émentxdominantntel quey,ydominen(ydominexouxdominey). De fait, RDF(n)définit le point d’entrée dans le superbloc qui permet d’accéder au blocn. Question 2.3 –Point d’entrée dans les blocsExpliquer 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 SSAPourquoi fautil que le code soit sous forme de SSA pour que cet algorithme fonctionne ?
Soyez le premier à déposer un commentaire !

17/1000 caractères maximum.