Hi again guys.
After a fairly long break I'm finally back in front of my monitor typing away on the
next chapter in the PxdScript tutorial series. We're getting closer now guys and gals
- it seems that this series will be finished after all :) Today's topic is
something as exciting as code generation - the second module in the compilers backend.
In this module we finally translate the high level source code into something (almost)
low-level enough to execute on our virtual machine, namely into symbolic assembly
code using our own custom instruction set.
I assume you have the stuff I described in chapter 7 about the layout of the VM fresh
in memory so that you understand how our VM operates on a stack to do its calculations
etc. If not then I suggest you browse through chapter 7 again to make your life easier
in this chapter.
Ok introduction aside - lets get started with the hairy stuff. I'll jump right into the technical details of the byte code instruction set that we'll compile PxdScript into. As I wrote in chapter 7 PxdScript is a stack-based language and I showed you a few instructions - or opcodes - from the instruction set, for example 'iadd', 'ldc_int', 'imul' etc. I also described how they operates on the stack - for example that 'iadd' pops two values of the stack, adds them and push the result back. There are of course many more instructions in our instruction set and below I'll list them all in a table along with a short description of what they do. Read through the list and try to understand the purpose and workings of each opcode. Don't worry if you can't remember them all when you're done reading - you can always use the table below as a reference.
|
Opcode |
Description |
| nop | No operation - do nothing. |
| imul | Pop two integers 'a' and 'b' from stack. Push 'a * b' |
| ineg | Negate the integer on top of the stack. |
| irem | Pop two integers 'a' and 'b' from stack. Push 'a % b' (the modulo operation) |
| isub | Pop two integers 'a' and 'b' from stack. Push 'a - b' |
| idiv | Pop two integers 'a' and 'b' from stack. Push 'a / b' (integer division) |
| iadd | Pop two integers 'a' and 'b' from stack. Push 'a + b' |
| aadd | Pop two strings 'a' and 'b' from stack. Push 'a + b' |
| goto | Read argument (label) from byte code and jump to it. |
| ifeq | Read argument (label) from byte code. Pop value 'a' from stack. If 'a' equals zero jump to the label. |
| ifne | Read argument (label) from byte code. Pop value 'a' from stack. If 'a' does not equals zero jump to the label. |
| if_acmpeq | Read argument (label) from byte code. Pop strings 'a' and 'b' from stack. If 'a' equals 'b' jump to the label. |
| if_acmpne | Read argument (label) from byte code. Pop strings 'a' and 'b' from stack. If 'a' does not equals 'b' jump to the label. |
| if_icmpeq | Read argument (label) from byte code. Pop integers 'a' and 'b' from stack. If 'a' equals 'b' jump to the label. |
| if_icmpgt | Read argument (label) from byte code. Pop integers 'a' and 'b' from stack. If 'a' is greater than 'b' jump to the label. |
| if_icmplt | Read argument (label) from byte code. Pop integers 'a' and 'b' from stack. If 'a' is less than 'b' jump to the label. |
| if_icmple | Read argument (label) from byte code. Pop integers 'a' and 'b' from stack. If 'a' is less than or equal to 'b' jump to the label. |
| if_icmpge | Read argument (label) from byte code. Pop integers 'a' and 'b' from stack. If 'a' is greater than or equal to 'b' jump to the label. |
| if_icmpne | Read argument (label) from byte code. Pop integers 'a' and 'b' from stack. If 'a' does not equals 'b' jump to the label. |
| ireturn | Return from function call. Treat top stack element as an integer return value of the function. |
| areturn | Return from function call. Treat top stack element as a string return value of the function. |
| return | Return from function call. There is no return value. |
| aload | Read argument (address) from byte code. Load string from stack at 'BSP + address' and push to top of stack. |
| astore | Read argument (address) from byte code. Store top stack element as string at 'address'. (at BSP + address) |
| iload | Read argument (address) from byte code. Load integer from stack at 'BSP + address' and push to top of stack. |
| istore | Read argument (address) from byte code. Store top stack element as integer at 'address'. (at BSP + address) |
| dup | Copy the top stack element and push to the stack. |
| pop | Pop the top stack element and discard the value. |
| iconst_0 ... iconst_5 | Load an integer value from 0 to 5 to the top of the stack. An optimization since these are very often used. |
| ldc_int | Read argument (constant integer value) from byte code and push to the stack. |
| ldc_string | Read argument (constant string value) from byte code and push to the stack. |
| cast_stringtoint | Cast top stack element from string to integer. |
| cast_booltostring | Cast top stack element from boolean to string. |
| cast_inttostring | Cast top stack element from integer to string. |
| call | Read argument (function to call) from byte code and call it. |
| setint_mdl |
*PxdScript specific* Pop the 3 top stack items
(mdlname as string, integer nr to set as integer, value to set it to as integer).
Call into game engine to the mdl model code with these values. See chapter 1 for more
information about this concept.
Similar opcodes exist for the other kind of entities: lights, cameras, the player and particle systems. |
| sleep | *PxdScript specific* Read argument (sleep time) from byte code. Halt program execution for 'sleep time' msecs. |
| sleep_trig | *PxdScript specific* Halt program execution until the program is 're-triggered' by its trigger event (on click, on collide etc.) |
As you can see most of the opcodes are very general and will probably be found in
almost every instruction set for a stack based VM. Only the last few opcodes are specifically
designed for PxdScript and those are the ones that operates outside the
virtual machine. All the rest are internal opcodes so to speak - they
simply keep the programs running in the VM and provides us with the functionality
we want to be able to program in PxdScript.
Most of the opcodes should be easy to understand but there are a few where you might
be wondering how they work exactly. For example the 'ldc' (load constant) opcodes
- how do you load a string from byte code? Or an integer? Isn't byte code 8bit values
only? Or what about the 'call' opcode - how exactly are we going to
call our functions? For now don't worry about those too much. Understand what they
do and just accept that they will do it. I'll explain them in a later chapter but
they uses things we have not talked about yet and those things are not important for
this chapter.
Well, now we have a large toolbox with lots of well-defined opcodes to work with.
Our task is now clear: we must translate our program from PxdScript into assembly
using only the instructions described in the table above. Then we must program a VM
that can interpret all of the above opcodes - but for now lets concentrate on the
first part: the code generation!
Ok, so how do we actually translate the PxdScript source into assembly code using
the above opcodes. Well, the important thing to remember in this chapter
is that we value correct code above optimized code! I mention this because
the code we'll generate in this chapter will be fairly un-optimized and
at certain points you might be tempted to try optimizing the generated code. Don't
do that! In this chapter we'll generate robust but slow code - but the code can be
optimized later in an optimization module. By trying to optimize the code here you
might actually break the correctness of the code in certain situations.
We'll generate the code in a recursive fashion by introducing code templates for
each language construct. This allows us to generate code for each language construct
while totally ignoring the surrounding context. You can think of these code templates
as building blocks you can build programs from by putting them after each other. If
the generated code for template A and B is correct and self contained then we know
that the program consisting of the combined templates 'AB' will also be correct.
Let me illustrate this idea of code templates with an example from PxdScript - the
while loop:
The language construct for the while loop looks like this:
While (EXP) STM
i.e.. "while the expression EXP evaluates to true, execute the statement(s) STM".
If we just had to produce code for the while loop, and knew nothing
about the surrounding context we could do something like:
:start:
EXP ; code to evaluate the expression
here which leaves the result on the stack
ifeq stop ; if the expression is 0 (false) jump to the label 'stop'
STM ; code for the body of the
while loop here.
goto start ; unconditional jump to start label
:stop:
Make sure you understand that the above code is indeed a while-loop written in assembly
using our instruction set. The 6 lines above is the code template for
the while loop. As long as the code for EXP and STM is also generated correctly the
above code will execute correctly no matter the context in which it is used. This
fits nicely with the way we currently have our code represented in our AST. Find the
STM node in tree.h and look at the whileS struct inside the union. The node
has two children - a conditional expression and a body consisting of a statement node
- and in the resource module we calculated two labels for it: a start label and a
stop label. This suggests a recursive strategy to generate the code for the while
loop. We follow the above template and recurs on the two children when the code for
them is needed in the template.
Now there are two rules - or invariants - which, if followed, will guarantee correct
code (if the templates are also correct).
A statement and a 'void' expression will leave the stack-height unchanged.
A non-void expression will increase the stack-height by exactly one.
The first rule guarantees for example that constructs such as a while-loop, an if-sentence,
a for-loop etc. will leave the stack height unchanged. This is to ensure that at any
given point in the code the stack height will be constant at any given time. For example
at the label 'start' in the template above the stack height will be some constant
number no matter how many iterations of the body we have executed. If this were not
the case and the stack height did depend on the number of iterations,
then we could not decide whether or not we have space left on our stack for the loop
and we could have a stack overflow while executing the code. With the invariant constraint
we can actually calculate the maximum stack height that a function or program will
ever have and use this information to decide whether or not we can call that program
or function in our VM. But this is something we'll have to calculate after the
code has been generated - we'll do this in the next chapter.
The second invariant simply guarantees that after the code for a non-void expression
has been executed, there will be a result on the stack that we can use in another
template.
As always there is an exception from the rule though - in this case the exception
is the function call. The function call is considered an expression but will affect
the stack slightly differently because arguments to the function are passed to it
by pushing them to the stack and is popped after the function returns. Therefore the
function expression might for example actually decrease the stack height if it has
more arguments than return values. In the next chapter we will write a function to
calculate the change in stack height that a given function call will result in. For
now don't think too much about it.
I'll not explain every single code template here because there are quite many of them
and you should be able to understand most of them by looking at the source code after
seeing just a few of them here. So I'll simply pick out a few examples and explain
those.
Lets start with some of the lowest level building blocks - those which does not recurs
further down the tree. It is after all those who makes out the leaves in our AST and
thus they are fundamental for many (or most actually) code templates. So how do we
generate code for expressions which are constants or variables for example? The template
for an expression of the type 'intconstK' consists of a single opcode plus an argument
(the value of the constant)
ldc_int 'value'
I'm sure you can figure out the templates for the other variable types yourself :)
Note that the template honors the stack invariant - the expression is non-void and
thus leaves the stack height one higher by pushed the loaded value to it.
The template for a variable lookup (or LVALUE) is also simple. In the resource module
we calculated the offset to the stack where each variable should be stored. So if
the variable is of type 'int' the template simply becomes:
iload 'address'
i.e.. again one opcode and one argument and again as it's
a non-void expression it increases the stack height by one.
Now lets look at the code template for a construct which seems extremely simple at
first glance but turns out to require a bit more code than expected - namely the Boolean
'not' language construct. So the language construct:
!E
has code template:
E ; generate
code to evaluate the expression
ifeq true ; if the expression is 0 (false) jump to the 'true'
label
ldc_int 0 ; if we gets here the expression is true (1). So
leave a false (0) on the stack and jump to the 'stop'
label
goto stop
:true:
ldc_int 1 ; leave true (1) on the stack.
:stop:
Make sure you understand that the template above actually leaves the logical 'not'
of the expression on the stack. Again since this is a non-void expression it increases
the stack height by one (and only 1! Why?).
Ok, lets leave the expressions for now and look at some of the statements. I explained
the while-loop template above and the other control statements (for-loop, if, if-else
etc.) follow the same idea so I'll leave those unexplained and ask you to look at
the source. The is however a small twist that is important to understand and that
is what happens with statement expressions - that is, expressions which
we consider as statements.
An expression can be a "statement" if one is not concerned with the result. (For example
if we calculate the expression but does not assign it to a variable)
An example of where an expression becomes a statement could be:
int a=5;
int b=8;
a+b; <--- This is legal in pxdscript
(like in C/C++) but the expression 'a+b' is then considered a statement
Another example is a call to a void function. A function call is considered an expression
- but if the function is of type 'void' it cant be placed on the right hand side of
an assignment. Thus a void function call is always an "expression statement"
So the code template for the statement expression
E
has the code template:
E
if the type of the expression is void - if the type of the expression is non-void we use template:
E
pop
to make sure the stack invariant is honored (a statement leaves the stack height unchanged
- remember?)
So why do I spend so much time explaining this little twist? Well, I do it because
it's important to remember if you want to understand how the 'assignment' expression
template works - if not it might look like voodoo to you. So an assignment expression language
construct:
x = E
has code template (assuming the type of 'x' is 'int' - slightly changed for string type):
E
dup
istore offset(x)
First we build code for the expression, then we take a copy of the result.
So now the result lies twice on the stack! The 'istore' opcode will
pop one copy and store it at the address of the variable 'x'. As a result the assignment
expression leaves one copy of the result on the stack and so the stack
height is increased by one as it should. If the assignment is actually a statement
expression it's type will be non-void as as the template above dictates it
will pop the second copy of the expression thus leaving the stack height unchanged.
The above might seem silly but let me restate my warning from above - do not try
to optimize the generated code at this point! For now the important thing is that
the generated code is correct regardless of the surrounding context!
The last template I'll talk about is the one for function calls. The template for
a call is easy enough - first it builds code to construct any arguments the function
might take and it simply puts a 'call' opcode. For example the function call:
someFunction(E1, E2);
will get code template:
E1 ; build first argument
E2 ; build second argument
call someFunction
Ok, there is a whole bunch of (much easier) templates that I didn't explain here - check those out in the source code and understand what they do.
Ok, a brief explanation of what's going on in the source code. First of all: this
time I've commented the source code very well (I think) so it should be easy to read
and understand. There are a few functions that need explanation though:
The first section of the code contains utility functions to make life a bit easier
later on. Look in tree.h for the struct 'CODE'. This is the structure we'll
use to hold our opcodes and the code segment of a function or program will be a linked
list of CODE structures. Notice that all opcodes which uses arguments stores those inside
their CODE structure. These arguments can be offsets (for the load and store
opcodes), constants (for the ldc_ opcodes) or label offsets for branching opcodes.
In the very top of the source there are 3 global variables:
CODE *currentcode;
CODE *currenttail;
LABEL *currentlabels;
These will be used to maintain the linked list of CODEs for a function or program.
Next follows a whole bunch of small functions which uses functions defined in tree.c to
actual allocate and initialize the needed CODE structs.
Further down you'll see 3 functions which are of interest:
char *codeType(TYPE *t)
char *codeFormals(DECL *f)
char *codeSignature(DECL *f, TYPE *t)
These are used to build a function signature for a function. A function signature is a short description of the function regarding the type and number of inputs it takes and the type of the return value. We need this signature in the next chapter to be able to calculate the stack-height change a function call will result in! Let me give an example:
int myIntFunction(int a, bool b)
will result in a signature:
(IB)I
meaning - it takes an 'int' and a 'bool' parameter - and returns an 'int':
void myIntFunction(int a, bool b, string c)
would have the signature:
(IBS)V
get it??
Finally you'll see the by now so familiar recursive run through the AST in which we
implement all the code templates described above. When the run has finished we will
have assigned the 'labels' and 'opcodes' members of the FUNCTION and
PROGRAM struct with the correct linked lists of CODEs and LABELs.
And now is the time where I will simply say: go read the source code and understand
what's going on - because I'll not explain it any further. Of course if you have problems
with a specific part feel free to send me an email and I'll be happy to help you out.
Good luck with generating some code :)
All right!! We've successfully generated the assembly code for our PxdScript program
- but it's not much fun as we can't really see it in a text file to make sure everything
works :(
But never fear - next chapter is a super short one which only deals with just that
- getting the assembly code out in a text format so we can look at it and make sure
everything works like it should. And because I know how much you're burning to see
the generated code I'll write that chapter right away - so expect it to appear very
soon (if it's not already there when you read this)
As always - send comments about what you think of this chapter and if there is something
that is very unclear I might update the chapter with more in-depth information on
that particular area. See you in a short while in chapter 9.
Keep on codin'
Kasper Fauerby
www.peroxide.dk