如何使用LLVM将基于栈的虚拟机字节码转换为SSA形式

Question

有很多关于如何将 SSA 表示转换为堆栈机器的问题，但我对逆向感兴趣。

问题

考虑具有 conditional/unconditional 跳转的基于堆栈的 VM，其中每个操作码都有固定数量的堆栈元素，它消耗和生成。

LLVM 框架中是否有tools/approaches 从字节码输出重建 SSA 形式。这本质上是一种反汇编形式。

Answer 1

LLVM本身并没有什么工具，只是SMoP。我已经做到了。它的某些部分很困难，但任何事情都是如此。我会回答而不是评论，以漫谈最困难的部分。

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

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

a 有一个类型，它的所有值都是 int（可能是 LLVM IR 中的 i32）。当第一行将 b() 中的 return 值压入堆栈时，堆栈顶部获取类型 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 入口处的堆栈是从 entry 和 b1 中每个末尾的堆栈计算得出的。您可以在每个基本块的开头为堆栈上的每个值生成一个 phi 节点；挑战在于每个 phi 节点的类型取决于前面块末尾堆栈上的类型。在这种情况下，entry 末尾的堆栈有一个条目，a1，b1 末尾的堆栈有一个条目，a2。因此 stack.0.b1 的类型取决于 a2 的类型，而 a2 又取决于 stack.0.b1。你需要认真考虑一下，特别是如果你的语言包含隐式类型提升或转换（i32 到 i64，字符串到对象等）。

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

如何使用LLVM将基于栈的虚拟机字节码转换为SSA形式

How to use LLVM to convert stack-based virtual machine bytecode to SSA form

compilation

llvm

disassembly

llvm-ir

ssa