Area need: which handed-over bytes anyone reads

A commarea is handed from program to program, but most of its bytes never decide where control goes next. Work out, per program, which bytes do, and track only those.

Where this shows up in reverse engineering

Recovering a CICS application's call graph means resolving its dynamic transfers: CALL WS-PGM, EXEC CICS XCTL PROGRAM(WS-NEXT-PGM). On a large CICS corpus (about 3,800 programs and 19,000 jumps) the target names come in three shapes: a literal VALUE in working storage, a MOVE 'LITERAL' TO WS-FIELD, and, for about 5% of sites, a field the program reads out of its DFHCOMMAREA and then transfers to. That last shape is the reason to follow values across programs at all.

• Following a value across programs means tracking the handed-over area in every caller. A commarea is often hundreds or thousands of bytes. Tracking all of it in every program that hands one over is most of the cost of the whole analysis, and almost none of those bytes ever name a program.
• The question to ask first is cheap: of each program's commarea, which bytes does anything downstream read to pick a call target? That is a liveness question, asked once per corpus, before the expensive forward analysis runs.
• The answer narrows the expensive run. Cobble runs cobble-dataflow-area-need, then cobble-dataflow-fixpoint --call-targets-only --narrow-areas, then the cross-program combine. On CardDemo the summed entry need fell from 4,394 bytes to 92, and the narrowed run gave the same targets, links and graph as the run over whole areas.

The problem

A caller writes a few fields of a 100-byte commarea and transfers to a callee. The callee reads one 8-byte field of it and uses it as the next program name. To resolve that name, the forward analysis has to carry the caller's writes into the callee. If it carries every byte of every commarea, it does work for 92 bytes it will never need. You want to know, for each program, which bytes of what it is handed actually feed a call target, so the forward analysis can drop the rest.

The catch is that "feeds a call target" crosses programs. A callee's need on entry decides what its caller must keep live at the call; that can make the caller's own commarea live on its entry, which its own callers must then keep. The need has to flow backward along call chains until it stops changing.

The intuition

Inside one program this is ordinary backward liveness: start from the reads you care about and walk the control flow graph backward, asking at each statement which bytes are still needed. A write that fully covers a needed byte satisfies it, so that byte is no longer needed above the write; the bytes the write copied from become needed instead. Where paths split, anything needed on either path is needed. It is the mirror image of reaching definitions, run with the same worklist, over byte extents rather than whole fields.

What makes it an area need is the seed and the summary.

• Seed: the operand of every dynamic call site is needed at that site. So is a TRANSID data name. At a call that hands over an area, the bytes of that area the callee reads on entry are needed at the call.
• Summary: the bytes of the program's own received areas still live at its entry are its entry row. For a LINK or CALL, which returns, the bytes of the handed area live right after the call are what the caller reads back; collected per callee, they become that callee's back row, which is needed at the callee's GOBACK, EXIT PROGRAM, STOP RUN or EXEC CICS RETURN.

Each row is indexed by a slot: the kind of area and its position. COMMAREA is what LINK and XCTL hand over (always position 0); USING is a CALL's arguments, by position; RETRIEVED is what a START hands over in its FROM area and the started program gets back with RETRIEVE INTO. Bytes are stored relative to the start of the area, so a caller's 100-byte group and the callee's DFHCOMMAREA line up by offset, not by field name.

Every program starts needing nothing. Walk all of them, rebuild the table from what they report, and walk again the ones whose inputs changed. Rows only ever grow, so this stops. How the rounds pick which programs to walk again is on its own page.

The example

PROGA fills two fields of a 100-byte commarea and transfers to PROGB. PROGB copies its whole DFHCOMMAREA into working storage and transfers to whatever program name sits in bytes 8 to 16.

       IDENTIFICATION DIVISION.
       PROGRAM-ID. PROGA.
       DATA DIVISION.
       WORKING-STORAGE SECTION.
       01  WS-COMMAREA.
           05  WS-USER-ID       PIC X(8).
           05  WS-NEXT-PGM      PIC X(8).
           05  WS-REST          PIC X(84).
       PROCEDURE DIVISION.
       MAIN-PARA.
           MOVE 'USER0001' TO WS-USER-ID.
           MOVE 'PROGC' TO WS-NEXT-PGM.
           EXEC CICS XCTL PROGRAM('PROGB')
                COMMAREA(WS-COMMAREA) END-EXEC.

       IDENTIFICATION DIVISION.
       PROGRAM-ID. PROGB.
       DATA DIVISION.
       WORKING-STORAGE SECTION.
       01  WS-COMMAREA.
           05  WS-USER-ID       PIC X(8).
           05  WS-NEXT-PGM      PIC X(8).
           05  WS-REST          PIC X(84).
       LINKAGE SECTION.
       01  DFHCOMMAREA          PIC X(100).
       PROCEDURE DIVISION.
       MAIN-PARA.
           MOVE DFHCOMMAREA TO WS-COMMAREA.
           EXEC CICS XCTL PROGRAM(WS-NEXT-PGM) END-EXEC.

Byte ranges are written region[start:end), counted from 0: ws[8:16) is WS-NEXT-PGM, linkage[0:100) is DFHCOMMAREA. Only statements are shown; the graph's other nodes write nothing and hand their live set on unchanged. Both XCTLs transfer for good, so neither program reads anything back and both back rows stay empty.

Step by step

Within a program the walk visits statements last to first (the worklist takes the highest position each time). Each table shows what is live on entry to the statement, that is, just above it.

Fed this file, cobble-dataflow-fixpoint --call-targets-only --narrow-areas demands only ws[8:16) at PROGA's XCTL instead of all of ws[0:100). PROGA then keeps one write target (WS-NEXT-PGM) instead of two, and its edge count drops from 2 to 1. The cross-program combine still follows linkage[8:16) in PROGB back to 'PROGC' in PROGA. These rows and counts are what cobble produced on these two programs.

Without the byte-for-byte copy rule, the MOVE in PROGB would make all of linkage[0:100) live, PROGB's entry row would be [0, 100), and PROGA would have to keep MOVE 'USER0001' too, along with whatever wrote the other 84 bytes.

The rule

Byte-for-byte copies. A MOVE copies byte for byte when either side is a group, or both are alphanumeric, the source has no subscript, and its reference-modification start (if any) is known to the compiler. For such a write, the walk maps each live target byte back to the one source byte that landed on it, and keeps only those. Any other write needs all its sources.

LENGTH OF in bounds. A reference-modification bound such as WS-AREA(LENGTH OF WS-HDR + 1 : LENGTH OF WS-BODY) is folded to a number, because the compiler knows each field's length from its declaration. Literals, LENGTH OF and + - * / over them fold. With both bounds known the extent is exact and narrow. Without folding it would be a clamped extent over the whole base field.

START and RETRIEVE. A START hands over its FROM area the way a LINK hands over a commarea, in slot RETRIEVED/0. Its transaction id is resolved to a program through the CSD, as a RETURN TRANSID's is. The started program's need in that slot is the bytes of its RETRIEVE INTO area live right after the RETRIEVE. The RETRIEVE itself demands nothing: it writes the area, it does not read it.

How the result narrows the fixpoint. --call-targets-only keeps only the writes a dynamic call target or a handed-over area depends on. Without --narrow-areas every handed-over area counts whole. With it, each call is charged only the bytes the area-need file says its callees read, so the forward run tracks those bytes and nothing else of the area.

What goes wrong

• One unresolved site charges everyone. A dynamic call site that hands over an area and is not resolved is charged the union of every member's entry row. In a corpus where some programs need thousands of bytes, that union is thousands of bytes, and it then makes the caller's own commarea live, which spreads to its callers. Before narrowing on the large CICS corpus, rows such as 4,500 bytes needed on entry appeared, mostly for this reason. Resolving as many sites as possible inside their own program, before the rounds start, is the fix; see resolving a dynamic site locally. A site resolved to no program at all charges nothing.
• Clamped extents keep whole areas live. A write whose target is not exact (a computed subscript, a reference-modification bound that does not fold) is weak: it kills nothing, and its whole target becomes live wherever it touches a live byte. Before LENGTH OF folded, a program that moved its saved state into part of a 2,000-byte commarea with LENGTH OF bounds made the whole area live, and its RETURN TRANSID to itself grew an 8-byte need to 2,000. That one fix took CardDemo from 4,394 bytes to 140; resolving sites through the combine took it to 92.
• Copies that are not byte-for-byte need everything. A MOVE into a numeric field, a subscripted source, or a source whose reference-modification start is a run-time value all fall back to needing the whole source. That is safe but wide. Before the copy rule, CardDemo's summed entry need was 32,767 bytes; with it, 1,033.
• A capped run can be short. --max-rounds N stops after N rounds and warns how many members were still to walk. A need that has not settled can miss bytes that only arrive through longer call chains, and a fixpoint narrowed by it can then miss candidates. An uncapped run always settles, since rows only grow and are bounded by the areas' sizes.
• It is only as good as the corpus. A callee that is not in the corpus, or is but does not receive that slot, is charged every byte of the area: nothing is known about what it reads. An unreadable member adds nothing, so its own targets go unresolved later.

In cobble

The command is cobble-dataflow-area-need. It runs the rounds over the whole corpus and stops when a round changes no row, or after --max-rounds N. --sites adds a report of each dynamic site and where it sits in the source. The fixpoint reads the result under cobble-dataflow-fixpoint --call-targets-only --narrow-areas, and tracks only the bytes of each handed-over area that some program reads. The command is documented in field dataflow.

Next: resolving a dynamic call site inside its own program, and rounds across programs, and walking only what changed.