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
    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$ 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
    Jun 7, 2021 at 7:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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