Tipos de Optimización
Optimizaciones Globales
Optimizaciones de Ciclo
Optimización de Mirilla
Optimizaciones Locales
- La optimización es un proceso que tiene a minimizar o maximizar alguna variable de rendimiento, generalmente tiempo, espacio, procesador, etc.
- La optimización se realiza reestructurando el código de tal forma que el nuevo código generado tenga mayores beneficios.
Optimización Local
• Las optimizaciones locales se realizan sobre el bloque básico
• Optimizaciones locales
– Folding
– Propagación de constantes
– Reducción de potencia
– Reducción de subexpresiones comunes
Bloque Básico
• Un bloque básico es un fragmento de código que tiene una única entrada y salida, y cuyas instrucciones se ejecutan secuencialmente. Implicaciones:
– Si se ejecuta una instrucción del bloque se ejecutan todas en un orden conocido en tiempo de compilación.
• La idea del bloque básico es encontrar partes del programa cuyo análisis necesario para la optimización sea lo más simple posible.
Ensamblamiento (Folding)
• El ensamblamiento es remplazar las expresiones por su resultado cuando se pueden evaluar en tiempo de compilación (resultado constante).
– Ejemplo: A=2+3+A+C -> A=5+A+C
• Estas optimizaciones permiten que el programador utilice cálculos entre constantes representados explícitamente sin introducir ineficiencias.
Implementación del Folding
• Implementación del floding durante la generación de código realizada conjuntamente con el análisis sintáctico.
– Se añade el atributo de constante temporal a los símbolos no terminales y a las variables de la tabla de símbolos.
– Se añade el procesamiento de las constantes a las reglas de análisis de expresiones.
– Optimiza: 2+3+b -> 5+b
• Hay una suma de constantes (2+3)+b
– No optimiza: 2+b+3 -> 2+b+3
• No hay una suma de constantes (2+b)+3
Implementación del Folding
• Implementación posterior a la generación de código
– Buscar partes del árbol donde se puede aplicar la propiedad conmutativa:
• Sumas/restas: como la resta no es conmutativa se transforma en sumas: a+b-c+d -> a+b+(-c)+d
• Productos/divisiones: como la división no es conmutativa se transforma en productos: a*b/c*e -> a*b*(1/c)*e
– Buscar las constantes y operarlas
– Reconstruir el árbol.
Propagación de constantes
• Desde que se asigna a una variable un valor constante hasta la siguiente asignación, se considera a la variable equivalente a la constante.
• Ejemplo: Propagación Ensamblamiento
PI=3.14 -> PI=3.14 -> PI=3.14
G2R=PI/180 -> G2R=3.14/180 -> G2R=0.017
PI y G2R se consideran constantes hasta la próxima asignación.
• Estas optimizaciones permiten que el programador utilice variables como constantes sin introducir ineficiencias. Por ejemplo en C no hay constantes y será lo mismo utilizar
– Int a=10;
– #define a 10
Con la ventaja que la variable puede ser local.
• Actualmente en C se puede definir const int a=10;
implementación de la Propagación de Constantes
• Separar el árbol en bloques básicos
– Cada bloque básico será una lista de expresiones y asignaciones
• Para cada bloque básico
– 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.
Ejecuci on en tiempo de compilaci on
Precalcular expresiones constantes (con constantes o variables cuyo valor no cambia)
i = 2 + 3 ! i = 5
j = 4
f = j + 2.5
!
j = 4
f = 6.5
2. Reutilizaci on de expresiones comunes
a = b + c
d = a - d
e = b + c
f = a - d
!
a = b + c
d = a - d
e = a
f = a - d
3. Propagaci on de copias
Ante instrucciones f = a, sustituir todos los usos de f por a
a = 3 + i
f = a
b = f + c
d = a + m
m = f + d
!
a = 3 + i
b = a + c
d = a + m
m = a + d
Reducci on de potencia
Reemplazar una operaci on por otra equivalente menos costosa
x2 ! x * x
2*x ! x + x (suma); x<<1 (despl. izq.)
4*x, 8*x,... ! x<<2, x<<3,...
x / 2 ! x>>2
Bucles
• Los ciclos son una de las partes más esenciales en el rendimiento de un programa dado que realizan acciones repetitivas, y si dichas acciones están mal realizadas, el problema se hace N veces más grandes.
Ciclos
• El problema de la optimización en ciclos y en general radica es que muy difícil saber el uso exacto de algunas instrucciones. Así que no todo código de proceso puede ser optimizado.
• Otros uso de la optimización pueden ser el mejoramiento de consultas en SQL o en aplicaciones remotas (sockets, E/S, etc.)
Globales
• La optimización global se da con respecto a todo el código.
• Este tipo de optimización es más lenta pero mejora el desempeño general de todo programa.
• Las optimizaciones globales pueden depender de la arquitectura de la máquina.
Optimización global
• En algunos casos es mejor mantener variables globales para agilizar los procesos (el proceso de declarar variables y eliminarlas toma su tiempo) pero consume más memoria.
• Algunas optimizaciones incluyen utilizar como variables registros del CPU, utilizar instrucción es enensamblador.
De mirilla
• La optimización de mirilla trata de estructurar de manera eficiente el flujo del programa, sobre todo en instrucciones de bifurcación como son las decisiones, ciclos y saltos de rutinas.
• La idea es tener los saltos lo más cerca de as llamadas, siendo el salto lo más pequeño posible.
