Êtes-vous un étudiant de l'EPFL à la recherche d'un projet de semestre?
Travaillez avec nous sur des projets en science des données et en visualisation, et déployez votre projet sous forme d'application sur Graph Search.
Concept
Static single assignment form
Résumé
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.
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
la
l'allocation de registres
Convertir du code ordinaire dans une représentation SSA est essentiellement un problème simple.
Source officielle
À propos de ce résultat
Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.
Cours associés (2)
CS-420: Advanced compiler construction
Students learn several implementation techniques for modern functional and object-oriented programming languages. They put some of them into practice by developing key parts of a compiler and run time
CS-320: Computer language processing
We teach the fundamental aspects of analyzing and interpreting computer languages, including the techniques to build compilers. You will build a working compiler from an elegant functional language in
Publications associées (35)
Personnes associées (8)
Concepts associés (2)
Constant folding
Constant folding and constant propagation are related compiler optimizations used by many modern compilers. An advanced form of constant propagation known as sparse conditional constant propagation can more accurately propagate constants and simultaneously remove dead code. Constant folding is the process of recognizing and evaluating constant expressions at compile time rather than computing them at runtime. Terms in constant expressions are typically simple literals, such as the integer literal 2, but they may also be variables whose values are known at compile time.
Optimizing compiler
In computing, an optimizing compiler is a compiler that tries to minimize or maximize some attributes of an executable computer program. Common requirements are to minimize a program's execution time, memory footprint, storage size, and power consumption (the last three being popular for portable computers). Compiler optimization is generally implemented using a sequence of optimizing transformations, algorithms which take a program and transform it to produce a semantically equivalent output program that uses fewer resources or executes faster.