Graf przepływu sterowania
Z Wikipedii
Graf przepływu sterowania (Control Flow Graph) jest abstrakcyjną strukturą danych używaną 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 zródłowym bloku.
Graf przepływu sterowania jest wykorzystywany do optymalizacji programów.
int result = 0;
int i = 0;
while (i < N) {
if (i % 2 == 0) {
result += i;
}
++i;
}
Fragment programu wyliczający sumę parzystych liczb z przedziału 0..N.
Graf przepływu sterowania dla powyższego 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 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.
