常见的基于堆栈的 VM 字节码优化？

Question

好的，我发布这个是担心它可能会在任何人阅读它之前就被关闭 - 我已经习惯了 - 但我会试一试......甚至将我指向右边方向或某些确实包含特定答案的现有答案肯定会...

---

所以，在这个简短的介绍之后......我目前正在用 C(基于堆栈的 VM)为我设计的编程语言编写一个字节码解释器。

如果您想查看支持的操作码，请随时在此处查看:https://github.com/arturo-lang/arturo/blob/master/src/vm/opcodes.h

堆栈机器并没有什么特别之处。值被推送和弹出，运算符和函数对其进行处理，将评估结果推回堆栈。到目前为止一切顺利。

现在，我正处于所有核心功能都在其中的阶段，我正试图通过进一步优化来进一步提升它。

这是一个例子(希望是一个相当有说明性的例子)。

输入:

fibo: $(x){
    if x<2 {
        return 1
    } {
        return [fibo x-1] + [fibo x-2]
    }
}

i: 0
loop i<34 {
    print "fibo(" + i + ") = " + [fibo i]
    i: i+1
}

产生的字节码:

|== Data Segment /======================>
0   : [Func  ]= function <5,1>
1   : [Int   ]= 34
2   : [String]= fibo(
3   : [String]= ) = 
==/ Data Segment =======================|

|== Bytecode Listing /======================>
0   :0       JUMP [Dword] 31
1   :5       LLOAD0
2   :6       IPUSH2
3   :7       CMPLT
4   :8       JMPIFNOT [Dword] 20
5   :13      IPUSH1
6   :14      RET
7   :15      JUMP [Dword] 30
8   :20      LLOAD0
9   :21      IPUSH1
10  :22      SUB
11  :23      GCALL0
12  :24      LLOAD0
13  :25      IPUSH2
14  :26      SUB
15  :27      GCALL0
16  :28      ADD
17  :29      RET
18  :30      RET
19  :31      CPUSH0
20  :32      GSTORE0
21  :33      IPUSH0
22  :34      GSTORE1
23  :35      GLOAD1
24  :36      CPUSH1
25  :37      CMPLT
26  :38      JMPIFNOT [Dword] 61
27  :43      CPUSH2
28  :44      GLOAD1
29  :45      ADD
30  :46      CPUSH3
31  :47      ADD
32  :48      GLOAD1
33  :49      GCALL0
34  :50      ADD
35  :51      DO_PRINT
36  :52      GLOAD1
37  :53      IPUSH1
38  :54      ADD
39  :55      GSTORE1
40  :56      JUMP [Dword] 35
41  :61      END

==/ Bytecode Listing =======================|

对于使用过编译器、字节码解释器甚至 JVM 的人来说，上面的代码应该很熟悉。

---

我想要什么？

关于如何进一步优化我的字节码的想法——一般的或具体的。

例如，每个*2(即:IPUSH2后跟一个MUL指令)都转换为:IPUSH1， SHL 因为它的操作速度更快。

您还有什么建议？是否有任何需要优化的列表？你能提出一些具体的建议吗？

提前致谢! :)

Answer 1

你给出的例子不是特别好，因为如果解释器进行移位而不是乘法，它的性能增益非常低。执行单字节代码指令的开销在几个数量级上完全超过此特定优化的 yield 。

解释器的最高性能增益是最小化需要执行的指令数量。例如，尽可能将同一寄存器上的两个连续加法或减法累加到一个操作中。

为了能够进行这种优化，您应该尝试识别所谓的基本 block (这些是执行所有指令或不执行指令的 block ，即没有跳入或跳出 block 发生)并通过将多条指令替换为一条指令来优化这些 block 中的指令数量，同时保持相同的代码语义。

如果你真的是认真的，你也可以尝试为你的语言写一个gcc后端来编译成字节码；这样您就可以受益于 gcc 对中间代码表示 (RTL) 的复杂优化方法。