Preface
This section was straight grunt work, I will leave it at that. I can see now why making a compiler is a “programming feat”. Near the end I was so exhausted of doing all of this work that I ended up not even checking and definitely have stuff missing for the IR generation.
Why you may ask? Well in the compiler front end you first create a list of tokens, then turn those tokens into a tree called the AST. Now you have to parse through this large ass tree and turn it into ANOTHER tree (IR), then turn that tree into a list of trees (canonicolization), and THEN you later turn that into a list of instructions in the backend. The grunt work mainly came from first walking through the tree and all of the possible node types and endpoints in the semantic analysis stage, and then later on combining those nodes to actually form real logic and make sense of it in the IR stage.
During this month or so, I spent weekends working on this shit. The amount of structural work I had to do for the IR stage was crazy, plus the pKVM project that I am doing on top of that, I have not been having a life.
Oh yeah also as I am writing this I have been working on the instruction selection and parsing through the IR tree, and I made a lot of structural decisions I didnt know would kinda fuck me later. Youll see in the future. Anyways that is enough complaining, lets get started.
Chp 5: Type checking
There is nothing special in this chapter, just creating the structure for walking through the AST. The way the book wants to structure this is by having semantic analysis, activation records, and translation all in one mega module. That is why I am lumping this into the compiler “middle end” even though it is technically the compiler front end.
What we are implementing mainly on this semantic analysis chapter is the type checking, so for example I can’t have a string variable and an int variable doing operations with each other (in the tiger language there shouldnt be any pointer arithmetic). Anyways the way we mainly do that is to keep track of each symbol’s current type in the scope and then in every operation between symbols we check the types.
The book gives me modules for handling the scoping through a simple function call. The way this is implemented is by just having a hash map keyed by the symbol name and then also having a stack that keeps track of all variables defined in a scope. When you do a scope enter, the symbol "<mark>" gets pushed on the stack. When you do scope exit, it will pop all items until it reaches the mark, removing them from the hash map in the process. This also makes it easy to check if a variable is already defined in a scope. It’s all pretty simple.
The main annoying part is setting up parsing through every single type of node and through all of the AST. That took forever and was a lot of code written. I separated it into sem.c for the main parsing through the AST and then sem_sym.c for code that handles the symbols and types.
Chp 6: Activation records
In this chapter you mainly handle the creation and lookup of stack frames and variables in stack frames (activation records). This chapter is mainly spent setting up the intersection between the sem.c (semantic analysis) and the trans.c (IR translation) module. The reason is that the book wants me to make it so that the sem.c module does not touch the frame.c module but rather goes through trans.c. Basically we are doing the whole type checking and translation on a single pass, which is interesting to say the least, but it worked out and I am not complaining as I dont want to write the whole second pass.
Outside of designing the intertwinings, the whole chapter can be explained by these structs I made:
struct frame_t {
frame_t* static_link;
fal_t* formals;
fal_t* locals;
frame_ty_t* tys;
size_t stack_size;
int param_count;
bool shared;
};
typedef struct {
S_symbol sym;
bool in_stack;
int stack_off;
int reg;
} frame_access_t;
typedef struct {
S_symbol sym;
bool in_stack;
int stack_off;
int reg;
} frame_access_t;
struct frame_ty_t {
S_symbol sym;
frame_field_t* fields;
frame_ty_t* next;
};
struct frame_field_t {
S_symbol sym;
size_t off;
frame_field_t* next;
};
Let’s go through the important parts:
frame_t:- formals are basically function parameters
- locals are just local variables
- a static link points to the parent scope’s frame, this is for in case you are trying to access a variable that is part of the parent scope, you can find its offset in the stack frame
- shared is something I needed to add because I didnt want to have a for loop have its own function prologue and epilogue LMAO, so I just make it combine into the nearest real activation record
frame_access_t, self explanatory.offjust holds the variable’s offset in the stack frame from the frames base pointer (or frame pointer)frame_ty_tis self explanatoryframe_field_tis just a field that is part of a type and it holds its offset from the type
By the way, the type handling stuff I had to add once I was already handling IR, I am just putting it here because it is fitting. Also the book says that frame.c should be target architecture specific, but I ended up not writing anything x86_64 specific so I wonder if I did something wrong that will bite me later.
Chp 7: IR Translation
The real exhausting work. Unlike semantic analysis, this wasn’t as brainless and actually had to think. It was nicer because it wasn’t really repetitive work, but the amount of edge cases that I would have to think about and solve got exhausting after a few 10-12 hour sessions.
As I am writing this, I have already practically finished the instruction selection chapter and I will say that I did implement a lot of things in the IR that I should of left for the code generation part, which made both the code generation a little more of a pain in the ass as well as the IR. One example is that I manually set up the function prologues and epilogues myself and since the IR has no push or pop, I had to subtract from sp and then write to its memory and vice versa. Then in the codegen I had to check for these specific sequences to then turn them into a push or pop. I should try to remember to talk about this in the next compiler post.
Handling different functions
Following up on that previous paragraph, the way I have this designed is that each scope gets their own trans_t object that looks like this:
struct trans_t {
trans_t* parent;
frame_t* frame;
T_stm ir;
tfl_t* fun_list;
};
The ir and frame fields are the important ones, as while I am translating I am adding to the ir field and at the end it should form an IR tree for the specific function, then I prepend and append the prologue and epilogues respectfully. The fun_list holds the child functions and their respective labels to the function name symbols. What I also do is hold a separate list of ALL of the functions being created, then I add as a sequence all of the functions prepended with their function label to the final IR tree once translation is over. This creates the final program IR tree while having the functions as separate. Next chapter will turn them into separate blocks though, so keep in mind this is temporary.
Accessing variables outside of scope
On top of that, the probably most important implementation in the IR that I added has to be when you access variables from parent scopes. At first what I did was find how many static links up I had to go, and then dereference the frame pointer by that many times as it should be pointing to the previous frame pointer in the stack, this in theory walks up the stack frames, right??? Well take this into account:
var a = 10;
function f () {
return a + 3;
}
function g() {
return f();
}
f();
g();
Imagine the global scope does not have a .data or .bss region and a is concequentally located in the stack as a “global stack frame”.
This isnt a programming language, just pseudocode. If you were to think about it, both functions f() and g() have the same static link, which is the global scope. This means that the function call f() in the global scope will correctly access a as the stack frames are ordered that way. But when we go through g(), it will also dereference the frame pointer once, causing the function call f() to access variables in g()’s scope. This is no bueno.
As I was thinking about this, what I did to solve this was to pass the respective static link frame pointer as the first parameter in every function call, then the prologue would push both the fp and param_1, that way the walkup setup I had stays the same, but walks through different pointers instead:
void trans_funcall(trans_t* t, S_symbol fun) {
Temp_label label = NULL;
trans_fun_t* f;
T_stmList params;
int param_count = 0;
int stdlib_idx;
TRANS_SEM_ERR_RET();
stdlib_idx = trans_stdlib_idx(fun);
if (stdlib_idx >= 0) {
label = Temp_namedlabel(S_name(fun));
param_count = g_stdlib_param_counts[stdlib_idx];
}
// LOOK HERE!!!!!!!!!!!!!!!!!!!!!!!!!!
else if ((f = trans_fun_get(t, fun))) {
label = f->label;
param_count = f->param_count + 1; // static link frame
}
// !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
if (!label)
return;
params = trans_pop_funcall_params(t, param_count);
t->ir = T_Seq(t->ir, T_Exp(T_Call(T_Name(label), params)));
}
Custom types allocations
The book allows you to define your own custom types with multiple fields and variable sizes as well as arrays that dont have a predictable size at compile time. Because of that I will need to handle dynamic allocation for these types (also later chapters in Part 2 implement garbage collection).
Because of this I created a fake __ALLOC standard function handler (I am handling standard library function calls different to normal calls) and then do the whole logic for initializing the values and whatnot, you can read the source for that bit:
void trans_alloc_exp(trans_t* t, T_exp e) {
TRANS_SEM_ERR_RET();
trans_funcall_param(t, 0, T_Seq(NULL, T_Exp(e)));
trans_funcall(t, S_Symbol("__ALLOC"));
}
// the record ptr is in a tmp while i populate the rec
Temp_temp trans_rec_alloc_exp(trans_t* t, T_exp e) {
Temp_temp rec = NULL;
T_exp call;
TRANS_SEM_ERR_RET(NULL);
trans_alloc_exp(t, e);
call = trans_pop_exp(t);
if (!call)
goto out;
rec = Temp_newtemp();
trans_assign_exp(t, T_Temp(rec), call);
out:
return rec;
}
Other silly stuff
Some silly things that I did were for example for handling parameters for function calls I would make separate mov instructions to populate fake r0-r5 for params, then the function call. This means that I modified the function call expression node in the given files, but later on I realized that if the populations for each parameter were not straight forward (take f(g(1)-5+h()) as an example), then there might be some issues. So I added it back, but instead of an expression list for params, I made it a statement list lmao. Its whatever
Another thing I did that I had to fix was that I was handling conditionals as true would fall to the next instruction and false would branch, which is backwards. I fixed that later.
Chp 8: Blocks & Canonicolization
P.S. I am on an airplane and cant google how to spell canonicolization,so I bet it is wrong.
Lastly, this chapter does everything for you if you implemented the IR as intended. I did not so I had to do some fixup but it wasnt bad. All it does is canonicolize the IR by cleaning up all SEQ and ESEQ nodes, flattening the tree into a list of IR trees instead. Then also setting up every branch block into its own separate block and then making each function be its own fragment. I just imagined the block stuff like the block flow graph in ghidra, because that is basically it. For now they all jump around each other but I am assuming that there are optimization algorithms for finding the most optimal way to order these blocks to minimize jumps.