Single-Entry Single-Exit (SESE) regions are a fundamental concept in structured programming and control-flow analysis. A SESE region is a portion of a program with exactly one entry point and one exit point, enabling modular reasoning, formal verification, and compiler optimization. Although the term SESE was popularized in the late 1980s, the underlying ideas date back to the origins of structured programming and the development of flow-graph theory in the 1970s.
In a control-flow graph (CFG), a SESE region is typically defined as a subgraph with: [1] [2]
A node x is said to dominate node y in a directed graph if every path from start to y includes x. A node x is said to post-dominate a node y if every path from y to end includes x.
This definition makes SESE regions mechanically identifiable and suitable for static analysis.
The conceptual roots of SESE lie in structured programming, developed in the 1960s to address the complexity caused by unrestricted jumps (goto). In 1964, Böhm defined a primitive programming language — P′′ — that was explicitly based on the SESE property:
a) It is only possible to enter a cycle from its first instruction, ...
b) It is only possible to exit a cycle from its last instruction.
— Böhm (1964) [3]
Böhm and Jacopini (1966) showed that any program can be written using sequence, selection, and iteration. [4] Dijkstra (1968) argued that programs must have clear control structure to be understandable and provably correct. [5] Hoare (1969), defining a logic for program correctness, assumed well-defined entry and exit points. [6]
All structured control constructs introduced in this period naturally obey the single-entry single-exit discipline.
Early work on control-flow analysis laid the foundation for the flow-graph representations used in SESE regions. The control-flow graph (CFG) was first introduced in the context of compiler optimization by Frances E. Allen, who formalized CFGs as representations of basic blocks and control flow, providing a basis for dominance analysis and other structural techniques used in SESE identification. [7]
Kosaraju used these CFG representations to give SESE regions their formal graph-theoretic characterization. [8] He defined single-entry single-exit regions within control-flow graphs and showed how structured programs can be decomposed into hierarchically nested SESE regions corresponding to standard control constructs such as conditionals and loops. This work demonstrated that SESE structure is not merely a stylistic guideline but a property that enables systematic program decomposition and facilitates formal program analysis and reasoning.
In the early to mid-1970s, Aho, Hopcroft, and Ullman (AHU) extended these ideas, developing formal frameworks for [9]
Intervals define single-entry regions within a CFG. Although AHU did not explicitly use the term SESE, their framework provided the mathematical basis for identifying regions with disciplined entry and exit behavior.
The term Single-Entry Single-Exit (SESE) was explicitly named and popularized by Ferrante, Ottenstein, and Warren (1987). [1]
Their contributions include:
Ferrante et al. explicitly credited AHU for the underlying flow-graph theory.
SESE regions are central to:
Because SESE regions isolate control flow, they allow transformations and reasoning to be performed locally while preserving global correctness.