Generating register based bytecode from an abstract syntax tree?

Question

What are some well known strategies for generating register based bytecode from a given anstract syntax tree (AST)?

Consider this expression 1 + 2 - 3 * 4 / 5 and its AST form:

bin_exp(-)
    bin_exp(+)
        num_exp(1)
        num_exp(2)
    bin_exp(/)
        bin_exp(*)
            num_exp(3)
            num_exp(4)
        num_exp(5)

I'm struggling to convert the AST into its corresponding bytecode procedurally. So far I have only found one article, in which it only briefly talks about it. My interpretation of what it's trying to say...

int ridx; // register index

function visit_exp(exp)
{
    switch (exp)
    {
        case bin_exp:
            visit_exp(exp.left);
            visit_exp(exp.right);

            printf("add %i, %i -> %i\n", ridx - 2, ridx - 1, ridx);

            // save ridx, as it contains the result
                    break;
        case num_exp:
            printf("mov %i -> %i\n", ridx, exp.value);
            break;
    }
}

Please give me a hand, thanks.

Answer 1

Do the following:

• Give each expression node a unique number en. You can do this as you walk over the tree, on-the-fly.
• For leaf node numbered el, generate "MOV el, operand"
• For each interior node "OP" numbered er, with binary children es and et, generate "OP er, es, et". Use the obvious generalization to handle operators with arbitrary numbers of children.

This will produce "naive" code, in the sense that the virtual register numbers can be arbitrarily large (e.g., determined by the size of the program).

A more sophisticated version would keep a pool of node numbers, assign the lowest available number from the pool to each node as you encounter them from left to right, and put the numbers for the OP-instruction input operands back in the pool (as they are now "free") as each OP instruction is generated. This will produce in practice a much smaller set of virtual register set numbers.

If you want to get clever, after you have done the above, apply register coloring to the generated code, to enable using a fixed number of registers.