Rounds across programs, and walking only what changed

Read first: Area need, Local site resolution

A program's need on entry can be decided by a program two calls away, whose answer depends on others in turn. So one walk per program is not enough: the corpus is walked in rounds until no answer moves, and on about 3,800 programs, walking every one every round is the cost.

PROGA LINKs to PROGB, which LINKs to PROGC; then PROGA XCTLs to the name it reads back from bytes [0, 8). So PROGC needs those bytes on entry, though its own code only writes them. Five rounds settle it, and walking only the programs whose inputs changed takes 9 walks instead of 20.

Each program is a member, with an entry row (bytes it needs on entry) and a back row (bytes its callers read after it returns).

The example

Four programs share one 16-byte commarea layout. Besides the PROGA → PROGB → PROGC chain, PROGD reads a program name from a queue and XCTLs there, handing its commarea on. Solid arrows: LINKs to a named program; dashed: XCTLs to a variable.

flowchart TD
    A[PROGA] -->|"LINK, WS-AREA"| B[PROGB]
    B -->|"LINK, DFHCOMMAREA"| C[PROGC]
    A -.->|"XCTL WS-NEXT-PGM, no area"| Q1["?"]
    D[PROGD] -.->|"XCTL WS-NEXT, DFHCOMMAREA"| Q2["? (read from NEXTQ)"]

The strip below is the 16-byte commarea as the rounds leave it. PROGB, PROGC and PROGD each need bytes [0, 8), CA-NEXT-PGM, on entry (marked need). Bytes [8, 16), CA-CODE and CA-ACCT, are needed by nobody, so a fixpoint narrowed to this need does not have to track them.

That is the whole answer, one row per member, settled after 5 rounds and 9 walks:

The lines that matter. CA-NEXT-PGM and PROGA's WS-NEXT-PGM are both bytes [0, 8):

* PROGA
EXEC CICS LINK PROGRAM('PROGB')
     COMMAREA(WS-AREA) END-EXEC.
EXEC CICS XCTL PROGRAM(WS-NEXT-PGM) END-EXEC.
* PROGB
EXEC CICS LINK PROGRAM('PROGC')
     COMMAREA(DFHCOMMAREA) END-EXEC.
EXEC CICS RETURN END-EXEC.

* PROGC
IF EIBAID = DFHPF3
    MOVE 'PROGE' TO CA-NEXT-PGM
END-IF.
EXEC CICS RETURN END-EXEC.
* PROGD
EXEC CICS READQ TS QUEUE('NEXTQ')
     INTO(WS-NEXT) END-EXEC.
EXEC CICS XCTL PROGRAM(WS-NEXT)
     COMMAREA(DFHCOMMAREA) END-EXEC.

      *> 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, 8) 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 is not 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 (the IF above). 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: PROGB in PROGA's callees becomes PROGA in PROGB's callers.

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. In the grid under why only some members walk again, below, that is all 5 × 4 = 20 cells. The dirty sets walk only the amber ones: 4 + 1 + 1 + 2 + 1 = 9.

Notice the direction each fact travels, on the row graph in the problem. A back row moves down (PROGA → PROGB → PROGC): the amber back cells, rounds 1 and 2. An entry row moves up (PROGC → PROGB → PROGA): the amber entry cells, rounds 3 and 4. The dynamic need moves sideways to PROGD, through that graph's dynamic box.

With --max-rounds 3, the run stops after round 3 and warns that it stopped after 3 rounds with 2 members still to walk. It writes the walk's round-3 table (step 3), compared here with the settled one: PROGB and PROGD need nothing on entry. Those bytes arrive only through the longer chain PROGA → PROGB → PROGC and back, which three rounds did not finish carrying.

amber: short of the settled need. The back rows, [0, 8) for PROGB and PROGC, are already settled by round 3.

Why only some members walk again

The walk started every member at "needs nothing" and walked each round against the table the round before built. Rows only grow, and they are bounded by the size of the areas, so eventually a round changes nothing: step 5. That table is the least one that holds, the strip in the example.

Round 1 walked all four members; after that, each round walked only one or two. Skipping is safe because 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).

For the example, one column per item in that list:

Everything else a walk reads is its own program, which never changes. So if none of the cells in a member's row of that table changed since its last walk, walking it again gives the same report: keep that report and skip the member. That leaves three reasons to walk a member again: a program it calls got a new entry row, its own back row changed, or the dynamic need changed and it has an unresolved site. Each fired in the walk:

The first reason needs "who calls PROGC", but each member only knows what it calls. So the callee map is inverted once, before the first round: "member → programs its sites reach" becomes "program → members whose sites reach it", the callers() column of the callee map in the example. 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 walks against the table the previous round built: in the grid below, round 4 walks PROGB and PROGD both against round 3's table. That is what lets one round's walks run in parallel.

amber: walked this round; kept: last report reused

Why one walk per program is not enough

In step 1 of the walk, PROGB's walk found nothing, because the table it walked against was empty. Only after PROGA's walk filled PROGB's back row could PROGB's walk in step 2 find anything. A member's walk is ordinary backward liveness over its own statements (see area need), but the demand it starts from comes from the table. The right-hand column is PROGB's rows once the rounds have settled:

The fragment below, from PROGB and PROGD, marks where each demand comes in:

* PROGB
EXEC CICS LINK PROGRAM('PROGC')
     COMMAREA(DFHCOMMAREA) END-EXEC.
                  *> PROGC's entry row
EXEC CICS RETURN END-EXEC.
                  *> PROGB's own back row
* PROGD
EXEC CICS XCTL PROGRAM(WS-NEXT)
     COMMAREA(DFHCOMMAREA) END-EXEC.
                  *> the dynamic need

At the LINK, which hands over an area, PROGB must supply what the callee reads on entry: the callee's entry row. At its own EXEC CICS RETURN (or a GOBACK), it must supply what its callers read back: its own back row. At PROGD's XCTL, a dynamic call nothing resolved, it must supply what any member might read: the union of every member's entry row.

So each walk's output depends on rows that other walks produce. The graph below draws that for the example: an arrow runs from the walk that produces a row to the walk that reads it. PROGB has two arrows in (PROGC's entry row, its own back row from PROGA) and three out (PROGC's back row, its own entry row to PROGA and to the dynamic box). Run once, per-program liveness cannot settle a loop like the PROGB ⇄ PROGC pair, where each walk's output is the other's input: in the walk, PROGB fed PROGC's back row in step 2 and read PROGC's entry row back in step 4.

flowchart TD
    A[PROGA] -->|"PROGB's back"| B[PROGB]
    B -->|"PROGC's back"| C[PROGC]
    C -->|"PROGC's entry"| B
    B -->|"PROGB's entry"| A
    D[PROGD]
    B -->|"entry"| DYN["dynamic need = ⋃ entry"]
    C -->|"entry"| DYN
    D -->|"entry"| DYN
    DYN -->|"unresolved XCTL"| D

Where this shows up

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, and these rounds are how it settles across the corpus. On CardDemo, the entry need summed over every program fell from 4,394 bytes to 92 once LENGTH OF bounds were folded and more sites resolved (area need has the steps), and the fixpoint narrowed to it gave identical targets, links and graph.

A commarea is a conversation between programs: no single program's source says that PROGC needs bytes [0, 8). And walking 3,800 programs per round is the cost, though most programs' inputs do not change after the first round or two: walking only the members whose inputs changed gives the same table for a fraction of the walks, 9 instead of 20 on the example.

The rule

Round 3 of the walk (step 3) is the rule applied once, term by term:

The stop clause fires twice on this page: in round 5, where dirty₅ is empty (the last step of the walk), and with --max-rounds 3, at k = 3 with |dirty₃| = 2 — the table above.

Why this reaches the same rows as walking everything: a walk reads only its program, which is fixed, and the three things in the table under why only some members walk again. 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. PROGA's column in the grid shows it: walked in round 1, kept through rounds 2–4, walked again in round 5. Its two reports, from the walk:

The round-5 walk changed nothing, which is why it is the last. 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: every amber cell in the walk goes from {} to [0, 8), and none ever shrinks.

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; the table, read off the walk, shows where the bytes [0, 8) were in each round:

  round	row that became [0, 8)	hop
  1	PROGB back	PROGA → PROGB
  2	PROGC back	PROGB → PROGC
  3	PROGC entry, dynamic	turns round in PROGC
  4	PROGB entry, PROGD entry	PROGC → PROGB; dynamic → PROGD
  5	none: PROGA has no entry row	PROGB → PROGA

• A capped run can be short, and a short need gives wrong targets. --max-rounds N stops after N rounds even when members are still dirty, and logs a warning with how many. This is the line cobble logged for the example with --max-rounds 3:

  area need: stopped after 3 rounds with 2 members still to walk: the need may be short of what a settled run finds

  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 — PROGB's and PROGD's [0, 8) in the capped table after the walk. A narrowed fixpoint that trusts a short need stops tracking those bytes, so a target that depends on them can lose values, and nothing in the result marks which targets did: the log warning is the only sign. 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 example the only such member is PROGD, and the union moves once, in round 3, because of PROGC — a program PROGD has no call to:

  round	union of entry rows after it	dirtied for dynamic
  1	{}	—
  2	{}	—
  3	[0, 8)	{PROGD}
  4	[0, 8)	—
  5	[0, 8)	—

  Every other member with an unresolved site would be in that round-3 cell too. 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. With --max-workers 2, cobble deals the example's members out in turn, in the order the extents file lists them (PROGA, PROGB, PROGC, PROGD), so each worker's work per round, from the grid, is:

  round	worker 1: PROGA, PROGC	worker 2: PROGB, PROGD
  1	PROGA, PROGC	PROGB, PROGD
  2	waits	PROGB
  3	PROGC	waits
  4	waits	PROGB, PROGD
  5	PROGA	waits

  After round 1, every round leaves one of the two workers waiting.
• 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. Change PROGB's LINK to name a program the corpus does not have:

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

  The LINK now demands all of [0, 16), so PROGB needs every byte on entry in round 1, and the union of entry rows widens to [0, 16), which PROGD is charged in round 2. PROGC, which nothing calls any more, needs nothing. It settles after 2 rounds and 4 + 3 = 7 walks (amber: wider than the settled table):

  member	entry	back
  PROGA	{}	{}
  PROGB	[0, 16)	[0, 8)
  PROGC	{}	{}
  PROGD	[0, 16)	{}
  dynamic	[0, 16)

  Against the strip in the example, bytes [8, 16) — CA-CODE and CA-ACCT, which no target reads — are now tracked on entry to two programs. 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. Run on this page's four programs with --max-workers 1, it logs the walk above round for round (timestamps, the reaching_defs and loading lines, and the closing "written to" line are left out):

area need: PROGD MAIN-PARA line 14 XCTL unresolved: not-a-literal
area need round 1: [1/4] PROGA, 0 bytes on entry
area need round 1: [2/4] PROGB, 0 bytes on entry
area need round 1: [3/4] PROGC, 0 bytes on entry
area need round 1: [4/4] PROGD, 0 bytes on entry
area need round 1: walked 4 members; 0 bytes needed on entry, 8 read back, summed over 4 members; 1 to walk next
area need round 2: [1/1] PROGB, 0 bytes on entry
area need round 2: walked 1 members; 0 bytes needed on entry, 16 read back, summed over 4 members; 1 to walk next
area need round 3: [1/1] PROGC, 8 bytes on entry
area need round 3: walked 1 members; 8 bytes needed on entry, 16 read back, summed over 4 members; 2 to walk next
area need round 4: [1/2] PROGB, 8 bytes on entry
area need round 4: [2/2] PROGD, 8 bytes on entry
area need round 4: walked 2 members; 24 bytes needed on entry, 16 read back, summed over 4 members; 1 to walk next
area need round 5: [1/1] PROGA, 0 bytes on entry
area need round 5: walked 1 members; 24 bytes needed on entry, 16 read back, summed over 4 members; 0 to walk next

The "to walk next" counts are the sizes of the chip rows in the walk: 1, 1, 2, 1, 0. The byte sums add up the table's columns: in round 4, entry rows of 8 bytes each for PROGB, PROGC and PROGD make 24, and back rows for PROGB and PROGC make 16.

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, which is why round 4 in the log above counts [1/2], [2/2] rather than carrying on from round 3.

The walk inside each member is backward liveness: the same worklist idea as fixpoints, run backwards, as area need describes. What the rows mean, and where the demand comes from — the annotated fragment in the problem — is in area need.