Static single assignment form

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:

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 à yy2 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, 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é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).



Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article Static single assignment form de Wikipédia en français (auteurs)

Игры ⚽ Поможем написать реферат

Regardez d'autres dictionnaires:

  • Static single assignment form — In compiler design, static single assignment form (often abbreviated as SSA form or SSA) is an intermediate representation (IR) in which every variable is assigned exactly once. Existing variables in the original IR are split into versions , new… …   Wikipedia

  • Static Single Assignment — Zwischencode ist Code, der im Verlauf eines Übersetzungsprozesses auf einer Abstraktionsebene zwischen der höheren Ausgangssprache und der in der Regel maschinennahen Zielsprache generiert wird. Es handelt sich in erster Linie um einen im… …   Deutsch Wikipedia

  • Single assignment — is used to describe a programming language or representation in which one cannot bind a value to a name if a value has already been bound to that name. In other words, a variable is initialized with (i.e. bound to) a value at the time that it is… …   Wikipedia

  • Assignment (computer science) — In computer programming, an assignment statement sets or re sets the value stored in the storage location(s) denoted by a variable name. In most imperative computer programming languages, assignment statements are one of the basic statements.… …   Wikipedia

  • Use-define chain — A Use Definition Chain (UD Chain) is a data structure that consists of a use, U, of a variable, and all the definitions, D, of that variable that can reach that use without any other intervening definitions. A definition can have many forms, but… …   Wikipedia

  • Continuation-passing style — In functional programming, continuation passing style (CPS) is a style of programming in which control is passed explicitly in the form of a continuation. Gerald Jay Sussman and Guy L. Steele, Jr. coined the phrase in AI Memo 349 (1975), which… …   Wikipedia

  • Dead code elimination — In compiler theory, dead code elimination is a compiler optimization to remove code which does not affect the program results. Removing such code has two benefits: it shrinks program size, an important consideration in some contexts, and it… …   Wikipedia

  • SafeTSA — is a static single assignment form (SSA) intermediate representation capable of representing all of the type safety of the Java programming language and the standard Java Virtual Machine (JVM) byte code.As of 2005, many optimizing compilers… …   Wikipedia

  • Dominator (graph theory) — For Dominating set problem, see Dominating set. In computer science, in control flow graphs, a node d dominates a node n if every path from the start node to n must go through d. Notationally, this is written as d dom n (or sometimes d n). By… …   Wikipedia

  • Zwischencode — Ein Zwischencode ist der Code, der im Verlauf eines Übersetzungsprozesses auf einer Abstraktionsebene zwischen der höheren Ausgangssprache und der in der Regel maschinennahen Zielsprache generiert wird. Es handelt sich in erster Linie um einen im …   Deutsch Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”