Cuando se traslada desde un lenguaje de alto nivel a ensamblador, en general, se realizan los pasos siguientes:
- Se asocian los registros con las variables del programa.
- Se produce el código para el cuerpo del procedimiento.
- Se preservan los registros a través del procedimiento.
El procedimiento SWAP
El procedimiento swap intercambia dos localidades de memoria. En C este procedimiento es:
void swap ( int v[ ], int k ) {
int temp;
temp = v[k];
v[k] = v[k+1];
v[k+1] = temp;
}
a)Asociación de registros con variables. El procedimiento swap recibe dos argumentos, por convención, estos argumentos los debe recibir en los registros $a0 (se asocia con el inicio del arreglo v) y $a1 (se asocia con la variable k).
Para la variable temp, debido a que swap es un procedimiento aislado, esta variable se asociará con el registro $t0 (que no debe preservarse a través de la llamada).
b)El cuerpo del procedimiento. En C el cuerpo del procedimiento es:
temp = v[k];
v[k] = v[k+1];
v[k+1] = temp;
debe considerarse que los datos se constituyen de palabras de 4 bytes, de manera que para obtener la dirección de v[k] primero se debe multiplicar a k por 4.
Add $t1, $a1, $a1 # $t1 = 2*k = k + k
Add $t1, $t1, $t1 # $t1 = 4*k = 2*k + 2*k
Add $t1, $a0, $t1 # $t1 tiene la dirección de v[k]
Ahora es posible hacer la carga de v[k], y de v[k + 1]
Lw $t0, 0($t1) # reg $t0 (temp) = v[k]
Lw $t2, 4($t1) # reg $t2 = v[k + 1]
Finalmente se hace el almacenamiento en memoria.
sw $t2, 0($t1) # v[k] = reg $t2
sw $t0, 4($t1) # v[k + 1] = reg $t0 (temp)
c)Preservación de registros. En este procedimiento no se preserva a algún registro, debido a que es un procedimiento aislado.
El código completo para la función swap es:
Swap: Add $t1, $a1, $a1 # $t1 = 2*k = k + k
Add $t1, $t1, $t1 # $t1 = 4*k = 2*k + 2*k
Add $t1, $a0, $t1 # $t1 tiene la dirección de v[k]
Lw $t0, 0($t1) # reg $t0 (temp) = v[k]
Lw $t2, 4($t1) # reg $t2 = v[k + 1]
sw $t2, 0($t1) # v[k] = reg $t2
sw $t0, 4($t1) # v[k + 1] = reg $t0 (temp)
jr $ra # Regresa a la rutina invocadora
Procedimiento sort
El procedimiento sort ordena los elementos de un arreglo, su código C es:
void sort ( int v[ ], int n ) {
int i, j;
for ( i = 0; i < n; i++ )
for (j = i – 1; j >= 0 && v[j] > v[j + 1]; j--)
swap( v, j);
}
a)Asociación de registros con variables. Los dos argumentos del procedimiento sort se reciben en los registros $a0 (inicio del arreglo v) y $a1 (la variable n). La variable i se asocia con el registro $s0 y j con el registro $s1.
b)El cuerpo del procedimiento. Para el ciclo mas externo:
for ( i = 0; i < n; i++ )
La primera expresión en ensamblador corresponde a:
Add $s0, $zero, $zero # i = 0
Luego se realiza la comparación:
For1o: slt $t0, $s0, $a1 # $t0 = 1 si i < n
Beq $t0, $zero, exit1 # Si $t0 = 0, termina este ciclo
El código siguiente corresponde al código que se realiza dentro de este ciclo repetitivo (cuerpo del primer for).
Una vez que este código concluye, se realiza el incremento y el salto a la siguiente iteración dentro del ciclo repetitivo.
Addi $s0, $s0, 1 # i ++
J For1o # Va a la siguiente iteración
El esqueleto de este primer ciclo repetitivo es:
Add $s0, $zero, $zero # i = 0
For1o: slt $t0, $s0, $a1 # $t0 = 1 si i < n
Beq $t0, $zero, exit1 # Si $t0 = 0 (i >= n), termina este ciclo
. . . .
. . . . # Cuerpo del primer for
Addi $s0, $s0, 1 # i ++
J For1o # Va a la siguiente iteración
Exit1:
El segundo for en C es:
for (j = i – 1; j >= 0 && v[j] > v[j + 1]; j--)
La inicialización de la variable j corresponde a:
Addi $s1, $s0, -1 # j = i - 1
Este ciclo prueba dos expresiones ligadas con un operador AND, si la primera falla, es suficiente para terminar con el ciclo. El cuerpo del for se realiza solo cuando las dos expresiones son verdaderas:
For2o: slt $t0, $s1, $zero # $t0 = 1 si j < 0
Bne $t0, $zero, exit2 # Si $t0 = 1 (j < 0), termina este ciclo
La segunda expresión a evaluar es v[j] > v[j + 1] si es verdadera se realiza el cuerpo del for, y en caso contrario, el ciclo termina. Esta prueba requiere transferir los datos de memoria a registros para poder compararlos, por lo que primero deberá multiplicarse a j por 4:
Add $t1, $s1, $s1 # $t1 = 2*j
Add $t1, $t1, $t1 # $t1 = 4*j
Add $t2, $a0, $t1 # $t2 tiene la dirección de v[j]
Se obtienen los datos a comparar:
Lw $t3, 0($t2) # $t3 tiene el valor de v[j]
Lw $t4, 4($t2) # $t4 tiene el valor de v[j + 1]
Ahora es posible la comparación:
slt $t0, $t4, $t3 # $t0 = 1 si v[j + 1] < v[j]
Beq $t0, $zero, exit2 # Si $t0 = 0 (v[j + 1] >= v[j]), termina
El código siguiente correspondería al cuerpo del ciclo for, y al final se debería incluir:
Addi $s1, $s1, -1 # El decremento j—
J For2o # El salto a la siguiente iteración
Juntando las piezas se obtiene el esqueleto del 2º. Ciclo for:
Addi $s1, $s0, -1 # j = i - 1
For2o: slt $t0, $s1, $zero # $t0 = 1 si j < 0
Bne $t0, $zero, exit2 # Si $t0 = 1 (j < 0), termina este ciclo
Add $t1, $s1, $s1 # $t1 = 2*j
Add $t1, $t1, $t1 # $t1 = 4*j
Add $t2, $a0, $t1 # $t2 tiene la dirección de v[j]
Lw $t3, 0($t2) # $t3 tiene el valor de v[j]
Lw $t4, 4($t2) # $t4 tiene el valor de v[j + 1]
slt $t0, $t4, $t3 # $t0 = 1 si v[j + 1] < v[j]
Beq $t0, $zero, exit2 # Si $t0 = 0 (v[j + 1] >= v[j]), termina
. . . .
. . . . # Cuerpo del segundo for
Addi $s1, $s1, -1 # El decremento j--
J For2o # El salto a la siguiente iteración
Exit2:
El cuerpo del ciclo mas interno incluye la llamada a la función swap, la cual aparentemente solo incluiría a la instrucción:
Jal swap
Sólo que al hacer la llamada debe considerarse el lugar correcto para los parámetros de la función swap. Los argumentos también deben preservarse a través de las llamadas, de manera que será necesario respaldar el valor actual de $a0 y $a1. Esto se hace con las instrucciones:
Add $s2, $a0, $zero # Se respalda el primer argumento
Add $s3, $a1, $zero # Se respalda el segundo argumento
Luego, ya será posible asignar los parámetros:
Add $a0, $s2, $zero # $a0 = v primer argumento de swap
Add $a1, $s1, $zero # $a0 = j segundo argumento de swap
c)Preservación de registros.
El primer registro a consideración es el que contiene la dirección de retorno, para que no se afecte con la llamada a swap. Además, debido a que el registro sort usa a los registros $s0, $s1, $s2 y $s3 debe respardarlos en la pila para preservarlos durante la llamada.
El prólogo del procedimiento sort es entonces:
Addi $sp, $sp, -20 # Hace espacio para 5 registros
Sw $ra, 16( $sp ) # Salva a $ra en la pila
Sw $s3, 12( $sp ) # Salva a $s3 en la pila
Sw $s2, 8( $sp ) # Salva a $s2 en la pila
Sw $s1, 4( $sp ) # Salva a $s1 en la pila
Sw $s0, 0( $sp ) # Salva a $s0 en la pila
Al final del procedimiento se recuperarían estos registros de la pila y se retornaría a la función invocadora.
El código completo para la función sort es:
#Respalda a los registros en la Pila
Sort: Addi $sp, $sp, -20 # Hace espacio para 5 registros
Sw $ra, 16( $sp ) # Salva a $ra en la pila
Sw $s3, 12( $sp ) # Salva a $s3 en la pila
Sw $s2, 8( $sp ) # Salva a $s2 en la pila
Sw $s1, 4( $sp ) # Salva a $s1 en la pila
Sw $s0, 0( $sp ) # Salva a $s0 en la pila
#Cuerpo del Procedimiento
#Mueve parámetros
Add $s2, $a0, $zero # Se respalda el primer argumento
Add $s3, $a1, $zero # Se respalda el segundo argumento
#Lazo externo
Add $s0, $zero, $zero # i = 0
For1o: slt $t0, $s0, $a1 # $t0 = 1 si i < n
Beq $t0, $zero, exit1 # Si $t0 = 0 (i >= n), termina
#Lazo interno
Addi $s1, $s0, -1 # j = i – 1
For2o: slt $t0, $s1, $zero # $t0 = 1 si j < 0
Bne $t0, $zero, exit2 # Si $t0 = 1 (j < 0), termina este ciclo
Add $t1, $s1, $s1 # $t1 = 2*j
Add $t1, $t1, $t1 # $t1 = 4*j
Add $t2, $a0, $t1 # $t2 tiene la dirección de v[j]
Lw $t3, 0($t2) # $t3 tiene el valor de v[j]
Lw $t4, 4($t2) # $t4 tiene el valor de v[j + 1]
slt $t0, $t4, $t3 # $t0 = 1 si v[j + 1] < v[j]
Beq $t0, $zero, exit2 # Si $t0 = 0 (v[j + 1] >= v[j]), termina
#Pase de parámetros y llama a swap
Add $a0, $s2, $zero # $a0 = v primer argumento de swap
Add $a1, $s1, $zero # $a0 = j segundo argumento de swap
Jal swap # Llama a swap
#Lazo interno
Addi $s1, $s1, -1 # El decremento j--
J For2o # El salto a la siguiente iteración
#Lazo externo
Exit2: Addi $s1, $s1, -1 # El decremento j--
J For2o # El salto a la siguiente iteración
#Restauración de Registros
Exit1: Lw $ra, 16( $sp ) # Recupera a $ra
Lw $s3, 12( $sp ) # Recupera a $s3
Lw $s2, 8( $sp ) # Recupera a $s2
Lw $s1, 4( $sp ) # Recupera a $s1
Lw $s0, 0( $sp ) # Recupera a $s0
Addi $sp, $sp, -20 # Recupera la pila
#Regresa del procedimiento
Jr $ra
Ejemplo: Carga de patrones arbitrarios de bits en registros
Considere el patrón de bits de la siguiente figura
correspondiente a una instrucción addi. Muestre cómo se puede cargar en el registro $s0 este patrón de bits particular. ¿Y cómo se puede poner en $s0 un patrón de bits que consiste en únicamente 1's?
Solución:
La mitad superior del patrón de bits tiene la representación hexadecimal 0x2110, mientras que la mitad inferior es 0x003d. Por lo tanto, las siguientes dos instrucciones logran lo que se requiere:
lui $s0, 0x2110 # pone mitad superior de patrón en $s0
ori $s0, $s0, 0x003d # pone mitad inferior de patrón en $s0
Estas dos instrucciones, con sus operandos inmediatos cambiados a 0xffff podría colocar el patrón de todos los 1 en $s0. Sin embargo, una forma más simple y rápida sucede a través de la instrucción NOR:
NOR $s0,$zero,$zero # porque (0 nor 0)=1
En representación de complemento a 2, el patrón de bits todos en 1 corresponde al entero -1.