En los compiladores , el análisis de variables en vivo (o simplemente análisis de vida ) es un análisis de flujo de datos clásico para calcular las variables que están en vivo en cada punto del programa. Una variable está activa en algún momento si tiene un valor que puede ser necesario en el futuro o, de manera equivalente, si su valor puede leerse antes de la próxima vez que se escriba en la variable.
Ejemplo
Considere el siguiente programa:
b = 3c = 5a = f (b * c)
El conjunto de variables activas entre las líneas 2 y 3 es { b
, c
} porque ambas se usan 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 c
se actualiza más tarde, en la línea 2. El el valor de la variable a
no se utiliza en este código.
Tenga en cuenta que la asignación a a
puede eliminarse porque a
no se usa más adelante, pero no hay información suficiente para justificar la eliminación de toda la línea 3, ya que f
puede tener efectos secundarios (impresión b * c
, tal vez).
Expresión en términos de ecuaciones de flujo de datos
El análisis de la vitalidad es un análisis "al revés". El análisis se realiza en un revés orden, y el flujo de datos del operador confluencia es set unión . En otras palabras, si se aplica el análisis de vivacidad a una función con un número particular de ramas lógicas dentro de ella, el análisis se realiza comenzando desde el final de la función trabajando hacia el principio (por lo tanto, "hacia atrás"), y una variable se considera viva si cualquiera de las ramas que avanzan dentro de la función podría potencialmente (por lo tanto, "puede") necesitar el valor actual de la variable. Esto contrasta con un análisis de "obligación hacia atrás" que, en cambio, impondría esta condición en todas las ramas que avanzan.
Las ecuaciones de flujo de datos utilizadas para un bloque básico dado sy el bloque f de salida en el análisis de variables en vivo son las siguientes:
- : El conjunto de variables que se utilizan en s antes de cualquier asignación.
- : El conjunto de variables a las que se les asigna un valor en s (en muchos libros [se necesita aclaración ] , 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 del flujo de datos):
El estado de un bloque es el conjunto de variables que están activas al comienzo del bloque. Su estado externo es el conjunto de variables que están activas al final del mismo. El estado externo es la unión de los estados internos de los sucesores del bloque. La función de transferencia de una declaración se aplica haciendo que las variables que están escritas estén muertas, luego haciendo que las variables que se leen estén activas.
Segundo ejemplo
// en: {}b1: a = 3; b = 5; d = 4; x = 100; // x nunca se usa más tarde, por lo tanto, no está en el conjunto inicial {a, b, d} si a> b entonces// out: {a, b, d} // unión de todos (in) sucesores de b1 => b2: {a, b} y b3: {b, d} // en: {a, b}b2: c = a + b; d = 2;// fuera: {b, d}// en: {b, d}b3: endif c = 4; return b * d + c;// fuera:{} |
El estado de b3 solo contiene b y d , ya que c se ha escrito. El estado externo de b1 es la unión de los estados internos de b2 y b3. La definición de c en b2 puede eliminarse, ya que c no está activo inmediatamente después de la declaración.
La resolución de las ecuaciones de flujo de datos comienza con la inicialización de todos los estados de entrada y salida en el conjunto vacío. La lista de trabajo se inicializa insertando el punto de salida (b3) en la lista de trabajo (típico del flujo hacia atrás). Su estado calculado difiere del anterior, por lo que sus predecesores b1 y b2 se insertan y el proceso continúa. El progreso se resume en la siguiente tabla.
Procesando | fuera del estado | viejo en el estado | nuevo en el estado | lista de trabajo |
---|---|---|---|---|
b3 | {} | {} | {b, d} | (b1, b2) |
b1 | {b, d} | {} | {} | (b2) |
b2 | {b, d} | {} | {a, b} | (b1) |
b1 | {a, b, d} | {} | {} | () |
Tenga en cuenta que b1 se ingresó en la lista antes de b2, lo que forzó el procesamiento de b1 dos veces (b1 se volvió a ingresar como predecesor de b2). Insertar b2 antes de b1 habría permitido una finalización más temprana.
Inicializar con el conjunto vacío es una inicialización optimista: todas las variables comienzan como muertas. Tenga en cuenta que los estados externos no pueden reducirse de una iteración a la siguiente, aunque el estado externo puede ser más pequeño que el estado interno. Esto se puede ver en el hecho de que después de la primera iteración, el estado externo solo puede cambiar mediante un cambio del estado interno. Dado que el estado comienza como el conjunto vacío, solo puede crecer en iteraciones posteriores.