Available Expressions

• $I{n}_s={\bigcap }_{p\in predecessors}Ou{t}_p$
  • This is the set of expressions available before statement s
  • Available means the expression has been computed on every path to s and it is unchanged since last computation
• $Ou{t}_s=Ge{n}_s\bigcup (I{n}_s-Kil{l}_s)$
  • The set of expressions available immediately after computing s which is the statement s computes minus those that have been invalidated by $Kil{l}_s$
• In: set of expressions available at beginning
• Out: set of expressions available at end
• Gen: set of expressions created in statement
• Kill: set of expressions killed by assignments in stmt

Analysis with Loops and Branches

• Similar to straight line analysis, we can compute the $Gen$ and $Kill$ sets after one step since these don’t depend on the ordering of blocks.
• Now we want to define expressions for our $In$ sets. These depend on the flow of the Control Flow of our program instead of just the $Ou{t}_{s-1}$. It is the $Ou{t}_{si}\bigcup Ou{t}_{sn}$ or, the out of all program blocks that lead back to program block s.
• Now we have $Gen$, $Kill$, and an expression for $In$. We can use the equation for $Out$ from the straight line analysis.
• Now we iterate: Out → In
• Stop when another round of iterations changes nothing