Temporal Compiladores

[pic 1]

Universidad Tecnológica Centroamericana

Facultad de Ingeniería y Arquitectura

Compiladores II

Investigación: Forma SSA

Docente:

Ing. Carlos Enrique Vallejo

Alumnos:

Ariel Martínez                11011200

Inti Velásquez                11341103

Juany Ramírez                 11511244

Campus Unitec TGU

4 de junio de 2018

Índice

Introducción        3

Forma de Asignación Estática Simple (SSA)        4

Beneficios        5

Función Phi        6

Ejemplos de compiladores que usan la forma SSA        10

GCC, The GNU Compiler Collection        10

LLVM        11

Java HotSpot, de Oracle        12

Conclusiones        15

Bibliografía        16

Introducción

La asignación de memoria consiste en el proceso de asignar una parte de la memoria para procesos específicos ya sea en tiempo de compilación o en tiempo de ejecución, si es en tiempo de compilación es asignación de memoria estática (SSA) y si es en tiempo de ejecución es asignación de memoria dinámica y si son variables locales a un grupo de sentencias de denomina automática, dicho proceso de asignación de memoria estática se hace durante la compilación antes de que el programa compilado sea ejecutado.

Forma de Asignación Estática Simple (SSA)

Es la representación de un programa o una estructura cuyo proceso es a veces realizado por una subrutina o una función, en donde se le asigna a una variable un espacio de memoria estático, como por ejemplo los tipos finals en java, los cons en javascript, los statics en C++, constant en ada, etc. que son variables constantes en memoria, sin embargo la forma SSA incluye que solo se pueden asignar una única vez, por lo que no se puede reutilizar las variables que se hayan declarado y asignado, este proceso es realizado por el compilador en tiempo de compilación, usualmente equivalente con Continuation-Passing Style (CPS) (Magno F., 2018).

Desarrollado en IBM por Cytron, Ferrante, Rosen, Wegman y Zadeck.

• ¿Por qué usar la forma SSA?

Simplifica el análisis y la optimización

• Importancia de la forma SSA

• Los papers de The Seminal hacen referencia de que la representación del programa Intermediario del SSA tiene más de 2,100 citaciones.
• Casi todos los libros de compiladores hablan acerca de la forma SSA.
• Google Scholar muestra más de medio millón de resultados al buscar “Static Single Assingment”.

Su nombre viene del hecho que cada variable solo puede ser definida en un lugar en el programa, en otras palabras, el programa entero contiene un solo punto en donde un valor es asignado a una variable.

Ejemplo:

[pic 2]

Para pasar las líneas de código escrito en Straight-Line Code se debe asegurar la asignación de cada variable una única vez.

Resultado:

[pic 3]

En otras palabras, si formamos un árbol con el código literalmente se formaría un árbol en donde los hijos no tienen hermanos, solo un único hijo.

Beneficios

El hecho de que la asignación se hace una sola vez simplifica significativamente varios procesos de optimización tales como la propagación constante y el análisis de variables de inducción. Por ejemplo, en forma de SSA, la propagación constante para la asignación x = c se puede realizar simplemente sustituyendo c por x sin considerar el alcance de esta asignación. Debido a los beneficios, la forma SSA se ha utilizado como una representación intermedia en varios compiladores de optimización recientes (Matsuno Y., 2018).

El formulario de SSA no solo simplifica la asignación de registros, sino que también ayuda a realizar optimizaciones como la eliminación de subexpresiones comunes, el movimiento de códigos invariable por bucle o la programación de instrucciones.

El uso de la representación de SSA y un CFG (gráfico de flujo de control) ayuda mucho con la implementación de todo tipo de pases de optimización, o al menos lo hace posible.

Al realizar el análisis de SSA; solo crea una nueva revisión para cada nueva asignación (definición) de una variable distinta, identifica las revisiones en los sitios de uso (es posible que necesite crear una instrucción PHI lógica si las revisiones múltiples llegan a la instrucción).

Hay una buena razón por la cual la mayoría de los compiladores (modernos) descomponen el código en bloques, y confían en SSA y CFG para la mayoría de los pases de optimización, incluidas la accesibilidad y las asignaciones de registros.

Función Phi

Tener un solo punto de asignación estática para una variable trae retos al abandonar los programas de straight-line code, pasando a programas con grafos de flujo más complejos:

[pic 4]

Una pregunta importante en este caso es que una vez se convierta este programa a la forma SSA (derecha), ¿Cuál definición de ‘b’ se debería usar en L5?

Podemos observar a través del grafo de flujo que la definición de ‘b’ que se utilizará en L5 depende de a través de cual camino fluya la ejecución. Si la ejecución llega a L5 a través de L4 entonces debemos utilizar b1, pero si llega a través de L2 debemos utilizar b0.

Las funciones Phi son utilizadas para representar este comportamiento. Las funciones Phi tienen la semántica de un multiplexor, copiando la definición correcta de acuerdo con cual camino son alcanzados en el flujo de ejecución.

[pic 5]

Como se observa en la imagen, un conjunto de N funciones Phi con M argumentos, cada una al comienzo de cada bloque básico, representa M copias paralelas. Cada copia lee N entradas y escribe en N salidas.

Los compiladores que utilizan la forma SSA tienen un paso antes de generar el código en ensamblador llamado la eliminación SSA en el cual las funciones Phi son reemplazadas con instrucciones.

[pic 6]

En este caso, colocar la copia de b2=b0 no es sencillo, ya que L2 está vinculado a L5 a través de un eje crítico; Los ejes críticos son aquellos que conectan a un bloque con múltiples sucesores a otro bloque con múltiples predecesores. Si la copia se coloca entre L1 y L2 se crearía una redundancia parcial.

...