2

关于如何将 SSA 表示转换为堆栈机器存在许多问题，但我对相反的问题很感兴趣。

问题

考虑一个带有条件/无条件跳转的基于堆栈的 VM，其中每个操作码都有固定数量的它消耗和产生的堆栈元素。

LLVM 框架中是否有工具/方法可以从字节码输出中重建 SSA 形式。这本质上是一种拆卸形式。

4

1 回答 1

2

LLVM 本身没有工具，但它只是 s SMoP。我已经做到了。它的一部分是困难的，但任何事情都是如此。我会回答而不是评论来讨论最困难的部分。

堆栈通常是无类型的；堆栈顶部的值具有类型，但“堆栈顶部”没有。LLVMValue总是有一个类型，当代码包含循环时，这两个系统会发生冲突。考虑这段代码：

int a = b();
while(a<10)
    a++;

a有一个类型，它的所有值都是 int（可能是 LLVM IR 中的 i32）。当第一行将返回值b()压入堆栈时，堆栈顶部获取类型 int。您可能可以想象这些行在您的堆栈机器上的外观。它应该像这样翻译成 IR：

entry:
  %a1 = call @b();
  br label %b1
b1:
  %stack.0.b1 = phi i32 [%entry, %a1], [%b1, %a2]
  %a2 = add i32 1, %stack.0.b1
  %done = icmp ult i32 %stack.0.b1, 10
  br i1 %done, label %b1, label %b2
b2:

（抱歉语法错误，我没有手动写太多 IR。）

您可能会看到除 之外的每条指令都phi可以从堆栈语言中的一条指令生成。也许您的堆栈语言中的一条指令会导致多个 IR 指令，或者不会导致任何 IR 指令，例如 dup 或 push-constant-zero，它们只会修改堆栈。

不同的phi是，它代表当时的堆栈。

进入块的堆栈是从每个和b1末尾的堆栈计算的。您可以在每个基本块的开头为堆栈上的每个值生成一个 phi 节点；挑战在于每个 phi 节点的类型取决于前面块末尾堆栈上的类型。在这种情况下，堆栈末尾有一个条目，而在is 的末尾有一个，. 因此 的 类型取决于 的，而 的 又取决于。您需要认真考虑这一点，特别是如果您的语言包含隐式类型提升或强制转换（i32 到 i64，字符串到对象等）。entryb1entrya1b1a2stack.0.b1a2stack.0.b1

（我可以从类似 ruby​​ 的类型系统和代码开始，而不是类似 c 的代码；我认为最终的问题是一样的，只是你的解决方案不同。）

于 2019-05-02T08:42:50.703 回答