В. Савченко - Анализ алиасов, страница 3

Òîãäà âíóòðèïðîöåäóðíûì àíàëèçîì àëèàñîâ äëÿ i-îé ôóíêöèè ÿâëÿåòñÿmSàíàëèç àëèàñîâ ϕi : ∀v, w ∈Vj → ϕi (v, w) = may , à àíàëèç àëèàñîâj=1j6=iϕ äëÿ âñåé ïðîãðàììû íà îñíîâàíèè âíóòðèïðîöåäóðíûõ àíàëèçîâ ϕiìîæåò áûòü ïîëó÷åí ñ ïîìîùüþ êîìïîçèöèè: ϕ = ϕ1 ◦ ϕ2 ◦ · · · ◦ ϕm . Åñëèïîòðåáîâàòü êîíñåðâàòèâíîñòü âñåõ ϕi , òî, ñîãëàñíî òåîðåìå î êîìïîçèöèè, ϕ áóäåò êîíñåðâàòèâåí è îïðåäåëåí íà âñåõ ïàðàõ ïåðåìåííûõ.Íî, äàæå åñëè ðàññìîòðåòü φ∗i : @ϕ0i : φ∗i < ϕ0i ≤ φ∗ (íàèáîëåå òî÷íûåâíóòðèïðîöåäóðíûå àíàëèçû àëèàñîâ), òî íåñìîòðÿ íà òî, ÷òî â îáùåì1Ïðè ÷òåíèè íå çàöèêëèâàéòåñü íà ÷òåíèè îïðåäåëåíèÿ âèäà, åñëè íå ìîæåòå ïîíÿòü î ÷åì èäåò ðå÷ü, ïîñìîòðèòå íà ïðèìåð.13ñëó÷àå φ∗1 ◦ φ∗2 ◦ · · · ◦ φ∗m ≤ φ∗ , íà ïðàêòèêå, â ïîäàâëÿþùåì ÷èñëå ñëó÷àåâ,ñòîèò ãîâîðèòü î ñòðîãîì íåðàâåíñòâå.Ïðèìåð 13.Ïðèìåð ìåæïðîöåäóðíîãî è âíóòðèïðîöåäóðíîãî àíàëèçîâvoid foo ( int &a , int & b ) {int *p , * q ;p = &a;q = &b;.

. .}void bar () {int x ;foo (x , x );} äàííîì ñëó÷àå V1 = {a, b, p, q, ∗p, ∗q}, V2 = {x} è V = V1 ∪ V2 .Ðàññìîòðèì 1 äëÿ íà÷àëà φ∗ :1. Èç-çà âûçîâà foo(x,x) ïîëó÷àåì φ∗ (x, a) = φ∗ (x, b) = must2. Âòîðîå ñâîéñòâî àíàëèçîâ àëèàñîâ äàåò íàì, ÷òî φ∗ (a, b) = must.3. Èç èíñòóðêöèé p = &a è q = &b óñòàíàâëèâàåì, ÷òî φ∗ (∗p, a) = φ∗ (∗q, b) =must4. Îïÿòü æå èç âòîðîãî ñâîéñòâà èìååì φ∗ (x, ∗p) = φ∗ (x, ∗q) = must5. Äëÿ îñòàëüíûõ ïàð âèäà (p, v) è (q, v), ãäå v ∈ V âåðíî, ÷òî φ∗ (p, v) =φ∗ (q, v) = neverÎ÷åâèäíî, ÷òî φ∗ - ìåæïðîöåäóðíûé, ò.ê. äàæå â ïîÿñíåíèè èñïîëüçîâàëèñü èíñòðóêöèè è ïåðåìåííûå èç äâóõ ðàçëè÷íûõ ôóíêöèé. Òåïåðüïîïðîáóåì ðàññìîòðåòü φ∗1 è φ∗2 . Íà÷íåì ñ φ∗1 :1.

Èç èíñòóðêöèé p = &a è q = &b óñòàíàâëèâàåì, ÷òî φ∗1 (∗p, a) = φ∗1 (∗q, b) =must2. Òàê êàê íå ìîæåò èñïîëüçîâàòüñÿ èíôîðìàöèÿ èç äðóãèõ ôóíêöèé,òî ìû íå èìååì íèêàêîé èíôîðìàöèè î òîì, ñ êàêèìè ïàðàìåòðàìèìîãëà âûçûâàòüñÿ ðàññìàòðèâàåìàÿ ôóíêöèÿ. Ïîýòîìó äëÿ ñîõðàíåíèÿ ñâîéñòâà êîíñåðâàòèâíîñòè ïðèõîäèòñÿ ñ÷èòàòü, ÷òî ïàðàìåòðû ìîãóò áûòü àëèàñàìè äëÿ âñåãî âíå ðàññìàòðèâàåìîé ôóíêöèè, ò.å. â äàííîì ñëó÷àå φ∗1 (a, x) = φ∗1 (b, x) = may .3. Èç âòîðîãî ñâîéñòâà ïîëó÷àåì, ÷òî φ∗1 (∗q, x) = φ∗1 (∗p, x) = ...

= mayφ∗2 â äàííîì ñëó÷àå ñîâïàäàåò ñ φ− . È êàê ðåçóëüòàò èìååì, ÷òî äàæå âòàêîì ïðîñòîì ñëó÷àå φ∗1 ◦ φ∗2 = φ∗1 < φ∗ .1Çäåñü íå ïðåäñòàâëåí àëãîðèòì ïîñòðîåíèÿ φ∗ , à ëèøü ïîÿñíåíèÿ îòíîñèòåëüíîåãî âèäà143.1.2Êîíòåêñòíàÿ ÷óâñòâèòåëüíîñòüÐàçëè÷àþò êîíòåêñòíî-÷óâñòâèòåëüíûå è êîíòåêñòíî-íå÷óâñòâèòåëüíûåàíàëèçû, ïîíèìàÿ ïîä ýòèì, ÷òî ïðè àíàëèçå ôóíêöèè è åå ïåðåìåííûõó÷èòûâàåòñÿ èëè íåò êîíòåêñò, â êîòîðîì áûëà âûçâàíà ôóíêöèÿ.Ïðèìåð 14.àíàëèçîâÏðèìåð êîíòåêñòíî-÷óâñòâèòåëüíîãî è êîíòåêñòíî-íå÷óâñòâèòåëüíîãî3.1.3Ïîòîêîâàÿ ÷óâñòâèòåëüíîñòü3.1.4Ïîëå-÷óâñòâèòåëüíîñòü3.1.5×óâñòâèòåëüíîñòü ê òèïàì3.2Äîïîëíèòåëüíûå ðàçëè÷èÿ3.2.1Ìîäåëè ïàìÿòè3.2.2Íåîáõîäèìîñòü ïîëíîãî êîäà ïðîãðàììû3.2.3Ïðåäñòàâëåíèå àëèàñîâ3.2.4Ïðåäñòàâëåíèå àãðåãàòîâÅñëè æå ãîâîðèòü î ðåàëüíûõ ïðèëîæåíèÿõ, òî ïîñòðîåíèå òî÷íîãî ðåøåíèÿ äàæå â êëàññå êîíòåêñòíî- è ïîòîêîâî-íå÷óâñòâèòåëüíûõ àíàëèçîâÿâëÿåòñÿ NP-òðóäíîé çàäà÷åé, ÷òî äåëàåò åå íåïðèìåíèìîé íà ïðàêòèêå.

Îäíàêî, ñóùåñòâóåò íåñêîëüêî ìåòîäîâ ïîñòðîåíèÿ êîíñåðâàòèâíûõàíàëèçîâ àëèàñîâ â ýòîì êëàññå, êîòîðûå çíà÷èòåëüíî ëó÷øå àíàëèçààëèàñîâ ïî âçÿòèþ àäðåñà.4Àíàëèç óêàçàòåëåéÎïðåäåëÿþùèì ôàêòîðîì ñëîæíîñòè àíàëèçà àëèàñîâ, íåñìîòðÿ íà íàëè÷èå è äðóãèõ ñïîñîáîâ, îñòàþòñÿ óêàçàòåëè. Ðàçðåøåíèå àëèàñîâ, ïîëó÷åííûõ äðóãèìè ñïîñîáàìè, íå ÿâëÿåòñÿ òðóäîåìêîé çàäà÷åé, ñîîòâåòñòâåííî, ãëàâíîé çàäà÷åé ñòàíîâèòñÿ àíàëèç óêàçàòåëåé.4.1ÎïðåäåëåíèåÏóñòü P - ìíîæåñòâî óêàçàòåëåé ïðîãðàììû. Îòìåòèì, ÷òî P ⊆ V .(Àíàëèç óêàçàòåëåé). Àíàëèçîì óêàçàòåëåé íàçîâåìîòîáðàæåíèå ξ : P → 2V .Îïðåäåëåíèå 9Òî åñòü àíàëèç óêàçàòåëåé åñòü ñîïîñòàâëåíèå êàæäîìó óêàçàòåëþïîäìíîæåñòâà ïåðåìåííûõ (ìíîæåñòâî ïåðåìåííûõ, íà êîòîðûå ìîæåòóêàçûâàòü óêàçàòåëü).154.2Ïîñòðîåíèå àíàëèçà àëèàñîâ ïî àíàëèçó óêàçàòåëåéÒàê êàê ìû ãîâîðèì îá àíàëèçå óêàçàòåëåé â êîíòåêñòå àíàëèçà àëèàñîâ,òî íåîáõîäèìî óìåòü ñòðîèòü èç ïåðâîãî âòîðîå.Ïîñòðîèì àíàëèç àëèàñîâ ϕξ èç àíàëèçà óêàçàòåëåé ξ :1.

Çà îñíîâó âîçüìåì òðèâèàëüíûé àíàëèç àëèàñîâ: ϕξ = φ−2. ∀p ∈ P, ∀a 6∈ ξ(p) → ϕξ (∗p, a) = ϕξ (a, ∗p) = never3.  òðåòüåì ïóíêòå èìåþòñÿ íåêîòîðûå ðàñõîæäåíèÿ:• Àíàëèç óêàçàòåëåé íàçûâàþò must-àíàëèçîì, åñëè íà åãî îñíîâàíèè ìîæíî ïðåäúÿâèòü ðåøåíèå must, òî åñòü ∀p ∈ P, ∀a ∈Vp → ϕξ (∗p, a) = ϕξ (a, ∗p) = must• Åñëè æå íåò, òî òàêîé àíàëèç íàçûâàþò may -àíàëèçîì.Äàëåå, íåñìîòðÿ íà òî, ÷òî must-àíàëèç ïðåäîñòàâëÿåò ëó÷øèå ðåçóëüòàòû, ìû íåÿâíî áóäåì èìåòü ââèäó èñïîëüçîâàíèå may -àíàëèçà, òàêêàê åãî ïîñòðîåíèå ïðîùå è òàê êàê ÷àùå âñåãî âàæíåå èìåííî ðåøåíèånever, êîòîðîå ìîæåò áûòü ïîëó÷åíî íà åãî îñíîâàíèè.Òîãäà äëÿ may -àíàëèçà óêàçàòåëåé ξ ìîæíî ñôîðìóëèðîâàòü, ÷òî∀p ∈ P, ∀a ∈ V → ϕξ (∗p, a) = never ⇔ a 6∈ ξ(p)∀a, b ∈ V → ϕξ (a, b) 6= mustÄàëåå ïîñòàðàåìñÿ ïåðåíåñòè òåðìèíîëîãèþ àíàëèçîâ àëèàñîâ íà àíàëèçû óêàçàòåëåé.4.3ÑðàâíåíèåÂâåäåì ñðàâíåíèå àíàëèçîâ óêàçàòåëåé.Îïðåäåëåíèå 10.ðèòü, ÷òî ξñëàáååÏóñòü ξ è ζ - àíàëèçû óêàçàòåëåé.

Òîãäà áóäåì ãîâîζ è îáîçíà÷àòü ξ ≤ ζ , åñëè ∀p ∈ P → ζ(p) ⊆ ξ(p).Áóäåì ãîâîðèòü, ÷òî ξξ < ζ , åñëè ξ ≤ ζ è ∃q ∈ P : ζ(p) ⊂ ξ(p).Îïðåäåëåíèå 11.Ëåììà 1ñòðîãî ñëàáååζ è îáîçíà÷àòü(Î ñðàâíåíèè àíàëèçîâ óêàçàòåëåé). Ïóñòü ξ è ζ - àíàëèçûóêàçàòåëåé. Òîãäàξ ≤ ζ ⇔ ϕξ ≤ ϕζÄîêàçàòåëüñòâî.1. Ïóñòü ξ ≤ ζ . Òîãäà ∀p ∈ P → ξ(p) ⊇ ζ(p).Ðàññìîòðèì ϕξ . Äëÿ íåãî âûïîëíÿòñÿ, ÷òî∀q ∈ P, ∀a ∈ V → ϕξ (∗q, a) = never ⇔ a 6∈ ξ(q)Òàê êàê ζ(q) ⊆ ξ(q), òî a 6∈ ζ(q) ⇒ ϕζ (∗q, a) = never. Ó÷èòûâàÿ,÷òî ∀a, b ∈ V → ϕξ (a, b) 6= must (àíàëîãè÷íîå âåðíî è äëÿ ϕζ ),ïîëó÷àåì ϕξ ≤ ϕζ .162.

Ïóñòü ϕξ ≤ ϕζ .Òàê êàê ϕξ è ϕζ íå ïðèíèìàþò must íè íà êàêèõ ïàðàõ ïåðåìåííûõ,òî äîñòàòî÷íî ðàññìîòðåòü ñëó÷àé ñ ðàâåíñòâîì never. Èç òîãî, ÷òîϕξ ≤ ϕζ ñëåäóåò, ÷òî∀q ∈ P, ∀a ∈ V → ϕξ (∗q, a) = never ⇒ ϕζ (∗q, a) = neverÝòî æå óòâåðæäåíèå ìîæíî çàïèñàòü â ñëåäóþùåì âèäå:a 6∈ ξ(q) ⇒ a 6∈ ζ(q)Ïðåîáðàçîâûâàÿ äàëüøå ïîëó÷àåì, ÷òî a ∈ ξ(q) ⇒ a ∈ ζ(q). Òàêêàê ýòî âåðíî äëÿ ïðîèçâîëüíîãî a, òî ζ(q) ⊇ ξ(q). Îòêóäà ïîëó÷àåì, ÷òî ξ(q) ⊇ ζ(q), ÷òî â ñâîþ î÷åðåäü âåðíî äëÿ ïðîèçâîëüíîãî q .Òîãäà ξ ≤ ζ .4.4ÊîíñåðâàòèâíîñòüÀíàëèç óêàçàòåëåé ξ áóäåì íàçûâàòü êîíñåðâàòèâíûì, åñëè ñîîòâåòñòâóþùèé åìó àíàëèç àëèàñîâ ϕξ êîíñåðâàòèâåí, ò.å.ϕξ ≤ φ∗ .Îïðåäåëåíèå 12.Îïðåäåëåíèå 13.ρ∗ êîíñåðâàòèâåí èÀíàëèç óêàçàòåëåé ρ∗ áóäåì íàçûâàòü òî÷íûì, åñëè@ξ : ξ êîíñåðâàòèâåí è ϕρ∗ < ϕξ .Òåîðåìà 2.

(Î ñóùåñòâîâàíèè òî÷íîãî àíàëèçà óêàçàòåëåé) Òî÷íûéàíàëèç óêàçàòåëåé ñóùåñòâóåò.Äîêàæåì ñóùåñòâîâàíèå ïîñòðîåíèåì òàêîãî àíàëèçà.Íà îñíîâàíèè φ∗ ïîñòðîèì àíàëèç óêàçàòåëåé ξ ñëåäóþùèì îáðàçîì:Äîêàçàòåëüñòâî.∀p ∈ P âûïîëíÿåòñÿ, ÷òî ∀v ∈ V : φ∗ (∗p, v) 6= never ⇔ v ∈ ξ(p)Î÷åâèäíî, ÷òî ξ êîíñåðâàòèâåí ïî ïîñòðîåíèþ. Ïîêàæåì, ÷òî ξ = ρ∗ .Ïóñòü ýòî íå òàê, òîãäà ∃ζ : ζ êîíñåðâàòèâåí è ϕξ < ϕζ .Òàê êàê ∀v, w ∈ V → ϕξ (v, w) 6= must è ϕζ (v, w) 6= must, à òàêæåϕξ < ϕζ , òî∃a, b ∈ V : ϕζ (a, b) = never, ϕξ (a, b) = mayÒàê êàê ϕζ ïîñòðîåí ïî àíàëèçó óêàçàòåëåé, òîϕζ (a, b) = never ⇔ ∃q ∈ P : a = ∗q èëè b = ∗qÄëÿ îïðåäåëåííîñòè áóäåì ñ÷èòàòü, ÷òî a = ∗q . Òîãäà b 6∈ ζ(q), íî b ∈ξ(q). Òàê êàê ϕζ (∗q, b) = never è ϕζ êîíñåðâàòèâåí, òî φ∗ (∗q, b) = never.Îäíàêî, èç òîãî, ÷òî b ∈ ξ(q) ñëåäóåò, ÷òî φ∗ (∗q, b) 6= never.

Ïîëó÷èëèïðîòèâîðå÷èå, çíà÷èò, ξ = ρ∗ .174.5ÊîìïîçèöèÿÎïðåäåëåíèå 14. Ïóñòü ξ è ζ - àíàëèçû óêàçàòåëåé. Òîãäà êîìïîçèöèåéàíàëèçîâ óêàçàòåëåé áóäåì íàçûâàòü ñëåäóþùóþ îïåðàöèþ:γ = ξ ◦ ζ ⇔ ∀p ∈ P → γ(p) = ξ(p) ∩ ζ(p)Ëåììà 2(Î êîìïîçèöèè àíàëèçîâ óêàçàòåëåé). Ïóñòü ξ è ζ - àíàëèçûóêàçàòåëåé. Òîãäàγ = ξ ◦ ζ ⇔ ϕγ = ϕξ ◦ ϕζÄîêàçàòåëüñòâî.1. Ïóñòü γ = ξ ◦ ζ . Ðàññìîòðèì ϕγ .∀q ∈ P, ∀a ∈ V → ϕγ (∗q, a) = never ⇔ a 6∈ γ(q)Òàê êàê γ = ξ ◦ ζ , òî a 6∈ ξ(q) ∩ ζ(q). Ïðåîáðàçóåì ïîëó÷åííîåâûðàæåíèå:a ∈ ξ(q) ∩ ζ(q) ⇔ a ∈ ξ(q) ∪ ζ(q)a ∈ ξ(q),a 6∈ ξ(q),Ïîëó÷àåì, ÷òî a ∈ ζ(q),⇔ a 6∈ ζ(q),a 6∈ ξ(q) ∪ ζ(q)a ∈ ξ(q) ∩ ζ(q) ϕξ (∗q, a) = never, ϕζ (∗q, a) = may;ϕξ (∗q, a) = may,Êàê ðåçóëüòàò èìååì, ÷òî ϕγ (∗q, a) = never ⇔  ϕζ (∗q, a) = never;ϕξ (∗q, a) = never,ϕζ (∗q, a) = never.Ýòî ñîîòâåòñòâóåò îïåðàöèè óòî÷íåíèÿ íà D, îòêóäà ìîæíî çàêëþ÷èòü, ÷òî ϕγ = ϕξ ◦ ϕζ .2. Ïóñòü ϕγ = ϕξ ◦ ϕζ .

Òîãäà ϕγ ðàâåí never äëÿ òàêèõ q ∈ P è a ∈ V ,÷òî ϕξ (∗q, a) = never èëè ϕζ (∗q, a) = never. Ýòî ìîæíî çàïèñàòüñëåäóþùèì îáðàçîì:ϕξ (∗q, a) = never,∀q ∈ P, ∀a ∈ V → ϕγ (∗q, a) = never ⇔ϕζ (∗q, a) = neverÏðåîáðàçóåì ïîëó÷åííîå âûðàæåíèå: a 6∈ ξ(q) èëè a 6∈ ζ(q) ⇔ a ∈ξ(q) èëè a ∈ ζ(q).

Îòêóäà ìîæíî çàêëþ÷èòü, ÷òî a ∈ ξ(q) ∪ ζ(q).Òî åñòü ϕγ (∗q, a) = never ⇔ a 6∈ ξ(q) ∩ ζ(q), ÷òî âåðíî äëÿ ïðîèçâîëüíûõ q è a. Òî åñòü γ = ξ ◦ ζ .Òåîðåìà 3 (Î êîìïîçèöèè êîíñåðâàòèâíûõ àíàëèçîâ óêàçàòåëåé). Ïóñòüξ è ζ - êîíñåðâàòèâíûå àíàëèçû óêàçàòåëåé. Òîãäà γ = ξ ◦ ζ òàêæå ÿâëÿåòñÿ êîíñåðâàòèâíûì àíàëèçîì àëèàñîâ, ïðè÷åì ξ ≤ γ è ζ ≤ γ .18Èç ëåììû 2 èìååì, ÷òî ϕγ = ϕξ ◦ ϕζ . Èç òåîðåìûî êîìïîçèöèè êîíñåðâàòèâíûõ àíàëèçîâ àëèàñîâ èìååì, ÷òî ϕγ êîíñåðâàòèâåí, à òàêæå, ÷òî ϕξ ≤ ϕγ è ϕζ ≤ ϕγ .

Òîãäà γ êîíñåðâàòèâåí ïîîïðåäåëåíèþ. Èç ëåììû 1 ïîëó÷àåì, ÷òî ξ ≤ γ è ζ ≤ γ .Äîêàçàòåëüñòâî.4.6Òåîðåìà î êîíñåðâàòèâíîñòè àíàëèçà óêàçàòåëåéÒåîðåìà 4. Ïóñòüòîëüêî òîãäà, êîãäàξ - àíàëèç óêàçàòåëåé. ξ êîíñåðâàòèâåí òîãäà èξ ≤ ρ∗ .1. Ïóñòü ξ ≤ ρ∗ . Èç ëåììû 1 èìååì, ÷òî ϕξ ≤ ϕρ∗ .Òàê êàê ϕρ∗ êîíñåðâàòèâåí, òî è ϕξ òîæå êîíñåðâàòèâåí. Îòêóäà ïîîïðåäåëåíèþ ξ êîíñåðâàòèâåí.Äîêàçàòåëüñòâî.2. Ïóñòü ξ êîíñåðâàòèâåí.