Zero

Zero
Zero

11 abril 2007

Optimización de uso de registros

El último trabajo en Zero ha consistido en la optimización del ensamblador, za.

Za es el backend a través del cuál todos los programas en Zero son compilados, bien sea a través del macroensamblador o a través de cualquiera de los dos lenguajes de programación disponibles (Prowl y J--).

Hasta ahora, Za realizaba algunas optimizaciones, como por ejemplo, el mover la creación de objetos primitivos al comienzo del método:


MTH + foo
   DEF x
   INT 0
   ASG x

   ETQ loop
   INT 1
   MSG x sum __acc
   INT 10
   MSG x isLessThan __acc
   JOT loop

   RET
ENM


Este código es muy ineficiente. Los valores primitivos 1 y 10 son creados continuamente a cada vuelta de bucle, por lo tanto, 10 veces cada uno. Za optimiza este código de esta manera:


MTH + foo
   DEF __lit__0
   INT 0
   ASG __lit__0
   DEF __lit__1
   INT 1
   ASG __lit__1
   DEF __lit__2
   INT 10
   ASG __lit__2
   DEF x
   MTA .CONSTEND
  
   SET __lit__0
   ASG x
  
   ETQ loop
   SET __lit__1
   MSG x sum __acc
   SET __lit__10
   MSG x isLessThan __acc
   JOT loop

   RET
ENM


Así, la parte del método hasta "MTA .CONSTEND" sólo se ejecuta una vez, la primera. El resto de las veces, se ejecuta desde la primera instrucción después de MTA.

Sin embargo, hasta ahora za dejaba todas aquellas cuestiones relacionadas con el uso de registros dentro de métodos sin tocar. Lo anterior, por ejemplo, deja muchos movimientos de registros innecesarios, ya que una referencia local puede ser utilizada como argumento a un mensaje sin necesidad de pasarla por el acumulador (__acc), ya que no es una referencia externa.

Por otra parte, código como éste:


obj.mth( a, b, c );


Es generado de manera estándar como sigue:


SET a
ASG __gp1
SET b
ASG __gp2
SET c
ASG __gp3
MSG obj mth __gp1 __gp2 __gp3


Incluyendo casos como éste:


obj.mth( 1, "a", 3.5 );

INT 1
ASG __gp1
STR "a"
ASG __gp2
FLT 3.5
ASG __gp3
MSG obj mth __gp1 __gp2 __gp3


En este último ejemplo parece obvio que podría hacerse una optimización muy simple con:


INT 1
ASG __gp1
STR "a"
ASG __gp2
FLT 3.5
MSG obj mth __gp1 __gp2 __acc


Pero recordemos que, en realidad, los valores primitivos son movidos al comienzo del método, lo que hace la posibilidad de una optimización todavía más acuciante:


SET __lit__0
ASG __gp1
SET __lit__1
ASG __gp2
SET __lit__2
MSG obj mth __gp1 __gp2 __acc


Ya que podría ser símplemente convertido a:


MSG obj mth __lit__0 __lit__1 __lit__2


... al tratarse de referencias locales.

Esto es lo que hace, precisamente, la última optimización aplicada a Za. Retomando el ejemplo anterior:


SET __lit__0
ASG __gp1
SET __lit__1
ASG __gp2
SET __lit__2
ASG __gp3
MSG obj mth __gp1 __gp2 __gp3


Busca ciertas instrucciones que son susceptibles de ser optimizadas. La que reúne más condiciones para ser optimizada es, precisamente, MSG. Así, el optimizador busca sentencias MSG, y comienza a buscar hacia atrás ("hacia arriba") por el primer argumento.
En este caso, el primer argumento es __gp1, y al buscar hacia arriba lo encuentra en:


ASG __gp1


que significa:


ASG __gp1 __acc ; __gp1 = __acc


El optimizador toma nota de que lo que antes era __gp1, en el resto de la búsqueda ahora es __acc. La sentencia encontrada pasa a ser marcada para su borrado. Toma nota de ello, y la búsqueda continúa:


SET __lit__0


que significa


SET __acc __lit__0 ; __acc = __lit__0


Está claro que __lit__0 es una referencia local (se busca entre los identificadores que aparecen acompañando a un DEF), por lo que esta sentencia se marca para ser eliminada y se anota que lo que antes se buscaba como __acc ahora es __lit__0. Como ya es una referencia (y no un registro), la búsqueda termina. Se sustituye por tanto __gp1 por __lit__0 en el MSG, quedando por tanto:


SET __lit__1
ASG __gp2
SET __lit__2
ASG __gp3
MSG obj mth __lit__0 __gp2 __gp3


Se continúa por __gp2:


SET __lit__2
ASG __gp3
MSG obj mth __lit__0 __lit__1 __gp3


Y finalmente, con __gp3:


MSG obj mth __lit__0 __lit__1 __lit__2


Con lo que la sentencia ha sido totalmente optimizada, quedando un código tan bueno como el que hubiera escrito el propio programador, de haberlo generado él mismo.