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.
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:
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)
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.
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 xy 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)
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
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
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.
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*
Ver analizador semántico (se mantiene lista encadenada hasta que aparece la etiqueta).
Información sobre una etiqueta:
expr_b TRF n inst1 n:
expr_b TRF m inst1 TR n m: inst2 n:
inst_i inst_i m: expr_b p: expr_b TRF n TRF s inst TR r fin q: fin TRT m TR p n: r: inst TR q s:
m: expr_b TRF n inst TR m n:
m: inst expr_b TRT m