Доступност израза

Израз $e$ је доступан на чвору $n$ графичке репрезентације програма ако је његова вредност претходно израчуната а затим није поништена ( ниједан од операнада израза $e$ није модификован ) дуж сваке путање до чвора $n$.

Мотивација

Програми могу садржати код чији је резултат потребан, али у коме је одређено рачунање заправо сувишно понављање ранијег рачунања унутар истог програма. Концепт доступности израза ( енг. еxпрессион аваилабилитy) је користан у решавању овакве ситуације.

Сваки програм садржи коначан број израза, тако да можемо говорити о скупу свих израза једног програма.

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

Скуп израза горе наведеног програма је { $x*y,s+t,u/v$ }.

Доступност

Доступност је дата-флоw својство израза. При свакој инструкцији, сваки израз у програму је или доступан или недоступан. Због тога, обично разматрамо доступност из перспективе инструкције: свака инструкција тј. чвор графицке репрезентације програма (енг. ноде оф тхе флоwграпх) има придружен скуп доступних израза. Тако је скуп достуних израза у чвору 3 горе наведеног кода {${x*y,s+t}$}

Ми желимо да знамо који изрази су дефинитивно доступни (тј.већ израчунати) за одређену инструкцију. Размотрићемо разлику између семантичке и синтаксне доступнсти израза, и детаља апроксимације које настојимо да откријемо анализом.

Израз је семантички доступан на чвору $m$ графицке репрезентације програма ако се његова вредност израцуна (а затим не поништава) дуж сваке извршне секвенце програма која се завршава на $n$.

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

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

Израз је синтаксно доступан на чвору $n$ ако се његова вредност израчунава (а затим не понистава) дуз сваког пута од уласка у графичку репрезентацију програма па све до чвора $n$. Семантичка доступност се бави извршним понашањем програма, док се синтаксна доступност бави синтаксном структуром програма.

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

Гледано семантички, један од горе наведених услова ће бити тачан, па на свакој извршној путањи графичке репрезентације горе наведеног кода, $x+y$  се израчунава два пута. Поновно рачунање $x+y$ је сувишно.

Анализа доступности израза

Прво ћемо разматрати више интуитувну презентацију, а онда ћемо је мало изменити до еквилалентне стандардне презентације анализе доступности израза(енг. Аваилабе еxпрессион аналисyс ).

Доступност израза пролонгира кроз програм. Свака инструкција утиче на скуп доступних израза. Инструкција чини израз доступним када генерише (израчунава) његову тренутну вредност.

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}

Инструкција чини израз недоступним када убија (поништава) његову тренутну вредност.

//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
//{}

Даље ћемо посматрати функције $gen(n)$ и $kill(n)$ које дају редом скупове израза генерисаних и поништених инструкцијом на чвору $n$. Редефинисање варијабле $x$ убија све изразе у програму који садрже појаве $x$.

У наставку, $E_{x}$је скуп израза који у програму садрже појаве варијабле $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}$

Како доступност тече даље кроз программ мимо инструкције, ми желимо да модификујемо  скуп доступних израза додавањем било којих израза које та инструкција генерише (они постају доступни) и уклањањем свих које убија (они постају недоступни).

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

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

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

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

$\downarrow {y+1}$

У случају да инструкција и генерише и убија изразе, ми морамо уколнити убијене изразе након додавања генерисаних.

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

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

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

За скупове који су доступни непосредно пре $(in-avail(n))$ и непосредно после $(out-avail(n))$ чвора $n$, следећа једначина мора да важи:

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

Пример:

$\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\}$

Када чвор $n$ има једног претходника $m$, очекивано ће важити ${\textstyle in-avail(n)=out-avail(m)}$. А када има неколико претходника, изрази доступни на улазу тог цвора  су  управо они изрази доступни на излазу свих његових претходника.

Дата-флоw једначине

Ово су дата-флоw једначине за анализу доступног израза, и оне нам говоре све што треба да знамо о томе како ширити(попагирати) информације о располозивости кроз програм.

$$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)$,

где је $pred(n)=\{n'|(n,n')\in edges(G)\}.$

Комбинацијом ове две једнакости долазимо до уопштене једначине доступности (енг. аваилабилитy еqуатион).

$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}}$

Функције и једначине које су представљене до сада су тачне, и њихове дефиниције су поприлично интуитивне. Ипак, мозда ћемо желети да дата-флоw једначине буду у облику који се ближи оном код ЛВА (енг. Ливе вариабле аналyсис) једначина, и тако лакше уочити сличност између ове две анализе. Неколико модификација је неопходно да би се ово постигло.

Најпре ћемо увести следеће две дефиниције:

• Чвор генереише израз $e$ ако мора да израчуна вредност $e$ и затим  не редифинисе било коју варијаблу која се јавља у $e$.

• Цвор убија израз $e$ ако може редефинисати неке од варијабли које се јављају у $e$ и затим не реизрачунава вредност $e$.

Будући да нове дефиниције узимају у обзир које све изразе чвор генерише (искљуцујучи оне који су генерисани само да би одмах потом били убијени), ми можемо пропагирати информације доступности кроз чвор тако што ћемо уколнити убијене изразе пре додавања генерисаних, бас као и у ЛВА (енг. Ливе вариабле аналyсис).

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

Из ове нове једначине за $out-avail(n)$ мошемо извести финалну дата-флоw једначину:

$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}}$

Алгоритам

Користићемо низ $avail[\ ]$ да чувамо доступне изразе за сваки чвор програма. Иницијализујемо $avail[\ ]$ тако да сваки чвор има све изразе доступне. Поново примењујемо дата-флоw једначину на сваком чвору док $avail[\ ]$ не престане да се мења.$$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))$

Претпоставимо да графичка репрепентација програма има само један улазни чвор ( први чвор у низу $avail[\ ]$ ). Онда $avail[1]$ можемо иницијализовати на празан скуп, и неће бити потребе да поново израчунавамо доступност на првом чвору током сваке итерације.

$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))$

Овај алгоритам ће се гарантовано прекинути будући да је ефекат једног понављања монотон (само уклања изразе из скупа доступних израза) и празан скуп доступних израза не мозе бити мање кардиналности. Свако решење дата-флоw једначине је безбедно, али овај алгоритам гарантовано даје највеће (и стога најпрецизније) решење.

Напомена о имплементацији:

• Ако уредимо наш програм тако да се сваки задатак додељује посебној варијабли, можемо избројати ове привремене варијабле и изразе чије су вредности њима додељене. Ако програм има $n$ таквих израза, можемо имплементирати сваки елемент низа $avail[]$ као $n$-битну вредност, где $m$-ти бит представља доступност израза броја м.
• Опет, можемо да чувамо доступност једном по основном блоку (енг. басиц блоцк) и реизрачунати унутар блока када је потребно. Ако је дато да сваки основни блок $n$ садржи $k_{n}$ инструкције $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}]))$

Резиме

• Доступност израза је дата-флоw својство
• Анализа доступних израза(АВАИЛ) је напредна дата-флоw анализа за одређивање доступности израза
• АВАИЛ се може изразити као пар комплементарних дата-флоw јендначина, које се могу комбиновати
• Једноставан итертиван алгоритам може се користити за проналажење највећег скупа ресења за АВАИЛ дата-флоw једначину

Литература

• Стуарт, Том (2006). Аваилабле еxпрессион аналyсис (ПДФ). Университy оф Цамбриаге.