What are some applications where irreducible control flow is required*?

I'm particularly interested in programming language features that will be tricky to efficiently compile if the compile target does not permit irreducible control flow. For example, a programming language offering GOTO will generate irreducible control flow for some programs. What other language constructs are like this? For example, is irreducible control flow required to implement resumable exceptions?

I'm also interested in application-level uses of irreducible control flow.

(*: irreducible control flow graphs (CFGs) can be converted to reducible CFGs at some cost, and also some compiler optimizations can convert reducible CFGs to irreducible CFGs, so what I mean is that the original, unoptimized CFG produced by the source code is irreducible. Less formally, I mean that the "programmer's intent" naturally includes irreducible control flow)


1 Answer 1


Spitballing here, but the automata used to implement regular expressions, inside a lexical analyzer for example, could have irreducible control flow. This might happen for example if your lexer bounces back and forth between states (think "normal", "string literal", "comment") and if the automaton is compiled down to code, not interpreted.


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.