C4-Structures de contrôle dans MIPS

CHAP4

Structures de contrôle dans MIPS

   Le paradigme de la programmation structurée repose sur le principe selon lequel tous les programmes peuvent être construits en utilisant seulement 3 types de structures de contrôle de programme. Ces structures sont:

• Séquences permettant aux programmes d'exécuter des instructions dans l'ordre.
• Les branches qui permettent aux programmes de sauter à d’autres points d’un programme.
• Boucles permettant à un programme d'exécuter un fragment de code plusieurs fois.

1 Instructions de branchements: 

• beq : Branchement si registre Rs est égal au registre Rt. Les contenus des registres Rs et Rt sont comparés. S’ils sont égaux, le programme saute à l’adresse associée à l’étiquette (label) par l’assembleur (le registre pc est modifié ). 

      Syntaxe : beq Rt, Rs, label

      Signification: SI (Rt = Rs) 

                          ALORS pc ← adresse associée à label

• bne : Branchement si registre Rs est différent du registre Rt. Les contenus des registres Rs et Rt sont comparés. S’ils sont différents, le programme saute à l’adresse associée à l’étiquette (label) par l’assembleur (le registre pc est modifié ). 

      Syntaxe : bne Rt, Rs, label  

      Signification: SI (Rt <> Rs) 

                          ALORS pc ← adresse associée à label 

• bgez : Branchement si registre Rs est supérieur ou égal à zéro. Si le contenu du registre Rs est supérieur ou égal à zéro, le programme saute à l’adresse associée à l’étiquette par l’assembleur (le registre pc est modifié ). 

      Syntaxe : bgez Rs, label

      Signification: SI (Rs >= 0) 

                          ALORS  pc ← adresse associée à label

• bgtz : Branchement si registre Rs est strictement supérieur à zéro. Si le contenu du registre Rs est strictement supérieur à zéro, le programme saute à l’adresse associée à l’étiquette par l’assembleur (le registre pc est modifié ). 

      Syntaxe : bgtz Rs, label
      Signification: SI (Rs > 0) 
                          ALORS  pc ← adresse associée à label

• blez : Branchement si registre Rs est inférieur ou égal à zéro. Si le contenu du registre Rs est inférieur ou égal à zéro, le programme saute à l’adresse associée à l’étiquette par l’assembleur (le registre pc est modifié ). 

      Syntaxe : blez Rs, label
      Signification: SI (Rs <= 0) 
                          ALORS  pc ← adresse associée à label

• bltz : Branchement si registre Rs est strictement inférieur à zéro. Si le contenu du registre Rs est strictement inférieur à zéro, le programme saute à l’adresse associée à l’étiquette par l’assembleur (le registre pc est modifié ). 

      Syntaxe : bltz Rs, label
      Signification: SI (Rs < 0) 
                          ALORS  pc ← adresse associée à label

• J : Saut inconditionnel immédiat. Le programme saute inconditionnellement à l’adresse associée à l’étiquette par l’assembleur (le registre pc est modifié ). 

      Syntaxe : j label
      Signification: pc ← adresse associée à label

• jal: Saut inconditionnel immédiat à un sous-programme. Le programme saute inconditionnel-lement à l’adresse associée au sous-programme et l'adresse de l'instruction suivante (pc+4) est sauvegardée dans $ra (le registre pc est modifié ). 

      Syntaxe : jal label_sous_programme
      Signification: $ra ← pc+4
                          pc ← adresse associée à label_sous_programme

• jr : Branchement inconditionnel registre Rs. Le programme saute à l’adresse contenue dans le registre Rs. (le registre pc est modifié souvent par $ra) 

      Syntaxe : jr Rs
      Signification: . pc ← Rs

• slt : (Set Less Than) Comparaison signée registre registre. Le contenu du registre Rs est comparé au contenu du registre Rt, les deux valeurs étant considérées comme des quantités signées. Si la valeur contenue dans Rs est inférieure à celle contenue dans Rt, alors Rd prend la valeur un, sinon il prend la valeur zéro.

      Syntaxe :slt Rd,Rs,Rt
      Signification: SI (Rs < Rt)
                         ALORS Rd ← 1
                         SINON Rd ← 0

• slti : Comparaison signée registre immédiat . Le contenu du registre Rs est comparé au contenu de la valeur immédiate sur 16 bits qui à subit une extension de signe.  Les deux valeurs étant considérées comme des quantités signées. Si la valeur contenue dans Rs est inférieure à celle de l’immédiat étendu,  alors Rd prend la valeur un, sinon il prend la valeur zéro.

      Syntaxe :slt Rt,Rs,Immediat
      Signification: SI (Rs < Immediat)
                               ALORS Rt ← 1
                               SINON Rt ← 0

• sltu : Comparaison non-signée registre registre. Le contenu du registre Rs  est comparé au contenu du registre Rt, les deux valeurs étant considérés comme des quantités non-signées. Si la valeur contenue dans Rs est inférieur à celle contenue dans Rt, alors Rd prend la valeur un, sinon il prend la valeur zéro. 

      Syntaxe :sltu Rd,Rs,Rt

      Signification: SI (Rs < Rt) et (Rs ≥ 0) et (Rt ≥ 0)

                             ALORS Rd ← 1

                             SINON Rd ← 0

• sltiu : Comparaison non-signée registre immédiat . Le contenu du registre Rs est comparé à la valeur immédiate sur 16 bits qui à subit une extension de signe. Les deux valeurs étant considérées comme des quantités non-signées, si la valeur contenue dans Rs est inférieur à celle de l’immédiat étendu, alors Rt prend la valeur un, sinon il prend la valeur zéro. 

      Syntaxe :sltiu Rt,Rs,Immediat

      Signification: SI (Rs < Immediat) et (Rs ≥ 0) et (Rt ≥ 0)

                              ALORS Rd ← 1
                              SINON Rd ← 0

• sle : (Set Less than or Equal) Comparaison signée registre registre. Le contenu du registre Rs est comparé au contenu du registre Rt, les deux valeurs étant considérées comme des quantités signées. Si la valeur contenue dans Rs est inférieure ou egale à celle contenue dans Rt, alors Rd prend la valeur un, sinon il prend la valeur zéro.

      Syntaxe :sle Rd,Rs,Rt
      Signification: SI (Rs ≤ Rt)
                             ALORS Rd ← 1
                             SINON Rd ← 0

      Il y a d'autres opérateurs de comparaison:

        sleu :  Comparaison non-signée registre registre (inférieur ou egale) . 

        seq : (Set EQual) Comparaison signée registre registre (Egal).

        sgt : Comparaison signée registre registre registre (Supérieur) . 

        sgtu : Comparaison non-signée registre registre (Supérieur) . 

        sge : (Set Greater than or Equal ) Comparaison signée registre registre (Supérieur ou Egal).

        sgeu : Comparaison non-signée registre registre (Supérieur ) .

        sne : (Set Not Equal) Comparaison signée registre registre (Non Egal).

2 Instructions SI simples 

    Cette section commencera par un petit exemple d'une instruction SI :
SI (num> 0) ALORS
{
     Ecrire("Le nombre est positif")
}

    L'instruction (num> 0) est une instruction dans laquelle l'opérateur > renvoie une valeur logique (booléenne) à évaluer. Cela pourrait être plus facile si la déclaration était écrite comme suit, ce qui a exactement la même signification.

 BOOLÉEN drapeau= (num> 0);
 SI (drapeau) ALORS ...

    Le programme en langage assembleur du fragment de code ci-dessus est présenté comme suit:
          .texte
          # si (num> 0)
          lw $t0, num
          sgt $t1, $t0, $ zéro    # $t1 est le drapeau booléen (num> 0)
          beqz $t1, fin_si      # le bloc de code est exécute si
                                       # si le drapeau  est vrai, ignoré si faux.
          # {
          #      Ecrire("Le nombre est positif")
          la $a0, Msg

          li $v0, 4
          syscall
          # }
fin_si:
          # Suite du programme ...
          .data
num:   .word 5
Msg:  .asciiz "Le nombre est positif"

2.1 Instruction SI simple avec conditions logiques complexes

    Cette  instruction SI est composée de plusieurs conditions :

SI ((x > 0 && ((x%2) == 0))   # i.e:  x > 0 et pair?

   Le moyen le plus simple de résoudre ce problème est de réduire la condition logique complexe en une seule équation. Donc,  l'instruction IF complexe ci-dessus serait traduite en l'équivalent du fragment de code suivant:

BOOLÉEN drapeau = ((x > 0) && ((x%2) == 0))

SI (drapeau) ALORS ...

     Ce fragment de code est facilement traduit en langage assembleur comme suit:

lw $t0, x

sgt $t1, t0$, zéro$

rem $t2, $ t0, 2
seq  $t2, $t2, $zero

and t1$, t1$, t2$

beqz $t1, fin_si

2.2 Instructions SI-SINON

  Si la condition est vraie, le premier bloc est exécuté, sinon le deuxième bloc est exécuté. Un simple fragment de code illustrant ce point est présenté ci-dessous:

SI (num> 0) ALORS

{

    Ecrire("Le nombre est positif")

}

SINON

{

    Ecrire("Le nombre est negatif")

}

     Ce code  imprime si le nombre est positif ou négatif. Le but ici est de montrer comment traduire une instruction Si-SINON en langage assembleur. L'instruction Si-Sinon est traduite comme suit.

1) Implémenter la partie conditionnelle de l'instruction

2) Ajoutez deux étiquettes au programme, une pour le SINON et une pour la fin du SI. Le beqz doit être inséré après l'évaluation de la condition pour passer à l'étiquette SINON.

3) À la fin du bloc SI, branchez-vous autour du bloc SINON en utilisant une instruction de branche inconditionnelle vers FIN_SI. Vous avez maintenant la structure de base de l'instruction SI et votre code doit ressembler à ceci:

           lw $t0, num

           sgt $t1, $t0, $zero

           beqz $t1, SINON

           #le bloc SI

           b FIN_SI

SINON:

           #le bloc SINON

FIN_SI:

4) Une fois que la structure de l'instruction SI-SINON est en place, vous devez insérer le code du bloc dans la structure. Ceci termine la traduction de l'instruction SI-SINON. vous obtiendrez un code semblable à celui-ci:

            .text

             lw $t0, num

             sgt $t1, $t0, $zero

             beqz $t1, SINON

#SI bloc

             li $v0, 4

             la $a0, MesPos

             syscall

             b FIN_SI

#SINON bloc

SINON:

             li $v0, 4

             la $a0, MesNeg

             syscall

FIN_SI:

# Suite du programme ...

             li $v0, 10

             syscall

             .data

num: .word -5

MesPos: .asciiz "Le nombre est positif"

MesNeg: .asciiz "Le nombre est negatif"

2.3 Instructions SI-SinonSI-SINON

  Un autre type de branchement à présenter dans ce cours permet au programmeur de choisir parmi plusieurs options.Il est implémenté sous la forme d'une instruction SI-SinonSI-SINON. Les instructions SI et SinonSI contiendront une condition pour décider si elles seront exécutées ou non. Le SINON sera automatiquement choisi si aucune condition n'est vraie.
  Pour introduire la déclaration SI-SinonSI-SINON, le programme suivant qui traduit un nombre de points (de 100  à 0) en une lettre alphabétique (de A à F ) est mise en œuvre.L'algorithme suivant montre la logique de cette instruction SI-SinonSI-SINON.

SI (note> 100) || note< 0) ALORS
{
            Ecrire("La note doit être comprise entre  0 et 100")
}
SinonSI(note>= 90) ALORS
{
            Ecrire("La note est A")
}
SinonSI(note>= 80) ALORS
{
            Ecrire("La note est B")
}
SinonSI(note>= 70) ALORS
{
            Ecrire("La note est C")
}
SinonSI(note>= 60) ALORS
{
            Ecrire("La note est D")
}
SINON
{
            Ecrire("La note est F")
}

   Les étudiants et les programmeurs sont vivement encouragés à implémenter la logique algorithmique de cette manière. Les étudiants qui souhaitent implémenter le code de manière totalement avancée, où les instructions sont générées telles qu’elles existent dans le programme, se trouveront complètement dépassées et rateront les conditions internes et d’arrêt, en particulier lorsque des blocs imbriqués contenant une logique imbriquée seront utilisés plus tard. L'instruction SI-SinonSI-SINON est traduite comme suit:

           .text
#SI bloc
           lw $s0, note
           slti $t1, $s0, 0
           sgt $t2, $s0, 100
           or $t1, $t1, $t2
           beqz $t1, note_A
#Erreur bloc
           li $v0, 4
           la $a0, MsgErr
           syscall
           b fin_si
note_A:
           sge $t1, $s0, 90
           beqz $t1, note_B
           li $v0, 4
           la $a0, MsgA
           syscall
           b fin_si
note_B:
           sge $t1, $s0, 80
           beqz $t1, note_C
           li $v0, 4
           la $a0, MsgB
           syscall
           b fin_si
note_C:
           sge $t1, $s0, 70
           beqz $t1, note_D
           li $v0, 4
           la $a0, MsgC
           syscall
           b fin_si
note_D:
           sge $t1, $s0, 60
           beqz $t1, sinon
           li $v0, 4
           la $a0, MsgD
           syscall
           b fin_si
sinon:
           li $v0, 4
           la $a0, MsgF
           syscall
           b fin_si
fin_si:
           li $v0, 10
           syscall

           .data
note:      .word 70
MsgErr: .asciiz "La note doit être comprise entre  0 et 100"
MsgA:   .asciiz "La note est A"
MsgB:    asciiz "La note est B"
MsgC:   .asciiz "La note est C"
MsgD:   .asciiz "La note est D"
MsgF:   .asciiz "La note est F"

3 Les boucles (répétitions)

    La notion de boucle ou répétition est une des notions fondamentales de la programmation. En effet, il existe  deux principales structures de boucles: La boucle avec condition et  La boucle avec  intervalle. Pour chacune de ces structures, nous présentons un exemple afin d’examiner les différentes techniques de programmation associées aux structures répétitives.

3.1 Boucle avec condition

    L’objectif de cet exemple est d’écrire une boucle avec condition  (TANT QUE) qui  réalise la saisie d’un entier au clavier et l’affiche à l’écran  jusqu’à ce que l’utilisateur saisie la valeur -1 (pour quitter la boucle).

num ← 0

TANT QUE (num != -1) FAIRE

{

      Ecrire("Enter un entier, ou -1 pour sortir ?")

      Lire (num)

      Ecrire("Vous avez taper :" , num)

}

   La boucle tant que est traduite en MIPS par la construction suivante :

            .text

# num = 0

            lw $s0, num

# Tant que (num != -1) faire{

debut_boucle:

            sne $t1, $s0, -1

            beqz $t1, fin_boucle

# {bloc d’instructions à l’intérieur de la boucle

            li $v0, 4                #Ecrire("Enter un entier, ou -1 pour sortir ?")

            la $a0, Msg1

            syscall

            li $v0, 5                #Lire (num)

            syscall

            move $s0, $v0

            sw $s0, num

            li $v0, 4                #Ecrire("Vous avez taper :")

            la $a0, Msg2

            syscall

            li $v0, 1                 #Ecrire(num)

            move $a0, $s0

            syscall

            b debut_boucle
# } fin bloc d’instructions 

fin_boucle:

             li $v0, 10
             syscall
             .data

num:     .word 0

Msg1:   .asciiz "\n Enter un entier, ou -1 pour sortir ?"

Msg2:   .asciiz "\n Vous avez taper :"

3.2 Boucle avec intervalle

    La boucle avec intervalle (POUR..) permet d’écrire des boucles dont on connaît à l’avance le nombre d’itérations (de tours) à exécuter. Elle est équivalente à l’instruction TANT QUE mais est plus simple à écrire. L’algorithme de exemple suivant fait la somme S des valeurs entières de 0 à N.

Ecrire("Entrer N ?")

Lire (N)

S ← 0

Pour (i← 0 , i<= N, i++) Faire

{

      S ← S + i

}

Ecrire("Somme =" , S)

   La boucle POUR est traduite en MIPS par la construction suivante :

             .text

# Ecrire("Entrer N ?")

              li $v0, 4

              la $a0, Msg1

              syscall

# Lire (N)

              li $v0, 5

              syscall

              sw $v0, N

              move $s1, $v0

#   i ← 0

              li $s0, 0

#  S ← 0 

              li $s2, 0

debut_boucle:

             sle $t1, $s0, $s1

             beqz $t1, fin_boucle:

# code bloc

              add $s2, $s2, $s0

             sw $s2, S

#incrémenter le compteur  i

             addi $s0, $s0, 1

             sw $s0, i

             b debut_boucle

fin_boucle:

#  fin bloc d’instructions et Suite du programme ...

             li $v0, 4

             la $a0, Msg2

             syscall

             li $v0, 1

             move $a0, $s2

             syscall

             li $v0, 10
             syscall

             .data

N:         .word 0

S:         .word 0

i:           .word 0

Msg1:   .asciiz "\n Enter N ?"

Msg2:   .asciiz "\n Somme= "

4 Blocs de code imbriqués

    Il est courant dans la plupart des algorithmes d'avoir des blocs de code imbriqués. Un exemple simple serait un programme qui calcule la somme des valeurs de 0 à Num, où l'utilisateur entre des valeurs pour Num jusqu'à ce qu’il entre un 0. De plus, l'entrée impose que seules les valeurs positives de Num soient prises en compte, et toute valeur négative de Num générera une erreur.

     Cet algorithme peut être exécuté dans n’importe quel langage si le lecteur veut s’assurer que cela fonctionne :

Variables Num , total , i : Entier

Num ¬ 1

Tant que (Num != 0) Faire

       Ecrire ("Entrez un entier, 0 pour arrêter ?")

       Lire(Num)

       Si (Num <= -1) Alors 

               Ecrire ("Entrée négative est invalide !");

       Sinon

               total ¬ 0

               Pour ( i ¬ 0; i <= Num; i++)  Faire

                       total = total + i;

               Fin_Pour

               Ecrire ("La somme est :" , total);

       Fin_Si

Fin_Tant_que 

      Cependant, la traduction de cet algorithme en assembleur est un processus relativement simple, comme le montre le code MIPS ci-dessous.

             .data

Num:    .word 0

total:     .word 0

i:           .word 0

prompt: .asciiz "\n Entrez la  valeur de Num, 0 pour arrêter ?"

erreur:  .asciiz "\n Entrée négative est invalide !"

result:   .asciiz "\n La somme est :"

             .text

main :

             li $s0, 1     

             sw $s0, Num    # Num ¬ 1

debut_tant_que: 

             sne $t1, $s0, $zero    #Tant que (Num != 0)

             beqz $t1, fin_tant_que

# Ecrire ("Entrez la  valeur de Num, 0 pour arrêter ?")

             la $a0, prompt

             li $v0, 4

              syscall

              li $v0, 5    #  Lire(Num)

              syscall

             move $s0, $v0

             sw $s0, Num

debut_si : # Si (Num <= -1)

             sle $t1, $s0, -1

             beqz $t1, sinon

alors :   la $a0, erreur

             li $v0, 4

              syscall

             b fin_si

sinon:

             li $s1, 0    # initialiser i¬0

             li $s2, 0    # initialiser total¬0

debut_pour:

             sle $t1, $s1, $s0     # i <= Num

             beqz $t1, fin_pour

             add $s2, $s2, $s1 # total = total + i

             sw $s2, total

             addi $s1, $s1, 1 # i++

             sw $s1, i

             b debut_pour

fin_pour:

             la $a0, result    # Ecrire ("La somme est :");

             li $v0, 4

              syscall

             move $a0, $s2  # Ecrire (total);

             li $v0, 1

              syscall

fin_si:

             b debut_tant_que

fin_tant_que:

             li $v0, 10
             syscall