LLVM 迴圈術語（以及正規形式）¶

迴圈定義 ¶

迴圈是程式碼最佳化器中的一個重要概念。在 LLVM 中，控制流程圖（CFG；其中節點代表基本區塊）中的迴圈檢測是由迴圈資訊完成的。它基於以下定義。

迴圈是控制流程圖（CFG；其中節點代表基本區塊）中節點的子集，具有以下屬性

誘導子圖（包含迴圈內 CFG 中所有邊的子圖）是強連通的（每個節點都可以從所有其他節點到達）。
從子集外部到子集的所有邊都指向同一個節點，稱為標頭。因此，標頭支配迴圈中的所有節點（即，到任何迴圈節點的每個執行路徑都必須通過標頭）。
迴圈是具有這些屬性的最大子集。也就是說，不能添加來自 CFG 的其他節點，使得誘導子圖仍然是強連通的，並且標頭保持不變。

在電腦科學文獻中，這通常稱為自然迴圈。在 LLVM 中，更廣義的定義稱為循環。

術語 ¶

迴圈的定義帶有一些額外的術語

進入區塊（或迴圈前驅）是一個非迴圈節點，它具有一條指向迴圈（一定是標頭）的邊。如果只有一個進入區塊，並且它的唯一邊是到標頭，則它也稱為迴圈的前導標頭。前導標頭支配迴圈，而它本身不是迴圈的一部分。
閂鎖是一個具有指向標頭的邊的迴圈節點。
回邊是從閂鎖到標頭的邊。
退出邊是從迴圈內部到迴圈外部節點的邊。此類邊的源稱為退出區塊，其目標稱為出口區塊。

重要注意事項 ¶

此迴圈定義具有一些值得注意的結果

一個節點最多可以作為一個迴圈的標頭。因此，迴圈可以通過其標頭來識別。由於標頭是進入迴圈的唯一入口，因此可以將其稱為單入口多出口（SEME）區域。
對於無法從函數入口到達的基本區塊，迴圈的概念未定義。這也是由於支配的概念未定義。
最小的迴圈是由一個分支到自身的基礎區塊所組成。在這種情況下，該區塊同時是迴圈頭、迴圈尾（如果它有另一個分支到不同區塊，則也是迴圈出口）。單個沒有分支到自身的區塊不被視為迴圈，即使它顯然是強連通的。

在這種情況下，迴圈頭、迴圈出口和迴圈尾的角色都落在同一個節點上。LoopInfo 將其報告為

$ opt input.ll -passes='print<loops>'
Loop at depth 1 containing: %for.body<header><latch><exiting>

迴圈可以互相嵌套。也就是說，一個迴圈的節點集可以是另一個具有不同迴圈頭的迴圈的子集。函數中的迴圈層級結構形成一個森林：每個頂級迴圈都是嵌套在其中的迴圈樹的根。

兩個迴圈不可能只共享少數節點。兩個迴圈要么不相交，要么一個嵌套在另一個裡面。在下面的例子中，左側和右側子集都違反了最大性條件。只有兩個集合的合併才被視為一個迴圈。

兩個邏輯迴圈也可能共享一個迴圈頭，但被 LLVM 視為單個迴圈

for (int i = 0; i < 128; ++i)
  for (int j = 0; j < 128; ++j)
    body(i,j);

這在 LLVM-IR 中可以表示如下。請注意，只有一個迴圈頭，因此只有一個迴圈。

LoopSimplify pass 會檢測迴圈並確保外部迴圈和內部迴圈有各自的迴圈頭。

CFG 中的循環並不意味著存在迴圈。下面的例子顯示了這樣一個 CFG，其中沒有一個迴圈頭節點支配循環中的所有其他節點。這稱為**不可簡化控制流程**。

「可簡化」一詞源於將 CFG 摺疊成單個節點的能力，方法是連續地用單個節點替換三種基本結構之一：基礎區塊的順序執行、非循環條件分支（或 switch 語句）以及自身循環的基礎區塊。維基百科對此有更正式的定義，基本上就是說每個循環都有一個支配性的迴圈頭。

不可簡化控制流程可以出現在迴圈嵌套的任何級別。也就是說，一個本身不包含任何迴圈的迴圈在其主體中仍然可以有循環控制流程；一個沒有嵌套在另一個迴圈中的迴圈仍然可以是外部循環的一部分；並且在任何兩個迴圈之間（其中一個包含在另一個迴圈中）可以有額外的循環。但是，LLVM 循環涵蓋了迴圈和不可簡化控制流程。
FixIrreducible pass 可以通過插入新的迴圈頭將不可簡化控制流程轉換為迴圈。它不包含在任何默認的優化 pass pipeline 中，但某些後端目標需要它。
退出邊緣並不是跳出迴圈的唯一方法。其他可能性包括不可達終止符、[[noreturn]] 函數、異常、信號和電腦的電源按鈕。
迴圈“內部”沒有路徑返回迴圈（即返回迴圈尾或迴圈頭）的基礎區塊不被視為迴圈的一部分。以下代碼說明了這一點。

for (unsigned i = 0; i <= n; ++i) {
  if (c1) {
    // When reaching this block, we will have exited the loop.
    do_something();
    break;
  }
  if (c2) {
    // abort(), never returns, so we have exited the loop.
    abort();
  }
  if (c3) {
    // The unreachable allows the compiler to assume that this will not rejoin the loop.
    do_something();
    __builtin_unreachable();
  }
  if (c4) {
    // This statically infinite loop is not nested because control-flow will not continue with the for-loop.
    while(true) {
      do_something();
    }
  }
}

不要求控制流程最終離開迴圈，即迴圈可以是無限的。**靜態無限迴圈**是指沒有退出邊緣的迴圈。**動態無限迴圈**具有退出邊緣，但有可能永遠不會被採用。這可能只會在某些情況下發生，例如以下代碼中的 n == UINT_MAX 時。

for (unsigned i = 0; i <= n; ++i)
  body(i);

最佳化器可能會將動態無限迴圈轉換為靜態無限迴圈，例如，當它可以證明退出條件始終為假時。由於永遠不會採用退出邊緣，因此最佳化器可以將條件分支更改為無條件分支。

如果使用 llvm.loop.mustprogress 中繼資料標註迴圈，則編譯器可以假設它最終會終止，即使它無法證明這一點。例如，它可能會移除主體中没有任何副作用的 mustprogress 迴圈，即使程式可能會永遠卡在該迴圈中。諸如 C 和 C++ 等語言對某些迴圈具有此類正向進度保證。另請參閱 mustprogress 和 willreturn 函式屬性，以及較舊的 llvm.sideeffect 內建函式。

離開迴圈之前迴圈標頭的執行次數是**迴圈執行次數**（或**迭代次數**）。如果根本不應執行迴圈，則**迴圈防護**必須跳過整個迴圈

由於迴圈標頭可能做的第一件事是檢查是否有另一個執行，如果沒有，則立即退出而不做任何工作（另請參閱旋轉迴圈），迴圈執行次數不是衡量迴圈迭代次數的最佳指標。例如，對於非正 n（在迴圈旋轉之前），以下程式碼的標頭執行次數為 1，即使根本沒有執行迴圈主體。

for (int i = 0; i < n; ++i)
  body(i);

更好的衡量標準是**後邊緣採用次數**，它是迴圈之前任何後邊緣被採用的次數。對於進入標頭的執行，它比執行次數少一。

迴圈資訊 ¶

迴圈資訊是用於獲取有關迴圈資訊的核心分析。以上給出的定義有一些關鍵含義，這些含義對於成功使用此介面非常重要。

迴圈資訊不包含有關非迴圈週期的資訊。因此，它不適用於任何需要完整的週期檢測才能確保正確性的演算法。
迴圈資訊提供了一個用於列舉所有頂級迴圈（例如，那些未包含在任何其他迴圈中的迴圈）的介面。從那裡，您可以遍歷根植於該頂級迴圈的子迴圈樹。
在最佳化過程中變得靜態不可達的迴圈*必須*從迴圈資訊中移除。如果由於某種原因無法做到這一點，則最佳化*需要*保留迴圈的靜態可達性。

迴圈簡化形式 ¶

迴圈簡化形式是一種規範形式，它使多種分析和轉換變得更簡單、更有效。它由迴圈簡化（-loop-simplify）過程確保，並在排程迴圈過程時由過程管理器自動添加。此過程在 LoopSimplify.h 中實現。當它成功時，迴圈具有

前標頭。
單個後邊緣（這意味著只有一個閂鎖）。
專用出口。也就是說，迴圈的任何出口區塊都沒有來自迴圈外部的前驅。這意味著所有出口區塊都由迴圈標頭控制。

迴圈封閉 SSA (LCSSA)¶

如果程式採用 SSA 形式，並且迴圈中定義的所有值僅在該迴圈內使用，則該程式採用迴圈封閉 SSA 形式。

以 LLVM IR 寫成的程式永遠是 SSA 格式，但不一定會是 LCSSA 格式。為了達成後者，對於每個跨越迴圈邊界的活躍值，會在每個結束區塊 [1] 插入單一入口 PHI 節點，以便在迴圈內「封閉」這些值。特別是，請考慮以下迴圈

c = ...;
for (...) {
  if (c)
    X1 = ...
  else
    X2 = ...
  X3 = phi(X1, X2);  // X3 defined
}

... = X3 + 4;  // X3 used, i.e. live
               // outside the loop

在內部迴圈中，X3 在迴圈內部定義，但在外部使用。在迴圈封閉 SSA 格式中，這將表示如下

c = ...;
for (...) {
  if (c)
    X1 = ...
  else
    X2 = ...
  X3 = phi(X1, X2);
}
X4 = phi(X3);

... = X4 + 4;

這仍然是有效的 LLVM；額外的 phi 節點純粹是冗餘的，但所有 LoopPass 都必須保留它們。此格式由 LCSSA (-lcssa) pass 確保，並在排程 LoopPass 時由 LoopPassManager 自動添加。在迴圈優化完成後，這些額外的 phi 節點將由 -instcombine 刪除。

請注意，結束區塊位於迴圈之外，那麼這樣的 phi 如何「封閉」迴圈內部的值，因為它在迴圈外部使用它？首先，對於 phi 節點，如 LangRef 中所述：「每個輸入值的使用都被認為發生在從相應的前驅區塊到當前區塊的邊緣上」。現在，到結束區塊的邊緣被認為是在迴圈之外，因為如果我們採用該邊緣，它顯然會將我們帶出迴圈。

但是，邊緣實際上不包含任何 IR，因此在原始碼中，我們必須選擇一個約定，即使用發生在當前區塊還是相應的前驅區塊中。出於 LCSSA 的目的，我們認為使用發生在後者（以便在內部考慮使用）[2]。

LCSSA 的主要好處是它簡化了許多其他迴圈優化。

首先，一個簡單的觀察是，如果需要查看所有外部使用者，則只需遍歷結束區塊中的所有（迴圈封閉）PHI 節點（另一種方法是掃描迴圈中所有指令的定義-使用鏈 [3]）。

然後，例如考慮對上述迴圈進行簡單迴圈切換。因為它是 LCSSA 格式，所以我們知道在迴圈內部定義的任何值都將僅在迴圈內部或在迴圈封閉 PHI 節點中使用。在這種情況下，唯一的迴圈封閉 PHI 節點是 X4。這意味著我們可以複製迴圈並相應地更改 X4，如下所示

c = ...;
if (c) {
  for (...) {
    if (true)
      X1 = ...
    else
      X2 = ...
    X3 = phi(X1, X2);
  }
} else {
  for (...) {
    if (false)
      X1' = ...
    else
      X2' = ...
    X3' = phi(X1', X2');
  }
}
X4 = phi(X3, X3')

現在，X4 的所有使用都將獲得更新值（通常，如果迴圈是 LCSSA 格式，則在任何迴圈轉換中，我們只需要更新迴圈封閉 PHI 節點即可使更改生效）。如果我們沒有迴圈封閉 SSA 格式，則意味著 X3 可能在迴圈外部使用。因此，我們必須引入 X4（即新的 X3）並將 X3 的所有使用替換為它。但是，我們應該注意，因為 LLVM 為每個值保留了一個定義-使用鏈 [3]，所以我們不需要執行數據流分析來查找和替換所有使用（甚至有一個實用函數 replaceAllUsesWith()，它通過迭代定義-使用鏈來執行此轉換）。

另一個重要優勢是歸納變數的所有使用的行為都是相同的。如果沒有這個，您需要區分在定義變數的迴圈外部使用變數的情況，例如

for (i = 0; i < 100; i++) {
  for (j = 0; j < 100; j++) {
    k = i + j;
    use(k);    // use 1
  }
  use(k);      // use 2
}

從具有普通 SSA 形式的外層迴圈來看，第一次使用 k 的行為不佳，而第二次使用是基數為 100 且步長為 1 的歸納變數。儘管在實務上以及 LLVM 環境中，SCEV 可以有效處理此類情況。純量演化（scalar-evolution）或 SCEV 是一種（分析）遍歷，用於分析和分類迴圈中純量表達式的演化。

一般來說，在 LCSSA 形式的迴圈中使用 SCEV 會更容易。根據定義，SCEV 可以分析的純量（迴圈變數）表達式的演化是相對於迴圈的。表達式在 LLVM 中由 llvm::Instruction 表示。如果表達式位於兩個（或多個）迴圈內（這只有在迴圈嵌套時才會發生，如上例所示），並且您想要從 SCEV 獲得其演化的分析，則您還必須指定相對於您想要的哪個迴圈。具體來說，您必須使用 getSCEVAtScope()。

但是，如果所有迴圈都採用 LCSSA 形式，則每個表達式實際上由兩個不同的 llvm::Instructions 表示。一個在迴圈內，一個在迴圈外，後者是迴圈結束 PHI 節點，表示最後一次迭代後表達式的值（實際上，我們將每個迴圈變數表達式分解為兩個表達式，因此每個表達式最多只在一個迴圈中）。您現在只需使用 getSCEV() 即可。您傳遞給它的這兩個 llvm::Instructions 中的哪一個消除了環境/範圍/相對迴圈的歧義。

註腳

[2]

將 PHI 入口值的用途視為位於相應的前驅節點中是整個 LLVM 中的慣例。原因主要是實用的；例如，它保留了 SSA 的支配性。它也只不過是實際使用次數的過度估計；進入區塊可能會分支到另一個區塊，在這種情況下，該值實際上並未使用，但沒有副作用（它可能會增加其活動範圍，這與 LCSSA 無關）。此外，如果我們考慮活躍性，我們可以獲得一些直覺：通常在當前區塊中插入 PHI，因為從這一點開始就不能再使用該值（即當前區塊是一個支配邊界）。考慮到該值在當前區塊中使用（由於 PHI）是沒有意義的，因為該值在 PHI 之前就停止活躍了。從某種意義上說，PHI 定義只是“替換”了原始值的定義，並沒有真正使用它。應該強調的是，這個比喻僅僅是一個例子，並不構成任何嚴格的要求。例如，該值可能支配當前區塊，但我們仍然可以插入一個 PHI（就像我們對 LCSSA PHI 節點所做的那樣），並在之後使用原始值（在這種情況下，兩個活動範圍重疊，儘管在 LCSSA 中（重點是）我們從不這樣做）。

“更多規範”迴圈 ¶

旋轉迴圈 ¶

迴圈由 LoopRotate (loop-rotate) 遍歷旋轉，該遍歷將迴圈轉換為 do/while 風格的迴圈，並在 LoopRotation.h 中實現。範例

void test(int n) {
  for (int i = 0; i < n; i += 1)
    // Loop body
}

轉換為

void test(int n) {
  int i = 0;
  do {
    // Loop body
    i += 1;
  } while (i < n);
}

警告：只有在編譯器可以證明迴圈主體至少會被執行一次的情況下，這種轉換才有效。否則，它必須插入一個在運行時測試它的防護。在上面的例子中，那將是

void test(int n) {
  int i = 0;
  if (n > 0) {
    do {
      // Loop body
      i += 1;
    } while (i < n);
  }
}

了解迴圈旋轉在 LLVM IR 層級的影響非常重要。我們將繼續使用 LLVM IR 中的先前範例，同時提供控制流程圖 (CFG) 的圖形表示。您可以透過使用 view-cfg Pass 來獲得相同的圖形結果。

初始的 for 迴圈可以轉換為

define void @test(i32 %n) {
entry:
  br label %for.header

for.header:
  %i = phi i32 [ 0, %entry ], [ %i.next, %latch ]
  %cond = icmp slt i32 %i, %n
  br i1 %cond, label %body, label %exit

body:
  ; Loop body
  br label %latch

latch:
  %i.next = add nsw i32 %i, 1
  br label %for.header

exit:
  ret void
}

_images/loop-terminology-initial-loop.png

在我們解釋 LoopRotate 將如何實際轉換這個迴圈之前，以下說明我們如何（手動）將其轉換為 do-while 風格的迴圈。

define void @test(i32 %n) {
entry:
  br label %body

body:
  %i = phi i32 [ 0, %entry ], [ %i.next, %latch ]
  ; Loop body
  br label %latch

latch:
  %i.next = add nsw i32 %i, 1
  %cond = icmp slt i32 %i.next, %n
  br i1 %cond, label %body, label %exit

exit:
  ret void
}

_images/loop-terminology-rotated-loop.png

請注意兩件事

條件檢查已移至迴圈的「底部」，即 latch。這是 LoopRotate 透過將迴圈的 header 複製到 latch 來完成的。
在這種情況下，編譯器無法推斷迴圈一定會至少執行一次，因此上述轉換無效。如上面所述，必須插入一個防護，這是 LoopRotate 將會做的事情。

這就是 LoopRotate 轉換這個迴圈的方式

define void @test(i32 %n) {
entry:
  %guard_cond = icmp slt i32 0, %n
  br i1 %guard_cond, label %loop.preheader, label %exit

loop.preheader:
  br label %body

body:
  %i2 = phi i32 [ 0, %loop.preheader ], [ %i.next, %latch ]
  br label %latch

latch:
  %i.next = add nsw i32 %i2, 1
  %cond = icmp slt i32 %i.next, %n
  br i1 %cond, label %body, label %loop.exit

loop.exit:
  br label %exit

exit:
  ret void
}

_images/loop-terminology-guarded-loop.png

結果比我們預期的要複雜一些，因為 LoopRotate 確保迴圈在旋轉後處於迴圈簡化形式。在這種情況下，它插入了 %loop.preheader 基本區塊，以便迴圈有一個 preheader，並且引入了 %loop.exit 基本區塊，以便迴圈有專用的出口（否則，將從 %latch 和 %entry 跳轉到 %exit，但 %entry 不包含在迴圈中）。請注意，迴圈必須先處於迴圈簡化形式，才能成功應用 LoopRotate。

這種形式的主要優點是它允許將不變指令（尤其是加載）提升到 preheader 中。這在非旋轉迴圈中也可以做到，但也有一些缺點。讓我們用一個例子來說明它們

for (int i = 0; i < n; ++i) {
  auto v = *p;
  use(v);
}

我們假設從 p 加載是不變的，並且 use(v) 是一些使用 v 的語句。如果我們只想執行一次加載，我們可以將其移出迴圈體，結果如下

auto v = *p;
for (int i = 0; i < n; ++i) {
  use(v);
}

但是，現在，如果 n <= 0，在初始形式中，迴圈體將永遠不會執行，因此加載也永遠不會執行。這主要是語義上的問題。考慮 n <= 0 且從 p 加載無效的情況。在初始程式中，不會有任何錯誤。但是，透過這種轉換，我們會引入一個錯誤，有效地破壞了初始語義。

為了避免這兩個問題，我們可以插入一個防護

if (n > 0) {  // loop guard
  auto v = *p;
  for (int i = 0; i < n; ++i) {
    use(v);
  }
}

這當然更好，但可以稍微改進一下。請注意，對 n 是否大於 0 的檢查執行了兩次（並且 n 在兩次檢查之間沒有變化）。一次是在我們檢查防護條件時，另一次是在迴圈的第一次執行時。為了避免這種情況，我們可以進行無條件的第一次執行，並在最後插入迴圈條件。這實際上意味著將迴圈轉換為 do-while 迴圈

if (0 < n) {
  auto v = *p;
  do {
    use(v);
    ++i;
  } while (i < n);
}

請注意，LoopRotate 通常不會進行此類提升。相反，它是其他 Pass（如迴圈不變代碼移動（-licm））的啟用轉換。

文件

參與

其他連結

本頁