Skip to content

Control Flow Graph

Jump to bottom
github-actions[bot] edited this page Sep 3, 2026 · 1 revision

Generated from 'wiki-cfg.ts' on 2026-08-29, 17:46:41 UTC (v2.15.8, R v4.6.1), please do not edit directly.

flowR produces three main perspectives of the program: 1) a normalized version of the AST, 2) a dataflow graph, and 3) a control flow graph (CFG). flowR uses this CFG interweaved with its data flow analysis and for some of its queries (e.g., to link to the last call in a Call-Context Query).

Please note that the control flow graph is a view on the dataflow graph, similar to the call graph.

Tip

If you want to investigate the Control Flow Graph, you can use the :controlflow* command in the REPL (see the Interface wiki page for more information). By default, this view does not use basic blocks as, for example, R allows unconditional jumps to occur in spots where conventional languages would assume expressions (e.g., if-conditions). Yet, by using :controlflowbb* you can inspect the CFG with basic blocks (although you have to keep in mind that now, there can be a value flow between basic blocks)

For readability, we structure this wiki page into various segments:

Tip

FlowR provides you with various helper objects to work with the CFG, such as CfgEdge and CfgVertex, which you can use to easily access the properties of the CFG and its vertices and edges.

Initial Overview

For now, let's look at a CFG for a program without any branching:

x <- 2 * 3 + 1

The corresponding CFG is a directed, labeled graph with two kinds of edges: flow edges and control edges.

flowchart LR
    n1(["`RNumber (1)
**2**`"])
    n2(["`RNumber (2)
**3**`"])
    n3(["`RBinaryOp (3)
**2 #42; 3**`"])
    n4(["`RNumber (4)
**1**`"])
    n5(["`RBinaryOp (5)
**2 #42; 3 #43; 1**`"])
    n0(["`RSymbol (0)
**x**`"])
    n6["`RBinaryOp (6)
**x #60;#45; 2 #42; 3 #43; 1**`"]
    n3 -->|"flows to"| n4
    n1 -->|"flows to"| n2
    n2 -->|"flows to"| n3
    n5 -->|"flows to"| n0
    n4 -->|"flows to"| n5
    n0 -->|"flows to"| n6
    style n1 stroke:cyan,stroke-width:6.5px;    style n6 stroke:green,stroke-width:6.5px;
Loading

(The analysis required 2.4 ms (including the dataflow analysis, normalization, and parsing with the r-shell engine) within the generation environment. We used the following simplification: unique-cf-sets . )

Important

Edges are in flow order: an edge from a to b means that b is evaluated after a. Use outgoingEdges (or successors) to ask what may run next and ingoingEdges (or predecessors) to ask what ran before. The visitors can walk either way.

Every vertex of the dataflow graph is a vertex here as well, carrying the same id and hence linking back to the normalized AST. The control flow is modeled in post-order, so an expression such as 2 * 3 is reached once both operands have been evaluated: the * vertex itself is where the calculation is over, and no extra node is needed.

To gain a better understanding, let's have a look at a simple program with a single branching structure:

flowchart LR
    n0(["`RSymbol (0)
**u**`"])
    n1["`RNumber (1)
**3**`"]
    n3["`RNumber (3)
**2**`"]
    n5["`RIfThenElse (5)
**if(u) 3 else 2**`"]
    n0 -.->|"branch on u (0) if T"| n1
    n0 -.->|"branch on u (0) if F"| n3
    n1 -->|"flows to"| n5
    n3 -->|"flows to"| n5
    style n0 stroke:cyan,stroke-width:6.5px;    style n5 stroke:green,stroke-width:6.5px;
Loading
R Code of the CFG

The analysis required 3.0 ms (including the dataflow analysis, normalization, and parsing with the r-shell engine) within the generation environment. We used the following simplification: unique-cf-sets .

if(u) 3 else 2

The condition u runs first and splits into the two branches, which join again on the if vertex itself. The if is therefore where the structure is left (see the structure section for more details).

Standing on u, the edges leaving it are control edges that name the if, so what a condition belongs to can be read off locally. ControlFlowGraph::decides lists the constructs a vertex decides, and ControlFlowGraph::entryOf goes the other way, from the if to the condition it starts with.

For you to compare, the following shows the CFG of an if without an else branch:

flowchart LR
    n0(["`RSymbol (0)
**u**`"])
    n1(["`RSymbol (1)
**v**`"])
    n2(["`RBinaryOp (2)
**u || v**`"])
    n3["`RNumber (3)
**3**`"]
    n5["`RIfThenElse (5)
**if(u || v) 3**`"]
    n2 -.->|"branch on u || v (2) if T"| n3
    n2 -.->|"branch on u || v (2) if F"| n5
    n0 -.->|"branch on u (0) if F"| n1
    n0 -.->|"branch on u (0) if T"| n2
    n1 -->|"flows to"| n2
    n3 -->|"flows to"| n5
    style n0 stroke:cyan,stroke-width:6.5px;    style n5 stroke:green,stroke-width:6.5px;
Loading
R Code of the CFG

The analysis required 4.2 ms (including the dataflow analysis, normalization, and parsing with the r-shell engine) within the generation environment. We used the following simplification: unique-cf-sets .

if(u || v) 3

The || branches as well, as it only evaluates v when u did not already decide the answer.

Basic blocks group what always runs together. A block ends where the flow may go more than one way, and starts where more than one way may arrive:

flowchart LR
    subgraph nbb-1 [Block bb-1]
        direction LR
    n1(["`RNumber (1)
**1**`"])
    n0(["`RSymbol (0)
**x**`"])
    n1 --> n0
    n2["`RBinaryOp (2)
**x #60;#45; 1**`"]
    n0 --> n2
    n4(["`RSymbol (4)
**x**`"])
    n2 --> n4
    n5(["`RNumber (5)
**2**`"])
    n4 --> n5
    n6(["`RBinaryOp (6)
**x #43; 2**`"])
    n5 --> n6
    n3(["`RSymbol (3)
**y**`"])
    n6 --> n3
    n7["`RBinaryOp (7)
**y #60;#45; x #43; 2**`"]
    n3 --> n7
    n8(["`RSymbol (8)
**y**`"])
    n7 --> n8
    end
    subgraph nbb-10 [Block bb-10]
        direction LR
    n10(["`RSymbol (10)
**y**`"])
    n12["`RFunctionCall (12)
**print(y)**`"]
    n10 --> n12
    end
    subgraph nbb-14 [Block bb-14]
        direction LR
    n14["`RIfThenElse (14)
**if(y) print(y)**`"]
    end
    nbb-1 -.->|"branch on y (8) if T"| nbb-10
    nbb-1 -.->|"branch on y (8) if F"| nbb-14
    nbb-10 -->|"flows to"| nbb-14
    style nbb-1 stroke:cyan,stroke-width:6.5px;    style nbb-14 stroke:green,stroke-width:6.5px;
Loading
R Code of the CFG

The analysis required 2.5 ms (including the dataflow analysis, normalization, and parsing with the r-shell engine) within the generation environment. We used the following simplifications: unique-cf-sets, to-basic-blocks .

x <- 1
y <- x + 2
if(y) print(y)

Compacting them is easier to read (although the reconstructed code can be slightly misleading, as flowR tries its best to make it syntactically correct and hence adds closing braces which are technically not part of the block):

flowchart LR
    nbb-1[["`Basic Block (bb-1)
x #60;#45; 1
y #60;#45; x #43; 2
y`"]]
    nbb-10[["`Basic Block (bb-10)
print(y)`"]]
    nbb-14[["`Basic Block (bb-14)
if(y) #123; #125;`"]]
    nbb-1 -.->|"branch on y (8) if T"| nbb-10
    nbb-1 -.->|"branch on y (8) if F"| nbb-14
    nbb-10 -->|"flows to"| nbb-14
    style nbb-1 stroke:cyan,stroke-width:6.5px;    style nbb-14 stroke:green,stroke-width:6.5px;
Loading
R Code of the CFG

The analysis required 2.0 ms (including the dataflow analysis, normalization, and parsing with the r-shell engine) within the generation environment. We used the following simplifications: unique-cf-sets, to-basic-blocks and render a simplified/compacted version.

x <- 1
y <- x + 2
if(y) print(y)

Branch-heavy code gains nothing from this: in if(u || v) 3 every vertex may be reached or left in more than one way, so every block holds a single vertex.

The control flow graph also harmonizes with function definitions, and calls:

flowchart LR
    n5(["`RFunctionDefinition (5)
**function() #123; 3 #125;**`"])
    subgraph n5-body ["body of function() #123; 3 #125;"]
        direction LR
    n3["`RNumber (3)
**3**`"]
    n4(["`RExpressionList (4)`"])
    end
    n0(["`RSymbol (0)
**f**`"])
    n6["`RBinaryOp (6)
**f #60;#45; function() #123; 3 #125;**`"]
    n8["`RFunctionCall (8)
**f()**
 calls:#91;5#93;`"]
    n3 -->|"flows to"| n4
    n6 -->|"flows to"| n8
    n5 -->|"flows to"| n0
    n0 -->|"flows to"| n6
    n5 -. holds .- n3
    style n5 stroke:cyan,stroke-width:6.5px;    style n8 stroke:green,stroke-width:6.5px;
Loading
R Code of the CFG

The analysis required 1.6 ms (including the dataflow analysis, normalization, and parsing with the r-shell engine) within the generation environment. We used the following simplification: unique-cf-sets .

f <- function() { 3 }
f()

Structure of the Control Flow Graph

You can produce your very own control flow graph with extractCfg. The ControlFlowGraph class describes everything required to model the control flow graph, with its edge types described by CfgEdge and its vertices by CfgVertex. However, you should be aware of the ControlFlowInformation interface which adds some additional information the CFG (and is used during the construction of the CFG as well):

  • ControlFlowInformation
    Summarizes the control information of a program

    Defined at src/control-flow/control-flow-graph.ts#L976 
    /**
 * Summarizes the control information of a program
 * @see {@link emptyControlFlowInformation} - to create an empty control flow information object
 */
export interface ControlFlowInformation<Vertex extends CfgVertex = CfgVertex> extends MergeableRecord {
    /** all active 'return'(-like) unconditional jumps */
    returns:     NodeId[],
    /** all active 'break'(-like) unconditional jumps */
    breaks:      NodeId[],
    /** all active 'next'(-like) unconditional jumps */
    nexts:       NodeId[],
    /** intended to construct a hammock graph, with 0 exit points representing a block that should not be part of the CFG (like a comment) */
    entryPoints: NodeId[],
    /** See {@link ControlFlowInformation#entryPoints|entryPoints} */
    exitPoints:  NodeId[],
    /** the control flow graph summarizing the flow information */
    graph:       ControlFlowGraph<Vertex>
}

To check whether the CFG has the expected shape, you can use the test function assertCfg which supports testing for sub-graphs as well (it provides diffing capabilities similar to assertDataflow). As the CFG may become unhandy for larger programs, there are simplifications available with simplifyControlFlowInformation (the analyzer applies the ones you ask for when you request the control flow).

CFG Vertices

All vertex types are summarized in the CfgVertexType enum which currently contains the following types:

  • Statement (1)
  • Expression (2)
  • Block (3)

We use the CfgBasicBlockVertex to represent basic blocks and separate expressions (CfgExpressionVertex) and statements (CfgStatementVertex) as control flow units with and without side effects (if you want to, you can see view statements as effectful expressions).

Every vertex corresponds to a vertex of the dataflow graph: the control flow is modeled in post-order, so a vertex is reached once everything it is made of has been evaluated, which makes it the point at which the construct is left. That is why there are no separate marker vertices to close an if or a loop.

In mermaid visualizations, we use rectangles for statements and rounded rectangles for expressions. Blocks are visualized as boxes around the contained vertices.

Note

Every CFG vertex has a NodeId that links it to the normalized AST (although basic blocks will find no counterpart as they are a structuring element of the CFG). Additionally, it may provide information on the called functions (in case that the current element is a function call). Additionally, a function definition names the vertices of its body as children, which is the only way into that region.

CFG Edges

Every edge points the way execution goes: an edge from a to b means that b runs after a. There are two kinds, told apart by the CfgEdgeType enum.

Flow Edges

A flow edge says that the target simply runs next. In x; y there is one from x to y:

flowchart LR
    n0["`RSymbol (0)
**x**`"]
    n1["`RSymbol (1)
**y**`"]
    n0 -->|"flows to"| n1
    style n0 stroke:cyan,stroke-width:6.5px;    style n1 stroke:green,stroke-width:6.5px;
Loading

(The analysis required 1.7 ms (including the dataflow analysis, normalization, and parsing with the r-shell engine) within the generation environment. We used the following simplification: unique-cf-sets . )

Control Edges

A control edge says the same, but only when a condition holds, which is how the branches of an if or the body of a loop are attached. Diagrams draw these dashed.

The edge is the ControlDependency it stands for, the same one the vertices behind it carry in their cds, so it names the deciding vertex, whether it is the true or the false case, and whether the decision comes from iterating a loop:

  • ControlDependency
    A control dependency links a vertex to the control flow element which may have an influence on its execution. Within if(p) a else b, a and b have a control dependency on the if (which in turn decides based on p).

    Defined at src/dataflow/info.ts#L21 
    /**
 * A control dependency links a vertex to the control flow element which
 * may have an influence on its execution.
 * Within `if(p) a else b`, `a` and `b` have a control dependency on the `if` (which in turn decides based on `p`).
 * @see {@link happensInEveryBranch} - to check whether a list of control dependencies is exhaustive
 * @see {@link negateControlDependency} - to easily negate a control dependency
 */
export interface ControlDependency {
    /** The id of the node that causes the control dependency to be active (e.g., the condition of an if) */
    readonly id:           NodeId,
    /** when does this control dependency trigger (if the condition is true or false)? */
    readonly when?:        boolean
    /** whether this control dependency was created due to iteration (e.g., a loop) */
    readonly byIteration?: boolean
    /**
     * any file-exist assumptions made
     */
    readonly file?:        string
}
Example: if-else 
flowchart LR
    n0(["`RSymbol (0)
**u**`"])
    n1["`RNumber (1)
**3**`"]
    n3["`RNumber (3)
**2**`"]
    n5["`RIfThenElse (5)
**if(u) 3 else 2**`"]
    n0 -.->|"branch on u (0) if T"| n1
    n0 -.->|"branch on u (0) if F"| n3
    n1 -->|"flows to"| n5
    n3 -->|"flows to"| n5
    style n0 stroke:cyan,stroke-width:6.5px;    style n5 stroke:green,stroke-width:6.5px;
Loading
R Code of the CFG

The analysis required 1.6 ms (including the dataflow analysis, normalization, and parsing with the r-shell engine) within the generation environment. We used the following simplification: unique-cf-sets .

if(u) 3 else 2
Example: while-loop 
flowchart LR
    n0(["`RSymbol (0)
**u**`"])
    n1["`RSymbol (1)
**b**`"]
    n3["`RWhileLoop (3)
**while(u) b**`"]
    n0 -.->|"branch on u (0) if T"| n1
    n0 -.->|"branch on u (0) if F"| n3
    n1 -->|"flows to"| n0
    style n0 stroke:cyan,stroke-width:6.5px;    style n3 stroke:green,stroke-width:6.5px;
Loading
R Code of the CFG

The analysis required 2.1 ms (including the dataflow analysis, normalization, and parsing with the r-shell engine) within the generation environment. We used the following simplification: unique-cf-sets .

while(u) b

Please note that repeat loops have no control edges, as they repeat their body unconditionally. Additionally, the control flow graph does not have to be connected. If you use a repeat without any exit condition, the loop is never left, so its vertex is not reachable from the entry:

Example: repeat-loop (infinite) 
flowchart LR
    n2["`RSymbol (2)
**b**`"]
    n3(["`RExpressionList (3)`"])
    n4["`RRepeatLoop (4)
**repeat #123; b #125;**`"]
    n5["`RSymbol (5)
**after**`"]
    n3 -->|"flows to"| n2
    n2 -->|"flows to"| n3
    style n2 stroke:cyan,stroke-width:6.5px;    style n5 stroke:green,stroke-width:6.5px;
Loading
R Code of the CFG

The analysis required 1.8 ms (including the dataflow analysis, normalization, and parsing with the r-shell engine) within the generation environment. We used the following simplification: unique-cf-sets .

repeat { b }; after
Example: repeat-loop (with break) 
flowchart LR
    n2["`RSymbol (2)
**b**`"]
    n3(["`RSymbol (3)
**u**`"])
    n4["`RBreak (4)
**break**`"]
    n6["`RIfThenElse (6)
**if(u) break**`"]
    n8(["`RExpressionList (8)`"])
    n9["`RRepeatLoop (9)
**repeat #123; b; if(u) break; #125;**`"]
    n10["`RSymbol (10)
**after**`"]
    n4 -->|"flows to"| n9
    n6 -->|"flows to"| n8
    n3 -.->|"branch on u (3) if T"| n4
    n3 -.->|"branch on u (3) if F"| n6
    n2 -->|"flows to"| n3
    n8 -->|"flows to"| n2
    n9 -->|"flows to"| n10
    style n2 stroke:cyan,stroke-width:6.5px;    style n10 stroke:green,stroke-width:6.5px;
Loading
R Code of the CFG

The analysis required 1.8 ms (including the dataflow analysis, normalization, and parsing with the r-shell engine) within the generation environment. We used the following simplification: unique-cf-sets .

repeat { b; if(u) break; }; after

For a for-loop, the control edge says whether the sequence still has values to iterate over.

Example: for-loop 
flowchart LR
    n0(["`RSymbol (0)
**i**`"])
    n1(["`RNumber (1)
**1**`"])
    n2(["`RNumber (2)
**10**`"])
    n3(["`RBinaryOp (3)
**1#58;10**`"])
    n4["`RSymbol (4)
**b**`"]
    n6["`RForLoop (6)
**for(i in 1#58;10) b**`"]
    n3 -->|"flows to"| n0
    n1 -->|"flows to"| n2
    n2 -->|"flows to"| n3
    n0 -.->|"branch on i (0) if T"| n4
    n0 -.->|"branch on i (0) if F"| n6
    n4 -->|"flows to"| n0
    style n1 stroke:cyan,stroke-width:6.5px;    style n6 stroke:green,stroke-width:6.5px;
Loading
R Code of the CFG

The analysis required 1.4 ms (including the dataflow analysis, normalization, and parsing with the r-shell engine) within the generation environment. We used the following simplification: unique-cf-sets .

for(i in 1:10) b

Extra: Call Links

The control flow graph is a view on the dataflow graph: the dataflow analysis records the control flow while it walks the program, and extractCfg projects it into the shape the control flow analyses expect. Because of that, the interprocedural knowledge the dataflow analysis gained is available without a second pass over the program.

Control flow itself stays intra-procedural. A call does not flow into the body of what it calls, and the body of a function definition is not entered when the definition is evaluated ‐ it only produces the closure. What a call may reach is named separately:

flowchart LR
    n3(["`RFunctionDefinition (3)
**function() b**`"])
    subgraph n3-body ["body of function() b"]
        direction LR
    n1["`RSymbol (1)
**b**`"]
    end
    n0(["`RSymbol (0)
**f**`"])
    n4["`RBinaryOp (4)
**f #60;#45; function() b**`"]
    n6["`RFunctionCall (6)
**f()**
 calls:#91;3#93;`"]
    n4 -->|"flows to"| n6
    n3 -->|"flows to"| n0
    n0 -->|"flows to"| n4
    n3 -. holds .- n1
    style n3 stroke:cyan,stroke-width:6.5px;    style n6 stroke:green,stroke-width:6.5px;
Loading
R Code of the CFG

The analysis required 1.5 ms (including the dataflow analysis, normalization, and parsing with the r-shell engine) within the generation environment. We used the following simplification: unique-cf-sets .

f <- function() b; f()

A calls attribute attached to the function call vertex holds the NodeId of the function definitions that are called from this vertex, taken from the calls edges the dataflow analysis resolved.

For built-in functions that are provided by flowR's built-in configuration (see the interface wiki page) the CFG does not contain the additional information directly:

flowchart LR
    n1(["`RNumber (1)
**3**`"])
    n3["`RFunctionCall (3)
**print(3)**`"]
    n1 -->|"flows to"| n3
    style n1 stroke:cyan,stroke-width:6.5px;    style n3 stroke:green,stroke-width:6.5px;
Loading
R Code of the CFG

The analysis required 1.3 ms (including the dataflow analysis, normalization, and parsing with the r-shell engine) within the generation environment. We used the following simplification: unique-cf-sets .

print(3)

This is due to the fact that the dataflow graph does contain the required call information (and there are no new control vertices to add as the built-in call has no target in the source code):

flowchart LR
    1{{"`*#91;RNumber#93;* **3**
      *1.7* (**id: 1**)`"}}
    3[["`*#91;RFunctionCall#93;* base#58;#58;**print**
      *1.1-8* (**id: 3**)
    arg: (1)`"]]
    built-in:print["`Built-In:
print`"]
    style built-in:print stroke:gray,fill:gray,stroke-width:2px,opacity:.8;
    1 -.->|"flow"| 3
    linkStyle 0 stroke:gray,color:gray;
    3 -->|"returns, arg"| 1
    3 -.->|"reads, calls"| built-in:print
    linkStyle 2 stroke:gray;
Loading
R Code of the Dataflow Graph

The analysis required 1.1 ms (including parse and normalize, using the r-shell engine) within the generation environment. No signature database is mounted for these generated graphs, so library() calls attach no package exports; base-R names are still qualified via the generated base-package store (e.g. acf as stats::acf). We encountered unknown side effects (with ids: 3 (linked)) during the analysis.

print(3)

Adding Basic Blocks

As mentioned in the introduction, our control flow graph does not use basic blocks by default and hence simply links all vertices independent of whether they have (un-)conditional jumps or not. On the upside, this tells us the execution order (and, in case of promises, forcing order) of involved expressions and seamlessly handles cases like x <- return(3). On the downside, this makes it hard to apply classical control flow graph algorithms and, in general, makes the graph much harder to read. Yet, we can request basic blocks or transform an existing CFG into basic blocks using the convertCfgToBasicBlocks function.

Any program without any (un-)conditional jumps now contains a single basic block:

flowchart LR
    nbb-1[["`Basic Block (bb-1)
x #60;#45; 2 #42; 3 #43; 1`"]]
    style nbb-1 stroke:cyan,stroke-width:6.5px;    style nbb-1 stroke:green,stroke-width:6.5px;
Loading
R Code of the CFG

The analysis required 1.5 ms (including the dataflow analysis, normalization, and parsing with the r-shell engine) within the generation environment. We used the following simplifications: unique-cf-sets, to-basic-blocks and render a simplified/compacted version.

x <- 2 * 3 + 1

While the CFG without basic blocks is much bigger:

flowchart LR
    n1(["`RNumber (1)
**2**`"])
    n2(["`RNumber (2)
**3**`"])
    n3(["`RBinaryOp (3)
**2 #42; 3**`"])
    n4(["`RNumber (4)
**1**`"])
    n5(["`RBinaryOp (5)
**2 #42; 3 #43; 1**`"])
    n0(["`RSymbol (0)
**x**`"])
    n6["`RBinaryOp (6)
**x #60;#45; 2 #42; 3 #43; 1**`"]
    n3 -->|"flows to"| n4
    n1 -->|"flows to"| n2
    n2 -->|"flows to"| n3
    n5 -->|"flows to"| n0
    n4 -->|"flows to"| n5
    n0 -->|"flows to"| n6
    style n1 stroke:cyan,stroke-width:6.5px;    style n6 stroke:green,stroke-width:6.5px;
Loading

(The analysis required 1.3 ms (including the dataflow analysis, normalization, and parsing with the r-shell engine) within the generation environment. We used the following simplification: unique-cf-sets . )

In a way, using the basic blocks perspective does not remove any of these vertices (we just usually visualize them compacted as their execution order should be "obvious"). The vertices are still there, as elems of the CfgBasicBlockVertex:

flowchart LR
    subgraph nbb-1 [Block bb-1]
        direction LR
    n1(["`RNumber (1)
**2**`"])
    n2(["`RNumber (2)
**3**`"])
    n1 --> n2
    n3(["`RBinaryOp (3)
**2 #42; 3**`"])
    n2 --> n3
    n4(["`RNumber (4)
**1**`"])
    n3 --> n4
    n5(["`RBinaryOp (5)
**2 #42; 3 #43; 1**`"])
    n4 --> n5
    n0(["`RSymbol (0)
**x**`"])
    n5 --> n0
    n6["`RBinaryOp (6)
**x #60;#45; 2 #42; 3 #43; 1**`"]
    n0 --> n6
    end
    style nbb-1 stroke:cyan,stroke-width:6.5px;    style nbb-1 stroke:green,stroke-width:6.5px;
Loading

(The analysis required 1.5 ms (including the dataflow analysis, normalization, and parsing with the r-shell engine) within the generation environment. We used the following simplifications: unique-cf-sets, to-basic-blocks . )

The benefit (for comprehensibility and algorithms) becomes more apparent when we look at a more complicated program:

f <- function(a, b = 3) {
 if(a > b) {
 	return(a * b);
 } else {
 	while(a < b) {
 		a <- a + 1;
 	}
 	return(a);
 }
}

print(f(21) + f(42))

With basic blocks, this code looks like this:

flowchart LR
    nbb-1[["`Basic Block (bb-1)
function(a, b=3) #123; #125;
a #62; b`"]]
    nbb-14[["`Basic Block (bb-14)
return(a #42; b)`"]]
    nbb-19[["`Basic Block (bb-19)
RExpressionList (19)`"]]
    nbb-22[["`Basic Block (bb-22)
while(a #60; b) #123;#125;`"]]
    nbb-28[["`Basic Block (bb-28)
#123; a #60;#45; a #43; 1 #125;`"]]
    nbb-33[["`Basic Block (bb-33)
return(a)`"]]
    nbb-39[["`Basic Block (bb-39)
RExpressionList (39)`"]]
    nbb-40[["`Basic Block (bb-40)
if(a #62; b) #123; #125;`"]]
    nbb-41[["`Basic Block (bb-41)
RExpressionList (41)`"]]
    nbb-42[["`Basic Block (bb-42)
f #60;#45; function(a, b=3) #123; #125;
print(f(21) #43; f(42))`"]]
    nbb-1 -.->|"branch on a #62; b (10) if T"| nbb-14
    nbb-1 -.->|"branch on a #62; b (10) if F"| nbb-22
    nbb-14 -->|"flows to"| nbb-19
    nbb-14 -->|"flows to"| nbb-41
    nbb-22 -.->|"branch on a #60; b (24) if T"| nbb-28
    nbb-22 -.->|"branch on a #60; b (24) if F"| nbb-33
    nbb-28 -->|"flows to"| nbb-22
    nbb-33 -->|"flows to"| nbb-39
    nbb-33 -->|"flows to"| nbb-41
    style nbb-42 stroke:cyan,stroke-width:6.5px;    style nbb-42 stroke:green,stroke-width:6.5px;
Loading

(The analysis required 3.7 ms (including the dataflow analysis, normalization, and parsing with the r-shell engine) within the generation environment. We used the following simplifications: unique-cf-sets, to-basic-blocks and render a simplified/compacted version. )

Now, without basic blocks, this is a different story...

The full CFG 
flowchart LR
    n40["`RIfThenElse (40)
**if(a #62; b) #123; return(a #42; b); #125; else #123; while(a #60; b) #123; a #60;#45; a #43; 1; #125; return(a); #125;**`"]
    n42(["`RFunctionDefinition (42)
**function(a, b = 3) #123; if(a #62; b) #123; return(a #42; b); #125; else #123; while(a #60; b) #123; a #60;#45; a #43; 1; #125; return(a); #125; #125;**`"])
    subgraph n42-body ["body of function(a, b = 3) #123;
 if(a #62; b) #123;
 	retu..."]
        direction LR
    n1(["`RSymbol (1)
**a**`"])
    n4(["`RNumber (4)
**3**`"])
    n3(["`RSymbol (3)
**b**`"])
    n8(["`RSymbol (8)
**a**`"])
    n9(["`RSymbol (9)
**b**`"])
    n10(["`RBinaryOp (10)
**a #62; b**`"])
    n22(["`RSymbol (22)
**a**`"])
    n23(["`RSymbol (23)
**b**`"])
    n24(["`RBinaryOp (24)
**a #60; b**`"])
    n33["`RWhileLoop (33)
**while(a #60; b) #123; a #60;#45; a #43; 1; #125;**`"]
    n35(["`RSymbol (35)
**a**`"])
    n37["`RFunctionCall (37)
**return(a)**`"]
    n41(["`RExpressionList (41)`"])
    n39(["`RExpressionList (39)`"])
    n28(["`RSymbol (28)
**a**`"])
    n29(["`RNumber (29)
**1**`"])
    n30(["`RBinaryOp (30)
**a #43; 1**`"])
    n27(["`RSymbol (27)
**a**`"])
    n31["`RBinaryOp (31)
**a #60;#45; a #43; 1**`"]
    n32(["`RExpressionList (32)`"])
    n14(["`RSymbol (14)
**a**`"])
    n15(["`RSymbol (15)
**b**`"])
    n16(["`RBinaryOp (16)
**a #42; b**`"])
    n18["`RFunctionCall (18)
**return(a #42; b)**`"]
    n19(["`RExpressionList (19)`"])
    end
    n0(["`RSymbol (0)
**f**`"])
    n43["`RBinaryOp (43)
**f #60;#45; function(a, b = 3) #123; if(a #62; b) #123; return(a #42; b); #125; else #123; while(a #60; b) #123; a #60;#45; a #43; 1; #125; return(a); #125; #125;**`"]
    n46(["`RNumber (46)
**21**`"])
    n48(["`RFunctionCall (48)
**f(21)**
 calls:#91;42#93;`"])
    n50(["`RNumber (50)
**42**`"])
    n52(["`RFunctionCall (52)
**f(42)**
 calls:#91;42#93;`"])
    n53(["`RBinaryOp (53)
**f(21) #43; f(42)**`"])
    n55["`RFunctionCall (55)
**print(f(21) #43; f(42))**`"]
    n3 -->|"flows to"| n8
    n4 -->|"flows to"| n3
    n10 -.->|"branch on a #62; b (10) if T"| n14
    n10 -.->|"branch on a #62; b (10) if F"| n22
    n8 -->|"flows to"| n9
    n9 -->|"flows to"| n10
    n16 -->|"flows to"| n18
    n14 -->|"flows to"| n15
    n15 -->|"flows to"| n16
    n18 -->|"flows to"| n19
    n18 -->|"flows to"| n41
    n24 -.->|"branch on a #60; b (24) if T"| n28
    n24 -.->|"branch on a #60; b (24) if F"| n33
    n22 -->|"flows to"| n23
    n23 -->|"flows to"| n24
    n33 -->|"flows to"| n35
    n30 -->|"flows to"| n27
    n28 -->|"flows to"| n29
    n29 -->|"flows to"| n30
    n31 -->|"flows to"| n32
    n27 -->|"flows to"| n31
    n32 -->|"flows to"| n22
    n35 -->|"flows to"| n37
    n37 -->|"flows to"| n39
    n37 -->|"flows to"| n41
    n1 -->|"flows to"| n4
    n43 -->|"flows to"| n46
    n42 -->|"flows to"| n0
    n0 -->|"flows to"| n43
    n48 -->|"flows to"| n50
    n46 -->|"flows to"| n48
    n53 -->|"flows to"| n55
    n52 -->|"flows to"| n53
    n50 -->|"flows to"| n52
    n42 -. holds .- n1
    style n42 stroke:cyan,stroke-width:6.5px;    style n55 stroke:green,stroke-width:6.5px;
Loading

(The analysis required 3.3 ms (including the dataflow analysis, normalization, and parsing with the r-shell engine) within the generation environment. We used the following simplification: unique-cf-sets . )

And again it should be noted that even though the example code is more complicated, this is still far from the average real-world script.

Working with the CFG

There is a plethora of functions that you can use the traverse the normalized AST and the dataflow graph. Similarly, flowR provides you with a set of utility functions and classes that you can use to interact with the control flow graph:

Simple Traversal

If you are just interested in traversing the vertices within the cfg, two simple functions visitCfgInOrder and visitCfgInReverseOrder are available. For basic blocks these will automatically traverse the elements contained within the blocks (in the respective order). For example, the following function will return all numbers contained within the CFG:

function sampleCollectNumbers(cfg: ControlFlowInformation, ast: NormalizedAst): RNumberValue[] {
	const numbers: RNumberValue[] = [];
	visitCfgInOrder(cfg.graph, cfg.entryPoints, id => {
		/* obtain the corresponding node from the AST */
		const node = ast.idMap.get(id);
		/* if it is present and a number, add the parsed value to the list */
		if(RNumber.is(node)) {
			numbers.push(node.content);
		}
	});
	return numbers;
}

Defined at src/documentation/wiki-cfg.ts#L54

Calling it with the CFG and AST of the expression x - 1 + 2L * 3 yields the following elements (in this order):

  • {"num":1,"complexNumber":false,"markedAsInt":false}
  • {"num":2,"complexNumber":false,"markedAsInt":true}
  • {"num":3,"complexNumber":false,"markedAsInt":false}

A more useful appearance of these visitors occurs with happensBefore which uses the CFG to determine whether the execution of one vertex always, maybe, or never happens before another vertex (see the corresponding query documentation for more information).

Diffing and Testing

As mentioned above, you can use the test function assertCfg to check whether the control flow graph has the desired shape. The function supports testing for sub-graphs as well (it provides diffing capabilities similar to assertDataflow). If you want to diff two control flow graphs, you can use the diffOfControlFlowGraphs function.

Checking Properties

To be a valid representation of the program, the CFG should satisfy a collection of properties that, in turn, you can automatically assume to hold when working with it. In general, we verify these in every unit test using assertCfgSatisfiesProperties, and you can have a look at the active properties by checking the CfgProperties object. In general, we check for a hammock graph (given that the program contains no definite infinite loop) and the absence of direct cycles.

Sophisticated CFG Traversal

The simple traversal functions are great for simple tasks, but very unhandy when you want to do something more sophisticated that incorporates language semantics such as function calls. Hence, we provide a series of incrementally more sophisticated (but complex) visitors that incorporate various alternative perspectives:

The later ones need the dataflow graph and the ast as well. As the CFG is a view on the dataflow graph, and that graph knows the ast, cfgVisitorConfig takes both from the control flow you hand it:

new MyVisitor(cfgVisitorConfig({ controlFlow, defaultVisitingOrder: 'forward' }))

Basic CFG Visitor

The BasicCfgGuidedVisitor class essential provides the same functionality as the simple traversal functions but in a class-based version. Using it, you can select whether you want to traverse the CFG in order or in reverse order.

To replicate the number collector from above, you can use the following code:

class CollectNumbersVisitor extends BasicCfgGuidedVisitor {
	private numbers: RNumberValue[] = [];
	private ast:     NormalizedAst;

	constructor(controlFlow: ControlFlowInformation, ast: NormalizedAst) {
		super({ controlFlow, defaultVisitingOrder: 'forward' });
		this.ast = ast;
	}

	protected override onVisitNode(node: NodeId): void {
		const astNode = this.ast.idMap.get(node);
		if(RNumber.is(astNode)) {
			this.numbers.push(astNode.content);
		}
		super.onVisitNode(node);
	}

	public getNumbers(): RNumberValue[] {
		return this.numbers;
	}
}

Defined at src/documentation/wiki-cfg.ts#L67

Instead of directly calling visitCfgInOrder we pass the forward visiting order to the constructor of the visitor. Executing it with the CFG and AST of the expression x - 1 + 2L * 3, causes the following numbers to be collected:

  • {"num":1,"complexNumber":false,"markedAsInt":false}
  • {"num":2,"complexNumber":false,"markedAsInt":true}
  • {"num":3,"complexNumber":false,"markedAsInt":false}

Syntax-Aware CFG Visitor

The SyntaxAwareCfgGuidedVisitor class incorporates knowledge of the normalized AST into the CFG traversal and directly provides specialized visitors for the various node types. Now, our running example of collecting all numbers simplifies to this:

class CollectNumbersSyntaxVisitor extends SyntaxAwareCfgGuidedVisitor {
	private numbers: RNumberValue[] = [];

	constructor(controlFlow: ControlFlowInformation, normalizedAst: NormalizedAst) {
		super({ controlFlow, normalizedAst, defaultVisitingOrder: 'forward' });
	}

	protected override visitRNumber(node: RNumber<ParentInformation>): void {
		this.numbers.push(node.content);
	}

	public getNumbers(): RNumberValue[] {
		return this.numbers;
	}
}

Defined at src/documentation/wiki-cfg.ts#L89

And again, executing it with the CFG and AST of the expression x - 1 + 2L * 3, causes the following numbers to be collected:

  • {"num":1,"complexNumber":false,"markedAsInt":false}
  • {"num":2,"complexNumber":false,"markedAsInt":true}
  • {"num":3,"complexNumber":false,"markedAsInt":false}

Dataflow-Aware CFG Visitor

There is a lot of benefit in incorporating the dataflow information into the CFG traversal, as it contains information about overwritten function calls, definition targets, and so on. Our best friend is the getOriginInDfg function which provides the important information about the origin of a vertex in the dataflow graph. The DataflowAwareCfgGuidedVisitor class does some of the basic lifting for us. While it is not ideal for our goal of collecting all numbers, it shines in other areas such as collecting all used variables, ...

class CollectNumbersDataflowVisitor extends DataflowAwareCfgGuidedVisitor {
	private numbers: RNumberValue[] = [];

	protected override visitValue(node: DataflowGraphVertexValue): void {
		const astNode = this.config.dfg.idMap?.get(node.id);
		if(RNumber.is(astNode)) {
			this.numbers.push(astNode.content);
		}
	}

	public getNumbers(): RNumberValue[] {
		return this.numbers;
	}
}

Defined at src/documentation/wiki-cfg.ts#L105

Again, executing it with the CFG and Dataflow of the expression x - 1 + 2L * 3, causes the following numbers to be collected:

  • {"num":1,"complexNumber":false,"markedAsInt":false}
  • {"num":2,"complexNumber":false,"markedAsInt":true}
  • {"num":3,"complexNumber":false,"markedAsInt":false}

Semantic CFG Visitor

The SemanticCfgGuidedVisitor class is flowR's most advanced visitor that combines the syntactic and dataflow information. The main idea is simple, it provides special handlers for assignments, conditionals, and other R semantics but still follows the structure of the CFG.

Note

This visitor is still in the design phase so please open up a new issue if you have any suggestions or find any bugs.

To explore what it is capable of, let's create a visitor that prints all values that are used in assignments:

class CollectSourcesSemanticVisitor extends SemanticCfgGuidedVisitor {
	private sources: string[] = [];

	protected override onAssignmentCall({ source }: { source?: NodeId }): void {
		if(source) {
			this.sources.push(RNode.lexeme(this.getNormalizedAst(source)) ?? '??');
		}
	}

	public getSources(): string[] {
		return this.sources;
	}
}

Defined at src/documentation/wiki-cfg.ts#L120

Executing it with the CFG and Dataflow of the expression x <- 2; 3 -> x; assign("x", 42 + 21), causes the following values (/lexemes) to be collected:

  • 2
  • 3
  • 42 + 21

All in all, this visitor offers the following semantic events:

Working With Exit Points

With the Dataflow Graph you already get a returns edge that tells you what a function call returns (given that this function call does neither transform nor create a value). But the control flow perspective gives you more! Given a simple addition like x + 1, the CFG looks like this:

flowchart LR
    n0(["`RSymbol (0)
**x**`"])
    n1(["`RNumber (1)
**1**`"])
    n2["`RBinaryOp (2)
**x #43; 1**`"]
    n0 -->|"flows to"| n1
    n1 -->|"flows to"| n2
    style n0 stroke:cyan,stroke-width:6.5px;    style n2 stroke:green,stroke-width:6.5px;
Loading
R Code of the CFG

The analysis required 2.4 ms (including the dataflow analysis, normalization, and parsing with the r-shell engine) within the generation environment. We used the following simplification: unique-cf-sets .

x + 1

The control flow is modeled in post-order: a vertex is reached once everything it is made of has been evaluated. For the addition above that means both operands come first and the + vertex itself is where they join again, so the vertex of an expression is its exit point ‐ there are no separate marker vertices.

Example: Where an if joins again 
flowchart LR
    n0(["`RSymbol (0)
**u**`"])
    n1["`RNumber (1)
**3**`"]
    n3["`RNumber (3)
**2**`"]
    n5["`RIfThenElse (5)
**if(u) 3 else 2**`"]
    n0 -.->|"branch on u (0) if T"| n1
    n0 -.->|"branch on u (0) if F"| n3
    n1 -->|"flows to"| n5
    n3 -->|"flows to"| n5
    style n0 stroke:cyan,stroke-width:6.5px;    style n5 stroke:green,stroke-width:6.5px;
Loading
R Code of the CFG

The analysis required 1.3 ms (including the dataflow analysis, normalization, and parsing with the r-shell engine) within the generation environment. We used the following simplification: unique-cf-sets .

if(u) 3 else 2

Both branches of the if (with id 5) flow into the if vertex itself, which is therefore the single point at which the statement is left, whichever branch ran.

Hence, the vertex of an expression names all of its exits, which is what keeps the graph a hammock graph without any auxiliary vertices.

Warning

Using basic blocks, this works just the same. However, please keep in mind that the vertex a control statement joins on does not have to be part of the same basic block as the branches leading to it.

Currently maintained by Florian Sihler and Oliver Gerstl at Ulm University
Email | GitHub | Penguins | Portfolio

💮 flowR Home (Landing Page)

Clone this wiki locally