Memory Management in PIRC

Introduction

PIRC is a new implementation of the PIR language, and currently under heavy construction. While the code is documented, it does not provide an easy overview of implementation issues and design decisions. In order to solve this documentation gap, I'm writing these design decisions in a series of parrotblog.org articles. This very short article discusses the memory management of PIRC. 

The current PIR compiler, IMCC, has had a lot of memory leaks, most of which have been solved by now. Although conceptually manual memory management through malloc() and free() is very simple and straightforward, things become ugly once you loose overview of when datastructures go out of scope, and as a result you forget to free the memory. In PIRC a different approach is taken.

Note that instead of using malloc() and free() directly, you should use mem_sys_allocate() and mem_sys_free(), respectively, which are provided by Parrot.

Cheater!

PIRC parses the PASM or PIR input, builds a data structure, and generates a Parrot Byte Code file (a so-called Packfile). (at the moment of writing, the PBC is not generated yet, but work is underway to fix this; might take a while, though). The data structures that are created represent the PASM or PIR program being parsed, and as such can be considered an Abstract Syntax Tree.

As these data structures are used throughout the compilation phase, PIRC can cheat with memory management. Instead of freeing the memory of the data structures by manually calling mem_sys_free(), PIRC keeps track of all allocated memory blocks. Only when PIRC is done with the bytecode generation will it release all resources. This is fine, because the data structures are needed up to the end anyway, so memory is not occupied longer than necessary.

Poor Man's Garbage Collector

Whenever PIRC needs memory, a block of memory is allocated through Parrot's memory allocation function, mem_sys_allocate() (or a variant, which zeroes out all bytes). Before returning a pointer to the allocated block of memory, however, PIRC stores a pointer to the block of memory as well (in a list), and only then is the pointer to the block returned.

When PIRC is done with compiling, it will go through the list of memory pointers, and release the memory pointed to by each of the pointers. In a sense, you could consider this a garbage collector, except that there's no reuse of memory (but there's no need to anyway).

"Wait a minute," you might say, where are these pointers stored then? Well, of course, these pointers are stored in an extensible list, as we don't know the number of pointers to store beforehand. Surely the list cannot be allocated and store a pointer to itself.  This is fine, because the problem of keeping track of memory is now isolated to a single point in the program. The nodes in the list of allocated memory pointers are allocated directly through Parrot's memory functions. When all stored pointers are mem_sys_free()d, we only have to remember to mem_sys_free() these nodes. 

In this way, there's no need to worry about when pointers should be freed: it's done automatically, as long as PIRC allocates its memory through its built-in memory management system.

List of Pointers

Obviously, we don't want to create a new node for each pointer to store. Instead, a node can store a number of pointers, currently set to 512. So, after allocating memory for 512 times, a new node is created. This number of 512 was decided upon after some experimentation, but might prove too low for real world PIR input. As it's #define'd, it's easy to change, though.

Summary

In this very short article, I described how PIRC does its memory management. PIRC cheats a bit, by storing each pointer to an allocated block of memory in a special list. Once PIRC is done with compiling, all these pointers are passed to mem_sys_free(), Parrot's free() function (one by one, obviously). This way, you don't have to worry about when to free the memory in PIRC.

Parsing heredocs with PIRC

Introduction

The PIR language allows you to write so-called heredocs, as known from Perl (and I believe the idea was stolen from some older languages). If you're not a Perl programmer (like me), you might wonder what the heck I'm talking about. So, let's start with a simple example (using PIR syntax):

$S0 = <<'CODE'

This is a heredoc string

over

multiple 

lines

CODE

So, using the special <<"CODE" is stored in register $S0. So, the string stored in $S0 is:

"\nThis is a heredoc string\nover\nmultiple\nlines\n"

Want to see for yourself? 

cd compilers/pirc

make

export LD_LIBRARY_PATH=../../blib/lib

./pirc <file>

Not too difficult, eh? Well... you're right, until you use multiple heredocs in, for instance, subroutine arguments. Many Parrot tests use Perl scripts to specify the input (code) and the expected output. That's done like this:

pir_output_is(<<'CODE', <<'OUTPUT');

.sub main

   say 42

.end

CODE

42

OUTPUT

PIR also allows multiple ("nested" if you want, but they're not symmetrically nested; a better word would be "overlapping") heredocs. The current PIR compiler (IMCC) cannot handle this, but the new PIR compiler (currently still under development) PIRC, can. In an attempt to maximize the "truck number" of PIRC (which is currently estimated to be 1), I'm trying to do as much documentation of PIRC as possible. In this article, I'll be discussing how heredoc parsing is done in PIRC.

Single heredoc parsing

Let's start out simple with a single heredoc string. The heredoc preprocessor is implemented in the file compilers/pirc/new/hdocprep.l. Yes, that's right, that's not a C file, but a Lex specification file. Using Lex (and it's probably Flex that you'll be running, a faster implementation of Lex), the .l file is converted into a C file.

Now, for this discussion I'll assume that you know a bit about using Flex. A particular (advanced) feature of Flex-generated scanners (or "lexer" if you want) is the use of states. Using states you can implement several scanners in a single specification. Based on the state that the lexer is in, it'll recognize a subset of the rules. If no rule is specified, then the built-in, default INITIAL state is assumed. States can be pushed and popped of a stack, also managed by the generated C file. Whenever a new state is pushed onto the stack, that becomes the active state, and all rules that are specific to that state will become active. Once the state is popped of the stack, the rules fall out of scope again, and the state at the top of the stack (after popping) will become active.

So, the trick that's used is, as soon as the heredoc marker is read (e.g. <<'CODE'), we enter a new state, which will read the input line by line. All rules of the previous state are no longer active, so strings such as "<<'OUTPUT'" won't be matched, but instead are stored in a string buffer. After reading each line, it will check whether the heredoc end marker was read. As soon as the end marker is read, the heredoc scanning state will be popped, and scanning will continue in the initial state.

Single heredoc strings as subroutine arguments

Consider the following PIR line:

foo(<<'CODE', 42, 'hi')

After reading <<'CODE', the scanner will continue scanning in the heredoc state. However, the rest of the line, containing ", 42, 'hi')" should be stored somewhere, as this is not part of the heredoc.  So, the "rest of the line" is scanned, stored in a buffer, and then the heredoc scanning can start. After reading the end marker of heredoc, the scanned heredoc is printed to the output, after which the "rest of the line" can be scanned. Not so hard, eh?

Scanning multiple heredocs

Things get more interesting when you need to scan input like the following:

foo(<<'CODE', 42, <<'OUTPUT', 'hi')

.sub main

 say 42

.end

CODE

42

OUTPUT

Scanning the first heredoc string works fine; the "rest of the line" is then:

", 42, <<'OUTPUT', 'hi')"

After scanning the first heredoc, we tell the lexer to start retrieving the next characters from the "rest of the line" buffer. When scanning this line buffer, we'll encounter the <<'OUTPUT' marker, which indicates another heredoc string. At this point, we need to re-save the "rest of the line", which will contain:

, 'hi')

At this point, we need to continue scanning from the input file, after the point we left off after scanning the first heredoc. So, off we go, again switching input buffers in the lexer, so that the contents of the second heredoc string are scanned. Again, scanning line by line, checking for the heredoc end marker. Again, once we find the end marker, we'll switch back to the "rest of line" buffer, and finish scanning that string. Once we read EOF on the line buffer, again we switch back to the input file, and the rest of the file is scanned as if nothing happened.

Heredoc preprocessing

The heredoc handling is implemented as a separate pass over the input file. This was done to keep the complexity of the lexer manageable. Although this does result in more I/O operations, having better readable code is, IMHO anyway, a more important goal than presumably faster code, that is hard to maintain. Currently, the output of the heredoc preprocessor is written to a temporary file, of which the PIR lexer is reading.

Including files

The PIR language has a C-preprocessor-like #include directive, spelled as ".include". Logically, it's part of the macro layer, as the include directive is replaced by the contents of the specified file. However, as an included file may contain heredoc strings as well, the whole invocation scheme of the PIR compiler becomes more complex, as that included file must be handled by the heredoc preprocessor as well. 

So, PIRC cheats a bit. Instead of implementing the .include directive in the macro layer, it is moved "forward" to the heredoc preprocessor. This way, the heredoc preprocessor converts all heredoc strings into normal strings (a process I like to call "flattening the string", as the multi-line string is now flat, meaning it's a one-line string), and stores the contents of all included files into the temporary file. PIRC's normal lexer only ever sees one single input file, and does not need to handle the .include directive.

Summary

This article discusses the implementation of the heredoc preprocessor. PIRC allows you to use multiple heredoc strings in a single PIR statement, which introduces some complexity to the lexer. For that reason, heredocs are processed in a separate pass over the input. Besides handling heredocs, the .include directive is handled in the heredoc preprocessor as well, to make life a bit easier for myself.

Register allocation in a PIR compiler

Introduction

As some of you may know, I have been working on a new implementation of a PIR compiler, which is named PIRC. In the end, my plan is to emit actual Parrot Byte Code (PBC), which can then be run by Parrot. Once everything's working and tested properly, I will make a case for replacing the current PIR compiler (IMCC). It might take a while before I get to that, though.

In the mean time, I'm trying to make PIRC as feature-complete as possible, and will try to write up some of the implementation issues that have to be dealt with. This can be interesting for lurkers, who 'have always wanted to know how to do it', but also just as a way to document things.

In this article, I will discuss the implementation of a recently added feature: a register allocator. Now, the implementation I came up with still needs a lot of testing, but the idea behind it does not change. The algorithm I chose is Linear Scan Register (LSR) Allocation, which is described in detail here. This algorithm is very different from the more well-known (classic, if you like) register coloring algorithm, which is based on graph coloring theory. I won't go into details too much, except mentioning that while a register coloring algorithm can yield more efficient register usage, but is a lot more expensive in terms of processor cycles, compared to the LSR algorithm. Obviously, for dynamic languages, where runtime compilation is a common feature, this is an important feature.

Register allocation

First, a short review of register allocation. I will make some rough simplifications just for the sake of this discussion, so I probably will make some false statements here. In real CPUs, there's a limited number of registers. This is fine, as long as the number of registers is larger than the number of variables that are alive. However, once you have more variables than registers, you need to overwrite a previously used register. If the value in the register being reused for another variable is going to be used after this overwriting, then you need to make sure the value is stored somewhere temporarily, typically in memory. This is called register spilling. Then, later, when the variable that was 'spilled' is referenced again, it needs to be reloaded into a register, overwriting that register's current value, which again needs to be spilled.

In short, you typically have to map N variables onto M registers, and if N > M, you need to spill registers.

In the Parrot virtual machine, this is not necessary. Parrot allows a subroutine to have as many registers as possible (up to the physical limitations of your memory, obviously). If a subroutine needs 50 registers, then it will happily allocate those. After all, Parrot can be considered a CPU in software, which uses memory for anything where a hardware CPU uses... eh... well, hardware. (Of course, memory chips are hardware... oh well, you get my point).

In any case, this is good news for any register allocator in the PIR compiler, as it makes the job of register allocation extremely simple. PIRC has a 'vanilla' register allocator, which allocates registers using a counter, starting at 0, and increment the counter whenever it needs a new register.

However, it's still a bit of a waste. If you look at typical PIR output of Rakudo, the Perl 6 implementation running on Parrot, then you'll see it's a lot of code. A Lot. It would be good if registers can actually be reused, if the variable that it represents is never referenced again. After all, as you now know, Parrot allocates as many registers as it needs for any given subroutine, and obviously, less is better, as it saves memory.

(Ok, I admit it, I really just did it because it was a nice challenge to implement).

Now you know why register optimization is useful, let's discuss some basics of the algorithm that was implemented.

Linear Scan Register Allocation

The Linear Scan Register Allocation (LSR) algorithm is really quite simple. The basic idea is that, each variable has a certain life time. In a programming language, a variable typically has a scope, which is the maximum life span of a variable (because it will go out of scope after the scope has closed. Are you still with me?) . However, the fact that a variable has a scope doesn't mean it's being used throughout the whole scope; it's very possible, and likely, that a variable is only used in one or two statements in the scope. So, suppose there are two variables, say, foo and bar, which have mutual exclusive life spans, (this means they never live in the same 'era'). This means they can both be mapped to the same register. This is the fundamental idea behind the SLR allocator.

Data structures
First, I need to explain some basic data structures that are used in PIRC. I won't do this in too much detail; that would be a good topic for some other time.
PIRC has basically two important parts: the parser, and the back-end. The parser is implemented using a Bison (I think it uses some features that are not Yacc-compatible) specification. The back-end is a bunch of data structures that are manipulated during the parse.
In the context of register allocation, the most important data structures are the structs target, symbol and pir_reg. A symbol is a declared .local identifier; a pir_reg represents a PIR symbolic register (like $I42). A target represents a so-called l-value object; this is an object that can be assigned to. Basically, symbols and pir_reg objects have a one-to-one mapping w.r.t. the symbol or symbolic register they represent, while targets have a many-to-one relation w.r.t. the underlying symbol or pir_reg. So, suppose you declare a .local int foo, then there will be a single symbol object representing foo, but there may be many target nodes pointing to this symbol.
As symbols and pir_regs are only created once for the target they represent, the vanilla register allocator (which is a very basic, dumb allocator) will assign a new register to each new symbol/pir_reg object. Whenever a target is being parsed (and it's easy to recognize whether it's a identifier or a symbolic register), the symbol or pir_reg object for that target is looked up, and linked to the target node.
This link is very important, because it is used to tell the symbol (from now on, wherever you read symbol, you can interpret it as 'symbol or pir_reg') that it is used in the current instruction. During the parse, the compiler keeps track of an instruction counter, which just assigns numbers in a consecutive way to the instructions. So, basically whenever a target is parsed, it updates the life span of the symbol. The first usage of an identifier indicates the first usage of that symbol (and not its declaration: you may declare a symbol, but never use it).
What this means is, that after the parse, for each symbol (.local identifier and symbolic register), we have a life interval object, which knows when is the first usage of the symbol, and when is the last.

Implementation
Once you know when the variables are used, it becomes extremely simple to optimize the register usage. Basically, you iterate through each life interval object, you assign the symbol it represents a new register (a real parrot register like P2, not a symbolic register, like $P2), and you place the live interval object into a list of "active" variables. Each iteration, you walk through this list, and "expire" any live intervals that represent symbols that are no longer used. For this, the interval objects that you're iterating over must be sorted. Whenever a live interval has expired, the register it was assigned becomes available, so you can put that register on a "free" list; the next time you need a new register, you first check whether there's any "old", previously used registers are available. If not, you just increment a counter, increasing the total number of registers that Parrot must allocate.

This all might sound very complex, but, really, it's not. The implementation is only about 200 lines of code or so (that's a wild guess), and can be found in compilers/pirc/new/pirregalloc.c.

Of course, the thing needs to be properly tested, but the basic idea stays the same. There's still quite some work to be done in PIRC anyway.

Conclusion
In this article I tried to explain the implementation of a register allocator, which optimizes the register usage of code generated by PIRC, a new PIR compiler. The basic data structures were briefly explained, and the algorithm was summarized. Experience should show whether the investment was worth it, or that more heavy-weight implementations, such as graph-coloring-based algorithm should be used.