Gráfico de fluxo de controle - Control-flow graph

Alguns exemplos de CFG:
(a) um if-then-else
(b) um loop while
(c) um loop natural com duas saídas, por exemplo, while com um if ... break no meio; não estruturado, mas redutível
(d) um CFG irredutível: um loop com dois pontos de entrada, por exemplo, goto em um while ou for loop

Um gráfico de fluxo de controle usado pelo compilador Rust para executar codegen.

Em ciência da computação , um gráfico de fluxo de controle ( CFG ) é uma representação , usando notação de gráfico , de todos os caminhos que podem ser percorridos por um programa durante sua execução . O gráfico de fluxo de controle foi descoberto por Frances E. Allen , que observou que Reese T. Prosser já havia usado matrizes de conectividade booleana para análise de fluxo.

O CFG é essencial para muitas otimizações de compilador e ferramentas de análise estática .

Definição

Em um gráfico de fluxo de controle, cada nó do gráfico representa um bloco básico , ou seja, um trecho de código em linha reta sem saltos ou alvos de salto ; os alvos de salto iniciam um bloco e os saltos terminam um bloco. Bordas direcionadas são usadas para representar saltos no fluxo de controle . Existem, na maioria das apresentações, dois blocos especialmente designados: o bloco de entrada , através do qual o controle entra no gráfico de fluxo, e o bloco de saída , através do qual todo o fluxo de controle sai.

Por causa de seu procedimento de construção, em uma CFG, toda aresta A → B tem a propriedade de:

outdegree (A)> 1 ou indegree (B)> 1 (ou ambos).

O CFG pode, portanto, ser obtido, pelo menos conceitualmente, começando a partir do gráfico de fluxo (completo) do programa - ou seja, o gráfico em que cada nó representa uma instrução individual - e realizando uma contração de aresta para cada aresta que falsifique o predicado acima, ou seja, contraindo cada borda cuja origem possui uma única saída e cujo destino possui uma única entrada. Este algoritmo baseado em contração não tem nenhuma importância prática, exceto como um auxílio de visualização para entender a construção do CFG, porque o CFG pode ser construído de forma mais eficiente diretamente a partir do programa, digitalizando-o em busca de blocos básicos .

Exemplo

Considere o seguinte fragmento de código:

0: (A) t0 = read_num
1: (A) if t0 mod 2 == 0
2: (B)   print t0 + " is even."
3: (B)   goto 5
4: (C) print t0 + " is odd."
5: (D) end program

Acima, temos 4 blocos básicos: A de 0 a 1, B de 2 a 3, C em 4 e D em 5. Em particular, neste caso, A é o "bloco de entrada", D o "bloco de saída "e as linhas 4 e 5 são alvos de salto. Um gráfico para este fragmento tem bordas de A a B, A a C, B a D e C a D.

Acessibilidade

Acessibilidade é uma propriedade de gráfico útil na otimização.

Se um subgráfico não estiver conectado a partir do subgráfico que contém o bloco de entrada, esse subgráfico ficará inacessível durante qualquer execução e, portanto, será o código inacessível ; em condições normais, pode ser removido com segurança.

Se o bloco de saída estiver inacessível a partir do bloco de entrada, pode existir um loop infinito . Nem todos os loops infinitos são detectáveis, consulte Problema de parada . Uma ordem de parada também pode existir lá.

Código inalcançável e loops infinitos são possíveis mesmo se o programador não os codificar explicitamente: otimizações como propagação constante e dobramento constante seguido de threading de salto podem colapsar vários blocos básicos em um, fazer com que as bordas sejam removidas de um CFG, etc., portanto, possivelmente desconectar partes do gráfico.

Relação de dominação

Um bloco M domina um bloco N se todo caminho desde a entrada que atinge o bloco N tem que passar pelo bloco M. O bloco de entrada domina todos os blocos.

Na direção reversa, o bloco M domina o bloco N se todo caminho de N até a saída tiver que passar pelo bloco M. O bloco de saída domina todos os blocos.

Diz-se que um bloco M domina imediatamente o bloco N se M domina N, e não há bloco intermediário P tal que M domine P e P domine N. Em outras palavras, M é o último dominador em todos os caminhos de entrada para N. Cada bloco tem um dominador imediato único.

Da mesma forma, há uma noção de pós -dominador imediato , análoga ao dominador imediato .

A árvore do dominador é uma estrutura de dados auxiliar que descreve os relacionamentos do dominador. Existe um arco do Bloco M para o Bloco N se M for um dominador imediato de N. Este gráfico é uma árvore, uma vez que cada bloco tem um dominador imediato único. Esta árvore está enraizada no bloco de entrada. A árvore dominadora pode ser calculada de forma eficiente usando o algoritmo de Lengauer-Tarjan .

Uma árvore pós - dominadora é análoga à árvore dominadora . Esta árvore está enraizada no bloco de saída.

Arestas especiais

Uma borda posterior é uma borda que aponta para um bloco que já foi encontrado durante uma passagem de profundidade ( DFS ) do gráfico. As bordas traseiras são típicas de loops.

Uma aresta crítica é uma aresta que não é a única aresta deixando seu bloco de origem, nem a única aresta entrando em seu bloco de destino. Essas arestas devem ser divididas : um novo bloco deve ser criado no meio da aresta, a fim de inserir cálculos na aresta sem afetar quaisquer outras arestas.

Uma borda anormal é uma borda cujo destino é desconhecido. As construções de manipulação de exceções podem produzi-los. Essas arestas tendem a inibir a otimização.

Uma aresta impossível (também conhecida como aresta falsa ) é uma aresta que foi adicionada ao gráfico apenas para preservar a propriedade de que o bloco de saída domina todos os blocos. Nunca pode ser percorrido.

Gerenciamento de loop

Um cabeçalho de loop (às vezes chamado de ponto de entrada do loop) é um dominador que é o alvo de uma borda posterior em formação de loop. O cabeçalho do loop domina todos os blocos no corpo do loop. Um bloco pode ser um cabeçalho de loop para mais de um loop. Um loop pode ter vários pontos de entrada, caso em que não possui "cabeçalho de loop".

Suponha que o bloco M seja um dominador com várias arestas de entrada, algumas delas sendo arestas posteriores (então M é um cabeçalho de loop). É vantajoso para várias optimização passa para quebrar H-se em dois blocos M _pré e M _circuito . O conteúdo de M e as bordas traseiras são movidos para o _loop M , o resto das bordas são movidas para apontar para M _pré , e uma nova borda de M _pré para o _loop M é inserida (de modo que M _pre é o dominador imediato do _loop M ) No início, M _pre estaria vazio, mas passa como se o movimento do código invariante do loop pudesse preenchê-lo. M _pre é chamado de pré-cabeçalho do loop , e o _loop M seria o cabeçalho do loop.

Redutibilidade

Um CFG redutível é aquele com bordas que podem ser particionadas em dois conjuntos disjuntos: bordas dianteiras e bordas traseiras, de modo que:

As arestas à frente formam um grafo acíclico direcionado com todos os nós alcançáveis a partir do nó de entrada.
Para todas as arestas posteriores (A, B), o nó B domina o nó A.

Linguagens de programação estruturadas são freqüentemente projetadas de forma que todos os CFGs que elas produzem sejam redutíveis, e instruções de programação estruturada comuns, como IF, FOR, WHILE, BREAK e CONTINUE produzem gráficos redutíveis. Para produzir gráficos irredutíveis, instruções como GOTO são necessárias. Gráficos irredutíveis também podem ser produzidos por algumas otimizações do compilador.

Conexão de loop

A conexão de loop de um CFG é definida em relação a uma determinada árvore de pesquisa em profundidade (DFST) do CFG. Este DFST deve ser enraizado no nó inicial e cobrir todos os nós do CFG.

As bordas no CFG que vão de um nó a um de seus ancestrais DFST (incluindo ele mesmo) são chamadas de bordas posteriores.

A conexão do loop é o maior número de bordas traseiras encontradas em qualquer caminho sem ciclo do CFG. Em um CFG redutível, a conexão do loop é independente do DFST escolhido.

A conexão de loop tem sido usada para raciocinar sobre a complexidade de tempo da análise de fluxo de dados .

Gráfico de fluxo de controle interprocessual

Enquanto os gráficos de fluxo de controle representam o fluxo de controle de um único procedimento, os gráficos de fluxo de controle entre procedimentos representam o fluxo de controle de programas inteiros.

Languages

In other projects