Pin*_*juh 2 optimization assembly code-generation
我正在为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和pop相比V).这需要"优化"为:
x + y
(基本上删除"无用的"代码)
我的想法是使用正则表达式.对于上面的情况,它将是一个看起来像这样的正则表达式:x:(U(x)+V(x)):null,意思是所有x查找U(x)后跟V(x)和替换null.想象一下更复杂的正则表达式,用于更复杂的优化.这应该适用于所有级别.
你有什么建议？什么是优化和生产快速x86组件的好方法？
你应该做的是构建一个抽象语法树(AST).
它是树形式的源代码的表示,更容易使用,尤其是进行转换和优化.
该代码表示为树,类似于:
(+
(+
x
(U f))
(+
(V f)
y))
然后你可以尝试进行一些转换:总和之和是所有术语的总和:
(+
x
(U f)
(V f)
y)
然后你可以扫描树,你可以有以下规则:
然后你会得到你想要的东西:
(+ x y)
任何关于编译器编写的好书都会在AST上讨论很多.函数式编程语言特别适合于此任务,因为通常很容易表示树并进行模式匹配以解析和转换树.
通常,对于此任务,您应该避免使用正则表达式.正则表达式定义了数学家称之为常规语言的东西.任何常规语言都可以通过一组正则表达式进行解析.但是,我认为您的语言不规则,因此无法通过正则表达式进行正确解析.
人们尝试并尝试使用正则表达式解析HTML等语言.这已在SO中进行了广泛讨论,您无法使用正则表达式解析HTML.总会出现一个特殊情况,你的正则表达式会失败,你必须适应它.
它可能与您的语言相同:如果它不是常规的,您应该避免许多令人头疼的事情,而不是尝试使用正则表达式解析它(尤其是"转换"它).
我在理解这个问题时遇到了很多麻烦,但我认为你会发现学习一些关于术语重写系统的东西很有用,这似乎是你提出的建议.机制是树重写(始终有效)还是正则表达式(某些时候某些语言和某些语言都适用)是次要的.
绝对可以通过术语重写来优化对象代码.你可能也会从学习窥视孔优化方面受益; 一个好的起点,因为它在基本面上非常强大,是戴维森和弗雷泽关于可重定向的窥视孔优化器的论文.贝尼特斯和戴维森的后期工作也非常出色.