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.
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 editar
Considerando 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..