MIPS: grananje i petlje

Granjanje i petlje su temeljni koncepti u programiranju koji omogućavaju programima da se izvršavaju na različite načine i prilagođavaju uvjetima izvođenja. Granjanje omogućuje programima donošenje odluka na temelju uvjeta, dok petlje omogućuju ponavljanje određenih blokova koda. U nastavku ćemo se baviti ovim konceptima i njihovom primjenom u programiranju.

Tijek izvođenja programa

Tijek izvođenja programa određuje redoslijed izvršavanja instrukcija i možemo ga podijeliti na tri osnovna tipa:

• slijedno izvođenje instrukcija,
• uvjetno grananje (if-else),
• petlje (for, while, do-while).

Slijedno izvođenje instrukcija podrazumijeva da se svaka instrukcija izvršava jedna za drugom, redom kako su napisane. Uvjetno grananje omogućava programu da preskoči određene dijelove koda u slučaju kada je odgovarajući uvjet zadovoljen, dok petlje omogućavaju ponavljanje određenog bloka više puta. Ovi tipovi tijeka izvođenja programa daju programerima mogućnost prilagodbe izvršavanja programa različitim situacijama i uvjetima.

Slijedno izvođenje instrukcija

Slijedno izvođenje instrukcija predstavlja osnovni način izvršavanja programa, gdje se naredbe izvršavaju jedna za drugom. Ovaj pristup osigurava predvidljivo i logično funkcioniranje programa. Svaka instrukcija se čita i izvršava bez preskakanja ili ponavljanja dijelova koda. Nakon što se jedna instrukcija dovrši, program nastavlja s izvršavanjem sljedeće instrukcije u memoriji.

Pogledajmo primjer programa u C++ koji zbraja dva broja. Prvo se deklarira varijabla a, zatim varijabla b i c u koju se sprema njihov zbroj. Na kraju program završava. U ovom primjeru naredbe se izvršavaju jedna za drugom bez preskakanja ili ponavljanja dijelova koda.

int main() {
    int a = 5;
    int b = 10;
    int c = a + b;
    return 0;
}

Uvjetno grananje

Uvjetno grananje je koncept koji omogućava programima da donose odluke na temelju određenih uvjeta. Kroz uvjetnu izjavu, program provjerava zadovoljava li određeni kriterij, poput usporedbe vrijednosti ili provjere logičkog izraza. Na temelju rezultata provjere, program odabire odgovarajuću putanju izvođenja, omogućavajući fleksibilnost i prilagodljivost u programiranju.

Pogledajmo sljedeći primjer programa u C++ koji provjerava je li uvjet a < b istinit:

int main() {
    int a = 5;
    int b = 10;
    if (a < b) {
        cout << "a je manje od b" << endl;
    } else {
        cout << "b je manje ili jednako od a" << endl;
    }
    return 0;
}

U ovom primjeru koristimo naredbu if-else za ispisivanje različitih poruka ovisno o odnosu između dvije varijable, a i b. Ako je uvjet a < b ispunjen, ispisuje se prva poruka, dok se u suprotnom ispisuje druga poruka. Ovaj koncept omogućava programu da dinamički odabere između različitih mogućnosti na temelju određenih uvjeta.

Petlje

Petlje (eng. loop) su ključni koncept u programiranju koji omogućava izvršavanje određenog bloka naredbi više puta. One se koriste kada želimo ponavljati određeni zadatak sve dok je određeni uvjet ispunjen.

U nastavku ćemo detaljnije objasniti različite vrste petlji, kao što su petlja for, while i do-while, zajedno s primjerima njihove upotrebe u programskom jeziku C++.

Petlja for

Petlja for omogućava ponavljanje određenog bloka naredbi kada je unaprijed poznat broj ponavljanja, u našem primjeru to je 10. Sastoji se od tri dijela: inicijalizacije int i = 1, uvjeta i <= 10 i ažuriranja i++. Inicijalizacija se koristi za postavljanje početne vrijednosti kontrolne varijable, uvjet određuje kada će se petlja prestati izvršavati, a ažuriranje se koristi za promjenu vrijednosti kontrolne varijable nakon svake iteracije petlje.

int main() {
    for (int i = 1; i <= 10; i++) {
        cout << i << endl;
    }
    return 0;
}

Pogledajmo primjer programa koji ispisuje brojeve od 1 do 10. Inicijalizacija postavlja početnu vrijednost varijable i na 1, uvjet petlje provjerava je li i manje ili jednako od 10, dok izraz inkrementacije povećava vrijednost i za 1 pri svakoj iteraciji petlje.

Kada se program izvrši, petlja će ispisati brojeve od 1 do 10, svaki u zasebnom redu na konzoli. U ovom primjeru možemo primijetiti da nam je unaprijed poznat broj ponavljanja petlje (10). Međutim, postoje situacije u kojima nam broj ponavljanja nije poznat unaprijed. U tim slučajevima koristimo petlje koje se izvršavaju sve dok je određeni uvjet ispunjen. Pogledajmo sada primjere programa koji koriste takve petlje.

Petlja shile

Petlja while se koristi kada želimo ponavljati određeni zadatak sve dok je uvjet ispunjen. Primjerice, program traži od korisnika da unese točnu zaporku. Dakle, program neće nastaviti dalje s izvođenjem dok korisnik ne unese točnu zaporku. Uvjet se provjerava prije svake iteracije petlje i ako je uvjet istinit izvršava se blok naredbi. Ako uvjet nije zadovoljen, petlja se prekida i izvršenje programa se nastavlja izvan petlje.

int main() {
    int i = 1;
    while (i <= 10) {
        cout << i << endl;
        i++;
    }
    return 0;
}

Ovaj program će također ispisati brojeve od 1 do 10. Petlja će se izvršavati sve dok je vrijednost varijable i manja ili jednaka 10. Nakon svake iteracije petlje provjerava se uvjet i <= 10, a ako je istinit, petlja se ponovno izvršava. Kada vrijednost i postane veća od 10, uvjet više nije istinit te se petlja prekida. Tada se izvršenje programa nastavlja izvan tijela petlje.

Petlja do-while

Petlja do-while slična je petlji while, ali s jednom ključnom razlikom. U petlji do-while, uvjet se provjerava nakon izvršavanja tijela petlje, što znači da će se blok naredbi uvijek izvršiti barem jednom, čak i ako uvjet na početku nije ispunjen. Nakon izvršavanja bloka narebi provjerava se uvjet. Ako je uvjet ispunjen, petlja se nastavlja iznova, a ako uvjet nije ispunjen, petlja se prekida i izvršenje programa nastavlja izvan tijela petlje.

Ova vrsta petlje korisna je kada želimo osigurati izvršavanje određenog bloka naredbi barem jednom, bez obzira na početnu vrijednost uvjeta.

Kao i u prethodnim primjerima koje smo vidjeli pogledajmo ovaj za ispis brojeva od 1 do 10:

int main() {
    int i = 1;
    do {
        cout << i << endl;
        i++;
    }
    while (i <= 10);
    return 0;
}

Na početku varijabla i se inicijalizira na vrijednost 1. Nakon toga se izvršava do-while petlja. Unutar petlje, trenutna vrijednost varijable i se ispisuje na ekran. Potom se vrijednost varijable i povećava za 1 pomoću operatora inkrementa ++.

Nakon izvršenja tijela petlje, provjerava se uvjet (i <= 10). Ako je uvjet ispunjen, petlja se ponavlja i izvršava se ponovno tijelo petlje. Ovaj korak se ponavlja sve dok je vrijednost varijable i manja ili jednaka 10. Kada vrijednost varijable i postane veća od 10, petlja se prekida, a izvršenje programa nastavlja se izvan tijela petlje.

MIPS: grananje

Programi se obično izvršavaju slijedno, slijedeći redoslijed instrukcija. Međutim, ponekad želimo da program donese odluke i promijeni svoje ponašanje ovisno o određenim uvjetima. U takvim situacijama koristimo grananje.

Jedan od najčešćih načina grananja je korištenje naredbi if-else. Unutar if bloka, određeni blok koda izvršava se samo ako je uvjet istinit. U slučaju da uvjet nije istinit, program preskače taj blok i prelazi na sljedeći dio koda u else bloku.

Jednostavno grananje naredbom if u MIPS-u

Proučimo primjer jednostavnog grananja u C++ koji ispisuje apsolutnu vrijednost varijable a:

if (a < 0) {
    a = -a;
}
cout << a;

Kako bismo preveli uvjetno grananje u MIPS asemblerski jezik, ovom primjeru možemo pristupiti na dva načina:

• 1. način: okrenuti uvjet naredbe if (a >= 0)
• 2. način: korištenje više oznaka i naredbi grananja

Okrenuti uvjet naredbe if u MIPS-u

Za početak, pretpostavimo da je varijabla a pohranjena u registru $a0. U ovom slučaju, koristit ćemo instrukcije uvjetnog grananja. Uvjet naredbe if je a < 0. Kako bismo okrenuli uvjet i provjerili je li a >= 0, koristit ćemo instrukciju bgez (engl. branch if greater than or equal to zero) koja uspoređuje sadržaj registra $a0 s nulom.

Ako je sadržaj veći ili jednak nuli, program će skočiti na određenu oznaku, u ovom primjeru to je oznaka granaj. U suprotnom, izvršit će se sljedeća instrukcija sub a0, $0, $a0 koja oduzima sadržaj registra $a0 od nule i rezultat pohranjuje natrag u registar $a0. Time se postiže efekt apsolutne vrijednosti varijable a.

    bgez  $a0, granaj   # ako je $a0 >= 0 skače na oznaku granaj
    sub   $a0, $0, $a0
granaj:
    li    $v0, 1        # ispis varijable a
    syscall
    li    $v0, 10       # izlaz
    syscall

Nakon izvršavanja instrukcija unutar if bloka ili preskakanja bloka, program nastavlja s izvršavanjem instrukcija koje se nalaze nakon if naredbe. U ovom slučaju to su naredbe za ispis na konzolu i izlaz iz programa.

Korištenje više oznaka i naredbi grananja

U ovom slučaju razmatramo uvjet a < 0 koristeći instrukciju bltz (engl. branch if less than zero) koja provjerava je li vrijednost registra $a0 manja od nule. Ako je, program će skočiti na oznaku granaj i pohraniti apsolutnu vrijednost varijable a natrag u registar $a0.

    bltz   $a0, granaj   # ako je a0<0 skače na granaj
    j      nastavak      # bezuvjetno grananje; skače na nastavak
granaj:
    sub    $a0, $0, $a0
nastavak:
    li     $v0, 1        # ispis varijable a
    syscall
    li     $v0, 10       # izlaz
    syscall

U slučaju kada uvjet nije ispunjen, nastavlja se izvršavanje sljedećih instrukcija. Prva sljedeća instrukcija je bezuvjetno grananje na oznaku nastavak iza koje se izvršavaju instrukcije ispisa i izlaz iz programa.

Primjetimo kako smo u ovom slučaju dobili više oznaka i naredbi grananja nego u prvom slučaju.

if (a0 > 0) {
    v0 = t0;
}
else if (a == 0) {
    v0 = t1;
}
else {
    v0 = t2;
}

    bltz   $a0, blok1
    beqz   $a0, blok2
blok_else:
    move   $v0, $t2
    b      dalje
blok1:
    move   $v0, $t0
    b      dalje
blok2:
    move   $v0, $t1
dalje:
    #...

if (a0 > 0) {
    v0 = a0 - 3;
}
else {
    v0 = 0;
}
cout << v0;

Instrukcije uvjetnog grananja

Složeni uvjeti grananja naredbom if u MIPS-u

U MIPS asemblerskom jeziku, tzv. SET instrukcije omogućuju izračunavanje složenih uvjeta na temelju usporedbe vrijednosti registara. SET instrukcije imaju sličan format kao i uvjetno grananje, koristeći mnemonik "s" s dodanim uvjetom.

Primjerice, instrukcija slt $Rdest, $Rsrc1, $Rsrc2 (engl. set if less then) uspoređuje vrijednosti registara $Rsrc1 i $Rsrc2 te rezultat (0 ili 1) pohranjuje u registr $Rdest. U ovom slučaju 1 pohranjuje u registar $Rdest ako je Rsrc1 < $Rsrc2.

if (a0 < 0 || a0 > 100) {
    a0 = 1;
}
else {
    a0++;
}

bool t = a0 < 0 || a0 > 100;
if (t != 0) {
    a0 = 1;
}
else {
    a0++;
}

    sltz   $t1, $a0          # t1 = a0 < 0
    li     $t2, 100          # t2 = 100
    sgt    $t0, $a0, $t2     # t0 = a0 > 100
    or     $t0, $t0, $t1     # t0 = t0 || t1
    bnez   $t0, prvislucaj   # t0 ≠ 0
    addi   $a0, $a0, 1       # a0 = a0 + 1 (a0++)
    j      dalje
prvislucaj:
    li     $a0, 1            # a0 = 1
dalje:
    #...

if (a1 > 50 || a0 > 0) {
    a0 = -a0;
}
else {
    a1 = 2 * a1;
}

int a = 0;
for (int i = 1; i <= 10; i++) {
    a += i;
}
cout << a;

Instrukcije usporedbe

MIPS: petlje

Petlja do-while u MIPS-u

Najjednostavniji slučaj je petlja do-while, gdje uvjet petlje odgovara uvjetu grananja. U slučajevima petlji while i for koristimo sličan koncept kao i kod naredbe if, s okrenutim uvjetom ili više oznaka i skokova. Ako je uvjet ispunjen, tijelo petlje će se izvršiti. Za razliku od naredbe if, kod petlji imamo bezuvjetni skok na početak, odnosno provjeru uvjeta.

int a0;
do {
    cin >> a0;
} while (a0 < 0)

cout >> a0;

pocetak:
    li     $v0, 5        # unos broja
    syscall
    move   $a0, $v0      # a0 = v0
    bltz   $a0, pocetak  # skoči na oznaku pocetak ako je $a0 < 0
    li     $v0, 1        # ispis
    syscall

Petlja while u MIPS-u

int a0;
int t0 = 0;
cin >> a0;
while (a0 > 2) {
    t0++;
    a0 = a0 - 2;
}

    li    $t0, 0
    li    $v0, 5
    syscall
    move  $a0, $v0
    li    $t1, 2
uvjet:
    bgt   $a0, $t1, petlja
    j     dalje
petlja:
    addi  $t0, $t0, 1
    sub   $a0, $a0, $t1
    j     uvjet
dalje:

    li   $t0, 0
    li   $v0, 5
    syscall
    move $a0, $v0
    li   $t1, 2
uvjet:
    ble  $a0, $t1, dalje
    addi $t0, $t0, 1
    sub  $a0, $a0, $t1
    j    uvjet
dalje:

Petlja for u MIPS-u

for (int a0 = 1; a0 <= t0; a0++) {
    t0 = t0*a0;
}

int a0 = 1;
while (a0 <= t0) {
    t = t0*a0;
    a0++;
}

    li    $a0, 1
uvjet:
    bgt   $a0, $t0, dalje
    mul   $t0, $t0, $a0
    addi  $a0, $a0, 1
    j     uvjet
dalje:

Složena petlja for u MIPS-u

int s = 0;
for (int i = 0; i < n; i++) {
    s = s + v[i];
}

int s = 0;
int i = 0;
while (i < n) {
    s = s + v[i];
    i++;
}

int s = 0;
int i = 0;
int *v1 = v;      // inicijalizacija pokazivača v1 na početak niza v
for (i < n) {
    s = s + *v1;  // dodavanje vrijednosti koju pokazuje v1 na varijablu s
    v1++;         // pomicanje pokazivača v1 na sljedeći element niza
    i++;
}

    li   $s0, 0          # int s = 0
    li   $t0, 0          # int i = 0
    move $v1, $v0        # v1 = v
uvjet:
    bge  $t0, $t1, dalje
    lw   $t3, 0($v1)     # tmp = *v1
    add  $s0, $s0, $t3   # s = s + tmp
    addi $v1, $v1, 4     # v1++ zbraja 4
    addi $t0, $t0, 1     # i++
    j    uvjet
    dalje: