Dostupnost izraza

Izraz $e$ je dostupan na čvoru $n$ grafičke reprezentacije programa ako je njegova vrednost prethodno izračunata a zatim nije poništena ( nijedan od operanada izraza $e$ nije modifikovan ) duž svake putanje do čvora $n$.

Motivacija

Programi mogu sadržati kod čiji je rezultat potreban, ali u kome je određeno računanje zapravo suvišno ponavljanje ranijeg računanja unutar istog programa. Koncept dostupnosti izraza ( eng. expression availability) je koristan u rešavanju ovakve situacije.

Svaki program sadrži konačan broj izraza, tako da možemo govoriti o skupu svih izraza jednog programa.

int z=x*y;
print s+t;
int w= u/v;

Skup izraza gore navedenog programa je { $x*y,s+t,u/v$ }.

Dostupnost

Dostupnost je data-flow svojstvo izraza. Pri svakoj instrukciji, svaki izraz u programu je ili dostupan ili nedostupan. Zbog toga, obično razmatramo dostupnost iz perspektive instrukcije: svaka instrukcija tj. čvor graficke reprezentacije programa (eng. node of the flowgraph) ima pridružen skup dostupnih izraza. Tako je skup dostunih izraza u čvoru 3 gore navedenog koda {${x*y,s+t}$}

Mi želimo da znamo koji izrazi su definitivno dostupni (tj.već izračunati) za određenu instrukciju. Razmotrićemo razliku između semantičke i sintaksne dostupnsti izraza, i detalja aproksimacije koje nastojimo da otkrijemo analizom.

Izraz je semantički dostupan na čvoru $m$ graficke reprezentacije programa ako se njegova vrednost izracuna (a zatim ne poništava) duž svake izvršne sekvence programa koja se završava na $n$.

int x= y*z;
.
.
.
return y*z; //y*z AVAILABLE

int x=y*z;
.
.
.
y=a+b;
.
.
.
return y*z; //y*z UNAVAILABLE

Izraz je sintaksno dostupan na čvoru $n$ ako se njegova vrednost izračunava (a zatim ne ponistava) duz svakog puta od ulaska u grafičku reprezentaciju programa pa sve do čvora $n$. Semantička dostupnost se bavi izvršnim ponašanjem programa, dok se sintaksna dostupnost bavi sintaksnom strukturom programa.

if ((x+1)*(x+1) == y) {
  s = x + y;
}
if (x*x + 2*x + 1 != y) {
  t = x + y;
}
return x+y; // x+y AVAILABLE

Gledano semantički, jedan od gore navedenih uslova će biti tačan, pa na svakoj izvršnoj putanji grafičke reprezentacije gore navedenog koda, $x+y$  se izračunava dva puta. Ponovno računanje $x+y$ je suvišno.

Analiza dostupnosti izraza

Prvo ćemo razmatrati više intuituvnu prezentaciju, a onda ćemo je malo izmeniti do ekvilalentne standardne prezentacije analize dostupnosti izraza(eng. Availabe expression analisys ).

Dostupnost izraza prolongira kroz program. Svaka instrukcija utiče na skup dostupnih izraza. Instrukcija čini izraz dostupnim kada generiše (izračunava) njegovu trenutnu vrednost.

int a,b;
// {} skup dostupnih izraza je prazan
print a*b; // generate a*b
// {a*b}
c = d+1; // generate d+1
// {a*b,d+1}
e=f/g; // generate e/g
//{a*b,d+1,f/g}

Instrukcija čini izraz nedostupnim kada ubija (poništava) njegovu trenutnu vrednost.

//pretpostavimo da je do ovog dela koda skup dostupnih izraza {a*b,c+1,d/e,d-1}
a=7; // kill a*b
//{c+1,d/e,d-1}
c=11; //kill c+1
//{d/e,d-1}
d=13; //kill d/e,d-1
//{}

Dalje ćemo posmatrati funkcije $gen(n)$ i $kill(n)$ koje daju redom skupove izraza generisanih i poništenih instrukcijom na čvoru $n$. Redefinisanje varijable $x$ ubija sve izraze u programu koji sadrže pojave $x$.

U nastavku, $E_{x}$je skup izraza koji u programu sadrže pojave varijable $x$.

$$gen(x=3)=\{\}\qquad gen(print\ x=1)=\{x+1\}$$

$kill(x=3)=E_{x}\quad kill(print\ x+1)=\{\}$

$gen(x=x+y)=\{x+y\}$

$kill(x=x+y)=E_{x}$

Kako dostupnost teče dalje kroz programm mimo instrukcije, mi želimo da modifikujemo  skup dostupnih izraza dodavanjem bilo kojih izraza koje ta instrukcija generiše (oni postaju dostupni) i uklanjanjem svih koje ubija (oni postaju nedostupni).

$\downarrow \ \ \ \{y+1\}$

$gen(print\ x+1)=\{x+1\}$

$\downarrow \ \ \ \{x+1,y+1\}$

$kill(x=3)=E_{x}$

$\downarrow {y+1}$

U slučaju da instrukcija i generiše i ubija izraze, mi moramo ukolniti ubijene izraze nakon dodavanja generisanih.

$\downarrow \ \ \ \{x+1,y+1\}$

$x=x+y$ $\ \ \ \ \ \ gen(x=x+y)=\{x+y\}$ , $kil(x=x+y)=E_{x}$

$\downarrow \ \ \ \{y+1\}$

Za skupove koji su dostupni neposredno pre $(in-avail(n))$ i neposredno posle $(out-avail(n))$ čvora $n$, sledeća jednačina mora da važi:

$(out-avail(n))={\biggl (}(in-avail(n))\cup gen(n{\biggr )}\backslash kill(n)$

Primer:

$\downarrow \ \ \ \ in-avail(n)=\{x+1,y+1\}$

$n:\ \ x=x+y$

$\downarrow \ \ \ \ out-avail(n)=(in-avail(n)\cup gen(n))\backslash kill(n)=(\{x+1,y+1\}\cup \{x+y\})\backslash \{x+1,x+y\}=\{y+1\}$

Kada čvor $n$ ima jednog prethodnika $m$, očekivano će važiti ${\textstyle in-avail(n)=out-avail(m)}$. A kada ima nekoliko prethodnika, izrazi dostupni na ulazu tog cvora  su  upravo oni izrazi dostupni na izlazu svih njegovih prethodnika.

Data-flow jednačine

Ovo su data-flow jednačine za analizu dostupnog izraza, i one nam govore sve što treba da znamo o tome kako širiti(popagirati) informacije o raspolozivosti kroz program.

$$in-avail(n)=\bigcap _{p\ \epsilon \ pred(n)}out-avail(p)$$

$out-avail(n)={\biggl (}(in-avail(n))\cup gen(n{\biggr )}\backslash kill(n)$,

gde je $pred(n)=\{n'|(n,n')\in edges(G)\}.$

Kombinacijom ove dve jednakosti dolazimo do uopštene jednačine dostupnosti (eng. availability equation).

$avail(n)={\begin{cases}\bigcap _{p\ \epsilon \ pred(n)}{\biggl (}(avail(p)\cup gen(p))\backslash kill(p){\biggr )},&{\text{if }}pred(n)\neq \{\}\\\{\},&{\text{if }}pred(n)=\{\}\end{cases}}$

Funkcije i jednačine koje su predstavljene do sada su tačne, i njihove definicije su poprilično intuitivne. Ipak, mozda ćemo želeti da data-flow jednačine budu u obliku koji se bliži onom kod LVA (eng. Live variable analysis) jednačina, i tako lakše uočiti sličnost između ove dve analize. Nekoliko modifikacija je neophodno da bi se ovo postiglo.

Najpre ćemo uvesti sledeće dve definicije:

• Čvor genereiše izraz $e$ ako mora da izračuna vrednost $e$ i zatim  ne redifinise bilo koju varijablu koja se javlja u $e$.

• Cvor ubija izraz $e$ ako može redefinisati neke od varijabli koje se javljaju u $e$ i zatim ne reizračunava vrednost $e$.

Budući da nove definicije uzimaju u obzir koje sve izraze čvor generiše (iskljucujuči one koji su generisani samo da bi odmah potom bili ubijeni), mi možemo propagirati informacije dostupnosti kroz čvor tako što ćemo ukolniti ubijene izraze pre dodavanja generisanih, bas kao i u LVA (eng. Live variable analysis).

$out-avail(n)={\biggl (}in-avail(n)\backslash kill(n){\biggr )}\cup gen(n)$

Iz ove nove jednačine za $out-avail(n)$ mošemo izvesti finalnu data-flow jednačinu:

$avail(n)={\begin{cases}\bigcap _{p\ \epsilon \ pred(n)}{\biggl (}(avail(p)\backslash kill(p))\cup gen(p){\biggr )},&{\text{if }}pred(n)\neq \{\}\\\{\},&{\text{if }}pred(n)=\{\}\end{cases}}$

Algoritam

Koristićemo niz $avail[\ ]$ da čuvamo dostupne izraze za svaki čvor programa. Inicijalizujemo $avail[\ ]$ tako da svaki čvor ima sve izraze dostupne. Ponovo primenjujemo data-flow jednačinu na svakom čvoru dok $avail[\ ]$ ne prestane da se menja.

$$for\ \ i=1\ \ to\ n\ do\ avail[i]\ :=\ U$$

$\quad while\ (\ avail[\ ]\ changes)\ do$

$\quad \quad for\ i=1\ to\ n\ do$

$\quad \quad \quad avail[\ n\ ]\ :=\ \bigcap _{p\ \in \ pred(i)}((avail[\ p\ ]\setminus kill(p))\ \bigcup \ gen(p))$

Pretpostavimo da grafička reprepentacija programa ima samo jedan ulazni čvor ( prvi čvor u nizu $avail[\ ]$ ). Onda $avail[1]$ možemo inicijalizovati na prazan skup, i neće biti potrebe da ponovo izračunavamo dostupnost na prvom čvoru tokom svake iteracije.

$avail\ [1]\ :=\{\}$

$for\ \ i=2\ \ to\ n\ do\ avail[i]\ :=\ U$

$while\ (\ avail[\ ]\ changes)\ do$

$\quad \quad for\ i=2\ to\ n\ do$

$\quad \quad \quad avail[\ n\ ]\ :=\ \bigcap _{p\ \in \ pred(i)}((avail[\ p\ ]\setminus kill(p))\ \bigcup \ gen(p))$

Ovaj algoritam će se garantovano prekinuti budući da je efekat jednog ponavljanja monoton (samo uklanja izraze iz skupa dostupnih izraza) i prazan skup dostupnih izraza ne moze biti manje kardinalnosti. Svako rešenje data-flow jednačine je bezbedno, ali ovaj algoritam garantovano daje najveće (i stoga najpreciznije) rešenje.

Napomena o implementaciji:

• Ako uredimo naš program tako da se svaki zadatak dodeljuje posebnoj varijabli, možemo izbrojati ove privremene varijable i izraze čije su vrednosti njima dodeljene. Ako program ima $n$ takvih izraza, možemo implementirati svaki element niza $avail[]$ kao $n$-bitnu vrednost, gde $m$-ti bit predstavlja dostupnost izraza broja m.
• Opet, možemo da čuvamo dostupnost jednom po osnovnom bloku (eng. basic block) i reizračunati unutar bloka kada je potrebno. Ako je dato da svaki osnovni blok $n$ sadrži $k_{n}$ instrukcije $n[1],...,n[k_{n}]:$

$\quad \quad \quad avail[\ n\ ]\ :=\ \bigcap _{p\ \in \ pred(i)}((avail[\ p\ ]\setminus kill(p[1]))\cup gen(p[1])...\setminus kill(p[k_{p}])\cup gen(p[k_{p}]))$

Rezime

• Dostupnost izraza je data-flow svojstvo
• Analiza dostupnih izraza(AVAIL) je napredna data-flow analiza za određivanje dostupnosti izraza
• AVAIL se može izraziti kao par komplementarnih data-flow jendnačina, koje se mogu kombinovati
• Jednostavan itertivan algoritam može se koristiti za pronalaženje najvećeg skupa resenja za AVAIL data-flow jednačinu

Literatura

• Stuart, Tom (2006). Available expression analysis (PDF). University of Cambriage.