Анализа живих променљивих
У теорији компајлера, analiza žive promenljive (или једноставно analiza života) је класична анализа протока података које изводи компилатор за сваки тачку програма. Изводи анализу да би израчунао променљиве које би потенцијално прочитао пре следећег писања, променљиве које су живе на излазу из сваке тачке програма.
Или једноставно: промељива је živa ако садржи вредности које ће можда бити потребне у будућности.
Примери
уреди
L1: b := 3; L2: c := 5; L3: a := f(b * c); goto L1; |
Скуп живих променљивих у линији L3 је {b,c}, јер су оба коришћена у множењу, о тиме је позив функције f додељен а. Али скуп живих променљивих у линији L1 је само b како је променљива c ажурирана у линији L2. Вредност променљиве a није никада коришћена. Приметимо да f може бити стање, тако да никада-живо додељивање a може бити елиминисано, али немамо довољно информација за одлучивање о целини L3.
Изрази у једначини проточности података
уредиАнализа животне способности је анализа „може уназад”. Анализа се обавља обрнутим редоследом, и оператор спајања протока података је комплетна унија. Другим речима, уколико применимо анализу живота променљивих над функцијом са посебним бројем логичких грана, анализа се спроводи од краја функције радећи ка почетку функције (отуда „уназад”). Променљиве ће се сматрати живе ако некој од грана, крећући се напред у оквиру функције, потенцијално затреба тренутно стање променљиве (отуда „може“). Ово је контраст у односу на “мора уназад” анализу која би уместо тога примењује ово стање на свим гранама које се крећу напред. Једначине протока података дате за једноставан блок s и постојећи блок f у анализи живих променљивих је следећи:
- : Скуп променљивих које су коришћене у s пре било какве доделе.
![{\displaystyle {\mbox{GEN}}[s]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/bde42b503e6ae65f77c0c3fa767a2d0fc9b9f9a6)
- : Скуп променљивих којима је додељена вредност у s (u mnogim knjigama[појаснити], KILL(s) је такође дефинисано као скуп променљивих којима је додељена вредност у s „пре било какве употребе“, али то не мења решење једначине протока података
![{\displaystyle {\mbox{KILL}}[s]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/843c3e280d6ed7c2e7e42c116ab3fa86cbc07e41)
![{\displaystyle {\mbox{LIVE}}_{in}[s]={\mbox{GEN}}[s]\cup ({\mbox{LIVE}}_{out}[s]-{\mbox{KILL}}[s])}](https://wikimedia.org/api/rest_v1/media/math/render/svg/958512c2d6a2ecc66fe5b62c39a93c150142465b)
![{\displaystyle {\mbox{LIVE}}_{out}[final]={\emptyset }}](https://wikimedia.org/api/rest_v1/media/math/render/svg/f990ba9f96420541277fb79b42bec51be9a36e64)
![{\displaystyle {\mbox{LIVE}}_{out}[s]=\bigcup _{p\in succ[S]}{\mbox{LIVE}}_{in}[p]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/7d776b57e49909524e9cacc70e365924234637f4)
![{\displaystyle {\mbox{GEN}}[d:y\leftarrow f(x_{1},\cdots ,x_{n})]=\{x_{1},...,x_{n}\}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/3f5c01720a2c3843fa99038c8887eba960719607)
![{\displaystyle {\mbox{KILL}}[d:y\leftarrow f(x_{1},\cdots ,x_{n})]=\{y\}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/b9f993860dfa62f1c430a9b805e8684346a1d87d)
Улазно стање у блоковима је скуп променљивих које су живе у почетку блока. Излазно стање је скуп променљивих које су живе на крају блока. Излазно стање је унија улазних стања и блокова следбеника. Функција преноса изјаве се примењује тако што се праве променљиве које су писано мртве, а затим праве променљиве које се читалачки живе.
Други пример
уреди
// улаз: {}
b1: a = 3;
b = 5;
d = 4;
x = 100; //x неће бити коришћен касније, тако ни у излазном скупу {a,b,d}
if a > b then
// излаз: {a,b,d} //унија свих (улазних) наследника од b1 => b2 : {a,b}, и b3:{b,d}
// улаз: {a,b}
b2: c = a + b;
d = 2;
// излаз: {b,d}
// улаз: {b,d}
b3: endif
c = 4;
return b * d + c;
// излаз:{}
|
Улазно стање b3 садржи само b и d, пошто је c записан. Излазно стање од b1 је унија улазних стања b3 и b3. Дефиниција c у b3 може бити уклоњена, како c није жив одмах након исказа.
Решавање једначине протока података почиње иницијализацијом свих улазних стања и излазних стања у празан скуп. Радна листа је иницијализована убацивањем излазне тачке (b3) у радну листу(типично за повратнни ток). Рачун улазна стања различит од претходних, па тако њени претходници b1 и b2 су убачени и процес се наставља. Прогрес је сумиран у следећој табели:
| обрада | излазно стање | старо улазно стање | ново улазно стање | радна листа |
|---|---|---|---|---|
| {} | {} | {b,d} | (b1,b2) | |
| b1 | {b,d} | {} | {} | (b2) |
| b2 | {b,d} | {} | {a,b} | (b1) |
| b1 | {a,b,d} | {} | {} | () |
Приметимо да је b1 ушао у листу пре b2, због чега се принудно b1 два пута обрадио (b1 је поново унет као предак b1). Убацивањм b1 пре b1 дозволило би се раније завршавање.
Иницијализација са празним скупом је једна оптимистична иницијализација: све променљиве почињу као мртве. Приметимо да се излазно стање не може сузити од једне итерације до друге, иако излазно стање може бити мање од улазног стања. То можемо видети из чињенице да се након прве итерације излазно стање може само променити променом улазног стања. Како улазно стање почиње са празним скупом, може само да расте у наредним итерацијама.