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.

• Los bloques básicos se convierten en los nodos de un grafo de flujo, cuyas flechas indican qué bloques pueden ir después de otros.

Los nodos del grafo de flujo son los nodos básicos. Hay una flecha del bloque B al bloque C sí, y sólo si es posible que la primera instrucción en el bloque C vaya justo después de la última instrucción en el bloque B. Hay dos formas en las que podría justificarse dicha flecha:

• Hay un salto condicional o incondicional desde el final de B hasta el inicio de C.

• C sigue justo después de B en el orden original de las instrucciones de tres direcciones, y B no termina en un salto incondicional.

Decimos que B es un predecesor de C, y que C es un sucesor de B.

Optimización de los bloques básicos

Podemos obtener mía considerable mejora sobre el tiempo de ejecución del código, con sólo realizar mía optimización local dentro de cada bloque básico por sí mismo.

La representación en GDA de un bloque básico nos permite realizar varias transformaciones para mejora de código, en el código representado por el bloque.

1. Podemos eliminar las subexpresiones locales comunes; es decir, las instrucciones que calculan un valor que ya se ha calculado.
2.  Podemos eliminar el código muerto; es decir, las instrucciones que calculan un valor que nunca se utiliza.
3.  Podemos reordenar las instrucciones que no dependen unas de otras; dicho reordenamiento puede reducir el tiempo que requiere un valor temporal para preservarse en un registro.
4.  Podemos aplicar leyes algebraicas para reordenar los operandos de las instrucciones de tres direcciones, lo cual algunas veces simplifica los cálculos.

Un generador de código simple

Una de las cuestiones principales durante la generación de código es decidir cómo usar los registros para sacarles el máximo provecho. Hay cuatro usos principales de los registros:

• En la mayoría de las arquitecturas de máquinas, algunos o todos los operandos de una operación deben estar en registros, para poder llevarla a cabo.
• Los registros son excelentes variables temporales: lugares para guardar el resultado de una subexpresión mientras se evalúa una expresión más grande o, dicho en forma más general, un lugar para guardar una variable que se utiliza sólo dentro de un bloque básico individual.
• Los registros se utilizan para guardar valores (globales) que se calculan en un bloque básico y se utilizan en otros bloques; por ejemplo, un índice de ciclo que se incrementa al pasar por el ciclo y se utiliza varias veces dentro del mismo.
• A menudo, los registros se utilizan para ayudar con la administración del almacenamiento en tiempo de ejecución, por ejemplo, para administrar la pila en tiempo de ejecución, incluyendo el mantenimiento de los apuntadores de la pila y posiblemente los elementos superiores de ésta.

El algoritmo de generación de código

 Una parte esencial del algoritmo es una función llamada obtenReg(I), la cual selecciona los registros para cada ubicación de memoria asociada con la instrucción de tres direcciones. La función obtenReg tiene acceso a los descriptores de registro y de acceso para todas las variables del bloque básico, y también puede tener acceso a cierta información útil del flujo de datos, como las variables que están vivas al salir del bloque.

...