Graphe de flot de contrôle
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. Dans un GFC, les sommets du graphe représentent 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. Prenons le fragment de code suivant : 0: (A) t0 = read_num 1: (A) if t0 mod 2 == 0 2: (B) print t0 + " is even." 3: (B) goto 5 4: (C) print t0 + " is odd." 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. L'accessibilité 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.
