LLVM 循环术语

循环

循环是 LLVM 循环 的推广，递归定义如下 [HavlakCycles]

  1. 在一个有向图 G 中，它是一个函数 CFG 或其子图，循环 是一个最大强连通区域，至少有一条内部边。（信息说明——至少有一条内部边的要求确保单个基本块仅当存在一条返回到相同基本块的边时才是一个循环。）

  2. 循环中一个可以从函数入口沿一条不访问循环中任何其他基本块的路径到达的基本块称为循环的入口。一个循环可以有多个入口。

  3. 对于从函数入口开始的给定深度优先搜索，第一个被访问的循环节点称为相对于此特定 DFS 的此循环的头。头始终是入口节点。

  4. 在从入口开始的任何深度优先搜索中，在 CFG 中找到的循环集都是相同的。这些是顶级循环，它们本身没有父循环。

  5. 嵌套在以 H 为头的循环 C 内部的子循环（或简称为循环）是子图上节点集 (C - H) 中的循环。C 被称为这些循环的父循环。

因此，循环形成一个实现定义的森林，其中每个循环 C 都是其内部嵌套的任何子循环的父循环。该树紧密遵循同一函数中循环的嵌套。可约循环（LLVM 循环）L 的唯一入口支配其所有其他节点，并且始终选择作为某个循环 C 的头，无论使用哪个 DFS 树。该循环 C 是循环 L 的超集。对于不可约循环，没有一个入口支配循环的节点。其中一个入口以实现定义的方式被选为循环的头。

如果一个循环具有多个入口，则该循环是不可约的，否则它是可约的。

如果基本块 B 出现在循环 C 中但不出现在 C 的任何子循环中，则称循环 C 是基本块 B 的父循环。然后也称 B 为循环 C 的子节点。

如果一个块 B 不是任何循环的子节点，则称其为顶级块。

如果两个基本块或循环 X 和 Y 都没有父循环或具有相同的父循环，则称 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，则存在一个包含 P 但不包含 D 的循环 C。

    证明：根据上述属性，D 支配 P 中的所有节点。对于实现定义的 DFS 发现的任何循环嵌套，考虑包含 P 的最小循环 C。为了反证，假设 D 在 C 中。则 C 的头 H 不能在 P 中，因为循环的头不能被循环中的任何其他节点支配。因此，P 在集合 (C-H) 中，并且 C 中必须存在一个更小的循环 C' 也包含 P，但这与我们如何选择 C 相矛盾。

  3. 如果一个闭合路径 P 包含节点 U1 和 U2 但不包含它们的支配者 D1 和 D2，则存在一个包含 U1 和 U2 但不包含 D1 和 D2 中任何一个的循环 C。

    证明：根据上述属性，每个 D1 和 D2 分别支配 P 中的每个节点。存在一个包含 P 但不包含 D1（分别为 D2）的循环 C1（分别为 C2）。C1 和 C2 要么是同一个循环，要么其中一个嵌套在另一个循环中。因此，始终存在一个包含 U1 和 U2 但不包含 D1 和 D2 中任何一个的循环。

  1. 在任何循环层次结构中，包含闭合路径 P 的最小循环 C 的头 H 本身位于 P 上。

    证明：如果 H 不在 P 中，则集合 C - H 中存在一个更小的循环 C' 包含 P，从而与 C 是此类最小循环的说法相矛盾。

可约循环头

尽管循环层次结构取决于所选择的 DFS，但可约循环满足以下不变式

如果在任何 DFS 中发现了以 H 为头的可约循环 C，则在每个以 H 为头的 DFS 中都存在一个循环 C'，它包含 C。

证明：对于通过 H 经过 C 中的闭合路径 P，每个循环层次结构都具有一个包含 P 且其头在 P 中的最小循环 C'。由于 H 是 P 的唯一入口，因此 H 必须是 C' 的头。由于头唯一地定义了循环，因此 C' 包含每个这样的闭合路径 P，因此 C' 包含 C。