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

Tommy Thorn <tommy.thorn@gmail.com>
21 Sep 2006 10:33:00 -0400

          From comp.compilers

Related articles
Generating a simple hand-coded like recursive descent parser mr.waverlye@verizon.net (Mr.E) (2006-09-08)
Re: Generating a simple hand-coded like recursive descent parser tommy.thorn@gmail.com (Tommy Thorn) (2006-09-10)
Re: Generating a simple hand-coded like recursive descent parser mr.waverlye@verizon.net (Mr.E) (2006-09-11)
Re: Generating a simple hand-coded like recursive descent parser tommy.thorn@gmail.com (Tommy Thorn) (2006-09-12)
Re: Generating a simple hand-coded like recursive descent parser mr.waverlye@verizon.net (Mr.E) (2006-09-16)
The 30 min optimizing native code compiler [was: Generating a simple h tommy.thorn@gmail.com (Tommy Thorn) (2006-09-21)
| List of all articles for this month |

From: Tommy Thorn <tommy.thorn@gmail.com>
Newsgroups: comp.compilers
Date: 21 Sep 2006 10:33:00 -0400
Organization: Sonic.Net
References: 06-09-02906-09-042 06-09-048 06-09-060 06-09-078
Keywords: code

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


Post a followup to this message

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