Control-Flow Graph Definition

Recall Linearizing Trees with Control-Flow, Different Views of IfThenElse

  • control-flow graphs are the graph view

Like automaton but with variables

Related to traditional notion of flow charts

Definition: Control-Flow Graph (CFG) is graph $(V,E,L)$ where

  • $V$ is set of CFG nodes, representing program points
  • $E \subseteq V\times V$ set of CFG edges (represent jumps)
  • $L : E \to ST$ gives a CFG statement for each edge
    • statements
    • conditions

Side Note:

In the example, what are V,E,L?

atomic expression = variable or a constant

ST statements are simple:

  • quadruples: x = y * z (y,z are atomic expression)
  • copy
  • procedure calls (parameters are variables)
  • relational operators between atomic expressions

Notion of Basic Blocks: straight sequence of nodes (no jumps to or from the middle)