Un graphe orienté qui représente l'ordre d'exécution possible et les transferts de contrôle entre blocs de base ou instructions dans un programme ; les nœuds représentent typiquement des blocs de base et les arêtes des sauts, branches et transitions par paliers.

Principe

Modéliser l'exécution d'un programme comme des transitions entre régions de contrôle afin que la question d'atteignabilité, de dominance, de vivacité et d'autres analyses centrées sur le contrôle puissent se formuler comme des problèmes de graphe sur des nœuds et arêtes représentant le flux du compteur de programme.

Démonstration

Une fonction avec un if/else et une boucle se cartographie en un CFG où un nœud conditionnel a deux arêtes sortantes vers les blocs 'then' et 'else' ; la boucle introduit une arête de retour du corps de la boucle vers l'en-tête, rendant le CFG cyclique.

Mauvaise application

Utiliser un CFG pour raisonner sur les dépendances de données (par ex. supposer que la définition d'une valeur circule le long des arêtes du CFG) ou supposer qu'une arête implique qu'une transition s'exécutera toujours avec la même fréquence — ces deux erreurs conduisent à des optimisations ou analyses incorrectes.

Conséquence

Une utilisation correcte permet des optimisations comme l'élimination de code mort, les transformations de boucles, des décisions d'inlining (combinées à de l'information interprocédurale) et des tâches de vérification comme prouver l'atteignabilité ou l'absence de certains chemins de contrôle.

Inversion

Considérer le programme uniquement comme un flux de données (graphe de calcul) où les constructions de contrôle sont encodées comme transformations de données ; cette inversion remplace les arêtes de contrôle explicites par des garde-fous basés sur les données et peut masquer les propriétés centrées sur le contrôle.

Limite

S'applique par défaut aux représentations intra-procédurales ; le contrôle interprocédural nécessite une extension (arêtes appel/retour, CFG interprocédural). Il n'encode pas les effets de bord sémantiques, les intercalations de concurrence ou le timing précis sauf extension.

Tension sémantique

Tension entre CFG et graphes de calcul/flux de données : le CFG insiste sur les transferts possibles du compteur de programme (contrôle), tandis que les graphes de données mettent l'accent sur la propagation des valeurs ; les confondre entraîne des analyses inappropriées.

Synthèse

Un graphe de flux de contrôle est l'abstraction du programme qui rend explicites les transitions possibles entre régions de programme sous forme d'arêtes orientées ; c'est la structure fondamentale pour les analyses et transformations dépendant de la forme du contrôle plutôt que du simple mouvement de données.