Sweeps: a fixpoint with a budget that says when it ran out

Read first: Visiting a graph, Fixpoints and worklists

A whole-corpus fixpoint is as slow as its slowest program: on a corpus of about 3,800 programs, the last three programs took 1,404 s, 2,324 s and 4,434 s. The default worklist cannot say how far along a program is, and capping it is only safe if a capped program says so instead of quietly returning less.

PROGA's loop writes WS-NEXT; a LINK after the loop reads it. A budget of 10 sweeps over its 13 nodes caps the walk at 130 visits before it starts; it finds both targets on sweep 2 and proves them on sweep 3. Stopped after one sweep, the LINK gets only PROGB, marked incomplete-walk.

A sweep is one pass over the graph in reverse postorder; the walk it replaces is the worklist from fixpoints and worklists.

The example

Cobble's control-flow graph for PROGA has 13 reachable nodes, numbered by their place in the sweep order. The dashed, highlighted edge is the one back edge.

flowchart TD
    L["MAIN-PARA#35;label · 1"] --> T["MAIN-PARA/0#35;loop#35;test · 2"]
    T -->|FALSE| M0["MAIN-PARA/0 PERFORM · 9"]
    T -->|TRUE| M1["MAIN-PARA/1 LINK · 3"]
    M0 --> PL["PICK-PARA#35;label · 10"]
    PL --> P0["PICK-PARA/0 MOVE 'PROGC' · 11"]
    P0 --> P1["PICK-PARA/1 ADD · 12"]
    P1 --> PE["PICK-PARA#35;end · 13"]
    PE -.->|back edge| T
    M1 --> M1r["MAIN-PARA/1#35;raise · 4"]
    M1r -->|TRUE| M1d["MAIN-PARA/1#35;dispatch · 8"]
    M1r -->|FALSE| M2["MAIN-PARA/2 RETURN · 5"]
    M2 --> M2r["MAIN-PARA/2#35;raise · 6"]
    M2r -->|TRUE| M2d["MAIN-PARA/2#35;dispatch · 7"]
    linkStyle 7 stroke:#f5b041,stroke-width:3px

The answer: the LINK's targets under each budget of sweeps, as cobble reports them. Three sweeps or more settle it, and the mark comes off.

The lines that matter:

05  WS-NEXT  PIC X(8) VALUE 'PROGB'.
05  WS-I     PIC 9(2) VALUE 0.
PERFORM PICK-PARA UNTIL WS-I > 3.
EXEC CICS LINK PROGRAM(WS-NEXT) END-EXEC.
PICK-PARA.
    MOVE 'PROGC' TO WS-NEXT.
    ADD 1 TO WS-I.

       IDENTIFICATION DIVISION.
       PROGRAM-ID. PROGA.
       DATA DIVISION.
       WORKING-STORAGE SECTION.
       01  WS-REC.
           05  WS-NEXT          PIC X(8) VALUE 'PROGB'.
           05  WS-I             PIC 9(2) VALUE 0.
       PROCEDURE DIVISION.
       MAIN-PARA.
           PERFORM PICK-PARA UNTIL WS-I > 3.
           EXEC CICS LINK PROGRAM(WS-NEXT) END-EXEC.
           EXEC CICS RETURN END-EXEC.
       PICK-PARA.
           MOVE 'PROGC' TO WS-NEXT.
           ADD 1 TO WS-I.

Besides one node per statement, the graph has a label at the start of each paragraph, a separate node for the loop's test, and for each EXEC CICS a #raise node (did the command raise a handled condition?) and a #dispatch node (where a handler would take it). The test's FALSE arm goes to the PERFORM (MAIN-PARA/0) and into PICK-PARA; its TRUE arm goes to the LINK (MAIN-PARA/1).

The reverse postorder cobble computes for it — the numbers in the graph — from depth-first search taking the test's FALSE arm first:

In the chips, the code after the loop (chips 3 to 8) comes ahead of the body (chips 9 to 13). The loop on the traversal page put the body first, because its search took the body's arm first. Either way the test, chip 2, comes before both, and that is what decides how many sweeps the loop needs.

The tables in the walk below show, for each node in the graph, the values WS-NEXT can hold on entry. PROGB is the VALUE clause; PROGC is written by PICK-PARA/0, node 11. WS-I is tracked too, and "settled" needs its states to stop changing as well. ADD 1 TO WS-I (node 12) is not a literal, so it is not evaluated: the write gives WS-I no values, only the reason not-a-literal (see the reasons taxonomy). Joined with the VALUE at the test, that is {00} plus not-a-literal after the first trip round the loop, and it does not grow after that; the sweeps do not count the loop to 4.

Step by step

The same program under each budget, as cobble reports it. "Visits" is sweeps times the 13 reachable nodes for a sweep walk, and dequeues for the worklist.

On a program this small the worklist does fewer visits: 24 in the last row against 39 in the two settled sweep rows. What the sweep buys is the bound: a budget of N costs at most N × 13 visits here, known before the walk starts, and its progress is a fraction of a known whole — the "sweep 2 of 10" in the log lines under why sweeps can stop early, rather than the queue lengths in the table under why not the worklist's budget.

With --call-targets-only, the liveness walk finds that only WS-NEXT matters, as in the byte strips under why sweeps can stop early: it is the LINK's operand, and WS-I feeds only the loop test. Cobble's log for the member reads 1 of 2 extents tracked: 2 written ranges, of which 1 is relevant. The table compares the two runs:

The worklist's first 13 dequeues are the same in both columns. At dequeue 14 the whole-program run re-queues the PERFORM and the LINK, whose entries both grew (WS-NEXT gained PROGC, WS-I gained not-a-literal), and goes round the body again; with only live bytes carried, the PERFORM is not among the live-node chips, so its entry is empty both times and does not grow, so only the LINK is re-queued and the walk ends at dequeue 15. The sweep walk, in row 2, still visits 13 nodes per sweep and settles on sweep 3, but each visit carries only WS-NEXT. The LINK's candidates, in row 4, are the same either way.

Why sweeps can stop early

One sweep visits every node the entry reaches, once, in reverse postorder. At each node it applies the statement to the node's entry state and pushes the result into each successor's entry state, joining it with whatever is there. Each step of the walk is one sweep.

A loop needs a second sweep. Steps 1 and 2 of the walk, cut down to the four nodes of the loop that matter, in the order a sweep visits them:

The test comes before the body in reverse postorder, because the test is how the body is reached. In step 1 the LINK in row 2 sees only what was true before the loop ran: the write in row 3 reaches the test only at row 4, along the back edge, after the test has had its visit. In step 2 the test starts with the body's write in its state and hands it on. A value has to go round a back edge once before it reaches the code after the loop. That is why two sweeps is the useful floor.

A forward chain is carried in one sweep, however long. Reverse postorder puts every node after all the nodes that lead into it, except along back edges. Take PROGX, a chain of copies through two PERFORMs (its four fields are PIC X(4)):

       MAIN-PARA.
           MOVE 'X' TO WS-A.
           PERFORM P1.
           MOVE WS-C TO WS-D.
           GOBACK.
       P1.
           MOVE WS-A TO WS-B.
           PERFORM P2.
       P2.
           MOVE WS-B TO WS-C.

Cobble's reverse postorder for it, 12 nodes

Each read and the definer the first sweep found for it

Every definer sits earlier in the chips row than its read, so the first sweep has already pushed its write forward by the time it visits the read. This graph has no back edge, so cobble runs one sweep and calls the member settled — its log line is PROGX sweep 1 of 10 done, 12 nodes reached, settled.

A sweep that changes nothing proves the fixpoint. Step 3 of the walk is that sweep: it leaves every entry state as it was, so the next would too, and the answer is exactly the worklist's. The member is settled. If the budget runs out while states are still growing, it is unsettled. Cobble logs which one each sweep was:

PROGA sweep 1 of 10 done, 13 nodes reached, still growing
PROGA sweep 2 of 10 done, 13 nodes reached, still growing
PROGA sweep 3 of 10 done, 13 nodes reached, settled

Sweep 2 already had the whole answer, but only the third line, the sweep that changed nothing, proves it.

Unsettled means missing, never wrong. Every transfer and the join are monotone (see the rule), so a state stopped early is a subset of the fixpoint's. Step 1's table against step 3's:

Every value in the middle column is also in the right-hand one, so every flow read off an early state is real; what may be absent is a value that needed more sweeps, like PROGC in row 1. Cobble says so: every dynamic call target and every jump in an unsettled member carries the reason incomplete-walk, as in step 1's target row (see the reasons taxonomy for the full list of reason codes), and the run's summary counts and names the member as unsettled. A walk in the combine that passes through that member's jump facts carries incomplete-walk on into the targets it feeds in other programs.

Carry less on each sweep. With --call-targets-only, cobble first runs a backward liveness walk over each program. The two strips below are the example's WS-REC, 10 bytes, with its starting values; outlined bytes are the ones liveness keeps.

Bytes [0, 8): WS-NEXT

Bytes [8, 10): WS-I

Liveness starts from the bytes the answer needs: each dynamic call target's operand, each area handed to another program (only the bytes some program reads, with --narrow-areas), and the LINKAGE areas read at an exit or a CICS RETURN. Working backward, a byte is live on entry to a node if some later node needs it and nothing in between certainly overwrites it; a write into a live byte makes its source bytes live. In the example the only such byte range is the LINK's operand, WS-NEXT's bytes [0, 8).

Nodes where bytes [0, 8) are live on entry (bytes [8, 10) are live at none)

The LINK at MAIN-PARA/1 reads bytes [0, 8), so they are live there and, going backward, at the test and the entry. PICK-PARA/0 certainly overwrites them, so they are live again only after it, at the last two chips; nothing after the LINK reads them. The forward walk drops every state entry that overlaps nothing live where it is handed: WS-I is carried nowhere, WS-NEXT only to those five nodes (the comparison table after the walk).

Why not the worklist's budget

Cobble's default walk is the worklist from fixpoints and worklists. Its budget is --iteration-factor: that many dequeues per CFG node (150 by default), after which it publishes what it has, unsettled. The example's graph has 14 nodes (MAIN-PARA#end unreachable): a cap of 150 × 14 = 2,100 dequeues; it finishes in 24. On the large corpus the worklist finished every program, but the run spent over an hour waiting on one.

A worklist is also hard to watch. Its queue on the example, after each of its 24 dequeues, as cobble runs it:

Nothing in it counts down. After dequeue 13 the queue holds one node, exactly as after dequeues 8 to 12, and yet 11 more follow; after dequeue 23 it holds one again, and only one follows. A progress line can only estimate from how fast the queue drains. The sweep walk's cost is known before it starts, it still gives the exact answer when it has time to, and it marks its results, like the LINK's row in step 1, when it does not:

Both caps are known up front, but only the second says how far along the walk is: after sweep 2 it is 26 visits into at most 130, and its log line says sweep 2 of 10.

Where this shows up

When the goal is one answer — which programs each CALL WS-PGM or EXEC CICS XCTL/LINK PROGRAM(WS-...) can reach — a few tangled programs should not hold the rest back, nor quietly return less than they found.

• Dynamic call targets across a large CICS corpus. On the corpus of about 3,800 programs, the per-program fixpoint decided how long the pipeline took. Most programs settled in seconds. A handful took most of the run.
• A budget a reviewer can read. A call target that comes back with incomplete-walk means "these programs at least, maybe more": a list of call sites to check by hand, not a silent gap. Cobble's targets.jsonl rows for the example's LINK, at one sweep and at three:

--sweeps 1:
{"caller": "PROGA", "node": "MAIN-PARA/1",
 "transfer": "CICS_LINK", "expression": "WS-NEXT",
 "candidates": ["PROGB"],
 "reasons": ["incomplete-walk"], "dropped": []}
--sweeps 3:
{"caller": "PROGA", "node": "MAIN-PARA/1",
 "transfer": "CICS_LINK", "expression": "WS-NEXT",
 "candidates": ["PROGB", "PROGC"],
 "reasons": [], "dropped": []}

The first row's "reasons": ["incomplete-walk"] is what tells a reviewer that "candidates": ["PROGB"] may be short, and the second row adds PROGC. Any whole-program analysis run under a time limit makes the same trade: let every program finish, or cap the work and mark what the cap touched. The marking is what makes the cap safe to use.

The rule

Each line is a step of the walk above. order is the 13-node chips row. The in(s) ⊔ … line is sweep 1's last visit, where PICK-PARA#end joins {PROGC} into the test's {PROGB}. "Changes no in(n)" is sweep 3, whose table matches sweep 2's. The unsettled ⇒ line is the budget-1 and budget-2 chips with incomplete-walk; "no back edge" is the chain program in why sweeps can stop early. keep_s under --call-targets-only is the five live-node chips.

A value written in a loop body reaches a reader after the loop on sweep 2, as the LINK's row in the walk does. Each further step it has to take backward against the order — around another back edge, or to a copy earlier in the same body, as in the second item below — costs one more sweep. Proving the result costs one more sweep than finding it, except on a graph with no back edge, where the first sweep is the fixpoint. Every program on this page, as cobble ran it:

The last two columns always differ by one where there is a back edge. The first column can run ahead of them, as in row 4, which the third item below explains.

What goes wrong

• Finding is not proving. In the example, two sweeps found every candidate, but the walk only knows that after a third sweep changes nothing. In the budget table's rows:

  walk	LINK candidates	reasons
  --sweeps 2	PROGB, PROGC	incomplete-walk
  --sweeps 3	PROGB, PROGC	none

  The candidates are identical, and row 1 still carries incomplete-walk. Two is the floor for finding a loop's write after the loop, not for settling it.
• Some loops need more. If the body copies the other way round, the value has to go round the back edge twice to reach the LINK. In this variant WS-CODE has a VALUE of its own:

             05  WS-CODE          PIC X(8) VALUE 'PROGD'.
        ...
         PICK-PARA.
             MOVE WS-CODE TO WS-NEXT.
             MOVE 'PROGC' TO WS-CODE.
             ADD 1 TO WS-I.

  budget	LINK candidates	settled
  --sweeps 1	PROGB	no
  --sweeps 2	PROGB, PROGD	no
  --sweeps 3	PROGB, PROGC, PROGD	no
  --sweeps 4	PROGB, PROGC, PROGD	yes

  On sweep 1 the body copies WS-CODE's PROGD into WS-NEXT and only then writes PROGC into WS-CODE; both reach the test along the back edge. Sweep 2 carries PROGD to the LINK, and copies the PROGC now in WS-CODE into WS-NEXT, which goes round the back edge a second time. Sweep 3 carries it to the LINK, and sweep 4 changes nothing. The LINK gains one candidate on sweep 2 and another on sweep 3, and the walk settles on sweep 4.
• Back edges without a loop. Cobble's graph has one copy of each paragraph, so a paragraph PERFORMed from two places returns to both: the second PERFORM becomes a back edge. A paragraph that falls through into one that was PERFORMed earlier does the same. This program has no loop in its source:

         MAIN-PARA.
             PERFORM SET-PARA.
             PERFORM SET-PARA.
             EXEC CICS LINK PROGRAM(WS-NEXT) END-EXEC.
             EXEC CICS RETURN END-EXEC.
         SET-PARA.
             MOVE 'PROGC' TO WS-NEXT.

  flowchart TD
      A["MAIN-PARA/0 first PERFORM"] --> S["SET-PARA#35;label"]
      S --> W["SET-PARA/0 MOVE 'PROGC'"]
      W --> E["SET-PARA#35;end"]
      E -->|RETURN| B["MAIN-PARA/1 second PERFORM"]
      E -->|RETURN| K["MAIN-PARA/2 LINK"]
      B -.->|back edge| S
      linkStyle 5 stroke:#f5b041,stroke-width:3px
  

  The graph shows the nodes around SET-PARA, leaving out the entry and the #raise and #dispatch nodes. In it, SET-PARA#end returns to both PERFORMs, and the second one's edge back into SET-PARA#label is the highlighted back edge. Sweep 1 gives the LINK {PROGC}, which is already the whole answer, and the back edge pushes {PROGC} into SET-PARA#label, which held only {PROGB}. Sweep 2 carries that grown state on into SET-PARA/0's entry, a change, though the write overwrites it. Sweep 3 changes nothing. So the program found every definition on sweep 1 and was settled on sweep 3.
• The mark is per program, not per site. An unsettled program marks every dynamic target and every jump with incomplete-walk, including ones whose values stopped changing several sweeps earlier. The walk does not track which sites were still growing. Put a second LINK ahead of the loop, EXEC CICS LINK PROGRAM(WS-FIRST) with WS-FIRST given VALUE 'PROGD' and never written, and run it with --sweeps 2:

  site	candidates	reasons
  LINK PROGRAM(WS-FIRST)	PROGD	incomplete-walk
  LINK PROGRAM(WS-NEXT)	PROGB, PROGC	incomplete-walk

  Row 1 had its whole answer from sweep 1 and nothing in the loop can change it, but it carries the mark because the member as a whole did not settle in two sweeps. With --sweeps 3 both rows lose it.
• Missing is still missing. No value in an unsettled result is invented, but a missing candidate is a missing edge in the call graph. Read the --sweeps 1 row under where this shows up without its reasons and the call graph is:

  flowchart LR
      A["PROGA"] -->|LINK| B["PROGB"]
      A -.->|"missing at --sweeps 1"| C["PROGC"]
  

  The dashed edge is the one the settled walk finds. The incomplete-walk reason on the row is the only thing that says it may be there. A consumer that reads candidates and ignores reasons will treat a partial answer as complete.
• A sweep is not cheaper per visit count. It visits every reachable node every sweep, including nodes nothing has changed for. In the budget table, the settled sweep rows do 39 visits to the worklist's 24: sweep 3 revisits all 13 nodes just to confirm, where the worklist's queue (under why not the worklist's budget) empties after re-taking only 11. On a small or simple program it can do more visits than the worklist. Its use is the bound.
• Call-targets-only narrows the output too. The dynamic targets and jumps are the same as a full run's, but graph.jsonl and defs.jsonl keep only rows for writes that are live afterwards, and the field query refuses that output directory. For the example:

  file	whole program	--call-targets-only
  graph.jsonl edges	LITERAL → WS-NEXT at PICK-PARA/0; WS-I → WS-I at PICK-PARA/1	LITERAL → WS-NEXT at PICK-PARA/0
  defs.jsonl rows	WS-I@working_storage[8:10] at PICK-PARA/1	none

  The WS-I rows are gone because bytes [8, 10) were live nowhere. Liveness also starts from what the jumps and targets read; anything else asked of the same run later is not there.

In cobble

The fixpoint (cobble-dataflow-fixpoint) runs the worklist by default, capped at --iteration-factor × nodes dequeues (default 150) — the 2,100 for the example under why not the worklist's budget. --sweeps N runs reverse-postorder sweeps instead, until one changes nothing or N are spent. The two flags cannot be combined, and --sweeps 0 is rejected:

cobble-dataflow-fixpoint: error: argument --iteration-factor: not allowed with argument --sweeps
cobble-dataflow-fixpoint: error: argument --sweeps: needs at least one sweep, got 0

A member with no back edge is settled after one sweep, as the chain program's log line in why sweeps can stop early shows. For each member the log says settled in N sweeps or NOT SETTLED after N sweeps; the closing warning names every unsettled member, and the summary counts them under unsettled. For the example with --sweeps 2:

PROGA 2/3 writes covered, 1 unhandled, 0 unmodelled, 2 edges, 2 of 2 extents tracked, 0.0s, NOT SETTLED after 2 sweeps -- edges are a subset
...
!! 1 members still growing when their walk's budget ran out (PROGA); their edges are a subset of the flows those programs have
{"analysed": 1, ..., "unsettled": 1, ...}

A walk that stops before settling adds the incomplete-walk reason to the targets and jumps it found, as in the targets.jsonl rows under where this shows up. With --call-targets-only, a backward liveness walk first works out what the targets and jumps read, narrowed by the area-need table under --narrow-areas; the forward walk then applies that result to every state it hands on, which is the byte strips and live-node chips under why sweeps can stop early. The flags are documented in the field dataflow reference. Next: answering every walk once.