Sesión 4

Implementando estructuras de control en MIPS

4.1 Objetivo General

Cubrir la implementación de estructuras de control usando el conjunto de instrucciones del MIPS

4.2 Objetivos específicos

Al terminar esta sesión de laboratorio:

2.3 Estructuras de control

Lo que distingue a las computadoras de las calculadoras simples es la habilidad de tomar decisiones. Basandose en los datos de entrada y en los valores que van calculando, las computadoras pueden ejecutar distintos grupos de instrucciones.

En los lenguajes de programación de más alto nivel la toma de decisiones se representa comúnmente a través de los enunciados (statements) if combinados, a veces, con enunciados goto.

2.4 El enunciado if en MIPS

MIPS incluye instrucciones para la toma de decisiones similares a un anunciado if con un goto: la instrucción

beq $8, $9, L1

significa "ir a(seguir ejecutando desde) la dirección etiquetada L1 si el valor en el registro $8 es igual al valor en el registro $9". beq significa branch equal (bifurca si es igual).

Ejemplo 4.1

En el siguiente segmento de código en C, f, g, h, i y j son variables:

if( i == j) goto L1;
f = g + h;
L1:      f = f - i;

Asumiendo que las cinco variables corresponden a los registros del $16 al $20, el código MIPS compilado es:

beq $19, $20, L1
add $16, $17, $18
L1:   sub $16, $16, $19

Las instrucciones pueden etiquetarse porque, dado que los porgramas también se almacenan en memoria, tienen asociada una dirección.

Ejemplo 4.2

Los compiladores frecuentemente crean bifurcaciones y etiquetas aún cuando no aparezcan en el código original. Usando las mismas variables y registros del ejemplo anterior, el codigo en C:

if( i == j)
   f = g + h;
else
   f = f - i;

se traduce a MIPS como:

bne $19, $20, Else
add $16, $17, $18
j Exit
Else: sub $16, $16, $19
Exit:

En el ejemplo anterior, la segunda instrucción MIPS realiza la parte "then" del if y la cuarta corresponde al "else". Para evitar la cuarta instrucción cuando i == j debemos "saltar" hasta la etiqueta Exit, lo cual nos lleva a una clase de bifurcación no condicional que instruye a la máquina para que siempre bifurque hacia otra dirección. Para distinguir entre bifurcaciones condicionales y no condicionales, en MIPS esta última clase se denomina jump (salto), y se abrevia como j.

En la siguiente tabla se resumen las instruciones de bifurcación y salto.

Instrucción
Ejemplo
Significado
Comentarios
branch on equal beq $1, $2, L if($1 == $2)goto L Prueba de igualda y bifurcación
branch on not equal bne $1, $2, L if($1 != $2) goto L Prueba de desigualdad y bifurcación
jump j 1000 goto 1000 Salto a la dirección destino
jump register j $31 goto $31 Para enunciados switch

4.5 Ciclos en MIPS

La toma de decisiones es importante tanto para escoger entre dos alternativas (como en los enunciados if) como para iterar un cálculo (como en los ciclos). De hecho, las mismas instrucciones de ensamblador se usan como piezas fundamentales en ambos casos.

Ejemplo 4.3

Este es un ciclo en C:

Loop: g = g + A[i];
i = i + j;
if (i != h) goto Loop;

Supongamos que A es un arreglo de 100 palabras y que el compilador asocia las variables g, h, i y j con los registros del $17 al $20, respectivamente. Supongamos que el arreglo comienza en Astart y que en el registro $10 se encuentra almacenado un 4.

El código MIPS correspondiente a este segmento en C es:

Loop: mult $9, $9, $10
          lw    $8, Astart($9)
          add $17, $17, $8
          add $19, $19, $20
          bne $19, $18, Loop

Como en el cuerpo de ciclos se modifica el valor de i, debemos multiplicar este valor por 4 en cada iteración. En una sesión posterior de laboratorio revisaremos la instrucción mult.

Ejemplo 4.4

Por supuesto, los programadores acostumbran no escribir ciclos con gotos, de manera que es tarea de los compiladores el traducir ciclos tradicionales a la versión apropiada del lenguaje ensamblador. El segmento de código en C

while ( A[i] == k)
          i = i + j;

se traduce a MIPS como

Loop: mult $9, $9, $10
          lw $8, $Astart($9)
          bne $8, $21, Exit
          add $19, $19, $20
          j Loop
Exit:

Bajo el supuesto de que i, j y k corresponden a los registros, $19, $20 y $21, de que el arreglo A empieza en la dirección Astart, y de que el registro $10 contiene un 4.

4.6 El enunciado switch en MIPS

La mayoria de los lenguajes de programación tienen un enunciado case o switch que permite seleccionar una de muchas alternativas dependiendo de un sólo valor. Una manera de implementar un switch es como una secuencia de if-then-else. Sin embargo, en algunas ocasiones las alternativas pueden ser codificadas eficiententemente como una tabla de alternativas de secuencias de instrucciones, de manera que el programador sólo necesite indexar la tabla de direcciones de salto (jump address table) y saltar luego a la secuencia apropiada. Para tal efecto, en MIPS se incluye la instrucción jr (jump register), que representa un salto incondicional a la dirección contenida en el registro que dicha instrucción tiene por argumento.

Ejemplo 4.5

El siguiente bloque de código en Java escoge entre cuatro alternativas dependiendo de si el valor de k es 0, 1, 2 ó 3.

switch(k){
          case 0: f = i + j; break;
          case 1: f = g+ h; break;
          case 2: f = g - h; break;
          case 3: f = i -j; break;
}

Suponiendo que las seis variables f a k corresponde a los seis registros $16 a $21, que en el registro $10 contiene un 4, y que las cuatro palabras en memoria comenzando en la dirección JumpTable tienen las direcciones correspondientes a las etiquetas L0, L1, L2 y L3 respectivamente. El código MIPS correspondiente es

Loop: mult $9, $19, $21
          lw    $8, JumpTable($9)
          jr     $8
L0:     add  $16, $19, $20
          j       Exit
L1:     add  $16, $17, $18
          j       Exit
L2:     sub  $16, $17, $18
          j       Exit
L3:     sub  $16, $19, $20
Exit:

4.5 Preguntas y ejercicios de revisión

  1. Existen seis condiciones relativas entre los valores de dos registros. Suponiendo que la variable i corresponde al registro $19 y que la variable j corresponde al $20, ¿Cómo se traducen a ensamblador del MIPS los siguientes enunciados en C?
    (a) if ( i == j ) goto L1;
    (b) if ( i != j ) goto L1;
    (c) if ( i <j ) goto L1;
    (d) if ( i <= j ) goto L1;
    (e) if ( i > j ) goto L1;
    (f) if ( i >= j ) goto L1;
  2. Las instrucciones slt, beq y bne se usan en MIPS, junto con el valor constante del registro 0, para crear todas las condiciones relativas de la pregunta anterior. Averigua el significado de la instrucción slt y explica cómo implementarias la pseudoinstrucción blt (branch on less than).
  3. La instrucción beq $2, $3, L1 compara el contenido de los registros $2 y $3 y bifurca hacia L1 sis on iguales. Desafortunadamente no existe ninguna instrucción para comparar $2 con un valor inmediato como 14. Escribe una secuencia de instrucciones de MIPS que bifurquen hacia L1 si $2 es igual a 14. Nota: las respuestas con más de dos instrucciones se considerarán erroneas.
  4. La traducción del segmento de C del ejemplo 4.4 utiliza tanto una bifurcación condicional como una no condicional durante cada iteración. Sólo compiladores muy pobres producen código con este gasto en saltos. Reescribe el código en ensamblador de manera que se use sólo un tipo de bifurcación durante cada iteración. Si el número de iteraciones sobre el ciclo es 10, ¿cuál es el número de instrucciones ejecutadas antes y después de la optimización?
  5. El siguiente programa trata de copiar palabras desde la dirección en el registro $4 a la dirección en el registro $5, contando el número de palabras copiadas en el registro $2. El programa termina de copiar cuando encuentra una palabra igual a 0. No es necesario preservar el contenido de los registros $3, $4 y $5. La palabra nula (igual a 0) debe copiarse pero no contarse.
    Loop: lw    $3, 0($4) # lee la siguiente palabra de la fuente
              addi $2, $2, 1 #incrementa el número de palabras contadas
              sw   $3, 0($5) #escribe en el destino
              addi $4, $4, 1 #avanza el apuntador a la siguiente fuente
              addi $5, $5, 1 #avanza el apuntador al siguiente destino
              bne  $3, $0, Loop #cicla si la palabra copiada != 0
    Hay varios bugs en este programa MIPS. Corrígelos y escribe la versión libre de errore del programa.
    Cuando en una sesión de laboratorio se requiera realizar un programa y/o reporte, éste deberá entregarse por e-mail. El mensaje electrónico deberá contener un archivo .tar.z o .tgz( o en su defecto .zip) con los programas incluidos y/o el reporte de la sesión (si es necesario). Al expandir el archivo tgz, deberá contener un directorio llamado como el login de tu cuenta, luego un subdirectorio llamado como la sesión (por ejemplo sesion1, o sesion2), finalmente, los programas y/o reportes a entregar. Los reportes deberán ser enviados en formato postscript (ps) o en archivo PDF, cualquier otro formato no será recibido. Y algo muy importante, los programas y/o reportes deberán de entregarse en la fecha indicada, no se recibirán después.
    Volver a la Introducción