控件依賴圖有循環嗎？

我試圖正確理解控制依賴圖的概念。假設我有以下控制流圖（用點表示）：控件依賴圖有循環嗎？

graph g { 
1 -> 2; 
2 -> 3; 
3 -> 2; 
2 -> 4; 
1 -> 4 
}

它具有獨特的入口節點（1）和一個唯一的出口節點（4），和一個循環2 - > 3 - > 2。

我的問題是：該CFG的控制依賴關係圖是否包含從2到自身的循環邊緣？

Allen &肯尼迪的「爲現代架構優化編譯器」有一個算法可以產生這樣的循環邊緣。但是，Muchnick的「Compiler design & implementation」的控制依賴算法不會產生這樣的邊緣。另外，在文獻中找不到任何CDG用這樣的循環邊緣繪製的例子。我傾向於認爲沒有這樣的優勢，但根據控制依賴的正式定義，並根據肯尼迪算法，它應該！

如果你可以請我指出一個例子，在CDG中存在這樣一個循環（最好在同行評議的論文或一些教授的講義中，等等），或者你可以爭辯爲什麼艾倫肯尼迪的算法應該是不正確的，我很高興知道。

來源

2012-01-27 anol

這種依賴關係圖的實用性決定了如何排序操作，對嗎？從這個意義上講，知道一個元素依賴於自身是沒有幫助的。如果你喜歡，你可以繪製循環，但其他所有邊緣真正重要。 – mitchus 2012-02-15 15:04:50

是的，我想我期待一些可用作oracle的測試多個實現的「規範定義」，但確實這兩個版本在所有實際用途上都是相同的......謝謝！ – anol 2012-05-07 14:24:46

@mitchus您應該將您的評論移至答案，以便它可以被接受爲答案。 – 2012-07-27 15:29:16

根據Ferrante 1987，控制依賴循環可以存在。在案例2中第325頁上，作者指定

在從A路徑上的支配後樹B，包括A和B，所有節點進行控制依賴於A.（此案例捕獲環路依賴性。）

因此，在這種情況下，在節點A處會出現環路。

來源

2013-07-29 20:58:25 tba

你說得對，我接受了@mitchus的回答，但是你的回答更加精確。我仍然發現mitchus的評論頗具針對性。 – anol 2013-07-30 16:32:07

這樣的依賴圖的實用性決定了如何排序操作，對嗎？從這個意義上講，知道一個元素依賴於自身是沒有幫助的。如果你喜歡，你可以繪製循環，但其他所有邊緣真正重要。

來源

2012-08-03 08:48:42 mitchus

控件依賴圖有循環嗎？

回答

相關問題