# How compiler optimizations create irreducible control flow graph?

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?

Thanks

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

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:

Can be written:

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

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

procedure3():
return procedure2()

• 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. Jun 5, 2021 at 21:52
• 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. Jun 6, 2021 at 14:11
• 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. Jun 7, 2021 at 7:49