Optimizacion de codigo 1

Optimización de Código

Compiladores II

1

Generación de Código y Optimización
• Generación de código
– Se realiza mientras se analiza el programa
– “Libre del contexto”

• Optimización
– Se realiza después de la generación de código de todo el
programa o de un elemento ejecutable del programa
(función, procedimiento, etc).
– “Dependiente del contexto”

Compiladores II

2

Generación deCódigo y Optimización

Programa fuente

Se ejecuta todo
junto. Mientras
se analiza se
genera código

Analizador
lexicográfico,
sintáctico y
semántico
Generador de
Código

Optimizador
Programa objeto

Compiladores II

3

Optimización
• Objetivo
– Obtener código que se ejecuta más eficientemente según los
criterios
• Tiempo de ejecución (optimización temporal)
• Espacio de memoria utilizado(optimización espacial)

• Funcionamiento
– Revisa el código generado a varios niveles de abstracción y
realiza las optimizaciones aplicables al nivel de abstracción
• Representaciones de código intermedio de más a menos
abstractas
– Árbol sintáctico abstracto: optimizar subexpresiones
redundantes, reducción de frecuencia, etc.
– Tuplas o cuadruplas: optimizar en uso de los registros o de las
variablestemporales.
– Ensamblador/Código máquina: convertir saltos a saltos cortos,
reordenar instrucciones
Compiladores II

4

Optimización
• Funcionamiento (continuación)
– 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 quebuscar 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
B=2*A+(A=c*d);

Pasar a
A=c*d;
B=A*3;
Compiladores II

5

Optimización Local
• Las optimizaciones locales se realizan sobre el bloque
básico
• Optimizacioneslocales
–
–
–
–

Compiladores II

Folding
Propagación de constantes
Reducción de potencia
Reducción de subexpresiones comunes

6

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

Compiladores II

7

Bloque Básico (ejemplos)

• Ejemplos (separación errónea):
for (i=1;i<10;++i) {
b=b+a[i];
c=b*i;
}
a=3;
b=4;
goto l1;
c=10;
l1: d=3;
e=4;

Compiladores II

8

Bloque Básico (ejemplos)

• Separación correcta
for (i=1;i<10;++i) {
b=b+a[i];c=b*i;
}
a=3;
b=4;
goto l1;
c=10;
l1: d=3;
e=4;

BB1:
i=1;
BB2:
i<10;
BB3:
b=b+a[i];
c=b*i;
++i
BB4:
a=3;
b=4;
goto l1;
BB5:
c=10;
BB6:
l1: d=3;
e=4;

Compiladores II

9

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 permitenque el programador utilice
cálculos entre constantes representados explícitamente sin
introducir ineficiencias.

Compiladores II

10

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.
– Seañ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

Compiladores II

11

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