How a Control-Flow Graph looks with many (Nested) Functions

From what I can remember the Control-Flow Graphs for which I have seen images have mostly been of single functions. So basically just statements with perhaps looping. But I am wondering what a control-flow graph would look like for a function, which may reference nested functions, which may reference other nested functions, etc.

For example, here is a set of functions:

``````function a(x) {
var m = b(x)
var n = c(x)
return m + n
}

function b(x) {
var m = d(x)
var n = e(x)
return m * n
}

function c(x) {
var m = d(x)
var n = e(x)
return m - n
}

function d(x) {
var i = x
var o
while (i--) {
if (i % 2 == 0) {
o += (x * 2)
} else {
o -= (x * 3)
}
}
return o
}

function e(x) {
var i = x
var o
while (i--) {
if (i % 3 == 0) {
o += (x * 3)
} else {
o -= (x + 3)
}
}
return o
}
``````

Wondering what it would look like as a Control-Flow Graph, or maybe just the nesting part to get started.

``````                       a(x)
___________|___________
|                      |
var m = b(x)           var n = c(x)
|                      |
?                      ?
``````

Hoping to do this without inlining the functions, which is just an artifact of the example functions chosen.

1 Answer

It is not possible to draw an accurate control flow graph (CFG) that includes function calls: a function may be called from multiple locations. The target of the control flow edge that represents a return depends on the return address which is run-time data. If we were to draw an edge for each statically possible call site, the graph would contain paths that are not actually possible, e.g. a call that returns to a completely different callsite.

Instead, the useful equivalent is a call graph which illustrates the dependencies between functions.

• Thank you for the clarification, I was wondering if it just wasn't possible. So basically this. Commented Jul 20, 2018 at 10:38
• This also must mean data-flow graphs work on control-flow graphs and so work on the IR of a program rather than at the higher level. Commented Jul 20, 2018 at 10:41
• @LancePollard The paper you linked addresses a more difficult problem: call graphs for OOP: the target of a virtual call depends on the runtime type of an object. Yes, high-level representation ASTs have an unsuitable structure for studying data flows. You might enjoy the LLVM-IR which uses static single assignment which makes data flow analysis very easy.
– amon
Commented Jul 20, 2018 at 10:47
• Or, Continuation Passing Style (CPS) which is isomorphic to Static Single Assignment (SSA). Commented Jul 20, 2018 at 12:07