<aside> 📝 Not including

• Method Calls
  • Intra-procedural CFG
• Aliases
  • Variables have no aliases </aside>

<aside> 💡 Summary

• Understand the three data flow analyses:
  1. Reaching Definitions
  2. Live Variables
  3. Available Expressions
• Can tell the differences and similarities of the three data flow analyses
• Understand the iterative algorithm and can tell why it is able to terminate </aside>

I. Overview of Data Flow Analysis

Crux

<aside> 📝 may analysis

outputs information that may be true (over-approximation)

</aside>

<aside> 📝 must analysis

outputs information that must be true (under-approximation)

</aside>

Over- and under-approximations are both for safety of analysis

II. Preliminaries of Data Flow Analysis

1. Input and Output States

• Each execution of an IR statement transforms an input state to a new output state
• The input (output) state is associated with the program point before (after) the statement

<aside> 💡 In each data-flow analysis application, we associate with every program point a data-flow value that represents an abstraction of the set of all possible program states that can be observed for that point.

</aside>

• Data flow value only represents abstraction
• The set of possible data-flow values is the domain for this application

<aside> 💡 Data-flow analysis is to find a solution to a set of safe-approximation directed constraints on the IN[s]’s and OUT[s]’s, for all statements s.

• constraints based on semantics of statements (transfer functions)
• constraints based on the flows of control </aside>

2. Notations for Transfer Function’s Constraints

• Forward Analysis $\sf OUT[s] = f_s (IN[s])$
• Backward Analysis $\sf IN[s] = f_s (OUT[s])$

Control flow within a BB

• $\sf IN[s_{i+1} ] = OUT[s_i ],~for~all~ i = 1, 2, …, n-1$

Control flow among BBs

• $\sf IN[B]=IN[s_1]$

• $\sf OUT[B]=OUT[s_n]$

• $\sf OUT[B]=f_B(IN[B]),~f_B=f_{s_n}\circ … \circ f_{s_2} \circ f_{s_1}$

• $\sf IN[B]=\wedge_{P\textsf{ a predecessor of B}}~OUT[P]$

• $\sf IN[B]=f_B(OUT[B]),~f_B=f_{s_1}\circ … \circ f_{s_{n-1}} \circ f_{s_n}$

• $\sf OUT[B]=\wedge_{P\textsf{ a successor of B}}~IN[P]$

The meet operator $\wedge$ is used to summarize the contributions from different paths at the confluence of those paths

III. Reaching Definitions Analysis