PxdScript language tutorial series.

Chapter 8 - Code Generation:

by Kasper Fauerby

Introduction

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.

The PxdScript opcodes

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!

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).

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.

Code templates

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.

The source code

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 :)

Checklist

Final words

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