T3-REPORTE DE PRACTICAS Y ACTIVIDADES LENG Y AUTO 2 18-05-21 - Mauricio axel 20

Vista previa del material en texto

REPORTE DE PRACTICA/ACTIVIDADES DEL APRENDIZAJE 
DEL TEMA 3 OPTIMIZACIÓN 
FECHA DE ENTREGA: 18 DE MAYO DE 2021 
PERIODO ESCOLAR: FEBRERO – JUNIO 2021 
 
 
CONTENIDO 
INTRODUCCIÓN ..................................................................................................................................... 4 
UNIDAD 3 OPTIMIZACIÓN .................................................................................................................... 6 
SUBTEMAS DE LA UNIDAD: ............................................................................................................ 6 
3.1 TIPOS DE OPTIMIZACIÓN ......................................................................................................... 6 
3.1.1 LOCALES ................................................................................................................................ 9 
3.1.2 CICLOS .................................................................................................................................. 13 
3.1.3 GLOBALES ........................................................................................................................... 13 
3.1.4 DE MIRILLA .......................................................................................................................... 14 
3.2 COSTOS (DE OPTIMIZACIÓN) ................................................................................................ 15 
3.2.1 COSTO DE EJECUIÓN 8MEMORIA, REGISTROS, PILAS)........................................ 15 
3.2.2 CRITERIOS PARA MEJORAR EL CÓDIGO ................................................................... 16 
3.2.3 HERRAMIENTAS PARA EL ANALISIS DEL FLUJO DE DATOS ................................ 16 
ACTIVIDAD 1.- APLICAR LAS TÉCNICAS PARA LA OPTIMIZACIÓN DEL CÓDIGO INTERMEDIO 
GENERADO ........................................................................................................................................... 17 
ACTIVIDAD 2.- TENER NOCIONES ALGEBRAICAS PARA ESTIMAR EL NÚMERO DE VECES 
QUE SE REALIZA UNA INSTRUCCIÓN DENTRO DE UN CICLO O CICOS ANIDADOS ....... 22 
CAPÍTULO 7. OPTIMIZACIÓN DE CÓDIGO ................................................................................... 22 
INSTRUCCIONES ESPECIALES ("IDIOMS") ............................................................................. 23 
REORDENACIÓN DEL CÓDIGO ................................................................................................... 23 
EJECUCIÓN EN TIEMPO DE COMPILACIÓN ............................................................................ 24 
ELIMINACIÓN DE REDUNDANCIAS ............................................................................................ 26 
REORDENACIÓN DE OPERACIONES ........................................................................................ 28 
OPTIMIZACIÓN DE BUCLES ......................................................................................................... 30 
REGIONES ......................................................................................................................................... 34 
ASIGNACIONES MUERTAS ....................................................................................................... 37 
ACTIVIDAD 3.- CONOCER QUE RECURSOS SE CONSUMEN EN INVOCACIÓN A FUNCIONES 
Y EXPRESIONES SIMPLES................................................................................................................ 37 
C_TR_RD — LEER ENTRADAS EN MEMORIA DIAGNÓSTICA ............................................. 37 
ACTIVIDAD 4.- ESTUDIAR NUEVAS TECNICAS PARA LA OPTIMIZACIÓN DE CÓDIGO SOBRE 
TODO PARA AQUELLOS LENGUAJES QUE REQUIEREN DE UNA MAQUINA VIRTUAL PARA 
SU EJECUCIÓN SOBRE MULTIPLATAFORMAS ........................................................................... 38 
 
 
ACTIVIDAD 5.- ESCRIBIR UN ENSAYO QUE ESTABLEZCA LAS TENDENCIAS Y TECNICAS 
EMPLEADAS PARA ESTE PROPSITO ............................................................................................. 47 
ACTIVIDAD 6.- CONOCER LOS CRITERIOS DE TIEMPO DE EJECUCIÓN O EXTENSIÓN DE 
CÓDIGO GENERADO .......................................................................................................................... 54 
FIFO — "FIRST-IN-FIRST-OUT" MEMORY (FIFO MEMORY) .................................................. 54 
2 = Read next value from the FIFOFIFO ........................................................................................ 54 
ACTIVIDAD 7.- INTEGRAR EQUIPOS, PAA ANALIZAR CÓDIGOS INTERMEDIOS EXISTENTES 
Y PRPONER ALGUNAS MEJORAS .................................................................................................. 57 
CONCLUSIÓN ........................................................................................................................................ 60 
BIBLIOGRAFÍA....................................................................................................................................... 61 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
INTRODUCCIÓN 
Idealmente, los compiladores deberían producir código objeto que fuera tan bueno 
como si estuviera escrito directamente por un buen programador. La realidad es que 
esto es difícil de conseguir y muy pocas veces se alcanza esa meta. Sin embargo, el 
código generado por el compilador puede ser mejorado por medio de unas 
transformaciones que se han denominado tradicionalmente optimizaciones, aunque el 
término optimización es impropio ya que raramente se consigue que el código generado 
sea el mejor posible. 
El objetivo de las técnicas de optimización es mejorar el programa objeto para que nos 
dé un rendimiento mayor. La mayoría de estas técnicas vienen a compensar ciertas 
ineficiencias que aparecen en el lenguaje fuente, ineficiencias que son inherentes al 
concepto de lenguaje de alto nivel, el cual suprime detalles de la máquina objeto para 
facilitar la tarea de implementar un algoritmo. Las distintas técnicas de optimización se 
pueden clasificar o dividir de diversas formas. 
Por una parte, podemos hablar de aquellas técnicas que son dependientes de la 
máquina, y aquellas que son independientes de la máquina (o sea, técnicas que sólo 
se pueden aplicar a una determinada máquina objeto y técnicas que son aplicables a 
cualquier máquina objeto). 
Por otra parte, las técnicas de optimización se dividen también en locales y globales. 
Las técnicas de optimización locales analizarán sólo pequeñas porciones de código y 
en ellas realizarán mejoras, mientras que para la aplicación de las técnicas globales 
será necesario el análisis de todo el código. 
Cada optimización está basada en una función de coste y en una transformación que 
preserve el significado del programa. Mediante la función de coste queremos evaluar la 
mejora que hemos obtenido con esa optimización y si compensa con el esfuerzo que el 
compilador realiza para poder llevarla a cabo. Los criterios más comunes que se suelen 
emplear son el ahorro en el tamaño del código, la reducción del tiempo de ejecución y 
la mejora de las necesidades del espacio para los datos del programa. 
 
 
En cuanto a preservar el significado del programa, es lógico que no tendría sentido 
realizar optimizaciones que modificaran el comportamiento del programa. Aunque 
parezca evidente, puede haber complicadas optimizaciones que fallen en ese aspecto. 
Por último, comentar que por muchas optimizaciones que se hayan realizado para 
mejorar el rendimiento de un programa, siempre se obtendrá un mejor rendimiento si se 
utiliza un algoritmo mejor. Por todo ello, para obtener un buen programa lo primero es 
ver qué algoritmo utilizamos y si no es posible desarrollar otro más eficiente. Una vez 
implementado el mejor algoritmo, ya se puede entonces optimizar el código obtenido a 
partir de él para mejorar el rendimiento del programa. 
 
 
 
 
 
 
 
 
 
 
 
 
UNIDAD 3OPTIMIZACIÓN 
SUBTEMAS DE LA UNIDAD: 
3.1 TIPOS DE OPTIMIZACIÓN 
Existen diversas técnicas de optimización que se aplican al código generado para un 
programa sencillo. Por programa sencillo entendemos aquel que se reduce a un sólo 
procedimiento o subrutina. Las técnicas de optimización a través de varios 
procedimientos se reducen a aplicar las vistas aquí a cada uno de los procedimientos y 
después realizar un análisis Inter procedural. Este último tipo de análisis no lo vamos a 
desarrollar en este artículo. 
Partiendo de un programa sencillo, obtenemos código intermedio de tres direcciones 
[AHO77], pues es una representación adecuada del programa sobre la que emplear las 
diversas técnicas de optimización. A partir de aquí dividimos el programa en bloques 
básicos [AHO86], o secuencia de sentencias en las cuales el flujo de control empieza 
al principio y acaba al final, sin posibilidad de parar o de tener saltos. Las sentencias de 
un bloque básico constituyen una unidad sobre la cual se aplican las optimizaciones 
locales. Estas optimizaciones se pueden dividir en: 
a) Optimizaciones que no modifican la estructura. Son: 
1. Eliminación de sobrexpresiones comunes. 
2. Eliminación de código muerto. 
3. Renombrar variables temporales. 
4. Intercambio de sentencias independientes adyacentes. 
b) Transformaciones algebraicas. Son aquellas transformaciones que simplifican 
expresiones y/o reemplazan operaciones costosas de la máquina por otras 
menos costosas. 
Además de este tipo de optimizaciones locales a un bloque básico, existe otro tipo de 
optimizaciones aún más locales, pues su ámbito se reduce a una breve secuencia de 
instrucciones. A este tipo de optimización local se le llama optimización peephole, e 
intenta mejorar el rendimiento del programa por medio de reemplazar esa breve 
 
 
secuencia de instrucciones objeto por otra secuencia más corta y/o más rápida. Hay 
varios tipos de optimización peephole, siendo los más usuales los siguientes: 
1. Eliminación de instrucciones redundantes. 
2. Optimizaciones en el flujo de control. 
3. Simpificaciones algebraicas. 
4. Uso de instrucciones máquina específicas. 
Debido a la naturaleza de este tipo de optimización, su salida es susceptible de ser 
optimizada de nuevo, con lo que serán necesarias varias pasadas para lograr la máxima 
optimización. Una aplicación de este tipo de optimización se puede encontrar en el kit 
ACK desarrollado por Tanenbaum [Tane82], donde se describen 123 combinaciones 
distintas de sentencias de código intermedio con sus correspondientes equivalencias. 
Las técnicas de optimización global se basan todos ellos en el análisis global de flujo 
de datos. Este análisis se realiza para el código de todo el programa, es decir, a lo largo 
de los distintos bloques básicos que forman el código del programa. Suponiendo que 
tenemos la información que nos proporciona este análisis, que lo veremos en el 
siguiente apartado, hay dos tipos de optimizaciones importantes que se realizan: la 
localización y la asignación global de registros para las variables, y las optimizaciones 
que se realizan en los bucles. 
a) Localización y asignación de registros: Para una máquina con registros lo común 
en los procesadores actuales- las instrucciones cuyos operandos están en los 
registros de la máquina son más cortas y más rápidas que aquellas que tratan 
con operandos que están en la memoria. Es por tanto importante decidir qué 
variables se deben almacenar en los registros (localización) y en qué registro se 
debe almacenar cada variable (asignación). 
Existen diversas estrategias para la localización y asignación de los registros. Es 
frecuente asignar algún número fijo de registros que contengan las variables más 
usadas en un bucle interno, sirviendo los registros restantes para las variables locales 
a cada bloque básico. 
 
 
Un método sencillo para determinar la ganancia que obtenemos por almacenar la 
variable "x" durante el bucle L es el siguiente: 
1. Contaremos un ahorro de una unidad por cada referencia a x en el bucle si x está 
en un registro y no está precedida por una asignación a x en el mismo bloque 
básico (debido a la naturaleza del algoritmo que empleamos para generar código 
-ver [AHO86]-). 
2. Contaremos un ahorro de dos unidades si x es una variable viva a la salida de 
un bloque básico en el cual se le ha asignado un valor a x, debido a que evitamos 
almacenar el valor de x a la salida de ese bloque. 
Entonces, una fórmula aproximada para calcular el beneficio obtenido por colocar la 
variable x en un registro en el bucle L es: Σ (use (x, B) + 2*live (x, B)) bloques B en L 
donde use (x, B) es el número de veces que x es usada en B antes de que sea definida, 
y live (x, B) es 1 si x está viva a la salida de B y se le asigna un valor en B, y 0 en 
cualquier otro caso. El cálculo de use (x, B) y live (x, B) se realiza gracias al análisis 
global del flujo de datos. 
b) Optimizaciones en bucles. Habitualmente, un programa pasa la mayor parte del 
tiempo de la ejecución en un trozo de código pequeño. A este fenómeno se le 
conoce como la regla 90-10, queriendo decir que el 90% del tiempo es pasado 
en el 10% del código. Este 10% del código suele estar constituido por bucles, y 
de ahí la importancia de una correcta optimización del código que forma parte de 
los bucles. 
Las principales optimizaciones que se realizan en los bucles son las siguientes: 
1. Movimiento de código. 
2. Eliminación de variables inducidas. 
3. Sustitución de variables costosas por otras menos costosas. 
Y también se suelen aplicar (aunque con menor importancia): 
4. Expansión de código (loop un Rolling) 
5. Unión de bucles (loop jamming) 
 
 
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. 
La optimización va a depender del lenguaje de programación y es directamente 
proporcional al tiempo de compilación; es decir, entre más optimización mayor tiempo 
de compilación. 
➢ Las optimizaciones pueden realizarse de diferentes formas. Las optimizaciones 
se realizan en base al alcance ofrecido por el compilador de programación y es 
directamente proporcional al tiempo de compilación; es decir, entre más 
optimización mayor tiempo de compilación. 
➢ Como el tiempo de optimización es gran consumidor de tiempo (dado que tiene 
que recorrer todo el árbol de posibles soluciones para el proceso de optimización) 
la optimización se deja hasta la fase de prueba final. 
➢ Algunos editores ofrecen una versión de depuración y otra de entrega o final. 
➢ La optimización es un proceso que tiene a minimizar o maximizar alguna variable 
de rendimiento, generalmente tiempo, espacio, procesador, etc. 
➢ Desafortunamente no existen optimizador que hagan un programa más rápido y 
que ocupe menor espacio. 
➢ La optimización se realiza reestructurando el código de tal forma que el nuevo 
código generado tenga mayores beneficios. La mayoría de los compiladores 
tienen una optimización baja, se necesita de compiladores especiales para 
realmente optimizar el código. 
3.1.1 LOCALES 
Las optimizaciones locales se realizan sobre el bloque básico 
➢ Optimizaciones locales 
• Folding 
• Propagación de constantes 
 
 
• Reducción de potencia 
• Reducción de sobreexpresiones 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 Folding 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ón en tiempo de compilación 
1. Precálculo 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 
➢ Reducción de potencia 
➢ Reemplazar una operación 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 
3.1.2 CICLOS 
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. 
• 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 usos de la optimización pueden ser el mejoramiento de consultas en SQL 
o en aplicaciones remotas (sockets, E/S, etc.) 
3.1.3 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 ensamblador. 
 
 
3.1.4 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 las llamadas, siendo el salto lo más 
pequeño posible. 
➢ Ideas básicas: 
• Se recorre el código buscando combinaciones de instrucciones que 
pueden 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, remplazan). 
• Las nuevas instrucciones son reconsideradas para las futuras 
optimizaciones. 
➢ Ejemplos: 
• Eliminación de cargas innecesarias 
• Reducción de potencia 
• Eliminación de cadenas de saltos 
 
 
 
 
 
 
 
 
3.2 COSTOS (DE OPTIMIZACIÓN) 
• Los costos son el factor más importante a tomar en cuenta a la hora de optimizar 
ya que en ocasiones la mejora obtenida puede verse no reflejada en el programa 
final, pero si ser perjudicial para el equipo de desarrollo. 
• La optimización de una pequeña mejora tal vez tenga una pequeña ganancia en 
tiempo o en espacio, pero sale muy costosa en tiempo en generarla. 
• Pero en cambio si esa optimización se hace por ejemplo en un ciclo, la mejora 
obtenida puede ser N veces mayor por lo cual el costo se minimiza y es benéfico 
la mejora. 
• Por ejemplo: for (int i=0; i < 10000; i++); si la ganancia es de 30 ms 300s. 
3.2.1 COSTO DE EJECUIÓN 8MEMORIA, REGISTROS, PILAS) 
Los costos de ejecución son aquellos que vienen implícitos al ejecutar el programa. 
• En algunos programas se tiene un mínimo para ejecutar el programa, por lo que 
el espacio y la velocidad de los microprocesadores son elementos que se deben 
optimizar para tener un mercado potencial más amplio. 
• Las aplicaciones multimedia como los videojuegos tienen un costo de ejecución 
alto por lo cual la optimización de su desempeño es crítica, la gran mayoría de 
las veces requieren de procesadores rápidos (e.g. tarjetas de video) o de mucha 
memoria. 
• Otro tipo de aplicaciones que deben optimizarse son las aplicaciones para 
dispositivos móviles. 
• Los dispositivos móviles tienen recursos más limitados que un dispositivo de 
cómputo convencional razón por la cual, el mejor uso de memoria y otros 
recursos de hardware tiene mayor rendimiento. 
• En algunos casos es preferible tener la lógica del negocio más fuerte en otros 
dispositivos y hacer uso de arquitecturas descentralizadas como cliente/servidor 
o P2P. 
 
 
3.2.2 CRITERIOS PARA MEJORAR EL CÓDIGO 
 La mejor manera de optimizar el código es hacer ver a los programadores que 
optimicen su código desde el inicio, el problema radica en que el costo podría ser muy 
grande ya que tendría que codificar más y/o hacer su código más legible. 
• Los criterios de optimización siempre están definidos por el compilador. 
• Muchos de estos criterios pueden modificarse con directivas del compilador 
desde el código o de manera externa. 
• Este proceso lo realizan algunas herramientas del sistema como los ofuscadores 
para código móvil y código para dispositivos móviles. 
3.2.3 HERRAMIENTAS PARA EL ANALISIS DEL FLUJO DE 
DATOS 
Existen algunas herramientas que permiten el análisis de los flujos de datos, entre ellastenemos los depuradores y desambladores. 
La optimización al igual que la programación es un arte y no se ha podido sistematizar 
del todo. 
 
 
 
 
ACTIVIDAD 1.- APLICAR LAS TÉCNICAS PARA LA OPTIMIZACIÓN 
DEL CÓDIGO INTERMEDIO GENERADO 
Transformaciones algebraicas: Son aquellas transformaciones que simplifican 
expresiones y/o reemplazan operaciones costosas de la máquina por otras menos 
costosas. 
Además de este tipo de optimizaciones locales a un bloque básico, existe otro tipo de 
optimizaciones aún más locales, pues su ámbito se reduce a una breve secuencia de 
instrucciones. A este tipo de optimización local se le llama optimización peephole, e 
intenta mejorar el rendimiento del programa por medio de reemplazar esa breve 
secuencia de instrucciones objeto por otra secuencia más corta y/o más rápida. Hay 
varios tipos de optimización peephole, siendo los más usuales los siguientes: 
1. Eliminación de instrucciones redundantes. 
2. Optimizaciones en el flujo de control. 
3. Simpificaciones algebraicas. 
 
 
4. Uso de instrucciones máquina específicas. 
Debido a la naturaleza de este tipo de optimización, su salida es susceptible de ser 
optimizada de nuevo, con lo que serán necesarias varias pasadas para lograr la máxima 
optimización. Una aplicación de este tipo de optimización se puede encontrar en el kit 
ACK desarrollado por Tanenbaum [Tane82], donde se describen 123 combinaciones 
distintas de sentencias de código intermedio con sus correspondientes equivalencias. 
Las técnicas de optimización global se basan todos ellos en el análisis global de flujo 
de datos. Este análisis se realiza para el código de todo el programa, es decir, a lo largo 
de los distintos bloques básicos que forman el código del programa. Suponiendo que 
tenemos la información que nos proporciona este análisis, que lo veremos en el 
siguiente apartado, hay dos tipos de optimizaciones importantes que se realizan: la 
localización y la asignación global de registros para las variables, y las optimizaciones 
que se realizan en los bucles. 
➢ ANALISIS GLOBAL DE FLUJO DE DATOS 
Para que el compilador pueda realizar la mayoría de las optimizaciones vistas hasta 
ahora, es necesario que posea información de todo el programa, para poder determinar 
si una variable está viva, o si dos sobreexpresiones son comunes, o si una variable se 
puede sustituir por un valor constante, etc. 
Esta información es recogida por el compilador mediante la resolución de las dos 
ecuaciones siguientes: X = (Y - S1) ∪ S2 (1) Y = op X (2) donde X, Y, S1 y S2 son 
diversos conjuntos específicos de cada problema y que definiremos más adelante. 
 
 
En función de que el análisis se realice hacia adelante (de la primera instrucción de 
código a la última) o hacia atrás, y en función del tipo de operador que aparece en la 
segunda ecuación (operador unión u operador intersección), se presentan los siguientes 
cuatro tipos de problemas en el análisis del flujo de datos: 
Mediante la resolución de los 
cuatro tipos de problemas 
anteriores se obtiene toda la 
información necesaria para 
poder realizar las 
optimizaciones anteriores. 
Para concretar, y a modo de 
ejemplo, vamos a desarrollar el 
problema denominado enlace Ud. 
EL ENLACE UD 
• El enlace ud, o enlace uso-definición, trata de determinar qué definiciones 
alcanzan un punto dado de un programa. 
• Por definición de A entendemos una asignación a A o bien la lectura de un valor 
para A. 
• Por uso de una variable A entendemos cualquier aparición de A en que actúa 
como operando. 
• Por un punto en el programa queremos decir la posición antes o después de 
cualquier sentencia de código. 
• Una definición de una variable 
• A alcanza un punto p si hay un camino en el flujo del programa de esa definición 
a p, tal que ninguna otra definición de A aparece en ese camino. 
• Un camino de p1 a pn es una secuencia de puntos p1, p2, ..., pn tal que para 
cada punto i entre el 1 y el n-1 se cumple: 
a) pi es el punto que precede inmediatamente a una sentencia y pi+1 es el 
punto que sigue inmediatamente a esa sentencia en el mismo bloque. 
 
 
b) O bien pi es el final de algún bloque y pi+1 es el comienzo de algún bloque 
sucesor. 
Para calcular qué definiciones alcanzan un punto dado, hemos de calcular para cada 
bloque básico: 
a) El conjunto de definiciones generadas por ese bloque, es decir, aquellas 
definiciones que alcanzan el final del bloque. A este conjunto lo denominaremos 
GEN[B]. 
b) El conjunto de definiciones exteriores a ese bloque que son redefinidas dentro 
del bloque. A este conjunto lo denominaremos KILL [B]. 
c) El conjunto de todas las definiciones que alcanzan el inicio del bloque, 
denominado IN [B], y el conjunto de todas las definiciones que alcanzan el final 
del bloque, denominado OUT[B]. 
Los conjuntos GEN [B] y KILL [B] se determinan por simple inspección en cada bloque 
básico. Para obtener IN [B] y OUT [B], se resuelven las ecuaciones (1) y (2) dadas en 
el apartado anterior, que en este caso adoptan la siguiente forma: 
 
Para la resolución de estas ecuaciones, hay 
que tener en cuenta lo siguiente: 
1. Los conjuntos IN, OUT, GEN, KILL se 
representan como vectores de bits, donde el 
bit i-ésimo tendrá el valor 1 si la definición 
numerada con "i" está en el conjunto. Ello permite que el espacio ocupado por 
estos conjuntos sea pequeño y que las operaciones anteriores se puedan 
implementar con el and y el or lógicos. 
 
 
2. La resolución de las ecuaciones se debe realizar de forma iterativa. Aunque se 
pueden resolver con otras suposiciones, es normal y muy eficiente utilizar el 
siguiente algoritmo para el cálculo de las ecuaciones: 
 
 
 
 
 
 
 
 
 
NOTAS: 
• El algoritmo finaliza cuando los conjuntos IN y OUT permanecen constantes para 
todos los bloques. Se puede probar que un límite superior de iteraciones es el 
número de nodos -bloques básicos- que tiene el diagrama de flujo [KIL73]. 
• El número medio de iteraciones para programas reales es menor que cinco. 
• En el cálculo de los predecesores, asumiremos que cualquier flecha en el 
diagrama de flujo puede ser recorrida. Aunque en algún caso esto no sea verdad, 
esta es una postura conservativa que lo único que hará es que perdamos alguna 
posible optimización, pero nunca que modifiquemos el comportamiento del 
programa, cosa que con la suposición contraria podría ocurrir 
• Una vez resueltas las anteriores ecuaciones, se realiza el cálculo del enlace ud, 
es decir, asociar a cada uso de la variable A las definiciones que alcanzan ese 
uso. 
 
 
• Hay una variedad de aplicaciones al enlace Ud. Entre otras, se puede determinar 
la sustitución de una variable por un valor constante, y también determinar si el 
uso de una variable A está indefinido en algún punto del programa. 
• Por último, señalar que este tipo de análisis de flujo de datos no sólo se aplica 
para optimizar código en compilación, sino que se utiliza también para otras 
aplicaciones. Una aplicación interesante se puede encontrar en [DEJ89]. 
ACTIVIDAD 2.- TENER NOCIONES ALGEBRAICAS PARA ESTIMAR EL 
NÚMERO DE VECES QUE SE REALIZA UNA INSTRUCCIÓN DENTRO 
DE UN CICLO O CICOS ANIDADOS 
CAPÍTULO 7. OPTIMIZACIÓN DE CÓDIGO 
La optimización de código puede realizarse durante la propia generación o como paso 
adicional, ya sea intercalado entre el análisis semántico y la generación de código (se 
optimizan las cuádruplas) o situado después de ésta (se optimiza a posteriori el código 
generado). 
Hay teoremas (Aho, 1970) que demuestran que la optimización perfecta es indecidible. 
Por tanto, las optimizaciones de código en realidad proporcionan mejoras, pero no 
aseguran el éxito total. 
Clasificación de optimizaciones: 
1. Dependientes de la máquina. 
o Asignación de registros (ver capítulo anterior). 
o Instrucciones especiales ("idiomas"). 
o Reordenación del código.2. Independientes de la máquina. 
o Ejecución en tiempo de compilación. 
o Eliminación de redundancias. 
o Cambio de orden. 
o Reducción de frecuencia de ejecución (invariancias). 
o Reducción de fuerza. 
 
 
Optimización y depuración suelen ser incompatibles. Por ejemplo, si se elimina 
totalmente una instrucción, puede ser imposible poner una parada en ella para 
depuración. Ejemplo: x = x; 
INSTRUCCIONES ESPECIALES ("IDIOMS") 
Algunas máquinas tienen instrucciones especiales que permiten acelerar ciertos 
procesos. Por ejemplo: 
• TRT en IBM 390 y XLAT en INTEL permiten realizar una codificación en una sola 
instrucción máquina. 
• MOV en IBM 370 permite copiar bloques de memoria de hasta 255 caracteres. 
• REP en INTEL permite copiar, llenar o comparar bloques de memoria utilizando 
como registros índices SI y DI. 
• TEST en INTEL permite realizar fácilmente varias comparaciones booleanas. 
Ej.: if (x&4 || x&8) ... se puede representar: 
 TEST X,12 
 JZ L 
 ... 
 L: 
REORDENACIÓN DEL CÓDIGO 
En muchas máquinas, la multiplicación en punto fijo de dos operandos de longitud 1 da 
un operando de longitud 2, mientras la división necesita un operando de longitud 2 y 
otro de longitud 1 para dar un cociente y un resto de longitud 1. Reordenar las 
operaciones puede optimizar. Por ejemplo: sea la expresión a=b/c*d; 
 MOV AX, B 
 XOR DX, DX 
 DIV AX, C 
 MUL AX, D 
 MOV A, AX 
 
 
Si la reordenamos así: a=b*d/c; aprovechando que la multiplicación y la división son 
asociativas, tenemos: 
 MOV AX, B 
 MUL AX, D 
 DIV AX, C 
 MOV A, AX 
Ahorramos una instrucción. Veamos otro ejemplo: 
 a=b/c; 
 d=b%c; 
Los dos códigos siguientes son equivalentes. Puede tratarse como un caso particular 
del manejo de registros. La realización de la primera división debería guardar constancia 
de que DX contiene el resultado del resto. 
 MOV AX, B MOV AX, B 
 XOR DX, DX XOR DX, DX 
 DIV AX, C DIV AX, C 
 MOV A, AX MOV A, AX 
 MOV AX, B MOV D, DX 
 XOR DX, DX 
 DIV AX, C 
 MOV D, DX 
EJECUCIÓN EN TIEMPO DE COMPILACIÓN 
Ejemplo: 
 int i; 
 float f; 
 i = 2+3; (+,2,3,t1) (=,5,,i) 
 (=,t1,,i) 
 i = 4; (=,4,,i) (=,4,,i) 
 f = i+2.5; (CIF,i,,t2) (=,6.5,,f) 
 
 
 (+, t2,2.5, t3) 
 (=, t3, f) 
La ejecución se aplica principalmente a las operaciones aritméticas (+-*/) y a las 
conversiones de tipo. 
La tabla de símbolos puede contener el valor conocido del identificador (ej., i=4), o bien 
podemos tener una subtabla T con pares (id, valor). 
Algoritmo para tratar la ejecución en tiempo de compilación: 
• Si la cuádrupla tiene la forma (op, op1, op2, res), donde op1 es un identificador 
y (op1, v1) está en la tabla T, sustituimos en la cuádrupla op1 por v1. 
• Si la cuádrupla tiene la forma (op, op1, op2, res), donde op2 es un identificador 
y (op2, v2) está en la tabla T, sustituimos en la cuádrupla op2 por v2. 
• Si la cuádrupla tiene la forma (op, v1, v2, res), donde v1 y v2 son valores 
constantes o nulos, eliminamos la cuádrupla, eliminamos de T el par (res, v), si 
existe, y añadimos a T el par (res, v1 op v2), a menos que v1 op v2 produzca un 
error, en cuyo caso daremos un aviso y dejaremos la cuádrupla como está. 
Ejemplo: if (false) f = 1/0; 
Esta instrucción debe dar un aviso, pero no un error. De hecho, una optimización 
adicional de código la eliminaría totalmente. 
• Si la cuádrupla tiene la forma (=, v1, res), eliminamos de T el par (res, v), si existe. 
Si v1 es un valor constante, añadimos a T el par (res, v1). 
En el ejemplo: 
 (+,2,3, t1) Elim, T = {(t1,5)} 
 (=, t1, i) Suet por (=, 5, i), T = {(t1,5), (i,5)} 
 (=, 4, i) T = {(t1,5), (i,4)} 
 (CIF, i, t2) Suet por (CIF, 4, t2), 
 Elim, T = {(t1,5), (i,4), (t2,4.0)} 
 
 
 (+, t2,2.5, t3) Sust por (+,4.0,2.5, t3) 
 Elim, T = {(t1,5), (i,4), (t2,4.0), (t3,6.5)} 
 (=, t3, f) Sust por (=,6. 5, f) 
Y quedan las cuádruplas optimizadas: (=, 5, i), (=, 4, i), (=,6. 5, f). 
En cuanto sea posible que los valores de las variables cambien, el compilador debe 
"olvidar" el valor de las variables (inicializar la tabla T, total o parcialmente). Esto puede 
ocurrir si aparece: 
• una etiqueta; 
• una cuádrupla objetivo de una transferencia; 
• una llamada a una subrutina, si se pasan variables por referencia o variables 
globales; 
• una instrucción de lectura externa. 
Este proceso no exige la generación de las cuádruplas, puede realizarse directamente 
durante las rutinas semánticas asociadas al análisis sintáctico, especialmente si es 
Bottom-up. 
Problema con la ejecución en tiempo de compilación: si tenemos un "cross-compiler", 
la precisión puede ser menor en el ordenador que compila que en el que ejecuta. 
ELIMINACIÓN DE REDUNDANCIAS 
Ejemplo: 
 int a, b, c, d; 
 a = a+b*c; (*, b, c, t1) (*, b, c, t1) 
 (+, a, t1, t2) (+, a, t1, t2) 
 (=, t2, a) (=, t2, a) 
 d = a+b*c; (*, b, c, t3) 
 (+, a, t3, t4) (+, a, t1, t4) 
 (=, t4, d) (=, t4, d) 
 b = a+b*c; (*, b, c, t5) 
 
 
 (+, a, t5, t6) 
 (=, t6, b) (=, t4, b) 
Una solución: el programador podría reescribir su programa así: 
 int a, b, c, d, e; 
 e = b*c; (*, b, c, t1) 
 (=, t1, e) 
 a = a+b; (+, a, e, t2) 
 (=, t2, a) 
 d = a+b; (+, a, e, t3) 
 (=, t3, d) 
 b = d; (=, a, b) 
Desventaja: esta forma de programar puede ser más larga y menos legible. Además, 
hay redundancias que el programador no puede eliminar. Por ejemplo: 
 array X[0:4, 0:9]; 
 X[i,j]:=X[i,j]+1; (*,i,10,t1) (*,i,10,t1) 
 (+, t1, j, t2) (+, t1, j, t2) 
 (+, X[t2],1, t3) (+, X[t2],1, t3) 
 (*, i,10, t4) (: =, t3, X[t2]) 
 (+, t4, j, t5) 
 (: =, t3, X[t5]) 
Algoritmo para eliminar redundancias: 
• A cada variable de la tabla de símbolos le asignamos la dependencia -1. 
• Numeramos las cuádruplas. 
• for (i=0; i<número de quádruplas; i++) { 
o Para cada uno de los dos operandos de la cuádrupla: si la cuádrupla de 
la que depende es (SAME, j,0,0), se sustituye el operando por el resultado 
de la cuádrupla (j). 
 
 
o A la cuádrupla (i) le asignamos como dependencia 1 + el máximo de las 
dependencias de sus operandos. 
o Si la cuádrupla (i) tiene como resultado el identificador id, asignamos a id 
la dependencia i. 
o Si la cuádrupla (i) es idéntica a la cuádrupla (j), j<i, excepto por el resultado 
generado, y las dependencias de ambas son iguales, sustituimos la 
cuádrupla i por una nula (SAME, j,0,0), que no genera código. En las 
asignaciones se exige también que el resultado sea el mismo. 
Prueba: si j<k<i, y la cuádrupla k cambiara alguno de los operandos de la cuádrupla i, 
entonces dep(i)>k. Pero dep(j)<=k, luego dep(i)>dep(j) y no se podría eliminar (i). 
Ejercicio: aplicar el algoritmo a los dos ejemplos anteriores. 
El uso de tripletes simplifica el proceso, y aún más si son indirectos. 
REORDENACIÓN DE OPERACIONES 
Tener en cuenta la conmutatividad de algunas operaciones puede mejorar el proceso, 
pues las cuádruplas (*, a, b, -) y (*, b, a, -) serían equivalentes. Para facilitar el 
reconocimiento, se puede adoptar un orden canónico para los operandos de las 
operaciones conmutativas. Por ejemplo: términos que no son variables ni constantes, 
luego variables indexadas por orden alfabético, luego variables sin indexar por orden 
alfabético, finalmente constantes. Esto mejora también la ejecución en tiempo de 
compilación. Por ejemplo, si tenemos las instrucciones 
a=1+c+d+3; a=c+d+1+3; b=d+c+2; b=c+d+2; la reordenación nos permite efectuar en 
tiempo de compilación la operación 1+3,y reconocer c+d como parte común de las dos 
instrucciones. Esto no es completo, sin embargo, ya que a=1+c+d+3; a=c+d+1+3; 
b=d+c+c+d; b=c+c+d+d; la reordenación no nos permite reconocer que c+d, evaluado 
en la primera instrucción, puede aplicarse a la segunda. 
Otra mejora podría ser la utilización de los operadores monádicos para aumentar el 
número de cuádruplos equivalentes. Por ejemplo: 
 
 
 a = c-d; (-, c, d, t1) (-, c, d, t1) 
 (=, t1, a) (=, t1, a) 
 b = d-c; (-, d, c, t2) (-, t1, t2) 
 (=, t2, b) (=, t2, b) 
que no disminuye el número de cuádruplas, pero sustituye una operación diádica por 
una monódica, que usualmente son más eficientes. 
Las variables intermedias para resultados parciales pueden reutilizarse para minimizar 
la memoria (aunque eso puede ir en contra de las optimizaciones anteriores). Por 
ejemplo: sea la expresión (a*b) +(c+d). Sus cuádruplos equivalentes serían: 
 (*, a, b, t1) 
 (+, c, d, t2) 
 (+, t1, t2, t1) 
En este caso, utilizamos dos variables auxiliares (t1, t2). Pero si aprovechamos la 
asociatividad de la suma para reordenar de esta manera: 
 (*, a, b, t1) 
 (+, t1, c, t1) 
 (+, t1, d, t1) 
necesitaremos sólo una variable auxiliar. 
El número mínimo de variables auxiliares se puede calcular construyendo un grafo de 
la expresión y aplicando las siguientes reglas: 
1. Marcar las hojas con 0. 
2. Si (a, b) son las marcas de los hijos del nodo i, si j=k, asociar (k+1) al nodo i, en 
caso contrario asociarle Max (j, k). 
Por ejemplo, el grafo de (a*b) +(c+d) es: 
 +(2) 
 ----------------- 
 *(1) +(1) 
 
 
 --------- --------- 
 a (0) b (0) c (0) d (0) 
Pero el grafo de ((a*b) +c) +d es: 
 +(1) 
 ---------------- 
 +(1) d (0) 
 ----------------- 
 *(1) c (0) 
 --------- 
 a (0) b (0) 
También se puede aprovechar la conmutatividad, como en el ejemplo: 
 (a+b) +(c*d) a+(c*d) +b 
 +(2) +(1) 
 ----------------- ----------------- 
 +(1) *(1) +(1) b (0) 
 --------- --------- --------- 
 a (0) b (0) c (0) d (0) a (0) *(1) 
 --------- 
 c (0) d (0) 
OPTIMIZACIÓN DE BUCLES 
Una operación es invariante respecto a un bucle, si ninguno de los operandos de los 
que depende cambia de valor durante la ejecución del bucle. La optimización consiste 
en sacar la operación fuera del bucle. 
Otra optimización es la reducción de la fuerza de una operación (sustituir una operación 
fuerte por otra más débil, como la multiplicación por la suma o la diferencia por el cambio 
de signo, como en el apartado anterior). Por Ejemplo: 
 for (i=a; i<c; i+=b) {... d=i*k; ...} 
 
 
donde b, k son invariantes respecto al bucle. (b podría ser una expresión, en cuyo caso 
todos sus operandos deben ser invariantes). Además, i no se modifica dentro del bucle, 
excepto en la instrucción de cierre, i+=b, y d no se usa ni modifica antes de la instrucción 
indicada y no se modifica después. En este caso, podemos sustituir el código generado 
por su equivalente: 
 d=a*k; 
 t1=b*k; 
 for (i=a; i<c; i+=b, d+=t1) {...} 
con lo que hemos reducido la fuerza de una multiplicación a una suma (dentro del bucle). 
Esto no se debe hacer si i o k son reales, pues podría perderse precisión al sumar i 
veces en vez de multiplicar una. Pero sí se puede hacer si j, k son enteros. 
Orto Ejemplo: 
 for (i=0; i<10; i++) {... a=(b+c*i) *d; ...} 
 INIT: (=, 0, i) 
 LOOP: ... 
 (*, c, i, t1) 
 (+, b, t1, t2) 
 (*, t2, d, t3) 
 (=, t3, a) 
 ... 
 INCR: (+, i,1, i) 
donde b, c, d son invariantes respecto al bucle, e i es la variable del bucle. Supongamos 
que se cumplen todas las condiciones. Podemos aplicar reducción de fuerza a la 
primera cuádrupla del bucle así: 
 INIT: (=, 0, i) 
 (*, c,0, t1) 
 (*, c,1, t4) 
 LOOP: ... 
 (+, b, t1, t2) 
 (*, t2, d, t3) 
 
 
 (=, t3, a) 
 ... 
 INCR: (+, i,1, i) 
 (+, t1, t4, t1) 
Ahora t1 desempeña el mismo papel que i. Se le asigna un valor inicial y en cada paso 
del bucle se le incrementa en t4. Por tanto, podemos aplicar reducción de fuerza a la 
cuádrupla siguiente: 
 INIT: (=, 0, i) 
 (*, c,0, t1) 
 (*, c,1, t4) 
 (+, b, t1, t2) 
 LOOP: ... 
 (*, t2, d, t3) 
 (=, t3, a) 
 ... 
 INCR: (+, i,1, i) 
 (+, t1, t4, t1) 
 (+, t2, t4, t2) 
Ahora pasa lo mismo con t2, luego podemos aplicar reducción de fuerza a la siguiente 
cuádrupla: 
 INIT: (=, 0, i) 
 (*, c,0, t1) 
 (*, c,1, t4) 
 (+, b, t1, t2) 
 (*, t2, d, t3) 
 (*, t4, d, t5) 
 LOOP: ... 
 (=, t3, a) 
 ... 
 INCR: (+, i,1, i) 
 
 
 (+, t1, t4, t1) 
 (+, t2, t4, t2) 
 (+, t3, t5, t3) 
Todavía podemos optimizar más notando que ahora t1 y t2 no se emplean dentro del 
bucle, luego no es necesario incrementarlas: 
 INIT: (=, 0, i) 
 (*, c,0, t1) 
 (*, c,1, t4) 
 (+, b, t1, t2) 
 (*, t2, d, t3) 
 (*, t4, d, t5) 
 LOOP: ... 
 (=, t3, a) 
 ... 
 INCR: (+, i,1, i) 
 (+, t3, t5, t3) 
Si sacamos operaciones fuera de un bucle, pueden quedar dentro de otro bucle más 
externo. El proceso podría repetirse. Si hay alguna llamada de subrutina dentro del 
bucle, es difícil saber si se cambia alguna de las variables (podrían ser globales o 
pasarse como argumento por referencia). En tal caso, sólo pueden aplicarse las 
optimizaciones si el compilador sabe qué variables se cambian. Esto suele ocurrir sólo 
para ciertas funciones y subrutinas predefinidas. Para realizar las optimizaciones 
pueden hacer falta dos pasos: uno primero, en el que se analizan los bucles y se obtiene 
información sobre las variables que cambian, y otro segundo, en el que se realiza la 
optimización propiamente dicha. Pero también se puede fusionar el proceso con el 
analizador semántico y el generador de código y hacerlo todo en un solo paso. Para 
esto, a veces hay que retrasar o cambiar de orden algunas de las operaciones del bucle. 
Por ejemplo, podríamos generar un código como el siguiente: 
 GOTO INIT 
 LOOP: ... 
 
 
 INCR: ... 
 GOTO TEST 
 INIT: ... 
 TEST: IF (no fin de bucle) GOTO LOOP 
con lo que INIT y INCR (que son los que cambian con la optimización) quedan al final. 
Hay que tener cuidado con estas optimizaciones. Si el bucle se ejecuta normalmente 0 
(o 1) veces, y es muy raro que se entre en él, las optimizaciones anteriores degradarán 
(o dejarán invariante) la eficiencia. 
REGIONES 
Supongamos que tenemos un programa dividido en bloques básicos. con ellos 
podemos formar un grafo donde los nodos son los bloques, los arcos indican sucesión 
de ejecución. Llamamos "región fuertemente conexa" (o simplement región) a un 
subgrafo del programa en el que existe un camino de cualquier nodo del subgrafo a otro 
nodo del subgrafo. Ejemplo: 
 --------------------- 
 | ------ -- | 
 v v | |v | 
 1 -> 2 -> 3 -> 5 -> 6 -> 7 -> 8 
 | ^ 
 |--> 4 ---| 
En la figura hay cinco regiones: (6), (3,5), (2,3,5,6,7), (2,3,4,6,7), (2,3,4,5,6,7). 
Llamamos "bloque de entrada" de una región a un bloque al que entra un arco desde 
fuera de la región. (3,5) tiene un bloque de entrada: 3. (2,3,5,6,7) tiene dos bloques de 
entrada: 2 y 6. 
Llamamos "predecesor"de una región a un bloque situado fuera de la región del que 
sale un arco que lleva a un bloque de entrada de la región. (3,5) tiene un predecesor: 
2. (2,3,5,6,7) tiene dos predecesores: 1 y 4. 
 
 
Construimos una lista R= {R1, R2, ¡Rn} de regiones tales que Ri! =Rj si i! =j, y i<j => Ri 
y Rj no tienen bloques en común o bien Ri es un subconjunto de Rj. En el ejemplo, una 
lista válida sería: (6), (3,5), (2,3,5,6,7), (2,3,4,5,6,7). Otra lista válida sería: (6), 
(2,3,4,6,7), (2,3,4,5,6,7). (2,3,4,6,7) y (2,3,5,6,7) no pueden estar juntas en una lista 
válida. 
¿Cuál elegir? Conviene que estén los bucles, que tienen normalmente un solo nodo 
predecesor y un solo nodo de entrada. Cuando haya dos posibilidades, preferiremos las 
regiones con esta propiedad. 
Para cada bloque definiremos las siguientes variables booleanas: 
• R[i]=1 si la variable i es utilizada dentro del bloque. 
• A[i]=1 si la variable i es asignada dentro del bloque. 
• B[i]=1 si la variable i es usada dentro del bloque antes de asignarle algo. 
El O lógico de R[i] de todos los bloques de una región nos da R[i] para la región. Lo 
mismo con A[i]. 
La optimización se aplica sucesivamente a cada región de la lista, de la primera a la 
última. Al optimizar cada región, se crean bloques nuevos de inicialización. En el 
ejemplo: 
 --------------------------- 
 | ------ -- | 
 v v | |v | 
 1 -> 2 -> 3 -> 5 -> I1 -> 6 -> 7 -> 8 
 | ^ 
 |--> 4 -> I2 ---| 
Los bloques I se añaden a las regiones correspondientes, para que entren en las nuevas 
optimizaciones. Todos los bloques de la región recién tratada se sustituyen por uno solo 
(R1, en este caso), calculando las variables booleanas aplicables a la región. Este 
bloque ya no debe ser optimizado. (R1), (3,5), (2,3,5, I1, R1,7), (2,3,4,5, I1, I2, R1,7). 
 
 
Pasamos a la región R2 (3,5), optimizamos: 
 ---------------------------------- 
 | ------ -- | 
 v v | |v | 
 1 -> 2 -> I3 -> 3 -> 5 -> I1 -> R1 -> 7 -> 8 
 | ^ 
 |--> 4 -> I2 ---| 
y sustituimos: 
 ------------------------------ 
 | -- | 
 v |v | 
 1 -> 2 -> I3 -> R2 -> I1 -> R1 -> 7 -> 8 
 | ^ 
 |-> 4 -> I2 -| 
Las regiones serán: (R1), (R2), (2, I3, R2, I1, R1,7), (2, I3, R2,4, I1, I2, R1,7). Etcétera. 
En principio, sólo hacen falta los vectores booleanos correspondientes a las variables 
que se utilizan dentro de la región que se está optimizando. El algoritmo es como sigue: 
1. i=1; 
2. Seleccionar región Ri. Preparar un bloque I vacío. 
3. Ejecutar y eliminar redundancias dentro de cada bloque de la región. Construir 
los vectores booleanos para cada bloque. 
4. Sacar invariancias y reducir la fuerza dentro de la región, llenando el bloque I. 
Eliminar asignaciones muertas (asignaciones que nunca se usan). Esto cambia 
los vectores booleanos y crea variables temporales. 
5. Crear los tres vectores para la región entera. Sustituir todos sus bloques por el 
bloque región, que ya no debe ser optimizado. Insertar copias del bloque I entre 
todo predecesor y bloque de entrada de la región. 
6. i++; si i<=n, ir al paso 2. 
7. Realizar optimización de cuádruplas y eliminación de redundancias en los 
bloques básicos que no pertenecen a ninguna región. 
 
 
ASIGNACIONES MUERTAS 
Surgen si el resultado de la asignación no se utiliza posteriormente o si la asignación 
es recursiva (ej., i++) y sólo se usa en dichas definiciones recursivas. Todas esas 
asignaciones pueden eliminarse. Suelen surgir como consecuencia de la reducción de 
fuerza y optimizaciones semejantes (como se vio). 
Para ver si una asignación está muerta se puede utilizar el algoritmo: 
1. Seguir las operaciones del bloque. Si aparece otra asignación a la misma 
variable sin un uso intermedio, la asignación está muerta. Si aparece un uso de 
esa variable, la asignación no está muerta. En caso contrario, ir al paso 2. 
2. Seguir todas las ramificaciones del programa a partir del bloque en que estamos 
y mirar las variables R, A, B de cada bloque por el que pasemos. Si encontramos 
B[i]=1 en un bloque, la asignación no está muerta. Si B[i]=0, pero A[i]=1, 
abandonamos este camino. Si se nos acaban los caminos o entramos en bucles, 
la asignación está muerta. 
ACTIVIDAD 3.- CONOCER QUE RECURSOS SE CONSUMEN EN 
INVOCACIÓN A FUNCIONES Y EXPRESIONES SIMPLES 
C_TR_RD — LEER ENTRADAS EN MEMORIA DIAGNÓSTICA 
Permite leer la memoria de diagnóstico. La memoria de diagnóstico contiene hasta 40 
entradas de diagnóstico. Una entrada de diagnóstico consta de 10 bytes. Los primeros 
cinco bytes contienen información sobre la hora del error. Los últimos cinco bytes 
contienen información sobre el error. 
Propina: Puede encontrar más información sobre la composición de las entradas de 
diagnóstico en el manual del sistema CPX. 
Parámetro de entrada 
FU32 
Número de la primera palabra de indicador en la que se van a guardar los 
datos (0 ... 9999) 
 
 
Parámetro de entrada 
FU33 
Número de la primera entrada en la memoria diagnóstica a partir de la cual se 
va a iniciar la lectura (0 ... 39) 
FU34 Número de entradas (0 ... 40) *) 
*) Con 0, no se leen entradas de diagnóstico, pero solo se proporciona la información 
de los parámetros de retorno FU33 y FU34. 
 
 
 
 
 
 
 
 
Parámetro de retorno *) 
FU32 Estado del módulo 
FU33 Número de entradas disponibles 3482 
FU34 
Atropello y estado 
- Bit 0: Overrun (más de 40 entradas) 
- Bit 1: Registro inactivo 
3483 
*) El parámetro corresponde al número de función denominado 
 
 
ACTIVIDAD 4.- ESTUDIAR NUEVAS TECNICAS PARA LA 
OPTIMIZACIÓN DE CÓDIGO SOBRE TODO PARA AQUELLOS 
LENGUAJES QUE REQUIEREN DE UNA MAQUINA VIRTUAL PARA SU 
EJECUCIÓN SOBRE MULTIPLATAFORMAS 
Organización de la memoria en tiempo de ejecución. 
 
Cuando un programa se ejecuta sobre un sistema operativo existe un proceso previo 
llamado cargador que suministra al programa un bloque contiguo de memoria sobre el 
cual ha de ejecutarse. El programa resultante de la compilación debe organizarse de 
forma que haga uso de este bloque. Para ello el compilador incorpora al programa objeto 
el código necesario. 
 
Las técnicas de gestión de la memoria durante la ejecución del programa difieren de unos 
lenguajes a otros, e incluso de unos compiladores a otros. En este capítulo se estudia la 
gestión de la memoria que se utiliza en lenguajes procedurales como FORTRAN, 
PASCAL, C, MODULA-2, etc. La gestión de la memoria en otro tipo de lenguajes 
(funcionales, lógicos, ...) es en general diferente de la organización que aquí se plantea. 
 
Para lenguajes imperativos, los compiladores generan programas que tendrán en tiempo 
de ejecución una organización de la memoria similar (a grandes rasgos) a la que aparece 
en la figura 1. 
 
 
 
 
 
 
 
 
 
 
Fig. 1. Organización de la memoria 
en la ejecución 
 
En este esquema se distinguen las secciones de: 
 
- El Código 
- La Memoria Estática. 
- La Pila. 
- El Montón. 
 
 
 
 
Es la zona donde se almacenan las instrucciones del programa ejecutable en código 
máquina, y también el código correspondiente a los procedimientos y funciones que 
utiliza. Su tamaño puede fijarse en tiempo de compilación. 
 
Algunos compiladores fragmentan el código del programa objeto usando “overlays”. 
Estos “overlays” son secciones de código objeto que se almacenan en ficheros 
independientes y que se cargan en la memoria central (RAM) dinámicamente, es decir, 
durante la ejecución del programa. Los overlays de un programa se agrupan en zonas y 
módulos,cada uno de los cuales contiene un conjunto de funciones o procedimientos. 
 
 
 
fig.2 Ejemplos de configuraciones de la zona de código utilizando “overlays” 
 
Durante el tiempo de ejecución sólo uno de los módulos de cada uno de los overlays 
puede estar almacenado en memoria. El compilador reserva en la sección de código una 
zona contigua de memoria para cada overlay. El tamaño de esta zona debe ser igual al del 
mayor módulo que se cargue sobre ella. Es función del programador determinar cuantas 
zonas de overlay se definen, qué funciones y procedimientos se encapsulan en cada 
módulo, y cómo se organizan estos módulos para ocupar cada uno de los overlays. Una 
restricción a tener en cuenta es que las funciones de un módulo no deben hacer referencia 
a funciones de otro módulo del mismo overlay, ya que nunca estarán simultáneamente 
en memoria. 
 
El tiempo de ejecución de un programa con overlays es mayor, puesto que durante la 
ejecución del programa es necesario cargar cada módulo cuando se realiza una llamada 
a alguna de las funciones que incluye. También es tarea del programador diseñar la 
estructura de overlays de manera que se minimice el número de estas operaciones. La 
técnica de overlays se utiliza cuando el programa a compilar es muy grande en relación 
con la disponibilidad de memoria del sistema, o bien si se desea obtener programas de 
menor tamaño.
El Código 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
La forma más fácil de almacenar el contenido de una variable en memoria en tiempo de ejecución 
es en memoria estática o permanente a lo largo de toda la ejecución del programa. No todos los 
objetos (variables) pueden ser almacenados estáticamente. Para que un objeto pueda ser 
almacenado en memoria estática su tamaño (número de bytes necesarios para su almacenamiento) 
ha de ser conocido en tiempo de compilación. Como consecuencia de esta condición no podrán 
almacenarse en memoria estática: 
 
• Los objetos correspondientes a procedimientos o funciones recursivas, ya que en 
tiempo de compilación no se sabe el número de variables que serán necesarias. 
 
• Las estructuras dinámicas de datos tales como listas, árboles, etc. ya que el número 
de elementos que la forman no es conocido hasta que el programa se ejecuta. 
 
 
 
fig 3. Alojamiento en memoria de un objeto X 
 
 
Las técnicas de asignación de memoria estática son sencillas. A partir de una posición 
señalada por un puntero de referencia se aloja el objeto X, y se avanza el puntero tantos 
bytes como sean necesarios para almacenar el objeto X. La asignación de memoria puede 
hacerse en tiempo de compilación y los objetos están vigentes desde que comienza la 
ejecución del programa hasta que termina. 
 
En los lenguajes que permiten la existencia de subprogramas, y siempre que todos los 
objetos de estos subprogramas puedan almacenarse estáticamente (por ejemplo, en 
FORTRAN-IV) se aloja en la memoria estática un registro de activación correspondiente 
a cada uno de los subprogramas. Estos registros de activación contendrán las variables 
locales, parámetros formales y valor devuelto por la función, tal como indica la fig. 4.b. 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
fig 4a. Registro de activación fig 4b. Estructura de la memoria estática en FORTRAN-IV 
 
Dentro de cada registro de activación las variables locales se organizan secuencialmente. 
Existe un solo registro de activación para cada procedimiento y por tanto no están 
permitidas las llamadas recursivas. El proceso que se sigue cuando un procedimiento p 
llama a otro q es el siguiente: 
 
• p evalúa los parámetros de llamada, en caso de que se trate de expresiones complejas, 
usando para ello una zona de memoria temporal para el almacenamiento intermedio. 
Por ejemplo, si la llamada a q es q((3*5)+(2*2),7) las operaciones previas a la llamada 
propiamente dicha en código máquina han de realizarse sobre alguna zona de 
memoria temporal. (En algún momento debe haber una zona de memoria que 
contenga el valor intermedio 15, y el valor intermedio 4 para sumarlos a continuación). 
En caso de utilización de memoria estática ésta zona de temporales puede ser común 
a todo el programa, ya que su tamaño puede deducirse en tiempo de compilación. 
• q inicializa sus variables y comienza su ejecución. 
 
Dado que las variables están permanentemente en memoria es fácil implementar la 
propiedad de que conserven o no su contenido para cada nueva llamada. 
La Memoria Estática. 
 
 
 
La aparición de lenguajes con estructura de bloque trajo consigo la necesidad de técnicas 
de alojamiento en memoria más flexibles, que pudieran adaptarse a las demandas de 
memoria durante la ejecución del programa. En estos lenguajes, cada vez que comienza 
la ejecución de un procedimiento se crea un registro de activación para contener los 
objetos necesarios para su ejecución, eliminándolo una vez terminada ésta. 
 
Dado que los bloques o procedimientos están organizados jerárquicamente, los distintos 
registros de activación asociados a cada bloque deberán colocarse en una pila en la que 
entrarán cuando comience la ejecución del bloque y saldrán al terminar el mismo. (Fig. 
5b) La estructura de los registros de activación varía de unos lenguajes a otros, e incluso 
de unos compiladores a otros. Este es uno de los problemas por los que a veces resulta 
difícil enlazar los códigos generados por dos compiladores diferentes. En general, los 
registros de activación de los procedimientos suelen tener algunos de los campos que 
pueden verse en la fig. 
5a. 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
fig 5b. Estructura de la pila 
fig.5a. Registro de activación 
El puntero de control de activación guarda el valor que tenía el puntero de la cima de la 
pila antes de que entrase en ella el nuevo registro, de esta forma una vez que se desee 
desalojarlo puede restituirse el puntero de la pila a su posición original. Es decir, es el 
puntero que se usa para la implementación de la estructura de datos “Pila” del 
compilador. 
 
En la zona correspondiente al estado de la máquina se almacena el contenido que hubiera 
en los registros de la máquina antes de comenzar la ejecución del procedimiento. Estos 
valores deberán ser repuestos al finalizar la ejecución del procedimiento. El código 
encargado de realizar la copia del estado de la máquina es común para todos los 
procedimientos. 
 
El puntero a las variables no locales permite el acceso a las variables declaradas en otros 
procedimientos. Normalmente no es necesario usar este campo puesto que puede 
La Pila 
 
 
conseguirse lo mismo con el puntero de control de activación, sólo tiene especial sentido 
cuando se utilizan procedimientos recursivos. 
 
 
Al igual que en el alojamiento estático los registros de activación contendrán el espacio 
correspondiente a los parámetros formales (variables que aparecen en la cabecera) y las 
variables locales, (las que se definen dentro del bloque o procedimiento) así como una 
zona para almacenar el valor devuelto por la función y una zona de valores temporales 
para el cálculo de expresiones. 
 
Para dos módulos o procedimientos diferentes, los registros de activación tendrán 
tamaños diferentes. Este tamaño por lo general es conocido en tiempo de compilación ya 
que se dispone de información suficiente sobre el tamaño de los objetos que lo 
componen. En ciertos casos esto no es así como por ejemplo ocurre en C cuando se 
utilizan arrays de dimensión indefinida. En estos casos el registro de activación debe 
incluir una zona de desbordamiento al final cuyo tamaño no se fija en tiempo de 
compilación sino solo cuando realmente llega a ejecutarse el procedimiento. Esto 
complica un poco la gestión de la memoria, por lo que algunos compiladores de bajo 
coste suprimen esta facilidad. 
 
El procedimiento de gestión de la pila cuando un procedimiento q llamaa otro 
procedimiento p, se desarrolla en dos fases, la primera de ellas corresponde al código que 
se incluye en le procedimiento q antes de transferir el control a p, y la segunda, al código 
que debe incluirse al principio de p para que se ejecute cuando reciba el control. 
 
› El procedimiento autor de la llamada (q) evalúa las expresiones de la llamada, utilizando para 
ello su zona de variables temporales, y copia el resultado en la zona correspondiente a los 
parámetros formales del procedimiento que recibe la llamada. 
› El autor de la llamada (q) coloca el puntero de control del procedimiento al que llama( p) 
de forma que apunte al final de la pila y transfiere el control al procedimiento al que 
llama (p). 
› El receptor de la llamada (p) salva el estado de la máquina antes de comenzar su ejecución 
usando para ello la zona correspondiente de su registro de activación. 
› El receptor de la llamada (p) inicializa sus variables y comienza su ejecución. 
Al terminar la ejecución del procedimiento llamado (p) se desaloja su registro de 
activación procediendo también en dos fases. La primera se implementa mediante 
instrucciones al final del procedimiento que acaba de terminar su ejecución (p), y la 
segunda en el procedimiento que hizo la llamada tras recobrar el control: 
› El procedimiento saliente (p) antes de finalizar su ejecución coloca el valor de retorno 
al principio de su registro de activación. 
› Usando la información contenida en su registro el procedimiento que finaliza (p) restaura el 
estado de la máquina y coloca el puntero de final de pila en la posición en la que estaba 
originalmente. 
› El procedimiento que realizó la llamada (q) copia el valor devuelto por el procedimiento 
La Pila 
 
 
al que llamó (p) dentro de su propio registro de activación (de q). 
 
La fig. 6b. Muestra el estado de la figura (durante el tiempo de ejecución cuando se 
alcanza la instrucción señalada en el código de la fig. 6a: 
 
 
fig.6b. Registros de activación en la pila durante la ejecución del programa
La Pila 
fig 6a. Código fuente 
 
 
 
 
 
Cuando el tamaño de un objeto a colocar en memoria puede variar en tiempo de 
ejecución, no es posible su ubicación en memoria estática, ni tan siquiera en la pila. Son 
ejemplos de este tipo de objetos las listas, los árboles, las cadenas de caracteres de 
longitud variable, etc. Para manejar este tipo de objetos el compilador debe disponer de 
un área de memoria de tamaño variable y que no se vea afectada por la activación o 
desactivación de procedimientos. Este trozo de memoria se llama montón (traducción 
literal del término ingles heap que se utiliza habitualmente en la literatura técnica). En 
aquellos lenguajes de alto novel que requieran el uso del montón, el compilador debe 
incorporar al programa objeto el código correspondiente a la gestión del montón. Las 
operaciones básicas que se realizan sobre el montón son: 
› Alojamiento: Se demanda un bloque contiguo para poder almacenar un objeto de un 
cierto tamaño. 
› Desalojo: Se indica que ya no es necesario conservar un objeto, y que por lo tanto, la memoria 
que ocupa debe quedar libre para ser reutilizada en caso necesario por otros objetos. 
 
Según sea el programador o el propio sistema el que las invoque, estas operaciones 
pueden ser explícitas o implícitas respectivamente. En caso de alojamiento explícito el 
programador incluye en el código fuente una instrucción que demanda una cierta cantidad 
de memoria para la ubicación de un dato (por ejemplo, en PASCAL mediante la 
instrucción new, fig. 7a; en C mediante malloc, fig 7b; etc.). La cantidad de memoria 
requerida puede ser calculada por el compilador en función del tipo correspondiente al 
objeto que se desea alojar, o bien puede ser especificado directamente por el 
programador. El resultado de la función de alojamiento es por lo general un puntero a un 
trozo contiguo de memoria dentro del montón que puede usarse para almacenar el valor 
del objeto. Los lenguajes de programación imperativos utilizan por lo general alojamiento 
y desalojo explícitos. Por el contrario, los lenguajes lógicos y funcionales evitan al 
programador la tarea de manejar directamente los punteros 
realizando las operaciones implícitamente. 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
fig. 7a. PASCAL 
 
El montón 
 
 
 47 
 
ACTIVIDAD 5.- ESCRIBIR UN ENSAYO QUE ESTABLEZCA LAS 
TENDENCIAS Y TECNICAS EMPLEADAS PARA ESTE PROPSITO 
INTRODUCCION 
 Idealmente, los compiladores deberían producir código objeto que fuera tan bueno 
como si estuviera escrito directamente por un buen programador. La realidad es que 
esto es difícil de conseguir y muy pocas veces se alcanza esa meta. Sin embargo, 
el código generado por el compilador puede ser mejorado por medio de unas 
transformaciones que se han denominado tradicionalmente optimizaciones, aunque 
el término optimización es impropio ya que raramente se consigue que el código 
generado sea el mejor posible. El objetivo de las técnicas de optimización es mejorar 
el programa objeto para que nos dé un rendimiento mayor. 
La mayoría de estas técnicas vienen a compensar ciertas ineficiencias que 
aparecen en el lenguaje fuente, ineficiencias que son inherentes al concepto de 
lenguaje de alto nivel, el cual suprime detalles de la máquina objeto para facilitar la 
tarea de implementar un algoritmo. Las distintas técnicas de optimización se pueden 
clasificar o dividir de diversas formas. Por una parte, podemos hablar de aquellas 
técnicas que son dependientes de la máquina, y aquellas que son independientes 
de la máquina (o sea, técnicas que sólo se pueden aplicar a una determinada 
máquina objeto y técnicas que son aplicables a cualquier máquina objeto). 
Por otra parte, las técnicas de optimización se dividen también en locales y globales. 
Las técnicas de optimización locales analizarán sólo pequeñas porciones de código 
y en ellas realizarán mejoras, mientras que para la aplicación de las técnicas 
globales será necesario el análisis de todo el código. Cada optimización está basada 
en una función de coste y en una transformación que preserve el significado del 
programa. Mediante la función de coste queremos evaluar la mejora que hemos 
obtenido con esa optimización y si compensa con el esfuerzo que el compilador 
realiza para poder llevarla a cabo. 
 Los criterios más comunes que se suelen emplear son el ahorro en el tamaño del 
código, la reducción del tiempo de ejecución y la mejora de las necesidades del 
espacio para los datos del programa. En cuanto a preservar el significado del 
programa, es lógico que no tendría sentido realizar optimizaciones que modificaran 
el comportamiento del programa. 
 
 
 48 
Aunque parezca evidente, puede haber complicadas optimizaciones que fallen en 
ese aspecto. Por último, comentar que por muchas optimizaciones que se hayan 
realizado para mejorar el rendimiento de un programa, siempre se obtendrá un 
mejor rendimiento si se utiliza un algoritmo mejor. Por todo ello, para obtener un 
buen programa lo primero es ver qué algoritmo utilizamos y si no es posible 
desarrollar otro más eficiente. Una vez implementado el mejor algoritmo, ya se 
puede entonces optimizar el código obtenido a partir de él para mejorar el 
rendimiento del programa. 
TIPOS DE OPTIMIZACION 
Existen diversas técnicas de optimización que se aplican al código generado5 para 
un programa sencillo. Por programa sencillo entendemos aquel que se reduce a 
un sólo procedimiento o subrutina. Las técnicas de optimización a través de varios 
procedimientos se reducen a aplicar las vistas aquí a cada uno de los 
procedimientos y después realizar un análisis Inter procedural. Este último tipo de 
análisis no lo vamos a desarrollar en este artículo. Partiendo de un programa 
sencillo, obtenemos código intermedio de tres direcciones [AHO77], pues es una 
representaciónadecuada del programa sobre la que emplear las diversas técnicas 
de optimización. 
A partir de aquí dividimos el programa en bloques básicos [AHO86], o secuencia 
de sentencias en las cuales el flujo de control empieza al principio y acaba al final, 
sin posibilidad de parar o de tener saltos. Las sentencias de un bloque básico 
constituyen una unidad sobre la cual se aplican las optimizaciones locales. Estas 
optimizaciones se pueden dividir en: a) Optimizaciones que no modifican la 
estructura. 
Son: 1. Eliminación de sobrexpresiones comunes. 
2. Eliminación de código muerto. 
3. Renombrar variables temporales. 
4. Intercambio de sentencias independientes adyacentes. 
b) Transformaciones algebraicas. Son aquellas transformaciones que simplifican 
expresiones y/o reemplazan operaciones costosas de la máquina por otras menos 
costosas. Además de este tipo de optimizaciones locales a un bloque básico, existe 
otro tipo de optimizaciones aún más locales, pues su ámbito se reduce a una breve 
secuencia de instrucciones. A este tipo de optimización local se le llama 
optimización peephole, e intenta mejorar el rendimiento del programa por medio de 
 
 
 49 
reemplazar esa breve secuencia de instrucciones objeto por otra secuencia más 
corta y/o más rápida. 
Hay varios tipos de optimización peephole, siendo los más usuales los siguientes: 
1. Eliminación de instrucciones redundantes. 
2. Optimizaciones en el flujo de control. 
3. Simpificaciones algebraicas. 
4. Uso de instrucciones máquina específicas. 
Debido a la naturaleza de este tipo de optimización, su salida es susceptible de ser 
optimizada de nuevo, con lo que serán necesarias varias pasadas para lograr la 
máxima optimización. 
Una aplicación de este tipo de optimización se puede encontrar en el kit ACK 
desarrollado por Tanembaum [Tane82], donde se describen 123 combinaciones 
distintas de sentencias de código intermedio con sus correspondientes 
equivalencias. Las técnicas de optimización global se basan todos ellos en el 
análisis global de flujo de datos. 
Este análisis se realiza para el código de todo el programa, es decir, a lo largo de 
los distintos bloques básicos que forman el código del programa. Suponiendo que 
tenemos la información que nos proporciona este análisis, que lo veremos en el 
siguiente apartado, hay dos tipos de optimizaciones importantes que se realizan: la 
localización y la asignación global de registros para las variables, y las 
optimizaciones que se realizan en los bucles. 
a) Localización y asignación de registros. - Para una máquina con registros -lo 
común en los procesadores actuales- las instrucciones cuyos operandos 
están en los registros de la máquina son más cortas y más rápidas que 
aquellas que tratan con operandos que están en la memoria. Es por tanto 
importante decidir qué variables se deben almacenar en los registros 
(localización) y en qué registro se debe almacenar cada variable 
(asignación). Existen diversas estrategias para la localización y asignación 
de los registros. 
b) Es frecuente asignar algún número fijo de registros que contengan las 
variables más usadas en un bucle interno, sirviendo los registros restantes 
para las variables locales a cada bloque básico. 
Un método sencillo para determinar la ganancia que obtenemos por almacenar 
la variable "x" durante el bucle L es el siguiente: 
 
 
 50 
1. Contaremos un ahorro de una unidad por cada referencia a x en el bucle si x 
está en un registro y no está precedida por una asignación a x en elmismo bloque 
básico (debido a la naturaleza del algoritmo que empleamos para generar código 
-ver [AHO86]-). 
2. Contaremos un ahorro de dos unidades si x es una variable viva a la salida de 
un bloque básico en el cual se le ha asignado un valor a x, debido a que evitamos 
almacenar el valor de x a la salida de ese bloque. Entonces, una fórmula 
aproximada para calcular el beneficio obtenido por colocar la variable x en un 
registro en el bucle L es: Σ ( use(x,B) + 2*live(x,B) ) bloques B en L donde use(x,B) 
es el número de veces que x es usada en B antes de que sea definida, y live(x,B) 
es 1 si x está viva a la salida de B y se le asigna un valor en B, y 0 en cualquier 
otro caso. 
El cálculo de use(x,B) y live(x,B) se realiza gracias al análisis global del flujo de 
datos. b) Optimizaciones en bucles. Habitualmente, un programa pasa la 
mayor parte del tiempo de la ejecución en un trozo de código pequeño. A este 
fenómeno se le conoce como la regla 90-10, queriendo decir que el 90% del 
tiempo es pasado en el 10% del código. Este 10% del código suele estar 
constituído por bucles, y de ahí la importancia de una correcta optimización del 
código que forma parte de los bucles. 
Las principales optimizaciones que se realizan en los bucles son las siguientes: 
1. Movimiento de código. 
2. Eliminación de variables inducidas. 
3. Sustitución de variables costosas por otras menos costosas. Y también se 
suelen aplicar (aunque con menor importancia): 
4. Expansión de código (loop unrolling). 
5. Unión de bucles (loop jamming). 
ANALISIS GLOBAL DE FLUJO DE DATOS 
Para que el compilador pueda realizar la mayoría de las optimizaciones vistas 
hasta ahora, es necesario que posea información de todo el programa, para 
poder determinar si una variable está viva, o si dos subexpresiones son comunes, 
o si una variable se puede sustituir por un valor constante, etc. 
 
 
 
 51 
 Esta información es recogida por el compilador mediante la resolución de las 
dos ecuaciones siguientes: X = ( Y - S1 ) ∪ S2 (1) Y = op X (2) donde X, Y, S1 y 
S2 son diversos conjuntos específicos de cada problema y que definiremos más 
adelante. 
EL ENLACE UD. 
El enlace ud, o enlace uso-definición, trata de determinar qué definiciones 
alcanzan un punto dado de un programa. Por definición de A entendemos una 
asignación a A o bien la lectura de un valor para A. Por uso de una variable A 
entendemos cualquier aparición de A en que actúa como operando. Por un punto 
en el programa queremos decir la posición antes o después de cualquier 
sentencia de código. Una definición de una variable A alcanza un punto p si hay 
un camino en el flujo del programa de esa definición a p, tal que ninguna otra 
definición de A aparece en ese camino. 
Un camino de p1 a pn es una secuencia de puntos p1 , p2 , ..., pn tal que para 
cada punto i entre el 1 y el n-1 se cumple: 
a) pi es el punto que precede inmediatamente a una sentencia y pi+1 es el punto 
que sigue inmediatamente a esa sentencia en el mismo bloque. 
b) O bien pi es el final de algún bloque y pi+1 es el comienzo de algún bloque 
sucesor. 
Para calcular qué definiciones alcanzan un punto dado, hemos de calcular para 
cada bloque básico: 
a) El conjunto de definiciones generadas por ese bloque, es decir, aquellas 
definiciones que alcanzan el final del bloque. A este conjunto lo denominaremos 
GEN[B]. 
b) El conjunto de definiciones exteriores a ese bloque que son redefinidas dentro 
del bloque. A este conjunto lo denominaremos KILL [B]. 
 c) El conjunto de todas las definiciones que alcanzan el inicio del 
bloque,denominado IN [B], y el conjunto de todas las definiciones que alcanzan 
el final del bloque, denominado OUT[B]. Los conjuntos GEN [B] y KILL [B] se 
determinan por simple inspección en cada bloque básico. 
 
 
 
 
 52 
Para obtener IN [B] y OUT [B], se resuelven las ecuaciones (1) y (2) dadas en el 
apartado anterior, que en este caso adoptan la siguiente forma: OUT[B] = ( IN[B] 
- KILL[B] ) ∪ GEN[B] IN[B] = ∪ OUT[P] P es un predecesor de B Para la 
resolución de estas ecuaciones, hay que tener en cuenta lo siguiente: 
1. Los conjuntos IN, OUT, GEN, KILL se representan como vectores de bits, 
donde el bit i-ésimo tendrá el valor 1 sii la definición numerada con "i" está en el 
conjunto. Ello permite que el espacio ocupado por estos conjuntos sea pequeño