The first chapter ended with a φ function that named “block 3” and “block 4”. This chapter shows what a block is, how the blocks of a routine form a graph, and which structure of that graph decides where SSA needs a φ: dominance.

The program

Work in the folder from chapter 1:

mkdir -p ssa-lab && cd ssa-lab

This chapter and the next two use one program. Save it as Evens.mica:

{
    Evens - the count of even numbers from 1 to a limit, found by testing each number in turn.

    A loop around a decision: 'count' changes only on the even rounds, 'k' on every round, and 'last' remembers the
    last even number seen without anyone reading it yet.
}
program Evens;

imp
    WriteLn : std;

{ The even numbers from 1 to the limit are counted one test at a time, and 'last' keeps the latest for nobody to read. }
function CountEven(limit : int64) : int64;
var
    count, k, last : int64;
begin
    count := 0;
    last := 0;
    k := 1;

    while k ≤ limit do
    begin
        if k mod 2 = 0 then
        begin
            count := count + 1;
            last := k;
        end;

        k := k + 1;
    end;

    CountEven := count;
end;

begin
    WriteLn("from 1 to 10 there are %lld even numbers", CountEven(10));
end.

Run it, then export it at the debug tier:

mica Evens.mica
mica --compile --optimize debug --platform linux,amd64,utf-8 --source Evens.mica --build build/debug --export
from 1 to 10 there are 5 even numbers
Exporting intermediate representations of source 'Evens.mica' to 'build/debug/export'

In the Spectra files, v2.1 is count, v2.2 is k, v2.3 is last, v2.4 is the result CountEven, and p2.1 is the parameter limit.

Basic blocks

A program does not run its instructions in the order they are written down: jumps send control forwards and backwards. To reason about every order that can happen, a compiler cuts the instruction list into basic blocks. A basic block is a straight run of instructions that control enters only at its first instruction and leaves only after its last. Inside a block there is nothing to decide: once the first instruction runs, all of them run, in order.

The cut follows a simple rule. A new block starts at the first instruction, at every label, and right after every jump. Mica writes the blocks to Evens.055.cfg-before-ssa. Block 3 is the test of the while loop:

      +- block 3
      |  +- function_name: Evens.CountEven
      |  +- labels: [l2.4]
      |  +- predecessors: [2, 6]
      |  +- successors: [7, 4]
      |  +- terminator: conditional_jump
      |  +- entry: false
      |  +- exit: false
      |  +- token_stream_index: 40
      |  +- instructions
      |     +- @l2.4:
      |     +- t2.4:int64 = loadVariable v2.2:int64 #13
      |     +- t2.5:int64 = loadVariable p2.1:int64 #14
      |     +- t2.6:bool = lessEqual t2.4:int64, t2.5:int64 #15
      |     +- jumpNotEqual t2.6:bool, @l2.5

It starts at the label @l2.4 and ends with the conditional jump out of the loop. Its predecessors are the blocks control can come from, its successors the blocks control can go to next; a conditional jump lists the block it jumps to first. Block numbers count through the whole program: the program body owns blocks 0 and 1, and CountEven owns blocks 2 to 8.

The control-flow graph

The blocks are the nodes of a graph, the control-flow graph, and an edge says that one block can run right after another. The file opens with every edge:

+- control_flow_graph
   +- block_count: 9
   +- edge_count: 9
   +- edges
   |  +- 0 -> 1 (fallthrough)
   |  +- 2 -> 3 (fallthrough)
   |  +- 3 -> 7 (taken)
   |  +- 3 -> 4 (fallthrough)
   |  +- 4 -> 6 (taken)
   |  +- 4 -> 5 (fallthrough)
   |  +- 5 -> 6 (fallthrough)
   |  +- 6 -> 3 (jump)
   |  +- 7 -> 8 (fallthrough)

An edge’s kind says how control gets there: jump follows an unconditional jump, taken a conditional jump that jumps, and fallthrough runs on into the next block. Drawn by hand from these edges, CountEven is a loop with a decision inside:

              block 2     count := 0, last := 0, k := 1      (the entry)
                 |
                 v
    +------> block 3      @l2.4: while k ≤ limit ---- taken ---> block 7   CountEven := count
    |            |                                                  |
    |            v                                                  v
    |        block 4      if k mod 2 = 0                         block 8   the way out
    |        /       \
    |       v         \ taken
    |   block 5        |
    |   count := count + 1, last := k
    |       \          |
    |        v         v
    +------- block 6      @l2.6: k := k + 1, then jump back to block 3

The edge 6 -> 3 goes back up to the loop’s test. An edge like it, whose target is reached on every path to its source, is a back edge: it is what makes a loop. The if without an else makes a triangle: block 4 either runs block 5 or jumps straight to block 6, where the two ways meet again.

The export writes two graphs, 050.cfg and 055.cfg-before-ssa. The second is the graph SSA is built on; the first is the graph of the code that is finally turned into machine code, which after optimization is a different program. At the debug tier they are one graph:

cmp build/debug/export/Evens.050.cfg build/debug/export/Evens.055.cfg-before-ssa && echo identical
identical

This series reads 055.cfg-before-ssa, because the φ functions name its blocks at every tier.

Dominance

Block A dominates block B when every path from the routine’s entry to B passes through A. Every block dominates itself. In CountEven, block 3, the loop test, dominates every block of the loop: there is no way into blocks 4, 5 or 6 that does not pass the test. Block 5 dominates nothing but itself, because the jump from block 4 to block 6 goes around it.

Among the blocks that dominate B, other than B itself, the closest to B is its immediate dominator. Every block except the entry has exactly one, so the immediate dominators form a tree, the dominator tree, with the entry at its root.

The dominance frontier of A is where A’s dominance ends: the blocks B such that A dominates a predecessor of B but does not strictly dominate B itself. In words, the frontier holds the first blocks where a path that came through A meets a path that did not.

The file Evens.060.dominance holds all three, for every routine:

function Evens.CountEven entry=2 rpo=[2 3 4 5 6 7 8]
  block 2 idom=- rpo=0 children=[3] df=[]
  block 3 idom=2 rpo=1 children=[4 7] df=[3]
  block 4 idom=3 rpo=2 children=[5 6] df=[3]
  block 5 idom=4 rpo=3 children=[] df=[6]
  block 6 idom=4 rpo=4 children=[] df=[3]
  block 7 idom=3 rpo=5 children=[8] df=[]
  block 8 idom=7 rpo=6 children=[] df=[]
FieldIt means
entry=2the routine’s entry block, the root of its dominator tree
idomthe immediate dominator; - for the entry
childrenthe blocks whose immediate dominator this block is
dfthe dominance frontier
rpothe block’s place in reverse postorder, an order in which a block comes before its successors except along back edges

Drawn by hand from the children lists, the dominator tree is:

block 2
└── block 3
    ├── block 4
    │   ├── block 5
    │   └── block 6
    └── block 7
        └── block 8

Block 6’s immediate dominator is block 4, not block 5: block 4 is the last block every path to block 6 must pass.

Now read the frontiers against the drawing of the graph:

  • Block 5 dominates itself, and it is a predecessor of block 6, but it does not dominate block 6, which can be reached around it. So block 6 is in its frontier: df=[6]. Block 6 is where the path through block 5 meets the path that skipped it.
  • Block 6 is a predecessor of block 3, over the back edge, and does not dominate it, so block 3 is in its frontier.
  • Block 3 dominates block 6, a predecessor of block 3, but no block strictly dominates itself, so the loop’s test is in its own frontier. Every loop header is: it is where the value from before the loop meets the value from the end of a round.
  • Block 2, the entry, dominates everything, so its frontier is empty.

The frontier is exactly where a value written in one block can meet a different value of the same variable that arrived another way. That is why the next chapter puts its φ functions there.

How Mica computes it

Mica finds the dominators with the iterative algorithm of Cooper, Harvey and Kennedy. It visits the blocks in reverse postorder and gives each block, as its immediate dominator, the place where the tree paths of its already visited predecessors meet: two fingers, one per predecessor, climb the tree built so far until they point at the same block. It repeats the visit until nothing changes. The frontiers come from the walk the same paper gives: for every block with two or more predecessors, climb the tree from each predecessor up to the block’s immediate dominator, and add the block to the frontier of every block passed on the way.

The file’s first line, self-check: ok, is a promise kept on every export: when you export, Mica computes the dominators a second time by the slow textbook method, every block’s whole set of dominators narrowed until nothing changes, and stops the compilation if the two answers disagree.

self-check: ok

Try it

Give the decision an else arm, so that last forgets on an odd number. Replace the end of the if statement:

if k mod 2 = 0 then
begin
    count := count + 1;
    last := k;
end
else
    last := 0;

Export again and read the edges and the dominance of CountEven:

+- control_flow_graph
   +- block_count: 10
   +- edge_count: 10
   +- edges
   |  +- 0 -> 1 (fallthrough)
   |  +- 2 -> 3 (fallthrough)
   |  +- 3 -> 8 (taken)
   |  +- 3 -> 4 (fallthrough)
   |  +- 4 -> 6 (taken)
   |  +- 4 -> 5 (fallthrough)
   |  +- 5 -> 7 (jump)
   |  +- 6 -> 7 (fallthrough)
   |  +- 7 -> 3 (jump)
   |  +- 8 -> 9 (fallthrough)
function Evens.CountEven entry=2 rpo=[2 3 4 5 6 7 8 9]
  block 2 idom=- rpo=0 children=[3] df=[]
  block 3 idom=2 rpo=1 children=[4 8] df=[3]
  block 4 idom=3 rpo=2 children=[5 6 7] df=[3]
  block 5 idom=4 rpo=3 children=[] df=[7]
  block 6 idom=4 rpo=4 children=[] df=[7]
  block 7 idom=4 rpo=5 children=[] df=[3]
  block 8 idom=3 rpo=6 children=[9] df=[]
  block 9 idom=8 rpo=7 children=[] df=[]

The triangle became a diamond. The new block 6 is the else arm, the merge is now block 7, and both arms have it as their whole frontier: a path through either arm meets the other at the merge. The decision, block 4, still dominates the merge, and the merge’s frontier is still the loop’s test.

Undo the edit before you go on: the next chapter reads the program as you saved it.

Next: Where the φ functions go.