WCET (Worst Case Execution Time) analysis: Visual walkthrough

We build on WCET (Worst Case Execution Time) analysis, and we will lean on the picture-language of the Control Flow Graph (CFG) and the timing ideas from Cache Memory Architecture. Everything else we construct here from zero.

Step 1 — What does "execution time" even mean?

WHAT. A program is a list of tiny machine instructions. When the CPU runs one, it needs a certain number of clock cycles — a cycle is just one tick of the CPU's internal metronome. If the CPU ticks 1 billion times a second, one cycle is one-billionth of a second.

WHY start here. Before we talk about "worst case" we must agree on the unit we are counting. We count cycles, not seconds, because cycles are what the hardware guarantees; seconds depend on clock speed. Everything downstream is a sum of cycle counts.

PICTURE. Below, each instruction is a black tile; its width is how many cycles it eats. Total time = total width. That is the entire idea of execution time: line the tiles up, measure the length.

Step 2 — Group instructions into blocks

WHAT. A basic block is a run of instructions with one way in and one way out — no jump lands in the middle, no branch leaves the middle. Once you enter, you run all of it.

WHY group them. Counting individual instructions is exhausting. But inside a basic block there are no decisions, so its cycle cost is a fixed number we can compute once and reuse. This shrinks the problem from "thousands of instructions" to "a handful of blocks."

PICTURE. The find_max code from the parent collapses into five blocks. Watch the red block B — it is the loop's test, the block we will hit again and again.

Step 3 — Turn the blocks into a graph (the CFG)

WHAT. Draw one node per block. Draw an arrow from block $X$ to block $Y$ if control can flow from $X$ into $Y$ . This picture is the Control Flow Graph (CFG).

WHY a graph. Execution time is not "add all blocks once." Some blocks are skipped (the else path), some repeat (the loop). A graph captures which blocks can follow which — exactly the information a plain sum throws away.

PICTURE. The red arrow is the loop back-edge $D \to B$ : it is the only arrow that goes upward, and it is why block B runs many times. Kill that arrow and there is no loop.

Step 4 — Give every block an execution count

WHAT. Let $x_{b}$ be the number of times block $b$ executes on a single run of the function. Then the run's total time is a weighted sum.

WHY counts, not paths. There are $2^{branches}$ possible paths — too many to list. But there are only five counts $x_{A}, \dots, x_{E}$ . If we can pin those five numbers, we get the time without ever enumerating paths.

PICTURE. Each block now wears a badge $x_{b}$ = how many copies of it stack up. Block B's stack is the tall red one.

Step 5 — Bound the loop, or the answer is infinity

WHAT. How big can each count get? The loop runs for (i=1; i<n; i++) with $n \leq 1000$ .

The body blocks C and D run once for each value of $i$ from $1$ to $n - 1$ : that is $n - 1$ times.
The test block B runs once more than the body: it fires for each of the $n - 1$ successful tests and one final time to discover i < n is false and exit the loop. So B runs $n$ times.

WHY B runs one extra time. A for loop always checks its condition before deciding to run the body. The last check is the one that says "stop" — the body does not run after it, but the test still costs its cycles. Forgetting that final failing test would make our bound too small (unsafe), so we keep it.

WHY we MUST bound it at all. Without a loop bound, the graph has that upward red arrow and the analyzer must assume the loop never stops → $x_{B} = \infty$ → the whole time estimate is $\infty$ . A useless answer. The bound $n \leq 1000$ is the one fact a machine cannot guess; a human or a static analyzer must supply it.

PICTURE. On the left, no bound: the count column shoots off the top (∞, red). On the right, the bound caps it — note B's stack is one taller than C's and D's, that extra tile is the failing exit test.

Step 6 — Pick the worst case inside each block: the branch and the cache

WHAT. Two "worst-case" choices live here.

The branch (block C's if). Is arr[i] > max true? If yes, block D runs; if no, D is skipped. To be safe we assume the more expensive option every single iteration: D always runs.
The cache (inside D). Reading arr[i] might be a cache hit (a few cycles) or a miss. To be safe we assume the miss (see Cache Memory Architecture).

A word on the number 6. On real hardware a cache hit costs a handful of cycles while a miss can cost 100–300 cycles — two orders of magnitude more. If we used the true miss cost, $T_{D}$ would be, say, $105$ and every number on this page would balloon. To keep the derivation's shape visible we use a small stand-in, $T_{D} = 6$ , meaning "the costly branch." The method is identical with the real number; only the digits change. In an honest analysis you would plug the measured miss penalty in here.

WHY assume the worst at all. WCET must be a safe upper bound: it has to be $\geq$ every real run. If we ever pick the cheaper option and reality picks the dearer one, our bound is too small and the safety proof collapses — the airbag fires late.

PICTURE. Two forks. At each fork the red path is the expensive one, and WCET always takes red. Left fork = branch taken; right fork = cache miss.

Step 7 — Assemble the whole run

WHAT. Put the once-only blocks (A and E) around the loop, multiply the per-iteration cost by the loop bound, and add the single final failing test.

WHY this shape. A executes once at entry, E once at exit — they are the boundary of the run, outside the loop. The middle is $(n - 1)$ copies of the 13-cycle worst iteration. Then one lone $T_{B}$ for the exit test that nobody's iteration owns. Add them.

PICTURE. A timeline: a fixed red cap ( $A$ ) on the left, a fixed cap ( $E$ ) on the right, a stretchable middle of $(n - 1)$ identical 13-cycle tiles, and a lone thin red tile (the final failing test $T_{B}$ ) just before $E$ .

Plug in the deadline-critical size $n = 1000$ : $WCET (1000) = 13 \times 1000 - 3 = 13000 - 3 = 12, 997 cycles .$

Step 8 — The degenerate cases (never let the reader hit an unshown scenario)

WHAT. Check the edges where the formula could break.

WHY. A bound that is right for $n = 1000$ but wrong for $n = 1$ is still wrong. Safety-critical means all inputs.

PICTURE. Four tiny scenarios: $n = 1$ (loop body never runs, but the test still fires once to exit), $n = 2$ (exactly one body pass), the "all branches false" run (D skipped every time — the best case, shown so you can see WCET sits above it), and $n = 0$ (empty array — the arr[0] read is itself the danger).

Case	What happens	From $13 n - 3$	Concrete check
$n = 1$	body runs $0$ times; A, one failing test $T_{B}$ , E	$13 (1) - 3 = 10$	$T_{A} + T_{B} + T_{E} = 5 + 3 + 2 = 10$ ✓
$n = 2$	one body pass, then the failing test	$13 (2) - 3 = 23$	$5 + 13 + 3 + 2 = 23$ ✓
all branches false	D skipped every pass (best case)	must be $< 13 n - 3$	$5 + (n - 1) (3 + 4) + 3 + 2 = 7 n + 3$ ; at $n = 1000$ that is $7003 < 12997$ ✓ safe
$n = 0$	`arr[0]` reads past an empty array — a bug, not a timing case	formula gives $- 3$ (nonsense)	WCET assumes valid input; guard $n \geq 1$

The one-picture summary

Everything above compresses into a single diagram: from source code → blocks → CFG → counted & bounded (with the extra exit test!) → worst-case chosen → summed into $13 n - 3$ . The red thread is the loop, the one thing that makes WCET grow.

Recall Feynman retelling — say it like you'd explain to a friend

"Running a program just means the CPU chews through instructions, and each one costs a few clock ticks, so execution time is really just adding up ticks. Instead of tracking thousands of instructions I glue them into blocks — chunks with one entrance and one exit, so each block has a fixed price. Then I draw arrows showing which block can follow which; that's the control-flow graph. The trick is: I don't care which path runs, I care how many times each block runs. Most blocks run once, but the loop test runs a lot — and here's the sneaky bit: the test runs one extra time to notice the loop is over and quit, so if the body runs $n - 1$ times the test runs $n$ times. I have to cap that or the answer is infinity, so I say 'this loop runs at most $n - 1$ body passes.' At every fork I deliberately choose the expensive side — assume the if is always taken, assume every memory read misses the cache — because a worst-case bound is only useful if nothing real can beat it. Then I just add: block A once (5), the loop body $n - 1$ times at 13 cycles each, one lonely final test (3), and block E once (2). Bundle the constants $5 + 2 = 7$ , fold the extra test in, and out comes $13 n - 3$ . For a thousand-element array that's 12,997 cycles. I even check the tiny cases: $n = 1$ gives 10 cycles (A, one failing test, E — no body), and the best case where the if never fires is cheaper, sitting safely below my bound. That last part is the reason I can promise the deadline is met — always, not usually. And notice I found a bug in the parent's number: it forgot the exit test and was three cycles too small."

See also: Real-Time Scheduling Algorithms (where this WCET becomes $C_{i}$ in the response-time test), Static Program Analysis (how loop bounds get found automatically), and Compiler Optimizations (why the machine code you time is not the source you wrote).