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

èçìåíåíèå îäíîé âñåãäà âëå÷åò çà ñîáîé èçìåíåíèå âòîðîéïåðåìåííîé• may îòâå÷àåò òîìó, ÷òî äâå ïåðåìåííûå ìîãóò áûòü àëèàñîì, ò.å.èçìåíåíèå îäíîé ìîæåò ïîâëå÷ü çà ñîáîé èçìåíåíèå âòîðîé ïåðåìåííîé, à ìîæåò è íåò• never îòâå÷àåò òîìó, ÷òî äâå ïåðåìåííûå òî÷íî íå ÿâëÿþòñÿ àëèàñàìè, ò.å. èçìåíåíèå îäíîé íèêîãäà íå âëå÷åò çà ñîáîé èçìåíåíèåâòîðîé ïåðåìåííîéÎïðåäåëåíèå 2 (Àíàëèç àëèàñîâ). Àíàëèçîì àëèàñîâ íàçîâåì îòîáðàæåíèå ϕ : V × V → D òàêîå, ÷òî ∀a, b ∈ V → ϕ(a, b) = ϕ(b, a).Òî åñòü, àíàëèç àëèàñîâ åñòü ñîïîñòàâëåíèå êàæäîé ïàðå ïåðåìåííûõíåêîòîðîãî ðåøåíèÿ î òîì, ìîãóò ëè äàííûå ïåðåìåííûå áûòü àëèàñîìèëè íåò.2.2ÑðàâíåíèåÂâåäåì òàêæå ñðàâíåíèå2ðàçëè÷íûõ àíàëèçîâ àëèàñîâ.Ïóñòü ϕ è ψ - àíàëèçû àëèàñîâ. Òîãäà áóäåì ãîâîðèòü,ψ è îáîçíà÷àòü ϕ ≤ ψ , åñëèmust, òîëüêî åñëè ψ(v1 , v2 ) = must∀v1 , v2 ∈ V → ϕ(v1 , v2 ) = never, òîëüêî åñëè ψ(v1 , v2 ) = nevermay,ïðè ëþáûõ çíà÷åíèÿõ ψ(v1 , v2 )Îïðåäåëåíèå 3.÷òî ϕñëàáåå1Ïî ñóòè ñâîåé òàêîå ìíîæåñòâî ðåøåíèé ñîîòâòåòñâóåò òðåõçíà÷íîé ëîãèêåÍå âñÿêèå äâà àíàëèçà àëèàñîâ ìîæíî ñðàâíèòü ïðè ïîìîùè äàííîé îïåðàöèèîòíîøåíèÿ28Áóäåì ãîâîðèòü, ÷òî ϕ ñòðîãî ñëàáåå ψ è îáîçíà÷àòüϕ < ψ , åñëè ϕ ≤ ψ è ∃v, w ∈ V : ψ(v, w) ∈ {must, never}, ϕ(v, w) = may .Îïðåäåëåíèå 4.Òî åñòü, åñëè ϕ ≤ ψ è äëÿ íåêîòîðûõ v, w ∈ V âûïîëíÿåòñÿ ϕ(v, w) =must, òî ψ(v, w) = must.

Îáðàòíîå, âîîáùå ãîâîðÿ, íå âåðíî. Àíàëîãè÷íîå âåðíî è äëÿ never.Óòâåðæäåíèå 1. Ââåäåííàÿ îïåðàöèÿ ñðàâíåíèÿ îáëàäàåò ñâîéñòâîìòðàíçèòèâíîñòè, òî åñòü, åñëèϕ, ψ è χ - àíàëèçû àëèàñîâ è ϕ ≤ ψ ,ψ ≤ χ, òî âåðíî, ÷òî ϕ ≤ χ.Ðàññìîòðèì âñå v, w ∈ V : ϕ(v, w) = must. Òàê êàê ϕ ≤ψ , òî ψ(v, w) = must. Òàê êàê ψ ≤ χ, òî χ(v, w) = must. Ïîëó÷èëè, ÷òîåñëè ϕ(v, w) = must, òî χ(v, w) = must. Àíàëîãè÷íî ìîæíî ïîëó÷èòü,÷òî åñëè ϕ(v, w) = never, òî χ(v, w) = never.

Òî åñòü ϕ ≤ χ.Äîêàçàòåëüñòâî.Àíàëîãè÷íî äîêàçûâàåòñÿ òðàíçèòèâíîñòü ñòðîãîãî ñðàâíåíèÿ.2.3ÊîíñåðâàòèâíîñòüÊàê âû ìîãëè äîãàäàòüñÿ, åñëè ðàññìàòðèâàòü âñå òàêèå îòîáðàæåíèÿ,òîëêó îò ýòîãî áóäåò, ìÿãêî ãîâîðÿ, íèêàêîãî. Àíàëèç àëèàñîâ, åñòåñòâåííî, äîëæåí áûòü ñâÿçàí ñ ñåìàíòèêîé êîíêðåòíîé ïðîãðàììû.Äëÿ êàæäîé ïðîãðàììû ñóùåñòâóåò àíàëèç àëèàñîâ, êîòîðûé íàèáîëåå òî÷íî îïèñûâàåò êîíêðåòíî åå.

Òàêîé àíàëèç àëèàñîâ áóäåì íàçûâàòüòî÷íûì è îáîçíà÷àòü φ∗ .Îïðåäåëåíèå 5.åñëè ϕ ≤ φ∗ .Àíàëèç àëèàñîâ ϕ áóäåì íàçûâàòü êîíñåðâàòèâíûì,Óòâåðæäåíèå 2. Ïóñòüñåðâàòèâåí èϕ è ψ - àíàëèçû àëèàñîâ. Òîãäà, åñëè ϕ êîíψ ≤ ϕ, òî ψ êîíñåðâàòèâåí.Äîêàçàòåëüñòâî íåïîñðåäñòâåííî ñëåäóåò èç òðàíçèòèâíîñòè ñðàâíåíèÿ: ψ ≤ ϕ, ϕ ≤ φ∗ ⇒ ψ ≤ φ∗Äîêàçàòåëüñòâî.Ïðè ýòîì ñóùåñòâóåò î÷åâèäíûé àíàëèç àëèàñîâ, ÿâëÿþùèéñÿ ïðèýòîì êîíñåðâàòèâíûì.Áóäåì íàçûâàòü òðèâèàëüíûì è îáîçíà÷àòü φ− àíàëèç àëèàñîâ òàêîé, ÷òîÎïðåäåëåíèå 6.∀v, w ∈ V → φ− (v, w) = mayÅñëè ãîâîðèòü îá àíàëèçå àëèàñîâ â êîíòåêñòå êîìïèëÿòîðíûõ îïòèìèçàöèé, òî èìååò ñìûñë ðàññìàòðèâàòü ëèøü êîíñåðâàòèâíûå îòîáðàæåíèÿ, ò.å.

çàäà÷à ñîñòîèò â ïîèñêå ϕ : φ− ≤ ϕ ≤ φ∗ .92.4Êîìïîçèöèÿ(Óòî÷íåíèå). Íà ìíîæåñòâå ðåøåíèé D îïåðàöèåé óòî÷áèíàðíóþ îïåðàöèþ × ñî ñëåäóþùåé òàáëèöåé èñòèííî-Îïðåäåëåíèå 7íåíèÿ íàçîâåìñòè 1 :×nevermustmaynevernevernevermustmustmustmaynevermustmayÎïåðàöèÿ óòî÷íåíèÿ ÿâëÿåòñÿ êîììóòàòèâíîé è àññîöèàòèâíîé, ÷òîëåãêî óñòàíàâëèâàåòñÿ èç òàáëèöû èñòèííîñòè.(Êîìïîçèöèÿ). Êîìïîçèöèåé àíàëèçîâ àëèàñîâ ϕ è ψáóäåì íàçûâàòü ñëåäóþùèé îïåðàöèþ:Îïðåäåëåíèå 8χ = ϕ ◦ ψ ⇔ ∀v, w ∈ V → χ(v, w) = ϕ(v, w) × ψ(v, w)Èç êîììóòàòèâíîñòè è àññîöèàòèâíîñòè óòî÷íåíèÿ íåïîñðåäñòâåííîñëåäóåò è êîììóòàòèâíîñòü è àññîöèàòèâíîñòü êîìïîçèöèè.Óòâåðæäåíèå 3.

Ïóñòü ϕ è ψ - àíàëèçû àëèàñîâ, χ = ϕ ◦ ψ è N ={(v, w) ∈ V × V : ϕ(v, w), ψ(v, w) ∈ {must, never} è ϕ(v, w) 6= ψ(v, w)},òîãäà íà ìíîæåñòâå N χ ÿâëÿåòñÿ àíàëèçîì àëèàñîâ.∀(a, b) ∈ N ðàññìîòðèì χ(a, b) = ϕ(a, b) × ψ(a, b) ={òàê êàê ϕ è ψ - àíàëèçû àëèàñîâ} = ϕ(b, a) × ψ(b, a) = {òàê êàê (a, b) ∈N , òî îïåðàöèÿ óòî÷íåíèÿ â äàííîì ñëó÷àå îïðåäåëåíà } = χ(b, a)Äîêàçàòåëüñòâî.2.5Òåîðåìà î êîìïîçèöèè êîíñåðâàòèâíûõ àíàëèçîâ àëèàñîâ(Î êîìïîçèöèè êîíñåðâàòèâíûõ àíàëèçîâ àëèàñîâ). Ïóñòüϕ è ψ - êîíñåðâàòèâíûå àíàëèçû àëèàñîâ, òîãäà χ = ϕ ◦ ψ ÿâëÿåòñÿîïðåäåëåííûì íà âñåì V ×V êîíñåðâàòèâíûì àíàëèçîì àëèàñîâ, ïðè÷åìϕ ≤ χ è ψ ≤ χ.Òåîðåìà 1Ðàçîáüåì äîêàçàòåëüñòâî íà òðè ÷àñòè: îïðåäåëåííîñòüχ íà âñåì V × V , êîíñåðâàòèâíîñòü χ è âûïîëíåíèå ϕ ≤ χ è ψ ≤ χ.Äîêàçàòåëüñòâî.1.

Äîêàæåì îò ïðîòèâíîãî. Ïóñòü χ îïðåäåëåí íå âåçäå, òîãäà∃v, w ∈ V : ϕ(v, w), ψ(v, w) ∈ {must, never} è ϕ(v, w) 6= ψ(v, w)Áåç îãðàíè÷åíèÿ îáùíîñòè ìîæíî ñ÷èòàòü, ÷òî ϕ(v, w) = never èψ(v, w) = must. Òàê êàê ϕ êîíñåðâàòèâåí, òî ϕ(v, w) = never ⇒φ∗ (v, w) = never. Îäíàêî, ψ òîæå êîíñåðâàòèâåí è àíàëîãè÷íûìîáðàçîì ïîëó÷àåì, ÷òî φ∗ (v, w) = must. Ïðèøëè ê ïðîòèâîðå÷èþ.1Ïðî÷åðê îçíà÷àåò, ÷òî íà ýòîé ïàðå îïåðàöèÿ íå îïðåäåëåíà102. Äîêàæåì îò ïðîòèâíîãî. Ïóñòü χ íåêîíñåðâàòèâåí, òîãäà∃v, w ∈ V : χ(v, w) ∈ {must, never} è φ∗ (v, w) 6= χ(v, w)Áåç îãðàíè÷åíèÿ îáùíîñòè ìîæíî ñ÷èòàòü, ÷òî χ(v, w) = never èφ∗ (v, w) = must. Òàê êàê χ = ϕ◦ψ , òî ϕ(v, w)×ψ(v, w) = never. Îòêóäà ñëåäóåò, ÷òî êàê ìèíèìóì îäíî èç ϕ(v, w) è ψ(v, w) ðàâíÿåòñÿnever.

Äëÿ îïðåäåëåííîñòè áóäåì ñ÷èòàòü, ÷òî ϕ(v, w) = never.Òàê êàê ϕ êîíñåðâàòèâåí, òî ϕ(v, w) = never ⇒ φ∗ (v, w) = never.Îäíàêî, âûøå óæå áûëî îïðåäåëåíî, ÷òî φ∗ (v, w) = must. Ïðèøëèê ïðîòèâîðå÷èþ.3. Òàê êàê êîìïîçèöèÿ êîììóòàòèâíà, òî äîñòàòî÷íî äîêàçàòü, ÷òîϕ ≤ χ. Ïîêàæåì, ÷òî∀v, w ∈ V : ϕ(v, w) ∈ {must, never} ⇒ χ(v, w) = ϕ(v, w)Âîçüìåì v, w : ϕ(v, w) = never, òîãäà χ(v, w) = never × ψ(v, w). Òàêêàê χ îïðåäåëåí íà âñåì V × V , òî ψ(v, w) ∈ {never, may}.

Òîãäàχ(v, w) = never. Àíàëîãè÷íî ïîêàçûâàåòñÿ, ÷òî äëÿ v, w : ϕ(v, w) =must âåðíî, ÷òî χ(v, w) = must. Îòêóäà ïî îïðåäåëåíèþ ϕ ≤ χ.Äîïîëíåíèå 1. Åñëè â óñëîâèÿõ òåîðåìû î êîìïîçèöèè êîíñåðâàòèâ-íûõ àíàëèçîâ àëèàñîâϕ ≤ ψ , òî χ = ψ .Ðàññìîòðèì ïðîèçâîëüíûå v, w ∈ V .Ïóñòü ψ(v, w) = never. Òàê êàê ψ ≤ χ, òî χ(v, w) = never. Àíàëîãè÷íî ïîêàçûâàåòñÿ, ÷òî åñëè ψ(v, w) = must, òî χ(v, w) = must.Ïóñòü ψ(v, w) = may . Òàê êàê èç òåîðåìû ϕ ≤ ψ , òî ϕ(v, w) = may .Òîãäà χ(v, w) = ϕ(v, w) × ψ(v, w) = may × may = may = ψ(v, w). Îòêóäàïîëó÷àåì, ÷òî çíà÷åíèÿ χ è ψ äëÿ ïðîèçâîëüíûõ v, w ñîâïàäàþò, òî åñòüχ = ψ.Äîêàçàòåëüñòâî.Äîïîëíåíèå 2.

Åñëè â óñëîâèÿõ òåîðåìû î êîìïîçèöèè êîíñåðâàòèâ-íûõ àíàëèçîâ àëèàñîâÄîêàçàòåëüñòâî.ϕ è ψ íåñðàâíèìû, òî ϕ < χ è ψ < χ.Åñëè ϕ è ψ íåñðàâíèìû, òî∃v1 , w1 ∈ V : ϕ(v1 , w1 ) = may, à ψ(v1 , w1 ) ∈ {must, never}∃v2 , w2 ∈ V : ψ(v2 , w2 ) = may, à ϕ(v2 , w2 ) ∈ {must, never}Äëÿ îïðåäåëåííîñòè áóäåì ñ÷èòàòü, ÷òî ψ(v1 , w1 ) = ϕ(v2 , w2 ) = must.Ðàññìîòðèì çíà÷åíèÿ χ(v1 , w1 ) è χ(v2 , w2 ):χ(v1 , w1 ) = ϕ(v1 , w1 ) × ψ(v1 , w1 ) = may × must = must11χ(v2 , w2 ) = ϕ(v2 , w2 ) × ψ(v2 , w2 ) = must × may = mustÈç òåîðåìû ϕ ≤ ψ . Ó÷èòûâàÿ òàêæå, ÷òî ∃v1 , w1 ∈ V : ϕ(v1 , w1 ) =may, à χ(v1 , w1 ) = must, ïî îïðåäåëåíèþ ïîëó÷àåì, ÷òî ϕ < χ.Àíàëîãè÷íî ïîêàçûâàåì, ÷òî ψ < χ.2.6Ïðîñòåéøèé íåòðèâèàëüíûé àíàëèç àëèàñîâÄàííûé ïîäõîä ÿâëÿåòñÿ ïåðâûì ïîäõîäîì ê àíàëèçó àëèàñîâ, êîòîðûéìîæåò ïðåäîñòàâëÿòü õîòü êàêóþ-òî ïîëåçíóþ èíôîðìàöèþ.Ïåðåä òåì, êàê ïðåäñòàâèòü ñîáñòâåííî àíàëèç àëèàñîâ, ââåäåì íåñêîëüêî îáîçíà÷åíèé.Ïóñòü G ⊆ V - ìíîæåñòâî ãëîáàëüíûõ ïåðåìåííûõ, àR = {v : v ∈ V, ∃p ∈ V : v = ∗p} - ìíîæåñòâî ðàçûìåíîâàíèé óêàçàòåëåé(ìíîæåñòâî çíà÷åíèé v èç V òàêèõ, ÷òî ñóùåñòâóåò ïåðåìåííàÿ p èç V ,ðàçûìåíîâàíèåì êîòîðîé è ÿâëÿåòñÿ v ).Îáðàùàÿñü òåïåðü ê êîäó öåëåâîé ïðîãðàììû, ðàññìîòðèì âñå v ∈ Vòàêèå, ÷òî ïîäâåðãàëèñü îïåðàöèè âçÿòèÿ àäðåñà, ò.å.

â êîäå ïðîãðàììûñóùåñòâóåò èíñòðóêöèÿ, â êîòîðóþ âõîäèò &v . Ìíîæåñòâî òàêèõ ïåðåìåííûõ îáîçíà÷èì A.Àíàëèçîì àëèàñîâ ïî âçÿòèþ àäðåñà (address-taken) íàçîâåì ñëåäóþùèé àíàëèç àëèàñîâ:åñëè v, w ∈ Rmay,Aϕ (v, w) = may,åñëè v ∈ R, w ∈ A ∪ Gnever, â îñòàëüíûõ ñëó÷àÿõÏîñòðîèì ϕA äëÿ äàííîãî ïðèìåðà.Äëÿ ýòîãî ïîñòðîèì ìíîæåñòâà V, G, R è A.Ïðèìåð 12.int c ;void foo () {int a , b , *p , * q ;p = &a;a = 3 , b = 4;. . .* q = 5;}V = {a, b, c, p, q, ∗p, ∗q, .

. . }.G = {c}, ò.ê. ïåðåìåííàÿ c - ãëîáàëüíàÿ.A = {a}, ò.ê. â êîäå ïðîãðàììû ïðèñóòñòâóåò èíñòðóêöèÿ p = &a.R = {∗p, ∗q}, ò.ê. p, q ∈ V .Òîãäà ϕA (∗p, ∗q) = ϕA (∗p, a) = ϕA (∗q, a) = ϕA (∗p, c) = ϕA (∗q, c) =may . Äëÿ âñåõ îñòàëüíûõ çíà÷åíèé èç V × V ôóíêöèÿ ϕA ðàâíà never.12 äàííîì ñëó÷àå, àíàëèç àëèàñîâ ïîçâîëèò ïîíÿòü, ÷òî ó ïåðåìåííîéb íåò àëèàñîâ, ÷åãî íå ìîã äàòü òðèâèàëüíûé ïîäõîä.3Âèäû àíàëèçîâÎòòàëêèâàòüñÿ îò òðèâèàëüíîãî ðåøåíèÿ äëÿ ïîèñêà ïîäõîäÿùåãî (êàêýòî äåëàëîñü â ñëó÷àå àíàëèçà àëèàñîâ ïî âçÿòèþ àäðåñà) íå ÿâëÿåòñÿîïòèìàëüíûì ïîäõîäîì.

Ïîýòîìó áóäåì ïðîáîâàòü ýôôåêòèâíî ñ÷èòàòüàíàëèçû àëèàñîâ íàèáîëåå ïðèáëèæåííûå ê φ∗ , íåæåëè ê φ− . Äëÿ ýòîãî ïîïðîáóåì êëàññèôèöèðîâàòü âñå ìíîãîîáðàçèå àíàëèçîâ àëèàñîâ èðåøèòü óæå áîëåå óçêî â êàêîì èìåííî êëàññå ìû áóäåì ðàáîòàòü.3.1Îñíîâíûå âèäûÇäåñü áóäóò ïåðå÷èñëåíû è îïèñàíû 1 îñíîâíûå êëàññû àíàëèçîâ àëèàñîâ. Äàííûå òåðìèíû îáùåïðèíÿòû è èñïîëüçóþòñÿ ïðè îáùåì îïèñàíèèëþáîãî àíàëèçà àëèàñîâ.3.1.1ÌåæïðîöåäóðíîñòüÐàçëè÷àþò ìåæïðîöåäóðíûå è âíóòðèïðîöåäóðíûå àíàëèçû àëèàñîâ,êîòîðûå ðàçëè÷àþòñÿ òåì, ÷òî ïåðâûå ó÷èòûâàþò âçàèìîäåéñòâèÿ ìåæäó ðàçëè÷íûìè ôóíêöèÿìè â ïðîãðàììå è èñïîëüçóþò èíôîðìàöèþ ñðàçó î âñåõ ôóíêöèÿõ â ïðîãðàììå, à âòîðûå èñïîëüçóþò èíôîðìàöèþëèøü îäíîé ôóíêöèè.Åñëè ãîâîðèòü î âíóòðèïðîöåäóðíîì àíàëèçå, òî ôîðìàëüíî åãî ìîæíî ïðåäñòàâèòü ñëåäóþùèì îáðàçîì.Ïðåäñòàâèì ìíîæåñòâî ïåðåìåííûõ V â âèäå G ∪ V1 ∪ V2 ∪ · · · ∪ Vm ,ãäå m - ÷èñëî ôóíêöèé â ðàññìàòðèâàåìîé ïðîãðàììå, à Vi - ìíîæåñòâîïåðåìåííûõ i-îé ôóíêöèè, ïðè÷åì ∀i, j ∈ [1, m] : i 6= j → Vi ∩ Vj = ∅.