Visiting a graph: BFS, DFS and reverse postorder

Read first: COBOL and CICS in 60 seconds, if the vocabulary is new

An analysis works out each statement from what arrives on every arrow into it. Visit a statement before one of the statements that lead into it, and its answer is built on part of its input: when the rest arrives, it has to be worked out again.

In the IF below, statement D has two arrows in: from B3, at the end of a three-statement then-arm, and from C, the whole else-arm. Breadth-first search visits D before B3, depth-first preorder visits it before C, and reverse postorder, A C B1 B2 B3 D E, visits it after both, so an analysis walking in that order works D out once.

A statement's predecessors are the statements with an arrow into it.

The example: where D lands

An IF whose then-arm is three statements long and whose else-arm is one, followed by a statement both arms lead into.

           IF WS-FLAG = 'Y'                  A
               MOVE 'YES ' TO WS-A           B1
               ADD 1 TO WS-N                 B2
               MOVE WS-N TO WS-M             B3
           ELSE
               MOVE 'NO  ' TO WS-A           C
           END-IF.
           MOVE WS-A TO WS-B.                D
           STOP RUN.                         E

As a graph: an arrow from each statement to every statement that can run next, so the IF has two arrows out, one per arm, and D, after it, has two arrows in. When a statement has two arrows out, the first one listed beside the picture is the one a walk tries first.

        A           A  → B1, C
       / \          B1 → B2
     B1   C         B2 → B3
      |   |         B3 → D
     B2   |         C  → D
      |   |         D  → E
     B3   |
       \ /
        D
        |
        E

The statement to watch is D, with its two predecessors B3 and C. Here is where each of the four orders this page builds puts it:

The first two rows fail the same way: D is reached while only one arm's input has arrived. The sections below build each row by walking the graph, then add a loop, where no order can put every statement after all its predecessors.

Breadth-first: nearest first

Breadth-first search (BFS) keeps a queue: a line of statements that have been found but not yet visited. It always takes the statement at the front of the line, and puts each newly found statement at the back. A statement it has seen before is not added again. Watch step 3, where D is found, and step 6, where it is found again.

The statements were taken in the order A B1 C B2 D B3 E, the first row of the table at the top. Grouped by how many arrows each is from A, along the path that first found it:

0 arrows:  A
1 arrow:   B1  C     A → B1
                     A → C
2 arrows:  B2  D     A → B1 → B2
                     A → C → D
                     (D's 4-arrow path ignored)
3 arrows:  B3  E     A → B1 → B2 → B3
                     A → C → D → E
                     (E's 5-arrow path ignored)

Read the groups top to bottom and you get the walk's order. That is not a coincidence. Everything found from a 1-arrow statement joins the back of the line behind every 1-arrow statement still waiting, so the whole 1-arrow group is taken before any of the 2-arrow group, and so on down. And a statement is placed by the first path that reaches it, the shortest: D is found at step 3 through A → C → D, and its four-arrow path arrives at step 6, too late.

So D sits in the 2-arrow group, ahead of its other predecessor B3. Distance from the start says nothing about whether everything leading into a statement has been visited.

Depth-first: as far as you can, then back up

Depth-first search (DFS) walks a single path from the start, making it as long as it can before trying anything else. It repeats one rule, always looking at the last statement on the path:

Every statement joins the path once and leaves it once, and DFS writes down both moments: preorder lists statements in the order they join, postorder in the order they leave. Watch both lists grow (amber: just written); the rule's "yes" applies at steps 2–6 and 12, its "no" at steps 7–11, 13 and 14:

The walk's last step holds both lists. Preorder, A B1 B2 B3 D E C, is no better than BFS: D comes before its predecessor C. Postorder, E D B3 B2 B1 C A, has every statement after everything it leads to, because a statement leaves only once everything it leads to has been dealt with (E leaves at step 7, before D at step 8). That is backwards from what an analysis wants.

The two lists are also how DFS remembers what it has seen. When it looks at an arrow, the target is in one of three states:

Reverse postorder

So turn postorder around:

Postorder, from the DFS walk

Reverse postorder

Now D comes after both B3 and C, and E after D: the last row of the table at the top. The table below checks every arrow of the graph against the DFS walk. For each arrow X → Y, Y left the path before X did, so Y is earlier in postorder and X is earlier in reverse postorder:

Those are the only two things that can happen when X tries an arrow in a graph without loops. Either Y joins the path after X and, being further along, leaves first (six rows), or Y has already left, as D had when C tried C → D (the amber row). Either way Y leaves first, for every arrow at once. C left at step 13, just before A, so turning the list round puts it second, ahead of D, as the arrow C → D requires.

Why D's place matters

An analysis needs, at each statement, what happened on every arrow coming in. In reverse postorder every arrow in the table above points forward, so each input is complete when first reached. In BFS order, D comes before B3 and is worked out twice. The visits, with the fixpoints page's worklist, which always takes the earliest pending statement in the order and requeues the successors of a statement whose result changed. The results are that page's notes, each field's possible last writers: D's grow when the second arm arrives, as the arms' writers differ (amber: a second visit):

BFS order — 8 visits

DFS preorder — 9 visits

Reverse postorder — 7 visits, one each

In the BFS row, E is still waiting when B3 requeues D, and D comes earlier in the order, so D is redone before E is first visited. In the preorder row E has already gone, so C's late arrival costs a second visit to both.

A loop is where that runs out. The end of a loop's body has an arrow back to the loop's test, so its statements lead into each other in a circle, and no order can put each of them after all its predecessors.

With a loop

Here is the loop from the fixpoints page:

           PERFORM LOOP-PARA UNTIL WS-N > 3.   T    (the loop's test)
           MOVE WS-B TO WS-C.                  X1
           STOP RUN.                           X2
       LOOP-PARA.
           MOVE WS-A TO WS-B.                  L1
           ADD 1 TO WS-N.                      L2

       T <---+
      / \    |
    X1   L1  |
     |    |  |
    X2   L2 -+

T → X1, L1    L1 → L2
L2 → T        X1 → X2

DFS from T, taking T's arrows in the order listed: X1 first. The rule is the same as before; step 8 is the new situation.

Step 8's label belongs to one run of DFS, not to the graph: try the arrows in another order and a different arrow of a loop can be the back edge. What every run guarantees is that each loop contains at least one, so a graph has a back edge exactly when it has a loop. That is the one thing cobble — the static-analysis tool these pages describe — asks of them here. (Compiler textbooks also use "back edge" for a narrower idea built on dominators: an arrow whose target dominates its source. The fixpoint pages do not need it; the loop-structure pages, starting with dominance and reachability, do.)

Postorder, from the walk's last step

Reverse postorder

Each arrow of the loop graph, with its two ends' positions in that reverse postorder:

Only the fourth row points backwards. That is the general result: in reverse postorder, the only arrows pointing backwards are the back edges that close loops. So the only redo an analysis needs is a trip round each loop.

One thing reverse postorder does not fix: where the code after the loop lands. Run DFS again, but take T's arrow to L1 first. This time the back edge turns up at step 4:

Postorder, from the walk's last step

Reverse postorder

That is also valid: every arrow but the back edge still points forward (L2 → T now runs from 5th to 1st). But it puts the code after the loop, in amber, before the loop body. Which arrow DFS tries first decides which of the two orders you get, and neither is wrong: the analysis reaches the same fixpoint either way. What differs is cost. Here are the visits each order produces when a worklist always takes the earliest pending statement in the order, on the analysis of the fixpoints page:

Order T L1 L2 X1 X2 — the fixpoints page's walk, 8 visits

Order T X1 X2 L1 L2 — same rule, 10 visits

In the first row the loop body is visited twice and settles before X1 and X2 are reached, so each is visited once. In the second, X1 and X2 are visited before the loop has gone round; when the back edge brings T new input, T's second visit queues them again, and they are visited a second time. (The second row is worked by hand with the fixpoints page's rule: T's notes grow on its second visit, so both its successors are queued, neither being pending; L2's second visit changes nothing, as at step 6 of that page's walk. It is the same count, 10, that page gives for a first-in-first-out worklist, which also visits X1 and X2 twice.)

Both rows assume a worklist that always takes the earliest pending statement. That is this page's model, and the fixpoints page's walk. Cobble's own worklist instead takes the first pending statement after the one just visited, wrapping round to the earliest (see fixpoints, In cobble). A plain sweep in either order, repeated until nothing changes, revisits everything on every pass.

In short

Where this shows up

• "What does this paragraph reach?" The DFS walk above, started at one PERFORM instead of at A, is how a corpus-wide tool finds every statement a change to one paragraph could affect, without reading the rest of the program.
• The same question in Java. A call graph seeded from one entry point and walked forward finds everything a web action can call into: on one real codebase, seeding from a single root cut call-graph construction from minutes to under two seconds, because the cost tracks what is reachable, not the whole program.
• Reverse postorder is what fixpoints and reaching definitions need: one visit each on loop-free code, as in the 7-visit row for the IF, and an extra trip per loop, as in the 8-visit row for the loop. That matters once a method runs to thousands of statements.

In cobble

Cobble's fixpoint stage orders its walks by this depth-first search, its reverse postorder and its back edges. It tries a statement's arrows in the order the control-flow graph lists them, and handles an arrow's target by the three states in the table under the DFS walk. From depth_first_order in cobble/dataflow/srccfg/order.py:

edge = next(remaining, None)
if edge is None:                 # nothing left: leaves
    stack.pop()
    on_path.discard(node_id)
    finished.add(node_id)
    postorder.append(node_id)
elif edge.target in on_path:     # still on the path
    back.add(edge)
elif edge.target not in finished:  # never seen: joins
    on_path.add(edge.target)
    stack.append(...)

(Abridged: the loop around it is left out, comments are added and the last call is shortened.) A target already in finished falls through all three branches and is skipped, as D is at step 13 of the DFS walk. The search keeps its own stack rather than calling itself, because the corpus's larger programs reach thousands of statements and Python allows a thousand nested calls.