I start to look at the source code of
QBE today.

Traversing along the CFG in reversed post order
is a very common procedure in data flow analysis.
So we start from here.

In QBE, the reversed post order of nodes is constructed
in function `fillrpo`

and `rporec`

.

In general,
`fillrpo`

will call `rporec`

to give each node
an integer ID, which represents the order between nodes.
`rporec`

will run recursively(hence it has the suffix `rec`

)
to traverse nodes along the CFG.

Here I annotate the source code of `rporec`

to reveal the details:

static int
// `b`: Current node to be visited.
// `x`: Currently available ID can be assigned to a node.
// `x` runs decreasingly because
// we want all IDs are arranged in *reversed* post order.
rporec ( Blk * b , int x )
{
Blk * s1 , * s2 ;
// If current node is null, or
// we encounter a node which has been visited,
// we return current ID unchanged.
if ( ! b || b -> id >= 0 )
return x ;
// Otherwise we give current node a temporary positive ID,
// so that we will not visit it again.
b -> id = 1 ;
// `Blk::s1` is a link to the next block.
// `Blk::s2` is a link to the target block of jump instruction(if any).
s1 = b -> s1 ;
s2 = b -> s2 ;
if ( s1 && s2 && s1 -> loop > s2 -> loop ) {
s1 = b -> s2 ;
s2 = b -> s1 ;
}
// In the post order traversal,
// We first visit children of current node recursively.
// Note that the currently available ID
// is updated during the traversal.
x = rporec ( s1 , x );
x = rporec ( s2 , x );
// Finally we visit the current node,
// and assign it with the permanent ID.
b -> id = x ;
assert ( x >= 0 );
// The IDs run decreasingly for *reversed* post ordering.
return x - 1 ;
}

And in the `fillrpo`

:

void
fillrpo ( Fn * f )
{
int n ;
Blk * b , ** p ;
// Initialize all nodes' ID with -1
// to mark them unvisited.
for ( b = f -> start ; b ; b = b -> link )
b -> id = - 1 ;
// The entry point to the traversal.
// The initial available ID is `nblk - 1`.
// Note that when there are dangled nodes,
// the number of these dangled nodes is given by `n`.
n = 1 + rporec ( f -> start , f -> nblk - 1 );
// Remove all dangled nodes.
f -> nblk -= n ;
f -> rpo = alloc ( f -> nblk * sizeof f -> rpo [ 0 ]);
for ( p =& f -> start ; ( b =* p );) {
if ( b -> id == - 1 ) {
// Remove all dangled nodes.
blkdel ( b );
* p = b -> link ;
} else {
// Compact the range of ID to [0, nblk).
b -> id -= n ;
f -> rpo [ b -> id ] = b ;
p = & b -> link ;
}
}
}