L7: Practica 3

Sesión Laboratorio 7: Práctica 3-1

• Tiempo: 2h
• Objetivos de la sesión:
  • Comprender el concepto de "salto"
  • Aprender cómo el procesador toma decisiones
  • Saber aplicar las instrucciones de salto condicional para:
    • Hacer bucles que terminen cuando se cumple una condición
    • Comparar valores en los registros
  • Practicar. Practicar. Practicar

Vídeos

• Fecha: 2019/Nov/21

Vídeo 1/6: Introducción. Toma de decisiones en los procesadores

Haz click en la imagen para ver el vídeo en Youtube

Vídeo 2/6: Saltos incondicionales hacia adelante

Haz click en la imagen para ver el vídeo en Youtube

Vídeo 3/6: Instrucción b / jal

Haz click en la imagen para ver el vídeo en Youtube

Vídeo 4/6: Salto incondicional hacia atrás

Haz click en la imagen para ver el vídeo en Youtube

Vídeo 5/6: Saltos condicionales. Toma de decisiones (IF)

Haz click en la imagen para ver el vídeo en Youtube

Vídeo 6/6: Bucles (FOR)

Haz click en la imagen para ver el vídeo en Youtube

Contenido

• Introducción
• Saltos incondicionales
  • Salto hacia adelante
  • Instrucción b
  • Juego de instrucciones comprimido
  • Salto hacia atrás
  • Salto con offset-0: Bucle infinito en una instrucción
• Saltos condicionales
  • Ejemplo: Comprobar si dos registros son iguales
  • Comprobando si dos registros son diferentes
• Haciendo bucles
  • Ejemplo: Imprimiendo los números del 1 al 10
  • Contando los caracteres de una cadena
• Actividades NO guiadas
  • Ejercicio 1
  • Ejercicio 2
  • Ejercicio 3
  • Ejercicio 4
  • Ejercicio 5
  • Ejercicio 6
  • Ejercicio 7
  • Ejercicio 8
  • Ejercicio 9
  • Ejercicio 10
• Autores
• Licencia
• Enlaces

Introducción

Ya vimos que el comportamiento por defecto del procesador es leer una instrucción de memoria, ejecutarla, leer la siguiente, ejecutarla... Las instrucciones se van ejecutando secuencialmente, una detrás de otra

Sin embargo, ese comportamiento lo podemos alterar para que se ejecuten instrucciones situadas en otros lugares de la memoria. Es lo que se denominan saltos

Saltos incondicionales

Mediante las instrucciones de salto incondicional modificamos el comportamiento del microprocesador para que siga ejecutando instrucciones situadas en otro punto de la memoria. En vez de continuar con la siguiente instrucción, podemos indicarle que ejecute las que se encuentran a partir de una dirección de memoria. La instrucción que utilizaremos para hacer estos saltos es b (branch)

Salto hacia adelante

En este ejemplo le damos los dos valores testigo 0xCAFE y 0xBACA a los registros t0 y t1 al comienzo del programa. Realizamos un salto hacia adelante para continuar con la ejecución de las instrucciones situadas a partir de la dirección de memoria indicada por la etiqueta salta. El código de ahí simplemente devuelve el control al sistema operativo

#-- Ejemplo de salto incondicional
#-- hacia adelante	
	.text
	
	#-- Dar valores a t0 y t1
	li t0, 0xCAFE
	li t1, 0xBACA
	
	#-- El procesador comienza a ejecutar
	#-- las instrucciones etiquetadas como salta
	b salta
	
	#-- "Salta" por encima de estas instrucciones,
	#-- que NO se ejecutan
	li t0, 0x0000
	li t1, 0xFFFF

salta:
	#-- Terminar
	li a7, 10
	ecall	
	
	#-- Los registros t0 y t1 
	#-- valen CAFE y BACA respectivamente

Observamos que hay dos instrucciones que dan los valores 0x0000 y 0xFFFF a los registros t0 y t1, que NUNCA se ejecutan. El procesador ha pasado por "encima de ellas" (decimos que las ha saltado) para continuar ejecutando las que están a partir de la etiqueta salta

De esta forma, al ejecutar el programa, observamos que los valores de t0 y t1 son los que se han establecido al comienzo: 0xCAFE y 0xBACA

En esta animación de la ejecución paso a paso del programa se ve más claramente el salto que hace el microprocesador

Instrucción b

La instrucción b es en realidad una pseudoinstrucción, que en el ejemplo 1 se traduce a la siguiente instrucción básica:

jal x0, 0x08

Si activamos la tabla de símbolos en el ejemplo anterior, comprobamos que la etiqueta salta contiene la dirección 0x00400020

El funcionamiento de la instrucción b se muestra en este dibujo, donde se ha representado el mapa de memoria correspondiente al programa anterior (ejemplo 1)

El microprocesador ejecuta las instrucciones desde arriba hasta abajo, comenzando en la dirección 0x00400000. Al llegar a la dirección 0x00400010 ejecuta el salto, por lo que continúa con la ejecución de la instrucción que está en la dirección 0x00400020 (que se corresponde con la etiqueta salta)

Las instrucciones de salto realizan un salto relativo, en el que tienen un campo offset que indica cuánto moverse hacia adelante, o hacia atrás (offset negativo). En el ejemplo 1, el procesador ha saltado 4 instrucciones hacia adelante. Como cada instrucción es una palabra, se ha hecho un salto hacia adelante de 4 palabras. Sin embargo, en la instrucción jal (que es la que hace realmente el salto), se ha utilizado el offset con valor 0x08. En realidad, la cuenta del offset en el RISC-V se hace en medias-palabras (16 bits). De esta forma, el salto de 4 palabras hacia adelante, es el mismo que un salto de 8 medias-palabras

Juego de instrucciones comprimido

La razón por la que el offset de los saltos se mide en medias palabras es porque el RISC-V tiene una extensión, conocida como RV32C, que implementa un juego de instrucciones comprimido. Algunas instrucciones comunes se codifican de forma que ocupen 16 bits, en vez de 32. De esta forma, se pueden comprimir dos instrucciones en lo que antes ocupaba una, con lo que se consiguen ahorros de hasta un 25% en el tamaño de los programas. Puedes encontrar más información en este documento: riscv-compressed-spec-v1.7.pdf

En esta asignatura NO veremos las instrucciones comprimidas

Salto hacia atrás

También se pueden realizar saltos hacia atrás, retrocediendo hacia direcciones más bajas de memoria, como se muestra en este ejemplo. El programa principal inicializa los registro t0 y t1 con los valores 0 y 2 respectivamente. Incrementa t0 en uno, t1 en dos y salta dos instrucciones hacia atrás para repetir el proceso. El ciclo se repite indefinidamente hasta que paramos el simulador o apagamos el microprocesador real. Se denomina bucle infinito (y es algo que se debe evitar. El control siempre hay que devolvérselo al sistema operativo)

#-- Ejemplo de salto incondicional
#-- hacia atras	
	.text
	
	#-- Inicializar t0 a 0
	li t0, 0
	
	#-- Inicializar t1 a 2
	li t1, 2
	
bucle:
	#-- Incrementar t0 en 1
	addi t0, t0, 1
	
	#-- Incrementar t1 en 2 unidades
	addi t1, t1, 2
	
	#-- Repetir el bucle (infinitas veces)
	#-- Salto hacia atras
	b bucle
	
	#-- Como es un bucle infinito
	#-- El codigo que hay aqui nunca se ejecuta

En esta animación se muestra el programa en funcionamiento. El micro ejecuta las instrucciones, una detrás de otra. Al llegar a la última retrocede 2 instrucciones, y continúa ejecutando

En la tabla de símbolos podemos ver la dirección asignada a la etiqueta bucle: 0x00400008

Si observamos la instrucción de salto que se ha generado, es:

jal x0, 0xfffffffc

El offset se interpreta como un número con signo. Como el salto es hacia atrás, esto se interpreta como negativo (la dirección de memoria se decrementa). El salto es ahora 2 instrucciones hacia atrás

Como el offset se especifica en medias palabras, se está realizando un salto de 4 medias palabras hacia atrás. Es decir, el offset es de -4. Que puesto en complemento a dos de 32 bits es el número 0xFFFFFFFC

Los offsets de las instrucciones de salto los podemos convertir fácilmente de hexadecimal a decimal con signo con la opción hexadecimal Values

Salto con offset 0: Bucle infinito de una instrucción

Este es un ejemplo de una instrucción que salta a sí misma, y por tanto se entra en un bucle infinito que no hace nada

#-- Ejemplo de salto incondicional
#-- a la propia instrucción: offset 0
	.text
	
	#-- Salto a la propia instruccion
	#-- Esto es un bucle infinito, que
	#-- no hace nada
inf:	b inf

El programa sólo tiene una instrucción, que se sitúa al comienzo del segmento de código. Por tanto, la etiqueta inf tiene ese mismo valor: 0x00400000

La instrucción de salto generada tiene offset 0:

jal x0, 0x0

Esto hace que la siguiente instrucción a ejecutar sea la que está en la dirección actual más 0. Es decir, otra vez la que se acaba de ejecutar. Así hasta el infinito... o hasta que se quite la alimentación del microprocesador

Saltos condicionales

Las instrucciones de salto condicional permiten al procesador tomar decisiones. Son muy importantes. Con ellas podemos comparar los valores de los registros y realizar unas acciones u otras en función los resultados. También nos sirven para hacer bucles que terminen al cumplirse alguna condición

Las instrucciones básicas de salto condicional son: beq, bne, bge y blt. Realizan las operaciones de comparación de igualdad (=), de desigualdad (!=), mayor o igual (>=) ó menor que (<). Como los saltos condicionales se utilizan mucho, se definen más pseudo-instrucciones para facilitarnos la vida: beqz, bgez, bgt, ble...

Ejemplo: Comprobar si dos registros son iguales

Empezaremos practicando con la instrucción beq que nos permite saber si dos registros son iguales o no. En caso de ser iguales se realiza un salto. Si no son iguales se continúa ejecutando el código que sigue a beq

En este ejemplo damos dos valores a los registros t0 y t1, y los comparamos. Si son iguales, se imprime la cadena "IGUALES", pero si son diferentes se imprimirá "DIFERENTES"

La lógica que se está implementando en el programa es el equivalente al if de los lenguajes de alto nivel:

  if t0 == t1:
    print("IGUALES")
  else:
    print("DIFERENTES")

Este es el programa en ensamblador

#-- Comparar el valor de dos registros
#-- Si son iguales imprime el mensaje "IGUALES"
#-- Si son diferentes, se imprime "DIFERENTES"

	.include "servicios.asm"
	
	#-- Valores constantes a comparar
	.eqv VALOR1 10
	.eqv VALOR2 10
	
	.data
	
	#-- Mensajes a imprimir en la consola
msg_iguales:     .string "IGUALES\n"
msg_diferentes:  .string "DIFERENTES\n"

	.text
	
	#-- Inicializar los registro t0 y t1 con dos valores
	li t0, VALOR1
	li t1, VALOR2
	
	#-- Realizar la comparacion de t0 y t1
	beq t0, t1, iguales
	
	#-- NO son iguales. 
	#-- Imprmir el mensaje "DIFERENTES"
	la a0, msg_diferentes
	li a7, PRINT_STRING
	ecall
	
	#-- Para terminar saltamos al codigo que hemos definido
	#-- para terminar. RECUERDA: es conveniente que SOLO haya un 
	#-- PUNTO DE SALIDA
	b fin
	
	#-- Son iguales. Se imprime el mensaje IGUALES
iguales:

	la a0, msg_iguales
	li a7, PRINT_STRING
	ecall


	#-- PUNTO DE SALIDA
	#-- BUENAS PRÁCTICAS DE PROGRAMACIÓN: que el punto de salida sea UNICO	
fin:	
	#-- Terminar
	li a7, EXIT
	ecall

La clave está en la instrucción beq:

beq t0, t1, iguales

Cuando t0 y t1 son iguales, el micro ejecuta las instrucciones que están a partir de la etiqueta iguales. En caso contrario, continúa ejecutando las que están a continuación del beq

Al ejecutarlo vemos que en la consola aparece la cadena IGUALES

En esta animación se muestra el funcionamiento. Primero se asigna el mismo valor a ambos registros, y se comprueba que se obtiene la cadena "IGUALES". Luego se vuelve a ejecutar pero colocando valores diferentes: ahora aparece la cadena "DIFERENTES"

Comprobando si dos registros son diferentes

La condición de que dos registros sean diferentes se comprueba con la instrucción bne que realiza un salto si NO son iguales. Es justo la contraria de beq

Como ejemplo haremos el mismo ejemplo anterior de comparación de dos números, pero usando bne en lugar de beq. Si los números son diferentes, se imprime el mensaje "DIFERENTES" y si son iguales se imprime "IGUALES"

Si lo expresásemos en un lenguaje de alto nivel, este sería el código:

if t0 != t1:
  print("DIFERENTES")
else:
  print("IGUALES")

Este es el programa en ensamblador:

#-- Comparar el valor de dos registros
#-- Si son iguales imprime el mensaje "IGUALES"
#-- Si son diferentes, se imprime "DIFERENTES"
#-- Se utiliza la instruccion bne

	.include "servicios.asm"
	
	#-- Valores constantes a comparar
	.eqv VALOR1 10
	.eqv VALOR2 10
	
	.data
	
	#-- Mensajes a imprimir en la consola
msg_iguales:     .string "IGUALES\n"
msg_diferentes:  .string "DIFERENTES\n"

	.text
	
	#-- Inicializar los registro t0 y t1 con dos valores
	li t0, VALOR1
	li t1, VALOR2
	
	#-- Realizar la comparacion de t0 y t1
	bne t0, t1, diferentes
	
	#-- Son iguales
	la a0, msg_iguales
	li a7, PRINT_STRING
	ecall
	
	#-- Ir al PUNTO DE SALIDA
	b fin
	
	#-- Son diferentes
diferentes:

	la a0, msg_diferentes
	li a7, PRINT_STRING
	ecall

	#-- PUNTO DE SALIDA
fin:	
	#-- Terminar
	li a7, EXIT
	ecall

La instrucción clave es:

bne t0,t1, diferentes

Si los registros t0 y t1 son diferentes, salta a ejecutar el código situado a partir de la etiqueta no_iguales. En caso contrario continúa ejecutando las instrucciones que están a continuación de bne

Por lo demás, este código es prácticamente igual al del ejemplo anterior. El mismo programa se puede implementar de múltiples maneras

Haciendo bucles

Las instrucciones de salto condicional nos permite hacer bucles que terminen cuando se cumpla una condición de salida

Ejemplo: Imprimiendo los números de 1 al 10

La instrucción blt realiza un salto si el primer registro es estrictamente menor que el segundo. Esto es muy útil para hacer, por ejemplo bucles que terminen cuando se alcanza un valor máximo

En este ejemplo se utiliza el registro t0 para contar de 1 a 10. Mientras que t0 sea menor a 10, se repite el bucle. En cuanto es 10, se termina

#-- Ejemplo de uso de bucles
#-- El programa imprime los números de 1 al 10
#-- en la consola y termina

	.include "servicios.asm"
	
	#-- Valor maximo del contador
	.eqv MAX 10
	
	#-- Caracter de salto de linea (\n)
	.eqv LF 10
	
	.text
	
	#-- t0 lo usamos de contador: 1,2,3,4...
	li t0, 0
	
bucle:
	#-- Incrementar el contador
	addi t0, t0, 1
	
	#-- Imprimir su valor
	mv a0, t0
	li a7, PRINT_INT
	ecall
	
	#-- Imprimir '\n' para separar los numeros
	li a0, LF
	li a7, PRINT_CHAR
	ecall
	
	#-- Si t0 < MAX repetir
	li t1, MAX
	blt t0, t1, bucle
	
	#-- Terminar
	li a7, EXIT
	ecall

La instrucción clave es:

blt t0, t1, bucle

Mientras que t0 < t1, se repite el bucle. A t1 se le ha asignado el valor constante MAX. El código equivalente en un lenguaje de alto nivel sería el siguiente:

t0 = 0
MAX = 10
while (t0 < MAX):
  t0 += 1
  print(t0)

Al ejecutar el programa, vemos los números del 1 al 10 impresos en la consola

Contando los caracteres de una cadena

Los bucles nos sirven para recorrer cadenas, detectando cuándo se llega al final. Esto lo sabemos porque su último elemento es el '\0'

Este programa calcula el número de caracteres que hay en una cadena. El programa usa un puntero, t0, para acceder a todos los elementos de la cadena hasta que alguno de ellos es 0. En ese momento se imprime su longitud

#-- Ejemplo de uso de bucles
#-- Recorrer una cadena para calcular su longitud

	.include "servicios.asm"
	
	.data
cad:	.string "Cadena de prueba"
msg:    .string "Longitud de la cadena: "
	
	.text
	
	#-- t0 es el puntero a la cadena
	la t0, cad
	
	#-- t1 es el contador de caracteres de la cadena
	li t1, 0

bucle:	
	#--- Leer el primer caracter de la cadena
	lb t2, 0(t0)
	
	#-- Si el caracter es zero, hemos terminado de 
	#-- recorrer la cadena
	beq t2, zero, fin_bucle
	
	#-- El caracter NO es cero. Incrementar el contador
	addi t1, t1, 1
	
	#-- Apuntar al siguiente caracter
	addi t0, t0, 1
	
	#-- Repetir
	b bucle
	
	
	#-- Se ha alcanzado el final de la cadena
fin_bucle:
	
	#-- Print "Longitud cadena: "
	la a0, msg
	li a7, PRINT_STRING
	ecall
	
	#-- Imprimir el numero de carateres, que está
	#-- en el contador t1
	mv a0, t1
	li a7, PRINT_INT
	ecall 

	#-- Terminar
	li a7, EXIT
	ecall     

Al ejecutar el programa obtenemos 16, que es efectivamente la longitud de la cadena usada de ejemplo

Actividades NO guiadas

Escribe muchos programas. Pruébalos. Modifícalos. Piensa en todos los casos posibles. Piensa qué ocurriría si.... Es la única manera de dominar la programación. Lo más importante, la clave de todo, es aprender a pensar. Es aprender a resolver problemas nuevos

Ejercicio 1

Escribe un programa que pida al usuario dos números enteros e imprima el mensaje "IGUALES" si son iguales y "DIFERENTES" si son distintos. Utiliza la instrucción beq para hacer la comparación. En esta animación se muestra cómo debe funcionar:

Ejercicio 2

Modificar el programa anterior para que funcione exactamente igual, pero usando la instrucción bne en vez de beq

Ejercicio 3

La operación de comparación de registros (beq) es muy útil para comprobar si un carácter es uno u otro. En este ejercicio la utilizaremos para comprobar si el carácter introducido por el usuario es el '1' ó el '2', y realizar un operación diferente según su valor

Escribe un programa que presente el siguiente menú, con dos opciones:

Menu de opciones
================
1. Incrementar contador
2. Exit

Opcion? :

Cuando el usuario introduce el carácter '1', se incrementará un contador y se imprimirá su valor en la consola. Estará inicializado a 0, por lo que la primera vez que se ejecute esta opción aparecerá:

Contador: 1

y se volverá a imprimir el menú. La segunda vez que se introduzca esta opción, obtendremos esto:

Contador: 2

y así sucesivamente. Después de incrementar el contador e imprimirlo en la consola, se volverá a sacar el menú

Si el usuario introduce el carácter '2', el programa terminará, imprimiendo la siguiente cadena:

EXIT: Terminando el programa

Si se introduce una opción no conocida, se mostrará el siguiente mensaje de error, y se volverá a mostrar el menú de opciones:

ERROR: Opcion invalida

En esta animación se muestra el programa en funcionamiento. En este ejemplo se solicita tres veces la opción 1, por lo que el contador se incrementará hasta 3, luego se introduce una opción incorrecta, y por último se termina, con la opción 2

Ejercicio 4

Escribe un programa que pida al usuario que introduzca un número entero (n), se impriman en pantalla los números de 1 hasta n, separados por una el carácter ','y termine. En esta animación se muestra un ejemplo de funcionamiento del programa. Se ejecuta dos veces. En la primera se introduce n=5, y en la segunda n=10:

Ejercicio 5

Escribe un programa que pida al usuario que introduzca una cadena, que calcule su longitud, la imprima en la consola y termine. El tamaño máximo de la cadena será de 1024 bytes. Ten en cuenta que el servicio READ_STRING introduce el carácter '\n' al final de la cadena. Usa este carácter para encontrar el final

En esta animación se muestra el programa en funcionamiento:

Ejercicio 6

Escribe un programa que pida al usuario dos números enteros (n1 y n2) y te indique en la pantalla cuál es la relación entre ellos, imprimiendo alguna de estas cadenas: "n1 < n2", "n1 == n2" o "n1 > n2"

En esta animación lo puedes ver en funcionamiento

Ejercicio 7

Escribe un programa que pida números enteros al usuario, los sume, imprima el total y termine. El número 0 se utiliza como terminador: al introducirse, el programa deja de pedir números y muestra el resultado de la suma

En esta animación se muestra un ejemplo de funcionamiento

Ejercicio 8

Escribe un programa para calcular todos los términos de la serie de Fibonacci hasta el N, donde N es una constante con el valor 10. Los dos primeros términos 0 y 1, se imprimen directamente (como la cadena "0,1,") y el resto los calcula el programa

Para un valor de la constante N = 10, la salida del programa es:

Ejercicio 9

Escribe un programa que pida al usuario una cadena (de tamaño máximo 1024 bytes) y cuente la cantidad de caracteres 'a' que hay en ella. Ese resultado lo debe mostrar en la consola

Esta es una animación con el funcionamiento del programa:

Ejercicio 10

Alguien ha escrito un programa en el simulador RARs, que al ensamblarlo produce este segmento de código:

1. La primera instrucción es un salto. ¿A qué dirección se realiza este salto?
2. ¿Cuál es, por tanto, la instrucción que se ejecuta tras el jal?
3. ¿Cuál sería el código fuente del programa ensamblador que al ensamblarlo produce ese segmento de código?
4. Comprobar que el código es correcto, ensamblándolo y viendo que efectivamente el segmento de código generado es igual al mostrado en la imagen

Notas para el profesor

• Título informal de la clase: "Tomando decisiones: Esta sí, esta no...."
• Una calculadora hace cálculos
• Un computador sabemos intuitivamente que "hace más " cosas que una calculadora
• ¿Qué diferencia a un computador de una calculadora? ¿Por qué un computador es más "potente" que una calculadora?
• Un computador tiene la potencia para ejecutar CUALQUIER ALGORITMO
• Para ejecutar cualquier algoritmo necesitamos lo siguiente:

1. Capacidad de hacer cálculos: + (a partir de la operación de suma se obtienen todas las demás)
2. Capacidad para tener variables: Almacenar en memoria y recuperar de ella
3. Entrada/salida (que para nosotros es lo mismo que acceder a "variables" especiales)
4. ¡TOMA DE DECISIONES! (IF)

• Resumiendo: Necesitamos (+, var, IF)
• En el riscv tenemos:

1. +: add, addi
2. var: lw, sw
3. IF: ?

• En esta sesión se ven todos los conceptos necesarios para entender cómo los procesadores implementan la instrucción IF, para así tomar decisiones y convertirse en máquinas de Turing (es decir, tener la suficiente potencia para ejecutar CUALQUIER ALGORITMO!)

Autores

• Katia Leal Algara
• Juan González-Gómez (Obijuan)

Licencia

Enlaces

• Documentación de la ABI del RISCV
• Simulador RARS, en github
• Universidad Rey Juan Carlos de Madrid
• Escuela Técnica Superior de Ingeniería de Telecomunicaciones (URJC)