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.
Do the following:
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.
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With