Representaciones de código para extraer información
Grafos.
Condiciones que se han de cumplir
El código optimizado se ha de comportar igual que el código de partida excepto por ser más rápido o ocupar menos espacio.
Hay que buscar transformaciones que no modifiquen el comportamiento del código según el comportamiento definido para el lenguaje de programación. Ejemplo
Si no se ha definido el orden de evaluación de los operandos la siguiente optimización es válida
Inicializar el conjunto de definiciones a conjunto vacío.
Definición: (variable,constante)
Procesar secuencialmente la lista de expresiones y asignaciones
Para expresión y asignación
Sustituir las apariciones de las variables que se encuentran en el conjunto de definiciones por sus constantes asociadas.
Para asignaciones
Eliminar del conjunto de definiciones la definición de la variable asignada
Añadir la definición de la variable asignada si se le asigna una constante
Ejemplo de Separación en Bloques Básicos
Fun
+- []
+- =>
+- f
| +- x
| +- y
+- InstrComp
+- ;
+- =
| +- i
| +- 0
+- ;
+- =
| +- b
| +- 5
+- ;
+- while
| +- <
| | +- i
| | +- x
| +- InstrComp
| +- ;
| +- Print
| | +- *
| | +- i
| | +- b
| +- =
| +- i
| +- +
| +- i
| +- 1
+- *
+- x
+- b
Fun f(x,y)=>
{
i=0;
b=5;
while (i
print(i*b);
i=i+1;
}
x*b
}
print(i*b);
i=i+1;
i
i=0;
b=5;
Eliminación de subexpresiones redundantes.
Las subexpresiones que aparecen más de una vez se calculan una sola vez y se reutiliza el resultado.
Idea: Detectar las subexpresiones iguales y que las compartan diversas ramas del árbol. Problema: Hay que trabajar con un grafo acíclico.
Dos expresiones pueden ser equivalentes y no escribirse de la misma forma A+B es equivalente a B+A. Para comparar dos expresiones se utiliza la forma normal
Se ordenan los operandos: Primero las constantes, después variables ordenadas alfabéticamente, las variables indexadas y las subexpresiones. Ejemplo
X=C+3+A+5 -> X= 3+5+A+C
Y=2+A+4+C -> Y=2+4+A+C
divisiones y restas se ponen como sumas y productos para poder conmutar
A-B -> A+ (-B)
A/B -> A * (1/B)
Implementación
Primero se aplica el ensamblamiento y la propagación de constantes.
Después se reordena el árbol sintáctico hasta obtener la forma normal.
Se inicia la eliminación de las subexpresiones redundantes.
Hay que considerar las asignaciones que pueden convertir una subexpresion redundante en no redundante. Ejemplo:
Q=A+B
A=Q^2+2
C[1]=A+B+P
Ejemplo de eliminación de subexpresiones
J=2*D+3
D=D*2
J=J+D
A+B no es redundante por la asignación
Optimizaciones Dentro de Bucles
La optimización de bucles es muy importante por las mejoras en tiempo de ejecución que se obtienen
Estrategias de optimización dentro de bucles
Expansión de bucles (loop unrolling)
Reducción de frecuencia (frequency reduction)
Reducción de potencia (strength reduction)
Expansión de bucles(loop unrolling)
La expansión de bucles solo se puede aplicar a los bucles cuyo número de iteraciones se conoce en tiempo de compilación. Ejemplo:
Se puede aplicar a los bucles
for i=1 to 10 do …
No se puede aplicar a los bucles
for i=a to b do …
La expansión de un bucle puede ser muy costosa en espacio. Hay que poner un criterio heurístico para decidir si se aplica la expansión.
Se puede aplicar una expansión parcial en la que sigue existiendo el bucle, pero cada iteración del nuevo bucle corresponde a varias iteraciones del bucle original.
Una variable V es inductiva cuando la única forma en que se modifica su código es V=V+K, donde K es una invariante de bucle.
Se considerará la necesidad de generar una variable inductiva temporal T a partir de encontrar expresiones de la forma V*C, donde C es una invariante de bucle.
Se sustituirá V*C por T
Se inicializa T después de la inicialización de V como T=V*C (solo se ejecuta al entrar en el bucle)
Al final de cada iteración se añade T=T+C*K
Optimización Global
Grafo del flujo de ejecución
Antes de realizar una optimización global es necesario crear el grafo de flujo de ejecución.
El grafo de flujo de ejecución representa todos los caminos posibles de ejecución del programa.
La información contenida en el grafo es útil para
el programador y
el optimizador
La optimización global a partir del análisis del grafo del flujo de ejecución permite
Una propagación de constantes fuera del bloque básico.
Eliminación del código no utilizado
Una mejor asignación de los registros.
Problema: la optimización global es muy costosa en tiempo de compilación
Se representa el programa en un código intermedio donde queden explícitamente representados los saltos condicionales e incondicionales.
Un bloque básico será cualquier trozo de código que no contenga saltos ni etiquetas en su interior (es posible tener etiquetas al inicio del bloque y saltos al final).
En el grafo, los vértices representan los bloques básicos y las aristas representan los saltos de un bloque básico a otro.
Detección de código no utilizado
El código no utilizado son los bloques básicos donde no llega ninguna arista.
Análisis del Grafo del Flujo de Ejecución
Hay que considerar como la información sobre las variables y expresiones se propaga a través del grafo.
Problemas resueltos durante el análisis del grafo
expresiones disponibles (al seguir la ejecución sigue siendo válido el resultado obtenido)
Alcance de las definiciones
variables vivas
expresiones muy utilizadas
Para la resolución de los problemas anteriores se utiliza la idea de punto entre instrucciones o bloques básicos.
r=1
i=1
while (i<=n)
Puntos
Expresiones Disponibles (Available expresions)
El problema de las expresiones disponibles consiste en determinar que expresiones están disponibles al inicio de cada bloque
Algoritmo
Para cada bloque básico se definen 4 conjuntos
AE_TOP(BB): la expresión está disponible en el punto que precede a BB
AE_KILL(BB): la expresión ya no será válida después de la ejecución de BB por que se ha modificado algún operando.
AE_GEN(BB): Se ha evaluado la expresión en BB sin que se modifiquen sus operándos.
AE_BOT(BB): La expresión está disponible justo después de la ejecución de BB
Alcance de las Definiciones (reaching definitions)
El valor de una variable se define cuando se le asigna un valor.
Este valor definido se pierde cuando se realiza una nueva asignación.
El problema del alcance de las definiciones es el mismo que el problema de las expresiones disponibles, pero en el caso de las variables.
Ecuaciones:
RD_BOT(BB)=(RD_TOP(BB)-RD_KILL(BB))
RD_GEN(BB)
RD_TOP(BB)= p precedente de BB RD_BOT(P)
Variables Vivas (live variables)
Una variable esta viva en un punto p cuando su valor es requerido para un camino de ejecución que pasa por p.
Un camino requiere el valor de una variable cuando hay una asignación de la variable al principio y una lectura al final.
Uso delimitar exactamente en que partes del código es necesaria una variable.
Ecuaciones
LV_TOP(BB)=(LV_BOT(BB)-LV_DEF(BB))
LV_USE(BB)
LV_BOT(BB)= s sucesor de BB LV_TOP(S)
Expresiones muy Utilizadas (Very Busy Expression)
Una expresión es muy utiliza en un punto p cuando el valor de la expresión se requiere antes que el valor de cualquiera de sus términos a lo largo de cualquier camino que empieza en p.
Ejemplo de Optimización Global Eliminación de Variables Innecesarias
A(1)<0
J>0
L:=2
L:=1
J:=2
K:=1
A(K+1):=A(K)+A(K+1);
I:=J;
L:=K*I
K:=K+2
K
{J,K}
{J,K}
{J,K}
{A(1),J}
{J}
Se puede eliminar L e I
Las A(K),A(K+1) no se eliminan pues no se han
podido considerar en el cálculo de variables vivas
Ejemplo de Optimización Global Propagación de Constantes
A(1)<0
J>0
J:=2
K:=1
A(K+1):=A(K)+A(K+1);
K:=K+2
K<2
{A(1),J}
{J:=2}
Eliminar J>0 por no
utilizarse y saltar
al mismo bloque básico
Eliminar A(1)<0 después
de eliminar J>0
Se puede expandir el bucle
Ejemplo de Optimización Global Expandir el Bucle
J:=2
K:=1
A(1+1):=A(1)+A(1+1);
A(2+1):=A(2)+A(2+1);
A(2):=A(1)+A(2);
A(3):=A(2)+A(3);
Eliminar J y k por que no se utilizan y
realizar los cálculos entre constantes
Optimización Dependiente de Máquina
La optimización dependiente de máquina pretende aprovechar las características específicas de la máquina para acelerar la ejecución del programa
Considerar los ciclos de reloj que gasta cada instrucción de código máquina.
Utilizar desplazamientos de bits para multiplicar y dividir.
Para poner un registro a cero utilizar la instrucción XOR reg,reg que accede menos a memoria
Utilizar saltos relativos de 8 o 16 bits para acceder menos a memoria.
Alinear instrucciones/Datos para que se acceda en un único ciclo de memoria.
Combinar operaciones en una misma instrucción.
Utilizar el direccionamiento con pre- y post-incremento.
Optimizaciones Dependientes de Máquina
Sacar provecho de todas las formas de direccionamiento del procesador.
Utilizar acceso indexado para los arrays.
Reordenar las instrucciones para paralelizar su ejecución.
Un Pentium es capaz de ejecutar en paralelo un cálculo con enteros con otro de flotantes.
Evitar que la siguiente instrucción dependa del resultado de la anterior para que no se produzca un fallo en la pipe-line. Incluso puede ser interesante añadir NOPs para evitar los fallos de pipe-line.
Optimizar el uso de los registros del procesador.
Es especialmente importante en los procesadores RISC.
Es cuando se selecciona el registro para guardar una variable
Como optimizar la asignación de registros
Minimizar el número de variables temporales necesarias para evaluar una expresión
Asignar las variables temporales a registros
Si hay suficientes registros ya se ha acabado
Si no hay que decidir que variables se han de transferir a memoria y como minimizar el número de transferencias
Minimizar el Número de Variables Temporales
Idea:
Minimizar el número de registros necesarios para los operandos de una operación y luego considerar en que orden se han de calcular los operandos para minimizar el número de registros del cálculo completo
Operación
binaria
Operando 1
n registros
Operando 2
m registros
Max{n,m+1} registros
R=Calcular Op1
Calcular Op2
Operación R,Op2
Max{n+1,m} registros
R=Calcular Op2
Calcular Op1
Operación Op1,R
Carga/Descarga de Registros
Minimizar el número de operaciones de carga y descarga
¿Que registro se ha de descargar a memoria?
No guardar en memoria los operandos izquierdos de operaciones no conmutativas (ej. / -) siempre que haya otra posibilidad. Sólo tiene sentido si el procesador no permite divisiones o restas con los operandos invertidos ( -A+B, A\B).
Guardar en memoria el valor que más se tardará en utilizar en el programa
No saltar en caso de un salto condicional hacia delante
Saltar en caso de salto condicional hacia atrás
Reducir el Número de Saltos
Reduce la posibilidad de predicciones erróneas
Reduce el número de entradas en la BTB (Branch Target Buffer)
Ejemplo: ebx = (A
cmp A, B ; condition
jge L30 ; conditional branch
mov ebx, CONST1
jmp L31 ; unconditional branch
L30:
mov ebx, CONST2
L31:
Pentium
xor ebx, ebx ;clear ebx
cmp A, B
setge bl ;When ebx = 0 or 1
;OR the complement condition dec ebx ;ebx=00...00 or 11...11
and ebx, (CONST2-CONST1) ;ebx=0
or (CONST2-CONST1)
add ebx, min(CONST1,CONST2)
Pentium II
move ebx,CONST1
cmp A, B
cmovege ebx, CONST2
Evitar paradas por uso parcial de registros (Avoid partial register stalls).
Register Stall al acceder a EAX
MOV AX, 8
ADD ECX, EAX
En el caso de Pentium II se puede producir para instrucciones no contiguas
MOV AL, 8
MOV EDX, 0x40
MOV EDI, new_value
ADD EDX, EAX ;Partial stall
Alinear
Alinear datos
Align 8-bit data on any boundary.
Align 16-bit data to be contained within an aligned 4-byte word.
Align 32-bit data on any boundary which is a multiple of four.
Align 64-bit data on any boundary which is a multiple of eight.
Align 80-bit data on a 128-bit boundary (that is, any boundary which is a multiple of 16 bytes).
Alinear código
Loop entry labels should be 16-byte aligned when less than eight bytes away from a 16-byte boundary.
Labels that follow a conditional branch should not be aligned.
Labels that follow an unconditional branch or function call should be 16-byte aligned when less than eight bytes away from a 16-byte boundary.
Reordenar las instrucciones para maximizar la ejecución paralela
Pairing cannot be performed when the following conditions occur:
The next two instructions are not pairable instructions (see Appendix A for pairing characteristics of individual instructions). In general, most simple ALU instructions are pairable.
The next two instructions have some type of register contention (implicit or explicit). There are some special exceptions to this rule where register contention can occur with pairing. These are described later.
The instructions are not both in the instruction cache. An exception to this which permits pairing is if the first instruction is a one-byte instruction.