Llamadas a Procedimiento.

Un procedimiento o subrutina es un conjunto de instrucciones independiente, que cumple alguna función en particular, y que es llamada y ejecutada en el programa cuando ésta se necesite. Las subrutinas son útiles también cuando se desea tener un programa bien estructurado, ordenado y que sea fácil de entender. La llamada a un procedimiento se diferencia de una instrucción de salto, debido a que la ejecución de un procedimiento implica después un retorno al punto donde se realizó la llamada.
Para soportar llamadas a subrutinas en lenguaje de máquina, se cuenta con una instrucción que bifurca a una dirección y simultáneamente guarda la dirección de la siguiente instrucción en el registro $31. La dirección almacenada en este registro se denomina dirección de retorno. La instrucción call (llamar a, o también, jump-and-link, tomado del $\mu$procesador SPARC) tiene la siguiente forma:

call SubrutineAddress

Para retornar, utilizaremos la instrucción jr (jump register), que fue utilizada en la instrucción switch. La instrucción jr tiene la forma:

$31 (o también jr $ra)

que significa, saltar a la dirección que está contenida en el registro $31.
Como vimos, el registro $31 contiene la dirección de retorno, pero ¿quién contiene la dirección de la instrucción actual, o de la siguiente a ejecutar?, existe un registro que cumple esta tarea, y se denomina contador de programa (program counter o PC), registro especial del procesador que es prácticamente invisible al programador.

Ejemplo 8.

SubA: add $1,$2,$3
      sw  $1,Mem1
      ...
      ...
      call SubB         # Llama a SubB
      ...
      ...
      jr $31            # Retorna al punto donde se llamó a SubA.

SubB: ...
      ...
      lw $3,Mem2
      add $1,$2,$3
      ...
      ...
      add $29,$29,$24   # Ajusta puntero de pila.
      sw  $31,0($29)    # Guarda dirección de retorno.
      call  SubC   	# Llama a SubC.
      ...
      lw $31,0($29)     # Recupera direc. de retorno de SubB.
      sub  $29,$29,$24  # Ajusta puntero de pila.
      ...
      jr  $31           # Retorna a rutina que llamó a B.

SubC: ...
      ...
      lw $31,0($29)     # Recupera direc. de retorno de SubC.
      sub  $29,$29,$24  # Ajusta puntero de pila.
      ...
      jr $31            # Retorna a rutina que llamó a C.

Como sólo es posible guardar una sola dirección de retorno en el registro $31, cuando se lleven a cabo sucesivas llamadas a subrutina, este registro no podrá contener todas las direcciones de retorno debido a esas llamadas. Por tanto, la solución ideal es almacenarlas en memoria. Se define entonces una región de memoria denominada pila o stack (estructura de tipo LIFO: last in-first out) que permitirá guardar estas direcciones de retorno.
Cada vez que se lleva a cabo una nueva llamada a subrutina, se debe ajustar el puntero de pila (sp) y guardar la dirección de retorno en la pila del programa, con las instrucciones:

  add  $29,$29,$24  # Ajusta puntero de pila.
  sw   $31,0($29)   # Guarda direccion de retorno en la pila, tomada 
desde el registro $31.

Esta operación se denomina PUSH.

El registro $24 debe contener un valor negativo, debido a que la pila crece desde las regiones altas hacia las regiones bajas de memoria.
Recordemos además, que el registro $29 es utilizado como puntero de pila.
Cuando se produce un retorno, antes se debe recuperar desde la pila la dirección de retorno y volver a reajustar el puntero de pila. Esto se lleva a cabo con las siguientes instrucciones:

  lw   $31,0($29)     # Recupera direc. de retorno y la carga en $31.
  sub  $29, $29,$24   # Ajusta puntero de pila.

Esta operación se denomina POP.

Por último, se utiliza la instrucción jr $31 para producir el retorno.
También es posible entregar argumentos a las subrutinas en el momento de la llamada, pero este proceso es un poco más complejo. Las arquitecturas RISC generalmente llevan a cabo el pasaje de parámetros a través de los registros del mismo procesador. Nuestra arquitectura utilizará los registros $4 a $7 ($a0 a $a3) para este propósito. Si una subrutina requiere más de cuatro parámetros, entonces el resto deberá ser trasladado a la pila del mismo programa. Para ello se crea un frame o porción de memoria dentro de la pila para este propósito llamado marco de llamada a procedimiento (procedure call frame, también conocido como registro de activación) . En esta porción de memoria, que como se dijo anteriormente forma parte de la pila del programa, se cargarán los parámetros que no pueden ser colocados en los registros del procesador (recordemos que hasta cuatro parámetros pueden ser soportados por los registros), también residirán las variables locales de los procedimientos y la dirección de retorno. Ahora, ¿de qué tamaño debe ser el frame?, eso depende de la cantidad de parámetros y variables locales de un procedimiento.
La figura 7.4 muestra en forma simplificada la estructura de la pila en el momento en que se ha hecho una llamada y el sistema genera un frame o marco para guardar parámetros y variables locales. Por ejemplo, un argumento en la estructura de pila puede ser cargada en el registro $2 con la instrucción:

lw $2,0($fp)

Figure 7.4: Un frame de Pila.

El registro $fp ($30) apunta al primer byte de la primera palabra de la estructura de pila del procedimiento que actualmente se está ejecutando, y el puntero de pila $sp ($29) apunta a la primera palabra libre del área de pila, después de la estructura.
Tanto el invocador, como el procedimiento invocado deben estar de acuerdo en cómo llevar a cabo las distintas etapas durante la llamada. En la primera parte, el invocador pone los argumentos de llamada del procedimiento en posiciones que son comunes y realiza la llamada para:

1. Pasar los argumentos. Por convención, los cuatro primeros argumentos son pasados a los registros $a0 a $a3. Cualquier argumento restante se introduce en la pila y aparece al comienzo de la estructura de pila ( frame) del procedimiento invocado.
2. Salvar los registros guardados por el invocador. El procedimiento invocado puede utilizar estos registros ($a0-$a3 y $t0-$t9) sin guardar primero su valor. Si el invocador espera utilizar uno de estos registros después de una llamada, debe guardar su valor antes de la llamada.
3. Ejecutar una instrucción call, que bifurca a la primera instrucción del invocado y guarda la dirección de retorno en el registro $ra ($31).

Antes de que comience a ejecutarse una rutina invocada, se deben realizar los siguientes pasos para inicializar su estructura de pila:

1. Asignar memoria a la estructura restando el tamaño de la estructura del puntero de pila.
2. Guardar los registros para guardar la rutina invocada en la estructura. Una llamada debe guardar los valores de estos registros ($s0-$s7,$fp, y $ra) antes de alterarlos ya que el invocador espera encontrar estos registros inalterados después de la llamada. El registro $fp es guardado por cada procedimiento que asigna una nueva estructura de pila. Sin embargo, el registro $ra solamente necesita ser guardado si la misma rutina invocada realiza una llamada a otro procedimiento. Los demás registros que se utilizan deben ser guardados.
3. Establecer el puntero de frame sumando el tamaño de la estructura de la pila a $sp y almacenar la suma en el registro $fp.

Finalmente, la rutina llamada retorna al procedimiento invocador ejecutando los siguientes pasos:

1. Si la rutina invocada es una función que devuelve un valor, coloca el valor de retorno en el registro $v0 ($2).
2. Restaura todos los registros de guardar invocado que se guardaron en la entrada del procedimiento.
3. Sacar la estructura de pila restando el tamaño de estructura de $sp.
4. Volver bifurcando a la dirección del registro $ra.

Ejemplo 9.

Consideremos el siguiente programa en lenguaje C, que calcula e imprime el factorial de 10:

main() {
    printf("El factorial de 10 es %d\n",fact(10));
 }

int fact(int n) { /*rutina recursiva*/
    if (n < 1) return 1;
    else return (n*fact(n-1));
}

Programa en lenguaje assembly:

        .section "text"
        .align 	word
        .global main
 main:  subu    $sp,$sp,32    # Frame de pila tiene 32 bytes
        sw      $ra,20($sp)   # Guarda dirección de retorno
        sw      $fp,16($sp)   # Guarda puntero de frame antiguo
        addu    $fp,$sp,32    # Activa puntero de frame
        li      $a0,10        # Carga argumento 10 en $a0
        call    fact          # Llama a función fact
        la      $a0,$LC0      # Pone string de formato en $a0
        mov     $a1,$v0       # Mueve resultado de fact a $a1
        call    printf        # Llama a función printf

Finalmente, después de imprimir el factorial, main vuelve. Pero primero debe restaurar los registros que guardó y sacó de su estructura de pila:

        lw     $ra,20($sp)   # Restaura dirección de retorno
        lw     $fp,16($sp)   # Restaura puntero de frame
        addu   $sp,$sp,32    # Retira estructura de pila (pop)
        jr     $ra           # Retorna al invocador

        .section ".rodata"
$LC0    .ascii	"El factorial de 10 es %d\n\000"

La rutina recursiva que calcula el factorial realiza algunas tareas similares quelas que hizo main, primero crea una estructura de pila y guarda los registros de guardarinvocado que utilizará. Además, para guardar $ra y $fp, la rutina fact también guarda su argumento ($a0), que utilizará para la llamada recursiva:

        .section "text"
        .align word
fact:   subu   $sp,$sp,32   # Estructura de pila es de 32 bytes
        sw     $ra,20($sp)  # Guarda dirección de retorno
        sw     $fp,16($sp)  # Guarda puntero de frame antiguo
        addu   $fp,$sp,32   # Activa puntero de frame
        sw     $a0,0($fp)   # Guarda argumento n (tipo entero)

En el resto del programa, fact se dedica a calcular el factorial de 10, examinando primero si el argumento es mayor que cero:

       lw   $2,0($fp) # Carga n
       bgtz $2,$L2    # Salta a $L2 si n > 0
       li   $2,1      # Devuelve 1
       j    $L1       # Salta a código para retornar
$L2:   lw   $3,0($fp) # Carga n
       subu $2,$3,1   # Calcula n-1
       mov  $a0,$2    # Mueve valor a $a0
       call fact      # Llama a función fact
       lw   $3,0($fp) # Carga n
       mult $2,$2,$3  # Calcula fact(n-1)*n

Luego, la rutina fact restaura los registros de guardar invocados y devuelve el valor al registro $2. Ahora el resultado está en $2 ($v0):

$L1:   lw   $31,20($sp)   # Restaura $ra
       lw   $fp,16($sp)   # Restaura $fp
       addu $sp,$sp,32    # Saca de pila (pop)
       jr   $31           # Retorna al invocador (main)

Finalmente, la figura 7.5 muestra la pila del programa cuando se realiza hasta la llamada fact(7). La función main se ejecuta primero, ya que ésta es invocada por una rutina especial del sistema operativo.

Figure 7.5: Estructura y contenido de la pila del programa cuando se realiza la llamada hasta fact(7).