I would like to render a control flow graph (CFG) out to high-level code. Normally this is very easy; walk the tree, render each basic block in turn, glue it all together with gotos.
Unfortunately, gotos are out of fashion these days, and most modern languages don't support them. So I need some way to glue my basic blocks together using only those control flow statements that exist in the language: for, while, do...while, if, break and continue. (I'm not willing to consider building a state machine using variables.)
It would appear that while there are algorithms to do this, they will not work in every case. That is, it's possible to construct a CFG that cannot be flattened to structured code using only the above limited set of control flow structures.
This seems intuitively obvious to me, but I can't prove it (and the documentation for the algorithms I've found don't go into more detail). And I haven't been able to find an example of a CFG which can't be flattened like this.
I would like to know, definitively, if this is possible or not.
Option (a): does anyone have a example of a CFG which cannot be flattened as described above? (Which will tell me that it's not possible.)
Option (b): does anyone have a proof that CFGs can be flattened as described above? (Which will tell me that it is possible.) An algorithm to do it would be highly desirable, too, as I would then have to make it work...
I think I have a result.
The answer seems to be: it is not possible. This is from Communications of the ACM, volume 9, pages 366 to 371 in a paper from 1966 called "Flow Diagrams, Turing Machines and Languages with only Two Formation Rules" by Giuseppe Jacopini. CiteSeer link. (Which, amusingly, I found referenced from Knuth's seminal (and, from my point of view, incredibly annoying) Go To Statement Considered Harmful.)
Disappointingly, they don't have a proof, saying they were unable to find one.
The good news is that the paper does describe a strategy for converting an arbitrary CFG into a CFG using only limited control-flow mechanisms in an efficient fashion, using as little state as possible. The paper is pretty hard going but it looks promising.