Análisis simbólico en el diseño del compilador

El análisis simbólico ayuda a expresar expresiones de programa como expresiones simbólicas. Durante la ejecución del programa, el comportamiento funcional se deriva de la representación algebraica de sus cálculos. Generalmente, durante la ejecución normal del programa, se calcula el valor numérico del programa pero se pierde la información sobre cómo se logran. Por lo tanto, el análisis simbólico nos ayuda a comprender la relación entre diferentes cálculos. Es de gran ayuda para optimizar nuestro programa utilizando técnicas de optimización como la propagación constante , la reducción de fuerza y ​​la eliminación de cálculos redundantes. Nos ayuda a comprender e ilustrar el análisis regional de nuestro programa. El análisis simbólico nos ayuda en la optimización , paralelizacióny comprender el programa.

Ejemplo:

#include <iostream>
using namespace std;
int main()
{
    int a, b, c;
    cin >> a;
    b = a + 1;
    c = a - 1;
    if (c > a)
        c = c + 1;
    return 0;
}

En el código anterior usando análisis simbólico, podemos darnos cuenta de que «if(c>a)» nunca es cierto y la línea «c=c+1» nunca se ejecuta, por lo tanto, permite que el optimizador elimine este bloque de código. 

1. Expresiones afines:

Una función afín es una función lineal. En el análisis simbólico, tratamos de expresar las variables como expresiones afines de las variables de referencia siempre que sea posible. Las expresiones afines se utilizan principalmente en la indexación de arrays, lo que ayuda a comprender la optimización y la paralelización de nuestro programa.

Una expresión afín también se puede escribir en términos de varias iteraciones en nuestro programa, esto a menudo se denomina variable inducida.

#include <iostream>
using namespace std;
int main()
{
    int a[1000];
    for (int induced_loop = 1; induced_loop <= 10;
         induced_loop++) {
        int induced_var = induced_loop * 10;
        a[induced_var] = 0;
    }
    return 0;
}

inducida_var toma valores 10,20,30….100.  bucle_inducido toma los valores 1,2,3…10. Por lo tanto, tanto bucle_inducido como var_inducida son variables de inducción de este bucle.

El programa anterior se puede optimizar usando el método de reducción de fuerza , donde tratamos de reemplazar la operación de multiplicación con suma, que es una operación menos costosa.

Código optimizado: 

#include <iostream>
using namespace std;
int main()
{
    int a[1000];
    int induced_var = 0;
    for (int induced_loop = 1; induced_loop <= 10;
         induced_loop++) {
        induced_var += 10;
        a[induced_var] = 0;
    }
    return 0;
}

A veces se vuelve imposible expresar el valor que tiene una variable después de llamar a una función como una función lineal, pero podemos determinar otras propiedades de esa variable usando el análisis simbólico, como la comparación entre dos variables, como se muestra en el siguiente ejemplo. 

#include <iostream>
using namespace std;
int sum() { return 10; }
int main()
{
    int a = sum();
    int b = a + 10;
    int c = a + 11;
    return 0;
}

Usando el análisis simbólico podemos afirmar claramente que el valor de la variable a > b

2. Problema de flujo de datos:

Esto nos ayuda a comprender dónde se deben mantener los valores de las variables y también contar la iteración en un bucle. Esta técnica usa mapas simbólicos, actúa como una función que mapea todas las variables dentro del programa con un valor. Considere el siguiente código 

#include <iostream>
using namespace std;
  
int main()
{
    int gfg = 0; // start of region 1
    for (int outer = 100; outer <= 200;
         outer++) { // start of region 2
        gfg++;
        int temp_outer = gfg * 10;
        int var = 0;
        for (int inner = 10; inner <= 20;
             inner++) { // start of region 3
            int temp_inner = temp_outer + var;
            var++;
        } // end of region 3
    } // end of region 2
} // end of region 1

Mediante el análisis de flujo de datos tratamos de dividir nuestro programa en diferentes regiones. Luego asignamos las variables de nuestro programa a un valor utilizando los mapas simbólicos, analizamos el programa y los reducimos aún más a expresiones afines. También tratamos de mantener las variables de bloque exclusivas. En el ejemplo anterior, vemos que la variable temp_outer se usa en la región 3, en realidad pertenece a la región 2, por lo que intentamos deshacernos de ella después de subestimar su naturaleza a partir del mapeo de símbolos de nuestro programa. Además, tratamos de reducir cualquier tipo de operaciones en la medida de lo posible dentro de nuestro programa. Por lo tanto, el código se puede reducir a:

#include <iostream>
using namespace std;
  
int main()
{
    int gfg = 0; // start of region 1
    int i;
    int j;
    for (int outer = 1; outer <= 100;
         outer++) { // start of region 2
        gfg = i;
        int temp_outer = gfg * 10;
        int var = 0;
        for (int inner = 10; inner <= 20;
             inner++) { // start of region 3
            int temp_inner = 10 * i + j - 1;
            var = j;
        } // end of region 3
    } // end of region 2
} // end of region 1

Intentamos deshacernos del problema del flujo de datos utilizando la función de transferencia de bloques, a la función de entrada que se menciona anteriormente.

3. Análisis simbólico basado en regiones:

El análisis basado en regiones consta de dos partes: paso de abajo hacia arriba y paso de arriba hacia abajo. El pase de abajo hacia arriba ayuda a analizar una región cuando la función de transferencia pasa un mapa simbólico en la entrada y el mapa simbólico de salida en la salida. Mientras que en el paso de arriba hacia abajo, los valores de los mapas de símbolos se pasan al bucle interno de nuestro programa.