Grafo de fluxo de controle
Em ciência da computação, grafo de fluxo de controle é uma representação que usa notação de grafo para descrever todos os caminhos que podem ser executados por um programa de computador.
![](http://upload.wikimedia.org/wikipedia/commons/thumb/2/26/Simplified_Control_Flowgraphs.jpg/220px-Simplified_Control_Flowgraphs.jpg)
Em tal grafo, cada nó representa um bloco básico, isto é, uma região de código sequencial sem qualquer salto de execução. Dessa forma, o destino dum salto denota o começo dum bloco, então o salto termina um bloco. Arestas direcionadas são usadas para representar tais saltos na estrutura de controle. Ainda há dois blocos especiais, o bloco de entrada e o bloco de saída, de onde se começa e termina o fluxo, respectivamente.
O grafo de fluxo de controle é essencial para diversas ferramentas de otimização de compiladores e análise sintática de código. Por exemplo, uma propriedade útil para a otimização é a alcançabilidade. Se um bloco ou subgrafo não está conectado ao subgrafo que contém o bloco de entrada, tal bloco não é alcançável em qualquer execução, resultando num código inalcançável, que pode ser removido. Se o bloco de saída é inalcançável a partir do bloco de entrada, há algum tipo de laço infinito no código (nem todos os laços infinitos são detectáveis, entretanto; ver problema da parada).
Exemplos
editarConsiderando o código abaixo:
0: (A) t0 ← read_num 1: (A) se t0 mod 2 == 0 goto 4 2: (B) imprima t0 + " é impar." 3: (B) goto 5 4: (C) imprima t0 + " é par." 5: (D) fim do programa
Há quatro blocos básicos, A, B, C e D. A é o bloco de entrada, enquanto D é o bloco de saída. as linhas 4 e 5 representam destinos de saltos.
Referências
- ↑ Joseph Poole, NIST (1991). A Method to Determine a Basis Set of Paths to Perform Program Testing Arquivado em 5 de junho de 2009, no Wayback Machine..