Презентация (В. Савченко - Анализ алиасов)

Àíàëèç ÀëèàñîâÎáçîðíàÿ ïðåçåíòàöèÿÑàâ÷åíêî Âàëåðèé20 ìàðòà 2014 ã.Ñîäåðæàíèå:1ÂâåäåíèåÀëèàñÏðèðîäà àëèàñîâÂàæíîñòü àíàëèçà àëèàñîâ2Âèäû àíàëèçîâÎáùàÿ ñâîäêàÏðèìåðû3Èçâåñòíûå ðåøåíèÿÀëãîðèòì Àíäåðñåíà (94`)Àëãîðèòì Ñòèíñãàðäà (96`)Ïîäõîä Ãîðâèö-Øàïèðî (97`)4Ñîâðåìåííûå èññëåäîâàíèÿÒåíäåíöèèÀëãîðèòìû, îñíîâàííûå íà âêëþ÷åíèèÀëãîðèòì Õàéíòöå-Òàðäü¼ (01`)Àëãîðèòì Ïèðñà-Êåëëè-Õýíêèíà (04`)Àëãîðèòìû ËÎÖ (LCD) è ÃÎÖ (HCD) (07`)Àëãîðèòìû ÂÐ (WP) è Ðà (DP) (09`)5Ðàçðàáîòêà àíàëèçà àëèàñîâÑ ÷åãî íà÷àòü?2 / 67×òî òàêîå àëèàñ?ÎïðåäåëåíèåÀëèàñîì áóäåì íàçûâàòü ñèòàóöèþ, â êîòîðîé ðàçíûå âûðàæåíèÿïðåäñòàâëÿþò îäèí è òîò æå ó÷àñòîê ïàìÿòè.ÂâåäåíèåÀëèàñ3 / 67×òî òàêîå àëèàñ?ÎïðåäåëåíèåÀëèàñîì áóäåì íàçûâàòü ñèòàóöèþ, â êîòîðîé ðàçíûå âûðàæåíèÿïðåäñòàâëÿþò îäèí è òîò æå ó÷àñòîê ïàìÿòè.ÏðèìåðA *p , * q ;p = new A ();q = p;ÂâåäåíèåÀëèàñ3 / 67×òî òàêîå àëèàñ?ÎïðåäåëåíèåÀëèàñîì áóäåì íàçûâàòü ñèòàóöèþ, â êîòîðîé ðàçíûå âûðàæåíèÿïðåäñòàâëÿþò îäèí è òîò æå ó÷àñòîê ïàìÿòè.ÏðèìåðA *p , * q ;p = new A ();q = p;ÂâåäåíèåÇäåñü ∗p è ∗q - àëèàñÀëèàñ3 / 67Îòêóäà ìîæåò âçÿòüñÿ àëèàñ?ÂâåäåíèåÏðèðîäà àëèàñîâ4 / 67Îòêóäà ìîæåò âçÿòüñÿ àëèàñ?ÓêàçàòåëèÂâåäåíèåÏðèðîäà àëèàñîâ4 / 67Îòêóäà ìîæåò âçÿòüñÿ àëèàñ?ÓêàçàòåëèÏåðåäà÷à ïàðàìåòðîâ ïî ññûëêåÂâåäåíèåÏðèðîäà àëèàñîâ4 / 67Îòêóäà ìîæåò âçÿòüñÿ àëèàñ?ÓêàçàòåëèÏåðåäà÷à ïàðàìåòðîâ ïî ññûëêåÈíäåêñàöèÿ ìàññèâîâÂâåäåíèåÏðèðîäà àëèàñîâ4 / 67Îòêóäà ìîæåò âçÿòüñÿ àëèàñ?ÓêàçàòåëèÏåðåäà÷à ïàðàìåòðîâ ïî ññûëêåÈíäåêñàöèÿ ìàññèâîâÏîëèìîðôíûå ñòðóêòóðû äàííûõ (òèïà union â C )ÂâåäåíèåÏðèðîäà àëèàñîâ4 / 67À ÷òî ìîæåò áûòü àëèàñîì?ÂâåäåíèåÏðèðîäà àëèàñîâ5 / 67À ÷òî ìîæåò áûòü àëèàñîì?Ñòàòè÷åñêè àëëîöèðîâàííûå îáúåêòûvoid foo () {int i , j ;.

. .}ÂâåäåíèåÏðèðîäà àëèàñîâ5 / 67À ÷òî ìîæåò áûòü àëèàñîì?Ñòàòè÷åñêè àëëîöèðîâàííûå îáúåêòûvoid foo () {int i , j ;. . .}ÂâåäåíèåÌîãóò ëè i è j áûòü àëèàñîì?Ïðèðîäà àëèàñîâ5 / 67À ÷òî ìîæåò áûòü àëèàñîì?Ñòàòè÷åñêè àëëîöèðîâàííûå îáúåêòûvoid foo () {int i , j ;. . .}Ìîãóò ëè i è j áûòü àëèàñîì?Äèíàìè÷åñêè àëëîöèðîâàííûå îáúåêòûvoid bar () {. . .p = new TreeNode ();p - > left = new TreeNode ();p - > right = new TreeNode ();. .

.}ÂâåäåíèåÏðèðîäà àëèàñîâ5 / 67À ÷òî ìîæåò áûòü àëèàñîì?Ñòàòè÷åñêè àëëîöèðîâàííûå îáúåêòûvoid foo () {int i , j ;. . .}Ìîãóò ëè i è j áûòü àëèàñîì?Äèíàìè÷åñêè àëëîöèðîâàííûå îáúåêòûvoid bar () {. . .p = new TreeNode ();p - > left = new TreeNode ();p - > right = new TreeNode ();.

. .}ÂâåäåíèåÀ p, p → lef t èp → right?Ïðèðîäà àëèàñîâ5 / 67×åì ýòî ìîæåò íàâðåäèòü?ÂâåäåíèåÂàæíîñòü àíàëèçà àëèàñîâ6 / 67×åì ýòî ìîæåò íàâðåäèòü?CSE*p = a + b;c = a + b;ÂâåäåíèåÂàæíîñòü àíàëèçà àëèàñîâ6 / 67×åì ýòî ìîæåò íàâðåäèòü?CSE*p = a + b;c = a + b;ÂâåäåíèåÀ åñëè ∗p àëèàñ äëÿ aèëè b?Âàæíîñòü àíàëèçà àëèàñîâ6 / 67×åì ýòî ìîæåò íàâðåäèòü?CSE*p = a + b;c = a + b;À åñëè ∗p àëèàñ äëÿ aèëè b?LICMwhile ( - - i >= 0) {c[i] = *p + a;}ÂâåäåíèåÂàæíîñòü àíàëèçà àëèàñîâ6 / 67×åì ýòî ìîæåò íàâðåäèòü?CSE*p = a + b;c = a + b;À åñëè ∗p àëèàñ äëÿ aèëè b?LICMwhile ( - - i >= 0) {c[i] = *p + a;}ÂâåäåíèåÀ åñëè ∃i : ∗p àëèàñ äëÿc[i]?Âàæíîñòü àíàëèçà àëèàñîâ6 / 67×åì ýòî ìîæåò íàâðåäèòü?CSE*p = a + b;c = a + b;À åñëè ∗p àëèàñ äëÿ aèëè b?LICMwhile ( - - i >= 0) {c[i] = *p + a;}À åñëè ∃i : ∗p àëèàñ äëÿc[i]?È ìíîæåñòâî äðóãèõ ïðèìåðîâ...ÂâåäåíèåÂàæíîñòü àíàëèçà àëèàñîâ6 / 67Êàêèå áûâàþò àëèàñ àíàëèçûÂèäû àíàëèçîâÎáùàÿ ñâîäêà7 / 67Êàêèå áûâàþò àëèàñ àíàëèçûÌåæïðîöåäóðíûå è âíóòðèïðîöåäóðíûåÂèäû àíàëèçîâÎáùàÿ ñâîäêà7 / 67Êàêèå áûâàþò àëèàñ àíàëèçûÌåæïðîöåäóðíûå è âíóòðèïðîöåäóðíûåÏîòîêîâî-÷óâñòâèòåëüíûå è -íå÷óâñòâèòåëüíûåÂèäû àíàëèçîâÎáùàÿ ñâîäêà7 / 67Êàêèå áûâàþò àëèàñ àíàëèçûÌåæïðîöåäóðíûå è âíóòðèïðîöåäóðíûåÏîòîêîâî-÷óâñòâèòåëüíûå è -íå÷óâñòâèòåëüíûåÊîíòåêñòíî-÷óâñòâèòåëüíûå è -íå÷óâñòâèòåëüíûåÂèäû àíàëèçîâÎáùàÿ ñâîäêà7 / 67Êàêèå áûâàþò àëèàñ àíàëèçûÌåæïðîöåäóðíûå è âíóòðèïðîöåäóðíûåÏîòîêîâî-÷óâñòâèòåëüíûå è -íå÷óâñòâèòåëüíûåÊîíòåêñòíî-÷óâñòâèòåëüíûå è -íå÷óâñòâèòåëüíûåÏîëå-÷óâñòâèòåëüíûå è -íå÷óâñòâèòåëüíûåÂèäû àíàëèçîâÎáùàÿ ñâîäêà7 / 67Êàêèå áûâàþò àëèàñ àíàëèçûÌåæïðîöåäóðíûå è âíóòðèïðîöåäóðíûåÏîòîêîâî-÷óâñòâèòåëüíûå è -íå÷óâñòâèòåëüíûåÊîíòåêñòíî-÷óâñòâèòåëüíûå è -íå÷óâñòâèòåëüíûåÏîëå-÷óâñòâèòåëüíûå è -íå÷óâñòâèòåëüíûåÓ÷èòûâàþùèå òèï èëè íåòÂèäû àíàëèçîâÎáùàÿ ñâîäêà7 / 67×åì îíè ìîãóò åùå ðàçëè÷àòüñÿ?Âèäû àíàëèçîâÎáùàÿ ñâîäêà8 / 67×åì îíè ìîãóò åùå ðàçëè÷àòüñÿ?Ìîäåëè ïàìÿòèÂèäû àíàëèçîâÎáùàÿ ñâîäêà8 / 67×åì îíè ìîãóò åùå ðàçëè÷àòüñÿ?Ìîäåëè ïàìÿòèÍåîáõîäèìîñòü ïîëíîãî êîäà ïðîãðàììûÂèäû àíàëèçîâÎáùàÿ ñâîäêà8 / 67×åì îíè ìîãóò åùå ðàçëè÷àòüñÿ?Ìîäåëè ïàìÿòèÍåîáõîäèìîñòü ïîëíîãî êîäà ïðîãðàììûÏðåäñòàâëåíèå àëèàñîâÂèäû àíàëèçîâÎáùàÿ ñâîäêà8 / 67×åì îíè ìîãóò åùå ðàçëè÷àòüñÿ?Ìîäåëè ïàìÿòèÍåîáõîäèìîñòü ïîëíîãî êîäà ïðîãðàììûÏðåäñòàâëåíèå àëèàñîâÏðåäñòàâëåíèå àãðåãàòîâÂèäû àíàëèçîâÎáùàÿ ñâîäêà8 / 67Íåêîòîðûå îáîçíà÷åíèÿÎïðåäåëåíèåÏóñòü p - óêàçàòåëü, i - íîìåð âûçîâà ôóíêöèè, ñîäåðæàùåé p, j íîìåð îïðåäåëåíèÿ p.

Òîãäà ÷åðåçpij → {a, ...}áóäåì îáîçíà÷àòü òî, ÷òî ïðè i-îì âûçîâå ôóíêöèè è j -îìîïðåäåëåíèè p îí ìîæåò óêàçûâàòü íà {a, ...}Âèäû àíàëèçîâÏðèìåðû9 / 67Ïîòîêîâî-÷óâñòâèòåëüíûé èêîíòåêñòíî-÷óâñòâèòåëüíûéint ** foo ( int ** p , ** q ) {int ** x ;x = p;. . .x = q;return x ;}int main () {int ** a , *b , *d , *f , c , e ;a = foo (& b , & f );*a = &c;a = foo (& d , & g );*a = &e;}Âèäû àíàëèçîâÏðèìåðû10 / 67Ïîòîêîâî-÷óâñòâèòåëüíûé èêîíòåêñòíî-÷óâñòâèòåëüíûéint ** foo ( int ** p , ** q ) {int ** x ;x = p;.

. .x = q;return x ;}p11 → {b}q11 → {f }p21 → {d}q21 → {g}x11 → {b}x12 → {f }x21 → {d}x22 → {g}a11 → {f }a12 → {g}f11 → {c}g11 → {e}int main () {int ** a , *b , *d , *f , c , e ;a = foo (& b , & f );*a = &c;a = foo (& d , & g );*a = &e;}Âèäû àíàëèçîâÏðèìåðû10 / 67Ïîòîêîâî-÷óâñòâèòåëüíûé èêîíòåêñòíî-íå÷óâñòâèòåëüíûéint ** foo ( int ** p , ** q ) {int ** x ;x = p;.

. .x = q;return x ;}int main () {int ** a , *b , *d , *f , c , e ;a = foo (& b , & f );*a = &c;a = foo (& d , & g );*a = &e;}Âèäû àíàëèçîâÏðèìåðû11 / 67Ïîòîêîâî-÷óâñòâèòåëüíûé èêîíòåêñòíî-íå÷óâñòâèòåëüíûéint ** foo ( int ** p , ** q ) {int ** x ;x = p;. .

.x = q;return x ;}p 1 → {b, d}q 1 → {f, g}x 1 → {b, d}x 2 → {f, g}a 1 → {f, g}a 2 → {f, g}f 1 → {c}g 1 → {c}f 2 → {c, e}g 2 → {c, e}_____int main () {int ** a , *b , *d , *f , c , e ;a = foo (& b , & f );*a = &c;a = foo (& d , & g );*a = &e;}Âèäû àíàëèçîâ_____Ïðèìåðû11 / 67Ïîòîêîâî-íå÷óâñòâèòåëüíûé èêîíòåêñòíî-÷óâñòâèòåëüíûéint ** foo ( int ** p , ** q ) {int ** x ;x = p;. . .x = q;return x ;}int main () {int ** a , *b , *d , *f , c , e ;a = foo (& b , & f );*a = &c;a = foo (& d , & g );*a = &e;}Âèäû àíàëèçîâÏðèìåðû12 / 67Ïîòîêîâî-íå÷óâñòâèòåëüíûé èêîíòåêñòíî-÷óâñòâèòåëüíûéint ** foo ( int ** p , ** q ) {int ** x ;x = p;. .

.x = q;return x ;}p1 → {b}q1 → {f }p2 → {d}q2 → {g}x1 → {b, f }x2 → {d, g}a1 → {b, f, d, g}b1 → {c, e}f1 → {c, e}d1 → {c, e}g1 → {c, e}______int main () {int ** a , *b , *d , *f , c , e ;a = foo (& b , & f );*a = &c;a = foo (& d , & g );*a = &e;}Âèäû àíàëèçîâ_____Ïðèìåðû12 / 67Ïîòîêîâî-íå÷óâñòâèòåëüíûé èêîíòåêñòíî-íå÷óâñòâèòåëüíûéint ** foo ( int ** p , ** q ) {int ** x ;x = p;. . .x = q;return x ;}int main () {int ** a , *b , *d , *f , c , e ;a = foo (& b , & f );*a = &c;a = foo (& d , & g );*a = &e;}Âèäû àíàëèçîâÏðèìåðû13 / 67Ïîòîêîâî-íå÷óâñòâèòåëüíûé èêîíòåêñòíî-íå÷óâñòâèòåëüíûéint ** foo ( int ** p , ** q ) {int ** x ;x = p;.

. .x = q;return x ;}pq__xa____bfdgint main () {int ** a , *b , *d , *f , c , e ;a = foo (& b , & f );*a = &c;a = foo (& d , & g );*a = &e;}Âèäû àíàëèçîâ→ {b, d}→ {f, g}→ {b, f, d, g}→ {b, f, d, g}→ {c, e}→ {c, e}→ {c, e}→ {c, e}__________Ïðèìåðû13 / 67Ïîòîêîâî-íå÷óâñòâèòåëüíûé èêîíòåêñòíî-íå÷óâñòâèòåëüíûéÑàìûå èçâåñòíûå è èñïîëüçóåìûå àëãîðèòìû àíàëèçà àëèàñîâîòíîñÿòñÿ êàê ðàç ê ýòîé ãðóïïå.Âèäû àíàëèçîâÏðèìåðû14 / 67Ïîòîêîâî-íå÷óâñòâèòåëüíûé èêîíòåêñòíî-íå÷óâñòâèòåëüíûéÑàìûå èçâåñòíûå è èñïîëüçóåìûå àëãîðèòìû àíàëèçà àëèàñîâîòíîñÿòñÿ êàê ðàç ê ýòîé ãðóïïå.Àëãîðèòì ÀíäåðñåíàÂèäû àíàëèçîâÏðèìåðû14 / 67Ïîòîêîâî-íå÷óâñòâèòåëüíûé èêîíòåêñòíî-íå÷óâñòâèòåëüíûéÑàìûå èçâåñòíûå è èñïîëüçóåìûå àëãîðèòìû àíàëèçà àëèàñîâîòíîñÿòñÿ êàê ðàç ê ýòîé ãðóïïå.Àëãîðèòì ÀíäåðñåíàÀëãîðèòì ÑòèíñãàðäàÂèäû àíàëèçîâÏðèìåðû14 / 67Ïîòîêîâî-íå÷óâñòâèòåëüíûé èêîíòåêñòíî-íå÷óâñòâèòåëüíûéÑàìûå èçâåñòíûå è èñïîëüçóåìûå àëãîðèòìû àíàëèçà àëèàñîâîòíîñÿòñÿ êàê ðàç ê ýòîé ãðóïïå.Àëãîðèòì ÀíäåðñåíàÀëãîðèòì ÑòèíñãàðäàÇàìå÷àíèåÁîëüøèíñòâî ðàçðàáîòàííûõ ïîçäíåå ìåòîäîâ ÿâëÿþòñÿ ëèáîìîäèôèêàöèÿìè, ëèáî íåêèìè ãèáðèäàìè ýòèõ äâóõ.Âèäû àíàëèçîâÏðèìåðû14 / 67Àëãîðèòì Àíäåðñåíà (94`)Ðàçðàáîòàí Ëàðñîì Óëå Àíäåðñåíîì è ïðåäñòàâëåí âñîîòâåòñòâóþùåé ðàáîòå â 1994-îì ãîäó.Èçâåñòíûå ðåøåíèÿÀëãîðèòì Àíäåðñåíà (94`)15 / 67Àëãîðèòì Àíäåðñåíà (94`)Ðàçðàáîòàí Ëàðñîì Óëå Àíäåðñåíîì è ïðåäñòàâëåí âñîîòâåòñòâóþùåé ðàáîòå â 1994-îì ãîäó.Ïîòîêîâî- è êîíòåêñòíî-íå÷óâñòâèòåëüíûéÈçâåñòíûå ðåøåíèÿÀëãîðèòì Àíäåðñåíà (94`)15 / 67Àëãîðèòì Àíäåðñåíà (94`)Ðàçðàáîòàí Ëàðñîì Óëå Àíäåðñåíîì è ïðåäñòàâëåí âñîîòâåòñòâóþùåé ðàáîòå â 1994-îì ãîäó.Ïîòîêîâî- è êîíòåêñòíî-íå÷óâñòâèòåëüíûéÑðåäè ñâîåãî êëàññà àíàëèçîâ îáåñïå÷èâàåò íàèëó÷øóþòî÷íîñòüÈçâåñòíûå ðåøåíèÿÀëãîðèòì Àíäåðñåíà (94`)15 / 67Îñíîâíûå ñâîéñòâàÈñïîëüçóåò óêàçûâàåò-íà ìíîæåñòâà (points-to sets) âêà÷åñòâå áîëåå êîìïàêòíîãî ðåçóëüòàòà àíàëèçà.Èçâåñòíûå ðåøåíèÿÀëãîðèòì Àíäåðñåíà (94`)16 / 67Îñíîâíûå ñâîéñòâàÈñïîëüçóåò óêàçûâàåò-íà ìíîæåñòâà (points-to sets) âêà÷åñòâå áîëåå êîìïàêòíîãî ðåçóëüòàòà àíàëèçà.ÏðèìåðÏóñòü P - ìíîæåñòâî óêàçàòåëåé, V - ìíîæåñòâî ïåðåìåííûõ.Îòìåòèì, ÷òî P ⊆ V .Ðåøåíèå ðàíåå:Ðåøåíèå ñåé÷àñ:{∀p ∈ P, ∀v ∈ V :< p, v, dp,v >}ãäå dp,v ∈ {0, 1, 12 }Èçâåñòíûå ðåøåíèÿ{∀p ∈ P : p → Vp }ãäå Vp ⊆ VÀëãîðèòì Àíäåðñåíà (94`)16 / 67Îñíîâíûå ñâîéñòâàÈíîãäà â àíàëèçèðóåìîé ïðîãðàììå ñîâåðøåííî íè÷åãî íåëüçÿñêàçàòü î òîì, êóäà óêàçûâàåò óêàçàòåëü.Èçâåñòíûå ðåøåíèÿÀëãîðèòì Àíäåðñåíà (94`)17 / 67Îñíîâíûå ñâîéñòâàÈíîãäà â àíàëèçèðóåìîé ïðîãðàììå ñîâåðøåííî íè÷åãî íåëüçÿñêàçàòü î òîì, êóäà óêàçûâàåò óêàçàòåëü.ÏðèìåðÓêàçàòåëü argvÈçâåñòíûå ðåøåíèÿÀëãîðèòì Àíäåðñåíà (94`)17 / 67Îñíîâíûå ñâîéñòâàÈíîãäà â àíàëèçèðóåìîé ïðîãðàììå ñîâåðøåííî íè÷åãî íåëüçÿñêàçàòü î òîì, êóäà óêàçûâàåò óêàçàòåëü.ÏðèìåðÓêàçàòåëü argvÑïåöèàëüíî äëÿ òàêèõ ñëó÷àåâ ââîäèòñÿ àáñòðàêòíàÿ ëîêàöèÿU nknown.ÎïðåäåëåíèåU nknown ∈ V ,ïðè÷åì, åñëè p → Vp è U nknown ∈ Vp, òî pìîæåò óêàçûâàòü íà âñå äîñòóïíûå â runtime îáúåêòû.Èçâåñòíûå ðåøåíèÿÀëãîðèòì Àíäåðñåíà (94`)17 / 67Îñíîâíûå ñâîéñòâàÅñëè q → U nknown è ∗q = &x, òî âñå óêàçàòåëè ìîãóòóêàçûâàòü íà x.

Èëè äàæå õóæå, åñëè ∗q = r è r → U nknown, òî∀p ∈ P ⇒ p → U nknown (ò.å. êàæäûé óêàçàòåëü ìîæåòóêàçûâàòü íà âñå îáúåêòû).Èçâåñòíûå ðåøåíèÿÀëãîðèòì Àíäåðñåíà (94`)18 / 67Îñíîâíûå ñâîéñòâàÅñëè q → U nknown è ∗q = &x, òî âñå óêàçàòåëè ìîãóòóêàçûâàòü íà x. Èëè äàæå õóæå, åñëè ∗q = r è r → U nknown, òî∀p ∈ P ⇒ p → U nknown (ò.å. êàæäûé óêàçàòåëü ìîæåòóêàçûâàòü íà âñå îáúåêòû).ÂûâîäÅñëè â lvalue èìååòñÿ ðàçûìåíîâàíèå óêàçàòåëÿp ∈ P : p → U nknown, ïðåêðàùàåì àíàëèç.Èçâåñòíûå ðåøåíèÿÀëãîðèòì Àíäåðñåíà (94`)18 / 67Îñíîâíûå ñâîéñòâàÌàññèâû ñ÷èòàþòñÿ àãðåãàòàìè, ò.å. ðàçëè÷íûå ýëåìåíòûìàññèâà ñ÷èòàþòñÿ íåîòëè÷èìûìè.ÏîÿñíåíèåÄëÿ àíàëèçà ∀i ∈ Z+ ⇒ a[i] ≡ ∗aÈçâåñòíûå ðåøåíèÿÀëãîðèòì Àíäåðñåíà (94`)19 / 67Îñíîâíûå ñâîéñòâàÌàññèâû ñ÷èòàþòñÿ àãðåãàòàìè, ò.å.