Анализа протока података

Анализа протока података је техника за прикупљање података о могућем скупу вредности израчунатих у рачунарском програму. Граф контроле протока програма се користи за утврђивање оних делова програма на које се може пропагирати одређена вредност додељена променљивој. Скупљене информације се често користе од стране компилатора када оптимизују програм.

Једноставан начин за извођење анализе протока података је да се подесе једначине контроле података за сваки чвор графа контроле протока и да се реше понављајући рачунање излаза из улаза за сваки чвор све док се читав систем не стабилизује, односно све док не достигнемо фиксну тачку. Овај општи приступ је развио Гери Килдал док је предавао у Поморскoj постдипломскoj школи ^[1]

Основни принципи

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

За сваки блок б:

out_{b}=trans_{b}(in_{b})

in_{b}=join_{p\in pred_{b}}(out_{p})

У овој, $trans_{b}$ је трансфер функција блока $b$ . Она ради на улазном стању $in_{b}$ , дајући излазно стање $out_{b}$ . Операција повезивања $join$ комбинује излазна стања претпроцесора $p\in pred_{b}$ , дајући улазно стање од $b$ .

Након решавања овог скупа једначина, улаз и/или излазна стања блокова могу се користити за извођење опција (својстава) програма код граница блока. Трансфер функција сваког дела се посебно може применити за добијање информација до тачке унутар базичног блока. Сваки посебан тип анализе протока података има своју специфичну трансфер функцију и операцију повезивања. Одређени проблеми протока података захтевају инверзну анализу протока података. Ово прати исти план, осим што је трансфер функција примењена на излазном стању дајући улазно стање и што операција повезивања ради на улазним стањима потомака како би добили излазно стање. Улазна тачка игра важну улогу: С обзиром на то да нема претпроцесоре, њена улазна стања су добро дефинисана на почетку анализе. На пример, скуп локалних променљивих са познатим вредностима је празан. Ако граф контроле протока не садржи циклусе (не постоје ни имплицитна ни експлицитна) решавање једначина је једносмерно. Самим тим граф контроле протока може бити тополошки сортиран; покрећући у редоследу овог сортирања, с обзиром да су претходници већ процесирани тако да су њихова излазна стања доступна. Ако граф контроле протока садржи циклусе онда је потребан напредни алгоритам.

Итеративни алгоритам

Најчешћи начин решавања једначина токова података је коришћење итеративног алгоритма.

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

Основни алгоритам за решавање једначина токова података је следећи псеудокод:

for i ← 1 to N

иницијализуј чвор i

while (све док се скупови мењају)

for i ← 1 to N

поново компајлирај скупове за чвор i

Конвергенција

Да би био употребљив, итеративни приступ пре свега треба заправо да постигне фиксну тачку. Ово се може гарантовати наметањем ограничења на комбинацију вредности стања, функције преноса и операције спајања. За домен је битно да је неки монотони низ са коначном горњом границом. Монотоност обезбеђује да ће на свакој итерацији вредност остати иста или ће се повећавати, док ће коначна горња граница обезбедити да не може расти на неодређено време. Па из тог разлога ћемо на крају доћи до ситуације гдје је T(x) = x за свако х, што је у ствари фиксна тачка.

Важност редоследа обиласка

На ефикасност итеративног решавања једначина протока података утиче редослед обиласка у којем се посећују чворови.^[2] Штавише, то зависи од тога да ли се једначине протока података користе за анализу протока података унапред или уназад кроз граф контроле протока (ГКП). Интуитивно, у проблему са протоком података унапред, било би најбоље да сви претходници блока буду обрађени пре самог блока јер би тада у итерацији биле коришћене најновије информације. У недостатку петљи могуће је направити такав редослед блокова да се исправни излазни подаци рачунају обрадом сваког блока само једном.

У наставку се разматра неколико итеративних редоследа за решавање једначина протока података:

Случајни редослед - Овим итеративним редоследом обиласка није познато да ли једначине протока података решавају проблем протока унапред или уназад. Због тога су перформансе релативно лоше у поређењу са неким специјалним односно напредним итеративним редоследима.
Постордер - Ово је типичан итеративни редослед обиласка за проблеме протока података уназад. Чвор се посећује након што се заврши посећивање свих његових наследника. Имплементира се стратегијом „прво најдубљи“.
Обрнути постордер - Ово је типичан итеративни редослед обиласка за проблеме протока података унапред. У оваквом редоследу чвор се посети пре него што се посети било који од његових наследника осим када се достигне наследник са спољне (задње) стране.

Иницијализација

Иницијалне вредности улазних стања су важне за добијање тачних резултата. Ако се резултати користе за оптимизацију компајлера, они би требало да пруже конзервативне информације, тј. када се те информације примене, програм не би требало да мења семантику. Итерација алгоритма фиксне тачке ће узимати вредности максималних елемената. Зато иницијализација свих блокова са максималним елементом није корисна па најмање један блок почиње са стањем чија је вредност мања од максимума. Сами детаљи зависе од проблема протока података. Ако минимални елемент представља потпуно конзервативне информације, резултати се могу безбедно користити чак и током саме итерације. Фиксна тачка, у случају да представља најтачније могуће информације, се достиже пре него што се сами резултати могу применити.

Примери

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

Анализа унапред

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

  if b==4 then
     a = 5;
  else 
     a = 3;
  endif
 
  if  a < 4 then
     ...

Доступне дефиниције променљиве a у линији 7 су скуп додела a = 5 у линији 2 и a = 3 у линији 4.

Анализа уназад

Анализа тренутне променљиве израчунава за сваку тачку програма променљиве које могу потенцијално бити касније прочитане пре њиховог следећег ажурирања писања. Резултат се типично користи када се елиминише мртви део кода, тј где се уклањају делови који додељују променљивама вредности које се не користи касније. Излазно стање блока је скуп променљивих које су "живе" на крају блока. Његово улазно стање је скуп променљивих које су "живе" на самом почетку. Излазна стања су скупови улазних стања наследника. Функција преноса се примењује тако што се прво праве променљиве које су "мртве" за писање, а затим праве варијабле које су "живе" за читање.

b1: a = 3; 
    b = 5;
    d = 4;
    x = 100;
    if a > b then
b2:    c = a + b;
       d = 2;
b3: endif
    c = 4;
    return b * d + c;

Анализа уназад:

// in: {}
b1: a = 3; 
    b = 5;
    d = 4;
    x = 100; //x се касније не користи па зато није у спољном скупу {a, b,d}
    if a > b then
// out: {a, b,d}    //унија свих улазних стања наследника b1 => b2: {a, b}, и b3:{b, d}  

// in: {a, b}
b2: c = a + b;
    d = 2;
// out: {b, d}

// in: {b, d}
b3: endif
    c = 4;
    return b * d + c;
// out:{}

Улазно стање b3 садржи само b и d, будући да је c већ написан. Излазно стање b1 је унија улазних стања b2 и b3. Дефиниција c променљиве у b2 се може уклонити, јер c није живо одмах након ицказа.

Решавање једначина протока података почиње са иницијализацијом свих улазних и излазних стања у празне скупове. Радна листа се иницијализује убацивањем излазног стања (b3) (ово је типично за проток уназад). Његова рачунања улазних стања се разликују од претходних; претходници b1 и b2 су убачени па се процес наставља и он је сумиран у доњој табели.

обрада	излазно стање	старо улазно стање	ново улазно стање	радна листа
b3	{}	{}	{b, d}	(b1, b2)
b1	{b, d}	{}	{}	(b2)
b2	{b, d}	{}	{a, b}	(b1)
b1	{a, b,d}	{}	{}	()

Имајте на уму да је b1 унет у листу пре b2, чиме је b1 двапут обрађено (b1 је поново унет као претходник b1). Убацивање b2 пре b1 би омогућило раније извршавање.

Иницијализација са празним скупом је оптимистичка иницијализација: све променљиве почињу као мртве. Такође, излазна стања се не могу смањити између две итерације, иако излазна стања могу бити мања од улазних. Ово се може видети из чињенице да се после прве итерације излазно стање може променити само променом улазног стања. Будући да се улазно стање иницијализује па самим тим и почиње као празан скуп, оно може само расти у даљим итерацијама.

Другачији приступи

Маркус Монен је 2002. године описао нову методу анализе протока података која не захтева експлицитну конструкцију графа протока података^[3], већ се ослања на апстрактној интерпретацији програма и одржавању радног скупа бројача програма. У свакој условној грани, оба опције се додају у радни скуп. Свака путања се прати са што је могуће више инструкција (до краја програма или док има промена), а затим се уклоне из скупа након чега се позива следећи бројач програма. Комбинација анализе протока и анализе тока података се показала као веома корисна и комплементарна у идентификацији кохезивних делова изворног кода имплементирајући функционалности система (нпр. карактеристике, захтеви).^[4]

Референце

^ Kildall, Gary Arlen (1973). „A Unified Approach to Global Program Optimization”. Proceedings of the 1st Annual ACM SIGACT-SIGPLAN Symposium on Principles of Programming Languages: 194—206. doi:10.1145/512927.512945. Приступљено 20. 11. 2006.
^ Cooper, Keith D.; Harvey, Timothy J.; Kennedy, Ken (26. 3. 2004) [November 2002]. „Iterative Data-Flow Analysis, Revisited” (PDF). PLDI 2003. ACM. TR04-432. Приступљено 1. 7. 2017. ^{[мртва веза]}
^ Mohnen, Markus (2002). „A Graph-Free Approach to Data-Flow Analysis”. Lecture Notes in Computer Science. Lecture Notes in Computer Science. 2304: 185—213. ISBN 978-3-540-43369-9. doi:10.1007/3-540-45937-5_6. Архивирано из оригинала 02. 01. 2011. г. Приступљено 02. 12. 2008.
^ Kuang, Hongyu; Mäder, Patrick; Hu, Hao; Ghabi, Achraf; Huang, LiGuo; Lü, Jian; Egyed, Alexander (01. 11. 2015). „Can method data dependencies support the assessment of traceability between requirements and source code?”. Journal of Software: Evolution and Process. 27 (11): 838—866. ISSN 2047-7481. doi:10.1002/smr.1736.

Литература

Cooper, Keith D.; Torczon, Linda (2003) [2002-01-01]. Engineering a Compiler. Morgan Kaufmann. ISBN 978-1-55860-698-2.
Muchnick, Steven Stanley (1997). Advanced Compiler Design and Implementation. Morgan Kaufmann Publishers. ISBN 978-1-55860-320-2.
Hecht, Matthew S. (1977). Flow Analysis of Computer Programs. Programming Languages Series. 5. Elsevier North-Holland Inc. ISBN 978-0-444-00210-5.
Khedker, Uday P.; Sanyal, Amitabha; Karkare, Bageshri (2009). Data Flow Analysis: Theory and Practice. CRC Press (Taylor and Francis Group).
Nielson, Flemming; Nielson, Hanne Riis; Hankin, Chris (2005). Principles of Program Analysis. Springer Science+Business Media.

[1] Kildall, Gary Arlen (1973). „A Unified Approach to Global Program Optimization”. Proceedings of the 1st Annual ACM SIGACT-SIGPLAN Symposium on Principles of Programming Languages: 194—206. doi:10.1145/512927.512945. Приступљено 20. 11. 2006.

[2] Cooper, Keith D.; Harvey, Timothy J.; Kennedy, Ken (26. 3. 2004) [November 2002]. „Iterative Data-Flow Analysis, Revisited” (PDF). PLDI 2003. ACM. TR04-432. Приступљено 1. 7. 2017. ^{[мртва веза]}

[3] Mohnen, Markus (2002). „A Graph-Free Approach to Data-Flow Analysis”. Lecture Notes in Computer Science. Lecture Notes in Computer Science. 2304: 185—213. ISBN 978-3-540-43369-9. doi:10.1007/3-540-45937-5_6. Архивирано из оригинала 02. 01. 2011. г. Приступљено 02. 12. 2008.

[4] Kuang, Hongyu; Mäder, Patrick; Hu, Hao; Ghabi, Achraf; Huang, LiGuo; Lü, Jian; Egyed, Alexander (01. 11. 2015). „Can method data dependencies support the assessment of traceability between requirements and source code?”. Journal of Software: Evolution and Process. 27 (11): 838—866. ISSN 2047-7481. doi:10.1002/smr.1736.

[1]

[2]

[3]

[4]