skip to content

Sequence and Basic Blocks

6 roadmaps5 questions

Straight-line execution, the basic block, and the theorem that three control forms suffice for any program. Interviewers use it to check you can reduce tangled flow to a graph.

on this pageshow

explore

questions

5

Splitting a nightly payroll routine into basic blocks — which statements begin a new block, and why?

level: middleimportance: must knowfreq 46%

answer

  1. find the leaders first
  2. entry only at the top
  3. every branch target begins one
  4. so does the statement after a branch
  5. a leader runs to the next leader

basics

~20 s

A block starts at a leader: the routine's first statement, any statement a branch can jump to, and any statement immediately after a branch. A block then runs from its leader to just before the next one, entered only at its top.

solid answer

~40 s

A **basic block** is a maximal run of statements that control can enter only at the first and leave only at the last. You find them by marking **leaders** — the routine's first statement, every branch target, and every statement that directly follows a branch — and taking each leader together with the statements up to, but not including, the next leader. The boundaries fall exactly there because those are the only places control can arrive from somewhere unexpected or depart early. Inside a block every statement runs exactly once, in order, so reasoning about it is local and straight-line; all the branching is pushed onto the edges between blocks, which is what turns a routine into a graph you can reason about.

code

pseudocode · 8 lines
pseudocode
L1: hours = read timesheet          // leader: routine entry
    gross = hours * rate
    if gross <= 0 then jump to L3

L2: net = gross - deductions(gross) // leader: follows a branch
    emit payslip(net)

L3: log run complete                // leader: branch target

go deeper

for a junior

Remember the shape of the definition: one way in at the top, one way out at the bottom, nothing jumping into the middle.

for a middle

Be able to list the three kinds of leader and partition a short routine on the spot. The statement after a branch is the one candidates forget.

for a senior

Show that you use blocks to turn a long routine into a small graph before you change anything, and that you can say which statements your analysis treats as branching.

for a principal

The judgment call is how much control flow your models treat as an edge — failures, calls that may not return — because every edge you add costs analysis and review effort but every one you omit hides a real path.

## What a basic block is A **basic block** is a maximal sequence of statements with two properties: - control enters it only at its **first** statement; - control leaves it only at its **last** statement. "Maximal" matters: any three consecutive statements with no branching trivially satisfy the two properties, but a basic block is extended as far as it can be in both directions. The point is not to chop the routine finely; it is to find the biggest pieces that are honestly straight-line. ## Finding the leaders A **leader** is the first statement of a block. There are exactly three sources of them: 1. **the first statement of the routine** — control enters there from outside; 2. **any statement that a branch can jump to** — control can arrive there from somewhere other than the statement above it; 3. **any statement immediately following a branch** — the statement above it may not hand control on, so this one starts a fresh piece. Each leader, together with every statement up to but *not including* the next leader, is one basic block. Statement order inside the block is untouched by this process; it is a partition, not a rearrangement. ## Why the boundaries fall exactly there Work backwards from the two properties. | the rule | which property it protects | |---|---| | a branch target starts a block | otherwise control would enter in the middle | | the statement after a branch starts a block | otherwise control could leave from the middle | | the routine's first statement starts a block | it is the entry from outside | Notice what is *not* on that list. Blank lines, indentation, comments, the source language's own bracketing and the length of the run are all irrelevant. A block is defined by where control can move, not by how the text is laid out. ## What the blocks buy you - **Local reasoning is straight-line.** Inside a block, every statement executes exactly once and in written order, so questions about ordering, substitution and data dependence can be answered without considering any condition. - **Branching becomes an edge, not a statement.** Once blocks are nodes, the routine is a control-flow graph, and questions about reachability, dead code and merge points become graph questions. - **The size of what you must hold in your head shrinks.** A tangled routine with thirty statements may be six blocks; six nodes is something a person can draw on a whiteboard. - **Merging is easy to spot.** If block A's only successor is B and B's only predecessor is A, the two are one straight-line run and can be treated as a single block. ## The edge cases worth naming - **A call to another routine.** In a simple treatment, a call sits inside a block like any other statement. In an analysis that models the possibility that a call does not return normally — a failure that unwinds, a routine that never comes back — the call ends the block and gets its own outgoing edge. Say which model you are using. - **A statement that can fail.** The same reasoning: if the failure path is modelled, that statement terminates a block. - **A multi-way branch.** One block, many outgoing edges; the block does not split, the graph fans out. - **A branch target that is also the statement after a branch.** It is a leader once, for either reason. Leaders do not stack. ## Working the payroll routine Take a nightly run: read the timesheet, compute gross, skip the payslip if gross is not positive, otherwise compute net and emit, then log the run. There is one conditional branch, so there are exactly three leaders — the first statement, the statement after the branch, and the statement the branch can jump to — and therefore three blocks. Whether the payslip is emitted is now an edge in the graph rather than something to keep in mind while reading the arithmetic. That is the shift the technique buys, and it is what an interviewer is checking: can you stop reading a routine as a list of lines and start reading it as a small graph whose nodes happen to contain lines?

  • Does a call to another routine end a basic block?
    It depends on the model. If the analysis assumes every call returns normally to the next statement, the call sits inside the block. If it models calls that may not return — an unwinding failure, a routine that never comes back — the call is a branch, so it ends the block and gains an edge to the alternative path.
  • Block A's only successor is block B, and block B's only predecessor is block A. What follows?
    They are one straight-line run and can be merged into a single block. Control reaching A always continues into B, and nothing else can arrive at B, so neither of the two defining properties is violated by treating them as one node.
  • A statement is both a branch target and the statement following another branch. How many blocks start there?
    One. Leader status is a property of the statement, not a count of reasons — either condition alone makes it a leader, and both together still make it the first statement of exactly one block.

saying these in an interview costs you the question

  • Thinks a basic block is whatever the source brackets together
  • Starts a new block at every assignment statement
  • Puts the branch target at the end of the previous block
  • Believes control may jump into the middle of a block
  • Says block boundaries follow blank lines or indentation
open as a page

The structured program theorem claims three control forms suffice — what does its construction add to the code?

level: middleimportance: must knowfreq 55%

basics

~20 s

It adds bookkeeping: a control variable holding which chunk of the original flowchart runs next, wrapped in one loop over a selection that dispatches on it. The rewrite preserves the computed result, not the structure a reader sees.

open as a page

In a straight-line stretch of a payroll routine, when may two adjacent statements be swapped safely?

level: middleimportance: should knowfreq 42%

basics

~20 s

Only when neither depends on the other's effect: neither reads what the other writes, neither writes what the other reads, and they do not both write the same place. Observable effects count as a shared place too.

open as a page

A tangled nightly payroll routine can be flattened mechanically into one loop over a state variable — when is that transformation the right call for the team?

level: principalimportance: should knowfreq 33%

basics

~20 s

Rarely as a destination, often as a scaffold. The flattening is behaviour-preserving and mechanical, which is its whole value on code nobody dares touch, but it moves the structure into a variable, so it must be followed by extracting and naming real regions.

open as a page

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%

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.

open as a page