Diseño del compilador: optimización de código

La optimización es una técnica de transformación de programas, que intenta mejorar el código haciéndolo consumir menos recursos (es decir, CPU, memoria) y entregar alta velocidad.

En la optimización, las construcciones de programación general de alto nivel se reemplazan por códigos de programación de bajo nivel muy eficientes. Un proceso de optimización de código debe seguir las tres reglas que se indican a continuación:

El código de salida no debe, de ninguna manera, cambiar el significado del programa.
La optimización debería aumentar la velocidad del programa y, si es posible, el programa debería demandar menos recursos.
La optimización en sí misma debería ser rápida y no debería retrasar el proceso de compilación general.

Se pueden realizar esfuerzos para un código optimizado en varios niveles de compilación del proceso.

Al principio, los usuarios pueden cambiar / reorganizar el código o utilizar mejores algoritmos para escribir el código.
Después de generar el código intermedio, el compilador puede modificar el código intermedio mediante cálculos de direcciones y mejorando los bucles.
Mientras produce el código de la máquina de destino, el compilador puede utilizar la jerarquía de memoria y los registros de la CPU.

La optimización se puede categorizar ampliamente en dos tipos: independiente de la máquina y dependiente de la máquina.

Optimización independiente de la máquina

En esta optimización, el compilador toma el código intermedio y transforma una parte del código que no involucra ningún registro de CPU y / o ubicaciones de memoria absoluta. Por ejemplo:

do
{
   item = 10;
   value = value + item; 
} while(value<100);

Este código implica la asignación repetida del elemento identificador, que si lo ponemos de esta manera:

Item = 10;
do
{
   value = value + item; 
} while(value<100);

no solo debe guardar los ciclos de la CPU, sino que puede usarse en cualquier procesador.

Optimización dependiente de la máquina

La optimización dependiente de la máquina se realiza después de que se ha generado el código de destino y cuando el código se transforma de acuerdo con la arquitectura de la máquina de destino. Implica registros de CPU y puede tener referencias de memoria absolutas en lugar de referencias relativas. Los optimizadores dependientes de la máquina se esfuerzan por aprovechar al máximo la jerarquía de memoria.

Bloques básicos

Los códigos fuente generalmente tienen una serie de instrucciones, que siempre se ejecutan en secuencia y se consideran los bloques básicos del código. Estos bloques básicos no tienen sentencias de salto entre ellos, es decir, cuando se ejecuta la primera instrucción, todas las instrucciones del mismo bloque básico se ejecutarán en su secuencia de aparición sin perder el control de flujo del programa.

Un programa puede tener varias construcciones como bloques básicos, como sentencias condicionales IF-THEN-ELSE, SWITCH-CASE y bucles como DO-WHILE, FOR y REPEAT-UNTIL, etc.

Identificación de bloque básico

Podemos usar el siguiente algoritmo para encontrar los bloques básicos en un programa:

Buscar declaraciones de encabezado de todos los bloques básicos desde donde comienza un bloque básico:
- Primera declaración de un programa.
- Declaraciones que son objetivo de cualquier rama (condicional / incondicional).
- Declaraciones que siguen a cualquier declaración de rama.
Las declaraciones de encabezado y las declaraciones que las siguen forman un bloque básico.
Un bloque básico no incluye ninguna declaración de encabezado de ningún otro bloque básico.

Los bloques básicos son conceptos importantes tanto desde el punto de vista de la optimización como de la generación de código.

Los bloques básicos juegan un papel importante en la identificación de variables, que se utilizan más de una vez en un solo bloque básico. Si alguna variable se utiliza más de una vez, la memoria de registro asignada a esa variable no necesita vaciarse a menos que el bloque termine de ejecutarse.

Gráfico de flujo de control

Los bloques básicos de un programa se pueden representar mediante diagramas de flujo de control. Un diagrama de flujo de control muestra cómo se pasa el control del programa entre los bloques. Es una herramienta útil que ayuda en la optimización al ayudar a localizar los bucles no deseados en el programa.

Optimización de bucle

La mayoría de los programas se ejecutan como un bucle en el sistema. Es necesario optimizar los bucles para ahorrar ciclos de CPU y memoria. Los bucles se pueden optimizar mediante las siguientes técnicas:

Invariant code: Un fragmento de código que reside en el bucle y calcula el mismo valor en cada iteración se denomina código invariante en bucle. Este código se puede sacar del bucle guardándolo para que se calcule solo una vez, en lugar de hacerlo con cada iteración.
Induction analysis : Una variable se denomina variable de inducción si su valor se modifica dentro del ciclo por un valor invariante del ciclo.
Strength reduction: Hay expresiones que consumen más ciclos de CPU, tiempo y memoria. Estas expresiones deben reemplazarse con expresiones más baratas sin comprometer la salida de la expresión. Por ejemplo, la multiplicación (x * 2) es cara en términos de ciclos de CPU que (x << 1) y produce el mismo resultado.

Eliminación de código muerto

El código muerto es una o más declaraciones de código, que son:

O nunca ejecutado o inalcanzable,
O si se ejecuta, su salida nunca se usa.

Por lo tanto, el código muerto no juega ningún papel en la operación de ningún programa y, por lo tanto, simplemente se puede eliminar.

Código parcialmente muerto

Hay algunas declaraciones de código cuyos valores calculados se utilizan sólo en determinadas circunstancias, es decir, a veces se utilizan los valores y otras no. Estos códigos se conocen como código parcialmente muerto.

El gráfico de flujo de control anterior muestra una parte del programa donde la variable 'a' se usa para asignar la salida de la expresión 'x * y'. Supongamos que el valor asignado a 'a' nunca se usa dentro del ciclo. Inmediatamente después de que el control abandona el ciclo, a 'a' se le asigna el valor de la variable 'z', que se usaría más adelante en el programa. Concluimos aquí que el código de asignación de 'a' nunca se usa en ningún lugar, por lo tanto, es elegible para ser eliminado.

Del mismo modo, la imagen de arriba muestra que la declaración condicional es siempre falsa, lo que implica que el código, escrito en caso verdadero, nunca se ejecutará, por lo que se puede eliminar.

Redundancia parcial

Las expresiones redundantes se calculan más de una vez en una ruta paralela, sin ningún cambio en los operandos, mientras que las expresiones redundantes parciales se calculan más de una vez en una ruta, sin ningún cambio en los operandos. Por ejemplo,

[expresión redundante]	[expresión parcialmente redundante]

El código invariante en bucle es parcialmente redundante y se puede eliminar mediante una técnica de movimiento de código.

Otro ejemplo de un código parcialmente redundante puede ser:

If (condition)
{
   a = y OP z;
}
else
{
   ...
}
c = y OP z;

Suponemos que los valores de los operandos (y y z) no se modifican de la asignación de variable a a variable c. Aquí, si el enunciado de la condición es verdadero, entonces y OP z se calcula dos veces, de lo contrario una vez. El movimiento de código se puede utilizar para eliminar esta redundancia, como se muestra a continuación:

If (condition)
{
   ...
   tmp = y OP z;
   a = tmp;
   ...
}
else
{
   ...
   tmp = y OP z;
}
c = tmp;

Aquí, si la condición es verdadera o falsa; y OP z debe calcularse solo una vez.

↰ Previous page