GEN and KILL sets

In data-flow analysis , GEN and KILL sets are concepts used to track where locations (~equiv. to place expressions and variables) are used throughout a program.

The $\GEN[B]$ set contains facts that are created within (basic block) $B$.

• Example (reaching definitions), the GEN set of $x\leftarrow a+b$ contains that specific definition of $x$.

• Example (available expressions), the GEN set of $x\leftarrow a+b$ contains the expression $a+b$.

• Example (live variables), the GEN set of $x\leftarrow a+b$ is $\{a,b\}$.

The $\KILL[B]$ set contains facts that are invalidated by $B$.

Reaching Definitions

• def=

Available Expression

Liveness Analysis