Reaching Definition

In compiler optimization, a instruction defining a variable reaches an instruction iff a path in the CFG from to , where, along that path, there are no other assignments to .

Some terminologies:

  • use: An instruction uses all of 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.