LLVM IR 中标签和间接跳转的地址
GCC 编译器支持一个有用的 "标签作为值" 扩展，允许代码获取标签的地址，然后在稍后执行一个无条件跳转到作为 void* 指定的地址。此扩展对于构建高效的解释器特别有用。LLVM 长期以来一直通过将其降低到“正确”但效率极低的形式来支持此扩展。LLVM 2.7 中的新增功能是 IR 支持获取标签的地址并在稍后跳转到该地址，这使得以更高效的方式实现此扩展成为可能。本文介绍了此新的 LLVM IR 功能及其工作原理。
在本讨论中，我将范围限制在仅考虑“局部”跳转。我们不会讨论 GCC 扩展意义上的非局部跳转：从嵌套函数跳转到外部函数。
标签地址扩展
在深入介绍新功能之前，我将介绍 GCC C 扩展以及 LLVM 2.6 及更早版本如何编译它。考虑以下代码（来自 PR3120）
static int fn(Opcodes opcodes) {
static const void *codetable[] =
{ &&RETURN, &&INCREMENT, &&DECREMENT, &&DOUBLE, &&SWAPWORD };
int result = 0;
goto *codetable[*(opcodes++)];
RETURN:
return result;
INCREMENT:
result++;
goto *codetable[*(opcodes++)];
DECREMENT:
result--;
goto *codetable[*(opcodes++)];
DOUBLE:
result <<= 1;
goto *codetable[*(opcodes++)];
SWAPWORD:
result = (result << 16) | (result >> 16);
goto *codetable[*(opcodes++)];
}
如您所见，代码使用 5 个标签的地址初始化 'codetable' 数组，然后通过计算出的指针跳转。
此扩展的一个有趣方面是，您允许对获取地址的标签执行的唯一操作是跳转到该标签。虽然它被广泛误用在其他方面（例如，linux 内核中的 BUG 宏，它在错误发生时打印标签的地址），但您真正真正只被允许跳转到它。您不允许在内联汇编中使用它、检查其值或执行任何其他操作。
LLVM 2.6 及更早版本
在 LLVM 2.6 及更早版本中，LLVM 充分利用了您不允许对该值执行除跳转到标签地址以外任何操作的事实。由于此扩展很少使用，我们不想为此扩展添加直接支持，因为它会增加 LLVM IR 的复杂性。相反，我们采用了一种非常简单的实现方法，它忠实地实现了扩展，但不需要任何新的 IR 功能。该方法很简单
- 当获取标签的地址时，该标签将被分配一个唯一的整数 ID（在其函数内），从 1 开始。获取标签的地址提供了此整数 ID，而不是标签的实际地址。
- 当看到间接 goto 时，我们将此结构降低为标准的 LLVM switch 指令。对于每个唯一分配的整数 ID，switch 将跳转到相应的标签。
static const void *codetable[] =
{ (void*)1, (void*)2, (void*)3, (void*)4, (void*)5 };
这显然没有提供指定标签的地址，但它确实为每个标签提供了唯一的 ID 号。有了它，间接 goto 被降低，就好像它被写成
switch (..) {
default: __builtin_unreachable();
case 1: goto RETURN;
case 2: goto INCREMENT;
case 3: goto DECREMENT:
case 4: goto DOUBLE;
case 5: goto SWAPWORD;
}
由于代码只被允许跳转到在当前函数中获取地址的标签（同样，不考虑非局部 goto），我们知道所有可能的目的地，并且可以将间接跳转编码为 switch。重申一下，这种方法的主要优点是它不需要任何 LLVM 扩展：switch 语句需要 LLVM IR switch 指令，因此在此重用它没有问题。
同样值得指出的是，虽然这种实现满足了扩展的字面意义，但它与扩展的意图相差甚远。除此之外，LLVM 2.6 实现的主要问题是生成的代码非常慢。
LLVM 2.7 及更高版本：blockaddress 和 indirectbr
虽然此扩展相对罕见，但使用它的情况非常重要。此扩展用于关键的解释器循环，在这些循环中，它可以提供相当大的优势（大约 15% 是典型的）。因此，LLVM 增加了能够以预期形式表示和编码生成此扩展的能力。此扩展使用两个新的 LLVM IR 功能
- 首先，获取标签的地址会生成一个新的 blockaddress 节点（由 LLVM BlockAddress 类表示）。
- 其次，通过地址跳转会生成一个新的 indirectbr 终止指令（IndirectBrInst 类）。
static const void *codetable[] =
{ blockaddress(@fn, %RETURN),
blockaddress(@fn, %INCREMENT),
blockaddress(@fn, %DECREMENT),
blockaddress(@fn, %DOUBLE),
blockaddress(@fn, %SWAPWORD)
};
在代码生成时，新的 blockaddress 常量实际上被降低为对它所对应到的 LLVM BasicBlock 的标签的引用。接下来，不是使用 switch，间接 goto 被编码生成到新的 'indirectbr' LLVM IR 指令中，如下所示
indirectbr i8* %address, [ label %RETURN, label %DOUBLE, label %INCREMENT, label %DECREMENT, label %SWAPWORD ]
虽然 blockaddress 常量相对简单，但您可能会惊讶地看到这里重复了所有标签。'indirectbr' 通常被降低为非常简单的机器代码：通过寄存器的机器级跳转。尽管有这种底层简单性，“indirectbr”指令的不变性是它必须包含（可能是超集）指令中所有可能的标签目标列表。跳转到未包含的标签是未定义的行为。指令中标签的顺序无关紧要，但标签的存在或不存在很重要。
此设计的含义
在将此功能添加到 LLVM 时，我们考虑了许多不同的方法，这些方法都有各种不同的权衡。与其描述所有可能的实现方法，不如我们只讨论通过考虑您可能提出的一组问题来了解此方法的一些含义
为什么 indirectbr 包含一个可能的 target block 列表？
我们在实现此新功能时最主要的担忧之一是，我们希望它能以尽可能少的特殊情况代码适应编译器的其他部分。一个特别重要的结构是控制流图 (CFG)，它是 LLVM 中所有数据流分析的基础。
在 LLVM 中，CFG 是使用 pred_iterator 和 succ_iterator 迭代器遍历的。succ_iterator非常简单，它只是遍历块末尾的 终止指令 的 BasicBlock 操作数。pred_iterator更难：它遍历 BasicBlock 的 use-def 链，并报告来自终止器的任何 use 作为前驱。
显然，为了使此扩展能够与这种方案一起使用，我们希望尽可能地遵循现有系统的工作方式。这意味着 indirectbr 具有一个可能的 target 列表使得后继迭代器非常简单（它只需遍历该列表即可获取可能的目的地）。第二个主要好处是这也修复了前驱迭代器：由于每个操作数都被视为一个 'use'，因此遍历获取地址的块的 use 列表将正常工作，因为将看到 indirectbr 的 use。
此扩展如何与 PHI 节点交互？
PHI 节点是根据 CFG 的属性定义的，因此它们根据上面描述的 CFG 行为正常工作，正如您所期望的那样。获取块本身的地址不会导致它有任何 PHI 节点。当 indirectbr 跳转到块时，获取地址的块将获得 PHI 节点条目。
为什么 blockaddress 是一个常量？
这很简单：BlockAddress IR 对象继承自 Constant，因为它需要能够用于初始化全局变量。全局变量初始化器必须是 Constant。
为什么 blockaddress 需要同时使用函数和 basic block 名称？
对此有两个答案。最明显的答案是 LLVM IR 并不像 C 代码那样嵌套。当使用标签的地址初始化静态变量时，该静态变量会像任何其他变量一样成为 LLVM 全局变量。如果全局变量中有一个对“foo”的引用，我们需要知道引用了哪个“foo”标签（因为每个函数都有自己的局部命名空间）。
第二个不太明显的答案是 LLVM IR 比 GCC C 扩展更通用：您被允许获取不同函数中块的地址。这种支持从我们需要初始化全局变量的支持中得出，并不明显有用，但它仍然存在。
此扩展如何与内联交互？
简单地说，LLVM 目前拒绝内联包含 indirectbr 的函数（GCC 也是如此）。在某些情况下，将来可能在某些情况下放松这种限制，但这将需要大量的分析。基本问题是内联 indirectbr 实际上是一件非常棘手的事情：除了将被调用者克隆到调用者中，我们还必须克隆所有引用调用者中块的 blockaddress 对象，以及克隆所有引用它们的对象。以下是在伪 IR 中的一个愚蠢的示例
static void *G = blockaddress(@foo, %bb);
void foo() {
goto *G;
bb:
return;
}
void bar() {
foo();
}
简单地将 foo 克隆到 bar 如下将不正确
static void *G = blockaddress(@foo, %bb);
void foo() {
goto *G;
bb: return;
}
void bar() {
goto *G;
bb:
return;
}
问题是 'bar' 会通过 G 跳转到在 'foo' 中定义的标签。从一个函数跳转到另一个函数是非法的。为了执行此内联，我们实际上必须克隆 G 本身。这样做是可能的，但不值得，特别是因为使用此扩展的大多数函数都是大型解释器循环。
此扩展如何与关键边分割交互？
很糟糕。
CFG 中的关键边是从具有多个后继者的块（例如，以条件分支结束的块）到具有多个前驱者的块（如 if/then/else 的合并点）的边。关键边对于各种代码移动变换来说是有问题的。在此扩展之前，CFG 中的任何关键边都可以通过在源块和目标块之间引入一个新的中间块来分割。
我对这种扩展最大的失望（也是我一直抵制实现它的原因）围绕着这样一个事实，即它本质上使某些边无法分割。考虑一个简单的 CFG，如下所示
BB1:
indirectbr i8* %P1, [ label %A, label %B ]
BB2:
br label %A
A:
...
边“BB1->A”是关键的，因为 A 具有多个前驱者（来自 BB1 和 BB2），而 BB1 具有多个后继者（到 A 和 B）。我们可以通过引入一个新的中间块来轻松地分割此示例中的边
BB1:
indirectbr i8* %P1, [ label %A1, label %B ]
BB2:
br label %A
A1:
br label %A
A:
...
这是正常的临界边分割转换。在这里我们可以看到从 BB1->A1 的边不是临界边（因为 A1 只有一个前驱），从 A1->A 的边也不是临界边（因为 A1 只有一个前驱）。问题在于我们破坏了一个重要的不变性：因为我们没有调整获取 A 地址的地方，所以现在 CFG 看起来像 BB1 跳到 A1 - 但实际上，indirectbr 获取的指针将包含 A 的地址。这会导致我们进行无效的数据流分析，并带来各种问题。
与内联一样，也可以教优化器学会分割一些临界边。然而，这还不够。如果存在优化器可能无法分割的单个临界边，这意味着各种 LLVM 优化必须假设临界边分割可能会失败。例如，这对循环优化器有重大影响，它假设可以分割临界边来形成规范循环。
我们能获得 CFG 边缘的 N^2 规模爆炸吗？
当然可以。问题在于你可以有 N 个间接分支指令（在上面的示例中，N = 5）和 M 个带有取地址标签（在示例中，M = 5）。由于每个 indirectbr 需要到每个带有取地址标签的标签的边，所以你得到 N*M 条边，也就是 N^2。这很快就会成为一个大的编译时间问题，因为大型解释器在其循环中通常有数百个这类东西。
幸运的是，这个问题的解决方案很简单：虽然优化器可以安全地复制 indirectbr 指令，但它决定这样做不划算。通过尝试在每个函数中最多保持一个 indirectbr 指令，我们有效地对边进行了因式分解。llvm-gcc 和 clang 前端都生成最多包含一个 indirectbr 指令的 IR：所有其他间接跳转都作为函数中公共 indirectbr 的分支降低。
为了生成高效的代码，代码生成器执行尾部复制来引入 N^2 CFG。它在足够早的时间完成此操作以获得良好的代码，但在足够晚的时间完成以不会对编译时间产生太大影响。
取地址但没有跳转到的标签怎么办？
回到 Linux BUG 宏和其他对该扩展的滥用，人们自然会想知道我们是否比 LLVM 2.6 更好地支持这些用法。答案是“有点”。在代码获取块地址并在函数中具有 indirectbr 的情况下，该地址将保留，其他用法将具有预期的行为：它们将看到块的地址，而不是一些魔术块 ID 号码。
然而，这通常还不够好。问题在于获取块的地址不足以防止其他优化（如块合并）影响它，它需要在 CFG 中具有前驱。如果我们决定更好地支持这种滥用，我们将需要扩展我们的模型来以某种方式支持它们。
无论如何，我希望关于 indirectbr 的讨论对你有帮助和启发。与 LLVM 2.6 及更早版本相比，LLVM 2.7 中的解释器循环将更高效！
-Chris