En informática , un gráfico de flujo de control ( CFG ) es una representación , utilizando notación gráfica , de todos los caminos que pueden recorrerse a través de un programa durante su ejecución . El gráfico de control de flujo fue descubierto por Frances E. Allen , [1] quien señaló que Reese T. Prosser usó matrices de conectividad booleanas para el análisis de flujo antes. [2]
El CFG es esencial para muchas optimizaciones de compiladores 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 bifurcaciones ni saltos dentro del bloque. Los bloques básicos comienzan con objetivos de salto y terminan con saltos o instrucciones de bifurcació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, toda arista A→B tiene la propiedad de que:
Por tanto, el CFG se puede obtener, 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 borde cuyo origen tiene una única salida y cuyo destino tiene una única entrada. Este algoritmo basado en contracciones no tiene importancia práctica, excepto como ayuda de visualización para comprender la construcción del CFG, porque el CFG se puede construir de manera más eficiente directamente desde el programa al escanearlo 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) imprime t0 + "es par".3: (B) ir a 54: (C) imprime t0 + "es impar".5: (D) finalizar el programa
En lo 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 gráfico para este fragmento tiene aristas de A a B, de A a C, de B a D y de C a D.
La accesibilidad es una propiedad gráfica útil en la optimización.
Si un subgrafo no está conectado desde el subgrafo que contiene el bloque de entrada, ese subgrafo es inalcanzable durante cualquier ejecución, al igual que el código inalcanzable ; en condiciones normales se puede eliminar de forma segura.
Si no se puede acceder al bloque de salida desde el bloque de entrada, puede existir un bucle infinito . No todos los bucles infinitos son detectables; consulte Problema de detención . Allí también puede existir una orden de detención.
El código inalcanzable y los bucles infinitos son posibles incluso si el programador no los codifica explícitamente: optimizaciones como la propagación constante y el plegado constante seguidos de un subprocesamiento de salto pueden colapsar múltiples bloques básicos en uno, hacer que los bordes se eliminen de un CFG, etc., por lo que posiblemente desconectar partes del gráfico.
Un bloque M domina 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 todos los bloques.
En la dirección inversa, el bloque M postdomina el bloque N si cada camino desde N hasta la salida tiene que pasar por el bloque M. El bloque de salida postdomina 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 de modo 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 dominador es una estructura de datos auxiliar que representa las relaciones dominadoras. Hay un arco del 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 sus raíces en el bloque de entrada. El árbol dominador se puede calcular de manera eficiente utilizando el algoritmo de Lengauer-Tarjan .
Un árbol postdominador es análogo al árbol dominador . Este árbol tiene sus raíces 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.
Un borde crítico es un borde que no es el único borde que sale de su bloque de origen ni el único borde que ingresa a su bloque de destino. Estos bordes deben dividirse : se debe crear un nuevo bloque en el medio del borde para poder insertar cálculos en el borde sin afectar ningún otro borde.
Una arista anormal es una arista cuyo destino se desconoce. Las construcciones de manejo de excepciones pueden producirlas. Estos bordes 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 del bucle domina todos los bloques del 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 un "encabezado de bucle".
Supongamos que el bloque M es un dominador con varios bordes entrantes, algunos de ellos son bordes posteriores (por lo que M es un encabezado de bucle). Es ventajoso realizar varias pasadas de optimización para dividir M en dos bloques M pre y M loop . El contenido de M y los bordes posteriores 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 sea el dominador inmediato de M loop). ). Al principio, M pre estaría vacío, pero los pases como el movimiento del código invariante en bucle podrían poblarlo. M pre se llama encabezado previo del bucle y M loop sería el encabezado del bucle.
Un CFG reducible es aquel con bordes que se pueden dividir en dos conjuntos disjuntos: bordes delanteros y bordes traseros, de modo que: [5]
Los lenguajes de programación estructurados a menudo están diseñados de manera que todos los CFG que producen sean reducibles, y las declaraciones de programación estructuradas comunes como IF, FOR, WHILE, BREAK y CONTINUE producen gráficos reducibles. Para producir gráficos irreducibles, se necesitan declaraciones como GOTO . Algunas optimizaciones del compilador también pueden producir gráficos irreducibles.
La conectividad del bucle de un CFG se define con respecto a un árbol de búsqueda en profundidad (DFST) dado del CFG. Este DFST debe tener su raíz en el nodo inicial y cubrir todos los nodos del CFG.
Los bordes en el CFG que van desde un nodo hasta uno de sus ancestros DFST (incluido él mismo) se denominan bordes posteriores.
La conectividad del bucle es el mayor número de bordes posteriores que se encuentran en cualquier ruta libre de ciclos del CFG. En un CFG reducible, la conectividad del bucle es independiente del DFST elegido. [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)