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 [8].

As it shows in the code below (in file I2PIR.trg), the resource allocation stage is limited to assign virtual registers to the inner nodes:

    {{ 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();
    }

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 verbatim⁶ 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 3):

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:

    ~/LEyapp/examples/ParsingStringsAndTrees$ perl -wd infix2pir.pl simple5.inf

    Loading DB routines from perl5db.pl version 1.31
    Editor support available.

    Enter h or `h h' for help, or `man perldebug' for more help.

    main::(infix2pir.pl:41):    my $filename = shift;
      DB<1> l 41,55
    41==>   my $filename = shift;
    42: my $parser = Infix->new(); 
    43: $parser->slurp_file($filename);
    44  
    45: my $t = $parser->YYParse() || exit(1);
    46  
    47  # Machine independent optimizations
    48: $t->s(our @algebra);  
    49  
    50  # Address Assignment 
    51: our $reg_assign;
    52: $reg_assign->s($t);
    53  
    54  # Translate to PARROT
    55: $t->bud(our @translation);
      DB<2> c 52
    main::(infix2pir.pl:52):    $reg_assign->s($t);
      DB<3> x $t->str
    0  'EXPS(TIMES(NEG(VAR[a]),NUM[2]))'

We have stopped the execution just before the call to $reg_assign->s($t). The AST for input -a*2 was displayed. Now let us execute $reg_assign->s($t):

  DB<4> n
main::(infix2pir.pl:55):    $t->bud(our @translation);

And have a look at how registers have been allocated:

  DB<4> *TIMES::info=*NEG::info=*VAR::info=*NUM::info=sub {$_[0]{reg}}

  DB<5> $Parse::Eyapp::Node::INDENT=2

  DB<6> x $t->str
0  '
EXPS(
  TIMES[$N2](
    NEG[$N1](
      VAR[a]
    ),
    NUM[2]
  ) # TIMES
) # EXPS'
  DB<7>

Observe that no registers were allocated for variables and numbers.

After the register assignment phase the nodes have been decorated with the attribute $reg.

To display the tree we use the str method of the AST nodes. This method is inherited from 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 Parse::Eyapp::Node variable $INDENT⁷controls the way the tree is displayed.