Laboratori 3: Traducció de programes
Lliuraments
Cal lliurar les respostes als exercicis següents al campus virtual abans de l’inici de la sessió de laboratori:
| Exercici | Nom i format del fitxer |
|---|---|
| Exercici 30.1 | s3_1_1.s |
| Exercici 30.2 | s3_2_1.s |
| Exercici 30.3 | s3_3_1.s |
| Exercici 30.4 | s3_4_1.s |
| Exercici 30.5 | s3_4_2.md i s3_4_2.s |
| Exercici 30.6 | s3_5_1.s |
Lectura prèvia
Abans de fer la sessió, cal haver llegit i entès els continguts següents:
| Concepte | On trobar-ho |
|---|---|
| Traducció literal C→RV32I | EC 3.1 |
Desplaçaments lògics (sll, srl, slli, srli) |
RISC-V 3.1 |
Desplaçament aritmètic (sra, srai) |
RISC-V 3.2 |
Operacions lògiques bit a bit (and, or, xor, not) |
RISC-V 3.3, RISC-V 3.4 |
Instruccions de comparació (slt, sltu, slti, sltiu) |
RISC-V 3.5 |
Salts condicionals (beq, bne, blt, bge, bltu, bgeu; pseudo: bgt, ble, beqz) |
RISC-V 3.7, RISC-V 3.8, RISC-V 3.9 |
Salts incondicionals (jal, j, ret) |
RISC-V 3.11, RISC-V 3.12, RISC-V 3.14 |
Traducció d’if-then-else |
Secció 3.6 |
Traducció de while i for |
Secció 3.7 |
Crida i retorn de subrutines (ra) |
Secció 3.9.1 |
Pas de paràmetres i retorn de resultats (a0–a7) |
Secció 3.9.2, RISC-V 3.17 |
Variables locals i bloc d’activació (sp) |
Secció 3.9.3, RISC-V 3.18 |
| Subrutines multinivell: registres temporals i segurs | Secció 3.9.4, RISC-V 3.22 |
30.1 Operacions lògiques i desplaçaments
Les operacions de desplaçament i lògiques bit a bit permeten construir màscares i manipular bits individuals. En aquest exercici es combinen per construir una màscara de bits de mida variable en temps d’execució (RISC-V 3.1, RISC-V 3.3).
Exercici 30.1 (s3_1_1.s) Donats dos enters X (\(0 \le X \le 31\)) i Y als registres s0 i s1 respectivament, escriviu un fragment de codi RV32I que complementi els X bits de menys pes de Y i deixi el resultat a s1. No podeu usar instruccions de salt ni de comparació, i el fragment ha de tenir com a màxim 4 instruccions.
Indicació: la sentència C equivalent és:
on ^ és la XOR bit a bit i 1 << X desplaça el valor 1 exactament X posicions a l’esquerra.
Comproveu que, afegint li s0, 5 i li s1, 0x12345678 abans del fragment, s1 acaba valent 0x12345667.
Solució 30.1.
s3_1_1.s
La clau és construir la màscara en temps d’execució: 1 << X produeix un 1 a la posició X i zeros a la resta; restar-li 1 posa a 1 tots els bits de posicions 0 a X-1. El XOR final complementa exactament aquells bits.
30.2 Sentències condicionals
Una sentència if-then-else imbricada es tradueix aplicant el patró de Secció 3.6 de manera recursiva: cada if interior es tracta com una sentència del cos de l’else exterior. L’avaluació tardana (lazy) de && i || (Essencial 3.5, Secció 3.6.2) s’implementa encadenant salts condicionals sense avaluar la segona condició quan la primera ja determina el resultat.
Exercici 30.2 (s3_2_1.s) Traduïu a RV32I el programa C del Codi 30.1. Les variables globals num i result s’han de declarar a la secció .data. Tots els temporals van a registres t.
num.
El programa ha de respectar l’avaluació tardana de && i || (Essencial 3.5). Comproveu que, per als valors 'm', 'Z', ' ', '!' i '7' de num (codis ASCII: 0x6D, 0x5A, 0x20, 0x21, 0x37), result val, respectivament, 0x6D, 0x5A, 0, 0 i -1 (0xFFFFFFFF).
Solució 30.2.
s3_2_1.s
.data
num: .byte '7'
result: .word 0
.text
la t1, num
lb t0, 0(t1) # t0 = num
# if (num >= 'a' && num <= 'z')
li t2, 'a'
blt t0, t2, comp_maj
li t2, 'z'
bgt t0, t2, comp_maj
j es_alfa
comp_maj:
# || (num >= 'A' && num <= 'Z')
li t2, 'A'
blt t0, t2, comp_esp
li t2, 'Z'
bgt t0, t2, comp_esp
es_alfa:
la t1, result
sw t0, 0(t1) # result = num
j fi
comp_esp:
# else if (num == ' ' || num == '!')
li t2, ' '
beq t0, t2, es_esp # primer operand || cert → lazy
li t2, '!'
bne t0, t2, es_altre
es_esp:
la t1, result
sw zero, 0(t1) # result = 0
j fi
es_altre:
la t1, result
li t2, -1
sw t2, 0(t1) # result = -1
fi:
li a7, 93
li a0, 0
ecallLa primera branca del || exterior usa dos && encadenats (dos rangs); la segona branca usa un || simple entre dues igualtats. En el || intern (' ' o '!'), el salt a es_esp quan la primera condició és certa implementa l’avaluació tardana: si num == ' ', no s’avalua la comparació amb '!'.
30.3 Bucles
El patró de traducció d’un while (Secció 3.7) consisteix a avaluar la condició al principi de cada iteració i saltar al final del bucle si és falsa. El recorregut d’una cadena de caràcters fins al sentinella '\0' és un cas particular molt freqüent: la condició del bucle és que el caràcter actual sigui diferent de zero.
Exercici 30.3 (s3_3_1.s) La cadena de caràcters w conté 31 dígits decimals seguits del sentinella '\0'. Escriviu un programa RV32I que compti quantes vegades apareix el caràcter '4' a w i deixi el resultat al registre s0.
C
Nota: useu un punter (t1) en lloc d’un índex per recórrer la cadena: és un patró que reapareixerà, amb variacions, a l’exercici de subrutines.
Comproveu que, en acabar, s0 val 12.
Solució 30.3.
s3_3_1.s
.data
w: .asciz "4444185720444938167204449251044"
.text
la t1, w # t1 = punter al caràcter actual
li s0, 0 # s0 = comptador d'aparicions de '4'
li t2, '4' # t2 = caràcter a cercar
while:
lb t0, 0(t1) # t0 = w[i]
beqz t0, fiwhile # si w[i] == '\0', fi del bucle
bne t0, t2, seguent # si w[i] != '4', no comptem
addi s0, s0, 1 # s0++
seguent:
addi t1, t1, 1 # avança el punter
j while
fiwhile:
li a7, 93
li a0, 0
ecallEl patró fonamental és: llegir el caràcter actual amb lb, comprovar el sentinella amb beqz, processar si escau, i avançar el punter amb addi t1, t1, 1. Aquest mateix esquelet apareixerà dins de moda a l’exercici de subrutines.
30.4 Subrutines
En una subrutina multinivell, els valors generats abans d’una crida i usats després s’han d’assignar a registres segurs (s0–s11); la subrutina ha de desar i restaurar aquests registres i ra (Secció 3.9.4, Essencial 3.11). Les variables locals estructurades (vectors) s’han d’allotjar al bloc d’activació (stack frame, BA) de la subrutina (RISC-V 3.20). Els dos exercicis d’aquesta secció s’han de fer en ordre: el segon reutilitza la traducció del primer.
Exercici 30.4 (s3_4_1.s) La funció update rep un punter a l’histograma h, l’índex i del caràcter actual i l’índex imax del caràcter més freqüent fins ara. Incrementa h[i] i retorna i si ara és el més freqüent, o imax en cas contrari.
C
Traduïu update a RV32I. Tingueu en compte:
- És una subrutina uninivell: no cal desar
ra. - Determineu quins valors, si n’hi ha, cal assignar a registres segurs abans d’escriure cap instrucció.
- El resultat es retorna a
a0(RISC-V 3.17).
Solució 30.4. Anàlisi de registres segurs. update és uninivell: no hi ha cap crida, de manera que cap valor travessa una frontera de crida. Tots els temporals van a registres t; no cal cap registre s. El BA és buit.
s3_4_1.s
update:
# update(int *h, char i, char imax)
# a0 = h, a1 = i, a2 = imax
# h[i]++
slli t0, a1, 2 # t0 = i * 4
add t0, a0, t0 # t0 = &h[i]
lw t1, 0(t0)
addi t1, t1, 1
sw t1, 0(t0) # h[i]++
# if (h[i] > h[imax]) return i; else return imax
slli t2, a2, 2 # t2 = imax * 4
add t2, a0, t2 # t2 = &h[imax]
lw t2, 0(t2) # t2 = h[imax]
ble t1, t2, ret_imax
mv a0, a1 # return i
ret
ret_imax:
mv a0, a2 # return imax
retCom que update és uninivell, els paràmetres a0–a2 es poden usar directament durant tot el cos sense risc de sobreescriptura per cap crida. No cal moure’ls a registres segurs.
Exercici 30.5 (s3_4_2.md i s3_4_2.s) La funció moda recorre la cadena vec de num caràcters, construeix un histograma local histo[10] i, per a cada caràcter, crida update (traduïda a Solució 30.4) per actualitzar el dígit més freqüent.
C
char w[32] = "4444185720444938167204449251044";
char resultat;
char moda(char *vec, int num) {
int k, histo[10];
char max;
for (k = 0; k < 10; k++)
histo[k] = 0;
max = '0';
for (k = 0; k < num; k++)
max = '0' + update(histo, vec[k] - '0', max - '0');
return max;
}
void main() {
resultat = moda(w, 31);
}Traduïu moda i el programa principal a RV32I, al fitxer s3_4_2.s. Abans d’escriure cap instrucció, responeu al fitxer s3_4_2.md:
- Identifiqueu quines dades es generen abans de la crida a
updatei s’usen després (Secció 3.9.4). Assigneu-les a registres segurs. - Dibuixeu el bloc d’activació de
modaamb els desplaçaments de cada element.
Comproveu que al final de l’execució la variable global resultat conté el caràcter '4'.
Nexe amb Exercici 30.3: el segon for de moda segueix el mateix patró de recorregut seqüencial caràcter a caràcter que heu fet servir a l’exercici de bucles (ara amb índex explícit en lloc de punter). Identifiqueu on apareix.
Solució 30.5. Pas 1. Registres segurs de moda.
Dades generades abans de la crida a update i usades després: histo (adreça base = sp; derivable en tot moment, no cal registre), vec → s0, num → s1, k → s2, max → s3. Cal desar també ra.
Pas 2. Bloc d’activació de moda (Figura 30.1).
![Bloc d'activació de 60 bytes, d'adreces baixes (sp) a altes: histo (int[10], 40 bytes, desplaçament +0) i els registres desats s0 (+40), s1 (+44), s2 (+48), s3 (+52) i ra (+56).](../auto_figs/L3_ba_moda__BA_light.svg)
![Bloc d'activació de 60 bytes, d'adreces baixes (sp) a altes: histo (int[10], 40 bytes, desplaçament +0) i els registres desats s0 (+40), s1 (+44), s2 (+48), s3 (+52) i ra (+56).](../auto_figs/L3_ba_moda__BA_dark.svg)
moda: el vector histo al desplaçament +0 i els registres desats s0, s1, s2, s3 i ra als desplaçaments +40, +44, +48, +52 i +56.
Mida del BA: 60 bytes (EC 3.7).
s3_4_2.s
.data
w: .asciz "4444185720444938167204449251044"
resultat: .byte 0
.text
la a0, w
li a1, 31
jal ra, moda
la t0, resultat
sb a0, 0(t0)
li a7, 93
li a0, 0
ecall
# update: vegeu la solució de s3_4_1.s (inseriu el codi aquí)
moda:
# moda(char *vec, int num) — a0 = vec, a1 = num
# pròleg
addi sp, sp, -60
sw s0, 40(sp)
sw s1, 44(sp)
sw s2, 48(sp)
sw s3, 52(sp)
sw ra, 56(sp)
mv s0, a0 # s0 = vec
mv s1, a1 # s1 = num
# for (k=0; k<10; k++) histo[k] = 0
li s2, 0 # k = 0
li t0, 10
for1:
bge s2, t0, fifor1
slli t1, s2, 2 # t1 = k * 4
add t1, sp, t1 # t1 = &histo[k]
sw zero, 0(t1)
addi s2, s2, 1
j for1
fifor1:
# max = '0'
li s3, '0'
# for (k=0; k<num; k++) ← mateix patró que s3_3_1.s
li s2, 0 # k = 0
for2:
bge s2, s1, fifor2
# vec[k] → t0; a1 = vec[k] - '0'
add t0, s0, s2 # t0 = &vec[k]
lb t0, 0(t0) # t0 = vec[k]
li t1, '0'
sub a1, t0, t1 # a1 = vec[k] - '0'
# a2 = max - '0'
sub a2, s3, t1 # a2 = max - '0'
# a0 = &histo
mv a0, sp
jal ra, update
# max = '0' + resultat
li t1, '0'
add s3, t1, a0 # s3 = '0' + update(...)
addi s2, s2, 1 # k++
j for2
fifor2:
mv a0, s3 # return max
# epíleg
lw s0, 40(sp)
lw s1, 44(sp)
lw s2, 48(sp)
lw s3, 52(sp)
lw ra, 56(sp)
addi sp, sp, 60
retEl patró de Exercici 30.3 reapareix al segon for: add t0, s0, s2 calcula l’adreça del caràcter actual (equivalent a avançar el punter), lb t0, 0(t0) el llegeix, i bge s2, s1, fifor2 comprova la condició de fi (aquí amb comptador explícit en lloc de sentinella, perquè num és conegut). El resultat esperat a resultat és '4' (0x34).
30.5 Depuració de codi
La depuració és el procés d’identificar i corregir errors en un programa. En assemblador, els errors més freqüents són confusions entre registres, errors d’adreçament i una gestió incorrecta del bloc d’activació. En aquest exercici es practiquen tots tres.
Exercici 30.6 (s3_5_1.s) El programa del Codi 30.2 declara el vector global alfabet amb les lletres majúscules de l’A a la Z i una cadena de caràcters d’entrada w1. La funció codifica recorre w1 caràcter a caràcter i, per a cada lletra, crida la funció g, que calcula la lletra simètrica (A↔︎Z, B↔︎Y, etc.) i en retorna el codi ASCII. El resultat s’escriu al vector de sortida w2.
codifica i g.
C
char alfabet[27] = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
char w1[13] = "ARQUITECTURA";
char w2[16];
int codifica(char *pfrasein, char *pfraseout) {
int i = 0;
while (*pfrasein != 0) {
*pfraseout = g(alfabet, pfrasein);
pfrasein++;
pfraseout++;
i++;
}
*pfraseout = 0;
return i;
}
char g(char *alfa, char *pfrase) {
return alfa[25 - (*pfrase - 'A')];
}
void main() {
codifica(w1, w2);
}El Codi 30.3, la traducció a RV32I, conté tres errors, tots dins de codifica. La funció g és correcta. Identifiqueu cada error, expliqueu per què és incorrecte i escriviu-ne la correcció. Les explicacions van com a comentaris dins del mateix s3_5_1.s, a la línia de cada correcció.
codifica.
s3_5_1.s
.data
alfabet: .asciz "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
w1: .asciz "ARQUITECTURA"
w2: .space 16
.text
la a0, w1
la a1, w2
jal ra, codifica
li a7, 93
li a0, 0
ecall
g:
lb t0, 0(a1) # t0 = *pfrase
li t1, 'A'
sub t0, t0, t1 # t0 = *pfrase - 'A'
li t1, 25
sub t0, t1, t0 # t0 = 25 - (*pfrase - 'A')
add t0, a0, t0 # t0 = &alfa[25 - ...]
lb a0, 0(t0) # a0 = alfa[25 - ...]
ret
codifica:
addi sp, sp, -16 # reserva el BA
sw s0, 0(sp)
sw s1, 4(sp)
sw s2, 8(sp)
mv s0, a0 # s0 = pfrasein
mv s1, a1 # s1 = pfraseout
li s2, 0 # i = 0
while:
lb t0, 0(s0)
beqz t0, fiwhile
la a0, alfabet
mv a1, s1
jal ra, g
sb a0, 0(s0)
addi s0, s0, 1
addi s1, s1, 1
addi s2, s2, 1
j while
fiwhile:
sb zero, 0(s1)
mv a0, s2
lw s0, 0(sp)
lw s1, 4(sp)
lw s2, 8(sp)
addi sp, sp, 16
retComproveu que, un cop esmenats els errors, w2 conté "ZIJFRGVXGFIZ" al final de l’execució.
Solució 30.6. El programa conté tres errors, tots dins de codifica: el pròleg i l’epíleg no tracten ra, la crida a g rep el punter equivocat i el resultat s’escriu al vector equivocat.
Error 1 — el pròleg no desa ra i l’epíleg no el restaura.
codifica és multinivell (crida g). La instrucció jal ra, g sobreescriu ra amb l’adreça de retorn cap a codifica, destruint l’adreça de retorn cap al programa principal. Quan codifica executa ret, no torna al programa principal sinó a la instrucció següent a jal ra, g (l’adreça de retorn de l’última crida a g), de manera que l’execució reprèn dins del cos del bucle de codifica.
El símptoma observable és immediat: l’epíleg ja ha restaurat s0 amb el valor que tenia en entrar a codifica —el del programa principal, que no l’inicialitza mai i, per tant, val 0—, de manera que la primera instrucció reexecutada, sb a0, 0(s0), intenta escriure a l’adreça 0x00000000. RARS avorta amb «address out of range 0x00000000».
Correcció: desar ra al pròleg i restaurar-lo a l’epíleg.
RV32I
Error 2 — mv a1, s1 passa pfraseout (s1) a g en lloc de pfrasein (s0).
La funció g ha de rebre el punter al caràcter d’entrada per calcular-ne la lletra simètrica. Amb mv a1, s1 rep el punter de sortida, que apunta a una posició de w2 (inicialment buida), i retorna un resultat incorrecte.
Correcció:
Error 3 — sb a0, 0(s0) escriu a pfrasein (s0) en lloc de pfraseout (s1).
El caràcter codificat que retorna g a a0 s’ha d’escriure al vector de sortida. Amb sb a0, 0(s0) s’escriu sobre el vector d’entrada w1, corrompent-lo i deixant w2 sense modificar.
Correcció:
Versió corregida de codifica:
s3_5_1.s
codifica:
addi sp, sp, -16
sw s0, 0(sp)
sw s1, 4(sp)
sw s2, 8(sp)
sw ra, 12(sp) # codifica crida g, que sobreescriu ra
mv s0, a0
mv s1, a1
li s2, 0
while:
lb t0, 0(s0)
beqz t0, fiwhile
la a0, alfabet
mv a1, s0 # g ha de rebre el punter d'entrada
jal ra, g
sb a0, 0(s1) # el caràcter codificat va al vector de sortida
addi s0, s0, 1
addi s1, s1, 1
addi s2, s2, 1
j while
fiwhile:
sb zero, 0(s1)
mv a0, s2
lw s0, 0(sp)
lw s1, 4(sp)
lw s2, 8(sp)
lw ra, 12(sp) # recupera l'adreça de retorn cap al programa principal
addi sp, sp, 16
ret