Rounds across programs, and walking only what changed

How area need settles across a whole corpus: walk every program once, then walk again only the programs whose inputs moved, until none did.

Where this shows up in reverse engineering

The goal on a large CICS corpus (about 3,800 programs) was to resolve dynamic call targets: CALL WS-PGM, EXEC CICS XCTL PROGRAM(WS-NEXT-PGM). To do that cheaply, the fixpoint should track only the handed-over bytes some target can depend on. Area need computes those bytes per program. On CardDemo, the entry need summed over every program fell from 4,394 bytes to 92, and the fixpoint narrowed to it gave identical targets, links and graph.

• A commarea is a conversation between programs. Whether a program needs byte 0 of its commarea can depend on a program three LINKs away that reads a next-program name back. No single program's source says so.
• One answer per program is not enough. Each program's answer feeds its callers and its callees. Change one and others may change. So the corpus is walked in rounds until no answer moves.
• Walking 3,800 programs per round is the cost. Most programs' inputs do not change after the first round or two. Walking only the ones whose inputs changed gives the same table for a fraction of the walks.

The problem

Each program (a member) has two rows in the area table:

• entry — the bytes of each area it receives that it needs on entry;
• back — the bytes of that area its callers read again after it returns.

A member's walk is ordinary backward liveness over its own statements (see fixpoints). But the demand that walk starts from comes from the table. At a call that hands over an area, the member must supply what the callee reads on entry: the callee's entry row. At its own GOBACK or EXEC CICS RETURN, it must supply what its callers read back: its own back row. At a dynamic call nothing resolved, it must supply what any member might read: the union of every member's entry row.

So the walk's output depends on rows that other walks produce. A member's entry row feeds its callers. Its read-backs feed its callees' back rows. Per-program liveness, run once, sees only the rows as they stood when it ran. It cannot settle a dependency that runs through other programs.

The intuition

Start every member at "needs nothing". Walk every member against that table. Collect what each walk reports and build a new table. Walk again against the new table. Rows only grow, and they are bounded by the size of the areas, so eventually a round changes nothing. That table is the least one that holds.

Walking every member every round is correct but wasteful. A walk reads exactly three things from the table:

1. the entry rows of the programs its call sites reach;
2. its own back row;
3. if it has a call site that hands over an area and that nothing resolved, the union of every member's entry row (the dynamic need).

Everything else it reads is its own program, which never changes. So if none of those three things changed since a member was last walked, walking it again gives the same report. Keep its last report and skip it. That leaves three reasons to walk a member again:

• a program it calls got a new entry row — the member is one of that program's callers;
• its own back row changed;
• the dynamic need changed, and the member has an unresolved site.

The first reason needs "who calls this program", but each member only knows what it calls. So the callee map is inverted once, before the first round: the inversion turns "member → programs its sites reach" into "program → members whose sites reach it". The sites counted are those naming a program, plus dynamic sites resolved to one or more programs (in their own program, see local site resolution, or by an earlier combine).

This is the worklist idea one level up. There, the items are statements, and a statement whose notes changed queues its neighbours. Here, the items are members, and a row that changed queues the members that read it. One difference: within a program the worklist takes one statement at a time and its result is visible at once. Here a whole round of members walks against the same table, built at the end of the previous round. That is what lets the walks of one round run in parallel.

The example

Four programs share one 16-byte commarea layout. PROGA LINKs to PROGB, which LINKs to PROGC. After PROGB returns, PROGA XCTLs to whatever program name came back. PROGD reads a program name from a queue and XCTLs there, handing its commarea on.

      *> Layout shared by PROGB, PROGC, PROGD (PROGA uses WS-AREA, same shape)
       01  DFHCOMMAREA.
           05  CA-NEXT-PGM          PIC X(8).
           05  CA-CODE              PIC X(2).
           05  CA-ACCT               PIC X(6).

       PROGRAM-ID. PROGA.
       WORKING-STORAGE SECTION.
       01  WS-AREA.
           05  WS-NEXT-PGM          PIC X(8).
           05  WS-CODE              PIC X(2).
           05  WS-ACCT               PIC X(6).
       PROCEDURE DIVISION.
           EXEC CICS LINK PROGRAM('PROGB') COMMAREA(WS-AREA) END-EXEC.
           EXEC CICS XCTL PROGRAM(WS-NEXT-PGM) END-EXEC.

       PROGRAM-ID. PROGB.
       PROCEDURE DIVISION.
           EXEC CICS LINK PROGRAM('PROGC') COMMAREA(DFHCOMMAREA) END-EXEC.
           EXEC CICS RETURN END-EXEC.

       PROGRAM-ID. PROGC.
       PROCEDURE DIVISION.
           IF EIBAID = DFHPF3
               MOVE 'PROGE' TO CA-NEXT-PGM
           END-IF.
           EXEC CICS RETURN END-EXEC.

       PROGRAM-ID. PROGD.
       WORKING-STORAGE SECTION.
       01  WS-NEXT                  PIC X(8).
       PROCEDURE DIVISION.
           EXEC CICS READQ TS QUEUE('NEXTQ') INTO(WS-NEXT) END-EXEC.
           EXEC CICS XCTL PROGRAM(WS-NEXT) COMMAREA(DFHCOMMAREA) END-EXEC.

What the walks need to know about these programs:

• PROGA's XCTL reads WS-NEXT-PGM, bytes 0–7 of WS-AREA, after the LINK. So it reads those bytes back from PROGB. PROGA receives no area, so it has no entry need of its own. Its XCTL hands over no area, so it reads nothing from the table and does not count as a member with an unresolved site.
• cobble treats a LINK as writing the area it hands over. So in PROGB, bytes live after the LINK are supplied by PROGC, not by PROGB's caller. PROGB's entry need is PROGC's entry need; what PROGB reads back from PROGC is PROGB's own back row.
• PROGC writes CA-NEXT-PGM on one path only. On the other path the incoming bytes go straight back to its caller. So its entry need is its back row.
• PROGD's XCTL target comes from a queue, so no definition resolves it. It hands over its commarea, so it is charged the dynamic need: the union of every member's entry row.

The callee map and its inversion:

Members with an unresolved site that hands over an area: {PROGD}. Rows below are commarea byte ranges, written half-open: [0,8) is bytes 0 to 7, the eight bytes of CA-NEXT-PGM.

Step by step

Each step is one round. It shows which members were walked, the table after the round (amber: changed in this round), and the members dirtied for the next round with the reason.

Walking every member every round produces the same five tables, round for round, because a skipped member would have reported exactly what it reported last time. It costs 5 × 4 = 20 walks. The dirty sets cost 4 + 1 + 1 + 2 + 1 = 9.

Notice the direction each fact travels. A back row moves down the chain (PROGA → PROGB → PROGC), one hop per round. An entry row moves up (PROGC → PROGB → PROGA), one hop per round. The dynamic need moves sideways to PROGD, which no call chain connects to the others.

With --max-rounds 3, the run stops after round 3 and warns that it stopped after 3 rounds with 2 members still to walk. The table it writes has PROGB and PROGD needing nothing on entry. Those bytes arrive only through the longer chain PROGA → PROGB → PROGC and back, which three rounds did not finish carrying.

The rule

Why this reaches the same rows as walking everything: a walk reads only its program, which is fixed, and the three things named above. A member is left out of a round only when none of those changed since its last walk. So its kept report is the one a fresh walk would produce, and each T_k equals the table the walk-everything run builds in round k. It stops because rows only grow — more demand in a liveness walk never means fewer live bytes — and every row is bounded by the bytes of the areas.

What goes wrong

• Rounds track chain length. A fact moves one call hop per round, because a round's walks all read the table from before the round. A deep LINK chain, or a back row that must travel down and come back up as an entry row, needs that many rounds. The example's three-deep chain took five.
• A capped run can be short, not wrong. --max-rounds N stops after N rounds even when members are still dirty, and logs a warning with how many. Every byte in the capped table is really needed; what it can miss is bytes that arrive only through call chains longer than the rounds covered. A narrowed fixpoint that trusts a short need stops tracking those bytes, so a target that depends on them can lose its values. The default, 0, runs until it settles.
• Unresolved sites couple everything. A member with an unresolved site that hands over an area depends on every member's entry row. Any change that widens the union dirties all of them at once. In the same way, what unresolved calls read back is added to every member's back row, so a change there dirties every member. Resolving sites first — in their own program, or from an earlier combine — cuts these edges and shrinks the need.
• A round waits for its slowest worker. Members are split across worker processes once, at load time. A round with one dirty member uses one worker while the others wait, and a round ends only when every worker has sent its reports.
• Missing programs count as needing everything. A callee that is not in the table, or does not receive the slot handed to it, is charged every byte. A member whose ASG cannot be read is dropped with a warning and adds no row.

In cobble

The command is cobble-dataflow-area-need. Before the first round it inverts the callee map once. After each round it compares the table before and after and finds the three kinds of dirty member, and the next round walks only those. It stops when that set is empty, or after --max-rounds rounds with a warning. A walk reads, for each call, the callee's entry row, the dynamic need for an unresolved site, or every byte for an unknown callee; and for itself, its own back row.

The members are shared out among worker processes (--max-workers). Each worker holds its share of the members for the whole run; only the table and the reports cross between processes. One progress count, under a lock, is advanced by every worker as it finishes a load or a walk, so the log numbers members in the order they finish. It is never reset: each round subtracts the walks made before it to print [i/n] for that round.

The walk inside each member is the backward liveness worklist of fixpoints. What the rows mean, and where the demand comes from, is in area need.