Gráfico de flujo de control

En informática , un grafo de flujo de control ( GFC ) es una representación , mediante notación gráfica , de todas las rutas que podría recorrer una función durante su ejecución , o flujo de control . El grafo de flujo de control fue concebido por Frances E. Allen , ^{[ 1 ] [ 2 ]} quien señaló que Reese T. Prosser había utilizado matrices de conectividad booleana para el análisis de flujo anteriormente. ^{[ 3 ]}

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

Un grafo de flujo de control es el grafo dirigido de los bloques básicos de la función (los nodos del grafo) y el flujo de control entre ellos (las aristas del grafo).

Los detalles exactos varían según la representación. Por lo general, un bloque básico consiste en una secuencia lineal de instrucciones o sentencias. Solo la última instrucción o sentencia de cada bloque puede controlar el flujo, y este solo puede dirigirse a la primera instrucción o sentencia del bloque.

En la mayoría de las representaciones CFG, hay dos bloques especialmente designados: el bloque de entrada , a través del cual el control ingresa a la función, y el bloque de salida , a través del cual todo el control sale de la función (normalmente mediante un retorno). ^{[ 4 ]} Algunas representaciones permiten múltiples bloques de salida, especialmente si hay diferentes tipos de salida, o permiten que el bloque de salida se omita si no es alcanzable.

Si existe una arista de flujo de control desde el bloque A al bloque B, entonces A se denomina predecesor de B, y B se denomina sucesor de A.

Como ejemplo sencillo, considere la siguiente definición de función en C :

void print_within_parentheses ( const char * p ) { printf ( "(" ); // 1 if ( p != NULL ) { // 1 printf ( "%s" , p ); // 2 } // 2 printf ( ")" ); // 3 }

Esta función tiene tres bloques básicos:

• El bloque 1 es el bloque de entrada. Se ejecuta desde el inicio de la función hasta el final de la expresión . Finaliza con el flujo de control, que pasa al bloque 2 si la condición es verdadera o al bloque 3 si es falsa.p != NULLif
• El bloque 2 es el cuerpo de la ifinstrucción. Termina pasando incondicionalmente al bloque 3.
• El bloque 3 es el bloque de salida. Va desde el final de la ifinstrucción hasta returnel final del cuerpo de la función.

La estructura anidada del programa fuente dificulta un poco la visualización de los bloques básicos. Como representación alternativa que hace que los bloques sean más evidentes, podemos aplanar esa estructura en una secuencia de bloques etiquetados. Para hacer explícito el flujo de control, requeriremos que cada bloque termine en goto, una if/ elsede goto, o return(solo en el bloque de salida).

void print_within_parentheses ( const char * p ) { block1 : { printf ( "(" ); if ( p != NULL ) { goto block2 ; } else { goto block3 ; } }bloque2 : { printf ( "%s" , p ); ir a bloque3 ; }bloque3 : { printf ( ")" ); return ; } }

Esta es una representación a nivel de código fuente de la gramática libre de contexto (GLC). Los bloques básicos consisten en secuencias de instrucciones C tomadas directamente del programa fuente. Solo se ha eliminado el flujo de control estructurado.

Consideremos ahora un ejemplo más complejo que incluye un bucle:

void print_as_ordered_tuple ( const char * const * p ) { printf ( "(" ); // 1 bool first = true ; // 1 for (; * p != NULL ; ++ p ) { // 2 if ( ! first ) { // 3 printf ( "," ); // 4 } // 4 first = false ; // 5 printf ( "%s" , * p ); // 5 } // 5 printf ( ")" ); // 6 }

Esta función tiene seis bloques básicos, que se pueden ver claramente en nuestra representación a nivel de fuente de la CFG:

void print_as_ordered_tuple ( const char * p ) { bool first ;bloque1 : { printf ( "(" ); first = true ; goto bloque2 ; }bloque2 : { si ( * p != NULL ) { ir a bloque3 ; } de lo contrario { ir a bloque6 ; } }bloque3 : { si ( ! primero ) { ir al bloque4 ; } de lo contrario { ir al bloque5 ; } }bloque4 : { printf ( "," ); ir a bloque5 ; }bloque5 : { primero = falso ; printf ( "%s" , * p ); ++ p ; ir al bloque2 ; }bloque6 : { printf ( ")" ); return ; } }

Este estilo de representación CFG a nivel de sentencia no se usa comúnmente y se muestra aquí solo con fines ilustrativos. No todos los programas se pueden representar fácilmente de esta manera, incluso en C. Nótese cómo la declaración de la variable local se ha elevado al principio de la función y su inicialización block1se ha convertido en una asignación. Esto causaría dificultades para características controladas por el ámbito, como el sombreado y los arreglos de longitud variable. Las sentencias también tendrían que reescribirse significativamente para manejar el flujo de control a nivel de expresión, como el que introducen los operadores &&, ||, y .? :

La mayoría de las representaciones CFG prácticas utilizan algo distinto a sentencias fuente completas como componentes de sus bloques básicos. Por ejemplo, los marcos de compilación como LLVM utilizan una CFG en la que los bloques básicos consisten en instrucciones abstractas estáticas de asignación única como su IR principal. Aquí está la función anterior traducida al IR de LLVM:

define void @print_as_ordered_tuple ( ptr %0 ) { block1: %p = alloca ptr %first = alloca i1 store ptr %0 , ptr %p call i32 ( ptr , ...) @printf ( ptr @"(" ) store i1 1 , ptr %first br label %block2bloque2: %1 = cargar ptr , ptr %p %2 = cargar ptr , ptr %1 %3 = icmp ne ptr %2 , null br i1 %1 , etiqueta %bloque3 , etiqueta %bloque4bloque3: %4 = cargar i1 , puntero %primer br i1 %4 , etiqueta %bloque4 , etiqueta %bloque5bloque4: llamar a i32 ( ptr , ...) @printf ( ptr @"," ) etiqueta br %bloque5bloque5: almacenar i1 0 , ptr %first %5 = cargar ptr , ptr %p %6 = cargar ptr , ptr %5 llamar a i32 ( ptr , ...) @printf ( ptr @"%s" , ptr %6 ) %7 = cargar ptr , ptr %p %8 = obtener elementoptr inbounds ptr , ptr %7 , i32 1 almacenar ptr %8 , ptr %p br etiqueta %block2bloque6: llamar a i32 ( ptr , ...) @printf ( ptr @")" ) ret void }

Observe cómo la estructura de bloques es la misma tanto en el código fuente como en las grafos de flujo de control de LLVM. En ambas representaciones, las funciones tienen la misma semántica básica, realizando la misma secuencia de operaciones y flujo de control. Solo difiere la representación de las operaciones individuales.

Se puede obtener un grafo de flujo de control muy explícito a partir de una función fuente colocando cada instrucción en su propio bloque básico. Si la instrucción no es una instrucción de flujo de control, se agrega un salto de "caída" al bloque de la siguiente instrucción. Desafortunadamente, esto tiende a crear una gran cantidad de bloques básicos y saltos de caída innecesarios, lo que hace que el análisis posterior sea más engorroso y costoso. Por lo general, es deseable que las instrucciones sucesivas se coloquen en el mismo bloque básico siempre que sea posible. Otra forma de decirlo es que, en todo el grafo de flujo de control, cada arista A→B debe tener la propiedad de que:

grado de salida (A) > 1 o grado de entrada (B) > 1 (o ambos). ^{[ 5 ]}

Dicho grafo puede derivarse del CFG de una instrucción por bloque mediante la contracción de aristas para cada arista que falsifique el predicado anterior; es decir, fusionando dos bloques siempre que el bloque de origen salte al bloque de destino y este último solo pueda ser saltado por el bloque de origen. Sin embargo, este algoritmo basado en la contracción tiene poca importancia práctica, salvo como ayuda visual para comprender la construcción del CFG, debido al coste de construir la forma inicial. En las implementaciones típicas, el CFG se construye directamente a partir del programa de forma que se minimicen los bloques innecesarios mediante la construcción, por ejemplo, escaneando el programa en busca de los límites necesarios entre los bloques básicos . ^{[ 5 ]}

La alcanzabilidad es una propiedad de grafo útil para la optimización. Si un bloque no puede ser alcanzado por ninguna ruta desde el bloque de entrada, entonces no puede ejecutarse; en ese caso, se denomina código inalcanzable . El código inalcanzable generalmente puede eliminarse del grafo de flujo de control sin consecuencias negativas.

Si el bloque de salida no puede ser alcanzado por ninguna ruta desde el bloque de entrada, entonces el flujo de control no puede abandonar el grafo normalmente. Esto indica la presencia de un bucle infinito o, en representaciones que admiten directamente estas características, una salida anormal o la terminación del programa. Que el bloque de salida sea alcanzable por alguna ruta no significa que el programa necesariamente lo alcanzará, y es imposible demostrar que se alcanzará en un grafo general; véase el problema de la parada .

La optimización puede revelar código inaccesible y bucles infinitos que no eran evidentes en el programa original. Por ejemplo, considere la siguiente función de LLVM:

define void @double_until_odd ( ptr %p ) { block1: br label %block2block2: %0 = load i32 , ptr %p ; Carga el valor actual de %p %1 = mul i32 %0 , 2 ; Multiplícalo por 2 store i32 %1 , ptr %p ; Almacena eso de nuevo en %p %2 = and i32 %1 , 1 ; Enmascara el bit menos significativo del producto %3 = icmp eq i32 %2 , 0 ; Comprueba si es 0 br i1 %3 , label %block2 , label %block3 ; Bucle si es asíbloque3: ret void }

En esta forma, el bucle de esta función no es un bucle infinito porque existe una ruta que sale del bucle: si %3es falso, el programa se bifurcará block3y regresará. Sin embargo, un análisis numérico puede demostrar que el producto de cualquier número y 2 será par, lo que significa que %2siempre es cero y %3nunca puede ser falso. Por lo tanto, esta función se puede optimizar a esta forma:

define void @double_until_odd ( ptr %p ) { block1: br label %block2bloque2: %0 = cargar i32 , puntero %p ; Cargar el valor actual desde %p %1 = multiplicar i32 %0 , 2 ; Multiplicarlo por 2 almacenar i32 %1 , puntero %p ; Almacenar eso de nuevo en %p etiqueta de bloque %bloque2bloque3: ; ret void inalcanzable }

Ahora existe un bucle infinito en el grafo de flujo de control, y ya no se puede acceder al bloque de salida. Cabe destacar que esta optimización no modificó el comportamiento del programa: siempre fue cierto que el bucle nunca terminaría. Lo único que ha cambiado es que el grafo de flujo de control refleja con mayor precisión esta realidad.

Un bloque M domina a un bloque N si todo camino desde la entrada que llega al bloque N también debe visitar el bloque M. El bloque de entrada domina a todos los demás bloques. Se dice que M domina propiamente a N si M domina a N y son bloques diferentes. Además, se dice que una instrucción o enunciado individual X domina propiamente a una instrucción o enunciado Y si el bloque que contiene X domina al bloque que contiene Y y, si son el mismo bloque, X precede estrictamente a Y en el bloque.

Se dice que un bloque M domina inmediatamente a un bloque N si M domina a N, y no existe ningún bloque intermedio P 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 hasta N. Cada bloque alcanzable tiene un único dominador inmediato, excepto el bloque de entrada, que no tiene ninguno.

El árbol de dominancia es un grafo dirigido que representa las relaciones de dominancia en la función. Los nodos del grafo son los bloques básicos alcanzables de la función, y existe una arista del bloque M al bloque N si M es un dominador inmediato de N. Dado que cada bloque alcanzable que no es de entrada tiene un único dominador inmediato, este árbol tiene su raíz en el bloque de entrada. El árbol de dominancia se puede calcular de manera eficiente utilizando el algoritmo de Lengauer-Tarjan .

En sentido inverso, el bloque M postdomina al bloque N si todo camino desde N hasta la salida también tiene que pasar por el bloque M. (Esto a veces se escribe sin guion : M postdomina a N). El bloque de salida postdomina a todos los bloques. Se dice que M postdomina propiamente a N si postdomina a N y son bloques diferentes. M es un postdominador inmediato de N si postdomina a N y no hay ningún bloque P tal que M postdomine a P y P postdomine a N. Cada bloque desde el que se puede alcanzar el bloque de salida tiene un único postdominador inmediato, excepto el bloque de salida, que no tiene ninguno. Esto da lugar a un árbol de postdominadores , enraizado en el bloque de salida, sobre los bloques desde los que se puede alcanzar el bloque de salida.

La definición estándar de dominancia incluye bloques inaccesibles, y la definición estándar de postdominancia incluye bloques desde los que no se puede acceder al bloque de salida. Sin embargo, estos bloques poseen propiedades únicas bajo estas relaciones: un bloque inaccesible está dominado por todos los demás bloques, y un bloque desde el que no se puede acceder al bloque de salida está postdominado por todos los demás bloques. La mayoría de los análisis que se basan en la dominancia o la postdominancia los ignorarán, y no se incluyen en los árboles de dominancia o postdominancia. Algunas representaciones requieren la adición de aristas imposibles para evitar la existencia de estos bloques, al menos formalmente.

Un borde crítico es aquel que no es ni el único que sale de su bloque de origen ni el único que entra en su bloque de destino. Algunas optimizaciones deben dividir los bordes críticos para insertar instrucciones a lo largo del borde sin afectar otras rutas del programa. Un borde se divide creando un nuevo bloque que contiene únicamente un salto al bloque de destino y, a continuación, reemplazando el destino de la bifurcación original con el nuevo bloque.

Una arista en retroceso es aquella para la cual existe un camino simple desde el bloque de entrada hasta el bloque de origen (como el que se podría encontrar mediante un recorrido en profundidad del grafo) que incluye el bloque de destino. Una arista en retroceso indica la presencia de un ciclo en el grafo de flujo de control. Una arista en retroceso se denomina arista de retroceso si el bloque de destino está presente en todos los caminos posibles hacia el bloque de origen, es decir, si el bloque de destino domina al bloque de origen.

Una arista anómala es aquella cuyo destino se desconoce. Las estructuras de manejo de excepciones pueden generarlas. Estas aristas tienden a inhibir la optimización.

Una arista imposible (también conocida como arista falsa ) es una arista que no se puede recorrer durante la ejecución y que se añade al grafo únicamente para preservar alguna propiedad útil. Por ejemplo, algunas representaciones requieren la adición de aristas imposibles para garantizar que el bloque de salida sea siempre alcanzable y que domine a todos los demás bloques.

Un componente fuertemente conectado (CFC) de un grafo de flujo de control es un conjunto de bloques básicos que son accesibles entre sí. Los bloques que forman parte de un bucle siempre pertenecen al mismo componente fuertemente conectado. Un bloque que no forma parte de un ciclo siempre se encuentra en un componente fuertemente conectado independiente. En particular, los bloques de entrada y salida siempre constituyen sus propios componentes fuertemente conectados.

Los componentes fuertemente conectados de un CFG forman un grafo dirigido acíclico llamado árbol SCC , donde el componente A tiene una arista al componente B si cualquier bloque en A tiene una arista a cualquier bloque en B. El árbol SCC es isomorfo al grafo de flujo de control si no hay ciclos en el CFG; si hay un ciclo, el árbol SCC esencialmente colapsa todos los bloques y aristas en él en un solo nodo. Esto puede ser útil para análisis que desean tratar todos los bloques en un ciclo como equivalentes. Por ejemplo, al intentar encontrar una vida útil de un objeto que cubra un conjunto de puntos de uso de la manera más precisa posible, si uno de esos puntos de uso está dentro de un SCC cíclico, la vida útil debe cubrir completamente cada bloque en ese componente.

El encabezado de un bucle (a veces llamado punto de entrada ) es un elemento dominante que sirve de destino a la arista de retorno que forma el bucle. El encabezado del bucle domina a todos los bloques del cuerpo del bucle. Un bloque puede ser el encabezado de más de un bucle. Un bucle puede tener varios puntos de entrada, en cuyo caso no tiene encabezado.

Supongamos que el bloque M es un dominador con varias aristas entrantes, algunas de ellas de retorno (por lo que M es un encabezado de bucle). Para varias pasadas de optimización, es ventajoso dividir M en dos bloques: M _pre y M _loop . El contenido de M y las aristas de retorno se mueven a M _loop , el resto de las aristas se mueven para apuntar a M _pre , y se inserta una nueva arista 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 pasadas como el movimiento de código invariante de bucle podrían llenarlo. M _pre se denomina encabezado previo del bucle , y M _loop sería el encabezado del bucle.

Un grafo de flujo de control se denomina reducible si todas sus aristas de retroceso son aristas de retorno. Las demás aristas de dicho grafo se denominan aristas de avance . ^{[ 6 ]} Las aristas de avance forman un grafo dirigido acíclico , y las aristas de retroceso siempre conducen a un bloque básico por el que ya ha pasado el flujo de control. Los grafos de flujo de control reducibles generalmente poseen propiedades estáticas más robustas y pueden analizarse y optimizarse con mayor facilidad. Por ejemplo, muchas optimizaciones de bucles están diseñadas para funcionar únicamente en grafos de flujo de control reducibles.

Los lenguajes de programación estructurada suelen diseñarse de forma que todos los grafos libres de contexto (GLC) que generan sean reducibles, y las instrucciones comunes de programación estructurada, como IF, FOR, WHILE, BREAK y CONTINUE, generan grafos reducibles de forma fiable. Para generar directamente un grafo irreducible, se necesitan instrucciones como GOTO , que permiten saltar a un punto arbitrario del programa, aunque no todos los usos de GOTO generan GLC irreducibles. Algunos optimizadores del compilador, como el encadenamiento de saltos , también pueden generar GLC irreducibles . Estos grafos se pueden convertir en reducibles, pero esto suele requerir duplicar código o introducir nuevas variables en el programa.

La conectividad de bucles de una gramática libre de contexto (GLC) se define con respecto a un árbol de búsqueda en profundidad (DFST) dado de la GLC. Este DFST debe tener su raíz en el nodo inicial y abarcar todos los nodos de la GLC.

En este contexto, las aristas en el CFG que van desde un nodo a uno de sus ancestros DFST (incluido él mismo) se denominan aristas de retroceso. Esto no coincide necesariamente con la definición habitual de arista de retroceso, ya que un ancestro DFST no tiene por qué dominar el nodo de origen de la arista.

La conectividad de bucle es el mayor número de aristas de retroceso encontradas en cualquier camino libre de ciclos del CFG. En un CFG reducible, la conectividad de bucle es independiente del DFST elegido. ^{[ 7 ] [ 8 ]}

La conectividad de bucles se ha utilizado para razonar sobre la complejidad temporal del análisis de flujo de datos . ^{[ 7 ]}

Mientras que los diagramas de flujo de control representan el flujo de control de un solo procedimiento, los diagramas de flujo de control interprocedimentales representan el flujo de control de programas completos. ^{[ 9 ]}

• Árbol de sintaxis abstracta
• Diagrama de flujo
• Diagrama de flujo de control
• Análisis del flujo de control
• Análisis del flujo de datos
• Intervalo (teoría de grafos)
• Grafo de dependencia del programa
• Complejidad ciclomática
• Asignación única estática
• Construcción de compiladores
• Representación intermedia

En el libro Dragon se incluye una nota bibliográfica. ^{[ 1 ]}

Ejemplos