Análisis del flujo de datos

Para que el método iterativo sea útil, debe alcanzar un punto fijo. Esto se puede garantizar imponiendo restricciones a la combinación del dominio de valores de los estados, las funciones de transferencia y la operación de unión.

El dominio de valores debe ser un orden parcial con altura finita (es decir, no hay cadenas ascendentes infinitas).${\displaystyle x_{1}}$<${\displaystyle x_{2}}$< ...). La combinación de la función de transferencia y la operación de unión debe ser monótona con respecto a este orden parcial. La monotonicidad garantiza que en cada iteración el valor se mantendrá igual o aumentará, mientras que la altura finita asegura que no puede crecer indefinidamente. Por lo tanto, finalmente llegaremos a una situación donde T(x) = x para todo x, que es el punto fijo.

Es fácil mejorar el algoritmo anterior al observar que el estado de entrada de un bloque no cambia si los estados de salida de sus predecesores permanecen sin cambios. Por lo tanto, introducimos una lista de trabajo : una lista de bloques que aún deben procesarse. Cada vez que cambia el estado de salida de un bloque, añadimos sus sucesores a la lista de trabajo. En cada iteración, se elimina un bloque de la lista de trabajo y se calcula su estado de salida. Si el estado de salida ha cambiado, se añaden los sucesores del bloque a la lista de trabajo. Para mayor eficiencia, un bloque no debe aparecer en la lista de trabajo más de una vez.

El algoritmo se inicia colocando bloques generadores de información en la lista de trabajo. Finaliza cuando la lista de trabajo está vacía.

La eficiencia de la resolución iterativa de ecuaciones de flujo de datos está influenciada por el orden en que se visitan los nodos locales. ^{[ 9 ]} Además, depende de si las ecuaciones de flujo de datos se utilizan para el análisis de flujo de datos hacia adelante o hacia atrás sobre el CFG. Intuitivamente, en un problema de flujo hacia adelante, sería más rápido si todos los predecesores de un bloque se hubieran procesado antes que el bloque mismo, ya que entonces la iteración utilizará la información más reciente. En ausencia de bucles, es posible ordenar los bloques de tal manera que los estados de salida correctos se calculen procesando cada bloque solo una vez.

A continuación, se analizan algunos órdenes de iteración para resolver ecuaciones de flujo de datos (un concepto relacionado con el orden de iteración de una CFG es el recorrido de un árbol ).

• Orden aleatorio : este orden de iteración no tiene en cuenta si las ecuaciones de flujo de datos resuelven un problema de flujo de datos hacia adelante o hacia atrás. Por lo tanto, su rendimiento es relativamente bajo en comparación con órdenes de iteración especializados.
• Iteración en postorden : Este es un orden de iteración típico para problemas de flujo de datos hacia atrás. En la iteración en postorden , un nodo se visita después de que todos sus nodos sucesores hayan sido visitados. Normalmente, la iteración en postorden se implementa con la estrategia de búsqueda en profundidad .
• Iteración en postorden inverso : Este es un orden de iteración típico para problemas de flujo de datos hacia adelante. En la iteración en postorden inverso , un nodo se visita antes que cualquiera de sus nodos sucesores, excepto cuando el sucesor es alcanzado por una arista de retorno. (Tenga en cuenta que la iteración en postorden inverso no es lo mismo que la iteración en preorden ).

El valor inicial de los estados de entrada es importante para obtener resultados correctos y precisos. Si los resultados se utilizan para optimizaciones del compilador, deben proporcionar información conservadora ; es decir, al aplicar la información, el programa no debe cambiar su semántica. La iteración del algoritmo de punto fijo tomará los valores en la dirección del elemento máximo. Por lo tanto, inicializar todos los bloques con el elemento máximo no es útil. Al menos un bloque comienza en un estado con un valor menor que el máximo. Los detalles dependen del problema de flujo de datos. Si el elemento mínimo representa información totalmente conservadora, los resultados pueden utilizarse de forma segura incluso durante la iteración del flujo de datos. Si representa la información más precisa, se debe alcanzar el punto fijo antes de poder aplicar los resultados.

El análisis de definición de alcance calcula, para cada punto del programa, el conjunto de definiciones que potencialmente pueden alcanzar dicho punto.

 si b == 4 entonces  a = 5;  demás  a = 3;  fin si  si a < 4 entonces  ... 

La definición de variable que se alcanza aen la línea 7 es el conjunto de asignaciones a = 5en la línea 2 y a = 3en la línea 4.

El análisis de variables vivas calcula, para cada punto del programa, las variables que podrían leerse posteriormente antes de su siguiente actualización de escritura. El resultado se suele utilizar para la eliminación de código muerto , eliminando las instrucciones que asignan un valor a una variable cuyo valor no se utiliza posteriormente.

El estado inicial de un bloque es el conjunto de variables que están activas al comienzo del mismo. Contiene inicialmente todas las variables activas (contenidas) en el bloque, antes de que se aplique la función de transferencia y se calculen los valores reales contenidos. La función de transferencia de una instrucción se aplica eliminando las variables que se escriben dentro de este bloque (retirándolas del conjunto de variables activas). El estado final de un bloque es el conjunto de variables que están activas al final del bloque y se calcula mediante la unión de los estados iniciales de los bloques sucesores.

Código inicial:

Análisis retrospectivo:

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.

Los ejemplos anteriores son problemas en los que el valor del flujo de datos es un conjunto, por ejemplo, el conjunto de definiciones alcanzables (usando un bit para la posición de una definición en el programa) o el conjunto de variables activas. Estos conjuntos se pueden representar eficientemente como vectores de bits , donde cada bit representa la pertenencia a un conjunto de un elemento en particular. Usando esta representación, las funciones de unión y transferencia se pueden implementar como operaciones lógicas bit a bit. La operación de unión es típicamente la unión o la intersección, implementada mediante la disyunción lógica bit a bit y la conjunción lógica . La función de transferencia para cada bloque se puede descomponer en los llamados conjuntos de generación y eliminación .

Como ejemplo, en el análisis de variables vivas, la operación de unión es la unión. El conjunto de eliminación es el conjunto de variables que se escriben en un bloque, mientras que el conjunto de generación es el conjunto de variables que se leen sin haber sido escritas previamente. Las ecuaciones de flujo de datos se convierten en:

${\displaystyle out_{b}=\bigcup _{s\in succ_{b}}in_{s}}$

${\displaystyle in_{b}=(out_{b}-kill_{b})\cup gen_{b}}$

En operaciones lógicas, esto se lee como

out( b ) = 0 para s en succ( b ) salida( b ) = salida( b ) o entrada( s ) in( b ) = (out( b ) y no kill( b )) o gen( b )

Los problemas de flujo de datos que tienen conjuntos de valores de flujo de datos que pueden representarse como vectores de bits se denominan problemas de vectores de bits , problemas gen-kill o problemas localmente separables . ^{[ 13 ]} Dichos problemas tienen soluciones genéricas de tiempo polinomial. ^{[ 14 ]}

Además de los problemas de definiciones alcanzables y variables vivas mencionados anteriormente, los siguientes problemas son instancias de problemas de vectores de bits: ^{[ 14 ]}

• expresiones disponibles
• expresiones muy ocupadas
• cadenas de definición de uso

Los problemas interprocedimentales, finitos, distributivos, de subconjuntos o problemas IFDS son otra clase de problemas con una solución genérica de tiempo polinomial. ^{[ 13 ] [ 15 ]} Las soluciones a estos problemas proporcionan análisis de flujo de datos sensibles al contexto y al flujo.

Hay varias implementaciones de análisis de flujo de datos basados ​​en IFDS para lenguajes de programación populares, por ejemplo en los marcos Soot ^{[ 16 ]} y WALA ^{[ 17 ]} para análisis de Java.

Todo problema de vector de bits es también un problema IFDS, pero existen varios problemas IFDS importantes que no son problemas de vector de bits, incluidas las variables verdaderamente activas y las variables posiblemente no inicializadas.