基于类型的别名分析在玩具优化器中的应用

在玩具优化器系列中，又一项新成果。

上一次，我们是在玩具优化器的背景下实现了“加载-存储转发”机制。我们成功地在编译时对从堆中读取和向堆中写入的结果进行了缓存！

我们特别注意对象别名问题：根据读取/写入所引用的偏移量，我们将堆信息划分为不同的别名类。 这样一来，即使我们不知道对象 a 和 b 是否存在别名关系，至少也能确定不同偏移量永远不会发生别名（前提是我们的对象不会重叠， 且内存访问发生在字大小的槽位上）。这是一种较为粗略的启发式方法。

幸运的是，在编译时我们往往能获得比偏移量更丰富的信息，因此应当充分利用这些信息。 我在脚注中提到过，我们还可以利用类型信息来改进别名分析。 在这篇文章中，我们将引入一种轻量级的基于类型别名分析（TBAA）技术（PDF）。

表示类型

我们再次回到菲利普·皮兹洛的领域——具体来说是我如何实现 SSA 形式。在我们的实现中，我们将沿用上一篇文章中介绍的分层堆效应表示法； 不过，如果你已经有自己独特的类型表示法，也可以直接使用。

这种表示法通过类型将堆划分为互不相交的区域。 例如，我们可以假设数组对象与字符串对象之间不存在重叠关系。 链表指针绝不会与整数指针发生别名关系。 因此，我们可以分别对它们进行推理和处理。

然而，有时我们并不能获得完美的类型信息。 如果某种语言中存在一个用于所有对象的“Object”基类，那么“Object”堆就可能与“Array”堆产生重叠。 因此，我们需要一种方法来表示这种情形——仅仅依靠枚举类型并不足以做到清晰而准确的表示。

以下是一个简化的类型层次结构示例：

其中，“Other”可以代表运行时数据结构的不同部分，并且还可以进一步细分为垃圾回收、线程等子类别。

菲利普的构想是：我们可以通过一个由整数组成的元组来表示该层次结构中的每个节点， 该元组的范围为 [start, end)（包含边界，但不包括边界）——这两个值分别代表树的前序遍历和后序遍历。 或者，如果树的遍历过程并未深植于你的骨髓之中，那么这些范围则可以用来表示树内所有嵌套对象的区间。

接下来，“此写操作是否会干扰此读操作”这一检查——也就是别名检查——实际上就是对范围重叠的查询。

以下是基于 Ruby 生成器和 JavaScriptCore 的 C++ 运行时代码，对范围与堆层次结构的一种或许略显“过度工程化”的 Python 实现：

其中，Any.compute(0) 作为树编号方案的起点。

菲利普的实现还涵盖了多种抽象堆，比如 SSAState 和 Control，因为他的实现主要用于代码移动以及其他相关功能。 这些功能稍后可以再添加进来，但在本文中我们暂不涉及。

至此，我们已经拥有了一个类型表示法。接下来，我们需要在“加载-存储转发”中加以运用。

加载-存储转发

回想一下，我们的加载-存储优化阶段大致如下：

其核心在于，我们逐条遍历指令，同时在编译时为堆维护一份表示。读取操作会被缓存，写入操作也会被缓存，而且写入操作还会清空编译时关于可能产生别名字段的信息状态。

在这种情况下，“可能别名”仅判断偏移量是否重叠。这意味着，以下单元测试将会失败：

该测试原本预期，尽管我们在 var1 中向同一个偏移量写入了数据，但 var0 的写入操作仍应保持缓存状态——因为我们已将 var0 标记为数组类型，而 var1 标记为字符串类型。

如果我们能在别名分析中考虑类型信息，就能让该测试顺利通过。

经过一番反复调试与优化，最终我将代码精简到了一个非常短的差异：

如果没有类型或别名信息，我们默认为每个对象都标记为“一无所知”（Any）。随后，我们会检查范围重叠情况。

优化加载-存储的布尔逻辑看起来或许有些奇怪。不过，我们也可以通过德摩根定律将其改写为：

因此，我们保留了所有已缓存的字段状态——对于那些已知其偏移量和类型不会发生别名关系的字段。也许这样表述更加清晰（不过差异也未那么显著）。

需要注意的是，这里类型表示法其实并不那么重要！如果你愿意，也可以采用位图形式来表示类型信息。真正关键的是，你可以轻松构建类型，并在不同类型之间进行重叠检测。

太棒了！现在我们的测试通过了！我们能够区分不同类型对象之间的内存访问。

但如果我们知道更多信息呢？

对象来源/分配位置

有时候，我们清楚某个对象的来源。例如，我们可能曾在跟踪记录中看到它被分配。 一旦我们看到了某个对象的分配过程，就可以确定它不会与任何通过参数传入的对象发生别名关系。 我们可以充分利用这类信息来发挥优势。

以以下虚构的 IR 片段为例：

我们知道，除了其他诸多事实之外，v0 不会与 arg0 或 v1 发生别名关系，因为我们已经观察到了 v0 的分配位置。

我在旧版 V8 IR Hydrogen 的轻量级别名分析中发现了这一点1：

此外，还有许多其他有用的信息，例如：

• 如果我们在编译时得知对象 A 在偏移量 0 处拥有 5 个元素，而对象 B 在偏移量 0 处拥有 7 个元素，那么 A 和 B 并不会发生别名关系（感谢 CF）。 • 在 PyPy 的 RPython JIT 中，这一特性被用来判断两个用户（Python）对象是否会发生别名关系，因为我们知道用户（Python）类字段的具体内容。 • 对象大小（不过这或许只是上述要点的一个特例）。 • 字段大小与类型。 • 将别名检查推迟到运行时执行。 • 如果 (a == b) { ... } else { ... }，则分支执行。 • … 如果你还有其他有趣的见解，欢迎随时分享。

与其他指令交互

在我们的优化器中，我们只处理加载和存储操作。 不幸的是，这也意味着我们可能会无意间缓存过期的信息。 试想一下：如果一个函数调用（或其他任何不透明指令）向我们正在跟踪的对象写入数据， 会发生什么？

保守的做法是，在函数调用时清空所有已缓存的信息。这样做当然没错，但对于优化器而言却有些遗憾。我们还能做些什么吗？

也许我们调用的是一些广为人知的函数，或是特定的 IR 指令。在这种情况下，我们可以在相同的抽象堆模型中为其添加一些效果标注：如果该指令没有写入数据， 或者只写入了某些堆，我们至少可以部分清空我们的堆缓存。

然而，如果这个函数尚不为人知，或者完全不透明，我们就需要更先进的别名信息，甚至可能还需要进行（部分）逃逸分析。

试想一下：即使一条指令没有操作数，我们也无法确切知道它当前处于何种状态。 如果这条指令写入了任意对象 A，我们便无法安全地缓存其他对象 B 的信息，除非我们确信 A 和 B 不会发生别名关系。而我们同样无法得知该指令究竟写入了什么。 因此，我们只能确认自己可以缓存 B 的信息，因为 B 是本地分配的，尚未发生逃逸。

随机存储与计算

一些运行时，例如 ART，会在比特矩阵中预先计算好所有的别名信息。在全控制流图中使用别名信息时， 这种方式显得更为合理，因为您可能需要在图中多次遍历。

而在跟踪上下文中，您只需一次遍历就能完成大量工作——无需构建矩阵。

这种做法在什么时候派上用场？又有多大的实际价值？

一如既往，这只是一个玩具 IR 和玩具优化器，因此很难准确评估它能让玩具程序跑得快多少。

不过总体而言，分析与优化之间有一个权衡：在精确度与速度之间寻找平衡点。 在这一权衡中，我们找到了一个令人欣慰的解决方案：相较于仅基于偏移量的无效化， 额外增加的分析成本微乎其微，但能带来更高的精度。 我很喜欢这样的折衷方案。

此外，这种优化方式在 JIT 编译器中也非常有用——通常，托管语言的表现要优于类似 C 的语言。托管语言往往比 C 语言表现得更好。在您的 IR 中，很可能已经存在大量来自强度削减优化的重复加载和存储操作，而这些操作可以有效清理冗余。

总结

请参阅 完整代码。

感谢各位的参与，我正努力为自己尝试应用基于类型别名分析。希望你们也觉得有趣。

另请参阅 Andy Wingo 的文章 动态类型检查的两种机制。 CRuby 使用了文章中所描述的第二种技术。

谢谢！

感谢 Chris Gregory 提供的宝贵反馈。

1. 我曾对 V8 进行了 分支开发,以便深入探索 Hydrogen IR。后来，我将 V8 仓库重置为最后一次提交，就在他们决定将其删除、转而使用全新的基于“Sea of Nodes”的 IR——TurboFan——之前。

↩