(x86) Assembler Optimization

Question

I'm building a compiler/assembler/linker in Java for the x86-32 (IA32) processor targeting Windows.

High-level concepts (I do not have any "source code": there is no syntax nor lexical translation, and all languages are regular) are translated into opcodes, which then are wrapped and outputted to a file. The translation process has several phases, one is the translation between regular languages: the highest-level code is translated into the medium-level code which is then translated into the lowest-level code (probably more than 3 levels).

My problem is the following; if I have higher-level code (X and Y) translated to lower-level code (x, y, U and V), then an example of such a translation is, in pseudo-code:

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

(An easy example) where V is the opposite of U (compare with a stack push as U and a pop as V). This needs to be 'optimized' into:

x + y

(essentially removing the "useless" code)

My idea was to use regular expressions. For the above case, it'll be a regular expression looking like this: x:(U(x)+V(x)):null, meaning for all x find U(x) followed by V(x) and replace by null. Imagine more complex regular expressions, for more complex optimizations. This should work on all levels.

What do you suggest? What would be a good approach to optimize and produce fast x86 assembly?

Answer 1

What you should actually do is build an Abstract Syntax Tree (AST).

It is a representation of the source code in the form of a tree, that is much easier to work with, especially to make transformations and optimizations.

That code, represented as a tree, would be something like:

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

You could then try to make some transformations: a sum of sums is a sum of all the terms:

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

Then you could scan the tree and you could have the following rules:

• (+ (U x) (V x)) = 0, for all x
• (+ 0 x1 x2 ...) = x, for all x1, x2, ...

Then you would obtain what you are looking for:

(+ x y)

Any good book on compiler-writing will discuss a lot on ASTs. Functional programming languages are specially suited for this task, since in general it is easy to represent trees and to do pattern matching to parse and transform the tree.

Usually, for this task, you should avoid using regular expressions. Regular expressions define what mathematicians call regular languages. Any regular language can be parsed by a set of regular expressions. However, I think your language is not regular, so it cannot be properly parsed by regexps.

People try, and try, and try to parse languages such as HTML using regular expressions. This has been extensively discussed here in SO, and you cannot parse HTML with regular expressions. There will always be an exceptional case in which your regular expressions would fail, and you would have to adapt it.

It might be the same with your language: if it is not regular, you should avoid lots of headaches and not try to parse it (and especially "transform" it) using regular expressions.

Answer 2

I'm having a lot of trouble understanding this question, but I think you will find it useful to learn something about term-rewriting systems, which seems to be what you are proposing. Whether the mechanism is tree rewriting (always works) or regular expressions (will work for some languages some of the time and other languages all of the time) is of secondary importance.

It is definitely possible to optimize object code by term rewriting. You probably also will benefit from learning something about peephole optimization; a good place to start, because it is very strong on the fundamentals, is a paper by Davidson and Fraser on a retargetable peephole optimizer. There's also excellent later work by Benitez and Davidson.