LLVM 迴圈術語

迴圈

迴圈是 LLVM 迴圈 的一般化，遞迴定義如下 [HavlakCycles]

  1. 在有向圖 G（函數 CFG 或其子圖）中，迴圈 是具有至少一個內部邊的最大強連通區域。（資訊說明 — 至少一個內部邊的要求確保單一基本區塊僅在存在返回相同基本區塊的邊時才是迴圈。）

  2. 迴圈中可以從函數入口沿著不訪問迴圈中任何其他基本區塊的路徑到達的基本區塊稱為迴圈的入口。迴圈可以有多個入口。

  3. 對於從函數入口開始的給定深度優先搜尋，第一個被訪問的迴圈節點稱為此迴圈相對於此特定 DFS 的標頭。標頭始終是入口節點。

  4. 在從入口開始的任何深度優先搜尋中，在 CFG 中找到的迴圈集是相同的。這些是本身沒有父節點的頂級迴圈。

  5. 嵌套在標頭為 H 的迴圈 C 內部的子迴圈（或簡稱為迴圈）是在節點集 (C - H) 上誘導的子圖中的迴圈。C 被稱為這些迴圈的父節點。

因此，迴圈形成了一個實現定義的森林，其中每個迴圈 C 都是嵌套在 C 內部的任何子迴圈的父節點。該樹緊密遵循相同函數中迴圈的嵌套。可約迴圈（LLVM 迴圈）L 的唯一入口支配其所有其他節點，並且始終被選為某些迴圈 C 的標頭，而不管使用的 DFS 樹如何。此迴圈 C 是迴圈 L 的超集。對於不可約迴圈，沒有一個入口支配迴圈的節點。其中一個入口以實現定義的方式被選為迴圈的標頭。

如果迴圈有多個入口，則它是不可約的，否則它是可約的。

如果基本區塊 B 出現在迴圈 C 中但不出現在 C 的任何子迴圈中，則稱迴圈 C 是基本區塊 B 的父節點。那麼 B 也被稱為迴圈 C 的子節點。

如果基本區塊不是任何迴圈的子節點，則稱其為頂級區塊。

如果基本區塊或迴圈 X 和另一個基本區塊或迴圈 Y 都沒有父節點，或者它們都具有相同的父節點，則它們互為兄弟節點。

資訊說明

  • 迴圈的非標頭入口區塊可以包含在子迴圈中。

  • 如果 CFG 是可簡化的，則循環就是自然迴圈，並且每個循環都只有一個入口區塊。

  • 根據定義，循環是良好巢狀的。

  • 循環的入口區塊在支配樹中是兄弟節點。

[HavlakCycles]

Paul Havlak，「可簡化和不可簡化迴圈的巢狀」。ACM 程式語言和系統學報 (TOPLAS) 19.4 (1997)：557-567。

循環範例

包含自然迴圈的不可簡化循環

_images/cycle-1.png

A 和 B 的自迴圈產生兩個單區塊自然迴圈。可能的循環層次結構為

cycle: {A, B, C} entries: {A, B} header: A
- cycle: {B, C}  entries: {B, C} header: C
  - cycle: {B}   entries: {B}    header: B

當 DFS 以 A、C、B 的順序（前序遍歷）訪問區塊時，就會出現這種層次結構。

兩個自然迴圈的不可簡化聯集

_images/cycle-2.png

有兩個自然迴圈：{A, C} 和 {B, D}。可能的循環層次結構為

cycle: {A, B, C, D} entries: {A, B} header: A
- cycle: {B, D}     entries: {B}    header: B

沒有自然迴圈的不可簡化循環

_images/cycle-3.png

此圖不包含任何自然迴圈 - 節點 A、B、C 和 D 在支配樹中是兄弟節點。可能的循環層次結構為

cycle: {A, B, C, D} entries: {A, B} header: A
- cycle: {B, D}     entries: {B, D} header: D

封閉路徑和循環

CFG 中的*封閉路徑*是指 CFG 中節點和邊的連接序列，其起始節點和結束節點相同，並且其餘（內部）節點不同。

封閉路徑 P 的*入口*是指 P 上的一個節點，該節點可以從函數入口到達，而無需經過 P 上的任何其他節點。

  1. 如果節點 D 支配封閉路徑 P 中的一個或多個節點，並且 P 不包含 D，則 D 支配 P 中的每個節點。

    **證明：**令 U 為 P 中由 D 支配的節點。如果 P 中存在一個節點 V 不受 D 支配，則可以從函數入口節點經由 V 到達 U，而無需經過 D，這與 D 支配 U 的事實相矛盾。

  2. 如果節點 D 支配封閉路徑 P 中的一個或多個節點，並且 P 不包含 D，則存在一個循環 C，它包含 P 但不包含 D。

    **證明：**根據上述性質，D 支配 P 中的所有節點。對於由實現定義的 DFS 發現的任何循環巢狀，請考慮包含 P 的最小循環 C。為了反證，假設 D 在 C 中。則 C 的標頭 H 不能在 P 中，因為循環的標頭不能由循環中的任何其他節點支配。因此，P 位於集合 (C-H) 中，並且 C 中必須存在一個更小的循環 C' 也包含 P，但这與我們選擇 C 的方式相矛盾。

  3. 如果封閉路徑 P 包含節點 U1 和 U2，但不包含它們各自的支配節點 D1 和 D2，則存在一個循環 C，它包含 U1 和 U2，但不包含 D1 和 D2。

    證明：根據上述性質，D1 和 D2 分別支配著 P 中的每個節點。存在一個環 C1（分別為 C2），它包含 P 但不包含 D1（分別為 D2）。C1 和 C2 要麼是同一個環，要麼其中一個嵌套在另一個環內。因此，始終存在一個包含 U1 和 U2 但不包含 D1 和 D2 的環。

  1. 在任何環階層結構中，包含封閉路徑 P 的最小環 C 的標頭 H 本身位於 P 上。

    證明：如果 H 不在 P 中，則在集合 C - H 中存在一個更小的環 C'，其中包含 P，這與 C 是此類最小環的說法相矛盾。

可縮減環標頭

儘管環階層結構取決於所選的 DFS，但可縮減環滿足以下不變量

如果在任何 DFS 中發現了標頭為 H 的可縮減環 C，則在每個 DFS 中都存在一個標頭為 H 的環 C'，其中包含 C。

證明：對於 C 中通過 H 的封閉路徑 P，每個環階層結構都有一個最小的環 C'，其中包含 P 並且其標頭位於 P 中。由於 H 是 P 的唯一入口，因此 H 必須是 C' 的標頭。由於標頭唯一地定義了環，因此 C' 包含每個此類封閉路徑 P，因此 C' 包含 C。