Example (cont.): [x:=5];[y:=1]2;whi1ex>1]3do([y:=x*y]4;[x:=x-1]5) Equations: RDentry(1) = {(x,),(y,?)} RDentry((2） 三 RDerit(1) RDentry(3) = RDerit(2)URDerit(5) RDentry(4) 三 RDerit(3) RDentry(5) = RDerit(4) RDerit(1) = (RDentry(1)八{(x,),(x,1),(x,5)})U{(x,1)} RDerit(2) (RDentry(2)八{(y,?),(y,2),(y,4)})U{(y,2)} RDexit(3)= RDentry(3) RDezit(4) = (RDentry(4八{(y,?),(y,2),(y,4)})U{(y,4)} RDexit(5) = (RDentry(5)八{(x,?),(x,1),(x,5)})U{(x,5)} PPA Section 2.1 CF.Nielson H.Riis Nielson C.Hankin (May 2005) 21
Example (cont.): [x:=5] 1 ; [y:=1] 2 ; while [x>1] 3 do ([y:=x*y] 4 ; [x:=x-1] 5 ) Equations: RDentry(1) = {(x, ?), (y, ?)} RDentry(2) = RDexit(1) RDentry(3) = RDexit(2) ∪ RDexit(5) RDentry(4) = RDexit(3) RDentry(5) = RDexit(4) RDexit(1) = (RDentry(1)\{(x, ?), (x, 1), (x, 5)}) ∪ {(x, 1)} RDexit(2) = (RDentry(2)\{(y, ?), (y, 2), (y, 4)}) ∪ {(y, 2)} RDexit(3) = RDentry(3) RDexit(4) = (RDentry(4)\{(y, ?), (y, 2), (y, 4)}) ∪ {(y, 4)} RDexit(5) = (RDentry(5)\{(x, ?), (x, 1), (x, 5)}) ∪ {(x, 5)} PPA Section 2.1 c F.Nielson & H.Riis Nielson & C.Hankin (May 2005) 21
Example (cont.) [x:=5];[y:=1]2;whi1e[x>1]3do(y:=x*y]4;x:=x-15) Smallest solution: RDentry(e) RDerit(e) 1 {(x,?),(y,) {(y,),(x,1)} 2 {(y,7),(x,1)} {(x,1),(y,2)} 3 {(x,1),(y,2),(y,4),(x,5)} {(x,1),(y,2),(y,4),(x,5)} 4 {(x,1),(y,2),(y,4),(x,5)} {(x,1),(y,4),(x,5)} 5 {(x,1),(y,4),(x,5)} {(y,4),(x,5)} PPA Section 2.1 C F.Nielson H.Riis Nielson C.Hankin (May 2005) 22
Example (cont.): [x:=5] 1 ; [y:=1] 2 ; while [x>1] 3 do ([y:= x*y ] 4 ; [x:=x-1] 5 ) Smallest solution: ` RDentry(`) RDexit(`) 1 {(x, ?), (y, ?)} {(y, ?), (x, 1)} 2 {(y, ?), (x, 1)} {(x, 1), (y, 2)} 3 {(x, 1), (y, 2), (y, 4), (x, 5)} {(x, 1), (y, 2), (y, 4), (x, 5)} 4 {(x, 1), (y, 2), (y, 4), (x, 5)} {(x, 1), (y, 4), (x, 5)} 5 {(x, 1), (y, 4), (x, 5)} {(y, 4), (x, 5)} PPA Section 2.1 c F.Nielson & H.Riis Nielson & C.Hankin (May 2005) 22
Why smallest solution? [z:=xty];while [true]e do [skip]e Equations: RDentry(e) {(x,?),(y,?),(z,)} RDentry(e) -RDerit(e)URDerit(e") RDentry(")= RDerit(e) no RDerit(e)=(RDentry(e)\{(z,?)})U{(z,e)} yes RDerit(e')=RDentry(e') RDerit(e")=RDentry(e") 【小 After some simplification:RDentry(e)={(x,?)(y,?),(z,e)}URDentry (e) Many solutions to this equation:any superset of {(x,?)(y,?),(z,e)} PPA Section 2.1 CF.Nielson H.Riis Nielson C.Hankin (May 2005) 23
Why smallest solution? [z:=x+y] ` ; while [true] ` 0 do [skip] ` 00 Equations: RDentry(`) = {(x, ?), (y, ?), (z, ?)} RDentry(` 0 ) = RDexit(`)∪RDexit(` 00) RDentry(` 00) = RDexit(` 0 ) RDexit(`) = (RDentry(`) \ {(z, ?)})∪{(z, `)} RDexit(` 0 ) = RDentry(` 0 ) RDexit(` 00) = RDentry(` 00) [· · ·] ` 00 [· · ·] ` 0 [· · ·] ` ❄ ❄ ❄ ❄ ✲ yes no After some simplification: RDentry(` 0) = {(x, ?), (y, ?), (z, `)} ∪ RDentry(` 0) Many solutions to this equation: any superset of {(x, ?), (y, ?), (z, `)} PPA Section 2.1 c F.Nielson & H.Riis Nielson & C.Hankin (May 2005) 23
Very Busy Expressions Analysis An expression is very busy at the exit from a label if,no matter what path is taken from the label,the expression is always used before any of the variables occurring in it are redefined. The aim of the Very Busy Expressions Analysis is to determine For each program point,which expressions must be very busy at the exit from the point. Example: point of interest if [a>b]1 then ([x:-b-a ]2;[y:=a-b]3)else ([y:=b-a]4;[x:-a-b]5) The analysis enables a transformation into [t1:-b-a]A;[t2:=b-a]B; if[a>b]1then([x:=t1]2;[y:=t2]3)else([y:=t1]4;[x:=t2]5) PPA Section 2.1 CF.Nielson H.Riis Nielson C.Hankin (May 2005) 24
Very Busy Expressions Analysis An expression is very busy at the exit from a label if, no matter what path is taken from the label, the expression is always used before any of the variables occurring in it are redefined. The aim of the Very Busy Expressions Analysis is to determine For each program point, which expressions must be very busy at the exit from the point. Example: point of interest ⇓ if [a>b] 1 then ([x:= b-a ] 2 ; [y:= a-b ] 3 ) else ([y:= b-a ] 4 ; [x:= a-b ] 5 ) The analysis enables a transformation into [t1:= b-a ] A; [t2:= b-a ] B; if [a>b] 1 then ([x:=t1] 2; [y:=t2] 3) else ([y:=t1] 4; [x:=t2] 5) PPA Section 2.1 c F.Nielson & H.Riis Nielson & C.Hankin (May 2005) 24
Very Busy Expressions Analysis the basic idea kilI N=(X\fall expressions with an x) U {all subexpressions of a} gen x:=a X=N1∩N2 N1 N2 PPA Section 2.1 C F.Nielson H.Riis Nielson C.Hankin (May 2005) 25
Very Busy Expressions Analysis – the basic idea N1 N2 ✟ ✟✟✟ ✟✟✟ ✟✟✟ ✟✟✟ ✟✟✟✯ ❍❍ ❍❍ ❍❍ ❍❍ ❍❍ ❍❍ ❍❍ ❍❨❍ X = N1 ∩ N2 x := a N = (X\ kill z }| { {all expressions with an x} ) ∪ {all subexpressions of a} | {z } gen ✻ PPA Section 2.1 c F.Nielson & H.Riis Nielson & C.Hankin (May 2005) 25