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 .
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:
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]
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 la imagen 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.
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.
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.
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.
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.
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.
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]
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]
{{cite web}}: CS1 maint: archived copy as title (link)