COMS W4117
Compilers and Translators:
Software Verification Tools
Lecture 6: Foundations of Data-Flow Analysis
September 20, 2007

Lecture Outline

  1. Review
  2. Available expressions
  3. Basic questions about the iterative algorithm
  4. Lattices and semilattices
  5. Transfer functions
  6. The iterative algorithm for general frameworks
  7. Meaning of a data-flow solution
  8. Reading


1. Review

  1. Introduction to data-flow analysis
  2. Data-flow schemas
  3. Reaching definitions
  4. Live-variable analysis


2. Available Expressions



3. Basic Questions about the Iterative Algorithm



4. Lattices and Semilattices



5. Data-Flow Analysis Frameworks



6. The Iterative Algorithm for General Frameworks



7. Meaning of a Data-Flow Solution



8. Reading



aho@cs.columbia.edu