从字节码构建 SSA：命令式珠玑

从字节码生成 SSA：命令式珍珠

Ufuk 评论说，他很喜欢我在 Aaron 的直播中对他描述的从字节码生成 SSA 的内容。在拍摄那场直播——一个 ZJIT 内部原理的介绍——时，我有点紧张，担心人们会被我们那 1900 行的 add_iseq_to_hir 函数吓退。这个函数负责将 CRuby 的 YARV 虚拟机的基于栈的字节码转换为供 ZJIT 分析和优化的高层 SSA IR。

它接收大致如下的字节码：

        push 3
push 4
add
      

转换为 SSA 形式，大致为每个栈槽赋予一个 SSA 值：

        v0 = const 3
v1 = const 4
v2 = add v0, v1
      

虽然我们的函数有 2000 行，是因为它处理了大量特定的操作码以及这些操作码的奇特情况，但它的核心很小。这就是那个核心。

如果有一个栈，但是虚拟的

字节码假设当它运行时，它将在一个栈上操作。这意味着每个操作码都有隐式的栈输入和隐式的栈输出。

例如，push 3 有空的栈输入和一个栈输出。相比之下，add 有两个栈输入和一个栈输出。有些指令如 nop 在两方面都是空的。据我所知，所有指令最多只有一个输出。

这些计数在查看字节码时是已知的：我们可以静态地推理每个操作码有多少输入和输出。有些是可变参数的，例如 send（调用），但它们会在附近的字段中携带参数计数。

让我们通过在每个指令运行后添加栈的视图来模拟第一个示例在 VM 上的运行。栈将显示为从左到右的列表，左边是底部，右边是顶部。

        ; []
push 3 ; [3]
push 4 ; [3, 4]
add    ; [7]
      

因为输入计数和输出计数是静态的，当 ZJIT 读取字节码时，我们可以在编译时运行它的栈部分。

我们实际上不需要知道栈上的值是什么；我们只需要跟踪它们来自哪里。当我说“它们来自哪里”时，我的意思是，我们为每个指令命名，并通过指令的名称来引用其输出。我喜欢论文《Design of the Java HotSpot™ Client Compiler for Java 6》（PDF）中的说法：

加载或计算值的指令既代表操作也代表其结果，因此操作数可以表示为指向先前指令的指针。

以下是上述示例的情况。除了运行时栈，我还会写出 SSA 指令，以表明我们正在生成新代码：

        ; []
push 3 ; v0 = const 3
       ; [v0]
push 4 ; v1 = const 4
       ; [v0, v1]
add    ; v2 = add v0, v1
       ; [v2]
      

这很巧妙！我们已经将基于栈的字节码转换为一种形式，其中指令可以直接引用它们的输入。不过你可能注意到，v0 和 v2 最终都位于同一个栈槽（第一个元素）。这就是为什么我之前说“大致为每个栈槽赋予一个 SSA 值”。

两者的区别在于时间。v0 曾在操作数栈中，但现在 v2 在那里。这有点像是为什么我将 SSA 描述为“将时间推入 IR”。

好的，让我们实现它。

实现

我们将从字节码的真实（“具体”）解释器开始，它在一个值栈上操作。这为你提供了一个 Ruby 内部工作原理的简化版本：

        def interpret(bytecode)
  stack = []
  bytecode.each do |op|
    case op
    in [:push, c]
      stack << c
    in [:add]
      right = stack.pop
      left = stack.pop
      stack << left + right
    else
      raise "Unknown op #{op}"
    end
  end
  stack.pop
end

bytecode = [
  [:push, 3],
  [:push, 4],
  [:add],
]

puts interpret(bytecode)  # 7
      

现在让我们看看抽象解释器，相比之下，它在一个 SSA 栈上操作。你可以看到它们看起来非常相似：

        def to_ssa(bytecode)
  code = []
  stack = []
  bytecode.each do |op|
    case op
    in [:push, c]
      name = :"v#{code.length}"
      code << "#{name} = const #{c}"
      stack << name
    in [:add]
      name = :"v#{code.length}"
      right = stack.pop
      left = stack.pop
      code << "#{name} = add #{left}, #{right}"
      stack << name
    else
      raise "Unknown op #{op}"
    end
  end
  code
end

bytecode = [
  [:push, 3],
  [:push, 4],
  [:add],
]

puts to_ssa(bytecode)
# v0 = const 3
# v1 = const 4
# v2 = add v0, v1
      

这些名字可以是任何东西，只要它们互不相同。为了简单和便于阅读，我选了 code 数组的长度，它是单调增长的。这是上面那篇 HotSpot 论文中真实指针做法的一种基于数组/向量的类比。

嗒哒！你已经构建了一个小型抽象解释器。

现在，要让它变得全局（以处理控制流），你需要某种跨基本块的数据流机制，比如 phi 节点或基本块参数。也许另一篇文章会多谈谈这个，但眼下，你可以看看我收集的别人关于这个话题的写作。

结论

我最初想把这篇博客文章命名为「你本可以发明抽象解释」或类似的名字，但我最终决定，我觉得这类标题很惹人厌，因为它们假定读者是不聪明的，或者读者自认为不聪明。也许我们本可以发明它吧。

这个标题有点半开玩笑地向「functional pearl」论文致敬——我总觉得它们应该比实际上更简单，却总是让我困惑。同时，也是对 Andrew Appel 的《SSA is Functional Programming》（PDF）一次更友善的致意。

参考资料

• A New Approach to Forth Native Code Generation (PDF, 1992)

• Java Bytecode to Native Code Translation: The Caffeine Prototype and Preliminary Results (PDF, 1996) 第 3.2 节

• CACAO - A 64 bit JavaVM Just-in-Time Compiler (PDF, 1997) 第 3 节

• Fast, Effective Code Generation in a Just-In-Time Java Compiler (PDF, 1998) 第 2.2 节，mimic stack

• The Jalapeño Dynamic Optimizing Compiler for Java™ (PDF, 1999)

• Dynamic optimization through the use of automatic runtime specialization (1999) 第 3.4 节