Resource Allocation

The back-end of the translator starts with resource assignment. The only resource to consider here is memory. We have to assign a memory location and/or machine register to each of the variables and inner nodes in the AST. The final target machine, Parrot, is a register based interpreter with 32 floating point registers. On top of the Parrot machine is a layer named Parrot Intermediate Representation (PIR). The PIR language and its compiler (imcc) make remarkably easier the task of mapping variables to registers: PIR provides an infinite number of virtual numeric registers named $N1, $N2, etc. and solves the problem of mapping variables into registers via Graph Coloring [10].

{{ my $num = 1; # closure
  sub new_N_register {
    return '$N'.$num++;
  }
}}

reg_assign: $x  => {
  if (ref($x) =~ /VAR|NUM/) {
    $x->{reg} = $x->{attr};
    return 1;
  }
  if (ref($x) =~ /ASSIGN/) {
    $x->{reg} = $x->child(0)->{attr};
    return 1;
  }
  $_[0]->{reg} = new_N_register();
}
As it shows the code above (in file I2PIR.trg), the resource allocation stage is limited to assign virtual registers to the inner nodes.

A treeregexp term like $x matches any node and creates a lexical variable $x containing a reference to the node that matched.

In between Treeregexp rules the programmer can insert Perl code between curly brackets. The code will be inserted verbatim7 at that relative point by the treereg compiler.

The Parse::Eyapp::YATW object $reg_assign generated by the compiler is available inside the main driver (revise section 2):

our $reg_assign;
$reg_assign->s($t);
Now we have an AST decorated with a new attribute reg. The following session with the debugger illustrates the way to expose the AST and its attributes:
$ perl -wd infix2pir.pl simple5.inf
main::(59): my $filename = shift;
DB<1> c 72    
-a*2        
EXPS(TIMES(NEG(VAR),NUM))    # The AST
We have stopped the execution just before the call to $reg_assign->s($t). The AST for input -a*2 was displayed.
main::(72): $reg_assign->s($t);
DB<2> n
main::(75): $t->bud(our @translation);
After the register assignment phase the nodes have been decorated with the attribute $reg. To display a tree we use the str method of Parse::Eyapp::Node. The str method traverses the syntax tree dumping the type of the node being visited in a string. If the node being visited has a method info it will be executed and its result inserted between $DELIMITERs into the string. The package variable $INDENT8controls the way the tree is displayed. Thus, the next three commands display the AST and the values of the reg attributes:
DB<2> *TIMES::info = *NEG::info = \
*VAR::info=*NUM::info=sub {$_[0]{reg}}
DB<3> $Parse::Eyapp::Node::INDENT=2
DB<4> x $t->str       # Decorated tree
0  '
EXPS(
  TIMES[$N2](
    NEG[$N1](
      VAR[a]
    ),
    NUM[2]
  ) # TIMES
) # EXPS'
Observe that no registers were allocated for variables and numbers.

Procesadores de Lenguaje 2007-03-01