Slides: pdf, pptx

Idea of Data Flow Analysis

Key Background

Control-Flow Graph Definition

Why control-flow graphs instead of syntax trees

• they can represent arbitrary jumps
• they are simple: conditions and loops represented uniformly
• used in most compilers (including LLVM and GCC)

Translation of syntax trees to control-flow graphs is (at a high-level) similar to translation from regular expressions to finite-state machines (see closure properties of finite state machines).

Decomposing Complex Expressions

If Statements to CFG

While Statements to CFG

Source and Target CFG Vertices

In Scala:

• DiGraphs.scala
• SimpleCFG.scala
• SimpleAST.scala
• SimpleTranslate.scala

Constant Propagation

Background: Partial order and Lattices

Continued in Lecturecise 23

• Lecture notes on static analysis by Michael Schwartzbach, especially chapters 4,5,6
• Compiler Construction by Niklaus Wirth, chapters 9,10, 11
• Tiger book, Chapters 7-11, 17
• Abstract Interpretation in a Nutshell by Patrick Cousot (also a course at MIT)
• Lecture 7 in Software Analysis and Verification 2009