Equations for Very Busy Expressions

 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)
 

 S  Succ (B)

 
 

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)
 

 S  Succ (B)
 
 
   In(B) = (Out(B) - Kill(B))  Gen(B)
 ENDFOR
 ENDWHILE