Un grafo dirigido que representa el posible orden de ejecución y la transferencia de control entre bloques básicos o sentencias en un programa; los nodos suelen representar bloques básicos y las aristas saltos, bifurcaciones y transiciones por caída.

Principio

Modelar la ejecución del programa como transiciones entre regiones de control para que la alcanzabilidad, dominancia, liveness y otros análisis centrados en el control puedan formularse como problemas de grafo sobre nodos y aristas que representan el flujo del contador de programa.

Demostración

Una función con un if/else y un bucle se mapea a un CFG donde un nodo condicional tiene dos aristas salientes hacia los bloques 'then' y 'else'; el bucle introduce una arista de retroceso desde la cola del bucle al encabezado, haciendo el CFG cíclico.

Aplicación incorrecta

Usar un CFG para razonar sobre dependencias de datos (por ejemplo, asumir que definiciones de valores fluyen a lo largo de aristas del CFG) o asumir que la presencia de una arista implica que una transición en tiempo de ejecución siempre ocurrirá con la misma frecuencia: ambos conducen a optimizaciones o análisis incorrectos.

Consecuencia

El uso correcto permite optimizaciones como eliminación de código muerto, transformaciones de bucles, decisiones de inlining (cuando se combina con información interprocedural) y tareas de verificación como demostrar alcanzabilidad o ausencia de ciertos caminos de control.

Inversión

Tratar el programa puramente como flujo de datos (grafo computacional) donde las construcciones de control se codifican como transformaciones de datos; esta inversión sustituye aristas de control explícitas por guardas basadas en datos y puede ocultar propiedades centradas en el control.

Límite

Se aplica por defecto a representaciones intraprocedurales; el flujo de control interprocedural requiere extensión (aristas de llamada/retorno, CFG interprocedural). No codifica efectos secundarios, entrelazados de concurrencia ni temporización precisa salvo que se amplíe.

Tensión semántica

Existe tensión entre el CFG y los grafos computacionales/de flujo de datos: el CFG enfatiza los posibles traslados del contador de programa (control), mientras que los grafos de datos enfatizan la propagación de valores; confundirlos lleva a análisis inapropiados.

Síntesis

Un grafo de flujo de control es la abstracción del programa que hace explícitas las transiciones posibles entre regiones del programa como aristas dirigidas; es la estructura fundamental para análisis y transformaciones que dependen de la forma del control más que del simple movimiento de datos.