optimization - (x86) 汇编器优化

Question

我正在用 Java 为面向 Windows 的 x86-32 (IA32) 处理器构建编译器/汇编器/链接器。

高级概念(我没有任何“源代码”:没有语法或词法翻译，所有语言都是常规的)被翻译成操作码，然后被包装并输出到文件中。翻译过程有几个阶段，一个是常规语言之间的翻译:最高级别的代码被翻译成中等级别的代码，然后再被翻译成最低级别的代码(可能 超过 3 个级别)。

我的问题如下；如果我将高级代码(X 和 Y)转换为低级代码(x、y , U 和 V), 那么这种翻译的一个例子是, 在伪代码中:

x + U(f) // generated by X
+
V(f) + y // generated by Y

(一个简单的示例)其中 V 与 U 相反(比较堆栈压入为 U 和出栈为 V).这需要“优化”成:

x + y

(基本上删除“无用”代码)

我的想法是使用正则表达式。对于上述情况，它将是一个如下所示的正则表达式:x:(U(x)+V(x)):null，表示所有 x找到 U(x) 后跟 V(x) 并替换为 null。想象更复杂的正则表达式，用于更复杂的优化。这应该适用于所有级别。

你有什么建议？优化和生成快速 x86 汇编的好方法是什么？

Answer 1

您实际上应该做的是构建一个 Abstract Syntax Tree (AST) .

它以树的形式表示源代码，更易于使用，尤其是进行转换和优化时。

该代码表示​​为一棵树，类似于:

(+
    (+
        x
        (U f))
    (+
        (V f)
        y))

然后您可以尝试进行一些转换:总和的总和是所有项的总和:

(+
    x
    (U f)
    (V f)
    y)

然后你可以扫描树，你可以有以下规则:

• (+ (U x) (V x)) = 0，对于所有 x
• (+ 0 x1 x2 ...) = x，对于所有 x1，x2，...

然后你会得到你要找的东西:

(+ x y)

任何一本关于编写编译器的好书都会对 AST 进行大量讨论。函数式编程语言特别适合这项任务，因为通常很容易表示树并进行模式匹配以解析和转换树。

通常，对于此任务，您应该避免使用正则表达式。正则表达式定义了数学家所说的常规语言。任何常规语言都可以通过一组正则表达式解析。但是，我认为您的语言不规则，因此正则表达式无法正确解析它。

人们尝试、尝试、尝试使用正则表达式解析 HTML 等语言。这已在 SO 中进行了广泛讨论，您不能使用正则表达式解析 HTML。总会有一种异常(exception)情况，您的正则表达式会失败，您将不得不对其进行调整。

它可能与您的语言相同:如果它不是正则的，您应该避免很多麻烦并且不要尝试使用正则表达式解析它(尤其是“转换”它)。