Graf przepływu sterowania

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacja, szukaj
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 pomiędzy blokami.

Często w reprezentacji grafu przepływu sterowania spotyka się dodatkowe specjalne bloki: blok wejściowy i blok wyjściowy, które oznaczają 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[edytuj | edytuj kod]

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, więc reprezentuje wszystkie przejścia programu. Na przykład dla instrukcji if / else zawiera jej obydwie 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 pomiędzy końcem i początkiem bloku). Cykle pozwalają kompilatorowi wykryć niejawnie zapisane pętle.

Zobacz też[edytuj | edytuj kod]