Available Expressions Analysis -the basic idea X1 X2 N=X10X2 x:=a kil训 X=(N\fexpressions with an x}) (subexpressions of a without an gen PPA Section 2.1 C)F.Nielson H.Riis Nielson C.Hankin (May 2005) 11
Available Expressions Analysis – the basic idea X1 X2 ❍❍❍❍❍❍❍❍❍❍❍❍❍❍❍❍❥ ✟✟ ✟ ✟ ✟✟ ✟✟ ✟ ✟ ✟✟ ✟✟ ✟✙✟ N = X1 ∩ X2 x := a X = (N\ kill z }| { {expressions with an x} ) ∪ {subexpressions of a without an x} | {z } gen ❄ PPA Section 2.1 c F.Nielson & H.Riis Nielson & C.Hankin (May 2005) 11
Available Expressions Analysis kill and gen functions killAE([x:=a)={a'∈AExp*|x∈FV(a')} killAE([skip]e) =0 killAE([]) =0 genAE([:a]e) Ha'E AExp(a)xFV(a)} genAE([skip]) 0 genAE([6])=AExp(6) data flow equations:AE- 0 AEenir(④={HAE(eI(e,)∈f1ow(S:)} if e=init(S) otherwise AEexit(e)=(AEentry(e)\killAE(Be))UgenAE(Be) where B∈blocks(S*) PPA Section 2.1 F.Nielson H.Riis Nielson C.Hankin (May 2005) 12
Available Expressions Analysis kill and gen functions killAE([x := a] `) = {a 0 ∈ AExp? | x ∈ FV(a 0)} killAE([skip] `) = ∅ killAE([b] `) = ∅ genAE([x := a] `) = {a 0 ∈ AExp(a) | x 6∈ FV(a 0)} genAE([skip] `) = ∅ genAE([b] `) = AExp(b) data flow equations: AE= AEentry(`) = ( ∅ if ` = init(S?) T {AEexit(` 0) | (` 0 , `) ∈ flow(S?)} otherwise AEexit(`) = (AEentry(`)\killAE(B`)) ∪ genAE(B`) where B` ∈ blocks(S?) PPA Section 2.1 c F.Nielson & H.Riis Nielson & C.Hankin (May 2005) 12
Example: [x:=a+b];[y:=a*b]2;while [y>a+b]3 do ([a:=a+1]4;[x:=a+b]5) kill and gen functions: L KillAE(e) genAE(e) 1 0 a+bl 0 {a*b} 3 0 {a+b} 4 a+b,a*b, a+1} 0 5 0 {a+b} PPA Section 2.1 F.Nielson H.Riis Nielson C.Hankin (May 2005) 13
Example: [x:=a+b] 1 ; [y:=a*b] 2 ; while [y>a+b] 3 do ([a:=a+1] 4 ; [x:=a+b] 5 ) kill and gen functions: ` killAE(`) genAE(`) 1 ∅ {a+b} 2 ∅ {a*b} 3 ∅ {a+b} 4 {a+b, a*b, a+1} ∅ 5 ∅ {a+b} PPA Section 2.1 c F.Nielson & H.Riis Nielson & C.Hankin (May 2005) 13
Example (cont.) [x:=a+b];[y:=a*b]2;whi1e[y>a+b]3do([a:=a+1]4;[x:=a+b]5) Equations: AEentry(1) = 0 AEentry(2) 三 AEerit(1) AEentry(3) 三 AEerit(2)nAEexit(5) AEentry(4) =AEerit(3) AEentry(5) AEerit(4) AEerit(1) =AEentry(1)U{a+b} AEexit(2) =AEentry(2)U{a*b} AEerit(3) =AEentry(3)U{a+b} AEerit(4) = AEentry(4)\{a+b,a*b,a+1} AEerit(5)= AEentry(5)U{a+b} PPA Section 2.1 CF.Nielson H.Riis Nielson C.Hankin (May 2005) 14
Example (cont.): [x:=a+b] 1 ; [y:=a*b] 2 ; while [y>a+b] 3 do ([a:=a+1] 4 ; [x:=a+b] 5 ) Equations: AEentry(1) = ∅ AEentry(2) = AEexit(1) AEentry(3) = AEexit(2) ∩ AEexit(5) AEentry(4) = AEexit(3) AEentry(5) = AEexit(4) AEexit(1) = AEentry(1) ∪ {a+b} AEexit(2) = AEentry(2) ∪ {a*b} AEexit(3) = AEentry(3) ∪ {a+b} AEexit(4) = AEentry(4)\{a+b, a*b, a+1} AEexit(5) = AEentry(5) ∪ {a+b} PPA Section 2.1 c F.Nielson & H.Riis Nielson & C.Hankin (May 2005) 14
Example (cont.): [x:=a+b]l;[y:=a*b]2;while[y>a+b]3do([a:=a+1]4;[x:=a+b]5) Largest solution: AEentry(e)AEerit(e) 1 0 {a+b} 2 {a+b} [a+b,a*b} {a+b} {a+b} 4 {a+b} 0 5 9 {a+b} PPA Section 2.1 C F.Nielson H.Riis Nielson C.Hankin (May 2005) 15
Example (cont.): [x:=a+b] 1 ; [y:=a*b] 2 ; while [y> a+b ] 3 do ([a:=a+1] 4 ; [x:=a+b] 5 ) Largest solution: ` AEentry(`) AEexit(`) 1 ∅ {a+b} 2 {a+b} {a+b, a*b} 3 {a+b} {a+b} 4 {a+b} ∅ 5 ∅ {a+b} PPA Section 2.1 c F.Nielson & H.Riis Nielson & C.Hankin (May 2005) 15