Análisis de flujo de datos

Método de análisis de variables en software.

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 aquellas 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 análisis de flujo de datos es llegar a definiciones .

Una forma sencilla de realizar análisis de flujo de datos de programas es establecer 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 , llega a 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 Naval de Postgrado . ^{[1] [2] [3] [4]}

Principios básicos

El análisis de flujo de datos es el proceso de recopilar 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. Generalmente, 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:

Para cada bloque b:

${\displaystyle out_{b}=trans_{b}(in_{b})}$

${\displaystyle in_{b}=join_{p\in pred_{b}}(out_{p})}$

En esto, está 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 , generando el estado de entrada de . ${\displaystyle trans_{b}}$ ${\displaystyle b}$ ${\displaystyle in_{b}}$ ${\displaystyle out_{b}}$ ${\displaystyle join}$ ${\displaystyle p\in pred_{b}}$ ${\displaystyle b}$ ${\displaystyle b}$

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 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 funciona en los estados de entrada de los sucesores para producir el estado de salida.

El punto de entrada (en el flujo directo) juega un papel importante: como no tiene predecesores, su estado de entrada está bien definido al inicio 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), resolver las ecuaciones es sencillo. Luego, el gráfico de flujo de control se puede ordenar topológicamente ; ejecutándose en el orden de este tipo, los estados de entrada se pueden calcular al comienzo de cada bloque, ya que todos los predecesores de ese bloque ya han sido procesados, 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.

Un algoritmo iterativo

La forma más común de resolver las ecuaciones de flujo de datos es mediante el uso de un algoritmo iterativo. Comienza con una aproximación del estado interno de cada bloque. Luego, los estados externos se calculan aplicando las funciones de transferencia a los estados internos. A partir de estos, los estados internos se actualizan aplicando las operaciones de unión. Los dos últimos pasos se repiten hasta que alcanzamos el llamado punto fijo : la situación en la que los estados internos (y, en consecuencia, los estados externos) no cambian.

Un algoritmo básico para resolver ecuaciones de flujo de datos es el algoritmo iterativo de operación por turnos :

para i ← 1 a N

inicializar el nodo i

mientras ( los conjuntos aún están cambiando )

para i ← 1 a N

recalcular conjuntos en el nodo i

Convergencia

Para que sea utilizable, el enfoque iterativo debería llegar a un punto fijo. Esto puede garantizarse imponiendo restricciones a la combinación del dominio de valor de los estados, las funciones de transferencia y la operación de unión.

El dominio del valor debe ser un orden parcial con 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 monotonicidad garantiza que en cada iteración el valor permanecerá igual o aumentará, mientras que la altura finita garantiza que no pueda crecer indefinidamente. Así, finalmente llegaremos a una situación en la que T(x) = x para todo x, que es el punto fijo. ${\displaystyle x_{1}}$ ${\displaystyle x_{2}}$

El enfoque de la lista de trabajo

Es fácil mejorar el algoritmo anterior al observar que el estado interno de un bloque no cambiará si los estados externos de sus predecesores no cambian. Por lo tanto, presentamos una lista de trabajo : una lista de bloques que aún deben procesarse. Siempre que cambia el estado exterior 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 exterior. Si el estado exterior 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. Termina cuando la lista de trabajo está vacía.

Realizar pedidos

La eficiencia de resolver iterativamente ecuaciones de flujo de datos está influenciada por el orden en 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 directo, 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 externos correctos se calculen procesando cada bloque sólo 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 ).

• 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, el rendimiento es relativamente pobre en comparación con las órdenes de iteración especializadas.
• Postorder : este es un orden de iteración típico para problemas de flujo de datos hacia atrás. En la iteración posterior al pedido , se visita un nodo después de que se hayan visitado todos sus nodos sucesores. Normalmente, la iteración posterior al pedido se implementa con la estrategia de profundidad primero .
• Postorder inverso : este es un orden de iteración típico para problemas de flujo de datos directos. En la iteración de orden posterior inverso , se visita un nodo antes de que cualquiera de sus nodos sucesores haya sido visitado, excepto cuando el sucesor es alcanzado por un borde posterior. (Tenga en cuenta que el pedido posterior inverso no es lo mismo que el pedido anticipado ).

Inicialización

El valor inicial de los estados internos es importante para obtener resultados correctos y precisos. Si los resultados se utilizan para optimizaciones del compilador, deberían proporcionar información conservadora , es decir, al aplicar la información, el programa no debería 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 del 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.

Ejemplos

Los siguientes son ejemplos de propiedades de programas de computadora que pueden calcularse mediante análisis de flujo de datos. Tenga en cuenta que las propiedades calculadas mediante el análisis de flujo de datos suelen ser sólo aproximaciones de las propiedades reales. Esto se debe a que el análisis del flujo de datos opera en 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 de flujo de datos suele diseñarse para calcular una aproximación superior respectivamente inferior de las propiedades reales del programa.

Análisis hacia adelante

El análisis de definición de alcance calcula para cada punto del programa el conjunto de definiciones que potencialmente pueden llegar a ese punto del programa.

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

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

Análisis hacia atrás

El análisis de variables en vivo calcula para cada punto del programa las variables que potencialmente pueden leerse después antes de su próxima actualización de escritura. El resultado suele utilizarse mediante la eliminación de código inactivo para eliminar declaraciones que se asignan a una variable cuyo valor no se utiliza posteriormente.

El estado interno de un bloque es el conjunto de variables que están activas al comienzo del mismo. Inicialmente contiene todas las variables vivas (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 externo 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 internos de los sucesores del bloque.

Código inicial:

Análisis hacia atrás:

El estado interno de b3 solo contiene b y d , ya que c ha sido 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 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 internos y externos 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 interno 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 ingresó en la lista antes que b2, lo que obligó a procesar 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 por el hecho de que después de la primera iteración el estado exterior sólo puede cambiar mediante un cambio del estado interior. Dado que el estado interno comienza como un conjunto vacío, solo puede crecer en iteraciones posteriores.

Otros enfoques

Varios compiladores modernos utilizan la forma estática de asignación única como método para el análisis de dependencias 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 una interpretación abstracta del programa y mantiene un conjunto funcional 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 se repite 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 cohesivas del código fuente que implementan funcionalidades de un sistema (p. ej., características , requisitos o casos de uso ). ^[8]

Clases especiales de problemas.

Existe una variedad de clases especiales de problemas de flujo de datos que tienen soluciones eficientes o generales.

Problemas de vectores de bits

Los ejemplos anteriores son problemas en los que el valor del flujo de datos es un conjunto, por ejemplo, el conjunto de definiciones alcanzadas (usando un bit para una posición de definición en el programa), o el conjunto de variables activas. Estos conjuntos se pueden representar eficientemente como vectores de bits , en los que cada bit representa la pertenencia al conjunto de un elemento 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 suele ser unión o intersección, implementada mediante lógica bit a bit o y lógica y . La función de transferencia de cada bloque se puede descomponer en los llamados conjuntos gen y kill .

Por ejemplo, en el análisis de variables en vivo, la operación de unión es unión. El kill set es el conjunto de variables que se escriben en un bloque, mientras que el gen set es el conjunto de variables que se leen sin escribirse primero. 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  in succ( b ) fuera( b ) = fuera( b ) o dentro( s )in( b ) = (out( b ) y no matar( 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 las definiciones de alcance y los problemas de variables activas mencionados anteriormente, los siguientes problemas son ejemplos de problemas de vectores de bits: ^[10]

• Expresiones disponibles
• Expresiones muy ocupadas.
• Cadenas de definición de uso

Problemas de IFDS

Los problemas interprocedimentales, finitos, distributivos, de subconjuntos o problemas IFDS son otra clase de problemas con una solución genérica de 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 análisis Java.

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

Sensibilidades

El análisis de flujo de datos suele ser insensible a la ruta, aunque es posible definir ecuaciones de flujo de datos que produzcan un análisis sensible a la ruta.

• Un análisis sensible al flujo tiene en cuenta el orden de las declaraciones en un programa. Por ejemplo, un análisis de alias de puntero insensible al flujo puede determinar "las variables xey pueden hacer referencia a la misma ubicación", mientras que un análisis sensible al flujo puede determinar "después de la declaración 20, las variables xey pueden hacer referencia a la misma ubicación".
• Un análisis sensible a la ruta calcula diferentes piezas de información de análisis dependiendo de los predicados en las instrucciones de bifurcación condicional. Por ejemplo, si una rama contiene una condición x>0, entonces en la ruta de acceso directo , el análisis asumiría que eso x<=0y en el objetivo de la rama asumiría que efectivamente x>0se cumple.
• Un análisis sensible al contexto es un análisis interprocedimental que considera el contexto de llamada al analizar el objetivo de una llamada de función. En particular, utilizando información de contexto se puede volver al sitio de llamada original, mientras que sin esa información, la información del análisis debe propagarse a todos los sitios de llamada posibles, perdiendo potencialmente precisión.

Lista de análisis de flujo de datos

• Llegando a definiciones
• Análisis de vida
• Análisis de asignación definitiva
• Expresión disponible
• Propagación constante

Ver también

• Interpretación abstracta
• Análisis de flujo de control
• XLT86

Referencias

1. Kildall, Gary Arlen (mayo de 1972). Optimización de expresiones globales durante la compilación (tesis doctoral). Seattle, Washington, EE.UU.: Universidad de Washington , Grupo de Ciencias de la Computación. Tesis N° 20506, Informe Técnico N° 72-06-02.
2. Kildall, Gary Arlen (1 de octubre de 1973). "Un enfoque unificado para la optimización de programas globales" (PDF) . Actas del primer simposio anual ACM SIGACT-SIGPLAN sobre principios de lenguajes de programación (POPL) . POPL '73. Boston, Massachusetts, Estados Unidos: 194–206. doi :10.1145/512927.512945. hdl :10945/42162. S2CID  10219496. Archivado (PDF) desde el original el 29 de junio de 2017 . Consultado el 20 de noviembre de 2006 .([1])
3. Rüthing, Oliver; Knoop, Jens; Steffen, Bernhard (31 de julio de 2003) [1999]. "Optimización: detección de igualdades de variables, combinando eficiencia con precisión". En Cortesi, Agostino; Filé, Gilberto (eds.). Análisis estático: Sexto Simposio Internacional, SAS'99, Venecia, Italia, 22 al 24 de septiembre de 1999, Actas . Apuntes de conferencias sobre informática. vol. 1694 (edición ilustrada). Saltador. págs. 232-247 [233]. ISBN 9783540664598. ISSN  0302-9743.
4. Huitt, Robert; Eubanks, Gordon ; Rolander, Thomas "Tom" Alan ; Leyes, David; Michel, Howard E.; Halla, Brian; Wharton, John Harrison ; Berg, Brian; Su, Weilian; Kildall, Scott ; Kampe, Bill (25 de abril de 2014). Leyes, David (ed.). "El legado de Gary Kildall: la dedicación al hito de CP/M IEEE" (PDF) (transcripción del vídeo). Pacific Grove, California, Estados Unidos: Museo de Historia de la Computación . Número de referencia CHM: X7170.2014 . Consultado el 19 de enero de 2020 . […] Eubanks : […] Gary […] era un inventor, tenía inventiva, hacía cosas. Su doctorado. La tesis demostró que el análisis del flujo global converge. […] Esta es una idea fundamental en informática. […] Una vez tomé un […] curso de verano con un tipo llamado Dhamdhere […] hablaron sobre optimización durante aproximadamente 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)
5. Cooper, Keith D .; Harvey, Timothy J.; Kennedy, Ken (26 de marzo de 2004) [noviembre de 2002]. "Análisis iterativo de flujo de datos, revisado" (PDF) . PLDI 2003 . ACM . TR04-432 . Consultado el 1 de julio de 2017 .^{[ enlace muerto permanente ]}
6. "Asignación única estática (con ejemplos relevantes)". Geeks para Geeks . 2021-10-02 . Consultado el 16 de agosto de 2023 .
7. Mohnen, Markus (2002). "Un gráfico: enfoque libre de los datos: análisis de flujo". Construcción del compilador . Apuntes de conferencias sobre informática. vol. 2304, págs. 185-213. doi :10.1007/3-540-45937-5_6. ISBN 978-3-540-43369-9.
8. Kuang, Hongyu; Mäder, Patrick; Hu, Hao; Ghabi, Achraf; Huang, Li Guo; Lü, Jian; Egyed, Alejandro (1 de noviembre de 2015). "¿Pueden las dependencias de datos de métodos respaldar la evaluación de la trazabilidad entre los requisitos y el código fuente?". Revista de software: evolución y proceso . 27 (11): 838–866. doi :10.1002/smr.1736. ISSN  2047-7481. S2CID  39846438.
9. representantes ab, Thomas; Horwitz, Susan; Sagiv, Mooly (1995). "Análisis preciso del flujo de datos entre procedimientos mediante accesibilidad gráfica". Actas del 22º simposio ACM SIGPLAN-SIGACT sobre principios de lenguajes de programación - POPL '95 . Nueva York, Nueva York, Estados Unidos: ACM Press . págs. 1, 49–61. doi :10.1145/199448.199462. ISBN 0-89791692-1. S2CID  5955667.
10. Knoop, Jens; Steffen, Bernhard ; Vollmer, Jürgen (1 de mayo de 1996). "Paralelismo gratis: análisis de vectores de bits eficientes y óptimos para programas paralelos". Transacciones ACM sobre lenguajes y sistemas de programación . 18 (3): 268–299. doi : 10.1145/229542.229545 . ISSN  0164-0925. S2CID  14123780.
11. Naeem, Nomair A.; Lhoták, Ondřej; Rodríguez, Jonathan (2010), "Extensiones prácticas del algoritmo IFDS", Construcción del compilador , Lecture Notes in Computer Science, vol. 6011, Berlín / Heidelberg, Alemania: Springer Verlag , págs. 124-144, doi : 10.1007/978-3-642-11970-5_8 , ISBN 978-3-64211969-9
12. Bodden, Eric (2012). "Análisis de flujo de datos entre procedimientos con IFDS/IDE y Soot". Actas del taller internacional ACM SIGPLAN sobre el estado del arte en el análisis de programas Java . Nueva York, Nueva York, Estados Unidos: ACM Press . págs. 3–8. doi :10.1145/2259051.2259052. ISBN 978-1-45031490-9. S2CID  3020481.
13. Rapoport, Mariana; Lhoták, Ondřej; Consejo, Frank (2015). "Análisis preciso del flujo de datos en presencia de llamadas a métodos correlacionados" . Simposio Internacional de Análisis Estático. Apuntes de conferencias sobre informática. vol. 9291. Berlín/Heidelberg, Alemania: Springer Verlag . págs. 54–71. doi :10.1007/978-3-662-48288-9_4. ISBN 978-3-66248287-2.

Otras lecturas

• Cooper, Keith D .; Torczon, Linda (2003) [1 de enero de 2002]. Ingeniería de un compilador . Morgan Kaufman . ISBN 978-1-55860-698-2.
• Muchnick, Steven Stanley (1997). Diseño e implementación de compiladores avanzados . Editores Morgan Kaufmann . ISBN 978-1-55860-320-2.
• Hecht, Matthew S. (3 de mayo de 1977). Análisis de flujo de programas informáticos . Serie de lenguajes de programación. vol. 5. Elsevier North-Holland Inc. ISBN 978-0-44400210-5.
• Khedker, Uday P.; Sanyal, Amitabha; Karkare, Bageshri (2009). Análisis de flujo de datos: teoría y práctica. Prensa CRC ( Grupo Taylor y Francis ).
• Nielson, Fleming; Nielson, Hanne Riis; Hankin, Chris (2005). Principios del análisis de programas . Springer Ciencia + Medios comerciales .