reaching definition problem
A instruction d defining a variable v reaches an instruction u iff a path in the CFG from d to u, where, along that path, there no other assignments to v.
- use: An instruction uses all its arguments
- definition: An instruction defines the variable it writes to
- available: Definitions that reach a given program point are available there.
- Kill: Any definition kills all of the currently available definitions
The reaching definitions problem: For every definition and every use, determine whether the definition reaches the use.
By solve this problem, abstract one generic data flow algorithm:
This is equal with dfa_foundation’s worklist algorithm.
So in the analysis algorithm, for different problem, the direction (forward/backward), transfer function and meet operator is user designed.