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 haciendo que consuma menos recursos (es decir, CPU, Memoria) y entregue alta velocidad.

En optimización, las construcciones de programación general de alto nivel se sustituyen 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 debe aumentar la velocidad del programa y, si es posible, el programa debe exigir menos recursos.

• La optimización en sí misma debe ser rápida y no debe retrasar el proceso de compilación general.

Se pueden hacer 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 usar mejores algoritmos para escribir el código.

• Después de generar código intermedio, el compilador puede modificar el código intermedio mediante cálculos de direcciones y mejorando los bucles.

• Al producir el código de máquina de destino, el compilador puede hacer uso de la jerarquía de memoria y los registros de CPU.

La optimización se puede clasificar 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 implica registros de CPU ni ubicaciones de memoria absolutas. Por ejemplo:

do{ item = 10; value = value + item; } while(value
This code involves repeated assignment of the identifier item, which if we put this way:
Item = 10;do{ value = value + item; } while(value
should not only save the CPU cycles, but can be used on any processor.
Machine-dependent Optimization
Machine-dependent optimization is done after the target code has been generated and when the code is transformed according to the target machine architecture. It involves CPU registers and may have absolute memory references rather than relative references. Machine-dependent optimizers put efforts to take maximum advantage of memory hierarchy.
Basic Blocks
Source codes generally have a number of instructions, which are always executed in sequence and are considered as the basic blocks of the code. These basic blocks do not have any jump statements among them, i.e., when the first instruction is executed, all the instructions in the same basic block will be executed in their sequence of appearance without losing the flow control of the program.
A program can have various constructs as basic blocks, like IF-THEN-ELSE, SWITCH-CASE conditional statements and loops such as DO-WHILE, FOR, and REPEAT-UNTIL, etc.
Basic block identification
We may use the following algorithm to find the basic blocks in a program:



Instrucciones de cabecera de búsqueda de todos los bloques básicos desde donde comienza un bloque básico:

Primera declaración de un programa.Instrucciones 
 que son destino de cualquier rama (condicional / incondicional).Declaraciones 
 que siguen a cualquier declaración de rama.



Las instrucciones de encabezado y las instrucciones que las siguen forman un bloque básico.


Un bloque básico no incluye ninguna instrucció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 generación de código como de la optimización.

 Los bloques básicos desempeñan 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 gráficos de flujo de control. Un gráfico 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 cualquier bucle no deseado en el programa.

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


Código invariante: Un fragmento de código que reside en el bucle y calcula el mismo valor en cada iteración se denomina código invariante de bucle. Este código se puede mover fuera del bucle guardándolo para ser calculado solo una vez, en lugar de con cada iteración.


Análisis de inducción: Una variable se denomina variable de inducción si su valor se altera dentro del bucle por un valor invariante del bucle.


Reducción de fuerza: Hay expresiones que consumen más ciclos de CPU, tiempo y memoria. Estas expresiones deben ser reemplazadas por 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 


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 ninguna operación de programa y, por lo tanto, simplemente se puede eliminar.
 Código parcialmente muerto
 Hay algunas sentencias de código cuyos valores calculados se usan solo en ciertas circunstancias, es decir, a veces se usan los valores y a veces no. Estos códigos se conocen como código parcialmente muerto.

 El gráfico de flujo de control anterior muestra un fragmento de programa donde se usa la variable ‘a ‘para asignar la salida de la expresión’x * y’. Supongamos que el valor asignado a ‘a’ nunca se usa dentro del bucle.Inmediatamente después de que el control abandona el bucle, 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 que es elegible para ser eliminado.

 Del mismo modo, la imagen de arriba muestra que la instrucción condicional siempre es falsa, lo que implica que el código, escrito en caso verdadero, nunca se ejecutará, por lo que puede eliminarse.
Redundancia parcial
 Las expresiones redundantes se calculan más de una vez en 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,

El código invariante en bucle es parcialmente redundante y puede eliminarse mediante una técnica de movimiento de código.
 Otro ejemplo de código parcialmente redundante puede ser:
If (condition){ a = y OP z;}else{ ...}c = y OP z;
Asumimos que los valores de los operandos (y y z) no se cambian de asignación de variable a a variable c. Aquí, si la declaración de condición es verdadera, entonces y OP z se calcula dos veces, de lo contrario una sola 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.


Anuncios