TIPOS DE OPTIMIZACION

  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.