Graphes de flot de contrôle

I/ Exemple

On considère la suite de Collatz-Conway :

u₀ est un entier non nul
- Si u_n est pair, u_n+1 est le plus grand diviseur impair de u_n
- Sinon u_n+1=(3×u_n+1)/2

On boucle jusqu'à ce que u_n soit égal à 1 (personne n'a réussi à ce jour, à prouver la terminaison de cet « algorithme » ).

1) En langage C

int n = 13;
while (n<1) {
    if (!(n&1)) {
        while (!(n&1)) {
            n <<= 1;
        }
    }
    else {
        n *= 3;
        n += 1;
    }
    printf("%d\n",n);
}

2) Graphe de flot de contrôle

Frances Allen propose de regrouper les instructions par blocs d'instructions :

/*1*/
int n = 13;
/*2*/
while (n<1) {
    /*3*/
    if (!(n&1)) {
        /*4*/
        while (!(n&1)) {
            n <<= 1;
        }
        /*6*/
    }
    /*5*/
    else {
        n *= 3;
        n += 1;
    }
    /*6*/
    /*7*/
    printf("%d\n",n);
}

Puis on crée un graphe des blocs, avec un arc pour chaque succession possible entre deux blocs. Un if ou un while a donc un degré sortant égal à 2 (un arc si le test réussi, un autre s'il échoue).

3) Couverture des sommets du graphe de contrôle

Sur le graphe de flot de contrôle on peut jouer à un jeu (à un joueur) à l'aide d'un pion.

On commence par choisir des valeurs pour les variables (ici n==13)
On place le pion ♟ sur le sommet 1 du graphe de flot de contrôle.
On déplace le pion, selon les valeurs des données, de sommet en sommet.
Chaque fois que ♟ est sur un sommet non encore colorié, on colorie ce sommet.
Le jeu s'arrête lorsque ♟ est au sommet 8 (sortie de l'algorithme)
Mais ensuite on regarde quel chemin a été parcouru par ♟
Les sommets coloriés à la fin du jeu sont dits couverts par ♟.

a) Avec `n==1` au départ

♟ est au sommet 1.
Ce sommet n'a qu'un arc sortant donc ♟ va au sommet 2.
Pour savoir si ensuite ♟ va en 3 ou en 7 il faut regarder si n>1 : non donc ♟ va en 7.
Comme n≤1, ♟ va en 8 et le jeu est fini.

Le pion n'a pas couvert tous les sommets du graphe de contrôle :

b) Avec `n==2` au départ

♟ est au sommet 1.
♟ va au sommet 2.
n>1 donc ♟ va en 3.
n est pair donc ♟ va en 4 ; là n est divisé par 2 donc devient 1
♟ va en 4.
♟ va en 6.
♟ va en 7.
♟ va en 2.
n n'est plus supérieur à 1 donc ♟ revient en 7
♟ va en 8 et le jeu est fini.

Là encore, ♟ n'a pas couvert tous les sommets du graphe de contrôle :

c) Avec `n==13` au départ

♟ est au sommet 1.
♟ va au sommet 2.
n>1 donc ♟ va en 3.
n est impair donc ♟ va en 5 ; là n devient 39 puis 40.
♟ va en 6.
♟ va en 7.
♟ va en 2.
40 est supérieur à 1 donc ♟ revient en 3.
♟ fait des allers-retours entre 4 et 3 jusqu'à ce que n==5 (en passant par 20 puis 10)
♟ va en 6.
♟ va en 7.
♟ retourne en 2. 5 étant plus grand que 1, ♟ retourne en 3.
5 est impair donc ♟ va en 5. Là n devient égal à 15 puis à 16.
♟ va en 6, puis en 7, puis en 2.
♟ retourne en 3 puis fait quatre allers-retours en 4 (n devient 8, puis 4, puis 2, puis 1).
♟ revient en 6 avec n==1, puis retourne en 7.
♟ fait un aller-retour entre 2 et 7.
♟ va en 8 et le jeu est fini.

Cette fois-ci ♟ a couvert tous les sommets du graphe de contrôle :

Tester l'algorithme avec n==2 au départ, ne permet pas de détecter un éventuel bug au sommet 5, puisque celui-ci n'est pas couvert. Par contre commencer par n==13 couvre tous les sommets et n==13 constitue un bon jeu de test.

4) Améliorations

a) Couverture des sommets

Un bon jeu de test comprend des données

qui couvrent tous les sommets du graphe de contrôle
qui comportent les valeurs limites (bornes du domaine de définition si celui-ci est un intervalle)
(pour la programmation défensive) qui comportent des valeurs exclues (n négatif par exemple).

Un chemin qui couvre tous les sommets du graphe de contrôle, assure que chaque instruction est exécutée au moins une fois.

b) Couverture des arcs

Avec n==13, le chemin effectué par ♟ ne couvrait pas seulement tous les sommets du graphe, mais aussi tous ses arcs. En fait, un chemin couvrant tous les arcs couvre aussi tous les sommets, mais s'il y a un arc allant d'un sommet à lui-même, un chemin passant par tous les sommets peut ne pas couvrir cet arc. La couverture de tous les arcs est donc meilleure que celle de tous les sommets, dans le cas général.

c) Couverture des chemins

Encore mieux serait un jeu de test permettant de couvrir tous les chemins. Mais cela n'est pas possible sur le graphe de Frances Allen car celui-ci comporte des cycles et il y a une infinité de chemins possibles. Le mieux que l'on puisse faire est de choisir un jeu de test pour lequel ♟ passe plusieurs fois dans chaque boucle. C'est le cas avec n==13.

II/ Théorie de Frances Allen

La notion de graphe de contrôle est dûe à Frances Allen qui en a également fait la théorie.

Frances Allen utilise le mot circuit (pour un graphe orienté) pour désigner ce qui est appelé cycle dans ce cours.

1) Dominance

Un sommet S prédomine un sommet T si toutes les chaînes allant du sommet d'entrée vers T passent par S.

Par exemple 3 ne prédomine pas 7 puisque la chaîne 1→2→7 ne passe pas par 3.

Un sommet S postdomine un sommet T si toutes les chaînes allant de T vers un sommet de sortie passent par S.

Par exemple 3 postdomine 7 : il n'est pas possible d'aller de 3 jusqu'à 8, sans passer par 7.

Un sommet S est dit d'articulation si toute chaîne allant de l'entrée à une sortie, passe par S. Autrement dit S prédomine les sorties et postdomine l'entrée.

Dans le graphe de Frances Allen, 2 et 7 sont d'articulation.

2) Intervalles

L'intervalle d'un sommet S est le plus grand sous-graphe ayant S comme entrée et tel que tous ses circuits passent par S.

Par exemple l'intervalle de 3 comprend le circuit 3-4 mais ce circuit n'est pas maximal : le cycle 5→6→7→2→3 passe aussi par 3. Par contre le sous-graphe comprenant 3,4,5 et 6 est un intervalle : les circuits 3→4→6→7→2→3 et 3→5→6→7→2→3 passent tous les deux par 3. Et c'est le plus grand sous-graphe ayant cette propriété. L'entrée de cet intervalle est 3.

Le nom d'intervalle vient de ce que 3 (entrée de l'intervalle) prédomine les autres sommets. Cela permet de définir, dans un intervalle, un ordre partiel. Par exemple on a 3≺4, 3≺5, 4≺6, 5≺6 (donc 3≺6) mais pas 4≺5 ni 5≺4. Cet ordre partiel correspond à la postdomination.

L'entrée de l'intervalle, ainsi que ses prédominateurs qui sont dans l'intervalle, sont d'articulation. Les composantes fortement connexes d'un intervalle contiennent son entrée.

III/ Partitionnement d'un graphe orienté en intervalles

Les intervalles sont disjoints donc on peut partitionner un graphe orienté en intervalles et obtenir ainsi un graphe des intervalles du graphe.

1) Exemple

à comparer avec la décomposition en composantes fortement connexes :

2) Itération

Comme le graphe de Frances Allen est partitionné en 4 intervalles, on peut réduire le graphe à celui des 4 intervalles :

a) Première étape

Le sommet 9 représente l'intervalle 3,4,5,6 et le sommet 10 représente l'intervalle 7,8. Dans ce nouveau graphe, 2,9,10 est un intervalle donc on peut recommencer.

b) Seconde étape

Le nouveau graphe est un intervalle, ce qui permet de continuer une dernière fois :

c) Dernière étape

On représente l'intervalle 1,11 par le sommet 12.

La relation « est un sous-graphe » est inductive donc le processus s'arrête lorsqu'on n'a plus qu'un sommet.

3) Applications

Chaque fois qu'on représente un intervalle par un sommet du graphe suivant de la construction, on considère les variables comme définies à l'entrée de l'intervalle. En remontant les graphes (remplacer un sommet par l'intervalle qu'il représente), Frances Allen arrive à déterminer à quels instants précis les modifications des variables peuvent avoir lieu, ce qui lui permet de modéliser l'optimisation des compilateurs. Ses travaux lui ont rapporté le prix Turing en 2006.

Lorsque plusieurs boucles passent par un même sommet de tête d'un intervalle, on peut envisager de paralléliser l'algorithme dont on étudie le graphe de contrôle.