La optimización de código puede realizarse durante la propia generación o como paso adicional, ya sea intercalado entre el análisis semántico y la generación de código (se optimizan las cuádruplas) o situado después de ésta (se optimiza a posteriori el código generado).
Hay teoremas (Aho, 1970) que demuestran que la optimización perfecta es indecidible. Por tanto, las optimizaciones de código en realidad proporcionan mejoras, pero no aseguran el éxito total.
Clasificación de optimizaciones:
Optimización y depuración suelen ser incompatibles. Por ejemplo, si se elimina totalmente una instrucción, puede ser imposible poner una parada en ella para depuración. Ejemplo:
x = x;
ALgunas máquinas tienen instrucciones especiales que permiten acelerar ciertos procesos. Por ejemplo:
Ej: if (x&4 || x&8) ... se puede representar:
TEST X,12 JZ L ... L:
En muchas máquinas, la multiplicación en punto fijo de dos operandos de longitud 1 da un operando de longitud 2, mientras la división necesita un operando de longitud 2 y otro de longitud 1 para dar un cociente y un resto de longitud 1. Reordenar las operaciones puede optimizar. Por ejemplo: sea la expresión a=b/c*d;
MOV AX,B XOR DX,DX DIV AX,C MUL AX,D MOV A,AX
Si la reordenamos así: a=b*d/c;, aprovechando que la multiplicación y la división son asociativas, tenemos:
MOV AX,B MUL AX,D DIV AX,C MOV A,AX
Ahorramos una instrucción. Veamos otro ejemplo:
a=b/c; d=b%c;
Los dos códigos siguientes son equivalentes. Puede tratarse como un caso particular del manejo de registros. La realización de la primera división debería guardar constancia de que DX contiene el resultado del resto.
MOV AX,B MOV AX,B XOR DX,DX XOR DX,DX DIV AX,C DIV AX,C MOV A,AX MOV A,AX MOV AX,B MOV D,DX XOR DX,DX DIV AX,C MOV D,DX
Ejemplo:
int i;
float f;
i = 2+3; (+,2,3,t1) (=,5,,i)
(=,t1,,i)
i = 4; (=,4,,i) (=,4,,i)
f = i+2.5; (CIF,i,,t2) (=,6.5,,f)
(+,t2,2.5,t3)
(=,t3,,f)
La ejecución se aplica principalmente a las operaciones aritméticas (+-*/) y a las conversiones de tipo.
La tabla de símbolos puede contener el valor conocido del identificador (ej., i=4), o bien podemos tener una subtabla T con pares (id, valor).
Algoritmo para tratar la ejecución en tiempo de compilación:
Ejemplo:
if (false) f = 1/0;Esta instrucción debe dar un aviso, pero no un error. De hecho, una optimización adicional de código la eliminaría totalmente.
En el ejemplo:
(+,2,3,t1) Elim, T = {(t1,5)}
(=,t1,,i) Sust por (=,5,,i), T = {(t1,5),(i,5)}
(=,4,,i) T = {(t1,5),(i,4)}
(CIF,i,,t2) Sust por (CIF,4,,t2),
Elim, T = {(t1,5),(i,4),(t2,4.0)}
(+,t2,2.5,t3) Sust por (+,4.0,2.5,t3)
Elim, T = {(t1,5),(i,4),(t2,4.0),(t3,6.5)}
(=,t3,,f) Sust por (=,6.5,,f)
Y quedan las cuádruplas optimizadas: (=,5,,i), (=,4,,i), (=,6.5,,f).
En cuanto sea posible que los valores de las variables cambien, el compilador debe "olvidar" el valor de las variables (inicializar la tabla T, total o parcialmente). Esto puede ocurrir si aparece:
Este proceso no exige la generación de las cuádruplas, puede realizarse directamente durante las rutinas semánticas asociadas al análisis sintáctico, especialmente si es Bottom-up.
Problema con la ejecución en tiempo de compilación: si tenemos un "cross-compiler", la precisión puede ser menor en el ordenador que compila que en el que ejecuta.
Ejemplo:
int a,b,c,d;
a = a+b*c; (*,b,c,t1) (*,b,c,t1)
(+,a,t1,t2) (+,a,t1,t2)
(=,t2,,a) (=,t2,,a)
d = a+b*c; (*,b,c,t3)
(+,a,t3,t4) (+,a,t1,t4)
(=,t4,,d) (=,t4,,d)
b = a+b*c; (*,b,c,t5)
(+,a,t5,t6)
(=,t6,,b) (=,t4,,b)
Una solución: el programador podría reescribir su programa así:
int a,b,c,d,e;
e = b*c; (*,b,c,t1)
(=,t1,,e)
a = a+e; (+,a,e,t2)
(=,t2,,a)
d = a+e; (+,a,e,t3)
(=,t3,,d)
b = d; (=,d,,b)
Desventaja: esta forma de programar puede ser más larga y menos legible. Además, hay redundancias que el programador no puede eliminar. Por ejemplo:
array X[0:4, 0:9];
X[i,j]:=X[i,j]+1; (*,i,10,t1) (*,i,10,t1)
(+,t1,j,t2) (+,t1,j,t2)
(+,X[t2],1,t3) (+,X[t2],1,t3)
(*,i,10,t4) (:=,t3,,X[t2])
(+,t4,j,t5)
(:=,t3,,X[t5])
Algoritmo para eliminar redundancias:
Prueba: si j<k<i, y la cuádrupla k cambiara alguno de los operandos de la cuádrupla i, entonces dep(i)>k. Pero dep(j)<=k, luego dep(i)>dep(j) y no se podría eliminar (i).
Ejercicio: aplicar el algoritmo a los dos ejemplos anteriores.
El uso de tripletes simplifica el proceso, y aún más si son indirectos.
Tener en cuenta la conmutatividad de algunas operaciones puede mejorar el proceso, pues las cuádruplas (*,a,b,-) y (*,b,a,-) serían equivalentes. Para facilitar el reconocimiento, se puede adoptar un orden canónico para los operandos de las operaciones conmutativas. Por ejemplo: términos que no son variables ni constantes, luego variables indexadas por orden alfabético, luego variables sin indexar por orden alfabético, finalmente constantes. Esto mejora también la ejecución en tiempo de compilación. Por ejemplo, si tenemos las instrucciones
a=1+c+d+3; a=c+d+1+3; b=d+c+2; b=c+d+2; la reordenación nos permite efectuar en tiempo de compilación la operación 1+3, y reconocer c+d como parte común de las dos instrucciones. Esto no es completo, sin embargo, ya que a=1+c+d+3; a=c+d+1+3; b=d+c+c+d; b=c+c+d+d; la reordenación no nos permite reconocer que c+d, evaluado en la primera instrucción, puede aplicarse a la segunda.
Otra mejora podría ser la utilización de los operadores monádicos para aumentar el número de cuádruplas equivalentes. Por ejemplo:
a = c-d; (-,c,d,t1) (-,c,d,t1)
(=,t1,,a) (=,t1,,a)
b = d-c; (-,d,c,t2) (-,t1,,t2)
(=,t2,,b) (=,t2,,b)
que no disminuye el número de cuádruplas, pero sustituye una operación
diádica por una monádica, que usualmente son más eficientes.
Las variables intermedias para resultados parciales pueden reutilizarse para minimizar la memoria (aunque eso puede ir en contra de las optimizaciones anteriores). Por ejemplo: sea la expresión (a*b)+(c+d). Sus cuádruplas equivalentes serían:
(*,a,b,t1) (+,c,d,t2) (+,t1,t2,t1)
En este caso, utilizamos dos variables auxiliares (t1, t2). Pero si aprovechamos la asociatividad de la suma para reordenar de esta manera:
(*,a,b,t1) (+,t1,c,t1) (+,t1,d,t1)necesitaremos sólo una variable auxiliar.
El número mínimo de variables auxiliares se puede calcular construyendo un grafo de la expresión y aplicando las siguientes reglas:
Por ejemplo, el grafo de (a*b)+(c+d) es:
+(2)
-----------------
*(1) +(1)
--------- ---------
a(0) b(0) c(0) d(0)
Pero el grafo de ((a*b)+c)+d es:
+(1)
----------------
+(1) d(0)
-----------------
*(1) c(0)
---------
a(0) b(0)
También se puede aprovechar la conmutatividad, como en el ejemplo:
(a+b)+(c*d) a+(c*d)+b
+(2) +(1)
----------------- -----------------
+(1) *(1) +(1) b(0)
--------- --------- ---------
a(0) b(0) c(0) d(0) a(0) *(1)
---------
c(0) d(0)
Una operación es invariante respecto a un bucle, si ninguno de los operandos de los que depende cambia de valor durante la ejecución del bucle. La optimización consiste en sacar la operación fuera del bucle.
Otra optimización es la reducción de la fuerza de una operación (sustituir una operación fuerte por otra más débil, como la multiplicación por la suma o la diferencia por el cambio de signo, como en el apartado anterior). Por ejemplo:
for (i=a; i<c; i+=b) {... d=i*k; ...}
donde b,k son invariantes respecto al bucle. (b podría ser una expresión,
en cuyo caso todos sus operandos deben ser invariantes). Además, i no se
modifica dentro del bucle, excepto en la instrucción de cierre, i+=b, y d no
se usa ni modifica antes de la instrucción indicada y no se modifica después.
En este caso, podemos sustituir el código generado por su equivalente:
d=a*k;
t1=b*k;
for (i=a; i<c; i+=b, d+=t1) {...}
con lo que hemos reducido la fuerza de una multiplicación a una suma
(dentro del bucle).
Esto no se debe hacer si i o k son reales, pues podría perderse precisión al sumar i veces en vez de multiplicar una. Pero sí se puede hacer si i,k son enteros.
Otro ejemplo:
for (i=0; i<10; i++) {... a=(b+c*i)*d; ...}
INIT: (=,0,,i)
LOOP: ...
(*,c,i,t1)
(+,b,t1,t2)
(*,t2,d,t3)
(=,t3,,a)
...
INCR: (+,i,1,i)
donde b,c,d son invariantes respecto al bucle, e i es la variable del
bucle. Supongamos que se cumplen todas las condiciones. Podemos aplicar
reducción de fuerza a la primera cuádrupla del bucle así:
INIT: (=,0,,i)
(*,c,0,t1)
(*,c,1,t4)
LOOP: ...
(+,b,t1,t2)
(*,t2,d,t3)
(=,t3,,a)
...
INCR: (+,i,1,i)
(+,t1,t4,t1)
Ahora t1 desempeña el mismo papel que i. Se le asigna un valor inicial y en cada paso del bucle se le incrementa en t4. Por tanto, podemos aplicar reducción de fuerza a la cuádrupla siguiente:
INIT: (=,0,,i)
(*,c,0,t1)
(*,c,1,t4)
(+,b,t1,t2)
LOOP: ...
(*,t2,d,t3)
(=,t3,,a)
...
INCR: (+,i,1,i)
(+,t1,t4,t1)
(+,t2,t4,t2)
Ahora pasa lo mismo con t2, luego podemos aplicar reducción de fuerza a la siguiente cuádrupla:
INIT: (=,0,,i)
(*,c,0,t1)
(*,c,1,t4)
(+,b,t1,t2)
(*,t2,d,t3)
(*,t4,d,t5)
LOOP: ...
(=,t3,,a)
...
INCR: (+,i,1,i)
(+,t1,t4,t1)
(+,t2,t4,t2)
(+,t3,t5,t3)
Todavía podemos optimizar más notando que ahora t1 y t2 no se emplean dentro del bucle, luego no es necesario incrementarlas:
INIT: (=,0,,i)
(*,c,0,t1)
(*,c,1,t4)
(+,b,t1,t2)
(*,t2,d,t3)
(*,t4,d,t5)
LOOP: ...
(=,t3,,a)
...
INCR: (+,i,1,i)
(+,t3,t5,t3)
Si sacamos operaciones fuera de un bucle, pueden quedar dentro de otro bucle más externo. El proceso podría repetirse.
Si hay alguna llamada de subrutina dentro del bucle, es difícil saber si se cambia alguna de las variables (podrían ser globales o pasarse como argumento por referencia). En tal caso, sólo pueden aplicarse las optimizaciones si el compilador sabe qué variables se cambian. Esto suele ocurrir sólo para ciertas funciones y subrutinas predefinidas.
Para realizar las optimizaciones pueden hacer falta dos pasos: uno primero, en el que se analizan los bucles y se obtiene información sobre las variables que cambian, y otro segundo, en el que se realiza la optimización propiamente dicha. Pero también se puede fusionar el proceso con el analizador semántico y el generador de código y hacerlo todo en un solo paso. Para esto, a veces hay que retrasar o cambiar de orden algunas de las operaciones del bucle. Por ejemplo, podríamos generar un código como el siguiente:
GOTO INIT
LOOP: ...
INCR: ...
GOTO TEST
INIT: ...
TEST: IF (no fin de bucle) GOTO LOOP
con lo que INIT y INCR (que son los que cambian con la optimización)
quedan al final.
Hay que tener cuidado con estas optimizaciones. Si el bucle se ejecuta normalmente 0 (o 1) veces, y es muy raro que se entre en él, las optimizaciones anteriores degradarán (o dejarán invariante) la eficiencia.
Supongamos que tenemos un programa dividido en bloques básicos. con ellos podemos formar un grafo donde los nodos son los bloques, los arcos indican sucesión de ejecución.
Llamamos "región fuertemente conexa" (o simplement región) a un subgrafo del programa en el que existe un camino de cualquier nodo del subgrafo a otro nodo del subgrafo. Ejemplo:
---------------------
| ------ -- |
v v | |v |
1 -> 2 -> 3 -> 5 -> 6 -> 7 -> 8
| ^
|--> 4 ---|
En la figura hay cinco regiones: (6), (3,5), (2,3,5,6,7), (2,3,4,6,7), (2,3,4,5,6,7).
Llamamos "bloque de entrada" de una región a un bloque al que entra un arco desde fuera de la región. (3,5) tiene un bloque de entrada: 3. (2,3,5,6,7) tiene dos bloques de entrada: 2 y 6.
Llamamos "predecesor" de una región a un bloque situado fuera de la región del que sale un arco que lleva a un bloque de entrada de la región. (3,5) tiene un predecesor: 2. (2,3,5,6,7) tiene dos predecesores: 1 y 4.
Construimos una lista R={R1,R2,...,Rn} de regiones tales que Ri!=Rj si i!=j, y i<j => Ri y Rj no tienen bloques en común o bien Ri es un subconjunto de Rj. En el ejemplo, una lista válida sería: (6),(3,5),(2,3,5,6,7),(2,3,4,5,6,7). Otra lista válida sería: (6),(2,3,4,6,7),(2,3,4,5,6,7). (2,3,4,6,7) y (2,3,5,6,7) no pueden estar juntas en una lista válida.
¿Cuál elegir? Conviene que estén los bucles, que tienen normalmente un solo nodo predecesor y un solo nodo de entrada. Cuando haya dos posibilidades, preferiremos las regiones con esta propiedad.
Para cada bloque definiremos las siguientes variables booleanas:
El O lógico de R[i] de todos los bloques de una región nos da R[i] para la región. Lo mismo con A[i].
La optimización se aplica sucesivamente a cada región de la lista, de la primera a la última. Al optimizar cada región, se crean bloques nuevos de inicialización. En el ejemplo:
---------------------------
| ------ -- |
v v | |v |
1 -> 2 -> 3 -> 5 -> I1 -> 6 -> 7 -> 8
| ^
|--> 4 -> I2 ---|
Los bloques I se añaden a las regiones correspondientes, para que entren en las nuevas optimizaciones. Todos los bloques de la región recién tratada se sustituyen por uno solo (R1, en este caso), calculando las variables booleanas aplicables a la región. Este bloque ya no debe ser optimizado. (R1), (3,5), (2,3,5,I1,R1,7), (2,3,4,5,I1,I2,R1,7).
Pasamos a la región R2 (3,5), optimizamos:
----------------------------------
| ------ -- |
v v | |v |
1 -> 2 -> I3 -> 3 -> 5 -> I1 -> R1 -> 7 -> 8
| ^
|--> 4 -> I2 ---|
y sustituimos:
------------------------------
| -- |
v |v |
1 -> 2 -> I3 -> R2 -> I1 -> R1 -> 7 -> 8
| ^
|-> 4 -> I2 -|
Las regiones serán: (R1), (R2), (2,I3,R2,I1,R1,7), (2,I3,R2,4,I1,I2,R1,7). Etcétera. En principio, sólo hacen falta los vectores booleanos correspondientes a las variables que se utilizan dentro de la región que se está optimizando. El algoritmo es como sigue:
Surgen si el resultado de la asignación no se utiliza posteriormente o si la asignación es recursiva (ej., i++) y sólo se usa en dichas definiciones recursivas. Todas esas asignaciones pueden eliminarse. Suelen surgir como consecuencia de la reducción de fuerza y optimizaciones semejantes (como se vio).
Para ver si una asignación está muerta se puede utilizar el algoritmo: