Compiladores

CAP9 Generación de
Código (cont.)

9.10 Generación de código a partir de un
GDA
• Generar código a partir de un GDA permite ver fácilmente
como reorganizar el orden de las proposiciones de tres
direcciones para generar código optimo

(MEJORA).

• GDA con arboles permite incluso generar código demostrado
como mas eficiente desde el punto de vista de la longitud del
programa (menor número deinstrucciones).

Reorganización del orden
• Reordenando las proposiciones puede influir en el costo del
código objeto resultante, generando código mas eficiente
mediante el ahorro de instrucciones (carga y descarga de
temporales).

Reorganización del orden (cont.)

Se guarda R0 en temp. t1

Se carga temp. t1 en R1.

Algoritmo de ordenamiento heurístico

Algoritmo de ordenamiento heurístico

•listar:= 4,1,3,2
• Se invierte ‘listar’ y queda 2,3,1,4

Sin ordenar

“mejorado”

Ordenamiento óptimo para GDA con
arboles
• Se puede determinar un orden óptimo para la evaluaciones de
proposiciones cuando la representación en GDA del bloque es
un árbol.
• Orden óptimo significa el orden que produce la secuencia de
instrucciones más corta, de todas las secuencias de
instrucciones que evalúan elárbol.

Algoritmo de ordenamiento óptimo para
GDA con árboles
• Consta de dos partes. La primera parte etiqueta cada nodo del
árbol, en forma ascendente, con un numerito que indica la
cantidad mínima de registros requerido para evaluar el árbol
sin utilizar la memoria.
• La segunda parte implica recorrido del árbol cuyo orden viene
determinado por las etiquetas calculadas de los nodos.
• El códigoresultante se genera durante el recorrido del árbol.
• El algoritmo de la segunda parte funciona evaluando los dos
operandos de un operador binario, primero el operando que
requiera un número mayor de registros (el operando mas
difícil). Si ambos operandos empatan en la exigencia de
registros, se evalúa cualquiera de ellos.

Algoritmo de etiquetado

Algoritmo de etiquetado

Algoritmo de generaciónde código a partir
de un árbol etiquetado
• Tiene como entrada un árbol ya etiquetado (paso 1) y produce como
salida una secuencia de código de máquina.
• El algoritmo utiliza el procedimiento recursivo gencódigo(n)
para producir código de máquina que evalúe, en algún registro R, el
subárbol de T con raíz n.
• El procedimiento gencódigo(n) utiliza una pila llamada ‘pilar’
para asignar registros, yademás utiliza una pila llamada ‘pilat’ para
asignar temporales.
• Una llamada a gencódigo puede encontrar un subconjunto de
los registros, quizás en un orden distinto en ‘pilar’, al salir del
procedimiento se vuelve a dejar los registros de ‘pilar’ en el mismo
orden en el que se encontraban.
• Al inicio la pila ‘pilar’ contiene todos los registros disponibles R0, R1,
…, R(r – 1), donde ‘r’(minúscula) es el máximo numero de registros
disponibles. Así mismo la pila ‘pilat’ contiene T0, T1, T2…

Algoritmo de generación de código a partir
de un árbol etiquetado
• La función permuta(pilar) intercambia los dos registros ubicados
en el tope de la pila ‘pilar’. Es decir si en el tope está R0 seguido de
R1, al permutar estará R1 en el tope seguido de R0.
• Ej.: R1,R0-> R0,R1
• El uso de permutagarantiza que un hijo izquierdo y su padre se
evalúen en el mismo registro.
• saca(pila) saca el ultimo elemento del tope de la pila,
mete(pila) mete un elemento en el tope de la pila, y tope(pila)
devuelve el elemento tope actual de la pila.

Algoritmo de generación de código a partir
de un árbol etiquetado

Algoritmo de generación de código a partir
de un árbol etiquetado
Solo se generainstrucción de
carga MOV...

Se genera código
para evaluar n1 en el
registro R =
tope(pilar) seguido
de la instrucción op
nombre, R.

9.12 Generación de código mediante
reescritura de árboles
• El código objeto se genera durante un proceso en el que el árbol de
entrada se reduce a un solo nodo, aplicando al árbol una secuencia
de reglas de reescritura de árboles.
• Cada regla de rescritura de...