9.6.1 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