Анализа зависности

У теорији компајлирања, анализа зависности даје ред извршења ограничен између израза/инструкција. Уопштено говорећи, израз S2 зависи од S1 ако S1 мора да се изврши пре S2. Уопштено, постоје две класе зависности - контролна зависност и зависност података.

Анализа зависности одређује да ли је или није сигурно да преуреди или да парализује изразе.

Анализа зависности

Анализа зависности је ситуација у којој се изврши инструкција програма уколико су претходне инструкције процењене на начин који дозвољава њихово извршавање. Следи пример такве једне анализе зависности:

S1       if x > 2 goto L1
S2       y := 3   
S3   L1: z := y + 1

У овом примеру, S2 се покреће једино ако је услов у S1 погрешан.

Зависност података

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

Проточна(Стварна) зависност

Израз S2 је проточна зависност на S1 (пише се $S1\ \delta ^{f}\ S2$) ако и само ако S1 модификује ресурс који S2 чита и у извршавању S1 претходи S2. Следи пример проточне (стварне) зависности (RAW: Read After Write):

S1       x := 10
S2       y := x + c

Антизависност

Израз S2 је антизависан на S1 (пише се $S1\ \delta ^{a}\ S2$) ако и само ако S2 модификује ресурс који S1 чита и у извршавању S1 претходи S2. Следи један пример антизависности (WAR: Write After Read):

S1       x := y + c
S2       y := 10

Овде, S2 поставља вредност коју има y, али S1 чита претходну вредност од y.

Излазна зависност

Израз S2 је излазна зависност на S1 (пише се $S1\ \delta ^{o}\ S2$) ако и само ако S1 и S2 модификују исти ресурс и у извршавању S1 претходи S2. Следи један пример излазне зависности (WAW: Write After Write):

S1       x := 10
S2       x := 20

Овде, и S2 и S1 постављају променљиву x.

Улазна зависност

Израз S2 је улазна зависност за S1 (пише се $S1\ \delta ^{i}\ S2$) ако и само ако S1 и S2 читају исти ресурс и у извршавању S1 претходиS2. Следи један пример зависности улаза (RAR: Read-After-Read):

S1       y := x + 3
S2       z := x + 5

Овде, и S2 и S1 приступају променљивој x. Ова зависност не забрањује преуређивање.

Зависност петље

Проблем израчунавања зависности унутар петље, што је значајан и нетривијални проблем, решава се помоћу анализе зависности петље, који проширује оквир зависности који је дат овде.

Види још

• Анализа програма

Литература

• Cooper, Keith D.; & Torczon, Linda. (2005). Engineering a Compiler. Morgan Kaufmann. ISBN 978-1-55860-698-2. 
• Kennedy, Ken & Allen, Randy. (2001). Optimizing Compilers for Modern Architectures: A Dependence-based Approach. Morgan Kaufmann. ISBN 978-1-55860-286-1. 
• Muchnick, Steven S. (1997). Advanced Compiler Design and Implementation. Morgan Kaufmann. ISBN 978-1-55860-320-2.