LLVM 循环术语（以及规范形式）¶

循环定义 ¶

循环是代码优化器中的一个重要概念。在 LLVM 中，控制流图 (CFG) 中循环的检测由 LoopInfo 完成。它基于以下定义。

循环是控制流图 (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 传递将检测循环并确保外部和内部循环有单独的头节点。

CFG 中的循环并不意味着存在循环。下面的示例显示了这样的 CFG，其中没有头节点支配循环中的所有其他节点。这称为**不可约控制流**。

术语“可约”源于能够通过依次将三种基本结构之一替换为单个节点来将 CFG 折叠成单个节点的能力：基本块的顺序执行、无环条件分支（或开关）以及自身循环的基本块。维基百科对此有一个更正式的定义，它基本上说每个循环都有一个支配头节点。

不可约控制流可以在循环嵌套的任何级别发生。也就是说，本身不包含任何循环的循环在其主体中仍然可能具有循环控制流；未嵌套在另一个循环内的循环仍然可以是外部循环的一部分；并且在任意两个循环之间可能存在其他循环，其中一个包含在另一个内部。但是，LLVM 循环涵盖了循环和不可约控制流。
FixIrreducible 传递可以通过插入新的循环头节点将不可约控制流转换为循环。它不包含在任何默认优化传递管道中，但某些后端目标需要它。
退出边不是退出循环的唯一方法。其他可能性包括不可到达的终止符、[[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);

更好的衡量标准是**后向边执行计数**，即所有后向边在循环之前执行的次数。对于进入头节点的执行，它比行程计数少 1。

LoopInfo ¶

LoopInfo 是获取循环信息的核心分析。上面给出的定义有一些关键含义，对于成功使用此接口非常重要。

LoopInfo 不包含有关非循环循环的信息。因此，它不适用于任何需要完整循环检测才能保证正确性的算法。
LoopInfo 提供了一个接口，用于枚举所有顶级循环（例如，那些不包含在任何其他循环中的循环）。从那里，您可以遍历以该顶级循环为根的子循环树。
在优化期间变得静态不可到达的循环**必须**从 LoopInfo 中删除。如果由于某种原因无法做到这一点，则优化**需要**保留循环的静态可达性。

循环简化形式 ¶

循环简化形式是一种规范形式，它使一些分析和转换更简单、更有效。它由 LoopSimplify (-loop-simplify) 传递确保，并在调度 LoopPass 时由传递管理器自动添加。此传递在 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) 遍会确保这种形式，并且在调度 LoopPass 时，LoopPassManager 会自动添加这些节点。在循环优化完成后，这些额外的 phi 节点将由 -instcombine 删除。

请注意，退出块位于循环之外，那么这样的 phi 如何“封闭”循环内部的值，因为它在循环外部使用了它呢？首先，对于 phi 节点，正如 LangRef 中所述：“每个传入值的用法被认为发生在从对应的前驱块到当前块的边上”。现在，到退出块的边被认为在循环之外，因为如果我们沿着这条边走，它会将我们带出循环。

但是，边实际上不包含任何 IR，因此在源代码中，我们必须选择一个约定，即使用是在当前块中还是在相应的前驱块中发生。为了 LCSSA 的目的，我们认为使用发生在后者（以便将使用视为在内部） [2]。

LCSSA 的主要好处是它使许多其他循环优化变得更简单。

首先，一个简单的观察结果是，如果需要查看所有外部使用者，他们只需遍历退出块中的所有（循环封闭）PHI 节点即可（另一种方法是扫描循环中所有指令的 def-use 链 [3]）。

然后，例如考虑 simple-loop-unswitch 上述循环。因为它处于 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 为每个 Value 保留了 def-use 链 [3]，所以我们不需要执行数据流分析来查找和替换所有使用（甚至有一个实用程序函数 replaceAllUsesWith()，它通过迭代 def-use 链来执行此转换）。

另一个重要的优势是所有归纳变量的使用行为都是相同的。如果没有这个，您需要区分变量在定义它的循环外部使用的情况，例如

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::Instruction 表示。一个在循环内部，一个在循环外部，它是循环封闭的 PHI 节点，表示最后一次迭代后表达式的值（实际上，我们将每个循环变量表达式分解成两个表达式，因此每个表达式最多在一个循环中）。您现在可以使用 getSCEV()。并且您传递给它的这两个 llvm::Instruction 中的哪一个会消除上下文/范围/相对循环的歧义。

脚注

[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 遍获得相同的图形结果。

初始的 **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

请注意两点

条件检查已移至循环的“底部”，即锁存器。这是 LoopRotate 通过将循环的头复制到锁存器来实现的。
在这种情况下，编译器无法推断出循环肯定至少执行一次，因此上述转换无效。如上所述，必须插入一个保护，这是 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 基本块，以便循环具有一个预头，并且它引入了 %loop.exit 基本块，以便循环具有专用的出口（否则，将从 %latch 和 %entry 跳到 %exit，但 %entry 不包含在循环中）。请注意，循环也必须事先处于循环简化形式才能成功应用 LoopRotate。

这种形式的主要优点是它允许将不变指令（尤其是加载）提升到预头。这也可以在非旋转循环中完成，但有一些缺点。让我们用一个例子来说明它们

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 通常不会执行此类提升。相反，它是其他遍（如循环不变代码移动 (-licm)）的启用转换。

文档

参与贡献

其他链接

本页