2 ms·
If you have labelled break and continue, you can construct any reducible CFG, including other kinds of unstructured graphs [1]. Loops with multiple entry points
by jcranmer 8y ago
If you have labelled break and continue, you can construct any reducible CFG, including other kinds of unstructured graphs [1]. Loops with multiple entry points are a necessary and sufficient condition for irreducible CFGs, and cannot be described with labelled break and continue. I don't know if you intend to consider generic labelled break/continue as having a goto, but if you do, they can't jump into the middle of a loop.
C and C++ are the most well-known languages with an unlimited goto, and they do allow you to jump into the middle of a loop. Worse, the switch statement also works as a hidden goto and can similarly be used to construct irreducible loops. There's even a name for how to do this... Duff's device.
[1] The definition of unstructured graph changes between authors on which constructs it includes, because it's a general term for "CFGs our algorithm cannot handle." A simple requirement is that every merge point must either postdominate its immediate dominator or be a loop header, but this definition means that even things such as multiple return statements, short-circuit and/or, and vanilla break statements cause unstructured graphs. Reducible CFG is a much more stringent definition, but graphs such as ladder graphs, lattice graphs, and complete graphs that bring out worst-case performance in algorithms are reducible by virtue of being acyclic.