Sur le flot du contrôle

Le dernier billet sur la syntaxe a posé les bases nécessaires à l’analyse du code, grâce à une représentation abstraite. Nous allons maintenant utiliser le même langage de programmation jouet défini auparavant pour expliquer ce que sont les optimisations réalisées dans les compilateur. Mais tout d’abord, il est nécessaire de changer encore une fois de représentation abstraite du code.

Branches conditionnelles

Reprenons notre langage du billet sur la syntaxe : dans celui-ci, un programme est une liste d’instructions assignant des valeurs à des variables, avec à la fin un return. Aujourd’hui, nous allons compliquer le langage en y rajoutant une structure conditionnelle introduite par les mot-clés if et else. Voilà ce que donne le nouvel arbre de syntaxe de notre langage :

type exp =
    | Var of string
    | Const of int
    | Plus of exp * exp
    | Minus of exp * exp
type cond =
    | Equal of exp * exp
    | Less of exp * exp
type stm =
    | Assignment of string * exp
    | Return of exp
    | If of cond * program * program
and program = stm list

La ligne ajoutée la plus importante est-celle ci : If of cond * (stm list) * (stm list), qui utilise un nouveau type cond qui décrit la manière de comparer deux expressions. Pour l’instant nous pouvons tester l’égalité (Equal) et si une valeur est strictement plus petite qu’une autre (Less). Prenons tout de suite un exemple de programme concret pour voir à quoi cela correspond :

x = 3;
y = 2;
if (y - 1 < x) {
    w = 5;
} else {
    z = 10;
    return z;
}
return y;

Avec cet ajout, notre langage se complique énormément, car désormais chaque branche if ou else peut elle-même contenir un programme entier, emboîté comme dans des poupées russes. Ceci soulève de nouvelles questions ; par exemple, le programme suivant (correct selon notre arbre de syntaxe abstrait) peut-il être exécuté ?

if (1 + 1 == 2) {
    return 0;
} else {
    x = 2;
}

La réponse naturelle est oui, car ici on sait que \(1 + 1 = 2\), donc lors de l’exécution c’est la branche return 0; qui sera prise et le programme va retourner 0. Mais dans le cas général, il est impossible de savoir quelle branche du if sera prise à l’exécution, surtout si par exemple la condition dépend d’entrées de l’utilisateur au moment de l’exécution. Ainsi, à la compilation, il nous faut prendre des hypothèses conservatives et prévoir tous les cas ; dans ce cas-ci, il nous faut aussi considérer ce qui se passe lorsque la branche else est prise à l’exécution.

Or ici si la branche else est prise, le programme va s’exécuter sans jamais rencontrer d’instruction return, ce qui est normalement interdit. Il nous faut donc rajouter une nouvelle règle à notre langage qui restreint le nombre de programmes valides : toutes les exécutions du programme doivent rencontrer une instruction return à un moment donné. Voici la fonction récursive en OCaml qui permet de faire cette vérification sur l’arbre de syntaxe abstrait, fonction dont la simplicité illustre une fois de plus la puissance de la programmation fonctionnelle dans ce genre de situations :

let rec check_return (program : stm list) : bool = match program with
  | [] -> false
  | (Assignment _ )::rest -> check_return rest
  | (Return _ )::_ -> true
  | (If (_ ,branch_true,branch_false))::rest ->
    let return_in_if =
     (check_return branch_true) && (check_return branch_false)
    in
    return_in_if || (check_return rest)

Flot du contrôle

Avec l’apparition de branches conditionnelles, l’exécution de nos programmes se complique et il devient utile de réfléchir plus avant à cette problématique. Pour cela, introduisons la notion de contrôle. Le contrôle est l’instruction ou l’expression qui est en train d’être évaluée par le processeur lors de l’exécution d’un programme. Sans conditionnelles, le contrôle se déplace linéairement dans le code : une fois qu’une instruction est exécutée, on passe à la suivante, jusqu’à atteindre un return qui met fin à l’exécution. Mais avec les conditionnelles, on ne peut pas « passer à l’instruction suivante » car il y a deux possibilités. À cause de cela, le contrôle peut prendre plusieurs chemins différents en fonction de la valeur vraie ou fausse des conditions des if. Comment représenter tous ces chemins différents ?

La réponse vient encore une fois des mathématiques, car nous allons utiliser un graphe appelé graphe de flot de contrôle. Construire le graphe à partir d’un arbre de syntaxe abstrait est simple :

• chaque instruction est un nœud du graphe ;
• deux instructions non-if qui se suivent dans un programme correspondent à une arrête dans le graphe ;
• l’instruction if possède deux arrête sortantes vers chacune des premières instructions dans les deux branches du if ;
• la dernière instruction d’un if a une arrête vers la première instruction après le if;
• chaque instruction return a une arrête sortant vers un nœud spécial appelé exit qui signifie la fin de l’exécution.

Voici le graphe du flot de contrôle de notre premier exemple :

Une première optimisation

Nous arrivons maintenant au moment où tous nos laborieux efforts de modélisation du code vont commencer à payer. En effet, le graphe de flot de contrôle contient toutes les informations nécessaires afin de comprendre comment les données et les valeurs transitent dans le programme.

Avant de développer tout cela plus formellement dans de prochains billets, voyons une première application assez puissante. Vous avez peut-être remarqué que l’instruction w = 5; dans la branche « vrai » du if ne sert à rien, car on n’utilise pas la valeur de w dans la suite. Grâce au graphe de flot de contrôle, il est possible de construire un algorithme qui détecte automatiquement ce genre d’instructions « inutiles ». Décrivons son fonctionnement dans les grandes lignes.

On part du graphe de flot de contrôle, et plus particulièrement de son nœud exit. Ensuite, on suit les arrêtes du graphe à l’envers et l’on maintient un ensemble de variables « utiles » de la manière suivante :

• lorsqu’on rencontre un nœud return <exp>;, toutes les variables dans <exp> sont utiles ;
• lorsqu’on rencontre un nœud x = <exp>;, alors si x est utile, toutes les variables dans <exp> sont utiles ;
• toutes les variables d’un nœud if(<exp>) sont utiles.

Après avoir remonté tous les nœuds jusqu’au début du graphe, on regarde quelles variables ne sont pas dans l’ensemble « utile ». On peut alors supprimer les instructions qui définissent ces variables « inutiles », et ainsi optimiser le programme qui tournera plus vite car comportant moins d’instructions pour le même effet.

Parce que la plupart des compilateurs implémentent ce genre d’optimisation, rajouter du code « inutile » dans un programme n’a généralement pas d’effet sur la performance. Nous verrons par la suite quel genre d’inneficacités dans un programme conduit vraiment à une chute de performance, et quelles autres sont corrigées automatiquement par les compilateurs.

Pour aller plus loin

• Un plugin Eclipse permet de visualiser le graphe de flot de contrôle de son programme Java directement dans l’IDE.