fix codetest failure - ASSERT_ARGS does not have a ; after and

[parrot.git] / compilers / pirc / README.pod

# Copyright (C) 2001-2009, Parrot Foundation.
# $Id$

=head1 NAME

README.txt - Readme file for PIRC compiler.

=head1 DESCRIPTION

PIRC is a fresh implementation of the PIR language using Bison and Flex.
Its main features are:

=over 4

=item * thread-safety, so it is reentrant.

=item * strength reduction, implemented in the parser.

=item * constant folding, implemented in the parser.

=item * checks for proper use of op arguments in PIR syntax (disallowing, e.g.: $S0 = print)

=item * allow multiple heredocs in subroutine invocations (like: foo(<<'A', <<'B', <<'C') )

=item * register usage optimization

=back

=head2 Compiling and Running

=head3 Windows using Microsoft Visual Studio

To compile PIRC on windows using MSVC:

   nmake

When running PIRC, it needs the shared library C<libparrot>; an easy way to do
this is copy C<libparrot.dll> in the Parrot root directory to C<compilers/pirc/src>.

Running PIRC is as easy as:

 pirc test.pir

See 'pirc -h' for help.

=head3 Linux using GCC

The Makefile should work fine on Linux:

 cd compilers/pirc && make

When running PIRC, it needs the shared library C<libparrot>; in order to let
PIRC find it, set the path as follows:

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

Running is as easy as:

 ./pirc test.pir

=head2 Overview

The new Bison/Flex based implementation of the PIR compiler is designed
as a two-stage compiler:

=over 4

=item 1. Heredoc preprocessor

=item 2. PIR compiler

=back

=head2 Heredoc preprocessing

The heredoc preprocessor takes the input as written by the PIR programmer,
and flattens out all heredoc strings. An example is shown below to illustrate
this concept:

The following input:

 .sub main
   $S0 = <<'EOS'
 This is a heredoc string
   divided
     over
       five
         lines.
 EOS
 .end

is transformed into:

 .sub
   $S0 = "This is a heredoc string\n  divided\n    over\n      five\n        lines.\n"
 .end

In order to allow C<.include>d file to have heredoc strings, the heredoc preprocessor
also handles the C<.include> directive, even though logically this is a macro function.
See the discussion below for how the C<.include> directive works.

=head2 PIR compilers

The PIR compiler parses the output of the heredoc preprocessor. PIRC's lexer also
handles macros.

The macro layer basically implements text replacements. The following directives are handled:

=over 4

=item C<.macro>

=item C<.macro_const>

=item C<.macro_local>

=item C<.macro_label>

=back

=head3 C<.include>

The C<.include> directive takes a string argument, which is the name of a file. The
contents of this file are inserted at the point where the C<.include> directive
is written. To illustrate this, consider the following example:

 main.pir:
 ========================
 .sub main
   print "hi\n"
   foo()
 .end

 .include "lib.pir"
 ========================

 lib.pir:
 ========================
 .sub foo
   print "foo\n"
 .end
 ========================

This will result in the following output:

 .sub main
   print "hi\n"
   foo()
 .end

 .sub foo
   print "foo\n"
 .end


=head3 C<.macro>

The macro directive starts a macro definition. The macro preprocessor
implements the expansion of macros. For instance, given the following input:

 .macro say(msg)
   print .msg
   print "\n"
 .endm

 .sub main
   .say("hi there!")
 .end

will result in this output:

 .sub main
   print "hi there!"
   print "\n"
 .end

=head3 C<.macro_const>

The C<.macro_const> directive is similar to the C<.macro> directive, except
that a C<.macro_const> is just a simplified C<.macro>; it merely gives a name
to some constant:

 .macro_const PI 3.14

 .sub main
   print "PI is approximately: "
   print .PI
   print "\n"
 .end

This will result in the output:

 .sub main
   print "PI is approximately: "
   print 3.14
   print "\n"
 .end


=head3 PIR compiler

As Parrot instructions are polymorphic, the PIR compiler is responsible for
selecting the right variant of the instruction. The selection is based on the
types of the operands. For instance:

 set $I0, 42

will select the C<set_i_ic> instruction: this is the C<set> instruction, taking
an integer (i) result operand and an integer constant (ic) operand. Other examples
are:

 $P0[1] = 42           --> set_p_kic_ic # kic = key integer constant
 $I0 = $P0["hi"]       --> set_i_p_kc   # kc = key constant from constant table
 $P1 = new "Hash"      --> new_p_sc     # sc = string constant

=head3 Constant folding

Expressions that can be evaluated at compile-time are pre-evaluated, saving
calculations during runtime. Some constant-folding is required, as Parrot
depends on this. For instance:

 add $I0, 1, 2

is not a valid Parrot instruction; there is no C<add_i_ic_ic> instruction.
Instead, this will be translated to:

 set $I0, 3

which, as was explained earlier, will select the C<set_i_ic> instruction.

The conditional branch instructions are also pre-evaluated, if possible. For
instance, consider the following statement:

 if 1 < 2 goto L1

It is clear during compile time, that 1 is smaller than 2; so instead of
evaluating this during runtime, we know for sure that the branch to label
C<L1> will be made, effectively replacing the above statement by:

 goto L1

Likewise, if it's clear that certain instructions don't have any effect,
they can be removed altogether:

 if 1 > 2 goto L1        --> nop  # nop is no opcode.
 $I0 = $I0 + 0           --> nop

Another type of optimization is the selection of (slightly) more efficient
variants of instructions. For instance, consider the following instruction:

 $I0 = $I0 + $I1

which is actually syntactic sugar for:

 add $I0, $I0, $I1

In C one would write (ignoring the fact that $I0 and $I0 are not a valid C
identifiers):

 $I0 += $I1

which is in fact valid PIR as well. When the PIR parser sees an instruction
of this form, it will automatically select the variant with 2 operands
instead of the 3-operand variant. So:

 add $I0, $I0, $1    # $I0 is an out operand

will be optimized, as if you had written:

 add $I0, $I1        # $I0 is an in/out operand

The PIR parser can do even more improvements, if it sees opportunity to do so.
Consider the following statement:

 $I0 = $I0 + 1

or, in Parrot assembly syntax:

 add $I0, $I0, 1

Again, in C one would write (again ignoring the valid identifier issue): C<$I0++>,
or in other words, C<incrementing> the given identifier. Parrot has C<inc> and C<dec>
instructions built-in as well, so that the above statement C<$I0 = $I0 + 1> can be
optimized to:

 inc $I0

=head3 Vanilla Register Allocator

The PIR compiler implements a vanilla register allocator. This means that each
declared C<.local> or C<.param> symbol, and each PIR register ($Px, $Sx, $Ix, $Nx)
is assigned a unique PASM register, that is associated with the original symbol
or PIR register throughout the subroutine.

PIRC has a register optimizer, which can optimize the register usage. Run PIRC
with the C<-r> option to activate this. The register optimizer is implemented
using a Linear Scan Register allocator.

The implementation of the vanilla register allocator is done in the PIR symbol
management module (C<pirsymbol.c>).

=head2 Register optimizer

PIRC has a register optimizer, which uses a Linear Scan Register algorithm.
For each symbolic register, a live-interval object is created, which has
an I<start> and I<end> point, indicating the first and last usage of that
symbolic register in the sub. The register optimizer figures out when
symbolic registers don't overlap, in which case they can use the same
register (assuming they're of the same type).

=head2 Status

Bytecode generation is done, but there is the occasional bug. These
are reported in trac.parrot.org.


=head1 IMPLEMENTATION

The directory compilers/pirc has a number of subdirectories:

=over 4

=item doc - contains documentation.

=item heredoc - contains the implementation of the heredoc preprocessor. This is now
integrated with pirc/src. It now only has a driver program to build a stand-alone
heredoc preprocessor.

=item src - contains the Bison/Flex implementation of PIRC

=item t - for tests. Tests input is fed into Parrot after compilation,
which will run the code.

=item macro - contains the old implementation of the macro preprocessor. This is now
integrated with pirc/src. These files are kept as a reference until the macro
preprocessor in pirc/src is completed.

=back

=head1 MAKING CHANGES

If you want to make changes to the lexer of parser files, you will need the Flex
and/or Bison programs. There are ports available for Windows, but I don't know
whether they're any good. I use Cygwin's tools.

=head2 Updating the lexer

The heredoc preprocessor is implemented in C<hdocprep.l>, and can be regenerated
using:

   cd compilers/pirc/src
   flex hdocprep.l

PIRC's normal lexer is implemented in C<pir.l>, and can be regenerated using:

   cd compilers/pirc/src
   flex pir.l

=head2 Updating the parser

The parser is implemented in C<pir.y>, and can be regenerated using:

   cd compilers/pirc/src
   bison pir.y

=head1 NOTES


=head2 Cygwin processable lexer spec.

The file C<pir.l> from which the lexer is generated is I<not> processable by Cygwin's
default version of Flex. In order to make a reentrant lexer, a newer version is needed,
which can be downloaded from the link below.

L<http://sourceforge.net/project/downloading.php?groupname=flex&filename=flex-2.5.33.tar.gz&use_mirror=belnet>

Just do:

 $ ./configure
 $ make

Then make sure to overwrite the supplied flex binary.

=head1 BUGS

Having a look at this implementation would be greatly appreciated, and any resulting
feedback even more :-). Please post bug reports in trac.parrot.org.


=head1 SEE ALSO

See also:

=over 4

=item * C<languages/PIR> for a PGE based implementation.

=item * C<compilers/imcc>, the current I<standard> PIR implementation.

=item * C<docs/imcc/syntax.pod> for a description of PIR syntax.

=item * C<docs/imcc/> for more documentation about the PIR language.

=item * C<docs/pdds/pdd19_pir.pod> for the PIR design document.

=back

=cut