Optimización de Bloques Básicos

La optimización se aplica a los bloques básicos después de la fase de generación de código intermedio del compilador. La optimización es el proceso de transformación de un programa que mejora el código consumiendo menos recursos y entregando alta velocidad. En la optimización, los códigos de alto nivel se reemplazan por sus códigos de bajo nivel eficientes equivalentes. La optimización de bloques básicos puede ser dependiente o independiente de la máquina. Estas transformaciones son útiles para mejorar la calidad del código que finalmente se generará a partir del bloque básico.

Hay dos tipos de optimizaciones básicas de bloque:   

1. Transformaciones que preservan la estructura
2. Transformaciones algebraicas

Transformaciones que preservan la estructura:

La transformación que preserva la estructura en bloques básicos incluye:

1. Eliminación de código muerto
2. Eliminación de subexpresiones comunes
3. Cambio de nombre de variables temporales
4. Intercambio de dos declaraciones adyacentes independientes

1. Eliminación de código muerto: 

El código muerto se define como esa parte del código que nunca se ejecuta durante la ejecución del programa. Entonces, para la optimización, se elimina dicho código o código muerto. El código que nunca se ejecuta durante el programa (Código Muerto) toma tiempo por lo que, por optimización y rapidez, se elimina del código. La eliminación del código muerto aumenta la velocidad del programa ya que el compilador no tiene que traducir el código muerto.

Ejemplo:

// Program with Dead code
int main()
{
    x = 2 
    if (x > 2) 
      cout << "code"; // Dead code
    else 
      cout << "Optimization";
    return 0;
}

// Optimized Program without dead code
int main()
{
    x = 2;
    cout << "Optimization"; // Dead Code Eliminated
    return 0;
}

2. Eliminación de subexpresiones comunes:

En esta técnica, las subexpresiones que son comunes y se usan con frecuencia se calculan solo una vez y se reutilizan cuando es necesario. DAG (Gráfico acíclico dirigido) se utiliza para eliminar subexpresiones comunes.

Ejemplo: 

 

3.Renombramiento de Variables Temporales: 

Las declaraciones que contienen instancias de una variable temporal se pueden cambiar a instancias de una nueva variable temporal sin cambiar el valor del bloque básico.

Ejemplo: La declaración t = a + b se puede cambiar a x = a + b donde t es una variable temporal yx es una nueva variable temporal sin cambiar el valor del bloque básico.

4. Intercambio de dos declaraciones adyacentes independientes:  

Si un bloque tiene dos declaraciones adyacentes que son independientes, se pueden intercambiar sin afectar el valor básico del bloque.

Ejemplo: 

t1 = a + b
t2 = c + d 

Estas dos declaraciones independientes de un bloque se pueden intercambiar sin afectar el valor del bloque.

Transformación algebraica:

Se pueden usar innumerables transformaciones algebraicas para cambiar el conjunto de expresiones calculadas por un bloque básico en un conjunto algebraicamente equivalente. Algunas de las transformaciones algebraicas en bloques básicos incluyen:

1. Plegado constante
2. Propagación de copias
3. Reducción de fuerza

1. Plegado constante:

Resuelva los términos constantes que son continuos para que el compilador no necesite resolver esta expresión.

Ejemplo:

x = 2 * 3 + y   ⇒ x = 6 + y  (Optimized code)

2. Propagación de copias: 

Es de dos tipos, propagación variable y propagación constante.

Propagación variable:

                                     x = y z = y + 2 (Código optimizado)

                                     z = x + 2

Propagación constante:

                                     x = 3 z = 3 + a (Código optimizado)

                                      z = x + un 

3. Reducción de fuerza: 

Reemplace las declaraciones/instrucciones caras por otras más baratas.

x = 2 * y (costly)  ⇒  x = y + y (cheaper)
x = 2 * y (costly)  ⇒ x = y << 1 (cheaper)

Optimización de bucle: 

La optimización de bucle incluye las siguientes estrategias:

1. Movimiento de código y reducción de frecuencia
2. Eliminación de variables de inducción
3. Fusión/combinación de bucles
4. Desenrollado de bucle

1. Código de movimiento y reducción de frecuencia

Mueve el código invariable del bucle fuera del bucle.

// Program with loop variant inside loop
int main()
{
    for (i = 0; i < n; i++) {
        x = 10;
        y = y + i;
    }
    return 0;
}

// Program with loop variant outside loop
int main()
{
    x = 10;
    for (i = 0; i < n; i++)
        y = y + i;
    return 0;
}

2. Eliminación de variables de inducción: 

Elimine varias variables de inducción innecesarias utilizadas en el bucle.

// Program with multiple induction variables
int main()
{
    i1 = 0;
    i2 = 0;
    for (i = 0; i < n; i++) {
        A[i1++] = B[i2++];
    }
    return 0;
}

// Program with one induction variable
int main()
{
    for (i = 0; i < n; i++) {
        A[i] = B[i]; // Only one induction variable
    }
    return 0;
}

3. Combinación/fusión de bucles: 

Si las operaciones realizadas se pueden realizar en un solo ciclo, fusione o combine los ciclos.

// Program with multiple loops
int main()
{
    for (i = 0; i < n; i++)
        A[i] = i + 1;
    for (j = 0; j < n; j++)
        B[j] = j - 1;
}
return 0;
}  

// Program with one loop when multiple loops are merged
int main()
{
    for (i = 0; i < n; i++) {
        A[i] = i + 1;
        B[i] = i - 1;
    }
    return 0;
}

4. Desenrollado de bucles: 

Si existe un código simple que puede reducir la cantidad de veces que se ejecuta el ciclo, entonces el ciclo se puede reemplazar con estos códigos.

// Program with loops
int main()
{
    for (i = 0; i < 3; i++)
        cout << "Cd";
    return 0;
}

// Program with simple code without loops
int main()
{
    cout << "Cd";
    cout << "Cd";
    cout << "Cd";
    return 0;
}