Implementing Pointers

Since the last update, progress has been a bit slow, but I’ve managed to get very basic pointers up and running. The compiler still only supporting one data type makes things easier with regard to data width. The main steps in implementing pointers were as follows:

Pointer Parse Rules

The abilities of pointers necessitate the addition of two main complexities in parsing. The first is the ability to declare variables at different levels of indirection (var vs var * vs var **, etc). This is simply handled by nesting a declared name under a one-legged subtree of “dereference” (*) tokens correspondingly deep. The second is the ability to arbitrarily use the dereference operators in expressions. Identically to c, the dereference operator is used to both read from and write to addresses denoted by sub-expressions depending on its placement.

Pointers and the Symbol Table

Because pointer declarations are nested as children of dereference operators, it’s easy to recurse during the first AST traversal to count how many levels of indirection a declaration specifies. Tracking this in the symbol table entry for each variable is then as simple as an integer count of indirection level. This should hold even when implementing different types down the road. Keeping track of how indirect a variable is will also enable the implementation of indirection level checks in the future. This will make it relatively easy to prevent writing var to var* and other such errors.

Intermediate Code for Pointers

When on the left-hand side of an expression, a single dereference operator signifies a write to the memory address dictated by the pointer subexpression following it. A pointer subexpression, including more dereference tokens, is treated the same as a pointer expression on the right-hand side. On the right-hand side of an expression, a dereference operator signifies a read from the memory address pointed to by the memory address dictated by its subexpression.

Assembly Generation and Register Allocation

Since pointer arithmetic ultimately just boils down to regular arithmetic, the only thing to deal with (for now) is just generating instructions to read and write memory when necessary. Optimizing pointer arithmetic and using different addressing modes are things that can happen down the road. For now it just needs to work.

Benchmark Improvements

Including the source and assembly for the benchmarks in the last blog post cluttered things up too much. For the actual source code and generated assembly, look here. Using pointers instead of recursive algorithms to find primes and fibonacci numbers (unsurprisingly) resulted in phenomenal performance gains. In the future I’ll have to think up some more complicated benchmarks to run.

Benchmark recursion only unoptimized pointers
First 20 Fibonacci numbers: 859,483 461
Just the 20th Fibonacci number: 328,363 461
All primes under 1000: 6,923,578 32,108

Post-Benchmark Horrors

After running the benchmarks, the logical next step was to implement some other tests. Unfortunately, this is where things fell apart. The overly-simplisic and greedy register allocator I had implemented to get codegen up and running just couldn’t handle everything being thrown at it. It happened to work well enough to hold together for the updated benchmarks, but anything more broke it. Things were ending up in the wrong place, lifetimes were getting mismatched, everything imploded all at once.

This means that optimizing pointers is now a lower priority than implementing proper register allocation and lifetime management. Improving pointer arithmetic linearization, and adding indirection level checks will have to come later. The next blog post will more than likely be an overview of a proper implementation of Linear Scan register allocation to get everything back on track.