Capítulo 6. Generación de código

El código generado por un compilador puede ser de uno de los tipos siguientes:

Usaremos como ejemplo la traducción a código simbólico (más legible).

Existen dos formas de realizar la generación de código:

               A.Semántico             G.Código
        Fuente -----------> Cuádruplas --------> Objeto
          |----------------------------------------|
                         A. Semántico

La primera posibilidad es más rápida, pero más compleja.

Operandos

En el código objeto, los operandos se representan usualmente por su dirección. Esta se almacena a menudo en forma de una base y un desplazamiento, habiendo un número limitado de zonas de datos, cada una con su base. Pueden utilizarse registros índices. (Habrá variables que describan el contenido de éstos, igual que con el acumulador o los registros de trabajo).

Los operandos temporales pueden no recibir memoria asociada, si su rango de actuación no pasa de un registro acumulador. En caso contrario, dicho rango puede almacenarse en la descripción de la variable para declarar libre el espacio en cuanto la variable no sea necesaria. En máquinas modernas se utiliza la pila de la máquina para los operandos temporales.

Información sobre un operando:

Indexado

Vamos a calcular la dirección de un elemento de un "array".

        ARRAY x[10;5]
        ... x[4;3] ...

En origen 1, la dirección equivalente es la de x[1;1] (base) más un desplazamiento igual a 3*5+2, si x está almacenado por filas. Si se almacena por columnas (FORTRAN), el desplazamiento es 2*10+3.

En general:

        ARRAY x[a;b; ... ;c;d]
        ... x[i;...;j;k;l] ...

El desplazamiento en origen 1, con almacenamiento por filas, es:

        (l-1)+(k-1)*d+(j-1)*c*d+...+(i-1)*b*...*c*d

El desplazamiento en origen 0, con almacenamiento por filas, es:

        l+k*d+j*c*d+...+i*b*...*c*d

Con almacenamiento por columnas, el orden se invierte.

Más en general, si tenemos

        ARRAY x[a : b ; c : d]
        ... x[i;j] ...
el desplazamiento es:
        (i-a)*(d-c+1)+(j-c)
        ARRAY x[a : b ; c : d ; e : f]
        ... x[i;j;k] ...
el desplazamiento es:
        (i-a)*(d-c+1)*(f-e+1)+(j-c)*(f-e+1)+(k-e)

Conversiones de tipo

Sea la expresión

      real A;
      int I,J;
      ...
      J = A*I+J

Si se pasa por cuádruplas, el análisis semántico podría generar las siguientes:

      (*,A,I,T1)
      (+,T1,J,T2)
      (=,T2,,J)

En este caso, las rutinas de generación de código tendrán que ocuparse de la compatibilidad y conversión de tipos. También podría complicarse el análisis semántico para que se generasen cuádruplas de conversión:

      (CVIR,I,,T1)
      (*R,A,T1,T2)
      (CVIR,J,,T3)
      (+R,T2,T3,T4)
      (CVRI,T4,,T5)
      (=I,T5,,J)

En este caso hay más rutinas de generación de código, pero son más sencillas.

Manejo de registros

Si el ordenador tiene un acumulador, tendremos una rutina para cargar un objeto escalar en el acumulador. Habrá una variable (ej. AC) que indique lo que hay en el acumulador en un momento dado. La rutina de carga del acumulador podría ser:

    int CAC (opd *x, opd *y)
    {
      if (AC!=NULL && AC==y) return 1;
      if (AC!=x) {
        if (AC!=NULL) GEN ("MOV ",AC,",AC");
        GEN ("MOV AC,",x);
        AC=x;
        }
    return 0;
    }

Esta rutina puede llamarse así:

    CAC (x,y)           // Podemos cargar x o y
    CAC (x,NULL)        // Tenemos que cargar x
y devuelve 0 si x está en el acumulador, 1 si es y.

Si en vez de un acumulador hay un conjunto de registros (ej. AX, BX, CX, DX, SI, DI) tendremos un vector de variables REG (equivalente a AC) y la rutina de carga devolverá el registro seleccionado.

Será preciso distinguir los registros en punto fijo de los de punto flotante. También, algunos registros pueden estar reservados para uso interno del compilador (ej., para bucles, índices, etc). El contenido puede ser una variable o un conjunto de variables (véase la sección sobre operandos).

Una rutina general de carga de registros deberá comenzar por seleccionar el registro a utilizar entre los disponibles. Para ello hay que tener en cuenta el tipo del registro sobre el que se desea cargar (registros enteros o en punto flotante). Si no hay ninguno del tipo deseado, se elegirá uno de los ocupados, perdiendo la información que contiene (si ya no es necesaria) o guardándola en la posición de memoria asociada. Una vez seleccionado el (los) registro(s), la carga propiamente dicha dependerá del tipo del objeto a cargar. Es conveniente hacer una tabla en función de dicho tipo, como la siguiente:

  Carga de X:
Tipo                          Tipo de X
reg    char        short      int-r   const      real    real-r
---- -----------------------------------------------------------
int  XOR RH,RH     MOV RX,X     -     MOV RX,X   FLD X   FISTP T
     MOV RL,X                                    (Carga) (Carga)
real XOR RH,RH     FILD X     MOV T,X MOV T,X    FLD X      -
     MOV RL,X                 (Carga) (Carga)
     (Carga)

Expresiones

La construcción de tablas de código generado es muy útil también para las operaciones que aparecen en las expresiones, especialmente para las diádicas, donde la tabla será de doble entrada (tipo del argumento izquierdo, tipo del derecho). A menudo, el cambio de tipo se puede realizar de forma más o menos directa a través de la operación de carga en registro definida anteriormente.

Veamos como ejemplo la tabla correspondiente a la operación suma:

  X+Y:
Tipo                      Tipo de Y
de X    char      short    int-r    const    real     real-r
------  -----------------------------------------------------
char    CARGA X   X<->Y    X<->Y    CARGA X  CARGA X  CARGA X
short   CARGA Y   CARGA Y  ADD Y,X  CARGA Y  CARGA X  FIADD X
int-r   CARGA Y   ADD X,Y  ADD X,Y  ADD X,Y  MOV T,X  MOV T,X
                                             (Suma)   (Suma)
const   X<->Y     X<->Y    X<->Y       -     CARGA X  FADD X
real    CARGA Y   CARGA Y  X<->Y    X<->Y    CARGA Y  FADD X
real-r  X<->Y     X<->Y    X<->Y    X<->Y    X<->Y    FADD Y

En la tabla anterior hemos aprovechado el hecho de que la operación es conmutativa y algunas casillas pueden reducirse a otras sin más que cambiar el orden de los operandos. La utilización de la operación CARGA reduce aún más la parte de la tabla verdaderamente dedicada a la generación del código. Siempre que realizamos una de estas operaciones, se entiende que hay que volver a aplicar la tabla, indexándola por los tipos de los nuevos operandos.

Programación de la tabla de la suma en seudocódigo:

    Label Tabla[n][n] = {LCX, LXG, LXG, LCX, LCX, LCX}
                        {LCY, LCY, L1,  LCY, LCX, L2}
                        {LCY, L3,  L3,  L3,  L4,  L4}
                        {LXG, LXG, LXG, 0,   LCX, L5}
                        {LCY, LCY, LXG, LXG, LCY, L5}
                        {LXG, LXG, LXG, LXG, LXG, L6}
  L: GOTO Tabla[tipox][tipoy];
  LCX: CARGA X;
       GOTO L;
  LCY: CARGA Y;
       GOTO L;
  LXG: X<->Y;
       GOTO L;
  L1:  GEN (ADD Y,X);
       return;
  L2:  GEN (FIADD Y);
       return;
  L3:  GEN (ADD X,Y);
       return;
  L4:  GEN (MOV T,X);
       GOTO L;
  L5:  GEN (FADD X);
       return;
  L6:  GEN (FADD Y);
       return;

En una operación no conmutativa (como la resta) el número de casillas generadoras de código aumenta. En las operaciones monádicas la tabla se reduce normalmente a una tabla de entrada simple. Por ejemplo, para el cambio de signo:

  -Y:
                          Tipo de Y
        char      short    int-r    const    real     real-r
        -----------------------------------------------------
char    CARGA Y   CARGA Y  NEG Y      -      CARGA Y  FCHS

Generación a partir de cuádruplas

Para funciones diádicas conmutativas (suma, producto):

    SUMA (opd *x, opd *y, opd *z)
    {
      if (CAC (x, y)) GEN ("ADD AC,",x);
      else GEN ("ADD AC,",y);
      AC=z;
    }

(+, O1, O2, R) se traduce por SUMA (O1, O2, R).

La multiplicación se haría igual, sustituyendo "ADD" por "MUL".

Para funciones diádicas no conmutativas:

    RESTA (opd *x, opd *y, opd *z)
    {
      CAC (x, NULL);
      GEN ("SUB AC,",y);
      AC=z;
    }

(-, O1, O2, R) se traduce por RESTA (O1, O2, R).

La división se haría igual, sustituyendo "SUB" por "DIV".

Para funciones monádicas:

    NEG (opd *x, opd *z)
    {
      CAC (x, NULL);
      GEN ("NEG AC");
      AC=z;
    }

(@, O1,, R) se traduce por NEG (O1, R).

Ejemplo: sea la expresión A*((A*B+C)-C*D)

Las cuádruplas son:

  Cuádrupla     Se genera       Valor de AC
  ------------  ----------      -----------
  (*,A,B,T1)    MOV AC,A             A
                MUL AC,B             T1
  (+,T1,C,T2)   ADD AC,C             T2
  (*,C,D,T3)    MOV T2,AC
                MOV AC,C             C
                MUL AC,D             T3
  (-,T2,T3,T4)  MOV T3,AC
                MOV AC,T2            T2
                SUB AC,T3            T4
  (*,A,T4,T5)   MUL AC,A             T5

A partir de notación polaca

Es el mismo algorimo que se explicó en el capítulo anterior para la evaluación de expresiones en notación polaca, sustituyendo las evaluaciones (intérprete) por generación de código (compilador).

Si el acumulador está en segundo lugar en la pila, al introducir un operando nuevo en la pila hay que generar una instrucción que pase el acumulador a una variable intermedia y sustituir el acumulador por el nombre de ésta. Con ello, un operador diádico no tendría que preocuparse por el acumulador. Uno monádico tendría que comprobar sólo si es el segundo operando de la pila.

Generación de código para la asignación

Sea la cuádrupla

      (=,B,,A)

En general, habrá que generar

      MOV AC,B
      MOV A,AC

En algunas máquinas existe una instrucción que permite pasar de memoria a memoria, tal como

      MOV A,B

También puede ser que, al generar esta instruccción, nos encontremos con que el acumulador contiene B (AC="B"), en cuyo caso bastaría con generar

      MOV A,AC

La asignación puede llevar implícitas diversas conversiones de tipo, que pueden haber sido tratadas previamente por el analizador semántico.

También puede haber conversión implícita de la profundidad de los punteros, como en

      ref int A;
      int B;
      ...
      B := A;

En este caso, el código generado debería ser:

      MOV índice,A
      MOV AC,[índice]
      MOV B,AC

Veamos un ejemplo de tabla de conversión de tipos para la asignación:

  X=Y:
Tipo                      Tipo de Y
de X    char      short    int-r    const    real     real-r
------  -----------------------------------------------------
char    CARGA Y   CARGA Y  MOV X,YL MOV X,Y  CARGA Y  FISTP T
                                                      MOV R,T
                                                      MOV X,RL
short   CARGA Y   CARGA Y  MOV X,Y  MOV X,Y  CARGA Y  FISTP X
int-r   CARGA Y*  CARGA Y* MOV X,Y* MOV X,Y  CARGA Y  FISTP T
                                                      MOV X,T
const     -         -        -        -        -        -
real    CARGA Y   CARGA Y  MOV T,Y  CARGA Y  CARGA Y  FSTP X
                           CARGA T
real-r  CARGA Y*  CARGA Y* MOV T,Y  CARGA Y* CARGA Y*   -
                           CARGA T*

Generación de código para GOTO

Ver analizador semántico (se mantiene lista encadenada hasta que aparece la etiqueta).

Información sobre una etiqueta:

Generación de código para instrucciones condicionales

Generación de código para bucles