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.

0

1 Answer 1

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.

4
  • Thank you for the clarification, I was wondering if it just wasn't possible. So basically this.
    – HareSurf
    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.
    – HareSurf
    Commented Jul 20, 2018 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
    Commented Jul 20, 2018 at 10:47
  • 2
    Or, Continuation Passing Style (CPS) which is isomorphic to Static Single Assignment (SSA). Commented Jul 20, 2018 at 12:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.