Análisis de flujo de datos
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 de computadora . El gráfico de flujo de control (CFG) de un programa se utiliza para determinar las partes de un programa a las que podría propagarse 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 llegar a las 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 de la entrada localmente en cada nodo hasta que todo el sistema se estabilice, es decir , alcanza 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 del flujo de datos es el proceso de recopilar información sobre la forma en que se utilizan las variables, definidas 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 ahí es fácil calcular la información en los puntos del bloque básico. En el análisis de flujo directo, 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 función de los estados de salida de sus predecesores. Esto produce un conjunto de ecuaciones de flujo de datos:
En este, es la función de transferencia del bloque . Funciona en el estado de entrada , produciendo el estado de salida . La operación de unión combina los estados de salida de los predecesores de , produciendo 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 usar para derivar propiedades del programa en los límites del bloque. La función de transferencia de cada declaració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 produce el estado de entrada, y la operación de unión trabaja en los estados de entrada de los sucesores para producir el estado de salida.