CN Wiki

= Laboratorul 5 - Instruction Set Architecture 4 = * Responsabil: [[dosarudaniel@gmail.com |Daniel Dosaru]] * Data publicării: 03.11.2018 * Data ultimei modificări: ~~LASTMOD~~ == Obiective == În [[https://elf.cs.pub.ro/cn/wiki/lab/cn2/lab04|laboratorul 4]] am menționat că din categoria instrucțiunilor de salt fac parte instrucțiunile ce apelează rutine și instrucțiuni care lucrează cu stiva. În continuare vom studia aceste instrucțiuni, dar și alte instrucțiuni și noțiuni necesare atunci când lucrăm cu funcții. == 1. Funcții == Funcțiile sunt un element important în orice limbaj de programare deoarece oferă suport pentru abstractizarea și refolosirea codului. Pentru a folosi o funcție, avem nevoie de prototipul ei - numele, numărul și tipul argumentelor, respectiv tipul valorii întoarse. Pentru a vedea cum se implementează funcțiile și apelul lor, trebuie întâi să stabilim ce se întâmplă atunci când apelăm o funcție. Vom lua un exemplu simplu: o funcție recursivă scrisă în C care calculează factorialul unui număr: <code C> int fact(int n) { if (n == 0) return 1; else return fact(n - 1) * n; } </code> Se declară parametrul **n**, de tip întreg. Această variabilă și oricare altă variabilă pe care am folosi-o trebuie să fie locală funcției și să nu existe conflicte cu alte variabile din alte funcții, chiar dacă acolo se vor folosi aceleași nume ca aici. De fapt, mai mult decât atât, pentru aceste variabile nu trebuie să existe conflicte nici măcar cu alte copii ale lor (exact cum se întâmplă la un apel recursiv). Pentru a putea implementa așa ceva, pentru fiecare apel al funcției **fact**, se realizează o copie într-o zonă de memorie diferită pentru variabila n, la fel ca și pentru tot corpul funcției. Vom avea nevoie de o zonă continuă de memorie, separată de restul programului, în care vom realiza aceste operații cu funcții și pe care o vom numi stivă, deoarece implementarea ei este asemănătoare cu a structurii de date cu același nume. == 2. Stiva == Stiva este o zonă rezervată din memorie, continuă, cu ajutorul căreia este implementată ideea de funcție și apel de funcție. === Implementarea efectivă a unui apel === Se alege prima oară o zonă de memorie arbitrară care va fi stivă. Pentru fiecare apel de funcție, va exista o secțiune pe stiva rezervată pentru acea funcție, numită "stack frame". Să luăm următorul exemplu de cod în C: <code C> int main(void) { int a = 5, b = 7, c; c = foo(a, b); return 0; } int foo(int a, int b) { return a + b; } </code> La intrarea în main(), stack-ul va conține doar frame-ul funcției main. Apoi, se ajunge la apelul funcției foo(), care ia 2 argumente. Metoda folosită de a trimite argumentele din main în funcția foo este să le încarci pe stivă, lăsând spațiu totodată și pentru valoarea de return a funcției foo(), spațiu din memorie care va fi încărcat odată ce foo() se termină. Stiva arată acum așa: {{:lab:cn2:main_stack_frame.png?350|}} După cum se vede, după ce am încărcat pe stivă argumentele și valoarea de return pentru funcția pe care o vom apela, "stack frame-ul" pentru main a crescut . Practic ce s-a întâmplat a fost să micșorăm valoarea lui SP (stack-pointer - care de obicei arată ori spre prima zonă de memorie neinițializată/nefolosită din stivă, ori spre ultima zonă inițializată/folosită) <note important>Argumentele și valoarea de return a unei funcții nu fac parte din stack frame-ul acesteia!</note> Când ajungem în corpul funcției foo(), aceasta e posibil să aibă nevoie de spațiu pentru variabile locale (în cazul de față nu), caz în care se modifică SP-ul pentru a crește "stack-frame-ul" lui foo() (operație echivalentă cu un PUSH). Stiva arată acum așa: {{:lab:cn2:main_and_foo_stack_frame.png?350|}} Se observă că a apărut un nou pointer, FP - frame pointer, care arată spre zona de memorie unde arată SP-ul înainte ca foo() să îl mute pentru a face loc variabilelor sale locale. Acest nou pointer ne va ajuta sa calculam locația în memorie pentru argumentele sau variabilele locale funcției (calculele de adresă pentru diferite variabile se vor face relativ la acest FP). Când funcția foo() s-a terminat, tot ce trebuie făcut este ca SP-ul să fie pus să arate spre locație de memorie indicată de FP (echivalent cu un POP). Astfel, după ce ieșim din foo(), stiva arată la fel cum arata înainte de a apela foo(), doar ca acum zona de memorie care a fost rezervată pentru valoarea de return o conține pe aceasta: {{:lab:cn2:ret_stack.png?350|}} După ce main() salvează valoarea de return, crește SP-ul astfel încât după ce se face POP la aceasta și la argumente, stiva va arăta exact ca la început. == 3. Instrucțiuni AVR == Instrucțiunile ce ne interesează în mod special sunt RCALL și RET. === RCALL === RCALL este un salt relativ de la adresa curentă la adresa specificată ca parametru. Atunci când se realizează un apel de funcție folosind RCALL, adresa instrucțiunii ce urmează după RCALL este salvată pe stivă. Această adresă se numește ''return address''. Este important să memorăm această adresă deoarece, la ieșirea din funcție, dorim să continuăm execuția normală a programului. În plus, la realizarea unui apel de funcție, pe stivă se rezervă 2 octeți - (''return address'' are 16 biți). Motivul pentru care RCALL realizează un salt relativ și reține adresa de revenire pe stivă este următorul: codul unei funcții/proceduri se poate afla oriunde în memorie. Aceasta poate fi situată la începutul sau la sfârșitul memoriei, într-o zonă în care există deja și o parte din codul unei alte funcții (spre exemplu ''main()'') sau într-o zonă aleatoare izolată. <note important>Datasheet-ul AVR oferă două implementări pentru RCALL: cu program counter pe 16 (I) și 22 (II) de biți. Implementarea folosită de noi este cea cu program counter pe 16 biți!</note> === RET === Instrucțiunea RET realizează revenirea dintr-o funcție la codul de unde a fost apelată aceasta. Practic, marchează sfârșitul zonei de memorie de unde se citește și execută codul funcției. RET este o instrucțiune cu 0 operanzi. Operanzii nu sunt necesari deoarece adresa la care trebuie să revină PC-ul pentru a continua execuția normală a programului se află salvată deja pe stivă. În urma apelului RET, se vor elibera 2 octeți de pe stivă (pentru varianta cu program counter pe 16 biți). <note important>Atenție! Dacă cineva modifică adresa de revenire salvată pe stivă la apelul unei funcții, programul va continua de la acea adresă modificată dacă ea este validă. Astfel, o funcție poate fi forțată să apeleze alte funcții la revenire.</note> == 4. TL;DR == * Funcțiile oferă suport pentru: abstractizare și refolosire cod. * Stiva e o zonă continuă de memorie cu ajutorul căreia se implementează apelurile de funcții. * Fiecare apel de funcție folosește o zonă de pe stivă numită stack frame. * Argumentele și valoarea de return a unei funcții nu fac parte din stack frame-ul acesteia! În acest laborator vom implementa următoarele instrucțiuni (pe 16 biți): * **RCALL** Salt relativ la o adresă (apelarea unei funcții) și salvarea (pe stivă) a următoarei instrucțiuni (return address) * Sintaxă: ''rcall k'' * Program Counter: ''PC <- PC + k + 1'' ; -2048 < k < 2047 * Stack Pointer: ''SP <- SP - 2'' * **RET** Revenirea dintr-o funcție * Sintaxă: ''ret'' * Program Counter: PC <- return address (de pe stivă) * Stack Pointer: ''SP <- SP + 2'' == 5. Exerciții == Scheletul laboratorului conține un checker pentru verificarea Taskului 1 și 2. <note important> Punctajul maxim pentru Task1 și Task2 se obține doar dacă **nu** apar în consola ISim teste picate (FAILED) **și** dacă ordinea de execuție a instrucțiunilor de mai jos (deja scrise in ''rom.v'') este: 0,1,4,5,2,3,6 <code asm> 0:ldi r16, 5 1:rjmp main_function first_function: 2:ldi r17, 15 3:ret main_function: 4:ldi r17, 10 5:rcall first_function 6:ldi r18, 20 </code> </note> **Task 0 (1P)** Analizați fișierul ''state_machine.v''. Cum s-a modificat stagiul MEM al benzii de asamblare pentru instrucțiunile RCALL și RET? **Task 1 (3P)** Implementați instrucțiunea RCALL. Folosiți varianta (I) a instrucțiunii (pentru dispozitive cu PC pe 16 biți). <note tip> RCALL este o combinație între PUSH și RJMP. Problema este că registrul PC, care trebuie salvat pe stivă, are, în implementarea noastră particulară, 10 biți, iar PUSH salvează numai 8. Pentru a putea salva toți biții necesari RCALL trebuie să facă două accese la memorie, vedeți ''TWO_CYCLE_MEM'' și ''cycle_count''.\\ \\ Urmăriți comentariile marcate ''TODO 1'' din fișierele ''decode_unit.v'', ''control_unit.v'' și ''signal_generation_unit.v''. </note> **Task 2 (3P)** Implementați instrucțiunea RET. Folosiți varianta (I) a instrucțiunii (pentru dispozitive cu PC pe 16 biți). <note tip> RET este o combinație între POP și un salt absolut. Urmăriți comentariile marcate ''TODO 2'' din fișierele ''decode_unit.v'', ''control_unit.v'' și ''signal_generation_unit.v''. </note> **Task 3 (1P)** Creați un program pentru testarea instrucțiunilor implementate mai devreme. Programul trebuie să apeleze o funcție care încarcă constanta ''66'' în registrul R20). Scrieți programul în fisierul ''rom.v'' folosind tool-ul {{:lab:cn2:avrasm.zip | avrasm.jar}} și executați programul. <note> java -jar avrasm.jar input.txt output.txt </note> **Task 4 (2P)** Creați un program care calculează diferența a două numere folosind o funcție ''dif'' ce primește doi parametrii. Înainte de apel se vor pune pe stivă cei doi parametrii ai funcției. Funcția ''dif'' va lua parametrii de pe stivă **fără a modifica** valoarea return_address (salvată tot pe stivă). Funcția ''dif'' va pune rezultatul în registrul R16. Exemplu cod C: <code C> int diff (int a, int b) { return a-b; } int main () { int a, b, d; a = 10; b = 2; d = diff (a, b); } </code> **Bonus (2P)** Creați un program care calculează suma primelor ''n'' numere naturale și o stochează în registrul R20. Programul va citi parametrul ''n'' de la o adresa fixa de memorie (pe care o stabiliți când creați programul). Trebuie sa calculați suma folosind o funcție recursiva (''sum(n) = n + sum(n - 1)''). Întâi scrieți codul pe hârtie și rulați-l manual (tot pe hârtie) pentru un număr mic. == 6. Resurse == * [[http://www.atmel.com/Images/Atmel-8235-8-bit-AVR-Microcontroller-ATtiny20_Datasheet.pdf |Datasheet ATTiny20]] * [[http://ww1.microchip.com/downloads/en/devicedoc/atmel-0856-avr-instruction-set-manual.pdf| Setul de Instrucțiuni AVR]] * {{:lab:cn2:avrasm.zip | avrasm}} - tool java pentru a genera cod mașină AVR. * {{ :lab:cn2:lab05:lab05_skel_v3.zip |Scheletul laboratorului}} (actualizat 3.11.2018, ora 18:00) <ifauth @user> * {{ :lab:cn2:lab05:sol:lab05_sol_v3.zip |Soluția laboratorului}} (Publicată pe 10.11.2018) </ifauth>