Código intermedio y estructuras de datos para generación de código



Descargar 43,47 Kb.
Fecha de conversión14.03.2017
Tamaño43,47 Kb.
5.1 Código intermedio y estructuras de datos para generación de código

El analizador sintáctico va generando acciones que valida el analizador semántico y que se convierten en tercetos. Esta conversión en tercetos constituye el generador de código intermedio.

Dado que el lenguaje puede presentar distintas funciones anidadas, los tercetos los generamos por orden del parser y son almacenados en un sitio u otro dependiendo del contexto en que nos encontremos. Es decir, se almacenan en una lista de tercetos dependiente de la Tabla de Símbolos. Hay tantas listas de tercetos como funciones haya en el código fuente más una lista de tercetos asociada a la Tabla de Símbolos Global.

No obstante una vez finalizado el análisis, todos estos tercetos repartidos en distintas listas se vuelcan a una sola lista de tercetos global. Esta será la que finalmente se optimice y a partir de la que se generará el programa en ensamblador.

El problema de tener que manejar tercetos indirectos fue resuelto modificando el método de inserción sobre la lista de tercetos utilizada en cada momento, de manera que se realiza previamente una búsqueda de algún terceto que sea exactamente igual al que estamos insertando. En caso afirmativo, insertamos en la lista no un terceto nuevo, sino un puntero al ya existente, y marcamos dicho terceto como terceto indirecto. Son tercetos indirectos aquellos marcados con un asterisco después del índice en los volcados de la lista de tercetos.
5.2 Técnicas básicas de generación de código
En programación, la generación de código es una de las fases mediante el cual un compilador convierte un programa sintácticamente correcto en una serie de instrucciones a ser interpretadas por una máquina. La entrada en esta fase viene representada, típicamente, por un Árbol Sintáctico, un Árbol de Sintaxis Abstracta, o una Representación Intermedia; la máquina destino puede ser un microprocesador o una máquina abstracta tal como una máquina virtual o un lenguaje intermedio, legible por un humano. Compiladores más sofisticados realizan múltiples traducciones en cadena (pipelining) con el fin de poder construir código para múltiples plataformas y evitar tener que construir todas las capas del compilador.
En términos más generales, la generación de código es usada para construir programas de una manera automática evitando que los programadores tengan que escribir el código a mano. La generación de código puede realizarse en tiempo de ejecución, Tiempo de carga, o Tiempo de compilación. Los compiladores JIT son un ejemplo de generadores de código.
5.3 Técnicas de optimación de código
Los factores a optimizar son: velocidad de ejecución, tamaño del programa, necesidades de memoria. Se sigue una aproximación conservadora, aunque no se aplican todas las posibles optimizaciones, solo las “seguras”

Clasificación de las optimizaciones:

1. En función de la dependencia de la arquitectura, dependientes de la máquina: Aprovechan características específicas de la máquina objetivo.

• Asignación de registros, uso de modos de direccionamiento.

• uso instrucciones especiales (IDIOMS).

• relleno de pipelines, predicción de saltos, aprovechamiento estrategias de

Memoria caché, etc.

Independientes de la máquina: Aplicables en cualquier tipo de máquina objetivo

• Ejecución en tiempo de compilación

• Eliminación de redundancias

• Cambios de orden de ejecución, etc..

2. En función del ámbito de aplicación:


Optimizaciones locales: Aplicadas dentro de un Bloque Básico

• Sólo estudian las instrucciones del B.B. actual.

Optimizaciones globales: Aplicadas a más de un B.B.

• Consideran contenido y flujo de datos entre todos o parte de los B.B.

• Necesidad de recoger información sobre los B.B y sus interrelaciones

Algoritmos de análisis global de flujo de datos

Posibilidades de optimización:

Sobre código fuente (programador/preprocesador) durante generación código objeto

sobre Código Intermedio.
Optimizaciones Locales

1. Ejecución en tiempo de compilación

Pre calcular 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ón 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ón 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
4. Eliminación redundancias en acceso matrices

Localizar expresiones comunes en cálculo direcciones de matrices Codigo fuente:


A: array [1..4, 1..6, 1..8] of integer

A[i,j,5] := A[i,j,6] + A[i,j,4]

Sin optimización:

direc(A[i,j,5]) = direc(A[1,1,1]) + (i-1)*6*8 + (j-1)*8 + (5-1)

direc(A[i,j,6]) = direc(A[1,1,1]) + (i-1)*6*8 + (j-1)*8 + (6-1)

direc(A[i,j,4]) = direc(A[1,1,1]) + (i-1)*6*8 + (j-1)*8 + (4-1)

Con optimizaci´on:

k := direc(A[1,1,1]) + (i-1)*6*8 + (j-1)*8 + (5-1)

direc(A[i,j,5]) = k + 4

direc(A[i,j,6]) = k + 5

direc(A[i,j,4]) = k + 3
c) Reacondicionamiento de operadores

Cambiar orden de evaluación aplicando propiedades conmutativa.

asociativa y distributiva

A := B*C*(D + E) ≡ A := (D + E)*B*C

MOV B,R0

MUL C,R0


MOV R0, t1

MOV D,R0


ADD E, R0

MUL t1,R0

MOV R0,A

MOV D,R0


ADD E,R0

MUL B,R0 5 instrucciones

MUL C,R0 0 temporales

MOV R0,A


Optimización de tipo Mirilla (Peephole optimization)

Aplicable en código intermedio o código objeto.

Constituye una nueva fase aislada.

Idea Básica

Se recorre el código buscando combinaciones de instrucciones que puedan ser reemplazadas por otras equivalentes más eficientes. Se utiliza una ventana de n instrucciones y un conjunto de patrones de transformación (patrón, secuencias reemplazamos). Si las instrucciones de la ventana encajan con algún patrón se reemplazan por lo secuencia de re emplazamiento asociada. Las nuevas instrucciones son reconsideradas para las futuras optimizaciones.
Ejemplos:

Eliminación de cargas innecesarias

MOV Ri, X

MOV X, Rj

MOV Ri, Rj

Reducción de potencia. Eliminación de cadenas de saltos

if C goto L1

L1: goto L2

→ if C goto L2

if C goto L1

goto FIN

L1: ...


...

FIN:
if not C goto FIN

L1: ...

...


FIN:

11.3 Optimizaciones Globales

Optimizaciones entre Bloques Básicos

Optimizaciones típicas:

Identificación de expresiones comunes entre bloques: Afecta a la asignación de registros entre B.B.

Optimización de llamadas a procedimientos; Optimización de bucles, Optimización Llamadas a Procedimientos: Llamadas a procedimientos son muy costosas, cambios del ámbito de referencias, gestión de Registros de Activación, paso de parámetros; asignación de datos locales.


Mejoras:
Optimizar manejo de Reg. Activación, minimizar copia de parámetros y no registros a salvar. Uso almacenamiento estático si no hay llamadas recursivas.

Expansión en línea.

Expansión en línea:

Idea: Eliminar llamadas a procedimientos, “copiando” el cuerpo del procedimiento en el

lugar donde es llamado. Evita sobrecarga asociada con llamadas a procedimientos.

Permite optimizaciones adicionales

El código llamado pasa a ser parte del código que lo llama. Limitaciones: Aumenta uso de memoria.

Util en procedimientos pequeños y llamados desde pocos lugares. Si se llama en un único lugar (es frecuente), no supone coste de espacio adicional.

No aplicable en procedimientos recursivos.
Ejemplos:

while (i <= (limite*2 - 1)) do {

...

}



tmp1 = limite*2 - 1;

while (i <= tmp1) {

...

}

A: array [1..900, 1..900, 1.900] of integer



for i:=1 to 900 do

for j:=1 to 900 do

for k:=1 to 900 do

A[i][j][k]:= i*j*k;

end for

end for


end for

for i:=1 to 900 do

for j:=1 to 900 do

tmp1:= i*j;

tmp2:= dir(A[i][j]);

for k:= 1 to 900 do

tmp2[k]:= tmp1*k;

end for


end for

end for


for i:= 1 to 900 do

tmp3:= dir(A[i]);

for j:= 1 to 900 do

tmp1:= i*j;

tmp2:= dir(tmp3[j]);

for k:= 1 to 900 do

tmp2[k]:= tmp1*k;

end for


end for

end for


i, j y A[i][j] son A[i] es constante.




La base de datos está protegida por derechos de autor ©absta.info 2016
enviar mensaje

    Página principal