Static single assignment form

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher

En compilation informatique, Static single assignement form (abrégé en SSA) est une représentation intermédiaire (abrégé RI) du code source d'un programme dont la particularité est d'astreindre chaque variable à n'être affectée qu'une et une seule fois. Les variables existantes dans la première représentation sont divisées en « versions », les nouvelles variables reprenant le nom original avec une extension.

La représentation SSA a été développé par Ron Cytron, Jeanne Ferrante, Barry K. Rosen, Mark N. Wegman, et F. Kenneth Zadeck, chercheurs pour IBM dans les années 1980.

Les compilateurs de langages fonctionnels tel que pour le Scheme, ML et Haskell utilisent généralement une technique dites "continuation-passing style" (CPS) alors que SSA est utilisé principalement pour des langages procéduraux tel que le C ou le Fortran. Ces deux représentations sont proches et les optimisations et transformations faites à l'une peuvent s'appliquer à l'autre.

Bénéfices[modifier | modifier le code]

L'intérêt principal de SSA est la simplification et l'amélioration des résultats de nombreuses optimisations, en simplifiant les propriétés des variables. Par exemple, soit le code suivant:

y := 1
y := 2
x := y

Les humains peuvent voir que la première affectation n'est pas nécessaire, car la valeur de y utilisée à la troisième ligne vient de la deuxième affectation de y. Un programme devrait faire une analyse d'atteinte des définitions pour le déterminer. Mais si le programme est sous la forme SSA, alors c'est immédiat ; dans la version suivante, il est évident que y1 n'est pas utilisé :

y1 := 1
y2 := 2
x1 := y2

Les algorithmes d'optimisation des compilateurs qui sont autorisées ou bien largement améliorées par l'utilisation de la forme SSA incluent:

Conversion vers SSA[modifier | modifier le code]

Convertir du code ordinaire dans une représentation SSA est essentiellement un problème simple. Il suffit à chaque assignation d'une variable de la remplacer par une nouvelle variable "versionnée" (la variable x se décompose en x1, x2, x3... lors des assignations successives). Enfin, à chaque utilisation de la variable, on utilise la version correspondant à cette position dans le code. Par exemple, à partir de ce graphe de flot de contrôle :

Un exemple de graphe de contrôle de flux, avant une conversion SSA

On remarque qu'à l'étape "x \leftarrow x - 3" , on peut remplacer dans la partie gauche de l'expression la variable x par une nouvelle variable sans changer le fonctionnement du programme. On utilise cela dans SSA en créant deux nouvelles variables: x1 et x2, chacune assignée une unique fois. De la même façon, on traite les autres variables, ce qui permet d'obtenir ceci:

Un exemple de graphe de contrôle de flux, partiellement converti en SSA

Il a été possible de définir à quelle version de la variable on se réfère, à l'exception d'un cas: La variable référence de y dans le dernier bloc peut aussi bien se référer à y1 ou à y2 selon le flux duquel on vient. Comment peut on connaitre la variable à utiliser?

Pour cela on utilise une déclaration spéciale, appelé Φ (Phi) et qui est écrite en début de bloc. Cette fonction générera une nouvelle version de y, y3 qui devra choisir entre y1 et y2, selon le bloc dont on vient:

Un exemple de graphe de contrôle de flux, conversion complète en SSA


Maintenant, l'utilisation de la variable y dans le dernier bloc se résume à l'utilisation de y3. On pourrait se poser la question d'utiliser la fonction Φ sur x. Ce n'est pas nécessaire ici car une seule version de x, appelé x2 atteint cette position, il n'y a donc pas d'ambiguïté.

Une question plus générale est de savoir, pour un graphe de flot de contrôle donné, comment déterminer quand doit être inséré la fonction Φ et pour quelles variables. C'est une question à laquelle on peut répondre de façon informatique via le concept de "frontières de dominance".

Note: En réalité la fonction Φ n'est pas implémentée: on utilise plutôt des marques pour que le compilateur place la valeur de toutes les variables groupées dans la fonction Φ dans la même zone mémoire (ou le même registre).