Graphe de flot de contrôle

Graphes de flot de contrôle simplifiées^[1]

En informatique, un graphe de flot de contrôle (abrégé en GFC, control flow graph ou CFG en anglais) est une représentation sous forme de graphe de tous les chemins qui peuvent être suivis par un programme durant son exécution.

Vue d'ensemble

Dans un GFC, les nœuds du graphe representent un bloc de base, c'est-à-dire un bout de code d'un seul tenant sans sauts ni cibles de sauts. Les cibles de sauts marquent le début d'un bloc de base, tandis que les sauts en marquent la fin. Les arcs représentent les sauts dans le flot de contrôle. La plupart des représentations d'un CFG comprennent deux blocs spéciaux : le bloc d'entrée, par lequel on entre dans le graphe de flot de contrôle et le bloc de sortie, par lequel on le quitte.

Les diagrammes de flot de contrôle sont essentiels pour de nombreuses optimisations de compilation et outils d'analyse statique.

Exemple

Prenons le fragment de code suivant :

0: (A) t0 = read_num
1: (A) if t0 mod 2 == 0
2: (B)   print t0 + " is odd."
3: (B)   goto 5
4: (C) print t0 + " is even."
5: (D) end program

On a quatre blocs de base :

• le bloc A, allant de la ligne 0 à la ligne 1
• le bloc B, allant de la ligne 2 à la ligne 3
• le bloc C, constitué par la ligne 4
• le bloc D, constitué par la ligne 5

A est le bloc d'entrée. D est le bloc de sortie. Les lignes 4 et 5 sont des cibles de sauts.

Le graphe de flot de contrôle associé à ce fragment comporte les arcs suivants :

• de A en B,
• de A en C (saut si t0 est impair),
• de B en D (saut inconditionnel)
• de C en D.

Atteignabilité

L'atteignabilité est une autre propriété de graphe utile en optimisation.

Si un bloc ou une portion du graphe n'est pas connecté au bloc d'entrée, ce bloc ne peut jamais être atteint durant l'exécution, et il s'agit de code mort qui peut être supprimé sans danger.

Si le bloc de sortie ne peut pas être atteint, c'est le signe d'une boucle infinie. Toutes les boucles infinies ne sont pas détectables, bien entendu, voir le problème de l'arrêt.

Le code mort et certaines boucles infinies sont possibles même si le programmeur ne les a pas codées explicitement ainsi. En effet, les optimisations comme la propagation de constantes et le constant folding suivis par des enchaînements de sauts (jump threading) peuvent réduire plusieurs blocs de base en un seul, ce qui fait que des arcs sont supprimés du GCF, ce qui peut déconnecter certaines partie du graphe.

Relation de domination

On dit qu'un bloc M domine un bloc N si chaque chemin qui atteint le bloc N passe par M. Le bloc d'entrée domine tous les blocs. En sens inverse, on dit qu'un bloc M postdomine un bloc N si chaque chemin de N vers le bloc de sortie passe par M. Le bloc de sortie postdomine tous les blocs.

Un bloc M domine immédiatement un bloc N si M domine N et s'il n'existe pas de bloc intermédiaire tel que M domine P et P domine N. En d'autres termes, M est le dernier dominant pour tous les chemins depuis le bloc d'entrée vers N. Chaque bloc a un seul dominant unique. De même, on peut parler de postdomination immédiate.

L'arbre de domination est un graphe décrivant les relations de domination immédiate. Ce graphe est un arbre puisque chaque bloc a un seul dominant immédiat. La racine de l'arbre est le bloc d'entrée. L'arbre de domination peut être déterminé efficacement grâce à l'algorithme de Lengauer-Tarjan. En sens inverse, l'arbre de postdomination a pour racine le bloc de sortie.

Arcs spéciaux

Pour les besoins du traitement, on a besoin d'introduire artificiellement certains arcs et d'en traiter à part d'autres.

Un arc critique est un arc qui n'est ni le seul arc à partir de son bloc source, ni le seul arc à arriver à son bloc destination. De tels arcs doivent être coupés en deux : un nouveau bloc doit être créé au milieu de l'arc critique de manière à pouvoir traiter cet arc sans affecter les autres arcs.

Un arc en arrière est un arc qui pointe vers un bloc déjà rencontré lors d'un parcours en profondeur du graphe. Ces arcs sont typiques des boucles.

Un arc anormal est un arc dont la destination est inconnue. Les constructions de gestion d'exception peuvent en produire. Ces arcs ont tendance à empêcher l'optimisation.

Un arc impossible, connu également sous le nom de faux arc est un arc qui a été ajouté au graphe uniquement pour préserver la propriété que le bloc de sortie postdomine tous les blocs. Il ne peut jamais être parcouru.

Traitement des boucles

L'en-tête de boucle est le point d'entrée de la boucle. C'est un bloc dominant qui est la cible de l'arc en arrière de la fin de boucle. Il domine tous les blocs du corps de la boucle.

Supposons qu'un bloc M soit dominant tout en étant la cible de plusieurs arcs, dont certains sont des arcs en arrière, de telle sorte que M est un en-tête de boucle. Il est intéressant pour plusieurs optimisations de diviser M en deux blocs, M_préboucle et M_boucle. Le contenu de M et des arcs inverses vont dans M_boucle, tandis que les autres arcs sont modifiés pour pointer vers M_préboucle. Enfin, un nouvel arc est ajouté pour permettre de passer de M_préboucle à M_boucle (et M_préboucle domine donc immédiatement M_boucle). Au départ, M_préboucle ne contient pas d'instructions, mais des passes d'optimisation comme le déplacement des invariants de boucle peuvent lui ajouter du contenu. M_préboucle est appelé le pré-entête de boucle tandis que M_boucle est l'entête de boucle.

Références

1. ↑ Joseph Poole, NIST (1991). A Method to Determine a Basis Set of Paths to Perform Program Testing.

Voir aussi

Articles connexes

• Organigramme de programmation

Liens externes

• (en) The Machine-SUIF Control Flow Graph Library
• (en) GNU Compiler Collection Internals
• (en) Infrastructure for Profile Driven Optimizations in GCC Compiler, par Zdeněk Dvořák et al.