The 30 min optimizing native code compiler [was: Generating a simple hand-coded like recursive descent parser]

Mr.E wrote:
> Thank you very much.
>
> Just looking at the code I almost understand it all. I'm looking
> forward to running it.


Thanks.


The example I posted was just the basics to get started, but it's enough
to allow me to make a point about the value of an internal representation.


Once you have the AST, it's much easier to add transformation and
optimizations. Fx. to eliminate (some) common subexpressions, all that
is needed is to instrument the tree building function "mk()" to search
for previous occurences, eg.:


ast_t mk(token_t kind, ast_t l, ast_t r, int k)
{
        for (p = &nodes[0]; p != &nodes[next]; ++p)
              if (p->kind==kind && p->l==l && p->r==r && p->intValue==k) {
                    p->shared = 1;
                    return p;
              }
        ...


In addition, the code generation must of course save and reuse the value
of a common subexpression.


Constant folding is also very easy at this point:


        // k1 + k2 -> [k1 + k2]
        if (kind == '+' && l->kind == INT && r->kind == INT)
              return mk(INT, 0, 0, l->intValue + r->intValue);
        // k1 * k2 -> [k1 * k2]
        if (kind == '*' && l->kind == INT && r->kind == INT)
              return mk(INT, 0, 0, l->intValue * r->intValue);


As are some algebraic simplifications:


        // x * 0 -> 0
        if (kind == '*' && r->kind == INT && r->intValue == 0)
              return mk(INT, 0, 0, 0);
        // x * 1 -> x
        if (kind == '*' && r->kind == INT && r->intValue == 1)
              return l;
        // x + 0 -> x
        if (kind == '+' && r->kind == INT && r->intValue == 0)
              return l;


I've put up a cleaner version of the expression compiler with these and
other enhancements on http://not.meko.dk/Hacks/Compiler


Tommy

Return to the comp.compilers page.
Search the comp.compilers archives again.