Static single assignment form

En compilation informatique, static single assignment form (SSA), en français, forme statique à affectation unique est une représentation intermédiaire (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ée 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 dite « 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

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és ou bien largement améliorés par l'utilisation de la forme SSA incluent:

• la simplification de sous-expressions constantes (constant folding ou constant propagation)
• la suppression du code mort
• la réduction partielle de duplication (en)
• la réduction de force (en)
• l'allocation de registres

Conversion vers SSA

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 :

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: x₁ et x₂, chacune assignée une unique fois. De la même façon, on traite les autres variables, ce qui permet d'obtenir ceci:

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 à y₁ ou à y₂ selon le flux duquel on vient. Comment peut on connaître la variable à utiliser?

Pour cela on utilise une déclaration spéciale, appelé Φ (Phi) et qui est écrite en début de bloc. Pour générer la nouvelle version de y (y₃), cette fonction devra choisir entre y₁ et y₂ selon le bloc dont on vient:

Maintenant, l'utilisation de la variable y dans le dernier bloc se résume à l'utilisation de y₃. 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ée x₂, 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ée 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 case mémoire (ou le même registre). Dans l'exemple ci-dessus, les variables y₁ et y₂ correspondront à la même case mémoire, si bien que y₃ recevra automatiquement l'une ou l'autre selon la branche empruntée lors de l'exécution.