В. Савченко - Анализ алиасов

Àíàëèç àëèàñîâÑàâ÷åíêî Âàëåðèé24 ìàðòà 2014 ã.Ñîäåðæàíèå1Ââåäåíèå31.11.23334455561.32Ïîñòàíîâêà çàäà÷è2.12.22.32.42.52.63Îïðåäåëåíèå . . . . . . . . . . . . . . . . . . . . . . . . . . .Ïðèðîäà àëèàñîâ . . . . . . . . . . . . . . . . . . . . . . . . .1.2.1 Óêàçàòåëè . . . . . . . .

. . . . . . . . . . . . . . . .1.2.2 Ïåðåäà÷à ïàðàìåòðîâ ïî ññûëêå . . . . . . . . . . . .1.2.3 Èíäåêñàöèÿ ìàññèâà . . . . . . . . . . . . . . . . . .1.2.4 Ïîëèìîðôíûå ñòðóêòóðû äàííûõ . . . . . . . . . . .1.2.5 Ñëó÷àè ãàðàíòèðîâàííîãî îòñóòñòâèÿ àëèàñà . . . .Âàæíîñòü àíàëèçà àëèàñîâ . . . . .

. . . . . . . . . . . . . .1.3.1 Óñòðàíåíèå îáùèõ ïîäâûðàæåíèé . . . . . . . . . . .1.3.2 Ïåðåìåùåíèå êîäà èíâàðèàíòíîãî îòíîñèòåëüíîãîöèêëà . . . . . . . . . . . . . . . . . . . . . . . . . . .1.3.3 Ðàñïðîñòðàíåíèå êîíñòàíò . . . . . . . . . . . . . . .1.3.4 Ðàñïðåäåëåíèå ðåãèñòðîâ . . . . . . .

. . . . . . . . .8Îïðåäåëåíèå . . . . . . . . . . . . . . . . . . . . .Ñðàâíåíèå . . . . . . . . . . . . . . . . . . . . . .Êîíñåðâàòèâíîñòü . . . . . . . . . . . . . . . . . .Êîìïîçèöèÿ . . . . . . . . . . . . . . . . . . . . .Òåîðåìà î êîìïîçèöèè êîíñåðâàòèâíûõ àíàëèçîâÏðîñòåéøèé íåòðèâèàëüíûé àíàëèç àëèàñîâ . .. . . . .. .

. . .. . . . .. . . . .àëèàñîâ. . . . .......Âèäû àíàëèçîâ3.13.267788910101213Îñíîâíûå âèäû . . . . . . . . . . . . .3.1.1 Ìåæïðîöåäóðíîñòü . . . . . . .3.1.2 Êîíòåêñòíàÿ ÷óâñòâèòåëüíîñòü3.1.3 Ïîòîêîâàÿ ÷óâñòâèòåëüíîñòü . .3.1.4 Ïîëå-÷óâñòâèòåëüíîñòü . . . . .3.1.5 ×óâñòâèòåëüíîñòü ê òèïàì . . .Äîïîëíèòåëüíûå ðàçëè÷èÿ . . .

. . . .3.2.1 Ìîäåëè ïàìÿòè . . . . . . . . .1................................................................................................13131515151515153.2.23.2.33.2.44Àíàëèç óêàçàòåëåé4.14.24.34.44.54.655.25.3........................Àëãîðèòì Àíäåðñåíà (94`) . . . . . . .5.1.1 Ïîñòðîåíèå àíàëèçà óêàçàòåëåé5.1.2 Ðàçðåøåíèå îãðàíè÷åíèé . . . .5.1.3 Ðåçóëüòàòû . . .

. . . . . . . . .Àëãîðèòì Ñòèíñãàðäà (96`) . . . . . . .5.2.1 Ýêâèâàëåíòíîñòü ïåðåìåííûõ .5.2.2 Ïîñòðîåíèå àíàëèçà . . . . . . .5.2.3 Ðåçóëüòàòû . . . . . . . . . . . .5.2.4 Ðàçíèöà ñ Àíäåðñåíîì . . . . .Ïîäõîä Ãîðâèö-Øàïèðî (97`) . . . . .5.3.1 Îñíîâíàÿ èäåÿ . . . . . . . . . .5.3.2 Êîíêðåòèçàöèÿ . . . . . . . . . .5.3.3 Ïîñòðîåíèå àíàëèçà .

. . . . . .5.3.4 Ðåçóëüòàòû . . . . . . . . . . . .Ãðàô6.1.16.1.26.1.36.1.415161617181919........................................................................................................................................................................îãðàíè÷åíèé . . . . . . . . . . . . . .Îãðàíè÷åíèÿ . . . . .

. . . . . . . .Îïðåäåëåíèå . . . . . . . . . . . . .Ðàçðåøåíèå îãðàíè÷åíèé íà ãðàôåÏðèìåð ðàáîòû àëãîðèòìà . . . . ...................................................Ñîâðåìåííûå ïîäõîäû6.115151515Îïðåäåëåíèå . . . . . . . . . . . . . . . . . . . . . . .Ïîñòðîåíèå àíàëèçà àëèàñîâ ïî àíàëèçó óêàçàòåëåéÑðàâíåíèå . . . . . . . . .

. . . . . . . . . . . . . . .Êîíñåðâàòèâíîñòü . . . . . . . . . . . . . . . . . . . .Êîìïîçèöèÿ . . . . . . . . . . . . . . . . . . . . . . .Òåîðåìà î êîíñåðâàòèâíîñòè àíàëèçà óêàçàòåëåé . .Êëàññè÷åñêèå ðåøåíèÿ5.16Íåîáõîäèìîñòü ïîëíîãî êîäà ïðîãðàììû . . . . . . .Ïðåäñòàâëåíèå àëèàñîâ . . . . . . . . .

. . . . . . . .Ïðåäñòàâëåíèå àãðåãàòîâ . . . . . . . . . . . . . . . .19202224242426262727272930303023031313233Òåêñò àííîòàöèè1ÀííîòàöèÿÂâåäåíèåÍà÷èíàÿ ãîâîðèòü î òàêîé îáøèðíîé òåìå, êàê àíàëèç àëèàñîâ, ñòîèòïðåæäå âñåãî ïðîÿñíèòü ÷òî æå òàêîå àëèàñ è ïî÷åìó èõ òàê âàæíî àíàëèçèðîâàòü.1.1Îïðåäåëåíèå(Àëèàñ). Àëèàñîì 1 áóäåì íàçûâàòü ñèòóàöèþ, â êîòîðîé äîñòóï ê îäíîìó è òîìó æå ó÷àñòêó ïàìÿòè ìîæåò îñóùåñòâëÿòüñÿïîä ðàçíûìè èìåíàìè.Îïðåäåëåíèå 1Ïðèìåð 1. äàííîì ïðèìåðå2∗p è ∗q ÿâëÿþòñÿ àëèàñîì.A *p , * q ;p = new A ();q = p;Ëèñòèíã 1: Ïðèìåð àëèàñà1.2Ïðèðîäà àëèàñîâÎäíàêî, ñòîèò òàêæå ïðîÿñíèòü ïî÷åìó â êîäå ïðîãðàìì ìîãóò âîçíèêàòü àëèàñû.Àëèàñû ìîãóò áûòü ïîëó÷åíû ïðè èñïîëüçîâàíèè ñëåäóþùèõ ñóùíîñòåé(äëÿ ëó÷øåãî ïîíèìàíèÿ êàæäàÿ êàòåãîðèÿ áóäåò èëëþñòðèðîâàòüñÿ íàãëÿäíûì ïðèìåðîì).1.2.1ÓêàçàòåëèÑàìûì î÷åâèäíûì ñïîñîáîì ïîëó÷åíèÿ àëèàñîâ, êîíå÷íî æå, ÿâëÿþòñÿóêàçàòåëè.Äâà (è áîëåå) ðàçëè÷íûõ óêàçàòåëÿ ìîãóò óêàçûâàòü íà îäíó îáëàñòü âïàìÿòè, îáðàçóÿ ïðè ýòîì àëèàñ.

Èëè æå óêàçàòåëü ìîæåò óêàçûâàòü íàîáëàñòü ïàìÿòè, â êîòîðîé ðàñïîëîæåíà íåêîòîðàÿ ïåðåìåííàÿ è áûòü,1 îòå÷åñòâåííîé ëèòåðàòóðå àëèàñû òàêæå íàçûâàþòìàìè2ïñåâäîíèìàìèèëèñèíîíè-Çäåñü è äàëåå â ëèñòèíãàõ áóäåò èñïîëüçîâàòüñÿ ÿçûê C/C++, òàê êàê äëÿ íåãîíàèáîëåå îñòðî ñòîèò ïðîáëåìà àíàëèçà àëèàñîâ3ñîîòâåòñòâåííî, åå àëèàñîì.Ïðèìåð 2.  êà÷åñòâå ïðèìåðà àëèàñà íà óêàçàòåëÿõ ìîæíî âçÿòü óæåóïîìÿíóòûé ïðèìåð1, à òàêæå äîáàâèòü åùå îäèí.int x , * y ;y = &x;Ëèñòèíã 2: Ïðèìåð àëèàñà íà óêàçàòåëÿõ äàííîì ñëó÷àå x è ∗y - àëèàñ.1.2.2Ïåðåäà÷à ïàðàìåòðîâ ïî ññûëêå ñëó÷àå ïîëó÷åíèÿ ïàðàìåòðîâ ïî ññûëêå ìîæíî òàêæå ïîëó÷èòü èïàðî÷êó àëèàñîâ àðãóìåíòîâ ôóíêöèè, êàê ìåæäó ñîáîé, òàê è ñ ãëîáàëüíûìè ïåðåìåííûìè. äàííîì ïðèìåðå àëèàñàìè ÿâëÿþòñÿ x è ãëîáàëüíàÿ ïåðåìåííàÿ a, à òàêæå àðãóìåíòû y , z è ëîêàëüíàÿ ïåðåìåííàÿ b.Ïðèìåð 3.int a ;void foo ( int &x , int &y , int & z ) {.

. .}int main () {. . .int b ;foo (a , b , b );. . .}Ëèñòèíã 3: Ïðèìåð àëèàñà ïðè ïåðåäà÷å ïàðàìåòðîâ ïî ññûëêå1.2.3Èíäåêñàöèÿ ìàññèâàÅñëè ãîâîðèòü î ìàññèâàõ, òî ðàçíûå èíäåêñíûå âûðàæåíèÿ (â îñîáåííîñòè â öèêëàõ) ìîãóò ïðèâåñòè ê ðàâåíñòâó èíäåêñîâ è, ñëåäîâàòåëüíî,ê îáðàùåíèþ ê òîé æå ÿ÷åéêå ïàìÿòè (ò.å. ê ïîÿâëåíèþ àëèàñà). äàííîì ïðèìåðå èíäåêñíûå âûðàæåíèÿ i è 9 − i ðàâíûïðè i = 5, ò.å. ïðè i = 5 a[i] è a[9 − i] ÿâëÿþòñÿ àëèàñîì.Ïðèìåð 4.int a [10];. . .for ( int i = 0; i <= 9; ++ i ) {a [ i ] = a [9 - i ] + 3;}Ëèñòèíã 4: Ïðèìåð àëèàñà, ïîðîæäåííîãî ðàçëè÷íûìè èíäåêñíûìè âûðàæåíèÿìè41.2.4Ïîëèìîðôíûå ñòðóêòóðû äàííûõ äàííîì ñëó÷àå (â êîíòåêñòå ÿçûêà C) ñòîèò ãîâîðèòü î union.

Äàííàÿñòðóêòóðà ïî ñâîåé ïðèðîäå ïîäðàçóìåâàåò àëèàñ.Ïðèìåð 5. äàííîì ïðèìåðå àëèàñîì ÿâëÿþòñÿ x.a è x.b.union {int a ;double b ;} x;Ëèñòèíã 5: Ïðèìåð àëèàñà ïðè èñïîëüçîâàíèè unionÑòîèò îòìåòèòü, ÷òî àëèàñû ìîãóò áûòü ïîëó÷åíû è ëþáîé êîìáèíàöèåé èç ðàññìîòðåííûõ âûøå ñïîñîáîâ.Îäíàêî, íåñìîòðÿ íà òàêîå êîëè÷åñòâî âîçìîæíîñòåé ïîÿâëåíèÿ àëèàñà, î÷åíü ÷àñòî ìîæíî òî÷íî ñêàçàòü îá îòñóòñòâèè àëèàñà.1.2.5Ñëó÷àè ãàðàíòèðîâàííîãî îòñóòñòâèÿ àëèàñàÏðèìåð 6.void foo () {.

. .int i , j ;. . .}Ëèñòèíã 6: Ñòàòè÷åñêè àëëîöèðîâàííûå îáúåêòûÏðèìåð 7.void bar () {. . .p = new TreeNode ();p - > left = new TreeNode ();p - > right = new TreeNode ();. . .}Ëèñòèíã 7: Äèíàìè÷åñêè àëëîöèðîâàííûå îáúåêòû äàííûõ ïðèìåðàõ ìîæíî óòâåðæäàòü, ÷òî i è j , à òàêæå p, p → lef t èp → right ãàðàíòèðîâàííî íå ÿâëÿþòñÿ àëèàñàìè.1.3Âàæíîñòü àíàëèçà àëèàñîâÏåðåä ôîðìàëüíûì ââåäåíèåì â àíàëèç àëèàñ æåëàòåëüíî ïîíÿòü çà÷åìåãî íåîáõîäèìî ïðîâîäèòü è ïî÷åìó äàííàÿ çàäà÷à ñòîëü âîñòðåáîâàíà.Ïðåæäå âñåãî àíàëèç àëèàñîâ èìååò îñîáóþ âàæíîñòü äëÿ êîìïèëÿòîðíûõ îïòèìèçàöèé, ò.ê.

ìîæåò íàïðÿìóþ âëèÿòü íà ðåçóëüòàòû èõ ðàáîòû. Äëÿ áîëåå ÿñíîãî ïðåäñòàâëåíèÿ òàêîãî ðîäà ýôôåêòîâ áóäåò ðàññìîòðåíî íåñêîëüêî ðàñïðîñòðàíåííûõ îïòèìèçàöèé è ïðèìåðîâ âëèÿíèÿ àëèàñîâ íà íèõ.51.3.1Óñòðàíåíèå îáùèõ ïîäâûðàæåíèé ðàññìàòðèâàåìîì ïðèìåðå îïòèìèçàöèÿ óñòðàíåíèÿ îáìîãëà áû óäàëèòü îáùåå ïîäâûðàæåíèå a + b èïîëó÷èòü êîä, êîòîðûé âû÷èñëÿåò åãî åäèíîæäû[ëèñòèíã 9].Ïðèìåð 8.ùèõ ïîäâûðàæåíèé 1t = a + b;*p = t;c = t;*p = a + b;c = a + b;Ëèñòèíã 8: Äî îïòèìèçàöèèËèñòèíã 9: Ïîñëå îïòèìèçàöèèÎäíàêî, äàííàÿ îïòèìèçàöèÿ ìîæåò áûòü ïðîâåäåíà òîëüêî â òîì ñëó÷àå, êîãäà èçâåñòíî, ÷òî ∗p íå ÿâëÿåòñÿ àëèàñîì íè äëÿ a, íè äëÿ b.1.3.2Ïåðåìåùåíèå êîäà èíâàðèàíòíîãî îòíîñèòåëüíîãî öèêëàÏðèìåð 9.

 ðàññìàòðèâàåìîì ïðèìåðå îïòèìèçàöèÿ ïåðåìåùåíèÿ êîäà 2 ìîãëà áû ïåðåìåñòèòü ïîäâûðàæåíèå ∗p + a çà ãðàíèöó öèêëà èïîëó÷èòü êîä[ëèñòèíã 11], íå âû÷èñëÿþùèé îäíî è òî æå âûðàæåíèå íàêàæäîé èòåðàöèè.t = *p + a;while ( - - i >= 0) {c[i] = t;}while ( - - i >= 0) {c[i] = *p + a;}Ëèñòèíã 10: Äî îïòèìèçàöèèËèñòèíã 11: Ïîñëå îïòèìèçàöèèÎäíàêî, ýòî ìîæåò áûòü ñäåëàíî òîëüêî â òîì ñëó÷àå, êîãäà èçâåñòíî,÷òî ∀i ∈ [0, n) âåðíî, ÷òî ∗p è c[i] íå ÿâëÿþòñÿ àëèàñîì.1Óñòðàíåíèå îáùèõ ïîäâûðàæåíèé - êîìïèëÿòîðíàÿ îïòèìèçàöèÿ, êîòîðàÿ èùåòâ ïðîãðàììå îäèíàêîâûå âû÷èñëåíèÿ è óäàëÿåò âòîðîå è ïîñëåäóþùèå âõîæäåíèÿðàññìàòðèâàåìîãî âûðàæåíèÿ, çàìåíÿÿ åãî óæå âû÷èñëåííûì çíà÷åíèåì2Ïåðåìåùåíèå êîäà èíâàðèàíòíîãî îòíîñèòåëüíî öèêëà - êîìïèëÿòîðíàÿ îïòèìèçàöèÿ, êîòîðàÿ ïåðåìåùàåò çà ïðåäåëû öèêëà êîä, ïåðåìåùåíèå êîòîðîãî íèêàê íåïîâëèÿåò íà ñåìàíòèêó öèêëà è ïðîãðàììû â öåëîì61.3.3Ðàñïðîñòðàíåíèå êîíñòàíò ðàññìàòðèâàåìîì ïðèìåðå îïòèìèçàöèÿ ðàñïðîñòðàíåìîãëà áû ðàñïðîñòðàíèòü çíà÷åíèå êîíñòàíòíîé ïåðåìåííîé x è ïîëó÷èòü êîä[ëèñòèíã 13].Ïðèìåð 10.íèÿ êîíñòàíò 1x = 3;* p = 4;y = x;x = 3;* p = 4;y = 3;Ëèñòèíã 12: Äî îïòèìèçàöèèËèñòèíã 13: Ïîñëå îïòèìèçàöèèÎäíàêî, ýòî ìîæåò áûòü ñäåëàíî òîëüêî â òîì ñëó÷àå, êîãäà èçâåñòíî,÷òî ∗p è x íå ÿâëÿþòñÿ àëèàñîì.1.3.4Ðàñïðåäåëåíèå ðåãèñòðîâ ñëó÷àå ðàñïðåäåëåíèÿ ðåãèñòðîâ 2 àíàëèç àëèàñîâ ÿâëÿåòñÿ ïðîñòîíåîáõîäèìûì óñëîâèåì äëÿ òîãî, ÷òîáû ïåðåìåííîé â ïðèíöèïå áûë áûñîïîñòàâëåí íåêîòîðûé ðåãèñòð.

Òî åñòü íà âðåìÿ íàõîæäåíèÿ ïåðåìåííîé â ðåãèñòðå íåîáõîäèìî áûòü óâåðåííûì, ÷òî íå ïðîèñõîäèò çàïèñè/÷òåíèÿ äàííîé ïåðåìåííîé ÷åðåç åå àëèàñ. ðàññìàòðèâàåìîì ïðèìåðå ïðè ðàñïðåäåëåíèè ðåãèñòðîâïåðåìåííàÿ x íà âðåìÿ öèêëà ìîãëà áûòü ðàçìåùåíà íà ðåãèñòðå, ÷òîçíà÷èòåëüíî ñîêðàòèëî áû ÷èñëî îáðàùåíèé ê ïàìÿòè.Ïðèìåð 11.x = 0;. . .while ( - - i >= 0) {* p += a [ i ];x += a [ i ];}Ëèñòèíã 14: Ðàñïðåäåëåíèå ðåãèñòðîâÎäíàêî, åñëè ∗p ÿâëÿåòñÿ àëèàñîì äëÿ x, íà âûõîäå èç öèêëà (ïîñëån−1Pîïòèìèçàöèè) x =a[i], õîòÿ áåç ðàçìåùåíèÿ íà ðåãèñòðå áûëî áûi=0x = 2∗n−1Pa[i], ÷òî, î÷åâèäíûì îáðàçîì, ÿâëÿåòñÿ íåêîððåêòíûì ïîâå-i=0äåíèåì ïðîãðàììû.1Ðàñïðîñòðàíåíèå êîíñòàíò - êîìïèëÿòîðíàÿ îïòèìèçàöèÿ, óìåíüøàþùàÿ ÷èñëîèçáûòî÷íûõ âû÷èñëåíèé çàìåíîé êîíñòàíòíûõ âûðàæåíèé è ïåðåìåííûõ èõ çíà÷åíèÿìè2Ðàñïðåäåëåíèå ðåãèñòðîâ - êîìïèëÿòîðíàÿ îïòèìèçàöèÿ, ñîñòîÿùàÿ â îòîáðàæåíèè ìíîæåñòâà ïåðåìåííûõ ïðîãðàììû â ìíîæåñòâî ðåãèñòðîâ öåëåâîãî ïðîöåññîðà7Ðàññìîòðåííûå îïòèìèçàöèè íå ïîêðûâàþò âñåãî ñïåêòðà ïðîáëåì,îäíàêî, õîðîøî äåìîíñòðèðóþò òîò êëàññ ïðîáëåì, êîòîðûé ìîæåò áûòüâûçâàí íåçíàíèåì íàáîðà àëèàñîâ ïðîãðàììû, à òàêæå âîçìîæíûå ìàñøòàáû óïóùåííîé âûãîäû.2Ïîñòàíîâêà çàäà÷èÒåïåðü ñòîèò ñêàçàòü ñîáñòâåííî î ñàìîé çàäà÷å àíàëèçà àëèàñîâ.2.1ÎïðåäåëåíèåÏóñòü V - ìíîæåñòâî ïåðåìåííûõ â ïðîãðàììå, à D - ìíîæåñòâî ðåøåíèé.×àùå âñåãî âûáèðàþò D ñëåäóþùåãî âèäà: |D| = 3, D = {must, may, never},ãäå1 :• must îòâå÷àåò òîìó, ÷òî äâå ïåðåìåííûå òî÷íî ÿâëÿþòñÿ àëèàñîì, ò.å.