Tema 3: Traducció de programes

12.1 Operacions lògiques i desplaçaments

Problema 12.1 Calculeu el resultat en hexadecimal de les operacions lògiques bit a bit següents amb 16 bits:

0x7654 | 0x3333
0x7654 & 0x3333
0x7654 << 2
0x7654 >> 3 (desplaçament lògic)

Problema 12.2 Donada la sentència en C:

C = A ^ B;

Traduïu-la a assemblador RISC-V sense utilitzar la instrucció xor. Recordeu que l’operació és equivalent a:

C = (~A & B) | (A & ~B);

Problema 12.3 Escriviu les seqüències de codi necessàries per deixar a t1 el resultat de les condicions lògiques següents, sense fer servir instruccions de salt. El valor final de t1 ha de ser 0 si la condició no es compleix, o diferent de zero altrament.

L’enter representat per t1 és negatiu.
L’enter representat per t1 és múltiple de 4.
El natural representat per t1 és tal que el seu quadrat no es pot escriure amb 32 bits.
El natural representat per t1 és tal que el seu doble no es pot escriure amb 32 bits.
Els bits 1, 3 i 5 de t1 valen zero.

Problema 12.4 Programeu una seqüència de no més de 6 instruccions que posi a 0 el bit $i$-èsim del registre t1, deixant la resta de bits intactes. Suposeu que $i$ està guardat a t2. Podeu usar altres registres per a resultats temporals.

Problema 12.5 Feu un programa que faci els desplaçaments següents sobre un nombre de 64 bits guardat als registres t2 (32 bits de més pes) i t1 (32 bits de menys pes):

Desplaçament a l’esquerra d’1 posició.
Desplaçament lògic a la dreta d’1 posició.
Desplaçament aritmètic a la dreta d’1 posició.
Desplaçament lògic a l’esquerra de $n$ posicions ($n < 32$), on $n$ ocupa t3.
Desplaçament lògic a la dreta de $n$ posicions ($n < 32$), on $n$ ocupa t3.

Problema 12.6 Suposeu que el registre t0 conté dos enters de 16 bits en complement a 2: un als 16 bits de més pes i un altre als 16 bits de menys pes. Escriviu una seqüència d’instruccions que extregui aquests dos nombres, els representi en 32 bits estenent el signe, i els guardi a t1 i t2 respectivament, sense usar cap instrucció d’accés a memòria.

Problema 12.7 Feu un programa que compti el nombre de bits actius que hi ha al registre t1, executant el mínim d’instruccions possible i sense fer cap lectura de memòria. El resultat s’ha de deixar al registre t3.

Problema 12.8 Escriviu un fragment de codi assemblador RISC-V que intercanviï tots els bits parells amb els bits senars del registre t0.

Problema 12.9 Representeu el valor inicial de cada bit de t4 amb una lletra: el bit 31 és b31, el bit 30 és b30, …, el bit 0 és b0. Cada lletra denota un valor binari desconegut (0 o 1).

Escriviu les instruccions necessàries perquè el bit de més pes passi a ser el de menys pes i la resta de bits es desplacin una posició cap a l’esquerra.
Seguint la mateixa notació, escriviu el contingut del registre t4 després d’executar les instruccions del Codi 12.1:

Codi 12.1: Codi de l’apartat b).

RV32I

        li      t1, 16
        mv      t2, t4
bucle:
        srli    t4, t4, 1
        add     t2, t2, t2
        addi    t1, t1, -1
        bne     t1, zero, bucle
        or      t4, t4, t2

12.2 Sentències condicionals i bucles

Vegeu Secció 3.6 i Secció 3.7.

Problema 12.10 Traduïu a assemblador RISC-V el programa en C del Codi 12.2, suposant que a, b i c ja s’han inicialitzat als registres t1, t2 i t3:

Codi 12.2: Sentències if imbricades.

void main() {
    int a, b, c, i;  // i s'emmagatzema a t0
    ...
    if (a > 0) {
        i = b;
        if (((i - 4) < a) && (i > 0))
            b = b + c;
        else if (c > 0)
            b = b - c;
    } else {
        a = a + b;
    }
}

Problema 12.11 Traduïu a assemblador RISC-V la sentència if del programa en C del Codi 12.3, que converteix un dígit hexadecimal (representat per un caràcter ASCII guardat a la variable global c) al seu valor binari equivalent i l’escriu a la variable global num (enter de 8 bits). Suposeu que el valor de c és un dels caràcters {'0'..'9', 'A'..'F', 'a'..'f'}.

Codi 12.3: Conversió d’un dígit hexadecimal en ASCII al seu valor.

char c, num;
void main() {
    ...
    if ((c >= 'A') && (c <= 'F'))
        num = c - 'A' + 10;
    else if ((c >= 'a') && (c <= 'f'))
        num = c - 'a' + 10;
    else
        num = c - '0';
}

Problema 12.12 Traduïu a assemblador RISC-V la sentència switch del Codi 12.4. La variable op ocupa el registre t0 i les variables a, b, res ocupen t1, t2, t3:

Codi 12.4: Sentència switch amb quatre casos i default.

int op, a, b, res;
...
switch (op) {
    case 0:  res = a + b;  break;
    case 1:  res = a - b;  break;
    case 2:  res = a & b;  break;
    case 3:  res = a | b;  break;
    default: res = 0;
}

Proposeu dues implementacions: una amb salts encadenats i una altra amb taula de salts (jump table). Quan és preferible cada enfocament?

Problema 12.13 Donat el programa en C:

void main() {
    int a = 23;  // guardat a t0
    int b = 12;  // guardat a t1
    int i;       // guardat a t2
    for (i = 0; i < 10; i++)
        a += b;
}

Traduïu-lo a assemblador RISC-V.
Quin és el nombre total d’instruccions que s’executen?
Suposant un processador a 2 GHz on totes les instruccions tenen CPI = 2, si el nombre d’instruccions executades fos 10, quants segons trigaria a executar-se el programa?
En un processador a 2 GHz, si el nombre d’instruccions executades fos 10, com a l’apartat c), i el programa trigués $5 \times 10^{-9}$ s, quin seria el CPI del programa?

Problema 12.14 Donades dues variables enteres a i b (amb b ≥ 0), ja inicialitzades als registres t1 i t2:

Programeu en C una seqüència d’instruccions que multipliqui a * b usant un bucle while i operacions de suma. El resultat s’ha de deixar a c, ubicada al registre t3.
Traduïu-la a assemblador RISC-V.
Quin és el nombre màxim d’instruccions RISC-V que poden arribar a executar-se?
En un processador a 2 GHz on totes les instruccions usen 2 cicles de rellotge, quants segons trigaria a executar-se el programa?
Si en comptes de sumes s’usa una única instrucció de multiplicació que utilitza 10 cicles de rellotge, quants segons trigaria a executar-se? Quin seria el CPI del programa?

Problema 12.15 Traduïu a assemblador RISC-V el programa en C del Codi 12.5:

Codi 12.5: Bucle while que escriu el vector D.

int D[10] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
void main() {
    int a = 0;   // guardat a t0
    int b = 12;  // guardat a t1
    while (a < 10) {
        D[a] = b + a;
        a += 1;
    }
}

Problema 12.16 Traduïu a assemblador RISC-V el programa en C del Codi 12.6, suposant que les variables globals ja s’han inicialitzat:

Codi 12.6: Suma i recompte dels elements de V més grans que 5.

#define N 30
int V[N], suma, elems;
void main() {
    int i;
    ...
    i = 0;
    elems = 0;
    suma = 0;
    while (i < N) {
        if (V[i] > 5) {
            suma = suma + V[i];
            elems++;
        }
        i++;
    }
}

Problema 12.17 Donada la variable global (on N és una constant):

int v[N];

Calculeu el temps d’execució en cicles de rellotge de cada versió del programa que suma els elements de v, suposant que:

Els accessos a memòria triguen 4 cicles.
Els salts que no salten triguen 1 cicle.
Els salts que salten triguen 2 cicles.
La resta d’instruccions triguen 1 cicle.

RV32I

        li      t0, 0        # suma
        li      t1, 0        # i
        li      t2, 0        # desplaçament
bucle:
        li      t3, N
        bge     t1, t3, fi
        la      t4, v
        add     t4, t4, t2
        lw      t4, 0(t4)
        add     t0, t0, t4
        addi    t2, t2, 4
        addi    t1, t1, 1
        j       bucle
fi:

RV32I

        li      t0, 0        # suma
        li      t1, 0        # i
bucle:
        li      t3, N
        bge     t1, t3, fi
        la      t3, v
        slli    t2, t1, 2
        add     t2, t3, t2
        lw      t2, 0(t2)
        add     t0, t0, t2
        addi    t1, t1, 1
        j       bucle
fi:

RV32I

        li      t0, 0        # suma
        li      t1, 0        # i
bucle:
        la      t3, v
        slli    t2, t1, 2
        add     t2, t2, t3
        lw      t2, 0(t2)
        add     t0, t0, t2
        addi    t1, t1, 1
        li      t3, N
        blt     t1, t3, bucle

RV32I

        li      t0, 0        # suma
        li      t1, N-1      # i
bucle:
        la      t3, v
        slli    t2, t1, 2
        add     t2, t3, t2
        lw      t2, 0(t2)
        add     t0, t0, t2
        addi    t1, t1, -1
        bge     t1, zero, bucle

RV32I

        li      t0, 0        # suma
        li      t1, N        # i
        la      t2, v
bucle:
        lw      t3, 0(t2)
        add     t0, t0, t3
        addi    t2, t2, 4
        addi    t1, t1, -1
        bne     t1, zero, bucle

Programeu una nova versió de l’apartat e) que en disminueixi el temps d’execució.

Problema 12.18 Donada la declaració en C (on N és una constant):

int V[2*N];

Escriviu un fragment de codi assemblador RISC-V que intercanviï cada element d’índex parell amb l’element següent d’índex senar.

Problema 12.19 Donades les declaracions:

RV32I

.data
v1:     .byte   '0', '0', '4', '1', '9'
v2:     .byte   '8', '9', '7', '2', '3'
v3:     .byte   0,   0,   0,   0,   0,  0

Cada vector conté caràcters ASCII que representen dígits numèrics. En conjunt, cada vector representa un natural decimal amb les unitats a l’última posició. Escriviu un programa que sumi els naturals representats per v1 i v2 i deixi el resultat a v3, que té un dígit de més per poder representar qualsevol suma sense desbordament. Feu servir l’algorisme típic de la suma dígit a dígit.

Problema 12.20 El vector d’enters Array està ubicat a l’adreça 0x10010000 de memòria i s’ha declarat així:

RV32I

.data
Array:  .word   2, 4, 6, 1

Feu un programa en assemblador RISC-V que ordeni els elements del vector de menor a major, deixant el valor més petit a la posició de memòria més baixa.

12.3 Subrutines: introducció

Vegeu Secció 3.9.

Problema 12.21 Escriviu en C i en assemblador RISC-V una funció que, donats dos enters de 32 bits passats per valor, retorni el mínim dels dos.

Problema 12.22 Traduïu a assemblador RISC-V la subrutina en C del Codi 12.7:

Codi 12.7: Funció strlen.

int strlen(char s[]) {
    int i = 0;
    while (s[i] != '\0')
        i++;
    return i;
}

Problema 12.23 Donat el fragment de programa en C:

void examen(char vi[], char vo[]) {
    int i = 0;
    while (vi[i] != '\0') {
        if (vi[i] != ' ')
            vo[i] = vi[i] - 32;
        else
            vo[i] = vi[i];
        i++;
    }
    vo[i] = '\0';
}
void main() {
    examen(vect1, vect2);
}

Sabent que vect1 i vect2 són variables globals:

Traduïu a assemblador RISC-V la funció main.
Traduïu a assemblador RISC-V la subrutina examen.

Problema 12.24 Donades les declaracions en C:

int proc(int vector[], int *x1);

char exam(int v[], int a, int b) {
    int i, *p;
    ...
}

Traduïu a assemblador RISC-V el fragment de codi del Codi 12.8, que pertany a exam, suposant que i i p ocupen t0 i t1:

Codi 12.8: Fragment de l’apartat a): una crida a proc.

p = &v[a + 5];
i = proc(v, p);

Traduïu a assemblador RISC-V la sentència condicional del Codi 12.9, que pertany a exam, suposant que i ocupa t0:

Codi 12.9: Sentència condicional de l’apartat b).

if ((i > 0) && (i < 10))
    i = 10;
else
    i = 0;

Traduïu a assemblador RISC-V el fragment de codi del Codi 12.10, que pertany a exam, suposant que i i p ocupen t0 i t1:

Codi 12.10: Bucle de l’apartat c).

p = v + b;
for (i = 0; i < 10; i++) {
    *p = 0;
    p++;
}

Problema 12.25 Donades les funcions en C:

void swap(int *a, int *b) {
    int temp;
    temp = *a;
    *a   = *b;
    *b   = temp;
}

void examen(int vector[], char c, int j) {
    swap(&vector[j + 1], &vector[j]);
}

Traduïu a assemblador RISC-V la subrutina swap.
Traduïu a assemblador RISC-V la subrutina examen.

Problema 12.26 Sabent que la funció f té la capçalera en C:

int f(int n);

i que la seva traducció a assemblador RISC-V és el Codi 12.11:

Codi 12.11: Traducció de la funció f.

RV32I

f:
        mv      t0, a0     # t0 = n
        li      a0, 0      # a0 = acumulador
buc:
        andi    t1, t0, 1
        add     a0, a0, t1
        srli    t0, t0, 1
        bne     t0, zero, buc
        li      t1, 32
        sub     a0, t1, a0
        ret

Quin valor retorna f per a n = 0x6789ABCD?
Expliqueu amb paraules què calcula la funció f.

Problema 12.27 Traduïu a assemblador RISC-V la funció recursiva del Codi 12.12:

Codi 12.12: Funció recursiva pellnumber.

int pellnumber(int n) {
    if (n < 2)
        return n;
    else
        return 2 * pellnumber(n - 1) + pellnumber(n - 2);
}

Problema 12.28 Traduïu a assemblador RISC-V la subrutina en C del Codi 12.13:

Codi 12.13: Subrutina recursiva maxv.

int maxv(int vector[], int length) {
    int temp;
    if (length == 1)
        temp = vector[0];
    else {
        temp = maxv(vector, length - 1);
        if (vector[length - 1] > temp)
            temp = vector[length - 1];
    }
    return temp;
}

Problema 12.29 Traduïu a assemblador RISC-V la funció func1:

unsigned int func1(unsigned int v, unsigned int *p) {
    if (v == 0)
        *p = 0;
    else
        *p = func1(func1(v - 1, p), p + 1) - 1;
    return *p;
}

Problema 12.30 El repertori de RISC-V inclou la instrucció jalr per cridar subrutines i per a salts indirectes. Suposeu que s’executa el fragment de codi RISC-V del Codi 12.14:

Codi 12.14: Fragment amb la, addi i jalr.

RV32I

        la      ra, etiq
        addi    ra, ra, -4
etiq:   jalr    ra, 0(ra)

Quina és la resposta correcta?

La instrucció jalr s’executa 1 vegada.
La instrucció jalr s’executa 2 vegades.
La instrucció jalr s’executa 3 vegades.
La instrucció jalr s’executa infinites vegades (el programa entra en un bucle infinit).
Sense saber el contingut d’altres posicions de memòria no es pot saber quantes vegades s’executa.

Problema 12.31 Donades les declaracions en C:

int s2(int c, long long *d, long long w[]);

int s1(int x, long long v[], int *p) {
    long long *k;
    k = &v[x];
    x = s2(*p, k, v);
    return *p + x;
}

Traduïu a assemblador RISC-V la funció s1.

12.4 Subrutines: context i bloc d’activació

Vegeu Secció 3.9.3 i Secció 3.9.4.

Problema 12.32 Donades les declaracions en C:

int subr2(int a, char *b, char c, int d);

int subr1(char v[], int e2, int *var, char p) {
    int valor;
    valor = subr2(*var, &v[e2], p, e2);
    return valor + e2;
}

Traduïu a assemblador RISC-V la funció subr1.

Problema 12.33 Donades les declaracions de variables globals i de la funció A:

char  x;
int   z;
char  w[20];

char A(char i, int k, char *v) {
    char r[10];
    char c;
    c    = v[3];
    r[k] = i;
    return c;
}

Traduïu a assemblador RISC-V la sentència:

x = A(x, z, w);

Dibuixeu el bloc d’activació d’una crida a la funció A.
Traduïu a assemblador RISC-V la funció A.

Problema 12.34 Traduïu a assemblador RISC-V la funció A:

int B(short *x, short y[], int z, char m);

int A(int a[], short b[], char c) {
    int   p1 = 0;
    short p2[5];
    p1         = B(b, p2, p1, 'A');
    p2[p1 + a[2]] = b[p1];
    if (c == 'z')
        p1 = p1 - 3;
    else
        p1 = 2;
    return p1;
}

Problema 12.35 Traduïu a assemblador RISC-V la funció sub (escrivint punts suspensius per a les sentències desconegudes):

void sub(int p1[10], int p2, int p3) {
    int x1[10], x2;
    ...
    x1[p2]  = p1[x2] + p3;
    ...
    sub(x1, p2, p1[3]);
    ...
    x2 = p2 + p3;
    ...
}

12.5 Compilació, assemblatge, enllaçament i càrrega

Vegeu Secció 3.10.

Problema 12.36 La pseudoinstrucció la rd, symbol s’expandeix habitualment en dues instruccions reals. Expliqueu quines són i per què són necessàries dues instruccions. Quina és la limitació en el desplaçament que pot representar l’expansió?

Problema 12.37 Un projecte té dos fitxers font:

// fitxer a.c
int x = 42;
int f(int n) { return n + x; }

// fitxer b.c
extern int x;
int f(int n);
int main() { return f(x); }

Quines fases del flux de generació (compilació, assemblatge, enllaçament) intervenen en construir l’executable?
El fitxer objecte b.o conté una referència externa a x i a f. Qui resol aquestes referències i en quin moment?
Si x es declara static int x = 42 a a.c, canvia alguna cosa? Per què?
La pseudoinstrucció la t0, x es tradueix en auipc + addi (Problema 12.36). Per què auipc, relatiu al PC, i no lui, que carrega una adreça absoluta?

--- number-sections: true language: crossref-exr-title: "Problema" crossref-exr-prefix: "Problema" --- # {{< var tema3 >}} {#sec-tema-traduccio-enunciats} ## Operacions lògiques i desplaçaments *Vegeu @sec-desplacaments-de-bits i @sec-operacions-logiques-bit-a-bit.* ::: {#exr-t3-logica-bitabit} Calculeu el resultat en hexadecimal de les operacions lògiques bit a bit següents amb 16 bits: a) `0x7654 | 0x3333` b) `0x7654 & 0x3333` c) `0x7654 << 2` d) `0x7654 >> 3` (desplaçament lògic) ::: ::: {#exr-t3-logica-xor} Donada la sentència en C: ```{.c filename="C"} C = A ^ B; ``` Traduïu-la a assemblador RISC-V sense utilitzar la instrucció `xor`. Recordeu que l'operació és equivalent a: ```{.c filename="C"} C = (~A & B) | (A & ~B); ``` ::: ::: {#exr-t3-logica-condicions} Escriviu les seqüències de codi necessàries per deixar a `t1` el resultat de les condicions lògiques següents, sense fer servir instruccions de salt. El valor final de `t1` ha de ser 0 si la condició no es compleix, o diferent de zero altrament. a) L'enter representat per `t1` és negatiu. b) L'enter representat per `t1` és múltiple de 4. c) El natural representat per `t1` és tal que el seu quadrat no es pot escriure amb 32 bits. d) El natural representat per `t1` és tal que el seu doble no es pot escriure amb 32 bits. e) Els bits 1, 3 i 5 de `t1` valen zero. ::: ::: {#exr-t3-logica-bit-variable} Programeu una seqüència de no més de 6 instruccions que posi a 0 el bit $i$-èsim del registre `t1`, deixant la resta de bits intactes. Suposeu que $i$ està guardat a `t2`. Podeu usar altres registres per a resultats temporals. ::: ::: {#exr-t3-logica-64bits} Feu un programa que faci els desplaçaments següents sobre un nombre de 64 bits guardat als registres `t2` (32 bits de més pes) i `t1` (32 bits de menys pes): a) Desplaçament a l'esquerra d'1 posició. b) Desplaçament lògic a la dreta d'1 posició. c) Desplaçament aritmètic a la dreta d'1 posició. d) Desplaçament lògic a l'esquerra de $n$ posicions ($n < 32$), on $n$ ocupa `t3`. e) Desplaçament lògic a la dreta de $n$ posicions ($n < 32$), on $n$ ocupa `t3`. ::: ::: {#exr-t3-logica-16bits-registre} Suposeu que el registre `t0` conté dos enters de 16 bits en complement a 2: un als 16 bits de més pes i un altre als 16 bits de menys pes. Escriviu una seqüència d'instruccions que extregui aquests dos nombres, els representi en 32 bits estenent el signe, i els guardi a `t1` i `t2` respectivament, sense usar cap instrucció d'accés a memòria. ::: ::: {#exr-t3-logica-bits-actius} Feu un programa que compti el nombre de bits actius que hi ha al registre `t1`, executant el mínim d'instruccions possible i sense fer cap lectura de memòria. El resultat s'ha de deixar al registre `t3`. ::: ::: {#exr-t3-logica-intercanvi-bits} Escriviu un fragment de codi assemblador RISC-V que intercanviï tots els bits parells amb els bits senars del registre `t0`. ::: :::: {#exr-t3-logica-rotacio} Representeu el valor inicial de cada bit de `t4` amb una lletra: el bit 31 és `b31`, el bit 30 és `b30`, ..., el bit 0 és `b0`. Cada lletra denota un valor binari desconegut (0 o 1). a) Escriviu les instruccions necessàries perquè el bit de més pes passi a ser el de menys pes i la resta de bits es desplacin una posició cap a l'esquerra. b) Seguint la mateixa notació, escriviu el contingut del registre `t4` després d'executar les instruccions del @lst-t3-logica-rotacio-b: ::: {#lst-t3-logica-rotacio-b} ```{.s filename="RV32I"} li t1, 16 mv t2, t4 bucle: srli t4, t4, 1 add t2, t2, t2 addi t1, t1, -1 bne t1, zero, bucle or t4, t4, t2 ``` Codi de l'apartat b). ::: :::: ## Sentències condicionals i bucles *Vegeu @sec-if-then-else i @sec-bucles.* :::: {#exr-t3-bucles-if-imbricat} Traduïu a assemblador RISC-V el programa en C del @lst-t3-bucles-if-imbricat, suposant que `a`, `b` i `c` ja s'han inicialitzat als registres `t1`, `t2` i `t3`: ::: {#lst-t3-bucles-if-imbricat} ```{.c filename="C"} void main() { int a, b, c, i; // i s'emmagatzema a t0 ... if (a > 0) { i = b; if (((i - 4) < a) && (i > 0)) b = b + c; else if (c > 0) b = b - c; } else { a = a + b; } } ``` Sentències `if` imbricades. ::: :::: :::: {#exr-t3-bucles-hexadecimal} Traduïu a assemblador RISC-V la sentència `if` del programa en C del @lst-t3-bucles-hexadecimal, que converteix un dígit hexadecimal (representat per un caràcter ASCII guardat a la variable global `c`) al seu valor binari equivalent i l'escriu a la variable global `num` (enter de 8 bits). Suposeu que el valor de `c` és un dels caràcters `{'0'..'9', 'A'..'F', 'a'..'f'}`. ::: {#lst-t3-bucles-hexadecimal} ```{.c filename="C"} char c, num; void main() { ... if ((c >= 'A') && (c <= 'F')) num = c - 'A' + 10; else if ((c >= 'a') && (c <= 'f')) num = c - 'a' + 10; else num = c - '0'; } ``` Conversió d'un dígit hexadecimal en ASCII al seu valor. ::: :::: :::: {#exr-t3-bucles-switch} Traduïu a assemblador RISC-V la sentència `switch` del @lst-t3-bucles-switch. La variable `op` ocupa el registre `t0` i les variables `a`, `b`, `res` ocupen `t1`, `t2`, `t3`: ::: {#lst-t3-bucles-switch} ```{.c filename="C"} int op, a, b, res; ... switch (op) { case 0: res = a + b; break; case 1: res = a - b; break; case 2: res = a & b; break; case 3: res = a | b; break; default: res = 0; } ``` Sentència `switch` amb quatre casos i `default`. ::: Proposeu dues implementacions: una amb salts encadenats i una altra amb taula de salts (*jump table*). Quan és preferible cada enfocament? :::: ::: {#exr-t3-bucles-for} Donat el programa en C: ```{.c filename="C"} void main() { int a = 23; // guardat a t0 int b = 12; // guardat a t1 int i; // guardat a t2 for (i = 0; i < 10; i++) a += b; } ``` a) Traduïu-lo a assemblador RISC-V. b) Quin és el nombre total d'instruccions que s'executen? c) Suposant un processador a 2 GHz on totes les instruccions tenen CPI = 2, si el nombre d'instruccions executades fos 10, quants segons trigaria a executar-se el programa? d) En un processador a 2 GHz, si el nombre d'instruccions executades fos 10, com a l'apartat c), i el programa trigués $5 \times 10^{-9}$ s, quin seria el CPI del programa? ::: ::: {#exr-t3-bucles-multiplicacio} Donades dues variables enteres `a` i `b` (amb `b ≥ 0`), ja inicialitzades als registres `t1` i `t2`: a) Programeu en C una seqüència d'instruccions que multipliqui `a * b` usant un bucle `while` i operacions de suma. El resultat s'ha de deixar a `c`, ubicada al registre `t3`. b) Traduïu-la a assemblador RISC-V. c) Quin és el nombre màxim d'instruccions RISC-V que poden arribar a executar-se? d) En un processador a 2 GHz on totes les instruccions usen 2 cicles de rellotge, quants segons trigaria a executar-se el programa? e) Si en comptes de sumes s'usa una única instrucció de multiplicació que utilitza 10 cicles de rellotge, quants segons trigaria a executar-se? Quin seria el CPI del programa? ::: :::: {#exr-t3-bucles-while-vector} Traduïu a assemblador RISC-V el programa en C del @lst-t3-bucles-while-vector: ::: {#lst-t3-bucles-while-vector} ```{.c filename="C"} int D[10] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}; void main() { int a = 0; // guardat a t0 int b = 12; // guardat a t1 while (a < 10) { D[a] = b + a; a += 1; } } ``` Bucle `while` que escriu el vector `D`. ::: :::: :::: {#exr-t3-bucles-suma-positius} Traduïu a assemblador RISC-V el programa en C del @lst-t3-bucles-suma-positius, suposant que les variables globals ja s'han inicialitzat: ::: {#lst-t3-bucles-suma-positius} ```{.c filename="C"} #define N 30 int V[N], suma, elems; void main() { int i; ... i = 0; elems = 0; suma = 0; while (i < N) { if (V[i] > 5) { suma = suma + V[i]; elems++; } i++; } } ``` Suma i recompte dels elements de `V` més grans que 5. ::: :::: ::: {#exr-t3-bucles-suma-vector} Donada la variable global (on `N` és una constant): ```{.c filename="C"} int v[N]; ``` Calculeu el temps d'execució en cicles de rellotge de cada versió del programa que suma els elements de `v`, suposant que: - Els accessos a memòria triguen 4 cicles. - Els salts que no salten triguen 1 cicle. - Els salts que salten triguen 2 cicles. - La resta d'instruccions triguen 1 cicle. a) ```{.s filename="RV32I"} li t0, 0 # suma li t1, 0 # i li t2, 0 # desplaçament bucle: li t3, N bge t1, t3, fi la t4, v add t4, t4, t2 lw t4, 0(t4) add t0, t0, t4 addi t2, t2, 4 addi t1, t1, 1 j bucle fi: ``` b) ```{.s filename="RV32I"} li t0, 0 # suma li t1, 0 # i bucle: li t3, N bge t1, t3, fi la t3, v slli t2, t1, 2 add t2, t3, t2 lw t2, 0(t2) add t0, t0, t2 addi t1, t1, 1 j bucle fi: ``` c) ```{.s filename="RV32I"} li t0, 0 # suma li t1, 0 # i bucle: la t3, v slli t2, t1, 2 add t2, t2, t3 lw t2, 0(t2) add t0, t0, t2 addi t1, t1, 1 li t3, N blt t1, t3, bucle ``` d) ```{.s filename="RV32I"} li t0, 0 # suma li t1, N-1 # i bucle: la t3, v slli t2, t1, 2 add t2, t3, t2 lw t2, 0(t2) add t0, t0, t2 addi t1, t1, -1 bge t1, zero, bucle ``` e) ```{.s filename="RV32I"} li t0, 0 # suma li t1, N # i la t2, v bucle: lw t3, 0(t2) add t0, t0, t3 addi t2, t2, 4 addi t1, t1, -1 bne t1, zero, bucle ``` f) Programeu una nova versió de l'apartat e) que en disminueixi el temps d'execució. ::: ::: {#exr-t3-bucles-intercanvi-parells} Donada la declaració en C (on `N` és una constant): ```{.c filename="C"} int V[2*N]; ``` Escriviu un fragment de codi assemblador RISC-V que intercanviï cada element d'índex parell amb l'element següent d'índex senar. ::: ::: {#exr-t3-bucles-suma-ascii} Donades les declaracions: ```{.s filename="RV32I"} .data v1: .byte '0', '0', '4', '1', '9' v2: .byte '8', '9', '7', '2', '3' v3: .byte 0, 0, 0, 0, 0, 0 ``` Cada vector conté caràcters ASCII que representen dígits numèrics. En conjunt, cada vector representa un natural decimal amb les unitats a l'última posició. Escriviu un programa que sumi els naturals representats per `v1` i `v2` i deixi el resultat a `v3`, que té un dígit de més per poder representar qualsevol suma sense desbordament. Feu servir l'algorisme típic de la suma dígit a dígit. ::: ::: {#exr-t3-bucles-ordenacio} El vector d'enters `Array` està ubicat a l'adreça `0x10010000` de memòria i s'ha declarat així: ```{.s filename="RV32I"} .data Array: .word 2, 4, 6, 1 ``` Feu un programa en assemblador RISC-V que ordeni els elements del vector de menor a major, deixant el valor més petit a la posició de memòria més baixa. ::: ## Subrutines: introducció *Vegeu @sec-subrutines.* ::: {#exr-t3-subrutines-minim} Escriviu en C i en assemblador RISC-V una funció que, donats dos enters de 32 bits passats per valor, retorni el mínim dels dos. ::: :::: {#exr-t3-subrutines-strlen} Traduïu a assemblador RISC-V la subrutina en C del @lst-t3-subrutines-strlen: ::: {#lst-t3-subrutines-strlen} ```{.c filename="C"} int strlen(char s[]) { int i = 0; while (s[i] != '\0') i++; return i; } ``` Funció `strlen`. ::: :::: ::: {#exr-t3-subrutines-examen} Donat el fragment de programa en C: ```{.c filename="C"} void examen(char vi[], char vo[]) { int i = 0; while (vi[i] != '\0') { if (vi[i] != ' ') vo[i] = vi[i] - 32; else vo[i] = vi[i]; i++; } vo[i] = '\0'; } void main() { examen(vect1, vect2); } ``` Sabent que `vect1` i `vect2` són variables globals: a) Traduïu a assemblador RISC-V la funció `main`. b) Traduïu a assemblador RISC-V la subrutina `examen`. ::: :::: {#exr-t3-subrutines-exam} Donades les declaracions en C: ```{.c filename="C"} int proc(int vector[], int *x1); char exam(int v[], int a, int b) { int i, *p; ... } ``` a) Traduïu a assemblador RISC-V el fragment de codi del @lst-t3-subrutines-exam-a, que pertany a `exam`, suposant que `i` i `p` ocupen `t0` i `t1`: ::: {#lst-t3-subrutines-exam-a} ```{.c filename="C"} p = &v[a + 5]; i = proc(v, p); ``` Fragment de l'apartat a): una crida a `proc`. ::: b) Traduïu a assemblador RISC-V la sentència condicional del @lst-t3-subrutines-exam-b, que pertany a `exam`, suposant que `i` ocupa `t0`: ::: {#lst-t3-subrutines-exam-b} ```{.c filename="C"} if ((i > 0) && (i < 10)) i = 10; else i = 0; ``` Sentència condicional de l'apartat b). ::: c) Traduïu a assemblador RISC-V el fragment de codi del @lst-t3-subrutines-exam-c, que pertany a `exam`, suposant que `i` i `p` ocupen `t0` i `t1`: ::: {#lst-t3-subrutines-exam-c} ```{.c filename="C"} p = v + b; for (i = 0; i < 10; i++) { *p = 0; p++; } ``` Bucle de l'apartat c). ::: :::: ::: {#exr-t3-subrutines-swap} Donades les funcions en C: ```{.c filename="C"} void swap(int *a, int *b) { int temp; temp = *a; *a = *b; *b = temp; } void examen(int vector[], char c, int j) { swap(&vector[j + 1], &vector[j]); } ``` a) Traduïu a assemblador RISC-V la subrutina `swap`. b) Traduïu a assemblador RISC-V la subrutina `examen`. ::: :::: {#exr-t3-subrutines-inversa} Sabent que la funció `f` té la capçalera en C: ```{.c filename="C"} int f(int n); ``` i que la seva traducció a assemblador RISC-V és el @lst-t3-subrutines-inversa: ::: {#lst-t3-subrutines-inversa} ```{.s filename="RV32I"} f: mv t0, a0 # t0 = n li a0, 0 # a0 = acumulador buc: andi t1, t0, 1 add a0, a0, t1 srli t0, t0, 1 bne t0, zero, buc li t1, 32 sub a0, t1, a0 ret ``` Traducció de la funció `f`. ::: a) Quin valor retorna `f` per a `n = 0x6789ABCD`? b) Expliqueu amb paraules què calcula la funció `f`. :::: :::: {#exr-t3-subrutines-recursiva-pell} Traduïu a assemblador RISC-V la funció recursiva del @lst-t3-subrutines-recursiva-pell: ::: {#lst-t3-subrutines-recursiva-pell} ```{.c filename="C"} int pellnumber(int n) { if (n < 2) return n; else return 2 * pellnumber(n - 1) + pellnumber(n - 2); } ``` Funció recursiva `pellnumber`. ::: :::: :::: {#exr-t3-subrutines-maxv} Traduïu a assemblador RISC-V la subrutina en C del @lst-t3-subrutines-maxv: ::: {#lst-t3-subrutines-maxv} ```{.c filename="C"} int maxv(int vector[], int length) { int temp; if (length == 1) temp = vector[0]; else { temp = maxv(vector, length - 1); if (vector[length - 1] > temp) temp = vector[length - 1]; } return temp; } ``` Subrutina recursiva `maxv`. ::: :::: ::: {#exr-t3-subrutines-func1} Traduïu a assemblador RISC-V la funció `func1`: ```{.c filename="C"} unsigned int func1(unsigned int v, unsigned int *p) { if (v == 0) *p = 0; else *p = func1(func1(v - 1, p), p + 1) - 1; return *p; } ``` ::: :::: {#exr-t3-memoria-jalr} El repertori de RISC-V inclou la instrucció `jalr` per cridar subrutines i per a salts indirectes. Suposeu que s'executa el fragment de codi RISC-V del @lst-t3-memoria-jalr: ::: {#lst-t3-memoria-jalr} ```{.s filename="RV32I"} la ra, etiq addi ra, ra, -4 etiq: jalr ra, 0(ra) ``` Fragment amb `la`, `addi` i `jalr`. ::: Quina és la resposta correcta? a) La instrucció `jalr` s'executa 1 vegada. b) La instrucció `jalr` s'executa 2 vegades. c) La instrucció `jalr` s'executa 3 vegades. d) La instrucció `jalr` s'executa infinites vegades (el programa entra en un bucle infinit). e) Sense saber el contingut d'altres posicions de memòria no es pot saber quantes vegades s'executa. :::: ::: {#exr-t3-subrutines-s1} Donades les declaracions en C: ```{.c filename="C"} int s2(int c, long long *d, long long w[]); int s1(int x, long long v[], int *p) { long long *k; k = &v[x]; x = s2(*p, k, v); return *p + x; } ``` Traduïu a assemblador RISC-V la funció `s1`. ::: ## Subrutines: context i bloc d'activació *Vegeu @sec-variables-locals i @sec-multinivell-pila.* ::: {#exr-t3-ba-subr1} Donades les declaracions en C: ```{.c filename="C"} int subr2(int a, char *b, char c, int d); int subr1(char v[], int e2, int *var, char p) { int valor; valor = subr2(*var, &v[e2], p, e2); return valor + e2; } ``` Traduïu a assemblador RISC-V la funció `subr1`. ::: ::: {#exr-t3-ba-funcioA} Donades les declaracions de variables globals i de la funció `A`: ```{.c filename="C"} char x; int z; char w[20]; char A(char i, int k, char *v) { char r[10]; char c; c = v[3]; r[k] = i; return c; } ``` a) Traduïu a assemblador RISC-V la sentència: ```{.c filename="C"} x = A(x, z, w); ``` b) Dibuixeu el bloc d'activació d'una crida a la funció `A`. c) Traduïu a assemblador RISC-V la funció `A`. ::: ::: {#exr-t3-ba-funcioA2} Traduïu a assemblador RISC-V la funció `A`: ```{.c filename="C"} int B(short *x, short y[], int z, char m); int A(int a[], short b[], char c) { int p1 = 0; short p2[5]; p1 = B(b, p2, p1, 'A'); p2[p1 + a[2]] = b[p1]; if (c == 'z') p1 = p1 - 3; else p1 = 2; return p1; } ``` ::: ::: {#exr-t3-ba-sub} Traduïu a assemblador RISC-V la funció `sub` (escrivint punts suspensius per a les sentències desconegudes): ```{.c filename="C"} void sub(int p1[10], int p2, int p3) { int x1[10], x2; ... x1[p2] = p1[x2] + p3; ... sub(x1, p2, p1[3]); ... x2 = p2 + p3; ... } ``` ::: ## Compilació, assemblatge, enllaçament i càrrega *Vegeu @sec-compilacio.* ::: {#exr-t3-compilacio-auipc} La pseudoinstrucció `la rd, symbol` s'expandeix habitualment en dues instruccions reals. Expliqueu quines són i per què són necessàries dues instruccions. Quina és la limitació en el desplaçament que pot representar l'expansió? ::: ::: {#exr-t3-compilacio-relocacio} Un projecte té dos fitxers font: ```{.c filename="C"} // fitxer a.c int x = 42; int f(int n) { return n + x; } ``` ```{.c filename="C"} // fitxer b.c extern int x; int f(int n); int main() { return f(x); } ``` a) Quines fases del flux de generació (compilació, assemblatge, enllaçament) intervenen en construir l'executable? b) El fitxer objecte `b.o` conté una referència externa a `x` i a `f`. Qui resol aquestes referències i en quin moment? c) Si `x` es declara `static int x = 42` a `a.c`, canvia alguna cosa? Per què? d) La pseudoinstrucció `la t0, x` es tradueix en `auipc` + `addi` (@exr-t3-compilacio-auipc). Per què `auipc`, relatiu al PC, i no `lui`, que carrega una adreça absoluta? :::