Анализа алијаса

Анализа алијаса је техника у теорији компајлера, која се користи за одређивање да ли се локацији за складиштење може приступити на више начина. За два показивача се каже да су алијаси ако указују на исту локацију.

Технике анализе алијаса се обично класификују по осетљивости протока и осетљивости контекста. Оне могу одредити може бити алијас (may-alias) или мора бити алијас (must-alias) информације. Термин анализа алијаса се често користи као синоним за показиваче анaлизатора, специфичан случај.

Анализатори алијаса намеравају да направе и израчунају корисне информације за разумевање алијаса у програмима.

Преглед

Генерално, анализа алијаса одређује да ли или не засебне меморијске референце указују на исто подручје меморије. Ово омогућава компајлеру да утврди које варијабле у програму ће бити под утицајем изјаве. На пример, размотрите следећи део кода који приступа члановима структура:

p.foo = 1;
q.foo = 2;
i = p.foo + 3;

Постоје 3 могућа случаја алијаса овде:

1. Променљиве p и q не могу бити алијаси .
2. Променљиве p и q морају бити алијаси.
3. То се не може са сигурношћу утврдити у тренутку превођења ако су  p и q алијаси или не.

Ако p и q не могу бити алијаси, онда i = p.foo + 3; може бити промењено у  i = 4. Ако p и q морају бити алијасу, онда i = p.foo + 3; може бити промењено у  i = 5. У оба случаја, омогућено нам је да изводимо оптимизације помоћу знања алијаса. Са друге стране, ако се не зна да ли су p и q алијаси или не, онда ниједна оптимизација не може бити изведена и цео код мора бити извршен да би се добио резултат. За 2 референце меморије се каже да имају may-алијас релацију ако је њихов алијас непознат.

Представљање анализа алијаса

У анализи алијаса, делимо меморију програма у класе алијаса. Класе алијаса су раздвојени скупови локација које не могу бити алијас једни другима. За расправу овде, претпоставља се да се оптимизације урађене овде јављају на ниском нивоу средњег представљања програма. За ово се каже да је програм састављен у бинарне операције, скаче, креће се између регистара, креће од регистара до меморије, креће из меморије до регистара, грана, и функција позиви / повратак.

Анализе алијаса засноване на типовима

Ако је језик који се саставио  типа безбедан, чек компајлерског типа је исправан, а језик нема способност да створи показиваче који упућују на локалне променљиве, (као што су ML, Haskell, или Java) онда се могу упућивати неке корисне оптимизације. Постоје многи случајеви у којима знамо да  две меморијске локације морају бити у различитим класама алијаса:

1. Две променљиве различитих типова не могу бити у истој класи алијаса јер је власништво снажно одређено, меморије без позивања (тј. позивања на меморијским локацијама не могу бити директно мењана) језика тако да две променљиве различитих типова не могу истовремено да деле исту меморијску локацију.
2. Издвајања локалних на тренутни стек оквир не могу бити у истој класи алијаса као и било која претходна расподела из другог стек оквира. То је случај, јер нова меморијска издвајања морају бити раздвојена од свих других меморијских издвајања.
3. Сваки запис поља од сваке врсте записа има своју класу алијаса, генерално, јер дисциплина куцања дозвољава обично само евиденцију исте врсте алијаса. Пошто ће сви записи о типу бити чувани у идентичном формату у меморији, поље може бити алијас само себи.
4. Слично томе, сваки спектар датог типа има свој класу алијаса.

Када се изводи анализа алијаса за код, свако учитавање и складиштење на меморију треба бити означено са својом класом. Онда имамо корисну особину, која даје локације меморије $A_{i}$ и $B_{j}$ са $i,j$ класама алијаса, тако да ако је $i=j$ онда $A_{i}$ may-алијас $B_{j}$, и ако $i\neq j$ онда локације меморије неће бити алијас.

Анализе алијаса засноване на току

Анализе засноване на току, за разлику од анализа заснованих на типу, се могу применити на програме на језику са референцама или типовима са распоређеним улогама . Анализе засноване на току се могу користити уместо или као додатак анализама заснованим на типу. У анализи на бази протока, нове класе алијаса се стварају за сваку доделу локације у меморији, као и за сваку глобалну и локалну променљиву чија адреса је коришћена. Референце могу да укажу на више од једне вредности током времена и тај начин може бити у више од једног алијаса класе. То значи да сваки меморијски простор има сет алијаса класе уместо једне алијас класе.

Види још

• Анализа излаза
• Анализа показивача
• Анализа облика

Литература

• Appel, Andrew W. (1998). Modern Compiler Implementation in ML. Cambridge, UK: Cambridge University Press. ISBN 978-0-521-60764-3. 

Спољашње везе

• Библиотека анализе алијаса - Једноставна С библиотека за имплементацију анализа алијаса и магистарски рад који даје увод у област.