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
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.
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.
