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

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

本文是LLVM官方文档中关于循环术语和规范形式的详细介绍。文章深入讲解了循环的基本概念、LoopInfo分析、循环简化形式、LCSSA（循环闭合SSA）以及循环旋转等主题。通过具体的代码示例和详细的解释，帮助读者理解这些概念在LLVM中的具体实现和应用。

循环定义

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

循环是控制流图（CFG；其中节点代表基本块）中节点的子集，具有以下属性：

• 诱导子图（它是包含循环内CFG中所有边的子图）是强连通的（每个节点都可以从所有其他节点到达）。
• 从子集外部到子集内部的所有边都指向同一个节点，称为头部。因此，头部支配循环中的所有节点（即，到达循环中任何节点的每条执行路径都必须经过头部）。
• 循环是具有这些属性的最大子集。也就是说，不能添加来自CFG的其他节点，使得诱导子图仍然是强连通的，并且头部保持不变。

在计算机科学文献中，这通常被称为自然循环。在LLVM中，更广义的定义称为环。

术语

循环的定义附带一些附加术语：

• 进入块（或循环前驱）是一个非循环节点，它有一条进入循环的边（必然是头部）。如果只有一个进入块，并且其唯一的边是指向头部的，则它也称为循环的前置头部。前置头部支配循环，但本身不是循环的一部分。
• 锁存器是一个循环节点，它有一条指向头部的边。
• 回边是从锁存器到头部的边。
• 退出边是从循环内部到循环外部节点的边。这种边的源节点称为退出块，其目标节点是出口块。

重要说明

此循环定义有一些值得注意的后果：

• 一个节点最多可以是一个循环的头部。因此，循环可以通过其头部来识别。由于头部是进入循环的唯一入口，因此它可以被称为单入口多出口（SEME）区域。
• 对于从函数的入口不可达的基本块，循环的概念是未定义的。这遵循支配概念也是未定义的。
• 最小的循环由一个分支到自身的基本块组成。在这种情况下，该块同时是头部、锁存器（以及退出块，如果它有另一条边到不同的块）。一个没有分支到自身的基本块不被认为是循环，即使它是平凡地强连通的。
• 循环可以相互嵌套。也就是说，一个循环的节点集可以是另一个具有不同循环头部的循环的子集。函数中的循环层次结构形成一个森林：每个顶层循环都是嵌套在其中的循环树的根。
• 两个循环不可能只共享它们的一些节点。两个循环要么是不相交的，要么一个嵌套在另一个内部。在下面的示例中，左侧和右侧子集都违反了最大性条件。只有两个集合的合并才被认为是循环。
• 两个逻辑循环也可能共享一个头部，但被LLVM视为单个循环
• CFG中的环并不意味着存在循环。下面的示例显示了这样一个CFG，其中没有支配环中所有其他节点的头部节点。这被称为不可约控制流。术语可约性源于通过连续用单个节点替换以下三个基本结构之一来将CFG折叠成单个节点的能力：基本块的顺序执行、非循环条件分支（或开关）以及基本块自身循环。维基百科有更正式的定义，它基本上是说每个环都有一个支配头部。
• 不可约控制流可能发生在循环嵌套的任何级别。也就是说，本身不包含任何循环的循环在其主体中仍然可能具有循环控制流；未嵌套在另一个循环内的循环仍然可能是外部循环的一部分；并且在其中一个包含在另一个循环中的任意两个循环之间可能存在其他环。但是，LLVM环涵盖了循环和不可约控制流。
• FixIrreduciblePass可以通过插入新的循环头部将不可约控制流转换为循环。它不包含在任何默认优化Pass管道中，但某些后端目标需要它。
• 退出边不是跳出循环的唯一方法。其他可能性包括不可达的终止符、[[noreturn]]函数、异常、信号和计算机的电源按钮。
• “在”循环“内部”且没有返回循环的路径（即到锁存器或头部）的基本块不被视为循环的一部分。以下代码说明了这一点。
• 控制流没有最终离开循环的要求，即循环可以是无限的。静态无限循环是没有退出边的循环。动态无限循环有退出边，但有可能永远不会被执行。这可能仅在某些情况下发生，例如当代码中的n == UINT_MAX时。

优化器可以将动态无限循环转换为静态无限循环，例如，当它可以证明退出条件始终为假时。由于永远不会执行退出边，因此优化器可以将条件分支更改为无条件分支。

如果循环使用llvm.loop.mustprogress元数据进行注释，则编译器允许假设它最终会终止，即使它无法证明这一点。例如，即使程序可能永远停留在该循环中，它也可能会删除主体中没有任何副作用的mustprogress循环。C和C++等语言对于某些循环具有此类前向进度保证。另请参阅mustprogress和willreturn函数属性，以及较旧的llvm.sideeffect内在函数。

• 循环头部在离开循环之前执行的次数是循环迭代次数（或迭代计数）。如果循环根本不应执行，则循环守卫必须跳过整个循环

由于循环头部可能做的第一件事是检查是否还有另一次执行，如果没有，则立即退出而不做任何工作（另请参阅旋转循环），因此循环迭代次数不是衡量循环迭代次数的最佳指标。例如，对于非正数n（在循环旋转之前）的以下代码，头部执行次数为1，即使循环体根本没有执行。

更好的度量是回边执行计数，它是循环之前执行任何回边的次数。对于进入头部的执行，它比迭代次数少一次。

LoopInfo

LoopInfo是获取循环信息的关键分析。上述定义的一些关键含义对于成功使用此接口非常重要：

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

循环简化形式

循环简化形式是一种规范形式，它使多个分析和转换更简单、更有效。它由LoopSimplify(-loop-simplify)Pass确保，并在调度LoopPass时由Pass管理器自动添加。此Pass在LoopSimplify.h中实现。当它成功时，循环具有：

• 前置头部。
• 单个回边（这意味着只有一个锁存器）。
• 专用出口。也就是说，循环的任何出口块都没有循环外部的前驱。这意味着所有出口块都由循环头部支配。

循环闭合SSA(LCSSA)

如果程序采用SSA形式，并且在循环中定义的所有值仅在该循环内部使用，则该程序处于循环闭合SSA形式。

以LLVM IR编写的程序始终采用SSA形式，但不一定采用LCSSA形式。为了实现后者，对于每个跨循环边界存活的值，在每个出口块中插入单入口PHI节点，以便在循环内“闭合”这些值。特别是，考虑以下循环：

在内部循环中，X3在循环内部定义，但在循环外部使用。在循环闭合SSA形式中，这将表示为如下：

这仍然是有效的LLVM；额外的phi节点是纯粹冗余的，但所有LoopPass都要求保留它们。此形式由LCSSA(-lcssa)Pass确保，并在调度LoopPass时由LoopPassManager自动添加。在循环优化完成后，这些额外的phi节点将由-instcombine删除。

请注意，出口块位于循环外部，那么这样的phi如何“闭合”循环内部的值，因为它在循环外部使用它？首先，对于phi节点，如LangRef中所述：“每个传入值的使用都被认为发生在从相应的前驱块到当前块的边上”。现在，到出口块的边被认为在循环外部，因为如果我们采用该边，它会清楚地将我们引出循环。但是，边实际上不包含任何IR，因此在源代码中，我们必须选择一个约定，即使用发生在当前块还是在前驱块中。对于LCSSA的目的，我们认为使用发生在后者中（以便将使用视为内部）。

LCSSA的主要好处是它使许多其他循环优化更简单。首先，一个简单的观察是，如果需要查看所有外部用户，他们可以只迭代出口块中的所有（循环闭合）PHI节点（另一种方法是扫描循环中所有指令的def-use链）。然后，例如考虑simple-loop-unswitch上面的循环。因为它采用LCSSA形式，我们知道在循环内部定义的任何值都将仅在循环内部或循环闭合PHI节点中使用。在这种情况下，唯一的循环闭合PHI节点是X4。这意味着我们可以只复制循环并相应地更改X4，如下所示：

现在，X4的所有使用都将获得更新后的值（一般来说，如果循环采用LCSSA形式，在任何循环转换中，我们只需要更新循环闭合PHI节点即可使更改生效）。如果我们没有循环闭合SSA形式，这意味着X3可能在循环外部使用。因此，我们将不得不引入X4（它是新的X3）并将X3的所有使用替换为它。但是，我们应该注意到，由于LLVM为每个Value保留了def-use链，我们不需要执行数据流分析来查找和替换所有使用（甚至有一个实用函数replaceAllUsesWith()，它通过迭代def-use链来执行此转换）。

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

从具有正常SSA形式的外部循环来看，k的第一次使用行为不端，而第二次使用是基数为100，步长为1的归纳变量。虽然在实践中和LLVM上下文中，此类情况可以通过SCEV有效处理。标量演化（scalar-evolution）或SCEV，是一个（分析）Pass，用于分析和分类循环中标量表达式的演化。

一般来说，在采用LCSSA形式的循环中使用SCEV更容易。SCEV可以分析的标量（循环变体）表达式的演化，根据定义，是相对于循环的。表达式在LLVM中由llvm::Instruction表示。如果表达式在两个（或更多）循环内（这只能在循环嵌套时发生，如上面的示例所示），并且您想获得对其演化（来自SCEV）的分析，则还必须指定相对于哪个循环。具体来说，您必须使用getSCEVAtScope()。

但是，如果所有循环都采用LCSSA形式，则每个表达式实际上由两个不同的llvm::Instruction表示。一个在循环内部，一个在循环外部，它是循环闭合PHI节点，表示表达式在最后一次迭代后的值（实际上，我们将每个循环变体表达式分解为两个表达式，因此，每个表达式最多在一个循环中）。您现在可以只使用getSCEV()。并且您传递给它的这两个llvm::Instruction中的哪一个消除了上下文/作用域/相关循环的歧义。

脚注：

• 要插入这些循环闭合PHI节点，必须（重新）计算支配边界（如果循环有多个出口）。
• 将PHI条目值的使用点视为在相应的前驱中是整个LLVM中的约定。原因主要是实际的；例如，它保留了SSA的支配属性。它也只是对实际使用次数的过度近似；传入块可能会分支到另一个块，在这种情况下，该值实际上未使用，但没有副作用（它可能会增加其生存期，但这在LCSSA中无关紧要）。此外，如果我们考虑活跃性，我们可以获得一些直觉：PHI通常插入在当前块中，因为从这一点开始，该值无法使用（即，当前块是支配边界）。认为该值在当前块中使用（由于PHI）是没有意义的，因为该值在PHI之前停止活跃。在某种意义上，PHI定义只是“替换”了原始值定义，实际上并没有使用它。应该强调的是，此类比仅用作示例，并不构成任何严格要求。例如，该值可能支配当前块，但我们仍然可以插入PHI（就像我们使用LCSSA PHI节点一样）并且之后使用原始值（在这种情况下，两个生存期范围重叠，尽管在LCSSA中（重点是）我们永远不会这样做）。
• SSA的一个属性是，每个定义都存在一个def-use链，它是此定义的所有使用的列表。LLVM通过在内部数据结构中保留Value的所有使用的列表来实现此属性。

“更规范”的循环

旋转循环

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

被转换为：

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

理解循环旋转在LLVM IR级别的效果非常重要。我们继续使用LLVM IR中的先前示例，同时还提供控制流图(CFG)的图形表示。您可以通过使用view-cfgPass获得相同的图形结果。

最初的for循环可以转换为：

在我们解释LoopRotate实际上将如何转换此循环之前，下面是我们如何（手动）将其转换为do-while样式循环。

注意两点：

• 条件检查已移至循环的“底部”，即锁存器。这是LoopRotate通过将循环的头部复制到锁存器来完成的。
• 在这种情况下，编译器无法推断出循环肯定会至少执行一次，因此上述转换无效。如上所述，必须插入一个守卫，这是LoopRotate将要做的。

这是LoopRotate转换此循环的方式：

结果比我们预期的要复杂一些，因为LoopRotate确保循环在旋转后处于循环简化形式。在这种情况下，它插入了%loop.preheader基本块，以便循环具有前置头部，并引入了%loop.exit基本块，以便循环具有专用出口（否则，%exit将从%latch和%entry跳转，但%entry不包含在循环中）。请注意，循环也必须预先处于循环简化形式，LoopRotate才能成功应用。

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

我们假设从p加载是不变的，use(v)是使用v的一些语句。如果我们只想执行一次加载，我们可以将其“移出”循环体，从而得到如下结果：

但是，现在，在n <= 0的情况下，在初始形式中，循环体永远不会执行，因此，加载永远不会执行。这主要是语义原因的问题。考虑n <= 0且从p加载无效的情况。在初始程序中，不会出现错误。但是，通过这种转换，我们将引入一个错误，从而有效地破坏初始语义。

为了避免这两个问题，我们可以插入一个守卫：

这当然更好，但可以稍微改进一下。请注意，检查n是否大于0执行了两次（并且n在两者之间没有变化）。一次是在我们检查守卫条件时，一次是在循环的第一次执行中。为了避免这种情况，我们可以进行无条件的第一次执行，并将循环条件插入到末尾。这实际上意味着将循环转换为do-while循环：

请注意，LoopRotate通常不进行此类提升。相反，它是其他Pass（如循环不变代码移动(-licm)）的启用转换。