NAME

IMCC - operation

VERSION

0.1 intital

OVERVIEW

This document describes the principles of imcc operation.

DESCRIPTION

The main features of imcc are:

Source file parsing

Register allocation

Optimization

Code generation

Running the code

Source file parsing

S. parsing.pod and syntax.pod for more.

Register allocation

Register allocation is done per compilation unit.

Imcc identifiers and temporary variables e.g. $I0 are assigned a phsyical parrot register depending on the life range of these variables. If the life range of one variable doesn't overlap the range of another variable, these might get the same parrot register.

   $I0 = 10
   $I1 = 20

will translate to

   set I0, 10
   set I0, 20

when $I0 is not used after these lines.

The first redundant assignment will be optimized away with -O2.

PASM registers keep their register. During the usage of a PASM register this register will be not get assigned to. So don't use these over long code pieces and only when really needed.

Basic blocks

To determine the life range of variables, the code gets separated into pieces, called basic blocks. A basic block starts at a label, which can get jumped to, and ends at a branch instruction.

Call graph

All connection between the basic blocks are calculated. This allows for:

Loop detection

where the range and depth of loops is calculated.

Life analysis

Whenever an operand is marked as an OUT argument, this operand starts with a new value. This means, that at this point the life range of the symbol ends and a new life range is started, which allows the allocation of a different register to the same variable or the same register to a different variable.

Variables used as IN parameters must keep their parrot register over their usage range.

Interference graph

With above information calculated, the next step is to look, which variable does interfer with which other. Non interfering variables can be given the same parrot register.

Spilling

When there are too many interferences, so that not all variables can be allocated to a parrot register, the least used variables are spilled, or stored in a PerlArray when they are not used.

  set $I1,1
  set $I2,2
  ...
  set $I33, 33
  ...
  print $I1

and usage of all these variables after this point makes it necessary, to spill.

  new P31, .PerlArray
  ...
  set I0, 1
  set P31[0], I0        # store $I1
  set I0, 2
  set P31[1], I0        # store $I2
  ...
  set I0, P31[0]        # fetch $I1
  print I0

When $I1 or $I2 are accessed then, code is generated to fetch the value from the spill array.

Optimization

Currently not much is done.

If branch optimization

A sequence of code:

    if cond, L1
    branch L2
 L1:
 ...
 L2:

will be converted to

    unless cond, L2
    ...
 L2:

The same is done for other conditional branches gt, ge, eq and their reverse meanings.

Unused labels

Labels not referenced somewhere get deleted.

Used LHS once

For a sequence of code

   $I0 = 10
   $I1 = 20

where $I0 is not used beyond, the first assignment will be tossed, resulting in code like:

   set I0, 20

Code generation

Imcc either generates PASM output ready to get assembled by assemble.pl or directly a PBC file, for running with parrot.

Running code

Additionally the generated code can be run immediately inside imcc. All parrot runtime options like -j or -t are available.

FILES

imc.c, cfg.c, optimizer.c, pbc.c

AUTHOR

Leopold Toetsch <lt@toetsch.at>

cpanm Make

perl -MCPAN -e shell
install Make