Gráfico de flujo de control ( inglés c control f low graph, CFG ) - en la teoría de la compilación - el conjunto de todas las formas posibles de ejecutar un programa, representado como un gráfico .
En el gráfico de flujo de control, cada nodo (vértice) del gráfico corresponde a un bloque básico : una sección de código en línea recta que no contiene operaciones de transferencia de control ni puntos a los que se transfiere el control desde otras partes del programa. Solo hay dos excepciones:
Los arcos dirigidos se utilizan en un gráfico para representar instrucciones de salto. Además, en la mayoría de las implementaciones, se agregan dos bloques especializados:
La estructura CFG es importante para muchas optimizaciones del compilador y para las utilidades de análisis de código estático .
Son posibles dos casos: falta un bloque o un subgrafo:
Un bloque que no está asociado con un bloque de entrada se considera inaccesible (código "muerto"). Accesibilidad es una de las propiedades gráficas utilizadas en las optimizaciones. Un bloque inalcanzable se puede eliminar del programa.
Un bloque que no está asociado con un bloque de salida contiene un bucle infinito. Confiando en esta declaración, no es posible detectar todos los bucles infinitos debido al problema de detención .
Al realizar optimizaciones, el compilador puede crear código "muerto" y bucles infinitos, incluso si el programador no lo codificó explícitamente. Por ejemplo , después de realizar un plegado constante y una propagación constante , la optimización de subprocesos de salto puede fusionar varios bloques en uno; como resultado, algunos bordes pueden desaparecer y algunos bloques pueden no estar conectados al gráfico.
Los siguientes términos se utilizan a menudo cuando se trabaja con gráficos de flujo de control.
borde borde dirigido (o arco) que conecta bloques de gráfico. Bloque de entrada, bloque de entrada, bloque de inicio el bloque del que parte cualquier camino. bloque de salida, bloque de salida el bloque que termina cualquier camino. Borde trasero un borde que apunta al bloque anterior, es decir, el bloque que se habría recorrido antes en el proceso de recorrer el gráfico en profundidad . borde crítico una arista que se origina en un bloque con múltiples aristas salientes y entra en un bloque con múltiples aristas entrantes. Borde anormal una arista que sale de un bloque y no entra en otro bloque por la imposibilidad de calcular este último. Ocurre, por ejemplo, después de la transformación de una construcción de manejo de excepciones . Dichos bordes interfieren con las optimizaciones. Borde imposible un borde agregado a un gráfico únicamente para preservar la propiedad del gráfico de que el bloque de salida está posdominado sobre cualquier otro bloque. Este borde no se puede atravesar. Dominador , dominador, antecesor obligado Se dice que el bloque M es dominante sobre el bloque N si cualquier ruta desde el bloque de entrada al bloque N pasa por el bloque M. El bloque de entrada domina a todos los demás bloques en el gráfico. Postdominador , postdominador Se dice que el bloque M es posdominante sobre el bloque N si cualquier camino desde N hasta el bloque de salida pasa por el bloque M. El nodo de salida domina después sobre todos los bloques del gráfico. Dominador inmediato, dominador inmediato Se dice que un bloque M es un bloque N directamente dominante si el bloque M domina al bloque N, y no hay otro bloque P intermedio que esté dominado por el bloque M y domine al bloque N. En otras palabras, M es el último dominador en cualquier camino desde el bloque de entrada al bloque N Cada bloque, excepto la entrada, tiene un único dominador inmediato. Postdominante inmediato un análogo del término dominador inmediato , pero para un postdominador. Árbol dominador una estructura de datos de árbol auxiliar que contiene información sobre las relaciones de dominancia. Se crea una rama del bloque M al bloque N si y solo si el bloque M es el dominador inmediato de N. La estructura de datos es un árbol, ya que cualquier bloque tiene un único dominador inmediato. La raíz del árbol es el nodo de entrada. Para la construcción se utiliza el eficiente algoritmo de Lengauer-Tarjan . Árbol posdominante análogo del árbol de dominadores , pero para postdominadores. La raíz del árbol es el bloque de salida. Encabezado de bucle, encabezado de bucle, punto de entrada de bucle un bloque conectado por bordes a todos los bloques del cuerpo del ciclo. El bloque domina todos los nodos del cuerpo del bucle. Preencabezado de bucle un bloque conectado por un borde al bloque de encabezado de bucle ; dominador inmediato para el punto de entrada al bucle. Sea el bloque M el punto de entrada del bucle. Para algunas fases de optimización, es beneficioso que el bloque M se divida en dos bloques: M pre (encabezado de bucle) y M loop (encabezado de bucle). Después de dividir el bloque M, su contenido y bordes posteriores se transfieren al bloque de bucle M , y los bordes restantes se transfieren al bloque M pre ; luego se crea un nuevo borde que conecta el bloque M pre con el bloque M loop ; por lo tanto, el prebloque M se convierte en el dominador directo del bloque de bucle M. El bloque M pre no contendrá ningún código hasta que algunas optimizaciones, como el movimiento de código invariable en bucle , completen su contenido .Para fragmento de código:
0: (A)t0 = read_num 1: (A) si t0 mod 2 == 0 ir a 4 2: (B) imprime t0 + "es impar". 3: (B) ir a 5 4: (C) imprime t0 + "es par". 5: (D) programa finalEl gráfico de flujo de control constará de 4 bloques básicos: A para las líneas 0-1, B para las líneas 2-3, C para la línea 4 y D para la quinta línea. El gráfico tendrá arcos A -> B, A -> C, B -> D, C -> D.