Optimización Independiente de la Máquina

En esta fase se hace un análisis del árbol, sometiéndolo a transformaciones que aumenten la eficiencia del código final producido.

Ejemplos de tareas que se pueden llevar a cabo en esta fase son:

• Extracción del interior de un bucle de cálculos que son invariantes del bucle
• Plegado de constantes: computar las expresiones constantes en tiempo de compilación, no de ejecución
• Propagación de las constantes: si se sabe que una variable en un punto del programa tiene un valor constante a = 4, se puede sustituir su uso por el de la constante
• Eliminación de computaciones redundantes, cuando la misma expresión aparece repetidas veces con los mismos valores de las variables
• La eliminación de código ``muerto'': código que se sabe que nunca podrá ser ejecutado

En nuestro primer ejemplo, reduciremos esta fase a realizar una tarea de plegado de las constantes. Primero lo haremos mediante la rutina

&Machine::Independent::Optimization::fold

En esta fase transformamos los AAA: si tenemos un árbol de la forma OPERATION(left, right), esto es, su raíz es una operación, primero plegamos los subárboles left y right, y si se han transformado en constantes numéricas, entonces plegamos el nodo que pasa a ser numérico:

 1 sub operator_fold { # Obsérvese el uso del aliasing
 2 
 3   if ($_[0]->LEFT->is_operation) {
 4     $_[0]->{LEFT}->fold; 
 5   }
 6   if ($_[0]->RIGHT->is_operation) {
 7     $_[0]->{RIGHT}->fold;
 8   }
 9   if (ref($_[0]->LEFT) eq "NUM" and ref($_[0]->RIGHT) eq "NUM") {
10     $_[0] = reduce_children($_[0]);
11   }
12 }
13 
14 sub PLUS::fold {
15  operator_fold(@_);
16 }
17 
18 sub TIMES::fold {
19  operator_fold(@_);
20 }

El plegado de las operaciones binarias se ha delegado en la subrutina operator_fold. En las líneas 3 y 6 se comprueba que se trata de un nodo de tipo operación. Si es así se procede a su plegado. Una vez plegados los dos subárboles hijo comprobamos en la línea 9 que los hijos actuales son de la clase NUM. Si es el caso, en la línea 10 cambiamos el nodo por el resultado de operar los dos hijos. Los nodos han sido extendidos con un método is_operation que determina si se trata de un nodo operación binaria o no. Para ello se han introducido nuevas clases de nodos: la clase Node está en la raíz de la jerarquía de herencia, las clases Leaf y Binary se usan para representar los nodos hoja y binarios y heredan de la anterior. Una clase informa a Perl que desea heredar de otra clase añadiendo el nombre de esa clase a la variable @ISA de su paquete. La herencia en Perl determina la forma de búsqueda de un método. Si el objeto no se puede encontrar en la clase, recursivamente y en orden primero-profundo se busca en las clases de las cuales esta hereda, esto es en las clases especificadas en el vector @ISA.

package Node;

sub is_operation {
  my $node = shift;

  return ref($node) =~ /^(TIMES)|(PLUS)$/;
}

package Leaf; # hoja del AAA
our @ISA = ("Node");
sub children {
  return ();
}

package Binary;
our @ISA = ("Node");
sub children {
  my $self = shift;

  return (LEFT => $self->{LEFT}, RIGHT => $self->{RIGHT});
}

Así pues, los objetos de la clase Leaf tienen acceso al método is_operation.

Ahora hacemos que las clases PLUS y TIMES hereden de la clase BINARY:

package PLUS;
our @ISA = ("Binary");

sub operator {
  my $self = shift;

  $_[0]+$_[1];
}

....

package TIMES;
our @ISA = ("Binary");

sub operator {
  my $self = shift;

  $_[0]*$_[1];
}

....

Obsérvese que en las líneas 4 y 7 del código del plegado de nodos de operación se ha accedido directamente al dato en vez de usar el método para modificar el atributo, saltándonos lo que la buena programación orientada a objetos indica. La forma en la que esta escrito hace que, por ejemplo, $_[0]->{LEFT} sea modificado. Recuérdese que en Perl los argumentos son alias de los parámetros.

La subrutina reduce_children es la encargada de crear el nuevo nodo con el resultado de operar los hijos izquierdo y derecho:

1 sub reduce_children {
2   my ($node) = @_;
3 
4   my $value = $node->operator($node->LEFT->VAL, $node->RIGHT->VAL);
5   NUM->new(VAL => $value, TYPE => $PL::Tutu::int_type);
6 }

En la línea 4 se usa el método operator asociado con un nodo operación.

Plegar una sentencia de impresión es plegar la expresión a imprimir:

sub PRINT::fold {
  $_[0]->{EXPRESSION}->fold;
}

Plegar una sentencia de asignación es plegar la parte derecha de la asignación:

sub ASSIGN::fold {
  $_[0]->{RIGHT}->fold;
}

de nuevo, hemos accedido a los campos en vez de usar los métodos.

Las restantes operaciones de plegado son triviales:

sub ID::fold { }

sub NUM::fold { }

sub STR::fold { }

Por último, para plegar todas las expresiones recorremos la lista de sentencias del programa y las plegamos una a una.

sub fold {
  my @statements = @{$tree->{STS}};
  for my $s (@statements) {
    $s->fold;
  }
}

Práctica: Plegado de las Constantes

Complete su proyecto de compilador de Tutu con la fase de plegado de las constantes siguiendo la metodología explicada en los párrafos previos. Mejore la jerarquía de clases con una clase abstracta Operation que represente a los nodos que se corresponden con operaciones binarias. Defina el método abstracto operation en dicha clase. Un método abstracto es uno que, mas que proveer un servicio representa un servicio o categoría. La idea es que al definir un clase base abstracta se indica un conjunto de métodos que deberían estar definidos en todas las clases que heredan de la clase base abstracta. Es como una declaración de interfaz que indica la necesidad de definir su funcionalidad en las clases descendientes, pero que no se define en la clase base. Un método abstracto debe producir una excepción con el mensaje de error adecuado si no se ha redefinido en la clase desendiente.

Para ello use la clave abstract del módulo Class::MethodMaker. Consulte la documentación del módulo Class::MethodMaker. Consulte [10] para saber más sobre clases abstractas.