Êtes-vous un étudiant de l'EPFL à la recherche d'un projet de semestre?
Travaillez avec nous sur des projets en science des données et en visualisation, et déployez votre projet sous forme d'application sur Graph Search.
Concept
Graphe de flot de contrôle
Résumé
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.
Source officielle
À propos de ce résultat
Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.