GENERACION DE CODIGO INTERMEDIO

TAREA_7_FERNANDEZ

 

El proceso de la compilación se desglosa en dos partes: la primera corresponde  con la parte de análisis (léxico, sintáctico y semántico). La segunda corresponde con la parte de síntesis (generación de código). Este último es la tarea más complicada de un compilador.

Una representación intermedia es una estructura de datos que representa al programa fuente durante el proceso de la traducción a código objeto. El árbol de análisis sintáctico como representación intermedia, junto con la tabla de símbolos que contenía información sobre los nombres (variables, constantes, tipos y funciones) que aparecían en el programa fuente.

Es necesario generar una nueva forma de representación intermedia. A esta representación intermedia, que se parece al código objeto pero que sigue siendo independiente de la máquina, se le llama código intermedio. Este puede tomar muchas formas. Todas ellas se consideran como una forma de linearizacion del árbol sintáctico, es decir, una representación del árbol sintáctico de forma secuencial. El código intermedio más habitual es el código de 3-direcciones este es una secuencia de proposiciones de la forma general  X= Y op Z:

DONDE:

 OP representa cualquier operador; X, Y, Z, operador aritmético de punto fijo o flotante, o un operador lógico sobre datos booleanos. Representan variables definidas por el programador o variables temporales generadas por el compilador. Y, Z también puede representar constantes o literales. 

Se llama código de 3-direcciones porque cada proposición contiene, en el caso general, tres direcciones, dos para los operandos y una para el resultado. (Aunque aparece el nombre de la variable, realmente corresponde al puntero a la entrada de la tabla de símbolos de dicho nombre).

El conjunto de proposiciones (operadores) debe ser lo suficientemente rico como para poder implantar las operaciones del lenguaje fuente. Las proposiciones de 3-direcciones van a ser en cierta manera análogas al código ensamblador.

IMPEMENTACION DE CODIGO DE TRES DIRECCIONES

Una proposición de código de 3-direcciones se puede implantar como una estructura tipo registro con campos para el operador, los operandos y el resultado. La representación final será entonces una lista enlazada o un vector de proposiciones.

IMPLEMENTACION MEDIANTE CUADRUPLOS

Un cuádruplo es una estructura tipo registro con cuatro campos(op, result, arg1, arg2). El campo op contiene un código interno para el operador.

Una alternativa a almacenar nombres en el cuádruplo es almacenar punteros a la tabla de símbolos, con lo que se evita tener que hacer operaciones de búsqueda en un procesado posterior.

IMPLEMENTACION MEDIANTE TRIPLETES

Para evitar tener que introducir nombres temporales en la tabla de símbolos, se hace referencia a un valor temporal según la posición de la proposición que lo calcula. Las propias instrucciones representan el valor del nombre temporal. La implantación se hace mediante registros de solo tres campos (op, arg1, arg2).

En la notación de tripletes se necesita menor espacio y el compilador no necesita generar los nombres temporales. Sin embargo, en esta notación, trasladar una proposición que defina un valor temporal exige que se modifique todas las referencias a esa proposición. Lo cual supone un inconveniente a la hora de optimizar el código, pues a menudo es necesario cambiar proposiciones de lugar.

CODIGO INTERMEDIO COMO UN ATRIBUTO SINTETIZADO

El código intermedio es visto como una cadena de caracteres y se puede diseñar un esquema de traducción dirigido por la sintaxis (ETDS) que genere dicho código al recorrer el árbol de análisis sintáctico en orden posfijo.

REUTILIZACION DE LOS NOMBRES TEMPORALES

Los nombres temporales utilizados para guardar valores intermedios de los cálculos de expresiones tienen que ser introducidos en la TS para guardar sus valores con el consiguiente aumento de espacio. Los nombres temporales se pueden reutilizar mediante un sencillo método que consiste en llevar una cuenta c, iniciada cero, de variables temporales. Cuando se utilice un nombre temporal como operando hay que decrementar el valor de c en 1.  

TRADUCCION DE EXPRESIONES BOOLEANAS

Las expresiones booleanas se utilizan principalmente como parte de las proposiciones condicionales que alteran el flujo de control del programa, if-then, if-then-else, while-do. Las expresiones booleanas se componen de los operadores booleanos and, or, not aplicados a variables booleanas o expresiones relacionales.

Uno de los métodos para traducir expresiones booleanas a código de 3-direcciones consiste en codificar numéricamente los valores true y false y evaluar una expresión booleana como una expresión aritmética, siguiendo unas prioridades. A menudo se utilizan 1 para indicar true y 0 para indicar false. Las expresiones booleanas se evalúan de manera similar a una expresión aritmética de izquierda a derecha.

TRADUCCION DE FUNCIONES

La generación de código para las funciones es la parte más complicada porque depende de la maquina objeto y de la organización del entorno de ejecución. La traducción de funciones implica dos etapas:

•  La definición de la función: esta crea un nombre, parámetros y código del cuerpo de la función pero no se ejecuta la función en ese punto.

• La llamada a la función: esta llamada crea los valores actuales para los parámetros y realiza un salto al código de entrada de la función que se ejecuta y retorna al punto de la llamada.

OPTIMIZACION DE CODIGO INTERMEDIO

La optimización de código intermedio se puede realizar:

•   A nivel local: solo utilizan la información de un bloque básico para realizar la optimización.
•   A nivel global: que usan información de varios bloques básicos.

El término de MEJORA de código sería más apropiado que el de OPTIMIZACIÓN.

La mayoría de los programas emplean el 90% del tiempo de ejecución en el 10% de su código. Lo más adecuado es identificar las partes del programa que se ejecuten más frecuentemente y tratar de que se ejecuten lo más eficientemente posible. Además de la optimización a nivel de código intermedio, se puede reducir el tiempo de ejecución de un programa actuando a otros niveles: a nivel de código fuente y a nivel de código objeto.

Un bloque básico es una unidad fundamental de código, es una secuencia de proposiciones donde el flujo de control entre en el principio del bloque y sale al final del bloque. Un flujo de control puede visualizarse como un grafo dirigido de bloques básicos.

ELIMINACION DE SUBEXPRESIONES COMUNES

Si una expresión se calcula más de una vez, se puede remplazar el cálculo de la segunda por el valor de la primera expresión. Esto solo es posible si los operandos que están implicados en el cálculo de la expresión no han modificado su valor en las proposiciones intermedias.

PROPAGACION DE COPIAS

La propagación de copias considera las proposiciones de la forma α = b. Después de esta sentencia sabemos que α y b tienen el mismo valor, por tanto, podemos remplazar cada vez que aparezca α por b, con la esperanza de que se pueda remplazar todas las ocurrencias de α hasta que se convierta en un nombre muerto y se pueda entonces eliminar la proposición de copia.

ELIMINACION DE CODIGO MUERTO

Podemos tener proposiciones que definen un nombre que nunca más es referenciado, está muerto. Estas proposiciones pueden entonces ser eliminadas. Dada la proposición α = b op c, se dice que es código muerto o inactivo si α no es referenciada. En general, el código muerto aparece como consecuencia de la propagación de copias y es esto lo que hace que la técnica de propagación de copias sea tan útil.

TRANSFORMACIONES ARITMETICAS

Se pueden hacer uso de transformaciones algebraicas simples para reducir la cantidad de computación transformando operaciones mas costosas por otras menos costosas. Existen tres tipos:

·         Calculo previo de constantes

Se trata de calcular a nivel de compilación el valor previo de constantes en vez de hacerlo en tiempo de ejecución que retardaría la ejecución de un programa.

·         Transformaciones algebraicas

Se puede hacer uso de identidades algebraicas para simplificar el código.

·         Reducción de intensidad

Siempre que sea posible es conveniente sustituir un operador más costoso (multiplicación y división) por otro menos costoso (suma y resta).

EMPAQUETAMIENTO DE TEMPORALES

Se trata de reusar los temporales con el fin de ahorrar espacio. Después de haber optimizado el código es normal pensar que se puedan usar menos temporales.

MEJORA DE LOS LAZOS

• ·         Traslado de código

Una modificación importante que disminuye la cantidad de código en un lazo es el traslado de código. Esta transformación toma una expresión que produce el mismo resultado independientemente del número de veces que se ejecute un lazo y la coloca antes del lazo.

• ·         Variables de inducción

Se trata de identificar las variables que permanecen ligadas entre sí en la ejecución, están relacionadas entre sí de forma que conocido el valor de una se puede obtener el de la otra.