LLVM循环术语（和规范形式）

原文链接：LLVM Loop Terminology (and Canonical Forms) — LLVM 10 documentation，本文翻译时版本：https://archive.is/W68H8，基于CC BY-NC-SA 4.0协议发布

介绍

循环在任何优化器中都是一个核心概念。本页面阐明了LLVM代码中用于描述循环结构的一些常用术语。

首先，让我们从基础开始。在LLVM中，循环是在控制流图（CFG）中形成强连接分量（SCC）的最大基本块集，其中存在专用的入口/头块，该入口/头块控制着循环中的所有其他块。因此，无需离开循环，就可以从头块到达循环中的每个块，并从循环中的每个块到达头块。

注意本定义有一些重要的隐含信息：

并非所有强连接分量都是循环。存在不符合控制要求的强连接分量，因此不将其视为循环。
循环可以包含非循环强连接分量，非循环强连接分量可以包含循环。循环也可以包含子循环。
头块与一个循环唯一关联。该循环中可以有多个强连接分量，但是由它们的并集形成的强连接分量必须始终是唯一的。
对于本定义中的“控制”的使用，所有的循环都是自函数的入口静态可达的。（原文：Given the use of dominance in the definition, all loops are statically reachable from the entry of the function.请求更好翻译）
每个循环都必须有一个头块，以及循环外的一些前驱。循环允许是静态地无限循环的，因此不需要任何退出边缘。
任何两个循环要么完全不相交（没有相交的块），要么一个循环必须是另一个循环的子循环。
函数中的循环形成森林。这一事实的一个暗示是，循环要么没有亲代，要么仅有一个亲代。

循环可以有任意数量的退出，无论是显式退出（通过控制流）还是隐式退出（通过引发将控制从包含的函数中移出的调用）。对出口块（分支之外的循环块）的形式或结构没有特殊要求。他们可能有多个前驱，phi等。

关键术语

头块（Header Block） – 控制循环中包含的所有其他块的基本块。因此，如果循环执行了，它将是第一个被执行的。注意一个块可以同时是两个单独的循环的头块，但前提是一个是另一个的子循环。

退出块（Exiting Block） – 给定循环中包含的一种基本块，该基本块在循环外至少有一个后继，以及在循环内至少有一个后继。（后者是由于该块包含在作为循环一部分的强连接分量内的结果。）也就是说，它具有一个后继，即出口块。

出口块（Exit Block） – 相关循环外部的一种基本块，在循环内部具有前驱。即它的前驱是退出块。

闩锁块（Latch Block） – 循环中的一种基本块，其后继包括循环的头块。因此，闩锁是返回边的来源。循环可以具有多个闩锁块。闩锁块可以是条件的，也可以是无条件的。

返回边（Backedge(s)） – 控制流图中从闩锁块到头块的边。注意，可以有多个这样的边，甚至可以有多个这样的从闩锁块离开的边。

循环前驱（Loop Predecessor） – 循环头的前驱块不包含在循环本身中。这些是通过执行可以进入循环的唯一块。当以单数形式使用时，意味着只有唯一一个这样的块。

Preheader块（Preheader Block） – Preheader是一个（单一）循环的前驱，其以无条件地将控制转移到循环头结束。请注意，并非所有循环都具有此类块。

返回边被使用数（Backedge Taken Count） – 返回边将要在某些关注的事件发生之前执行的次数。通常在不限定事件的情况下用作某些退出块分支到某个退出块的简写。它可能为零，或者并非静态可计算的。

迭代数（Iteration Count） – 循环头在发生某些关注的事件之前执行的次数。通常不加限定地使用，指的是循环退出时的迭代数。将始终比所采用的返回边被使用数大一。警告：此句在整数域中为真；如果要处理定宽整数（例如LLVM值或SCEV），则在将一个转换为另一个时需要谨慎。

要注意，同一基本块可以在同一循环中或同时在不同循环中扮演多个角色。例如，一个块可以一次成为两个嵌套循环的头，同时也可以仅是一个内部循环的退出块和一个同级循环的出口块。例：

while (..) {
  for (..) {}
  do {
    do {
      // <-- 需关注的块
      if (exit) break;
    } while (..);
  } while (..)
}

LoopInfo

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

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

循环简化形式（Loop Simplify Form）

循环简化形式是一种规范的形式，它使多项分析和转换更简单，更有效。它由LoopSimplify（-loop-simplify）pass确保，并且在调度LoopPass时由传递管理器自动添加。此过程在LoopSimplify.h中实现。成功后，循环将具有：

一个Preheader
单个的返回边（这意味着只有一个闩锁）。
专用出口。即该循环的任何出口块都没有位于循环外部的前驱。这意味着所有出口块都由循环头控制。

循环封闭SSA (Loop Closed SSA，LCSSA)

如果程序为SSA形式，并且该程序在循环中定义的所有值仅在此循环内使用，则该程序为“循环封闭SSA形式”。用LLVM IR编写的程序始终采用SSA形式，但不一定采用LCSSA。要实现后者，需在循环末尾为存活到跨越循环边界的所有值插入一个PHI节点¹。特别是，请考虑以下循环：

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

... = X3 + 4;  // 使用了X3，即存活到了循环外部

在内部循环中，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节点（替代方法是扫描循环中所有指令的def-use链²）。

然后，考虑-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），并用X4替代X3的所有使用。但是，我们应该注意，因为LLVM为每个Value保留了一个def-use链，所以我们不需要执行数据流分析来查找和替换所有使用（甚至还有一个实用函数，replaceAllUsesWith()，它通过迭代def-use链来执行此转换）。

另一个重要的优点是，归纳变量（induction variable）的所有使用的行为都是相同的。否则，需要区分在变量被定义的循环之外使用变量的情况，例如：

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

从具有常规SSA形式的外部循环看，第一次使用k行为不正确，而第二次使用是一个基数为100、步数为1的归纳变量（译注：即i + 100，100是j迭代完成后的值）。尽管在实践中和LLVM上下文中，此类情况SCEV实际上是可以处理的。标量演化（scalar-evolution）又称SCEV，是一种（分析）Pass，它对循环中标量表达式的演化进行分析和分类。

通常，在LCSSA形式的循环中使用SCEV更容易。根据定义，SCEV可以分析的标量（循环可变的）表达式的演化是相对于循环的。LLVM中的表达式由llvm::Instruction表示。如果表达式位于两个（或多个）循环内（仅在循环嵌套的情况下才可能发生，如上例所示），并且想要分析其演化（从SCEV），则还必须指定相对于你想要的什么循环。具体来说，必须使用getSCEVAtScope()。

但是，如果所有循环都是LCSSA形式，则每个表达式实际上由两个不同的llvm::Instructions表示。一个在循环内部，一个在循环外部，它是循环封闭的PHI节点，代表最后一次迭代后表达式的值（实际上，我们将每个循环可变的表达式分成两个表达式，因此，每个表达式最多在一个循环中）。现在只要使用getSCEV()，然后通过传递给它的这两个llvm::Instructions中的那个来消除上下文/作用域/相对循环的歧义。

“更加规范”的循环

旋转循环（Rotated Loops）

循环通过LoopRotate（loop-rotate）旋转，该Pass将循环转换为do / while样式循环，并在LoopRotation.h中实现。例：

void test(int n) {
  for (int i = 0; i < n; i += 1)
    // 循环体
}

被转换到：

void test(int n) {
  int i = 0;
  do {
    // 循环体
    i += 1;
  } while (i < n);
}

警告：仅当编译器可以证明循环体至少执行一次时，此转换才有效。否则，它必须插入一个将在运行时对其进行测试的保护程序。在上面的示例中，将是：

void test(int n) {
  int i = 0;
  if (n > 0) {
    do {
      // 循环体
      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
}

在说明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
}

注意两件事：

将条件检查移至循环的“底部”，即闩锁。这是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
}

结果比我们预期的要复杂一些，因为LoopRotate确保旋转后循环处于“循环简化形式”。在这种情况下，它插入％loop.preheader基本块，以便该循环具有一个Preheader，并引入了％loop.exit基本块，以便该循环具有专用出口（否则，％exit将从％latch和％entry跳转到，但循环中不包含％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) {  // 循环防护
  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的一种使能转换（Enabling transformation）（如循环不变代码移动（-licm））。