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:

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.
            *p = b->link;
        } else {
            // Compact the range of ID to [0, nblk).
            b->id -= n;
            f->rpo[b->id] = b;
            p = &b->link;