skip to content

In a control-flow graph, what makes a region single-entry/single-exit, and what does that buy you?

level: seniorimportance: nice to knowfreq 28%

answer

  1. one way in, one way out
  2. entry nodes, not entry edges
  3. collapses to a single node
  4. each control form builds one
  5. a stuck collapse means added state

basics

~20 s

A region is single-entry/single-exit when every edge into it from outside lands on one node and every edge out of it leaves from one node. It can then be collapsed to a single node and reasoned about as one statement.

solid answer

~40 s

This is a property of the **graph**, not a rule about how code is written. A set of nodes is single-entry when all edges arriving from outside land on one node of the set, and single-exit when all edges leaving for outside depart from one node. The payoff is compositional: such a region behaves exactly like one statement, so you can collapse it to a single node and the surrounding graph is unchanged, reason about it with one entry condition and one exit condition, and replace its insides without touching anything else. Each of the three control forms builds a single-entry/single-exit region out of single-entry/single-exit parts, which is why structured code collapses cleanly and a tangled routine does not.

go deeper

for a junior

Hold on to the picture: a piece of a program with exactly one way in and one way out can be treated as a single step.

for a middle

State the property in terms of edges and nodes, and notice that many edges may arrive at the single entry node — it is entry nodes that are counted, not edges.

for a senior

Use it as a review tool: hunt for collapsible regions to extract, and treat the part that refuses to collapse as the routine's real control complexity.

for a principal

The leadership angle is what to do with the residue. A routine that will not reduce needs either added state or duplicated code, and choosing which one a team should prefer is a standard worth setting explicitly.

## The property, stated on the graph Take a set of nodes `R` inside a control-flow graph. `R` is **single-entry** when every edge that comes from a node outside `R` arrives at the *same* node of `R` — the entry. It is **single-exit** when every edge that leaves for a node outside `R` departs from the *same* node of `R` — the exit. Note what is allowed: - **many edges into the entry node** are fine; it is the number of distinct entry *nodes* that must be one; - **loops inside `R`** are fine; internal edges are unconstrained; - **the entry and the exit may be the same node**, which is the degenerate one-node region. What is forbidden is arriving in the middle, or leaving from the middle. Those are the two ways a region stops behaving like a single step. ## Why the three forms build them | control form | the region it builds | entry | exit | |---|---|---|---| | sequence of A then B | A's nodes plus B's nodes | A's entry | B's exit | | selection over A and B | the test, A, B, and the join | the test node | the join node | | iteration of body A | the test plus A | the test node | the test node | Read the table as an induction: each form takes regions with the property and produces a region with the property. That is the real content of "the three forms compose" — they are closed under this graph property, so anything built from them collapses, and anything that does not collapse was not built from them. ## Collapsing the graph The practical procedure is short: 1. Find a set of nodes satisfying both conditions, with more than one node in it. 2. Replace the whole set with a single node, attaching every incoming edge where the entry's incoming edges were and every outgoing edge where the exit's outgoing edges were. 3. Repeat. Step 2 is safe precisely because the outside edges only ever touched the entry and the exit, so nothing outside the region has to be rewritten. Keep going and a routine assembled from sequence, selection and iteration reduces to a single node. ## When the collapse gets stuck Sometimes the procedure halts with several nodes left and no qualifying region. That is informative rather than a failure: the remaining tangle is flow with no direct expression in the three forms — typically because a loop can be entered at two different nodes, or a region has two distinct ways in. To express that flow with sequence, selection and iteration you must add state, so that the second entry becomes a value rather than an edge, or duplicate code, so that each entry gets its own copy of what follows. This is the same fact the structured program theorem states from the other direction, and it is why the theorem's licence to add variables is not a technicality. ## What the property is not It is a statement about edges in a graph. It is not a claim about how a routine is laid out in text, and it is not a count of anything in the source. Reviewers sometimes invoke the phrase as if it constrained the shape of a routine's source; it does not — you can reason about entries and exits of a region regardless of how that region is spelled. It is also not a promise that the region is small, simple, or side-effect free. A region with one way in and one way out may contain any amount of machinery. The property tells you the region *composes* like one statement, not that it *is* one. ## Using it in review When you look at a long routine and feel the usual dread, the useful move is to hunt for these regions rather than to read top to bottom: - a run of nodes with one way in and one way out is a candidate to be **named** — extract it, and the name becomes the summary of its entry and exit conditions; - what is left after extracting every such region is the routine's genuine control complexity, and it is usually much smaller than the line count suggested; - if extraction keeps failing because something jumps into the middle of the candidate, that is the finding — write it down, because it tells you where state has to be introduced. That is the whole technique: use the property to decide what can be pulled out cleanly, and treat the residue that resists as the real work.

  • Why does a region with two distinct entry nodes resist being written with the three control forms?
    Because each of the three forms produces a region entered at exactly one node, so no composition of them can produce two. Expressing the flow anyway means encoding the choice of entry in a value the region tests, or duplicating the region so each entry has its own copy.
  • What does it mean when the collapse halts with more than one node remaining?
    That what is left is not expressible directly as sequence, selection and iteration over the parts already collapsed. It marks the routine's genuine control complexity, and tells you the restructuring will need added state or duplicated code rather than pure extraction.
  • Several edges arrive at the region's entry node from outside. Is it still single-entry?
    Yes. The condition constrains the number of distinct nodes where outside control can land, not the number of edges landing there. Many callers converging on one entry is exactly the normal case, and collapsing the region simply re-attaches all of those edges to the new node.

A single-entry/single-exit region is a sealed room with one door in and one door out: you can rebuild the inside however you like, and nobody in the rest of the building has to be told.

saying these in an interview costs you the question

  • Reads it as a rule about how many times a routine returns
  • Thinks several edges into one entry node break the property
  • Believes a region containing a loop cannot be single-exit
  • Says collapsing a region alters the surrounding graph's behaviour
  • Assumes every routine's graph collapses to one node eventually