编译器中的部分静态单信息形式（Partial SSI）：动机、实现与权衡

在编译器中，静态单一信息形式（SSI）是常见的扩展 静态单一转让表（SSA）。它由C. Scott Ananian在 1999年，他的硕士论文（PDF）1.

SSI通过查明事实，延长您现有的SSA中级代理 从你现有的程序中，将其具体化为路径依赖/流敏感 红外节点。这听起来可能很复杂，但至少基本想法很漂亮 自然的。我在《我谈论IR时的谈话》中稍微谈过，这里我会更深入地复述，先从一些开始 激励人的例子。请考虑这个明显牵强的例子：

我们应该能从比较中学到，在国际关系的某些分支中， v0为阳性。在该区域，我们可以添加一个新的IR指令v2，使得 它直接将这些知识附加在指令的类型字段中（耶， 稀疏！）然后将v0的使用重写为v2。

因为我们已经做到了，我们的（虚构的）优化规则去除了 已知正整数的绝对值可以生效，我们可以删除 呼唤绝对值。优化，太棒了！

但至少对我来说，还有几个问题：

1. 编译器流水线中何时何地插入和移除这些类型 改进？

2. 我们是否需要在每个条件句后进行精炼？

3. 我们是否需要实现整个进入SSI和退出SSI的算法，从 那些看起来很复杂的文件？

我们将从编译器流水线开始逐一介绍。

我们什么时候插入类型细化？

最初的SSI论文开头是（我记得是这样？）SSA形式及位置 基于条件句的新精炼节点。说实话，我并没有怎么尝试过 很难，但进入SSI的算法看起来复杂且有点重。作为 奖励是你获得“线性”进入SSI的时间复杂度。

但我是个谦逊的编译工程师，没时间详细讲解 把这一切都灌输到脑海里。相反，我所见所做的和正在发生的事情 这样做就是走捷径：在SSA期间积累部分SSI。 建筑2。

大多数情况下，这来自字节码，但也可能是其他类型的 非社会保障局的IR。无论如何，这是一个极好的捷径，原因有两个：

1. 它让我能清楚地区分添加类型细化（漂亮 直接的）从所有操作数重写的难点开始 还有Phi分班、评分以及各种其他无关紧要的规定。

2. 除了分离关注点外，最难的部分已经由 SSA的建筑。我们其实可以跳过它！SSA负责处理φ 放置、操作数重写，所有这些。它大概可以很好地融入一个 天真或布劳恩式（PDF）构造。

这很有说服力。我们可以从字节码中学习，但用非常小的 边际新复杂度的量。参见我在ZJIT中的实现例如。它实际上只是修改摘要 从 branchnil、branchif 和 构建 SSA 时的解释状态 branchunless 字节码指令以考虑新的精炼 价值观。

对于已经在用户源程序中的分支来说，这没问题，但 有时优化，尤其是动态语言，会添加新的分支 以前没有。有时这些分支会在很晚、很长的时候才加上 SSA建成后。然后呢？我们能做类似的事情并依赖 现有基础设施？

在SSA优化过程中

这个“我们能做到吗”的假设是你的IR会追踪数据 从用法到对应的定义依赖关系，但从定义到用法则不然。海 节点（至少是很简单 实现），是一种能够始终双向跟踪的红外线，以便更简单 重写。许多投资介入关系不会这样做，所以我们继续假设存在 没有“轻松的出路”。

动态语言编译器的JIT优化通常会添加合成Guard 对IR的指示，强制执行先决条件。这些守卫允许 在JIT代码中优化happ/fast路径情况，同时保留解释器作为 后备方案。例如，我们可能能够连续优化两个 SetInstanceVariable 指令（在 世界中是非常动态的操作） 但具体通过对象形状实现时速度很快）来自：

这非常通用，涉及调用C代码，可能会引发 例外，更像是：

这要快得多（假设运行时形状稳定）。有一个 不过有个烦人的问题，就是我们有很多重复的 现在IR上散落着指令，因为我们的优化器每个指令都处理过 个别教学。有点像“模板优化器”的情况。现在我们需要 有些人会经过清理杂物。

全局值编号（GVN）能很好地去除重复指令。 它应该注意到我们已经有一个指令，看起来像 GuardHeapObject x 调用 v0，并将 v3 重写为 v3 = v0。太好了 因为我们已经去了卫队的重复。不过GVN可能不会包含所有内容;如果 有些指令后来会使用 X，但它们不会被重写为改用 这些新守卫指令的输出。为此，我们需要添加某种 通过某种规范化功能来规范化 PASS（通行或增强）GVN。那个 规范化处理操作数重写以使用“最新版本”的 可以说是某种价值。参见克里斯·法林的正典化部分精彩的AEGRAPHS博客文章 更多（当然还有（目前是区块本地）ZJIT中的实现).

不过我想说的是，你可能已经有一些了 基于支配的指令重写机制，适用于编译器，可以是 无论是GVN的一部分还是单独存在！你可以用它来做非常低的代码 在优化器中间进入部分SSI。

这意味着你完全可以插入 RefineType 在条件句的后续块中执行指令，并获得 into-SSI “对于” 免费“。

在哪些条件句之后我们要细化？

这取决于你自己。编译时和运行时之间存在权衡， 尤其是在JITs中。插入更多指令和重写次数可能会 放慢编译器速度。这是便宜的午餐，不是免费的。

这和那些看起来复杂的论文相比如何？

我不知道。我不太清楚这个“部分SSI”和它有什么区别 “全额SSI”。我不打算近期实施完整的SSI。

我需要指出，这种部分SSI方法并没有做到两件事：

1. 它不会用新的σ节点拆分变量，并且通常会插入 目标块内的精炼节点，而非分支之上

2. （仅用于规范化）它不会插入新的phi节点;它就这样离开了 两个红外节点都可用，且不重新合并，而是丢弃它们

我无法判断这会带来什么影响。

在其他编译器中

就像《Simple》一样，松露红宝石建在节点之海之上 红外线（格拉尔）。克里斯·西顿有精彩的博客文章关于 TruffleRuby 使用“印章节点”（“Pi 节点”3）。该 我觉得 replaceAtUsagesAndDelete 函数能做很多繁重的工作 因为Graal的轨道使用。

辛德主要是插入式 在 HIR 构建器中，RefineType 指令，在 into-SSA 之前，然后让 社会保障局的建筑会处理好一切。我就是在那里学会了这个技巧， 其实。这里是一个例子 在构建模式的红外线时，细化匹配操作数的类型 匹配。

夏威夷派对正在做类似的事情， 但他们的类型检测器。和他们团队里的人聊天其实是 这也是我写这篇文章的部分原因。

Android ART看起来确实有HBoundType 并插入在参考类型传播中. 它处理类检查、空检查和实例检查。

顺便说一句：比如堆对象升级的逻辑

最后，我想谈谈一些你可以提出的有趣推理 当你有两个实现可以切换时，对于 例如，JIT（+ 解释器），或 C 语言中的别名和非别名情况，或 比如奇怪的NULL-UB推理，LLVM能对C代码做类似的事情。

在ZJIT中，我们目前机会性地在“简单”情况下插入RefineTypes 当我们从解释器字节码构建 HIR 时。

例如，如果字节码中存在一个分支比较某个值 x 使用 NIL 时，它将有两个输出控制流边：一个块，其中 x 绝对是零，而一个方块X绝对不是零。在每个 在这些控制流边中，我们可以插入相应的类型细化提示。 这很常见。但我们也可以做更奇怪的事情。

CRuby 有堆对象与即时对象的概念。许多（甚至大多数？）物体 是堆对象。然而，例如，整数5并未分配在 堆，但用带标签的位模式表示 假装是一个地址：整个值都编码在指针中 就是它自己。

我们将这些知识编码在HIR的类型系统中：“堆性”和 “即时性”在类型格中都有一定的体现。我们 在优化器中使用此方法来推理影响， 还有其他事情。

我们很多时候无法知道一个物体的类型，所以我们会悲观地看待 大多数通过字节码流动的对象类型为 BasicObject。这种类型 封装了可能放置在堆栈上的所有可能值的世界，或者 在局部变量中。

在大多数堆对象上，除了少数例外，你可以写实例 变量（字段、属性，或者你想怎么称呼它们都行）。你永远都做不到 写一个实例变量到一个即时变量。这意味着如果我们观察到 字节码中的模式如下：

然后在为 setinstancevariable 操作码构建并发出 HIR 后，我们 可以将 x 的类型从 BasicObject 升级为 HeapBasicObject。我们可以 这样做是因为如果它不是堆分配对象，我们会留下 编译代码并输入解释器。

这是另一种你可以在编译器里实现的SSI类功能。

结论

呃，我想结论是你不必做全额SSI和部分 SSI可用且不太可怕吗？你的编译器是这样操作的吗？请读者 写进来。

1. …并于2002年进行了优化（PDF）， 2009年重新审视（PDF），2010年在LLVM中实现（PDF），2017年进行了摘要编译研究 （PDF），可能还有更多。2009年Boissinot、Brisk、Darte和 拉斯泰洛甚至指出阿纳尼安和辛格的论文都有漏洞，而 也许是无意中也在对文学作品开了一个很棒的双关语 “稀疏”。↩

2. 这篇博客文章不同于LLVM论文（PDF）所称的部分SSI。偏 原因各不相同。也许它已经不再是单一信息了。↩

3. 今天我了解到这个术语来自ABCD的论文（PDF）。↩