Graf przepływu sterowania
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]
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.
