1. Especificación de la máquina UDMC02

1.1. Introducción

La máquina UDMC02 es una simplificación de una máquina CISC (Complex Instruction Set Computer, si es que esta denominación tiene algún sentido hoy en día), orientada a la escritura del código necesario para mostrar la estructura del programa objeto que genera un compilador de un lenguaje de programación de alto nivel.

En este documento se muestran la arquitectura, los mecanismos de direccionamiento, los tipos de datos y el repertorio de instrucciones (en forma de ensamblador).

1.2. Arquitectura

La máquina UDMC02 es una típica arquitectura de 32 bits: bus de datos y direcciones de ese tamaño, registros de propósito general de ese tamaño, etc. No nos preocupan, sin embargo, cuestiones como la existencia de caché, interrupciones, y otros similares. Sin embargo, sí suponemos que dispone de una unidad de proceso de coma flotante, pero, al contrario que las arquitecturas habituales (que suelen diferenciar el trabajo con esta unidad, también llamada coprocesador matemático), supondremos que su manejo es transparente (o sea, integrado en el procesador básico) en cuanto a composición, instrucciones y demás.

Los registros de la máquina son los siguientes:

• AD, BD, CD, DD son cuatro registros de 32 bits de propósito general, aunque orientados al almacenamiento de datos. En lo que sigue, estos cuatro registros se denominarán genéricamente con RegD.
• SP, BP, GP, EP son cuatro registros de 32 bits de propósito general, aunque orientados al almacenamiento de direcciones. En lo que sigue, estos cuatro registros se denominarán genéricamente con RegP, y el conjunto de RegD y RegP se denominará con RegDP.
• R0, …, R7 son ocho registros de 64 bits de datos reales (coma flotante). En lo que sigue, se denominarán genéricamente por RegR.
• IP (32 bits) es el contador de programa.

Deberíamos hablar del registro de estado, pero no es importante para nuestro propósito, simplemente supondremos que existe.

1.3. Tipos de datos

Hay cinco tipos de datos: byte (u octeto), halfword (o entero corto, 2 bytes), word (o entero, 4 bytes), dirección (4 bytes) y real (en coma flotante, 8 bytes). La especificación de tipo en instrucciones y datos inmediatos se realiza mediante las letras b, h, w, d y r, respectivamente. El tipo dirección no es estrictamente necesario en una máquina real, pero resulta cómodo para entender el código generado. En nuestro caso, para simplificar, entenderemos las cantidades enteras y reales con signo, mientras que las direcciones son sin signo.

1.4. La memoria y su direccionamiento

La memoria se supone organizada de forma lineal en bytes, desde la dirección 0x0000000000000000 hasta la dirección máxima posible 0xFFFFFFFFFFFFFFFF. No existe segmentación (como en la arquitectura Intel), ni alineamiento (es decir, se puede direccionar cada byte de la memoria, no es preciso que sean múltiplos de 2 o de 4).

La estructura de los bytes en los tipos de datos que contienen varios es little-endian, esto es, el byte menos significativo (LSB) ocupa direcciones de memoria más bajas. Por lo tanto, cuando mediante la dirección d se señala un dato (digamos entero, por ejemplo) de la memoria, se están señalando los bytes d, d+1, d+2 y d+3, del menos al más significativo, respectivamente (en el modelo big-endian, el byte de la dirección d es el más significativo).

		0xFF…FF
	MSB
	…	Memoria ↑
	…
d →	LSB
		0x00…00

El direccionamiento de posiciones de memoria mediante registro (lo que se suele llamar direccionamiento indirecto) admite un desplazamiento (u offset), pero puede venir en dos modalidades:

• direccionamiento indirecto sin desplazamiento, es el contenido de la dirección de memoria que contiene el registro R:

  [ R ]

  o con desplazamiento:

  [ R + despl ]      [ R - despl ]

  es el contenido de la dirección de memoria que se obtiene sumando o restando despl al contenido del registro R;

• direccionamiento indirecto doble sin desplazamiento, es el contenido de la dirección de memoria almacenada en la dirección de memoria que contiene el registro R:

  [[ R ]]

  o con desplazamiento:

  [[ R + despl ]]      [[ R - despl ]]

  es el contenido de la dirección de memoria almacenada en la dirección que se obtiene sumando o restando despl al contenido del registro R.

Obsérvese que los corchetes actúan como un operador de "contenido", pero son necesarios en las instrucciones incluso en los contextos en que se esperaría la especificación de una dirección (ver más adelante en las instrucciones).

1.5. La pila

La máquina UDMC02 proporciona la posibilidad de manejar cierta parte consecutiva de la memoria en forma de pila (o stack). Esta pila crece hacia las direcciones altas de memoria (en cambio, la arquitectura Intel lo hace al revés). En cada momento, el valor del registro de direcciones SP señala la primera dirección libre de la pila.

		0xFF…FF
SP →
	MSB
Pila ↑	…	Memoria ↑
	…
	LSB
		0x00…00

De esta manera, si la cumbre de la pila contiene primero un dato de 4 bytes, y debajo otro de 2, se accede a los mismos a través de los direccionamientos indirectos [SP-4] y [SP-6], respectivamente.

Se supone que al comienzo del programa que ejecuta la máquina UDMC02, si va a hacer uso de esta característica, se establecerá el valor inicial del registro SP con la instrucción correspondiente. En tal caso, el resto del programa no deberá usar este registro con otro propósito que el señalado, y ha de tenerse en cuenta que existen instrucciones que implícitamente hacen uso de la pila como tal (modificando por tanto el valor del registro SP).

1.6. Repertorio de instrucciones

Las instrucciones de la máquina UDMC02 se dan en forma de pseudocódigo (lo que también podría llamarse ensamblador, pero atípico en su sintaxis en ciertos momentos).

1.6.1. Formato, etiquetas y operandos

Las instrucciones pueden llevar o no una etiqueta. En caso afirmativo, la etiqueta es una cadena alfanumérica que comienza por el carácter # y una letra, y se coloca precediendo a la instrucción propiamente dicha, separada de ella por el carácter dos puntos (:). Por ejemplo:

#loop3:  SP :=d BP

En general, las instrucciones tienen cero, uno o dos orígenes de datos, y pueden tener (o no, explícitamente queremos decir) un destino para el resultado. En el ejemplo anterior, BP es el origen y SP el destino. Diremos que BP aparece en un contexto de lado derecho (o de valor) y que SP aparece en un contexto de lado izquierdo (o de dirección). Por otro lado, casi todas las instrucciones incorporan una especificación de tipo de dato (que puede ser alguna de las letras b, h, w, d o r) para indicar el tamaño del origen y/o destino. En el ejemplo, es la d que aparece después de :=.

Los argumentos de las instrucciones (dependiendo de cada caso) pueden ser los siguientes:

• Dato inmediato o literal:

  inmediato

  Representa el propio valor, en contextos de lado derecho, en principio. En el caso de enteros (tipos b, h, w y d) es una secuencia de dígitos decimales. En el caso de reales, se escriben como en el lenguaje C (en decimal, con punto para separar la parte entera de la fraccionaria, y parte exponencial opcional). Ambos pueden comenzar con un signo - opcional. En el caso de etiquetas, es el identificador de la misma. Ejemplos:

  123
  -12.34
  12.34e-5
  #loop3
  

• Dato en registro:

  R

  En contextos de lado derecho, representa el contenido del registro; en contextos de lado izquierdo, significa tomar el registro como destino. No puede ser IP. Normalmente, las instrucciones de manejo de reales solo pueden usar los registros reales (RegR) y las demás los otros (RegDP), pero hay algunas que pueden manejar ambos; se indicará en cada caso.

• Dato en registro con desplazamiento:

  R + despl      R - despl

  Siempre representa una dirección, en contextos de lado derecho exclusivamente: es la dirección resultado de sumar o restar despl a la dirección contenida en R. Se aplica solamente a registros RegP de direcciones; despl es un dato inmediato entero de cualquier tamaño (b, h o w). Ejemplos:

  SP - 4
  BP + 27
  

• Dato en memoria indirecto sin/con desplazamiento:

  [ R ]      [ R + despl ]      [ R - despl ]

  En contextos de lado derecho, es el contenido de la dirección de memoria almacenada en R (o de la dirección almacenada en R más/menos despl); en contextos de lado izquierdo, significa que esa dirección es el destino. La primera modalidad (sin desplazamiento) puede aplicarse a RegDP, pero la segunda (con desplazamiento) se aplica solamente a RegP (en ningún caso se aplica a registros reales); despl es un dato inmediato entero de cualquier tamaño (b, h o w). Ejemplos:

  [DD]
  [BP + 27]
  

• Dato en memoria indirecto doble sin/con desplazamiento:

  [[ R ]]      [[ R + despl ]]      [[ R - despl ]]

  En contextos de lado derecho, es el contenido de la dirección de memoria almacenada en la dirección de memoria almacenada en R (o en la dirección almacenada en R más/menos despl); en contextos de lado izquierdo, significa que esa dirección es el destino. La primera modalidad (sin desplazamiento) puede aplicarse a RegDP, pero la segunda (con desplazamiento) se aplica solamente a RegP (en ningún caso se aplica a registros reales); despl es un dato inmediato entero de cualquier tamaño (b, h o w). Ejemplos:

  [[DD]]
  [[BP + 27]]
  

Los dos últimos argumentos (de acceso indirecto a la memoria) se denominan genéricamente como memoria en la especificación de las instrucciones que aparece a continuación.

1.6.2. Instrucciones de movimiento de datos

Equivalen a las típicas MOVE o LOAD/STORE para mover datos entre registros y/o memoria del mismo tipo. El formato general será:

dst  :=esp  org

donde:

• dst es el destino (contexto de lado izquierdo);
• org es el origen (contexto de lado derecho);
• esp es la especificación de tipo de dato (b|h|w|d|r); es opcional, si no aparece, se sobreentiende w; debería ser consistente con dst y org (por ejemplo, no puede usarse r sobre registros que no sean reales).

Ejemplos:

SP :=d 1024        ; llevar 1024 (como dirección) a SP
[SP-8] :=r R3      ; llevar el real contenido en R3 a la
                   ; dirección SP-8

A continuación, se enumeran los argumentos que pueden ser origen y destino, dependiendo de cada tipo de dato. En cualquiera de los casos, sin embargo, hay que anticipar que no es posible que el origen y el destino sean memoria simultáneamente, es decir, una instrucción como:

[SP-4] := [BP+20]    ; ¡erróneo!

no está admitida, debiendo escribirse como dos instrucciones:

AD := [BP+20]
[SP-4] := AD

La lista de argumentos admitida es:

• esp ∈ b|h|w (o no está presente)

  org	dst
  inmediato (b|h|w) registro RegDP	registro RegDP memoria
  memoria	registro RegDP

• esp = d

  org	dst
  inmediato (d|etiqueta) registro RegDP	registro RegDP memoria
  registro RegP con desplazamiento	registro RegP
  memoria	registro RegDP

  nótese que si org es registro RegP con desplazamiento, dst ha de ser un registro de direcciones (RegP).

• esp = r

  org	dst
  inmediato (r) registro RegR	registro RegR memoria
  memoria	registro RegR

1.6.3. Instrucciones aritméticas binarias

Contemplamos, para simplificar, solamente las operaciones básicas de cálculo (aditivas y multiplicativas), pero no habría ningún problema en disponer de otras (potencias y raíces, trigonométricas, etc.). El formato general es:

dst  op:=esp  org

donde:

• dst es el primer operando y el destino (contexto de lado izquierdo);
• org es el segundo operando (contexto de lado derecho);
• op es el operador;
• esp es la especificación de tipo de dato (b|h|w|d|r); es opcional, si no aparece, se sobreentiende w; debería ser consistente con dst, org y op.

Ejemplos:

AD +:=h 1024      ; sumar AD y 1024 (como enteros cortos),
                  ; y dejar el resultado en AD
R3 *:=r [SP-8]    ; multiplicar R3 y el contenido de SP-8
                  ; (como reales), y dejar el resultado en R3

Como antes, no es posible que el origen y el destino sean memoria simultáneamente, es decir, la siguiente instrucción no es válida:

[SP-4] +:= [BP+20]    ; ¡erróneo!

La lista de argumentos y operadores admitida es:

• esp ∈ b|h|w (o no está presente), entonces op ∈ +|-|*|/|%

  org	dst
  inmediato (b|h|w) registro RegDP	registro RegDP memoria
  memoria	registro RegDP

  / es el cociente y % es el resto de la división.

• esp = d, entonces op ∈ +|-

  org	dst
  inmediato (d) registro RegDP	registro RegDP memoria
  memoria	registro RegDP

• esp = r, entonces op ∈ +|-|*|/

  org	dst
  inmediato (r) registro RegR memoria	registro RegR

  / es el cociente (real) de la división. Obsérvese que las instrucciones aritméticas con reales solo pueden tener un registro RegR como destino.

1.6.4. Instrucciones aritméticas unarias

Son básicamente el cambio de signo y los complementos, y solo pueden aplicarse a enteros y reales. El operando origen ha de ser también el destino. El formato general es:

dst  op:=esp

donde:

• dst es el operando y el destino (contexto de lado izquierdo);
• op es el operador;
• esp es la especificación de tipo de dato (b|h|w|r); es opcional, si no aparece, se sobreentiende w; debería ser consistente con dst y op.

Ejemplos:

[BP+20] -:=h     ; cambiar de signo el entero corto contenido
                 ; en la dirección BP+20
R3 -:=r          ; cambiar de signo el real contenido en R3

La lista de argumentos y operadores admitida es:

• esp ∈ b|h|w (o no está presente), entonces op ∈ -|!, y dst puede ser registro RegD o memoria. - es el cambio de signo aritmético (complemento a 2) y ! es la negación bit a bit. Obsérvese que si se aplican a registros, han de ser de datos.
• esp = r, entonces op = -, y dst solo puede ser registro RegR. - es el cambio de signo aritmético.

1.6.5. Instrucciones de conversión de tipo de datos

Convierten entre enteros y/o reales. El dato real, sea origen, sea destino, debe estar en un registro RegR. Para convertir un entero en real, tenemos:

dst  w2r:=esp  org

donde:

• dst es el destino (contexto de lado izquierdo); solo puede ser registro RegR;
• org es el origen (contexto de lado derecho); pueder ser registro RegD o memoria (no se admiten inmediatos ni registros de direcciones);
• esp es la especificación de tipo de dato de origen (b|h|w); es opcional, si no aparece, se sobreentiende w.

Para convertir un real en entero, tenemos rnd (round, redondea) o trn (trunc, trunca):

dst  op:=esp  org

donde:

• dst es el destino (contexto de lado izquierdo); puede ser registro RegD o memoria (no se admite registro de direcciones);
• org es el origen (contexto de lado derecho); solo puede ser registro RegR;
• op es rnd|trn;
• esp es la especificación de tipo de dato de destino (letras b, h, w); es opcional, si no aparece, se sobreentiende w.

Ejemplos:

R3 w2r:=h [BP-24]     ; convertir entero corto de la dirección
                      ; BP-24 a real, y escribir resultado en R3
AD rnd:=w R7          ; convertir real del registro R7 a entero
                      ; (por redondeo) y escribir resultado en AD

1.6.6. Saltos incondicionales

Las instrucciones de control básicas estarían compuestas por los saltos condicionales y el salto incondicional. Nosotros no necesitaremos más que este último, por lo que es el único que se documenta:

JMP  dst

donde dst es la dirección a la que se salta (contexto de lado derecho), que puede ser: inmediato (d|etiqueta), registro RegP o memoria, pero no registro de datos.

Obviamente, el efecto de esta instrucción es modificar el valor del registro IP (más consistente con nuestra notación sería por lo tanto escribir:

IP  :=d  dst

pero en este caso preferimos la primera, más tradicional). Ejemplos:

JMP #procpar      ; saltar a la instrucción de etiqueta #procpar
JMP [BP-4]        ; saltar a la dirección contenida
                  ; en la dirección BP-4

1.6.7. Subrutinas

La máquina UDMC02 dispone del concepto de subrutina, incluyendo evidentemente, el de su llamada o activación y su retorno o terminación. En principio, es deseable que el código de una subrutina esté contiguo en el texto del programa, pero no es obligatorio. En el ensamblador que se está usando, el comienzo de una subrutina vendrá dado por una etiqueta (como #procpar en el ejemplo anterior) que se colocará a la primera instrucción que se quiera ejecutar de la misma. El final será la ejecución de la instrucción de retorno, pero no se señala de manera explícita en el código, ni tendrá que ser la última instrucción del texto de una subrutina.

Las instrucciones de llamada a y retorno de subrutina (CALL y RET, respectivamente) hacen siempre uso de la pila (y por tanto, usan y modifican el registro SP y las direcciones de memoria a las que este apunte). Evidentemente, también modifican el contador de programa IP. La instrucción CALL tiene el siguiente formato:

CALL  dst

donde dst es la dirección a la que se salta (contexto de lado derecho), que puede ser: inmediato (d|etiqueta), registro RegP o memoria, pero no registro de datos. Ejemplos:

CALL #procpar     ; llamar al código que está en #procpar
CALL [BP-24]      ; llamar al código que está en
                  ; la dirección BP-24

El efecto de esta instrucción se podría describir (si fueran instrucciones admisibles, que no lo son) de la siguiente manera:

SP +:=d 4
[SP-4] :=d IP+1
JMP dst

donde, evidentemente, con el IP+1 de la segunda instrucción nos referimos a la dirección de la instrucción que sigue a la CALL. Es decir:

• se reserva espacio para una dirección (4 bytes) en la pila, incrementando SP;
• se escribe en ese espacio la dirección de retorno, que es la que sigue a la instrucción CALL;
• se salta a la dirección dst.

La instrucción de retorno de subrutina RET tiene dos modalidades, la primera sin argumento:

RET

y una segunda con argumento, en cuyo caso ha de ser un dato inmediato (b|h|w), eso sí, positivo:

RET  inmediato

(por ejemplo, RET 12). Su efecto (salvando lo dicho antes para CALL) es el siguiente:

RP :=d [SP-4]
SP -:=d (4 + inmediato)    ; en el primer modo, queda 4
JMP RP

Nótese que se usa un registro de direcciones ficticio RP. Es decir:

• se supone que la cumbre de la pila debe contener una dirección (a veces, esto es mucho suponer, como se sabe); se recoge en cualquier caso un dato de tipo dirección (4 bytes) de la cumbre de la pila;
• en la primera modalidad, se elimina una dirección de la pila, decrementando SP en 4;
• en la segunda modalidad, se eliminan de la pila tantos bytes como el resultado de sumar 4 (una dirección) y el valor de inmediato;
• se salta a la dirección recogida en el primer paso.

1.6.8. Manejo de la pila

La pila que la máquina UDMC02 utiliza (como hemos visto, al menos para implementar las subrutinas) puede usarse para otros propósitos, pero siempre a través del registro de direcciones SP. Por ello, se proporcionan instrucciones de acumulación (PUSH) y eliminación (POP) de datos de la pila.

La instrucción PUSH tiene dos modalidades. La primera de ellas no incorpora argumento:

PUSHesp

donde esp es la especificación de tipo de dato a acumular (b|h|w|d|r); es opcional, si no aparece, se sobreentiende w.

Como resultado, se incrementa SP en el número de bytes asociado al tipo de dato esp, es decir, es totalmente equivalente a:

SP +:=d nbytes(esp)

Obsérvese que no se modifica de ninguna manera la memoria que se "ha reservado" de esta forma. Ejemplos:

PUSHr     ; reservar espacio para un real en la pila
PUSHd     ; reservar espacio para una dirección en la pila

La segunda modalidad de PUSH incorpora un argumento:

PUSHesp  org

donde org es el origen del dato a copiar en la pila (contexto de lado derecho) y esp es lo mismo que en el caso anterior.

Como resultado, primero se incrementa SP en el número de bytes asociado al tipo de dato esp, y luego se escribe el valor de lado derecho asociado a org en ese espacio, es decir, sería equivalente a:

SP +:=d nbytes(esp)
[SP-nbytes(esp)] :=esp org

Los argumentos válidos como origen son los siguientes:

• si esp ∈ b|h|w (o no está presente), entonces org puede ser: inmediato (b|h|w), registro RegDP o memoria;
• si esp = d, entonces org puede ser: inmediato (d), registro RegDP, registro RegP con desplazamiento o memoria;
• si esp = r, entonces org puede ser: inmediato (r), registro RegR o memoria.

Ejemplos:

PUSHh 12         ; acumula entero corto 12
PUSHr [BP-20]    ; acumula real almacenado en BP-20
PUSHd BP+4       ; acumula la dirección BP+4

La instrucción POP tiene dos modalidades. La primera de ellas no incorpora argumento:

POPesp

donde esp es la especificación de tipo de dato a eliminar (b|h|w|d|r); es opcional, si no aparece, se sobreentiende w.

Como resultado, se decrementa SP en el número de bytes asociado al tipo de dato esp, es decir, es totalmente equivalente a:

SP -:=d nbytes(esp)

Obsérvese que no se modifica de ninguna manera la memoria que se "ha liberado" de esta forma. Ejemplos:

POPr      ; liberar espacio de un real en la pila
POPd      ; liberar espacio de una dirección en la pila

La segunda modalida de POP incorpora un argumento:

POPesp  dst

donde dst es el destino donde se copiará el dato liberado de la pila (es un contexto de lado izquierdo, por lo tanto) y esp es lo mismo que en el caso anterior.

Como resultado, primero se escribe el dato de la cumbre de la pila en la dirección asociada a dst, y después se decrementa SP en el número de bytes asociado al tipo de dato esp, es decir, sería equivalente a:

dst :=esp [SP-nbytes(esp)]
SP -:=d nbytes(esp)

Los argumentos válidos como destino son los siguientes:

• si esp ∈ b|h|w|d (o no está presente), entonces dst puede ser registro RegDP o memoria;
• si esp = r, entonces org puede ser registro RegR o memoria.

Ejemplos:

POPh AD         ; sacar entero corto y escribirlo en registro AD
POPr [BP-20]    ; sacar real y escribirlo en dirección BP-20
POPd BP         ; sacar dirección y escribirla en registro BP

1.6.9. Miscelánea

La máquina UDMC02 no estaría completa sin la aportación de dos instrucciones importantísimas (NOP y HALT), cuyo significado es obvio.

1.7. Ejemplo de programas en ensamblador UDMC02

Mostramos la solución al examen de Compiladores II de septiembre de 2002.

; apartado A:  Ef( PF1, PC1 )
; parte del llamador

        PUSHr              ; reserva espacio para valor de retorno
        R0 w2r:=w [BP-24]  ; PF1 a real
        PUSHr R0           ; primer parámetro (por valor)
        EP :=d BP          ; PC1, dl=2, -24
        EP :=d [EP-12]
        EP :=d [EP-12]
        PUSHd EP-24        ; segundo parámetro (por referencia)
        EP :=d BP          ; Ef, dl=2
        EP :=d [EP-12]
        EP :=d [EP-12]
        PUSHd EP           ; enlace de acceso
        CALL #comEf        ; llamada (acumula dirección de retorno)  

; parte del receptor

#comEf: PUSHd BP           ; enlace de control
        BP :=d SP          ; actualiza BP
        SP +:=d 16         ; reserva espacio para locales

; apartado B:  LE3 := LA2 * PC2 + 7

        AD := [GP+4]       ; LA2 es global
        EP :=d BP          ; PC2, dl=2, -16
        EP :=d [EP-12]
        EP :=d [EP-12]
        BD := [[EP-16]]    ; PC2 es por referencia
        AD *:= BD          ; multiplicación
        AD +:= 7           ; suma
        EP :=d BP          ; LE3, dl=1, +12
        EP :=d [EP-12]
        [EP+12] := AD      ; asignación

; apartado C:  return( LCb ) que viene de LA1 := Cf( LA3, LA2 )
; parte del receptor

        AD := [BP+8]       ; obtiene valor de retorno
        [BP-28] := AD      ; asigna en espacio del valor de retorno
        SP :=d BP          ; libera locales y temporales
        POPd BP            ; recupera BP
        RET 4              ; retorna liberando enlace de acceso

; parte del llamador

        POPd               ; libera segundo parámetro (referencia)
        POPr [GP+8]        ; saca primer parámetro y escribe en LA3
        POP [GP+0]         ; saca valor de retorno y escribe en LA1

Bibliografía

James R. Larus [1994] "Appendix A. Assemblers, Linkers, and the SPIM Simulator" (en John L. Hennessy, David A. Patterson [1994] Computer organization and design: the hardware-software interface, Morgan Kaufmann, ISBN155860281X), páginas A1-A78.

Motorola, Inc.; IBM, Corp. [1997] PowerPC Microprocessor Family: The Programming Environments (MPCFPE/AD 1/97 REV.1).

Intel, Corp. [2003] IA-32 Intel Architecture Software Developer’s Manual (3 volúmenes).