Kill(B) = { X op Y | either X or Y defined before use of x op Y in B} Gen(B) = {x op Y | X op Y used in B before any definition of X or Y}
Transfer Equation
In(B) = (Out(B) - Kill(B)) Gen(B)
Confluence Equation
Out(B) = In(S)
Algorithm for Computing Very Busy Expressions
We want to avoid considering X op Y as very busy just because neither X nor Y is redefined. To do this, we introduce a dummy block D such that
Kill(D) = all expressions Gen(D) = none
and we let D be a successor of all blocks that have the program end as a possible successor.
Algorithm
Very Busy Expressions
FOR each block B DO Out(B) := all expressions In(B) := (Out(B) - Kill(B)) Gen(B)) END WHILE there are changes DO FOR each block B DO Out(B) = In(S)
Send questions and comments to: Karen Lemone