Fixpoints and worklists

How a program analysis handles loops: keep applying the rules until nothing changes.

Where this shows up in reverse engineering

This is the central technique a static dataflow tool for a legacy corpus is built on: a byte-level fixpoint over every field, run once per program, that answers which writes reach each read and what values a field can hold — everything else in this series of pages is a refinement of that one loop.

• A paragraph that PERFORMs itself, or a field whose value loops back into its own computation, needs the worklist to revisit it until nothing changes. Stopping after one pass over such a program does not produce an approximate answer — it produces a specific wrong one, silently, on exactly the programs with enough real control flow to be worth analysing in the first place.
• The same shape appears on the Java side in call-graph construction: resolving every virtual call's possible targets is itself a worklist that "drains" once nothing new is discovered, for the same reason — a class hierarchy with its own cycles of interface implementations needs the same keep-going-until-stable discipline, not a single top-to-bottom pass.
• Why it has to be a fixpoint and not a cache: a legacy program's fields are exactly the place self-referential logic accumulates over decades of maintenance — a running total updated from itself, a flag a loop both reads and sets. Those are the cases a one-pass analysis gets wrong first.

The problem

You want to know, at every statement in a program, which statements may have last written each field — not on one run, but on any run, whatever the input data. You cannot run the program on every input, so you reason about it instead.

The intuition

Start the way you would by hand: walk the program from the top, keeping notes at each statement on which statements may have last written each field. A MOVE into a field replaces that field's note with itself. At an IF, walk both arms, because you do not know which one will run; where the arms meet, keep everything either arm noted.

That works until you reach a loop. The first time you arrive at the loop's test, the only thing that reaches it is what came from before the loop. Then you walk the body, and by the end of the body you know something new — say, a field was just written inside it. That flows back to the test, so the test's notes were incomplete. You have to go round again with the new information, and again, until a trip round the loop adds nothing. That end state, where one more trip would change nothing, is the fixpoint.

Re-walking the whole program each time is wasteful: a statement's notes can only change if something before it changed. So keep a list of the statements that need visiting — the worklist. It starts with the first statement. Take a statement off the list and work out its notes from what its predecessors have noted so far. If its notes changed, everything after it may change too, so put its successors on the list. If they did not change, add nothing. When the list runs dry, no statement's notes can change any more: you are at the fixpoint.

Two things make this trustworthy. It always stops, because notes only ever grow and there are only so many statements that could appear in them. And it reaches the same notes whatever order you take statements off the list: order changes how much work you do, not what you find.

The example

A loop whose body copies WS-A into WS-B, and a read of WS-B after the loop.

       IDENTIFICATION DIVISION.
       PROGRAM-ID. FIXLOOP.
       DATA DIVISION.
       WORKING-STORAGE SECTION.
       01  WS-A                 PIC X(4) VALUE 'AAAA'.
       01  WS-B                 PIC X(4).
       01  WS-C                 PIC X(4).
       01  WS-N                 PIC 9(2) VALUE 0.
       PROCEDURE DIVISION.
       MAIN-PARA.
           PERFORM LOOP-PARA UNTIL WS-N > 3.
           MOVE WS-B TO WS-C.
           STOP RUN.
       LOOP-PARA.
           MOVE WS-A TO WS-B.
           ADD 1 TO WS-N.

The notes here are, for each field, the set of statements that may have last written it. start stands for the value the field holds on entry. The statements are named the way cobble names them: paragraph, then position.

Step by step

When the worklist holds more than one statement, something has to pick which goes next. This run picks the one that comes earliest in reverse postorder — an order in which every statement comes after the statements that lead into it, except where a loop leads back to its own test. Visiting a graph builds it step by step. For this program it is MAIN-PARA/0, LOOP-PARA/0, LOOP-PARA/1, MAIN-PARA/1, MAIN-PARA/2: the loop body comes before the code after the loop, so the loop settles before that code is visited.

Each step shows the notes after the visited statement (amber: what changed) and the worklist after it.

A first-in-first-out worklist reaches exactly the same notes, but leaves the loop before it has settled, so it visits MAIN-PARA/1 and MAIN-PARA/2 twice: 10 visits instead of 8.

The rule

Two properties make this terminate with one answer. Each transfer is monotone: more knowledge in never means less out. And there are only finitely many notes: each field can be credited to at most every write in the program. Every change makes some set strictly bigger, so changes run out.

What goes wrong

• Order is cost. First-in-first-out wanders out of the loop before the loop has settled, then has to redo everything after it once the loop changes. Reverse postorder, with the loop body ahead of the code after the loop, finishes the loop first. On cobble's largest program, changing order alone cut statement visits from about 107,000 to about 20,000, with an identical answer.
• Budgets. A big program with many nested loops can still need a lot of visits, so a real analysis caps them. Stopping early gives notes that are missing some writes, never ones that are wrong: everything recorded was reached by a real path. Cobble publishes such a result and marks it unsettled.
• Non-monotone rules break everything. If a transfer could shrink a fact, the loop could oscillate forever, and different orders could stop at different answers.

In cobble

The fixpoint stage (cobble-dataflow-fixpoint) runs this worklist over each member, queued in reverse postorder. Cobble's notes are kept per byte range rather than whole fields — see byte extents — but the loop is this one.