Próbuję dokładnie zrozumieć pojęcie wykresu zależności sterowania. Załóżmy, że mają następujący wykres kontroli przepływu (w notacji DOT):Czy wykres zależności sterowania może zawierać pętle?
graph g {
1 -> 2;
2 -> 3;
3 -> 2;
2 -> 4;
1 -> 4
}
Posiada charakterystyczny punkt wejścia (1) i unikalną węzła wyjściowego (4), oraz pętlę 2 -> 3 -> 2.
Moje pytanie brzmi: czy wykres zależności sterowania dla tej kombinacji CFG zawiera krawędź pętli od 2 do siebie?
Allen & "Optymalizowanie kompilatorów dla nowoczesnych architektur" Kennedy'ego ma algorytm, który wytwarza taką krawędź pętli. Jednak "algorytm implementacji" algorytmu Muchnick'a dla zależności sterowania nie wytwarza takiej krawędzi. Poza tym nie znalazłem w literaturze przykładów, w których rysuje się CDG z taką krawędzią pętli. Zwykle uważam, że nie ma takiej przewagi, ale zgodnie z formalną definicją zależności kontrolnej i zgodnie z Allenem & algorytm Kennedy'ego, powinien!
Jeśli możesz proszę wskazać mi przykład, w którym jest taka pętla w CDG (najlepiej w recenzowanej gazecie lub w notatkach z wykładów profesora itp.), Lub jeśli możesz argumentować dlaczego Allen & Algorytm Kennedy'ego powinien być niepoprawny, chętnie bym się dowiedział.
Narzędziem takiego grafu zależności jest sposób zamawiania operacji, prawda? W tym sensie nie jest pomocne wiedzieć, że element zależy od niego samego. Możesz narysować pętle, jeśli chcesz, ale najważniejsze są wszystkie pozostałe krawędzie. – mitchus
Tak, myślę, że oczekiwałem jakiejś "definicji kanonicznej", która mogłaby zostać wykorzystana jako wyrocznia do testowania wielu implementacji, ale prawdą jest, że obie wersje są równoważne ze wszystkich praktycznych powodów ... dzięki! – anol
@mitchus Powinieneś przenieść swój komentarz na odpowiedź, aby mogła zostać zaakceptowana jako odpowiedź. –