I've been looking through research papers and the internet and found many claims that "compiler optimizations can cause irreducible control flow". However, I was not able to find a single example of how that can happen. In particular, in [1], there is written that tail recursion elimination in combination with inlining can yield an irreducible control flow graph. I can imagine some transformations that could create irreducible control flow, but I cannot come up with an example of how tail recursion elimination with inlining can do that?

Does anybody have a pointer here?


[1] J. Stainer, D. Watson. A study of irreducibility in C programs.


1 Answer 1


Steele and Sussman's "LAMBDA The Ultimate Imperative", AI Memo 353, 1976 explains that a (tail) procedure call is just a goto statement and the name of the procedure is just a label.

So the classic irreducible flow graph:

an irreducible flow graph

(copy pasted from http://staff.cs.upt.ro/~chirila/teaching/upt/c51-pt/aamcij/7113/Fly0135.html)

Can be written:

  if (some-condition):
    return procedure2()
    return procedure3()

  if (some-other-condition):
    return True
    return procedure3()

  return procedure2()
  • 1
    $\begingroup$ I suppose you could argue that inlining is necessary to combine these three functions into a single flowgraph that can be classified as irreducible. It's a bit ambiguous since one can also treat a flowgraph as a collection of tail-recursive functions. $\endgroup$
    – benrg
    Commented Jun 5, 2021 at 21:52
  • $\begingroup$ You are correct. I've removed that statement about inilining being unnecessary. Flow graphs are almost always thought of as being intra-procedural, so you need the inlining. $\endgroup$ Commented Jun 6, 2021 at 14:11
  • $\begingroup$ But doesn't inlining always create a new copy of the procedure? That is, the labels generated for inlined instances of procedure2 would be different and the flow would not be irreducible. $\endgroup$
    – Edown
    Commented Jun 7, 2021 at 7:49
  • $\begingroup$ You can't copy the procedure when inlining mutually recursive functions as that will create copies infinitely. In the example you need to inline the CFGs of functions in the parent function (procedure1) and introduce edges between them, and somehow to the stack manipulation before the jumps (push args, pop return values etc.). I don't know if compilers actually do this kind of thing though. I think most compilers will simply not inline mutually-recursive groups. $\endgroup$
    – osa1
    Commented Oct 5, 2022 at 9:41

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.