Version 21 (modified by kjs, 5 years ago)

--

PIRC Introduction

PIRC is a fresh implementation of the PIR language. It is being developed as a replacement for the current PIR compiler, IMCC. Somewhere in the future, we all hope to be able to finish it. However, some help is needed. Most of the tricky parts have been done for you, such as implement all sorts of weird features of the PIR language.

The basic workflow of PIRC is as follows. The lexer and parser are implemented with Flex and Bison specifications. During the parsing phase, a data structure is built that represents the input. To stick with compiler jargon, let's call this the Abstract Syntax Tree (AST). After the parse, this AST is traversed and for each instruction the appropriate bytecode is emitted. Registers are allocated by the built-in vanilla register allocator. This means that for the following code:

.sub main
  $S12 = "Hi there"
  print $S12
  $I44 = 42
  print $I44
.end

$S12 and $I44 will be mapped to the registers S0 and I0 respectively (yes, you guessed it, it starts allocating from 0). As you would expect, the vanilla register allocator is pretty stupid, but the generated bytecode is not too bad, really. If you want to optimize the register usage (which saves runtime memory), you can activate the register optimizer. The register optimizer is based on a Linear Scan Register allocator. The original algorithm, as described in  this paper, assumes a fixed number of available registers. Since Parrot has a variable number of registers available per subroutine, the algorithm has been changed here and there. See the file [source:/trunk/compilers/pirc/src/pirregalloc.c] for the implementation.

PIRC vs IMCC

While PIRC is an implementation of the PIR language which is specified in PDD19, there are some subtle differences with the current implementation, IMCC. In case you were wondering, IMCC stands for IMC Compiler, with IMC being the old name of the PIR language, standing for Intermediate Machine Code. The name was changed a long time ago.

  • "nested" heredocs, can be handled by PIRC, not by IMCC. Yes, it was very painful to implement which is why IMCC doesn't.
  • comments or whitespace in the parameter lists are accepted by PIRC, but not by IMCC. It sounds like an easy fix, but it isn't. Hence, PIRC!
  • reentrant: PIRC is, IMCC is not.
  • checks for improper use syntactic sugar with OUT arguments, such as "$S0 = print". PIRC checks for this, IMCC doesn't. Again, it sounds (and looks) like an easy fix, but it isn't.

Building and running PIRC

PIRC is located in compilers/pirc. In order to compile, do the following:

cd compilers/pirc
make
make test

At this point (August 5, 2009) some tests are failing, so don't be alarmed if you see them failing.

In order to run PIRC:

./pirc -h
./pirc -b test.pir # will generate a file a.pbc

Enjoy!

PIRC Status

PIRC is not complete yet. All stages are implemented (lexer, parser, bytecode generator), but all of them need some additional work to complete them. See the section below for the specific items that need to be fixed. Once these are fixed, PIRC will be done about 98%.

PIRC Development Tasks

Shouldn't-be-too-hard tasks

  • ticket #43: autoheaderize all PIRC sources.
  • ticekt #55: decorate all function arguments with ARGIN macros etc.
  • write tests for the generated output.

Hardcore hacking tasks

  • Fix parser to "calculate" the right signature for ops such as:
    $P0 = new ['Integer']
    

Currently, the argument is encoded as "_ksc", for key, string-constant.

  • Convert all C strings in PIRC into STRINGs. All identifiers and strings that are scanned should be stored as STRING objects, not C strings.
  • Fix ticket #198. It seems that when there is a sequence of more than one instruction dealing with STRINGs or NUMs, the resulting bytecode segfaults. Apparently, PIRC is emitting the wrong bytecode. Bug #186 is related to this issue.
  • Fix ticket #173. Lexicals are not stored correctly in the generated bytecode. The code for storing the lexicals is taken from IMCC, and therefore it doesn't come as a complete surprise it's not working. However, I don't see what's wrong.
  • Fix ticket #14. Braced arguments to macros are not handled correctly. Nested macro expansion isn't correctly handled yet.
  • Fix ticket #163. Keyed multi types must be implemented

PIRC Internals

In this section, PIRC's guts are dissected in order to explain what exactly is going on under the hood. If you are interested in the nitty-gritty details, keep on reading. (Note that this is a work-in-progress and will take some time to be completed)

PIRC Lexer

Heredoc processor

The Heredoc processor has only one task: flattening heredoc strings. By "flattening", I mean the following. This string:

 $S0 = <<'EOS'
This is
 a multi-line
  heredoc
   string
    with
     increasing
      indention
       on each line.
EOS

is "flattened" into:

 $S0 = "This is  a multi-line\n  heredoc\n   string\n    with\n     increasing\n      indention\n       on each line." 

Note that "newline" characters are inserted as well, so that the string is equivalent to the original heredoc string. Besides assigning heredoc strings to String registers, the PIR specification also allows you to use heredoc strings as arguments in subroutine invocations:

.sub main
  foo(<<'A')
This is a heredoc
string argument
A
.end

.sub foo
 # ...
.end

Again, the heredoc string (delimited by the string "A") will be flattened. According to the PIR specification, you can even pass multiple heredoc string arguments, like so:

.sub main
  foo(<<'A', 42, <<'B', 3.14, <<'C')
 I have a Parrot
A
 It is not a bird
B
 It is a virtual machine
C
.end

Note that the heredoc arguments may be mixed with other, simple arguments such as integers and numbers. In the rest of this section, the implementation will be discussed.

Heredoc parsing implementation

The implementation of the Heredoc preprocessor can be found in [source:/trunk/compilers/pirc/src/hdocprep.l]. It is a Lex/Flex lexer specification, which means you need the Flex program to generate the C code for this preprocessor. The preprocessor takes a PIR file that contains heredoc strings, and flattens out all heredoc strings. It writes a temporary file to disk that is exactly the same as the original PIR file, except that all heredoc strings are flattened.

For this discussion, it is assumed you have a basic understanding of the Flex program. For instance, you need to know what "state" means in Flex context. If you don't know, please refer to  the Flex documentation page.

In order to make the heredoc preprocessor reentrant, no global variables are used. Instead, lines [source:/trunk/compilers/pirc/src/hdocprep.l#L83 83 to 98] define a struct global_state. The comments in the code briefly describe what each field is for, but they will be discussed in more detail later if we walk through the actual processing of the heredocs. A new instance of this struct can be created by invoking [source:/trunk/compilers/pirc/src/hdocprep.l#L157 init_global_state]. For now, it is useful to know that this struct has a pointer to a Parrot interpreter object, the name of the file being processed, and a pointer to the output file.

The function [source:/trunk/compilers/pirc/src/hdocprep.l#L208 process_heredocs] is the main function of the heredoc preprocessor that the main compiler program (PIRC) invokes. This function opens the file to be processed, initializes the lexer, creates a new global_state struct instance, as described above, invokes the lexer to do the processing and cleans up afterwards.

We will now walk through two different scenarios, in order to simplify the discussion. Scenario 1 discussed the case of single heredoc parsing, and Scenario 2 discusses multiple heredoc parsing. Multiple heredoc parsing starts out with Scenario 1, but is a bit more advanced.

Scenario 1: single heredoc parsing

Consider the following input:

.sub main
  $S0 = <<'EOS'
This
is
a
heredoc
string.

EOS
.end
 

The lexer starts out in the INITIAL state by default (as per Flex specification). When reading input such as <<'EOS', the rule on [source:/trunk/compilers/pirc/src/hdocprep.l#L306 line 306] is activated. The actual string ("EOS") is stored in the field state->delimiter, and an escaped newline character is stored in the heredoc buffer.

Since the preprocessor does not build a data structure representing the input, but instead writes the output directly (to a file), the "rest of the line" needs to be stored somewhere. This is because the <<'EOS' heredoc token is basically a placeholder for the actual (heredoc) string contents. Hence, the [source:/trunk/compilers/pirc/src/hdocprep.l#L318 activation of SAVE_REST_OF_LINE state].

The state SAVE_REST_OF_LINE has only one function, and that is to SAVE the REST OF the LINE :-). It will match all the text after the <<'EOS' heredoc marker up to and include the end-of-line character. This, including an additional "\n" character is stored in the linebuffer field, which always contains the "rest of the line". As you can see, in this scenario there is no "rest of the line", except for the end-of-line character ("\n", or "\r\n" on Windows).

After the heredoc marker the actual heredoc string must be scanned, hence the activation of the HEREDOC_STRING state on [source:/trunk/compilers/pirc/src/hdocprep.l#L331 line 331].

Scenario 2: multiple heredoc parsing

POD parsing

Macro layer

PIRC Parser

Symbol Management

Constant Folding

Strength Reduction

Abstract Syntax Tree

Vanilla Register Allocator

Register Usage Optimizer

Bytecode Generation

Running code at compile time: the :immediate flag