Fixpoints and worklists

Read first: Visiting a graph

A loop sends what its body writes back to statements an analysis has already visited. Walk the program once, top to bottom, and those writes are silently missing: the answer is not loose but incomplete, and every later stage trusts it as final.

In this page's program, MOVE WS-B TO WS-C reads a WS-B that only the loop body writes. One pass says nothing in the program wrote it. Going round until nothing changes, the fixpoint, says MOVE WS-A TO WS-B, or nothing since the program began. A worklist gets there in 8 visits by revisiting a statement only when something before it changed.

A statement's notes say, for each field, which statements may have last written it.

The example

Each box is a statement of FIXLOOP, named the way cobble names them (paragraph, then position). The dashed back edge is the loop going round.

flowchart TD
    E(["entry: every field = start"]) --> M0["MAIN-PARA/0: PERFORM LOOP-PARA UNTIL WS-N > 3"]
    M0 -->|"WS-N not > 3"| L0["LOOP-PARA/0: MOVE WS-A TO WS-B"]
    L0 --> L1["LOOP-PARA/1: ADD 1 TO WS-N"]
    L1 -.->|back edge| M0
    M0 -->|"WS-N > 3"| M1["MAIN-PARA/1: MOVE WS-B TO WS-C"]
    M1 --> M2["MAIN-PARA/2: STOP RUN"]

The answer at MAIN-PARA/1, the read after the loop: these statements may have last written WS-B.

start, the entry box, stands for the value a field holds on entry: for WS-A its VALUE 'AAAA', for WS-B whatever its storage held. It is a teaching device; cobble has no such definition (see in cobble). Stop after one trip down the graph and both reads of a field written in the loop come out short:

Each left-hand note misses the write that comes round the back edge. Row 1 is the worse: it says WS-C is copied from a WS-B nothing in the program has written. The 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.

       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.

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:

In the graph above, every box comes after the box its solid arrow comes from, and only the dashed back edge runs the other way. 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. Watch step 3: the list holds MAIN-PARA/1 and MAIN-PARA/0, and MAIN-PARA/0 goes first because it is earlier in that order.

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. In the table, the first-in-first-out column takes MAIN-PARA/1 at visit 2 and MAIN-PARA/2 at visit 4, before the body has gone round once, and has to redo them at visits 7 and 9. The reverse-postorder column is steps 1–8 of the walk.

Why go round again

Steps 1–3 are the walk you would do by hand: go down the graph keeping notes. A MOVE replaces its target's note with itself, so after step 2 WS-B's note is just LOOP-PARA/0. The PERFORM … UNTIL may go either way, so both are walked; where paths meet, everything either path noted is kept.

Then the back edge carries step 3's notes to MAIN-PARA/0, whose notes from step 1 held only start: they were incomplete. Step 4 goes round again, and steps 5 and 6 carry the new notes through the body until step 6 changes nothing: the loop has settled.

Re-walking the whole program each time would be wasteful, since a statement's notes change only if something before it changed. So the chips under each step are a worklist: take a statement off, work out its notes from its predecessors', and queue its successors only if its notes changed. When the list runs dry, at step 8, nothing can change any more: that is the fixpoint.

It always stops: notes only grow, and only so many statements can appear in them. Here no note can ever hold more than this:

WS-B's note after MAIN-PARA/0 goes from {start} in step 1 to its row of that table in step 4, and can go no further. And the order statements come off the list changes how much work is done, not what is found: the two runs compared above, 8 visits and 10, end with the same notes.

The question it answers

At every statement, 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 the walk reasons about it instead. That is why step 7 keeps start for WS-B: the analysis does not track that WS-N starts at 0, so it allows for the path that skips the loop altogether:

Where this shows up

This is the loop 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 refines it.

• Self-referential fields. Decades of maintenance pile up running totals updated from themselves and flags a loop both reads and sets, like WS-N here, which reads the value it wrote on the previous trip. Those are the cases a one-pass analysis gets wrong first.

  LOOP-PARA.
      MOVE WS-A TO WS-B.
      ADD 1 TO WS-N.

• The same shape on the Java side. Resolving every virtual call's possible targets is a worklist that drains once nothing new turns up: each newly reachable method can create objects of new types, which add targets to virtual calls already visited.

The rule

Step 4 of the walk is the first line at work. MAIN-PARA/0 has two arrows into it in the graph: the entry brings start for every field, and the back edge brings step 3's notes, the middle column. Adding start to each row gives step 4's table, the right-hand column:

PERFORM … UNTIL writes nothing, so its out is that in. The second line is step 5: LOOP-PARA/0's transfer replaces WS-B with itself and passes WS-N {LOOP-PARA/1, start} through unchanged. The third line decides the chips: step 5's notes grew, so LOOP-PARA/1 was queued; step 6's did not, so nothing was.

Two properties make this terminate with one answer. Each transfer is monotone: more knowledge in never means less out. In step 4, MAIN-PARA/0 got more in than in step 1, and its notes went from {start} to {LOOP-PARA/0, start} for WS-B, a superset. And there are only finitely many notes: each field can be credited to at most every write in the program, as in the bound table above. 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. Counting the two runs compared above by statement, the whole difference is the two statements after the loop:

  statement	visits, first in first out	visits, reverse postorder
  MAIN-PARA/0	2	2
  LOOP-PARA/0	2	2
  LOOP-PARA/1	2	2
  MAIN-PARA/1	2	1
  MAIN-PARA/2	2	1
  total	10	8

  Both runs end with the notes of step 8: WS-B {LOOP-PARA/0, start}, WS-C {MAIN-PARA/1}, WS-N {LOOP-PARA/1, start}. 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. Cut the walk off after 4 visits — after step 4 — and the notes for WS-N stand like this:

  notes after	WS-N, stopped after step 4	WS-N at the fixpoint
  MAIN-PARA/0	{LOOP-PARA/1, start}	{LOOP-PARA/1, start}
  LOOP-PARA/0	{start}	{LOOP-PARA/1, start}
  LOOP-PARA/1	{LOOP-PARA/1}	{LOOP-PARA/1}
  MAIN-PARA/1	not visited	{LOOP-PARA/1, start}
  MAIN-PARA/2	not visited	{LOOP-PARA/1, start}

  The amber cells are short, not wrong: every entry in the middle column also appears in the right one. Cobble publishes such a result and marks it unsettled.

• Non-monotone rules break everything. If a transfer could shrink a fact, re-walking could oscillate forever, and a worklist could empty on an answer that is not a fixpoint at all.

  A concrete example: suppose that, to keep notes short, the loop test MAIN-PARA/0 used the rule "when a definition of a field arrives that is not already noted, drop the ones already noted — keep only the newest". This is not monotone: in step 4, more arrives than in step 1, yet start is lost. Follow WS-B there, re-walking the whole program in reverse postorder each round:

  round	arriving at MAIN-PARA/0	kept, newest only
  1	{start}	{start}
  2	{LOOP-PARA/0, start}	{LOOP-PARA/0}
  3	{LOOP-PARA/0, start}	{start}
  4	{LOOP-PARA/0, start}	{LOOP-PARA/0}

  In round 1 the body has not run yet, so only start arrives. In round 2, LOOP-PARA/0 is the newcomer, so start is dropped. In round 3, start arrives again from the entry and is now the newcomer, so LOOP-PARA/0 is dropped. The right-hand column alternates for ever, and no round ever changes nothing. The union rule, given the same middle column, keeps {LOOP-PARA/0, start} from round 2 on, and round 3 confirms it.

  The worklist does worse: it stops. Run the walk above under the newest-only rule and steps 1–6 visit the same statements; step 4 now leaves {LOOP-PARA/0} for WS-B and {LOOP-PARA/1} for WS-N. Step 6's LOOP-PARA/1 still ends with the same notes as in step 3, so nothing re-queues MAIN-PARA/0, and the list empties after 8 visits (first in, first out also stops there, after 10). Step 7's notes, under each rule: the newest-only run has dropped start, the path that skips the loop, which the analysis must allow for (see the question it answers).

  notes after MAIN-PARA/1	newest-only worklist	the walk's step 7
  WS-B	{LOOP-PARA/0}	{LOOP-PARA/0, start}
  WS-N	{LOOP-PARA/1}	{LOOP-PARA/1, start}

  The empty list looks like a fixpoint and is not: visiting MAIN-PARA/0 once more would flip its note back to {start}. The worklist only skips a statement safely when its result depends on nothing but what arrives and never shrinks as more arrives; the newest-only rule breaks both.

In cobble

The fixpoint stage (cobble-dataflow-fixpoint) runs this worklist over each member, queued in reverse postorder. Rather than always the earliest queued statement, as in the walk above, it takes the first queued statement after the one just visited, wrapping round to the earliest, so that changes coming back round a loop are carried together in one pass. Cobble's notes are kept per byte range rather than whole fields — see byte extents — but the loop is this one. Cobble has no start: a path on which nothing wrote the bytes adds no definer, and shows up instead in the field's values, as its VALUE clause or, without one, the reason uninitialised (see value sets). Run on this page's program, it reports these definers for the two reads in the one-pass table; its --sweeps 1 option makes one reverse-postorder pass instead of the worklist:

Cobble names the reads WS-B@working_storage[4:8] and WS-N@working_storage[12:14]. Where this page writes start, cobble gives a starting value instead, in both runs: the reason uninitialised for WS-B, which has no VALUE clause, and the image 00 of WS-N's VALUE 0. Read that way, the worklist column is the one-pass table's fixpoint column and the --sweeps 1 column is its one-pass column; cobble marks the one-pass run unsettled.