Why largest solution? [z:=x+y];while [true]e do [skip]e Equations: AEentry(e) 0 AEentry(e) =AEerit(e)nAEerit(e") AEenirv(e)=AEerit(e) no AEerit(e)=AEentry(e)U{x+y} yes AErit(e) =AEentry(e) AEerit(e")=AEentry(e) 【J" After some simplification:AEentry(e)={x+y}nAEentry(e) Two solutions to this equation:{x+y}and 0 PPA Section 2.1 CF.Nielson H.Riis Nielson C.Hankin (May 2005) 16
Why largest solution? [z:=x+y] ` ; while [true] ` 0 do [skip] ` 00 Equations: AEentry(`) = ∅ AEentry(` 0 ) = AEexit(`) ∩ AEexit(` 00) AEentry(` 00) = AEexit(` 0 ) AEexit(`) = AEentry(`) ∪ {x+y} AEexit(` 0 ) = AEentry(` 0 ) AEexit(` 00) = AEentry(` 00) [· · ·] ` 00 [· · ·] ` 0 [· · ·] ` ❄ ❄ ❄ ❄ ✲ yes no After some simplification: AEentry(` 0) = {x+y} ∩ AEentry(` 0) Two solutions to this equation: {x+y} and ∅ PPA Section 2.1 c F.Nielson & H.Riis Nielson & C.Hankin (May 2005) 16
Reaching Definitions Analysis The aim of the Reaching Definitions Analysis is to determine For each program point,which assignments may have been made and not overwritten,when program execution reaches this point along some path. Example: point of interest [x:=5];[y:=12;whi1ex>1]3do(y:=x*y]4;[x:=x-1]5) useful for definition-use chains and use-definition chains PPA Section 2.1 C F.Nielson H.Riis Nielson C.Hankin (May 2005) 17
Reaching Definitions Analysis The aim of the Reaching Definitions Analysis is to determine For each program point, which assignments may have been made and not overwritten, when program execution reaches this point along some path. Example: point of interest ⇓ [x:=5] 1 ; [y:=1] 2 ; while [x>1] 3 do ([y:=x*y] 4 ; [x:=x-1] 5 ) useful for definition-use chains and use-definition chains PPA Section 2.1 c F.Nielson & H.Riis Nielson & C.Hankin (May 2005) 17
Reaching Definitions Analysis -the basic idea X1 X2 N=X1UX2 [z:=a] kjII X=(N(c,),(c,1),}) |U,9 gen PPA Section 2.1 C)F.Nielson H.Riis Nielson C.Hankin (May 2005) 18
Reaching Definitions Analysis – the basic idea X1 X2 ❍❍❍❍❍❍❍❍❍❍❍❍❍❍❍❍❥ ✟✟ ✟ ✟ ✟✟ ✟✟ ✟ ✟ ✟✟ ✟✟ ✟✙✟ N = X1 ∪ X2 [x := a] ` X = (N\ kill z }| { {(x, ?), (x, 1), · · ·} ) ∪ {(x, `)} | {z } gen ❄ PPA Section 2.1 c F.Nielson & H.Riis Nielson & C.Hankin (May 2005) 18
Reaching Definitions Analysis kill and gen functions killRD([:=a])={(?) Uf(x,e)Be is an assignment to a in S} killRD([skip]e)= 0 killRD([]) 0 gengD([x :a]e) {(x,)} genRD([skip]e) = 0 genRD([]) = 0 data flow equations:RD= RDn(U((e nowS) {(x,?)|x∈FV(S*)} if e=init(S) otherwise RDerit(e)=(RDentry(e)\killRD(B))UgenRD(B) where B2∈blocks(S*) PPA Section 2.1 C F.Nielson H.Riis Nielson C.Hankin (May 2005) 19
Reaching Definitions Analysis kill and gen functions killRD([x := a] `) = {(x, ?)} ∪{(x, `0) | B` 0 is an assignment to x in S?} killRD([skip] `) = ∅ killRD([b] `) = ∅ genRD([x := a] `) = {(x, `)} genRD([skip] `) = ∅ genRD([b] `) = ∅ data flow equations: RD= RDentry(`) = ( {(x, ?) | x ∈ FV(S?)} if ` = init(S?) S {RDexit(` 0) | (` 0 , `) ∈ flow(S?)} otherwise RDexit(`) = (RDentry(`)\killRD(B`)) ∪ genRD(B`) where B` ∈ blocks(S?) PPA Section 2.1 c F.Nielson & H.Riis Nielson & C.Hankin (May 2005) 19
Example: [x:=5];[y:=1]2;whi1e[x>1]3do([y:=x*y]4;[x:=x-1]5) kill and gen functions: killD(e) genRD() 1 {(x,7),(x,1),(x,5)} {(x,1)} 2 {(y,?),(y,2),(y,4)} {(y,2)} 3 0 0 4 {(y,7),(y,2),(y,4)} {(y,4)} 5 {(x,?),(x,1),(x,5)} {(x,5)} PPA Section 2.1 F.Nielson H.Riis Nielson C.Hankin (May 2005) 20
Example: [x:=5] 1 ; [y:=1] 2 ; while [x>1] 3 do ([y:=x*y] 4 ; [x:=x-1] 5 ) kill and gen functions: ` killRD(`) genRD(`) 1 {(x, ?), (x, 1), (x, 5)} {(x, 1)} 2 {(y, ?), (y, 2), (y, 4)} {(y, 2)} 3 ∅ ∅ 4 {(y, ?), (y, 2), (y, 4)} {(y, 4)} 5 {(x, ?), (x, 1), (x, 5)} {(x, 5)} PPA Section 2.1 c F.Nielson & H.Riis Nielson & C.Hankin (May 2005) 20