Static single assignment form

En compilation, 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 de ne permettre à une variable d'ê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 faîtes à 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:

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

Les algorithmes d'optimisations des compilateurs autorisés ou bien largement améliorés par l'utilisation de la forme SSA incluent:

• la propagation de constantes
• l'élimination du code mort
• la réduction partielle de duplication
• la réduction de force
• 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 contrôle de flux:

On remarque qu'à l'étape "x 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_y2 selon le flux duquel on vient. Comment peut on connaitre la variable à utiliser?

Pour cela on utilise une déclaration spécial, appelé Φ (Phi) et qui est écrite en début de bloc. Cette fonction générera une nouvelle version de y, y₃ qui 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é x₂ atteint cette position, il n'y a donc pas d'ambiguïté.

Une question plus général est de savoir, pour un graphe de contrôle de flux donnée 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).

• Portail de la programmation informatique