Graf przepływu sterowania

Graf przepływu sterowania przykładowego programu. Dla zwiększenia przejrzystości wierzchołki grafu reprezentujące predykaty zwierają słowa kluczowe instrukcji, w których są zawarte

Graf przepływu sterowania (ang. control flow graph) – abstrakcyjna struktura danych używana przez kompilator do reprezentacji pojedynczej procedury programu. Wierzchołkami grafu są bloki podstawowe, a skierowane krawędzie wskazują powiązania między blokami.

Często w reprezentacji grafu przepływu sterowania spotyka się dodatkowe specjalne bloki: blok wejściowy i blok wyjściowy, oznaczające odpowiednio początek i koniec procedury.

Krawędzie mogą być etykietowane wartościami „prawda” lub „fałsz” – wówczas oznaczają, że wykonanie docelowego bloku zależy od wartości predykatu zawartego w źródłowym bloku.

Graf przepływu sterowania jest wykorzystywany do optymalizacji programów.

Przykład

Fragment programu wyliczający sumę parzystych liczb z przedziału 0...N. Jego graf przepływu sterowania znajduje się obok.

int result = 0;
int i = 0;
while (i < N) {
    if (i % 2 == 0) {
        result += i;
    }
    ++i;
}

Graf przepływu sterowania jest statyczną reprezentacją programu, reprezentuje więc wszystkie przejścia programu. Na przykład dla instrukcji if / else zawiera jej obie gałęzie, choć wiadomo, że zawsze wykonuje się dokładnie jedna z nich. Cykl w grafie mówi, że w programie występuje pętla (zwłaszcza jeśli jest to cykl między końcem i początkiem bloku). Cykle pozwalają kompilatorowi wykryć niejawnie zapisane pętle.

Zobacz też

• złożoność cyklomatyczna