Generación de Código Definicion

[pic 1]

[pic 2][pic 3][pic 4][pic 5]

Contenido

Generación de Código        1

Definicion        1

Cuestiones sobre el diseño de un generador de código        1

Entrada del generador de código        1

Selección de instrucciones        2

Asignación de registros        2

El lenguaje destino        2

Costos del programa y las instrucciones        3

Direcciones en el código destino        3

Bloques básicos y grafos de flujo        3

Optimización de los bloques básicos        4

Un generador de código simple        4

El algoritmo de generación de código        5

Optimización de mirilla (peephole)        5

Repartición y asignación de registros        6

Selección de instrucciones mediante la rescritura de árboles        6

Esquemas de traducción de árboles        6

Generación de código óptimo para las expresiones        6

Generación de código de programación dinámica        7

Evaluación contigua        7

El algoritmo de programación dinámica        7

Generación de Código

Definicion

Un generador de código tiene tres tareas principales: selección de instrucciones, repartición y asignación de registros, y ordenamiento de instrucciones.

• La selección de instrucciones implica la selección de instrucciones apropiadas de la máquina destino para implementar las instrucciones de la representación intermedia.

• La repartición y asignación de registros implica decidir qué valores mantener en qué registros.

• El ordenamiento de instrucciones implica decidir en qué orden se va a programar su ejecución.

Cuestiones sobre el diseño de un generador de código

El criterio más importante para un generador de código es que debe producir código correcto. La precisión de este código es muy relevante, debido al número de casos especiales que podría enfrentar un generador de código. Dada la importancia en la precisión del código, diseñar un generador de código de manera que pueda implementarse, probarse y mantenerse con facilidad es una meta primordial de diseño.

Entrada del generador de código

La entrada del generador de código es la representación intermedia del programa fuente producido por la interfaz de usuario, junto con la información en la tabla de símbolos que se utiliza para determinar las direcciones en tiempo de ejecución de los objetos de datos denotados por los nombres en la representación intermedia.

Selección de instrucciones

El generador de código debe asignar el programa de representación intermedia a una secuencia de código que la máquina de destino pueda ejecutar. La complejidad de realizar esta asignación se determina mediante factores como:

•  El nivel de la representación intermedia.
•  La naturaleza de la arquitectura del conjunto de instrucciones.
•  La calidad deseada del código generado.

Si la representación intermedia es de alto nivel, el generador de código puede traducir cada instrucción de este tipo en una secuencia de instrucciones de máquina, usando plantillas de código. Sin embargo, tal generación de código instrucción por instrucción produce a menudo código de baja calidad, que requiere de más optimización.

Asignación de registros

Un problema clave en la generación de código es decidir qué valores guardar en qué registros. Los registros son la unidad computacional más veloz en la máquina destino pero, por lo general, no tenemos suficientes como para contener todos los valores. Los valores que no se guardan en registros deben residir en la memoria. Las instrucciones que involucran operandos de registros son invariablemente más cortas y rápidas que las que involucran el uso de operandos en la memoria, por lo que la utilización eficiente de los registros es muy importante. A menudo, el uso de los registros se divide en dos sus problemas:

1. Repartición de registros, durante la cual seleccionamos el conjunto de variables que residirán en los registros, en cada punto del programa.

2. Asignación de registros, durante la cual elegimos el registro específico en el que residirá una variable.

El lenguaje destino

Un requisito previo para diseñar un buen generador de código es estar familiarizado con la máquina destino y su conjunto de instrucciones.

Costos del programa y las instrucciones

A menudo asociamos mi costo con la compilación y la ejecución de un programa. Dependiendo del aspecto del programa que nos interese optimizar, algunas medidas de costos comunes son la longitud del tiempo de compilación y el tamaño, el tiempo de ejecución y el consumo de energía del programa de destino. La determinación del costo actual de compilar y ejecutar un programa es un problema complejo.

Por simplicidad, consideraremos que el costo de una instrucción será de uno más los costos asociados con los modos de direccionamiento de los operandos. Este costo corresponde a la longitud en palabras de la instrucción.

Direcciones en el código destino

• Un área de Código determinada en forma estática, la cual contiene el código destino ejecutable. El tamaño del código destino se puede determinar en tiempo de compilación.
• Un área de datos Estática determinada en forma estática, para contener constantes globales y demás datos que genera el compilador. El tamaño de las constantes globales y de los datos del compilador también puede determinarse en tiempo de compilación.
• Un área Montículo administrada en forma dinámica, para contener objetos de datos que se asignan y se liberan durante la ejecución del programa. El tamaño del Montículo no puede determinarse en tiempo de compilación.
• Un área Pila administrada en forma dinámica, para contener los registros de activación a medida que se crean y se destruyen, durante las llamadas a los procedimientos y sus retornos. Al igual que el Montículo, el tamaño de la Pila no puede determinarse en tiempo de compilación.

Bloques básicos y grafos de flujo

La generación de código se beneficia del contexto.

La representación se construye de la siguiente forma:

• Se proporciona el código intermedio en bloques básicos, los cuales son secuencias máximas de instrucciones consecutivas de tres direcciones, con las siguientes propiedades:

(a) El flujo de control sólo puede entrar en el bloque básico a través de la primera instrucción en el bloque. Es decir, no hay saltos hacia la parte media del bloque.

(b) El control saldrá del bloque sin detenerse o bifurcarse, excepto tal vez en la última instrucción en el bloque.

...