Seti-Ulmanov algoritam

U računarstvu, Seti-Ulmanov algoritam je algoritam za prevođenje sintaksnog drveta u mašinski kod, koji koristi što je moguće manji broj instrukcija. Imenovan je po svojim izumiteljima, Ravi Setiju i Džefri D. Ulmanu.

Pregled

Kada generiše kod za aritmetički izraz, kompajler mora da odluči koji je najbolji način da prevede izraz u terminima broja korišćenih instrukcija, kao i broja registara koji su potrebni kako bi se procenilo neko podstablo. Naročito u slučaju kada slobodnih registara ima malo, red u kome se vrši procena može biti važan zbog dužine generisanog koda, zato što različit poredak može dovesti do "curenja" međuvrednosti u memoriju. Seti-Ulmanov algoritam, (takođe poznat kao Seti-Ulmanovo nabrajanje) proizvodi kod koji ima najmanji mogući broj instrukcija kao i najmanji broj skladišnih registara (pod pretpostavkom da se komutativnost i asocijativnost primenjuju na operatore koji se koriste, ali da zakon distribucije npr. $a*b+a*c=a*(b+c)$ ne važi). Primetićete da algoritam uspeva iako ni komutativnost ni asocijativnost ne važe za zadati izraz, i stoga, aritmetičke transformacije se ne mogu primeniti.

Jednostavni Seti-Ulmanov algoritam

Jednostavni Seti-Ulmanov algoritam radi kao što je navedeno (za RISK arhitekturu):

1. Obiđi apstraktno sintaksno stablo u prefiksnom ili postfiksnom redosledu
   1. Svakom nekonstantnom čvoru koji je list, dodeli 1 (drugim rečima, 1 registar je potreban da čuva promenljivu/polje/itd.). Svakom konstantnom čvoru koji je list (RHS operacije – literali, vrednosti), dodeli 0.
   2. Svakom čvoru koji nije list n, dodeli broj registara koji je potreban da se proceni odgovarajuće podstablo od n. Ako broj registara potrebnih u levom podstablu (l) nije jednak broju registara koji su potrebni u desnom podstablu (r), broj registara potrebnih za trenutni čvor n je maksimum(l, r). Ako je l == r, onda je broj registara potrebnih za trenutni čvor l + 1.
2. Širenje koda
   1. Ako je broj registara koji je potreban za računanje levog podstabla čvora n veći od broja registara za desno podstablo, onda se levo podstablo prvo procenjuje (pošto je moguće da taj jedan registar koji je potreban desnom podstablu da čuva rezultat čini da levo podstablo curi). Ako je desnom podstablu potrebno više registara nego levom podstablu, desno podstablo se procenjuje prvo. Ako oba podstabla zahtevaju podjednako registara, onda je redosled procene nebitan.

Primer

Za aritmetički izraz $a=(b+c+f*g)*(d+3)$, apstraktno sintaksno stablo izgleda ovako:

               =
              / \
             a   *
                / \
               /   \
              +     +
             / \   / \
            /   \ d   3
           +     *
          / \   / \
         b   c f   g

Da bi nastavili sa algoritmom, potrebno je samo da ispitamo aritmetičke operacije $(b+c+f*g)*(d+3)$, drugim rečima potrebno je samo da gledamo na desno podstablo od znaka '=':

               *
              / \
             /   \
            +     +
           / \   / \
          /   \ d   3
         +     *
        / \   / \
       b   c f   g

Sada počinje obilazak stabla (u prefiksnom redosledu), dodeljujemo broj registara potrebnih kako bi se procenila oba podstabla (primetiti da je poslednji sabirak u izrazu $(b+c+f*g)*(d+3)$ konstanta):

               *2
              / \
             /   \
            +2    +1
           / \   / \
          /   \ d1  30
         +1   *1
        / \   / \
       b1  c0f1  g0

Iz ovog stabla može se videti da je potrebno još 2 registra za računanje levog podstabla '*', a samo 1 registar za računanje desnog podstabla. Čvorovima 'c' i 'g' nisu potrebni registri iz sledećih razloga: Ako je T stablo list, onda broj registara za izračunavanje T je 1 ili 0 što zavisi od toga da li je T levo ili desno podstablo (pošto operacija kao što je add R1, A može da obradi desnu komponentu A bez direktnog ubacivanja u registar). Stoga, trebalo bi proizvesti kod prvo iz levog podstabla, zato što se može dospeti u situaciju da postoje samo 2 slobodna registra za računanje celog izraza. Ako je prvo izračunato desno podstablo (kome je potreban samo jedan registar), bio bi potreban registar da čuva rezultat desnog podstabla dok se izračunava levo podstablo (kome bi opet bilo potrebno 2 registra), stoga je potrebno 3 registra istovremeno. Izračunavanje prvo levo podstabla zahteva 2 registra, ali se rezultat može čuvati u jednom, i pošto je desnom podstablu potreban samo 1 registar za izračunavanje, računanje izraza se može odraditi samo sa preostala 2 registra.

Napredni Seti-Ulmanov algoritam

U naprednoj verziji Seti-Ulmanovog algoritma, aritmetičke operacije se prvo transformišu, koristeći algebarska svojstva korišćenih operatora.

Literatura

• Sethi, Ravi; Ullman, Jeffrey D. (1970), „The Generation of Optimal Code for Arithmetic Expressions”, Journal of the Association for Computing Machinery, 17 (4): 715—728, doi:10.1145/321607.321620 .

Vidi još

• Stralerov broj, minimalni broj registara koji su potrebni kako bi se izračunao izraz bez spoljašnjeg prostora

Spoljašnje veze

• Code Generation for Trees Arhivirano na sajtu Wayback Machine (17. jul 2012)