Optimización de código en el diseño del compilador – Part 1

La optimización de código en la fase de síntesis es una técnica de transformación de programas, que trata de mejorar el código intermedio haciéndolo consumir menos recursos (es decir, CPU, memoria) para que resulte un código de máquina de ejecución más rápida. El proceso de optimización del compilador debe cumplir los siguientes objetivos:

• La optimización debe ser correcta, no debe, de ninguna manera, cambiar el significado del programa.
• La optimización debería aumentar la velocidad y el rendimiento del programa.
• El tiempo de compilación debe ser razonable.
• El proceso de optimización no debe retrasar el proceso de compilación general.

¿Cuándo optimizar? 

La optimización del código a menudo se realiza al final de la etapa de desarrollo, ya que reduce la legibilidad y agrega código que se usa para aumentar el rendimiento. 

¿Por qué optimizar? 

La optimización de un algoritmo está más allá del alcance de la fase de optimización del código. Entonces el programa está optimizado. Y puede implicar reducir el tamaño del código. Entonces, la optimización ayuda a:

• Reduce el espacio consumido y aumenta la velocidad de compilación.
• El análisis manual de conjuntos de datos implica mucho tiempo. Por lo tanto, utilizamos software como Tableau para el análisis de datos. Del mismo modo, realizar la optimización manualmente también es tedioso y es mejor hacerlo usando un optimizador de código.
• Un código optimizado a menudo promueve la reutilización.

Tipos de optimización de código: el proceso de optimización se puede clasificar en términos generales en dos tipos:

1. Optimización independiente de la máquina: esta fase de optimización de código intenta mejorar el código intermedio para obtener un mejor código de destino como salida. La parte del código intermedio que se transforma aquí no involucra ningún registro de CPU ni ubicaciones de memoria absolutas.
2. Optimización dependiente de la máquina: la optimización dependiente de la máquina se realiza después de generar el código de destino y cuando el código se transforma de acuerdo con la arquitectura de la máquina de destino. Involucra 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 la memoria.

La optimización del código se realiza de las siguientes maneras diferentes:

1. Evaluación del tiempo de compilación:

(i)   A = 2*(22.0/7.0)*r 
      Perform 2*(22.0/7.0)*r at compile time.
(ii)  x = 12.4
      y = x/2.3 
      Evaluate x/2.3 as 12.4/2.3 at compile time.

2. Propagación variable:

//Before Optimization 
c = a * b                                               
x = a                                                  
till                                                           
d = x * b + 4 
  
  
//After Optimization 
c = a * b  
x = a
till
d = a * b + 4

3. Propagación constante:  

• Si el valor de una variable es una constante, entonces reemplace la variable con la constante. La variable puede no ser siempre una constante.

Ejemplo: 

(i)  A = 2*(22.0/7.0)*r
     Performs 2*(22.0/7.0)*r at compile time.
(ii)  x = 12.4
      y = x/2.3
      Evaluates x/2.3 as 12.4/2.3 at compile time.
(iii) int k=2;
      if(k) go to L3;
      It is evaluated as :
      go to L3 ( Because k = 2 which implies condition is always true)

4. Plegado constante: 

• Considere una expresión: a = b op c y los valores b y c son constantes, entonces el valor de a se puede calcular en tiempo de compilación.

Ejemplo: 

#define k 5
x = 2 * k 
y = k + 5
   
This can be computed at compile time and the values of x and y are :
 x = 10
 y = 10

Nota: diferencia entre propagación constante y plegamiento constante: 

• En la propagación constante, la variable se sustituye por su constante asignada donde, al igual que en la propagación constante, se consideran y calculan las variables cuyos valores se pueden calcular en el momento de la compilación. 

5. Propagación de copias: 

• Es extensión de constante propagación.
• Después de asignar a x, use a para reemplazar x hasta que a se asigne nuevamente a otra variable, valor o expresión.
• Ayuda a reducir el tiempo de compilación, ya que reduce la copia.

Ejemplo : 

//Before Optimization
c = a * b                                              
x = a                                                 
till                                                          
d = x * b + 4
 
 
//After Optimization
c = a * b 
x = a
till
d = a * b + 4

6. Eliminación de subexpresión común: 

• En el ejemplo anterior, a*b y x*b es una subexpresión común.

7. Eliminación de código muerto: 

•  La propagación de copias a menudo conduce a que las declaraciones de asignación se conviertan en código muerto.
• Se dice que una variable está muerta si nunca se usa después de su última definición.
• Para encontrar las variables muertas, se debe realizar un análisis de flujo de datos.

Ejemplo: 

c = a * b                                               
x = a                                               
till                                                         
d = a * b + 4  
 
//After elimination :
c = a * b
till
d = a * b + 4

8. Eliminación de código inalcanzable: 

• Primero, se debe construir el gráfico de flujo de control.
• El bloque que no tiene un borde entrante es un bloque de código inalcanzable.
• Después de una propagación constante y un plegamiento constante, las ramas inalcanzables pueden eliminarse.
   

#include <iostream>
using namespace std;
 
int main() {
  int num;
  num=10;
    cout << "GFG!";
    return 0;
  cout << num; //unreachable code
}
//after elimination of unreachable code
int main() {
  int num;
  num=10;
    cout << "GFG!";
    return 0;
 }

9. Función en línea: 

• Aquí, una llamada de función se reemplaza por el cuerpo de la función misma.
• Esto ahorra mucho tiempo al copiar todos los parámetros, almacenar la dirección de retorno, etc.

10. Clonación de funciones: 

• Aquí, se crean códigos especializados para una función para diferentes parámetros de llamada.
• Ejemplo: sobrecarga de funciones

11. Variable de inducción y reducción de fuerza: 

• Se utiliza una variable de inducción en el bucle para el siguiente tipo de asignación i = i + constante. Es una especie de técnica de optimización de bucle. 
• La reducción de fuerza significa reemplazar el operador de alta fuerza por uno de baja fuerza.

Ejemplos: 

Example 1 :
Multiplication with powers of 2 can be replaced by shift right operator which is less
expensive than multiplication
a=a*16
// Can be modified as :
a = a<<4
 
Example 2 :
i = 1;                                                                     
while (i<10)                                                         
{                                                                            
   y = i * 4;
}
 
 
//After Reduction
i = 1
t = 4
{
  while( t<40)
  y = t;
  t = t + 4;
}

Técnicas de optimización de bucle: 

1. Movimiento de código o reducción de frecuencia: 

• Se reduce la frecuencia de evaluación de la expresión.
• Las sentencias invariantes del bucle se sacan del bucle. 

Ejemplo: 

a = 200;
 while(a>0)
 {
     b = x + y;
     if (a % b == 0}
     printf(“%d”, a);
   }
 
 
//This code can be further optimized as
a = 200;
b = x + y;
while(a>0)
 {
     if (a % b == 0}
     printf(“%d”, a);
   }

2. Atasco de bucle: 

• Dos o más bucles se combinan en un solo bucle. Ayuda a reducir el tiempo de compilación.

Ejemplo: 

// Before loop jamming
for(int k=0;k<10;k++)
{
 x = k*2;
}
 
for(int k=0;k<10;k++)
{
 y = k+3;
}
 
//After loop jamming
for(int k=0;k<10;k++)
{
 x = k*2;
 y = k+3;
}

3. Desenrollado de bucles: 

• Ayuda a optimizar el tiempo de ejecución del programa al reducir las iteraciones.
• Aumenta la velocidad del programa al eliminar el control de bucle y las instrucciones de prueba.

Ejemplo: 

//Before Loop Unrolling
 
for(int i=0;i<2;i++)
{
  printf("Hello");
}
 
//After Loop Unrolling
 
printf("Hello");
printf("Hello");

¿Dónde aplicar la Optimización? 

Ahora que aprendimos la necesidad de optimización y sus dos tipos, ahora veamos dónde aplicar esta optimización.

• Programa fuente: la optimización del programa fuente implica realizar cambios en el algoritmo o cambiar las estructuras de bucle. El usuario es el actor aquí.
• Código intermedio: la optimización del código intermedio implica cambiar los cálculos de dirección y transformar las llamadas de procedimiento involucradas. Aquí el compilador es el actor.
• Código de destino: el compilador realiza la optimización del código de destino. El uso de registros y las instrucciones de selección y movimiento son parte de la optimización involucrada en el código de destino.
• Optimización local: las transformaciones se aplican a pequeños bloques básicos de declaraciones. Las técnicas seguidas son la numeración de valores locales y el equilibrio de la altura del árbol.
• Optimización Regional: Las transformaciones se aplican a los Bloques Básicos Extendidos. Las técnicas seguidas son la numeración de valores superlocales y el desenrollado de bucles.
• Optimización global: las transformaciones se aplican a grandes segmentos de programas que incluyen funciones, procedimientos y bucles. Las técnicas seguidas son el Análisis de Variables en Vivo y el Reemplazo de Código Global.
• Optimización entre procedimientos:   como su nombre lo indica, las optimizaciones se aplican entre procedimientos. Las técnicas seguidas son la sustitución en línea y la colocación de procedimientos.