snippetMinor
How compiler optimizations create irreducible control flow graph?
Viewed 0 times
irreducibleflowcreatecontrolgraphcompilerhowoptimizations
Problem
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.
Does anybody have a pointer here?
Thanks
[1] J. Stainer, D. Watson. A study of irreducibility in C programs.
Solution
Steele and Sussman's "LAMBDA The Ultimate Imperative", AI Memo 353, 1976 explains that a (tail) procedure call is just a
So the classic irreducible flow graph:
(copy pasted from http://staff.cs.upt.ro/~chirila/teaching/upt/c51-pt/aamcij/7113/Fly0135.html)
Can be written:
goto statement and the name of the procedure is just a label.So the classic 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()
Context
StackExchange Computer Science Q#141040, answer score: 5
Revisions (0)
No revisions yet.