El manejo de procedimientos o rutinas es uno de los aspectos mas importantes de la programación estructurada; por lo que cualquier repertorio de instrucciones debe de incluirlo de alguna manera.
Cuando se ejecuta un procedimiento, intrínsecamente se están realizando los siguientes pasos:
- Se colocan los argumentos (o parámetros) en algún lugar donde el procedimiento puede accesarlos.
- Se transfiere el control al procedimiento.
- Se adquieren los recursos de almacenamiento necesarios para el procesamiento.
- Se realiza la tarea deseada.
- Se coloca el valor del resultado en algún lugar donde el programa invocador puede accesarlo.
- Se regresa el control al punto de origen.
Anteriormente mencionamos que los registros son mas rápidos de manipular que las localidades en memoria, por lo tanto, la arquitectura MIPS dedica algunos registros para el manejo de procedimientos:
- $a0 - $a4 : Cuatro registros en los cuales se pueden pasar los argumentos. Si el número de argumentos es mayor, el resto deberá estar en memoria.
- $v0 - $v2 : Dos registros en los cuales se colocarán los valores de retorno.
- $ra : Un registro para almacenar la dirección de retorno, una vez que el procedimiento termine.
Además de la reserva de estos registros, MIPS incluye una instrucción que provoca un salto hacia la dirección del procedimiento al mismo tiempo que guarda la dirección de la instrucción siguiente en el registro $ra (nos estamos refiriendo a la dirección de retorno), la instrucción es:
jal Dirección_del_procedimiento ( jal – jump and link )
Aunque no se ha mencionado, pero al tener el programa almacenado en memoria, debe contarse con un registro que indique que instrucción se está ejecutando. A este registro por tradición se le denomina contador del programa (program counter) o PC en forma abreviada. La arquitectura MIPS incluye a este registro y no es parte de los 32 registros de propósito general. Véase la figura 3.3.1 para mayor detalle.
La instrucción jal guarda en $ra el valor de PC + 4 para ligar la siguiente instrucción en el retorno del procedimiento. De manera que el final de la rutina se marcaría con la instrucción:
jr $ra
La instrucción de salto a registro que se utilizó también en las estructuras switch-case.
Un punto importante en la llamada a los procedimientos, es que si dentro de algún procedimiento se van a utilizar algunos registros, su valor debe ser restaurado de manera que los registros conserven lo que contenían antes de que el procedimiento fuera invocado, para ello, su valor debe respaldarse en memoria. También con anterioridad habíamos comentado que si se requiere de un mayor número de argumentos éstos pueden ubicarse en memoria.
Una Pila (stack) es la estructura mas adecuada para resolver este tipo de situaciones, y en este caso, como en muchas otras arquitecturas, la pila crece hacía abajo, es decir, de las direcciones mas altas hacia las mas bajas. El registro dedicado como apuntador de la pila es el $sp (stack pointer), que corresponde al $29. Sin embargo, por la sencillez de la arquitectura MIPS no se incluyen instrucciones propias para la pila, mas bien los accesos se hacen combinando instrucciones simples, esto se ilustra en el siguiente ejemplo
Ejemplo: Un procedimiento que no llama a otros procedimientos.
¿Cuál sería el código MIPS para el procedimiento siguiente?
int ejemplo_simple ( int g, int h, int i, int j )
Respuesta:
{
int f;
f = ( g + h ) – ( i + j );
return f;
}
Los argumentos reciben en los registros: $a0, $a1, $a2 y $a3, que corresponden a las variables g, h, i y j, para f se utiliza al registro $s0. El procedimiento inicia con una etiqueta que corresponde a su nombre:
ejemplo_simple:
Lo primero que se realiza es el respaldo de las variables a utilizar:
sub $sp, $sp, 12 # Hace espacio en la Pila
sw $t1, 8 ($sp) # Salva a $t1 para uso posterior
sw $t0, 4 ($sp) # Salva a $t0 para uso posterior
sw $s0, 0 ($sp) # Salva a $s0 para uso posterior
Lo siguiente es el cuerpo del procedimiento:
add $t0, $a0, $a1 # $t0 = g + h
add $t1, $a2, $a3 # $t1 = i + j
sub $s0, $t0, $t1 # $f = ( g + h ) – ( i + j )
Antes de terminar se deben recuperar los valores almacenados en la Pila:
lw $t1, 8 ($sp) # Recupera a $t1
lw $t0, 4 ($sp) # Recupera a $t0
lw $s0, 0 ($sp) # Recupera a $s0
add $sp, $sp, 12 # Ajusta al puntero de la Pila
Finaliza la rutina:
jr $ra # Regresa a la instrucción posterior
# a la llamada a la rutina
En la figura 3.6.1 se muestra el comportamiento de la pila para este ejemplo
Fig. 3.6.1 Comportamiento de la Pila (a) Antes de la rutina, (b) durante la rutina (note que ya están almacenados los registros $t1, $t0 y $s0) y (c) después de la rutina (el $sp debe volver a su valor inicial).
En el ejemplo anterior se respaldaron en la pila todos lo registros por que se supuso que su valor podría estar siendo utilizado en alguna otra parte del programa. Para evitar accesos innecesarios a la memoria (y mejorar el rendimiento), los registros se dividen de la siguiente manera:
- $t0 - $t9 : 10 registros temporales cuyo valor no se preserva durante las llamadas a procedimientos.
- $s0 - $s7 : 8 registros seguros cuyo valor se preservará durante las llamadas a procedimientos.
Procedimientos anidados
Es común que un procedimiento invoque a otro procedimiento, en este caso ocurrirá un conflicto si no se busca como hacer esto. Por ejemplo, si un procedimiento A recibe como argumento al número 3, éste estará en el registro $a0. Si el procedimiento A invoca a un procedimiento B y le pasa como argumento al número 7 ¿Qué ocurrirá si se quiere usar el valor 3 después de la llamada al procedimiento B?
Se esperaría que no hubiera problemas en el manejo de procedimiento anidados y para ello se utiliza la pila, para conservar todos los registros que se van a utilizar dentro del procedimiento y recuperarlos justo antes de que el procedimiento finalice.
Existen dos criterios para este respaldo de registros:
- Guardar Invocador: El procedimiento invocador debe respaldar todos los registros que usará el procedimiento invocado, y recuperarlos una vez que termine el procedimiento. El procedimiento invocado no respalda registro alguno.
- Guardar Invocado: El procedimiento invocado es el que se encarga de respaldar y recuperar a los registros, el invocador simplemente realiza la invocación.
Ejemplo: Un procedimiento recursivo.
Consideremos la función que obtiene el factorial de un número:
int fact ( int n )
{
if ( n< 1) return 1;
return n * fact(n – 1);
}
Respuesta:
Puesto que el procedimiento es recursivo, debe conservarse la dirección de retorno y el valor del argumento, para que no se pierda en la medida en que se profundiza dentro de la recursividad:
fact:
Se evalúa para ver si ocurre el caso base (cuando n < 1):
sub $sp, $sp, 8 # Hace espacio en la Pila
sw $ra, 4 ($sp) # Salva la dirección de retorno
sw $a0, 0 ($sp) # Salva al argumento n
slt $t0, $a0, 1 # $t0 = 1 si n < 1
beq $t0, $zero, L1 # Si n no es menor que 1 continua en la función
Si ocurre el caso base, deberían recuperarse los datos de pila, pero como no se han modificado, no es necesario. Lo que si se requiere es restablecer al puntero de la pila.
add $v0, $zero, 1 # retorno = 1
add $sp, $sp, 8 # Restablece al apuntador de la pila
jr $ra # Finaliza regresando el resultado en $v0
Si no ocurre el caso base, prepara la llamada recursiva
L1: sub $a0, $a0, 1 # n = n - 1
jal fact # llama a fact con n – 1
Después de la llamada, se hace la restauración de los registros:
lw $a0, 0($sp) # Recupera el valor de n
lw $ra, 4($sp) # recupera la dirección de retorno
add $sp, $sp, 8 # Restablece al apuntador de la pila
Para concluir, se actualiza el valor de retorno y se regresa el control al invocador:
mul $v0, $a0, $v0 # Retorno = n * fact (n – 1)
jr $ra # regresa al invocador
La complejidad en los programas reales es que la pila también es usada para almacenar variables que son locales a los procedimientos, que no alcanzan en los registros, tales como arreglos locales o estructuras. El segmento de pila que contiene los registros salvados de un procedimiento y las variables locales es llamado armadura del procedimiento o (procedure frame). Se designa a un registro como apuntador a la armadura (el registro $fp que corresponde al $29), en la figura 3.6.2 se muestra el comportamiento de la pila, junto con el apuntador de armadura
Fig. 3.6.2 Comportamiento del apuntador de la armadura del procedimiento (a) Antes de una llamada (b) durante la llamada, y (c) después de la llamada.
Algunos programas usan el apuntador de armadura, en general éste puede no ser utilizado. La única ventaja de utilizarlo es que se cuenta con un registro base, a partir del cual se encuentran las variables locales a un procedimiento (que no alcanzaron en los registros), por lo que el compilador puede usar este registro para referenciar a las diferentes variables.