Análisis de variables en vivo

En los compiladores , el análisis de variables activas (o simplemente análisis de vivacidad ) es un análisis clásico del flujo de datos que permite calcular qué variables están activas en cada punto del programa. Una variable está activa si contiene un valor que podría ser necesario en el futuro, o, de forma equivalente, si su valor podría leerse antes de que se vuelva a escribir en ella.

Considere el siguiente programa:

b = 3 c = 5 a = f(b * c)

El conjunto de variables activas entre las líneas 2 y 3 es { b, c} porque ambas se utilizan en la multiplicación de la línea 3. Pero el conjunto de variables activas después de la línea 1 es solo { b}, ya que la variable cse actualiza más tarde, en la línea 2. El valor de la variable ano se utiliza en este código.

Tenga en cuenta que la asignación a apuede eliminarse ya aque no se usa más adelante, pero no hay suficiente información para justificar la eliminación de toda la línea 3 ya que fpuede tener efectos secundarios (imprimir b * c, tal vez).

El análisis de vivacidad es un análisis de "posibilidad inversa". El análisis se realiza en orden inverso , y el operador de confluencia de flujo de datos es la unión de conjuntos . En otras palabras, al aplicar el análisis de vivacidad a una función con un número determinado de ramas lógicas, el análisis se realiza desde el final de la función hacia el principio (de ahí el término "inverso"), y una variable se considera viva si alguna de las ramas que avanzan dentro de la función podría potencialmente (de ahí el término "puede") necesitar el valor actual de la variable. Esto contrasta con un análisis de "obligación inversa", que impondría esta condición a todas las ramas que avanzan.

Las ecuaciones de flujo de datos utilizadas para un bloque básico dado${\displaystyle s}$y bloque de salida${\displaystyle {\mathit {final}}}$En el análisis de variables en tiempo real se incluyen las siguientes:

${\displaystyle {\mbox{GEN}}[s]}$: El conjunto de variables que se utilizan en s antes de cualquier asignación en el mismo bloque básico.

${\displaystyle {\mbox{KILL}}[s]}$: El conjunto de variables a las que se les asigna un valor en s (en muchos libros que tratan sobre el diseño de compiladores, KILL(s) también se define como el conjunto de variables a las que se les asigna un valor en s antes de cualquier uso , pero esto no cambia la solución de la ecuación de flujo de datos):

${\displaystyle {\mbox{LIVE}}_{\mathrm {in} }[s]={\mbox{GEN}}[s]\cup ({\mbox{LIVE}}_{\mathrm {out} }[s]-{\mbox{KILL}}[s])}$

${\displaystyle {\mbox{LIVE}}_{\mathrm {out} }[{\mathit {final}}]={\emptyset }}$

${\displaystyle {\mbox{LIVE}}_{\mathrm {out} }[s]=\bigcup _{p\in \mathrm {succ} [s]}{\mbox{LIVE}}_{\mathrm {in} }[p]}$

${\displaystyle {\mbox{GEN}}[d:y\leftarrow f(x_{1},\cdots ,x_{n})]=\{x_{1},...,x_{n}\}}$

${\displaystyle {\mbox{KILL}}[d:y\leftarrow f(x_{1},\cdots ,x_{n})]=\{y\}}$

El estado inicial de un bloque es el conjunto de variables que están activas al comienzo del mismo. Su estado final es el conjunto de variables que están activas al final del bloque. El estado final es la unión de los estados iniciales de los bloques sucesores. La función de transferencia de una instrucción se aplica desactivando las variables que se escriben y activando las que se leen.

El estado de entrada de b3 solo contiene b y d , ya que c ha sido escrito. El estado de salida de b1 es la unión de los estados de entrada de b2 y b3. La definición de c en b2 puede eliminarse, ya que c no está activa inmediatamente después de la instrucción.

La resolución de las ecuaciones de flujo de datos comienza con la inicialización de todos los estados de entrada y salida al conjunto vacío. La lista de trabajo se inicializa insertando el punto de salida (b3) en ella (típico para el flujo inverso). Su estado de entrada calculado difiere del anterior, por lo que se insertan sus predecesores b1 y b2 y el proceso continúa. El progreso se resume en la tabla siguiente.

Nótese que b1 se introdujo en la lista antes que b2, lo que obligó a procesar b1 dos veces (b1 se volvió a introducir como predecesor de b2). Si se hubiera insertado b2 antes que b1, se habría podido completar antes.

Inicializar con el conjunto vacío es una inicialización optimista: todas las variables comienzan como inactivas. Cabe destacar que los estados de salida no pueden disminuir de una iteración a la siguiente, aunque el estado de salida puede ser menor que el estado de entrada. Esto se evidencia en que, después de la primera iteración, el estado de salida solo puede cambiar si cambia el estado de entrada. Dado que el estado de entrada comienza como el conjunto vacío, solo puede crecer en iteraciones posteriores.

Aho, Alfred; Lam, Monica; Sethi, Ravi; Ullman, Jeffrey (2007). Compiladores: Principios, técnicas y herramientas (2.ª  ed.). pág.  608.