The goal of the data flow analysis is to extract some facts of the program at a given program point

• IN[s] contains the set of facts that are true before statement s
• OUT[s] contains the set of facts that are true after statement s
• forward and backward data flow analysis

constant propagation (lecture 4 & 5)

The goal of constant propagation data-flow analysis is to find out whether the value of a variable is constant at a given program point or not.

• in and out

• forward data flow analysis

• meet operator

• transfer function

• initialization: OUT[BB] = UNDEF

• constant propagation in ssa form

  

live variable (lecture 5)

The variable x is not live at point p if the expected behavior of the program doesn’t change even if you assign a garbage value to x at point p.

• backward data flow analysis

• meet operator: OUT BB = Union of successors IN[S]

• in and out

• initialization

  for each BB != EXIT:
  		IN[BB] = {}
  

All the variables that are live at the ENTRY basic block are uninitialized variables.

• Other uses of live variable
  • Global register allocation
  • SSA construction
  • Discover useless stores