COMS W4117
Compilers and Translators:
Software Verification Tools
Lecture 8: Loops in Flow Graphs
September 27, 2007

Lecture Outline

  1. Review
  2. Dominators
  3. Depth-first ordering
  4. Edges in a depth-first spanning tree
  5. Reducible flow graphs
  6. Natural loops
  7. Reading


1. Review

  1. Data-flow analysis frameworks
  2. Iterative algorithm for general frameworks
  3. Meaning of a data-flow solution
  4. Framework for constant propagation


2. Dominators



3. Depth-First Ordering



4. Reducible Flow Graphs



5. Natural Loops



6. Reading



aho@cs.columbia.edu