Visiting a graph: BFS, DFS and reverse postorder

Three ways to walk the statements of a program, and why one of them hands every statement its input complete.

Where this shows up in reverse engineering

Before anything else can be asked about an unfamiliar program, something has to walk it. The order chosen is not incidental — it decides whether a later analysis finishes in one pass or many.

• "What does this paragraph reach?" — a reachability query from a single PERFORM, answered by exactly the depth-first walk this page builds, is how a corpus-wide tool finds every statement a change to one paragraph could possibly affect, without reading the rest of the program.
• The same question on the Java side. A call graph seeded from one entry point — a controller method, a batch job's main — and walked forward is how a tool finds everything a web action can call into, cheaply: 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 actually reachable, not the whole program.
• Reverse postorder specifically is what the next two pages, fixpoints and reaching definitions, need to converge in one pass instead of several — the difference that matters once a method's control-flow graph runs into the thousands of statements, not the handful on this page.

The problem

A program's statements form a graph: an arrow from each statement to every statement that can run next. An IF has two arrows out, one per arm. The statement after the IF has two arrows in. A loop has an arrow from the end of its body back to its test.

An analysis visits the statements one at a time, and at each one it needs to know what happened before it — on every arrow coming in. If it visits a statement before one of the statements that lead into it, it has to come back to it later, when that input arrives. So the order of visiting decides how much work is repeated. There are a few standard orders, and they have names.

The example

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, with the arrows written out. When a statement has two arrows out, the first one listed is the one a walk tries first.

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

A → B1, C     B1 → B2
B2 → B3       B3 → D
C → D         D → E

The statement to watch is D. It has two predecessors, B3 and C, and a good order visits both of them before it.

Breadth-first: nearest first

Breadth-first search (BFS) sorts statements by how many arrows it takes to reach them from the start, and visits the nearest first.

Some statements can be reached in more than one way. D is two arrows away through the else-arm (A → C → D) and four through the then-arm (A → B1 → B2 → B3 → D). BFS counts the shortest. It finds each statement once, the first time any path reaches it, and the shortest path always gets there first; when a longer path arrives later, the statement is already placed and the longer path is ignored. So D counts as two arrows away, and E, just after it, as three.

Grouped by that shortest count:

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)

BFS reads the groups top to bottom: A B1 C B2 D B3 E.

Look where D landed: in the 2-arrow group, placed by its short path. But its other predecessor, B3, is in the 3-arrow group, so BFS visits D before B3. An analysis walking in this order would work out D from the else-arm alone, then have to redo it when the then-arm's input arrives.

The trouble is that distance from the start says nothing about whether everything leading into a statement has been visited. A statement with a short path and a long path into it is reached by the short one first.

How BFS produces that order: it 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.

The statements were taken in the order A B1 C B2 D B3 E — the groups above, read top to bottom. 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 when it is first seen, which is by its shortest path: step 6 is the longer path to D showing up after D already has its place.

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:

• If that statement has an arrow DFS has not tried yet, to a statement it has not seen yet, follow it: the new statement joins the path.
• Otherwise, DFS is done with that statement: it leaves the path, and DFS backs up to the statement before it.

Every statement joins the path once and leaves it once. That gives two orders:

• Preorder: statements in the order they join the path.
• Postorder: statements in the order they leave it. A statement only leaves once everything it leads to has been dealt with.

"Not seen yet" means DFS has to remember what it has seen. The two lists are that memory. Everything in the preorder list has joined the path at some point, so it has been seen. Everything in the postorder list has also left. So when DFS looks at an arrow, its target is in one of three states:

• Not in preorder: never seen. DFS follows the arrow, and the target joins the path.
• In preorder but not in postorder: still on the path. Following the arrow would go round in a circle. This is the back edge of the loop section below.
• In postorder: already left. Everything reachable from it has been explored, so going there again would only repeat work. DFS skips it — as at step 13, where C skips D.

Watch both lists grow (amber: just written):

Preorder: A B1 B2 B3 D E C. That is no better than BFS: D comes before its predecessor C.

Postorder: E D B3 B2 B1 C A. Every statement comes after everything it leads to — backwards from what an analysis wants.

Reverse postorder

So turn postorder around. Reverse postorder: A C B1 B2 B3 D E.

Now D comes after both B3 and C, and E after D. Every statement comes after every statement that leads into it. An analysis walking in this order finds each statement's input complete the first time it gets there, so it never redoes anything.

Why it always works, in a graph without loops: take any arrow X → Y. X cannot leave the path before Y has left it. Either Y had already left when X tried the arrow — as D had when C tried C → D — or Y joins the path after X, and being further along the path, leaves first. Either way Y leaves first, so Y is earlier in postorder and X is earlier in reverse postorder. That holds for every arrow at once. In the example, C left second to last, just before A, so turning the list round puts it second — ahead of D, as the arrow C → D requires.

With a loop

A loop breaks the guarantee, because a loop's statements lead into each other in a circle: no order can put each of them after all its predecessors. 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.

That 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 asks of them. (Compiler textbooks also use "back edge" for a narrower idea built on dominators. Cobble does not use it, and nothing in these pages needs it.)

Postorder: X2 X1 L2 L1 T. Reverse postorder: T L1 L2 X1 X2.

Every arrow still points forward in this order except the back edge L2 → T. 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:

Postorder: L2 L1 X2 X1 T. Reverse postorder: T X1 X2 L1 L2. That is also valid — every arrow but the back edge still points forward — but it puts the code after the loop before the loop body. An analysis using it visits X1 and X2 before the loop has settled, and has to visit them again once it does. Which arrow DFS tries first decides which of the two orders you get.

In short

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. The search keeps its own stack rather than calling itself, because a real program's paths are thousands of statements long and Python allows a thousand nested calls.