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

Walk the whole program in reverse postorder a fixed number of times. Stop early when a sweep changes nothing. If the sweeps run out first, say so on every result.

Where this shows up in reverse engineering

A whole-corpus run is as slow as its slowest program. When the goal is one specific answer — here, 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, and they should not quietly return less than they found either.

• Dynamic call targets across a large CICS corpus. On a corpus of about 3,800 programs, the per-program fixpoint was the step that 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". That is a list of call sites to check by hand, not a silent gap in the call graph.
• The same trade appears in any whole-program analysis run under a time limit: either 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 problem

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 the walk stops and publishes what it has, unsettled. On the large corpus the worklist did finish every program. But the last three programs took 1,404 s, 2,324 s and 4,434 s. The run spent over an hour waiting on one program.

A worklist is also hard to watch. Nothing in it counts down: the queue grows and shrinks, so the best a progress line can do is estimate from how fast the queue drains. You cannot tell in advance how much work a program will need, or how far along it is.

What is wanted is a walk whose cost is known before it starts, which still gives the exact answer when it has time to, and which marks its results when it does not.

The intuition

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.

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. So when a sweep reaches a node, everything that flows into it along forward edges has already arrived. MOVE 'X' TO WS-A, then PERFORM P1, where P1 does MOVE WS-A TO WS-B and PERFORM P2, and P2 does MOVE WS-B TO WS-C; then, back in the caller, MOVE WS-C TO WS-D and GOBACK. Every one of those reads finds its definer in a single sweep. On a program like that with no back edge, cobble runs one sweep and calls the member settled — there is nothing a second sweep could add.

A loop needs a second sweep. A loop's test comes before its body in reverse postorder, because the test is how the body is reached. The body's write gets back to the test only along the back edge, at the end of the body. By then the sweep has already visited the test and pushed its state to the code after the loop. So in the first sweep, every reader after the loop sees only what was true before the loop ran. In the second sweep 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 sweep that changes nothing proves the fixpoint. If a whole sweep leaves every entry state as it was, the next sweep would too: the walk is at the fixpoint, and the answer is exactly the worklist's. The member is settled. If the budget of sweeps runs out while states are still growing, the member is unsettled.

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. Every flow read off it is a real flow; every value in a set is a value the field can really hold. What may be absent is a flow or a value that needed more sweeps. Cobble says so: every dynamic call target and every jump in an unsettled member carries the reason incomplete-walk (see value sets for how reasons work), and the member is counted and named as unsettled in the run's summary.

Carry less on each sweep. With --call-targets-only, cobble first runs a backward liveness walk over each program. It 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. The forward walk then drops every state entry that overlaps nothing live at the node it is handed to. The walk still visits the same nodes, but each visit carries only what the dynamic targets and handed-over areas depend on.

The example

A loop body writes WS-NEXT. A LINK after the loop reads it.

       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.

Cobble's control-flow graph for this program has 13 reachable nodes. Besides one node per statement, it 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 and into PICK-PARA; its TRUE arm goes to the LINK. The end of PICK-PARA returns to the test: that is the one back edge.

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

Here the code after the loop comes ahead of the body. The loop on the traversal page put the body first, because its search took the body's arm first. Either way the test comes before both, and that is what decides how many sweeps the loop needs.

The tables below show, for each node, the values WS-NEXT can hold on entry. PROGB is the VALUE clause; PROGC is written by PICK-PARA/0.

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. 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.

With --call-targets-only, the liveness walk finds that only WS-NEXT matters: 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 worklist then needs 15 dequeues instead of 24, because changes to WS-I no longer re-queue anything. The sweep walk still visits 13 nodes per sweep and settles on sweep 3, but each visit carries only WS-NEXT. The LINK's candidates are the same in every case.

The rule

A value written in a loop body reaches a reader after the loop on sweep 2. Each further step it has to take backward against the order — around another back edge, or to a copy earlier in the same body — 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.

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. With --sweeps 2 the LINK's row is complete and 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 — MOVE WS-CODE TO WS-NEXT first, then MOVE 'PROGC' TO WS-CODE — the value has to go round the back edge twice to reach the LINK. In that variant, with WS-CODE given a VALUE of its own, the LINK gained one candidate on sweep 2 and another on sweep 3, and the walk settled 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. A program with no loop in its source can still need a third sweep to settle; one such test 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.
• Missing is still missing. No value in an unsettled result is invented, but a missing candidate is a missing edge in the call graph. The incomplete-walk reason is the only thing that says so. 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. On a small or simple program it can do more visits than the worklist, as above. 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. 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). --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. A member with no back edge is settled after one sweep.

The log says settled in N sweeps or NOT SETTLED after N sweeps for each member. The closing warning names every unsettled member, and the summary counts them under unsettled. A walk that stops before settling adds the incomplete-walk reason to the targets and jumps it found.

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.

The flags are documented in the field dataflow reference. Next: answering every walk once.