如何优化具有控制流和副作用的混合堆栈/寄存器字节码？

Question

我试图找出一种技术来优化以下虚拟机的字节码：

• 字节码是一个平面的指令列表，从第一个指令开始执行。
• 堆栈字节码: i++、a+b、方法调用f(a、b、c)等指令发生在操作数堆栈的顶部1、2、N值上，并将其结果留在操作数堆栈的顶部。
• 字节码用于丢弃堆栈的顶部值，例如，如果您调用一个副作用方法，但不希望返回值
• N个局部变量的数组，用于将值从局部变量复制到操作数堆栈顶部的指令。
• 无条件的GOTO，条件跳转，在操作数堆栈的顶部有各种谓词
• 副作用说明:将操作数堆栈的最高值读写到全局变量

这个虚拟机的输入将是一些有效的字节码，但是有了一些冗余:一些指令将无法到达，操作数堆栈上计算的一些变量将被弹出，存储在局部变量中的一些变量将被重写而不会被读取，一些GOTOs将先到另一个GOTO，而不是直接到达最终目的地。

我知道作为一个开始，向前遍历跟随跳跃会告诉我们可到达指令在哪里，让我们消除不可到达的指令。但是其他的呢:优化代码计算，未使用的值，或冗余的GOTOs？

我知道，对于没有副作用的程序，我可以从返回的值开始计算数据流图，然后向后看哪些计算值是未使用的。但是，在我需要保留其顺序的情况下，这似乎不起作用，因为数据流图会忽略它们。我想，除了数据流图之外，我还需要一个控制流图，但我不确定这两个图如何协同工作，以帮助我优化字节码。

在控制流和全局副作用(读和写)存在的情况下，我可以使用什么样的技术来优化那些需要保留顺序的技术？CPS或SSA或任何其他中间表示格式在这方面有帮助吗？

Answer 1

关于这个主题有大量的研究，所以我真的推荐你读一本编译器的书。穆赫尼克的书可以很好地作为参考。我真的很喜欢现代编译器实现，但我认为它是绝版的。

如果您是通过阅读代码学习得更好的人，Scala编译器将完成上述所有操作，JVM可以满足您为VM列出的所有要点。

更重要的是：

• 我强烈推荐不使用堆栈的表示形式。当您修改代码时，保持它的一致性是很痛苦的:如果您删除了在一个分支上推送堆栈值的指令，您也需要在其他分支上添加一个下拉列表，否则堆栈在合并点将不一致。在完成所有优化传递之后，可以轻松地从基于寄存器的代码中生成基于堆栈的代码。
• 你想删除“死代码”。如果表示形式已经很简单(我认为ANF比CPS简单得多，我成功地使用了它--粗略地说，它将所有表达式分解为简单的两个操作数和临时表达式)，您可以简单地标记为"live“所有有效的指令。然后，您将需要“活动”信息，该信息计算稍后使用的赋值(从所有实时指令开始向后返回，并将其输入标记为“活动”，等等)。棘手的部分是在CFG中的合并点，在那里您需要保守地近似(基本上，您对程序的了解越来越少，以考虑哪个分支的不确定性)。
• 我认为最简单的方法是将控制流保持为您的主要数据结构，并在需要时计算数据流信息(例如活性)。
• 如果您有选择，请使用树而不是CFG。树保留了程序的结构(而，如果)，而条件跳转和无条件跳转则要强大得多，您将花费大量的精力重新计算从AST中丢弃的内容(例如，在CFG中查找主导者)。
• 您可能会在管道中运行几次死代码，因为每次优化传递都可能产生更多的死区代码。这是好的，而且通常比使每一个优化都更聪明和不必要的复杂更好。

Answer 2

你所指的每一件事都需要/有它自己的个别优化算法。优化器是一组优化算法的集合，按顺序运行，甚至经常重复，直到没有变化。

我知道作为一个开始，向前遍历跟随跳跃会告诉我们可到达指令在哪里，让我们消除不可到达的指令。但是其他的呢:优化代码计算，未使用的值，或冗余的GOTOs？

未使用的表达式一次优化(即删除)一条指令，方法是识别未使用的最后一条指令，并消除产生该值的指令。一次只需一条指令，就可以删除全部未使用的表达式。基本算法识别出一条未使用的指令，该算法被重复，直到没有改变为止。

冗余分支是通过自己的特定优化来处理的，它们寻找分支到分支的分支。有时，代码也会被重新排列，以改进条件分支。还有面向循环的优化，以删除循环末尾的无条件分支(有利于条件分支)。

总之，每个转换都是一个单独的优化，优化编译器有数百个，其中一些是重复的，直到它们无法匹配它们所寻找的模式(S)。

但是，在我需要保留其顺序的情况下，这似乎不起作用，因为数据流图会忽略它们。我想，除了数据流图之外，我还需要一个控制流图，但我不确定这两个图如何协同工作，以帮助我优化字节码。

数据流分析必须考虑控制流。

控制流分析涉及到识别基本块，它是由分支不间断的指令序列，例如从一个标签开始，以一个分支指令或另一个标签结束。进一步的控制流分析将基本块连接起来，识别循环，如果-然后-否则构造，等等。

控制流分析的输出是一个图结构，表示基本块的节点&边；节点和连接它们的边。

数据流分析通常有两种形式:基本块内部的分析和控制流后基块边缘之间的分析。通常，这些分析也是双向的，向前:跟踪到达定义，向后:跟踪暴露的用途。因此，我们得到关于变量定义和变量使用的信息。

数据流的输出通常是位向量上的一些变化，其中每个位位置代表程序中的不同变量。如果设置了位，则有变量的定义(用于定义，或者用于使用，如果没有，则没有). (在控制流图上操作的数据流算法，也是不动点算法，这意味着它们可以收敛:它们可以重复使用，直到没有变化)。

我们可以考虑到，在程序中的每条指令之前和之后，有两个潜在的位向量，它们表示哪些(前面的)定义到达该位置，以及(后续)使用的是什么消耗结果--尽管通常这些信息不是存储在每条指令中，而只是在每个基本块开始之前和结束之后(指令级信息在遍历基本块时是可重复的)。

优化以各种方式使用这个数据流信息。例如，当变量的定义没有使用时，就可以检测到这一点，这就是如何识别未使用的计算。例如，可以确定两个变量在程序中的同一点(或不是)处于同一位置，因此需要(或不需要)不同的CPU寄存器。

SSA是一种数据流分析的形式，它引入和跟踪变量的版本，以便信息是全局正确的(它是精确的、无位置的)，而旧的(可以说更简单的)数据流算法直接跟踪变量，这种跟踪必须在位置的上下文中理解。

Answer 3

您刚刚描述了一种名为第四第四的编程语言。它是开源的，有很多实现，涵盖了相对幼稚的，非常复杂的.

一种技术是处理机器中的每一件东西:堆栈、堆、文件系统、屏幕等等。具有一个关联的操作列表，每个操作都采用上一个操作产生的值，并返回一个更新的值。每条指令本质上都是附加到这些列表中的一组操作。

行动仍然需要一个相对的顺序，但它不需要严格的意义上说，每一个动作是与所有其他的顺序。但是，它确实需要足够严格，以便操作始终读取正确的值，并将该值显示给变量上的后一个操作。这允许这些操作不了解系统其他部分的状态，它们只关心应用到的对象。它们使用的任何其他信息要么是在将操作添加到列表时传入的，要么是早期时间操作分组中的另一个操作已分配了该值。

在此之后，两个(或更多)指令在这些列表上生成一组操作。现在有些动作会互相抵消。说swap a,b; swap b,a;吧。当它们在一起时，它们对结果的影响是零的。剩下的操作是执行该代码所需的必要和足够的操作。

要优化此代码，请执行以下操作：

1. 定义一个新指令，该指令的定义正是这些操作。
2. 找到一个与其定义相同的操作的较短的系列指令，希望有很少/没有取消操作。

我还要退一步，看看源代码所代表的程序结构。如果这与机器结构相同，请忽略这一点，但是如果它是高阶结构，请尝试在此图级别应用优化。在这个语义细节级别上，应用特定的优化要简单得多，因为您不必从一系列较小的步骤和一些有关分支、兄弟姐妹等的常见查询中识别它们。都是微不足道的。