1

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.

Lance
  • 2,537
  • 15
  • 34

1 Answers1

1

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.

amon
  • 132,749
  • 27
  • 279
  • 375
  • Thank you for the clarification, I was wondering if it just wasn't possible. So basically [this](https://www.diva-portal.org/smash/get/diva2:205514/FULLTEXT01.pdf). – Lance Jul 20 '18 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. – Lance Jul 20 '18 at 10:41
  • 1
    @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 Jul 20 '18 at 10:47
  • 2
    Or, *Continuation Passing Style (CPS)* which is isomorphic to *Static Single Assignment (SSA)*. – Jörg W Mittag Jul 20 '18 at 12:07