stringtranslate.com

Gráfico de flujo de control

Algunos ejemplos de CFG:
(a) un if-then-else
(b) un bucle while
(c) un bucle natural con dos salidas, p. ej. while con un if...break en el medio; no estructurado pero reducible
(d) un CFG irreducible: un bucle con dos puntos de entrada, p. ej. goto en un bucle while o for
Un gráfico de flujo de control utilizado por el compilador Rust para realizar la generación de código.

En informática , un gráfico de flujo de control ( GFC ) es una representación , mediante notación gráfica , de todos los caminos que se pueden recorrer a través de un programa durante su ejecución . El gráfico de flujo de control fue descubierto por Frances E. Allen , [1] quien notó que Reese T. Prosser había usado matrices de conectividad booleanas para el análisis de flujo anteriormente. [2]

El CFG es esencial para muchas optimizaciones del compilador y herramientas de análisis estático .

Definición

En un gráfico de flujo de control, cada nodo del gráfico representa un bloque básico , es decir, una secuencia de código en línea recta con un único punto de entrada y un único punto de salida, donde no se producen ramificaciones ni saltos dentro del bloque. Los bloques básicos comienzan con objetivos de salto y terminan con saltos o instrucciones de ramificación. Los bordes dirigidos se utilizan para representar saltos en el flujo de control . En la mayoría de las presentaciones, hay dos bloques especialmente designados: el bloque de entrada , a través del cual el control ingresa al gráfico de flujo, y el bloque de salida , a través del cual sale todo el flujo de control. [3]

Por su procedimiento de construcción, en un CFG, cada arista A→B tiene la propiedad de que:

grado de salida (A) > 1 o grado de entrada (B) > 1 (o ambos). [4]

El CFG puede así obtenerse, al menos conceptualmente, partiendo del gráfico de flujo (completo) del programa (es decir, el gráfico en el que cada nodo representa una instrucción individual) y realizando una contracción de arista para cada arista que falsifique el predicado anterior, es decir, contrayendo cada arista cuyo origen tenga una única salida y cuyo destino tenga una única entrada. Este algoritmo basado en la contracción no tiene importancia práctica, excepto como ayuda de visualización para comprender la construcción del CFG, porque el CFG puede construirse de manera más eficiente directamente desde el programa escaneándolo en busca de bloques básicos . [4]

Ejemplo

Considere el siguiente fragmento de código:

0: (A) t0 = núm_lectura1: (A) si t0 mod 2 == 02: (B) imprimir t0 + " es par".3: (B) ir al 54: (C) imprimir t0 + " es impar".5: (D) finalizar programa

En el ejemplo anterior, tenemos 4 bloques básicos: A de 0 a 1, B de 2 a 3, C en 4 y D en 5. En particular, en este caso, A es el "bloque de entrada", D el "bloque de salida" y las líneas 4 y 5 son objetivos de salto. Un grafo para este fragmento tiene aristas de A a B, A a C, B a D y C a D.

Accesibilidad

La alcanzabilidad es una propiedad gráfica útil en la optimización.

Si un subgráfico no está conectado desde el subgráfico que contiene el bloque de entrada, ese subgráfico es inalcanzable durante cualquier ejecución, y también lo es el código ; en condiciones normales, se puede eliminar de forma segura.

Si el bloque de salida no es accesible desde el bloque de entrada, puede existir un bucle infinito . No todos los bucles infinitos son detectables, consulte el problema de detención . También puede existir una orden de detención.

Son posibles códigos inalcanzables y bucles infinitos incluso si el programador no los codifica explícitamente: optimizaciones como la propagación constante y el plegado constante seguido de subprocesos de salto pueden colapsar múltiples bloques básicos en uno, hacer que se eliminen los bordes de un CFG, etc., posiblemente desconectando así partes del gráfico.

Relación de dominación

Un bloque M domina a un bloque N si cada camino desde la entrada que llega al bloque N tiene que pasar por el bloque M. El bloque de entrada domina a todos los bloques.

En la dirección inversa, el bloque M posdomina al bloque N si cada camino desde N hasta la salida debe pasar por el bloque M. El bloque de salida posdomina a todos los bloques.

Se dice que un bloque M domina inmediatamente al bloque N si M domina a N, y no hay ningún bloque P intermedio tal que M domine a P y P domine a N. En otras palabras, M es el último dominador en todos los caminos desde la entrada a N. Cada bloque tiene un dominador inmediato único.

De manera similar, existe una noción de postdominador inmediato , análoga a dominador inmediato .

El árbol de dominadores es una estructura de datos auxiliar que representa las relaciones de dominadores. Existe un arco desde el bloque M al bloque N si M es un dominador inmediato de N. Este gráfico es un árbol, ya que cada bloque tiene un dominador inmediato único. Este árbol tiene su raíz en el bloque de entrada. El árbol de dominadores se puede calcular de manera eficiente utilizando el algoritmo de Lengauer-Tarjan .

Un árbol postdominador es análogo al árbol dominador . Este árbol tiene su raíz en el bloque de salida.

Bordes especiales

Un borde posterior es un borde que apunta a un bloque que ya se ha encontrado durante un recorrido en profundidad ( DFS ) del gráfico. Los bordes posteriores son típicos de los bucles.

Una arista crítica es una arista que no es la única que sale de su bloque de origen ni la única que entra en su bloque de destino. Estas aristas deben dividirse : se debe crear un nuevo bloque en el medio de la arista para poder insertar cálculos en la arista sin afectar a ninguna otra arista.

Una arista anormal es una arista cuyo destino es desconocido. Las construcciones de manejo de excepciones pueden producirlas. Estas aristas tienden a inhibir la optimización.

Una arista imposible (también conocida como arista falsa ) es una arista que se ha agregado al gráfico únicamente para preservar la propiedad de que el bloque de salida domina todos los bloques. Nunca se puede atravesar.

Gestión de bucles

Un encabezado de bucle (a veces llamado punto de entrada del bucle) es un dominador que es el objetivo de un borde posterior que forma un bucle. El encabezado de bucle domina todos los bloques en el cuerpo del bucle. Un bloque puede ser un encabezado de bucle para más de un bucle. Un bucle puede tener múltiples puntos de entrada, en cuyo caso no tiene "encabezado de bucle".

Supongamos que el bloque M es un dominador con varios bordes entrantes, algunos de los cuales son bordes traseros (por lo que M es un encabezado de bucle). Es ventajoso realizar varios pases de optimización para dividir M en dos bloques M pre y M loop . El contenido de M y los bordes traseros se mueven a M loop , el resto de los bordes se mueven para apuntar a M pre y se inserta un nuevo borde de M pre a M loop (de modo que M pre es el dominador inmediato de M loop ). Al principio, M pre estaría vacío, pero los pases como el movimiento de código invariante de bucle podrían rellenarlo. M pre se llama preencabezado de bucle , y M loop sería el encabezado de bucle.

Reducibilidad

Un CFG reducible es uno con aristas que se pueden dividir en dos conjuntos disjuntos: aristas delanteras y aristas traseras, de modo que: [5]

Los lenguajes de programación estructurada suelen estar diseñados de forma que todos los gráficos de función que producen sean reducibles, y las instrucciones de programación estructurada comunes, como IF, FOR, WHILE, BREAK y CONTINUE, producen gráficos reducibles. Para producir gráficos irreducibles, se necesitan instrucciones como GOTO . Algunas optimizaciones del compilador también pueden producir gráficos irreducibles.

Conectividad de bucle

La conectividad de bucle de un CFG se define con respecto a un árbol de búsqueda en profundidad (DFST) determinado del CFG. Este DFST debe tener su raíz en el nodo de inicio y cubrir todos los nodos del CFG.

Los bordes en el CFG que van desde un nodo a uno de sus ancestros DFST (incluido él mismo) se denominan bordes posteriores.

La conectividad de bucle es el mayor número de aristas posteriores que se encuentran en cualquier camino sin ciclos del CFG. En un CFG reducible, la conectividad de bucle es independiente de la DFST elegida. [6] [7]

La conectividad de bucle se ha utilizado para razonar sobre la complejidad temporal del análisis del flujo de datos . [6]

Gráfico de flujo de control interprocedimental

Mientras que los gráficos de flujo de control representan el flujo de control de un solo procedimiento, los gráficos de flujo de control entre procedimientos representan el flujo de control de programas completos. [8]

Véase también

Referencias

  1. ^ Frances E. Allen (julio de 1970). "Análisis de flujo de control". Avisos SIGPLAN . 5 (7): 1–19. doi :10.1145/390013.808479.
  2. ^ Reese T. Prosser (1959). "Aplicaciones de matrices booleanas al análisis de diagramas de flujo". Documentos presentados en la conferencia informática conjunta IRE-AIEE-ACM del este del 1 al 3 de diciembre de 1959. págs. 133–138. doi :10.1145/1460299.1460314.
  3. ^ Yousefi, Javad (2015). "Enmascaramiento de errores de flujo de control de sucesores erróneos empleando redundancia de datos". 2015 5.ª Conferencia internacional sobre ingeniería informática y del conocimiento (ICCKE). IEEE. págs. 201–205. doi :10.1109/ICCKE.2015.7365827. ISBN . 978-1-4673-9280-8.
  4. ^ ab Peri L. Tarr; Alexander L. Wolf (2011). Ingeniería de software: las contribuciones continuas de Leon J. Osterweil . Springer Science & Business Media. pág. 58. ISBN 978-3-642-19823-6.
  5. ^ "Copia archivada" (PDF) . Archivado desde el original (PDF) el 2020-08-01 . Consultado el 2018-03-24 .{{cite web}}: CS1 maint: archived copy as title (link)
  6. ^ ab Kam, John B.; Ullman, Jeffrey D. (1 de enero de 1976). "Análisis de flujo de datos global y algoritmos iterativos". Revista de la ACM . 23 (1): 158–171. doi : 10.1145/321921.321938 . ISSN  0004-5411. S2CID  162375.
  7. ^ Offner, Carl. "Notas sobre algoritmos de grafos utilizados en la optimización de compiladores" (PDF) . Archivado (PDF) desde el original el 25 de julio de 2008. Consultado el 13 de abril de 2018 .
  8. ^ "Análisis de flujo de control" (PDF) . 2016. Archivado (PDF) desde el original el 19 de diciembre de 2016.

Enlaces externos

Ejemplos