Control Flow Graph
Scale uses an intermediate representation of the program called a control flow graph.
The Scale Control Flow Graph is referred to as the Scribble CFG.
A control flow graph shows how control moves during execution of the program.
Each node is essentiallly some executable sequence of the program.
Each node is connected to the node(s) that immediately follow it during program execution.
The Scribble CFG allows easy modification; nodes may be easily moved, added or deleted.
Lowering may be performed on the parts of the graph.
Implicit loops are detected and transformed into explicit loops.
Pre- and post-dominance relations are computed and maintained.
Dominance frontiers are computed and maintained.
Scribble consists of a small set of language independent node types that correspond to executable operations:
- statements
- which represent imperatives such as
- evaluate expression
- if-then-else control flow
- switch control flow
- loop markers to mark loop entrances and exits
- expressions
- which represent expressions to be evaluated.
Expression node types are a small set of language independent operations such as add, store, and multiply that form trees that are connected to the statement nodes.
In the Scribble CFG most evaluate statement nodes have simple executable expressions connected to them.
These expressions are generally of the form
a <- b
a <- b op c
The graph is easily modified while maintaining essential information.
The nodes and operations comprising a Scribble CFG can be annotated.
Example Scribble CFG
Return to Scale dataflow diagram.
Return to Scale home page.
(Last changed: March 21, 2007.)
