El análisis de flujo de datos es una técnica para recopilar información sobre el posible conjunto de valores calculados en varios puntos de un programa informático . El gráfico de flujo de control (GFC) de un programa se utiliza para determinar las partes de un programa a las que se podría propagar un valor particular asignado a una variable. Los compiladores suelen utilizar la información recopilada al optimizar un programa. Un ejemplo canónico de un análisis de flujo de datos es la obtención de definiciones .
Una forma sencilla de realizar análisis de flujo de datos de programas es configurar ecuaciones de flujo de datos para cada nodo del gráfico de flujo de control y resolverlas calculando repetidamente la salida a partir de la entrada localmente en cada nodo hasta que todo el sistema se estabilice, es decir, alcance un punto fijo .Este enfoque general, también conocido como método de Kildall , fue desarrollado por Gary Kildall mientras enseñaba en la Escuela de Postgrado Naval . [1] [2] [3] [4]
El análisis de flujo de datos es el proceso de recopilación de información sobre la forma en que se definen y utilizan las variables en el programa. Intenta obtener información particular en cada punto de un procedimiento. Por lo general, es suficiente obtener esta información en los límites de los bloques básicos , ya que a partir de eso es fácil calcular la información en los puntos del bloque básico. En el análisis de flujo hacia adelante, el estado de salida de un bloque es una función del estado de entrada del bloque. Esta función es la composición de los efectos de las declaraciones en el bloque. El estado de entrada de un bloque es una función de los estados de salida de sus predecesores. Esto produce un conjunto de ecuaciones de flujo de datos:
Para cada bloque b:
En este caso, se trata de la función de transferencia del bloque . Actúa sobre el estado de entrada , lo que genera el estado de salida . La operación de unión combina los estados de salida de los predecesores de , lo que genera el estado de entrada de .
Después de resolver este conjunto de ecuaciones, los estados de entrada y/o salida de los bloques se pueden utilizar para derivar propiedades del programa en los límites de los bloques. La función de transferencia de cada instrucción por separado se puede aplicar para obtener información en un punto dentro de un bloque básico.
Cada tipo particular de análisis de flujo de datos tiene su propia función de transferencia y operación de unión específicas. Algunos problemas de flujo de datos requieren un análisis de flujo inverso. Esto sigue el mismo plan, excepto que la función de transferencia se aplica al estado de salida que genera el estado de entrada, y la operación de unión actúa sobre los estados de entrada de los sucesores para generar el estado de salida.
El punto de entrada (en el flujo hacia adelante) juega un papel importante: dado que no tiene predecesores, su estado de entrada está bien definido al comienzo del análisis. Por ejemplo, el conjunto de variables locales con valores conocidos está vacío. Si el gráfico de flujo de control no contiene ciclos (no hubo bucles explícitos o implícitos en el procedimiento), la resolución de las ecuaciones es sencilla. El gráfico de flujo de control se puede ordenar topológicamente ; al ejecutarse en el orden de esta ordenación, los estados de entrada se pueden calcular al comienzo de cada bloque, ya que todos los predecesores de ese bloque ya se han procesado, por lo que sus estados de salida están disponibles. Si el gráfico de flujo de control contiene ciclos, se requiere un algoritmo más avanzado.
La forma más común de resolver las ecuaciones de flujo de datos es mediante un algoritmo iterativo. Comienza con una aproximación del estado de entrada de cada bloque. Luego, se calculan los estados de salida aplicando las funciones de transferencia a los estados de entrada. A partir de estos, los estados de entrada se actualizan aplicando las operaciones de unión. Los dos últimos pasos se repiten hasta llegar al denominado punto fijo : la situación en la que los estados de entrada (y, en consecuencia, los estados de salida) no cambian.
Un algoritmo básico para resolver ecuaciones de flujo de datos es el algoritmo iterativo round-robin :
Para que el método iterativo sea utilizable, debería 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 una altura finita (es decir, no hay cadenas ascendentes infinitas < < ...). 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 monotonía garantiza que en cada iteración el valor permanecerá igual o aumentará, mientras que la altura finita garantiza que no puede crecer indefinidamente. Por lo tanto, finalmente llegaremos a una situación en la que T(x) = x para todo x, que es el punto fijo.
Es fácil mejorar el algoritmo anterior si se observa que el estado de un bloque no cambiará si los estados fuera de sus predecesores no cambian. Por lo tanto, introducimos una lista de trabajo : una lista de bloques que aún necesitan procesarse. Siempre que cambia el estado fuera de un bloque, agregamos sus sucesores a la lista de trabajo. En cada iteración, se elimina un bloque de la lista de trabajo. Se calcula su estado fuera de estado. Si el estado fuera de estado cambió, los sucesores del bloque se agregan a la lista de trabajo. Para mayor eficiencia, un bloque no debe estar 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 y 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 el que se visitan los nodos locales. [5] 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 han procesado antes del 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 un CFG es el recorrido de un árbol ).
El valor inicial de los estados 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 la semántica. La iteración del algoritmo de punto fijo tomará los valores en la dirección del elemento máximo. Por lo tanto, no es útil inicializar todos los bloques con el elemento máximo. 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 se pueden utilizar 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 que se puedan aplicar los resultados.
Los siguientes son ejemplos de propiedades de programas informáticos que se pueden calcular mediante el análisis del flujo de datos. Tenga en cuenta que las propiedades calculadas mediante el análisis del flujo de datos suelen ser solo aproximaciones de las propiedades reales. Esto se debe a que el análisis del flujo de datos opera sobre la estructura sintáctica del CFG sin simular el flujo de control exacto del programa. Sin embargo, para que siga siendo útil en la práctica, un algoritmo de análisis del flujo de datos suele estar diseñado para calcular una aproximación superior o inferior de las propiedades reales del programa.
El análisis de definición de alcance calcula para cada punto del programa el conjunto de definiciones que potencialmente pueden alcanzar este punto del programa.
si b == 4 entonces a = 5; demás a = 3; fin si Si a < 4 entonces ...La definición de alcance de la variable 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 activas calcula para cada punto del programa las variables que pueden ser leídas potencialmente más adelante, antes de su próxima actualización de escritura. El resultado se utiliza normalmente en la eliminación de código muerto para eliminar instrucciones que asignan valores a una variable cuyo valor no se utiliza más adelante.
El estado de entrada de un bloque es el conjunto de variables que están activas al comienzo del mismo. Inicialmente, contiene todas las variables activas (contenidas) en el bloque, antes de que se aplique la función de transferencia y se calculen los valores contenidos reales. La función de transferencia de una declaración se aplica eliminando las variables que están escritas dentro de este bloque (eliminándolas del conjunto de variables activas). El estado de salida 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 de entrada de los sucesores del bloque.
Código inicial:
Análisis hacia atrás:
El estado de entrada de b3 solo contiene b y d , ya que c ya se escribió. 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 se puede eliminar, 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 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 siguiente tabla.
Tenga en cuenta 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). La inserción de b2 antes de b1 habría permitido completarlo antes.
Inicializar con el conjunto vacío es una inicialización optimista: todas las variables comienzan como inactivas. Nótese 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 interno comienza como el conjunto vacío, solo puede crecer en iteraciones posteriores.
Varios compiladores modernos utilizan la forma estática de asignación única como método para el análisis de dependencias de variables. [6]
En 2002, Markus Mohnen describió un nuevo método de análisis de flujo de datos que no requiere la construcción explícita de un gráfico de flujo de datos, [7] sino que se basa en la interpretación abstracta del programa y mantiene un conjunto de trabajo de contadores de programa. En cada rama condicional, ambos objetivos se agregan al conjunto de trabajo. Cada ruta se sigue para tantas instrucciones como sea posible (hasta el final del programa o hasta que haya completado un bucle sin cambios) y luego se elimina del conjunto y se recupera el siguiente contador de programa.
Se ha demostrado que una combinación de análisis de flujo de control y análisis de flujo de datos es útil y complementaria para identificar regiones de código fuente cohesivas que implementan funcionalidades de un sistema (por ejemplo, características , requisitos o casos de uso ). [8]
Hay una variedad de clases especiales de problemas de flujo de datos que tienen soluciones eficientes o generales.
Los ejemplos anteriores son problemas en los que el valor del flujo de datos es un conjunto, por ejemplo, el conjunto de definiciones de alcance (utilizando un bit para una posición de definición en el programa) o el conjunto de variables activas. Estos conjuntos se pueden representar de manera eficiente como vectores de bits , en los que cada bit representa la pertenencia al conjunto de un elemento particular. Utilizando esta representación, las funciones de unión y transferencia se pueden implementar como operaciones lógicas a nivel de bits. La operación de unión es típicamente unión o intersección, implementada por operaciones lógicas a nivel de bits o y operaciones lógicas y . La función de transferencia para cada bloque se puede descomponer en los denominados conjuntos gen y kill .
Por ejemplo, en el análisis de variables en vivo, la operación de unión es 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 escribirse primero. Las ecuaciones de flujo de datos se convierten en
En operaciones lógicas, esto se lee como
out( b ) = 0 para s en succ( b ) fuera( b ) = fuera( b ) o dentro( 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 . [9] Estos problemas tienen soluciones genéricas en tiempo polinomial. [10]
Además de los problemas de definiciones y variables en vivo mencionados anteriormente, los siguientes problemas son ejemplos de problemas de vectores de bits: [10]
Los problemas interprocedimentales, finitos, distributivos, de subconjuntos o problemas IFDS son otra clase de problemas con una solución genérica en tiempo polinomial. [9] [11] Las soluciones a estos problemas proporcionan análisis de flujo de datos sensibles al contexto y al flujo.
Existen varias implementaciones de análisis de flujo de datos basados en IFDS para lenguajes de programación populares, por ejemplo, en los marcos Soot [12] y WALA [13] para el análisis de Java.
Cada problema de vector de bits es también un problema de IFDS, pero hay varios problemas de IFDS importantes que no son problemas de vector de bits, incluidas variables verdaderamente activas y posiblemente variables no inicializadas.
El análisis del flujo de datos generalmente no tiene en cuenta las rutas, aunque es posible definir ecuaciones de flujo de datos que produzcan un análisis sensible a las rutas.
x>0, entonces en la ruta de transición , el análisis asumiría que x<=0y en el destino de la bifurcación asumiría que efectivamente x>0se cumple.[…]
Eubanks
: […]
Gary
[…] era un inventor, era inventivo, hacía cosas. Su tesis doctoral demostró que el análisis de flujo global converge. […] Esta es una idea fundamental en la informática. […] Una vez tomé un […] curso de verano con un tipo llamado Dhamdhere […] Hablaron sobre optimización durante una semana y luego pusieron una diapositiva y dijeron: “El método de Kildall”, esta es la verdadera historia. […] Eso es algo en lo que nadie piensa nunca. […][2][3] (33 páginas)