Potok (strumień) (ang. Flowchart) czynności, które powinna wykonać instrukcja

Przyjmiemy, że wartości zmiennych f, g, h, i, j znajdują się kolejno w rejestrach od $s0 do $s4. Pierwszy symbolna rysunku mówi, że należy porównać wartości zmiennych i oraz j, np. przy pomocy instrukcji bne

bne $s3,$s4,Else # jeżeli i<> j idź do etykiety Else

jeżeli są równe

add $s0,$s1,$s2 # wykonuje dodawanie f = g + h i umieszcza wynik w rejestrze $s0

wykonuje skok j (od słowa jump) do etykiety kończącej program

j Exit # idź do etykiety Exit

jeżeli są równe

Else: sub $s0,$s1,$s2 # wykonuje odejmowanie f = g – h i umieszcza wynik w rejestrze $s0

j Exit: # koniec programu.

W powyższym kodzie została wykorzystana instrukcja o nazwie symbolicznej ‘j’ (jump - skocz), którą można traktować jako bezwarunkową gałąź. Oznacza to, że procesor zawsze wykona gałąź rozpoczynającą się od etykiety po nazwie instrukcji jump. Etykieta Exit oznacza koniec kodu.

Instrukcja iteracji

Równie ważną jak możliwość wyboru jest możliwość wielokrotnego sekwencyjnego użycia tego samego zbioru instrukcji. Taką konstrukcję potocznie nazywa się pętlą. Obydwie tworzą pewien zamknięty blok instrukcji, który można użyć jako budulca do tworzenia bardziej skomplikowanego kodu. W języku C wielokrotne wykonanie tego samego zbioru instrukcji umożliwia funkcja while, jej argumentem jest zmienna logiczna.

Przykład

Kod w C pętli korzystającej z funkcji while:

k = 11; i = 1;

while (A[i] <> k) i += 1;

co oznacza "dopóki i-ty wyraz szeregu A(i) nie jest równy k powiększaj wskaźnik i o 1". Muszą być znane: szereg A, wartość zmiennej k oraz początkowa wartość wskaźnika i.

Przyjmiemy, że zmienna i znajduje się w rejestrze $s3 oraz zmienna k znajduje się w rejestrze $s5, natomiast baza szeregu znajduje się w rejestrze $s6.

Wykonanie zadania zaczyna się od utworzenia etykiety wywołującej instrukcję, która powiększa wskaźnik i o 1. Trzeba przypomnieć sobie, że słowa zaczynają się w adresach, których numery są wielokrotnością 4. To oznacza, że aby powiększyć wskaźnik i o 1 trzeba powiększyć adres o 4. Adres można powiększyć dodając 4 do poprzedniej wartości adresu, ale można również przez przesunięcie bitów w poprzednim adresie w lewo o 4 = 2². Następnie trzeba w kodzie umieścić etykietę Loop aby było wiadomo dokąd program ma powrócić po osiągnięciu końca pętli:

Loop: sll $t1,$s3,2 # tymczasowy rejestr $t1 zawiera 4 * i.

Aby otrzymać adres i-tego wyrazu szeregu A musimy dodać zawartość rejestru $t1 i bazę szeregu znajdującą się w rejestrze $s6:

add $t1,$t1,$s6 # $t1 zawiera adres A(i)

Teraz można wykorzystać ten adres w celu ściągnięcia A(i) z pamięci do rejestru:

lw $t0,0($t1) # tymczasowy rejestr $t0 zawiera A(i).

Następna instrukcja sprawdza czy spełniony jest warunek 'while (A[i] == k)' i kończy pętlę jeżeli warunek jest spełniony:

beq $t0,$s5, Exit # program przechodzi do etykiety Exit jeżeli A(i) ==k.

Kolejna instrukcja dodaje 1 do i:

add $s3,$s3,1 # i = i + 1.

Koniec pętli kieruje wykonywanie programu do funkcji 'while', czyli początku pętli:

j Loop # program przechodzi do etykiety Loop.

Trzeba jeszcze umieścić etykietę Exit w ostatnim wierszu kodu:

Exit # program kończy pracę.

Długość słowa komputera decyduje o ograniczeniu na skrajne wartości liczb które może przetwarzać komputer. Wynika to z prostego rozumowania na przykładzie archtektury 32-bitowej. Jeden bit spośród 32 musi być przeznaczony na określenie znaku liczby, w pozostałych 31 bitach można zapisać liczbę całkowitą nie większą niż 2³¹. Wobec tego 32-bitowe słowo może reprezentować liczby całkowite z przedziału (-2³¹, 2³¹-1), czyli (-2 147 483 648, 2 147 483 648). W rejestrze o formacie I (immediate) pole przeznaczone na dane ma 16 bitów. Podobne rozumowanie jak powyżej wskazuje, że można w nim zmieścić stałą liczbę całkowitą z przedziału (-2¹⁵, 2¹⁵-1) czyli (-32 768,32 767).

Procedury

Procedurą lub funkcją nazywa się przechowywany w pamięci podprogram wykonujący przypisane mu zadanie. Procedura posiada nazwę, parametry wejściowe, które są niezbędne do wykonania zadania. Wynik działania procedury jest przekazywany głównemu programowi. Ta sama procedura może być wielokrotnie wywoływana przez różne programy główne.

Przykład w C

int procA(int a,int b,int i,int j)

{int f;

f = (a + b) – (i * j);

return f;}

Procedura nazywa się procA, jej argumentami są liczby całkowite a, b, i, j, wynikiem jest liczba całkowita f.

Wywołanie procedury w programie głównym:

.

.

u = procA(1,3,4,2);

.

.

v = procA(10,5,8,11);

.

Wywołanie procedury nie wpływa na przebieg programu głównego, po wykonaniu procedury program kontynuuje pracę od wiersza następnego po wierszu wywołującym procedurę.

W asemblerze kod procedury i jej wywołania są bardziej skomplikowane. Należy wykonać następujące kroki:

- umieścić parametry procedury w odpowiednich rejestrach,

- zarezerwować zasób pamięci dla procedury

- przekazać sterowanie do procedury,

- wykonać operacje przewidziane procedurą,

- umieścić wynik tych operacji w odpowiednim rejestrze,

- przekazać sterowanie spowrotem do miejsca wywołania procedury.

W wykonywaniu procedury uczestniczą następujące rejestry:

- $a0–$a3: przechowują argumenty procedury,

- $v0–$v1: dwa rejestry, do których trafiają wyniki wykonania procedury,

- $ra: rejestr przechowujący adres instrukcji następnej po instrukcji wywołania procedury.

Wywołanie procedury polega na wykonaniu skoku bezwarunkowego do procedury, równocześnie trzeba zapisać w rejestrze $ra adres instrukcji znajdującej się w programie bezpośrednio za procedurą. Jest to niezbędne aby po wykonaniu procedury można było kontynuować następne instrukcje programu. Nazwa i format tej nowej instrukcji jest następująca

jal ProcedureAddress # (skrót od to 'jump and link').

Ponieważ procedura będzie właśnie wykonywana więc jej adres znajduje się w rejestrze PC, zatem adres następnej procedury jest PC+4, i ten adres znajdzie się w rejestrze $ra. Po pobraniu argumentów procedury z rejestrów $a0–$a3 i jej wykonaniu wynik zostaje zapisany w rejestrach $v0, $v1, a program wykonuje skok bezwarunkowy powrotu do instrukcji zapisanej w rejestrze $ra. Nazwa i argument tej instrukcji skoku to

jr $ra #(nazwa to skrót od 'jump register').

Stos

Jeżeli liczba argumentów procedury jest większa niż 4 albo liczba wyników procedury nie mieści się w dwóch rejestrach $v0 i $v1, to zachodzi potrzeba 'przelania' (ang. 'spill') zawartości rejestrów tych dwóch grup do pamięci. Pamięcią najlepiej nadającą się do tego celu jest stos (ang. 'stack') to znaczy pamięć, z której najpierw wyjmuje się to, co się ostatnio do niej włożyło (Last In First Out, skrót LIFO). Stos wymaga posługiwania się wskaźnikiem do ostatnio wpisanego na stos adresu. Wskaźnik zawiera adres miejsca, do którego zostanie przelana informacja niemieszcząca się w wymienionych rejestrach lub miejsca, z którego można pobrać wcześniej przelaną informację. Wskaźnik stosu jest modyfikowany o jedno słowo gdy zawartość rejestru jest umieszczana na stosie lub usuwana ze stosu. W MIPS wskaźnik stosu znajduje się w rejestrze $sp (skrót od 'stack pointer'). Powszechnie stosowane są terminy 'push' dla operacji przenoszenia danej na stos i 'pop' dla operacji usuwania danej ze stosu. Umówiono się również, że stos rośnie od adresów wyższych do niższych. Konsekwencje tej umowy są następujące:

- przeniesienie danej na stos (push) jest równoznaczne z usunięciem jej z wskaźnika stosu,

- usunięcie danej ze stosu (pop) jest równoznaczne z dodaniem jej do wskaźnika stosu.

Zawartość stosu (b)

Wartości wskaźnika stosu $sp przed wykonaniem procedury (a),

w trakcie (b) i po wykonaniu procedury (c).

(Wskaźnik stosu ('stack pointer') zawsze wskazuje na 'top' stosu, który znajduje się na samym dole)

Przykład

Napisać asemblerowy kod procedury z poprzedniego przykładu i jego wywołanie w programie głównym.

Zakładamy, że parametry procedury, czyli dane a, b, i, j znajdują się w rejestrach $a0, $a1, $a2, and $a3, natomiast rejestr $s0 jest zarezerwowany na wynik procedury, czyli f.

Program główny w wierszu poprzedzającym kod procedury musi zwierać instrukcję

jal PC+4 # w rejestrze $ar zostaje zapisany adres instrukcji następującej po procedurze.

Ponieważ procedura właśnie będzie wykonywana więc jej adres znajduje się w rejestrze PC, zatem adres następnej procedury jest PC+4. Następny wiersz zawiera etykietę poprzedzającą kod procedury:

procA:

W jednym z poprzednich przykładów należało obliczyć wartość podobnego wyrażenia jak w obecnej procedurze. Okazało się, że na przechowanie pośrednich wartości obliczeń potrzebne są trzy rejestry. Teraz trzeba te trzy liczby umieścić na stosie. W tym celu należy na stosie zarezerwować miejsce na trzy słowa a następnie umieścić w nich (push) poprzednie zawartości rejestrów.

addi $sp,$sp,-12 # przystosowuje stos dla trzech słów,

sw $t1, 8($sp) # zawartość rejestru $t1 została umieszczona na stosie,

sw $t0, 4($sp) # zawartość rejestru $t0 została umieszczona na stosie,

sw $s0, 0($sp) # zawartość rejestru $s0 została umieszczona na stosie.

Następne trzy wiersze zawierają instrukcje wykonujące czynności zawarte w procedurze

add $t0,$a0,$a1 # rejestr $t0 zawiera sumę a + b

mul $t1,$a2,$a3 # rejestr $t1 zawiera iloczyn i * j

sub $s0,$t0,$t1 # rejestr $s0 zawiera wynik f

Aby wynik był dostępny na zewnątrz procedury trzeba go wpisać do rejestru wyników, dokonuje się tego dodając zawartość rejestru $s0 do zawartości rejestru $zero, która zawsze jest równa 0,

add $v0,$s0,$zero # w rejestrze v0 znajduje się suma zawartości $s0 + 0.

Teraz można odtworzyć w rejestrach $s0, $t0, $t1, poprzednią ich zawartość, która została przeniesiona na stos. W tym celu zdejmujemy je ze stosu (pop) i wprowadzamy do rejestrów

lw $s0, 0($sp) # odtwarza zawartość rejestru $s0,

lw $t0, 4($sp) # odtwarza zawartość rejestru $t0,

lw $t1, 8($sp) # odtwarza zawartość rejestru $t1.

A następnie opróżniamy stos

addi $sp,$sp,12 # zmniejsza pojemność stosu.

Ostatni wiersz kodu procedury zawiera etykietę skoku do adresu zawartego w rejestrze $ra, to znaczy powrotu do programu głównego

jr $ra #koniec procedury i powrót do programu głównego.

Analizując przykład można było zauważyć, że zawartość rejestrów wykorzystywanych wewnątrz procedury jest usuwana po zakończeniu procedury, do programu głównego przechodzi tylko wynik procedury. Podobna sytuacja jest w języku C. Zmienne lokalne procedury są automatycznie usuwane z pamięci, pozostają tylko tzw. zmienne statyczne przechowywane w pamięci do chwili zakończenia programu lub do chwili usunięcia. Dla ułatwienia dostępu do zmiennych typu statycznego w MIPS zarezerwowano dodatkowy rejestr o nazwie wskaźnik globalny ('global pointer'), nazwa symboliczna $gp.