Estrategias de Optimización de Compiladores: Rendimiento de Código Local y Global

Optimización de Compiladores: Técnicas Locales y Globales

Optimización Local de Código

La optimización local se aplica a fragmentos de código pequeños, generalmente dentro de un bloque básico, buscando mejorar la eficiencia inmediata.

Definición de Bloque Básico

Un bloque básico es un fragmento de código que tiene una única entrada y una única salida, y cuyas instrucciones se ejecutan de manera secuencial.

Técnicas Clave de Optimización Local

• Propagación de Constantes: Reemplazar variables por sus valores constantes conocidos.
• Folding (Plegado de Constantes): Evaluación de expresiones constantes en tiempo de compilación.
• Reducción de Potencia (Strength Reduction): Sustituir operaciones costosas por otras más simples.
• Eliminación de Subexpresiones Comunes: Calcular subexpresiones que aparecen más de una vez una sola vez y reutilizar el resultado.

Detalle de Técnicas Locales

Plegado de Constantes (Folding): Consiste en reemplazar las expresiones por su resultado cuando se pueden evaluar en tiempo de compilación (resultado constante). Ejemplo: A = 2 + 3 + A + C se transforma en A = 5 + A + C.

Propagación de Constantes: Desde que se asigna un valor constante a una variable hasta la siguiente asignación, se considera que la variable es equivalente a la constante.

Reducción de Potencia: Se busca sustituir operaciones costosas por otras más simples. Ejemplo: sustituir productos por sumas.

Eliminación de Subexpresiones Comunes: Las subexpresiones que aparecen más de una vez se calculan una sola vez y se reutiliza el resultado.

Optimización Global de Bucles

Expansión de Bucles (Loop Unrolling)

Esta técnica solo se puede aplicar a los bucles cuyo número de iteraciones se conoce en tiempo de compilación, reduciendo la sobrecarga de control del ciclo.

Conceptos de Optimización Global

Para la optimización global, se utiliza el Árbol de Dominación, donde no puede haber más de un dominador inmediato por nodo.

Reducción de Frecuencia (Frequency Reduction)

Detecta las operaciones invariantes de ciclo y las calcula una única vez delante del ciclo, evitando su repetición en cada iteración.

Reducción de Potencia (Strength Reduction)

Se busca sustituir operaciones laboriosas por otras más simples, especialmente útil dentro de los bucles.

Flujo de Datos y Optimización Global

Antes de realizar una optimización global, es necesario crear el Grafo de Flujo de Ejecución. Este grafo representa todos los caminos posibles de ejecución del programa.

La información contenida en el grafo es útil para:

• El programador
• El optimizador

Información Clave del Flujo de Datos (Representación en Conjuntos)

Esta información se representa en forma de conjuntos como los siguientes:

• Expresiones disponibles
• Alcance de las definiciones
• Variables vivas
• Expresiones muy utilizadas (Very Busy Expressions)

Definición de Expresión Muy Utilizada

Una expresión es muy utilizada en un punto $p$ cuando el valor de la expresión se requiere antes que el valor de cualquiera de sus términos a lo largo de cualquier camino que empieza en $p$.

Herramientas para el Flujo de Datos

El proceso de flujo de datos utiliza las siguientes herramientas:

1. Diagrama de Flujo de Datos (DFD)
2. Diccionario de Datos
3. Diagrama de Estructura de Datos

Diagrama de Flujo de Datos (DFD)

Los DFD, como se les conoce popularmente, son la herramienta más importante y la base sobre la cual se desarrollan otros componentes del sistema.

Diccionario de Datos

Un diccionario de datos es un catálogo, un depósito, de los elementos de un sistema.

Diagrama de Estructura de Datos

Es una técnica necesaria para la modelización de datos, la cual representa un conjunto de datos relacionados entre sí y describe en forma colectiva un componente del sistema.

Optimización de Mirilla (Peephole Optimization)

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.

• Es aplicable en código intermedio o código objeto.
• Constituye una nueva fase aislada dentro del proceso de compilación.