4
$\begingroup$

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.

$\endgroup$
5
$\begingroup$

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:

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

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

procedure3():
  return procedure2()
$\endgroup$
3
  • 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 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$ – Wandering Logic Jun 6 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 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.