Explainer 7 of 11

Resolving a dynamic call site inside its own program

Before any cross-program work, ask each program what its own dynamic XCTL, LINK, CALL, RETURN TRANSID and START sites can reach. Most can be answered from the program alone, and every one answered there stops costing the union of everyone's need.

Where this shows up in reverse engineering

On a large CICS corpus (about 3,800 programs and 19,000 jumps), the only goal was a call graph with the dynamic targets filled in. Those targets came in three shapes:

A literal VALUE in working storage, then EXEC CICS XCTL PROGRAM(WS-NEXT-PGM). Nothing ever writes the field.
A MOVE 'LITERAL' TO WS-FIELD, often one per branch of an IF or EVALUATE, then the call through the field.
A name read out of DFHCOMMAREA (about 5% of sites): a caller put the next program's name in the commarea, and this program XCTLs to it.

The first two shapes need nothing outside the program. Only the third needs the cross-program walk. The area-need stage decides which commarea bytes the fixpoint must track, and it was charging every dynamic site as if it were the third shape. Answering the first two locally stops those sites from being charged that union, so a program's row reflects the programs it really reaches.

The problem

Area need works out, per program, which bytes of a handed-over area the program's call targets depend on. At a call site that hands over an area, the caller must keep alive whatever the callee needs on entry. For XCTL PROGRAM('PROGB') that is PROGB's row. For XCTL PROGRAM(WS-NEXT-PGM) the callee is not known, so the only safe charge is the union of every member's entry row for that kind of area. In a corpus where some programs need thousands of bytes, that union is thousands of bytes, and it lands on every program with even one such site. It then spreads to their callers.

So: for each dynamic site, can we name every program it can reach, using only its own program? If yes, charge only those programs.

The intuition

Run reaching definitions forward over the program's control-flow graph, but carry the value set of one field only: the operand of the site. A write that overwrites every byte of the operand with a literal sets the set to that literal. A write that touches the operand any other way makes it unknown, and says why. Where paths meet, take the union. At the site, if every value is a literal, the site is resolved.

One doubt is let through: uninitialised. It means some path reaches the site with the operand never written and no VALUE. That storage belongs to this program, and no other program can have put a name in it. The site can reach only the names its literals spell.

The example

One program, three dynamic sites. PROGB, PROGC and PROGD each XCTL to a name in their own commarea: PROGB reads bytes 20–28, PROGC bytes 40–48, PROGD bytes 60–68. Nothing calls PROGD.

       IDENTIFICATION DIVISION.
       PROGRAM-ID. PROGA.
       DATA DIVISION.
       WORKING-STORAGE SECTION.
       01  WS-FIRST-PGM         PIC X(8) VALUE 'PROGB'.
       01  WS-MENU-PGM          PIC X(8).
       01  WS-NEXT-PGM          PIC X(8).
       01  WS-FLAG              PIC X.
       01  WS-MODE              PIC X.
       LINKAGE SECTION.
       01  DFHCOMMAREA.
           05  LK-NEXT          PIC X(8).
           05  LK-REST          PIC X(92).
       PROCEDURE DIVISION.
       MAIN-PARA.
           IF WS-FLAG = 'Y'
               MOVE 'PROGB' TO WS-MENU-PGM
           ELSE
               MOVE 'PROGC' TO WS-MENU-PGM
           END-IF.
           MOVE LK-NEXT TO WS-NEXT-PGM.
           EVALUATE WS-MODE
               WHEN '1'
                   EXEC CICS XCTL PROGRAM(WS-FIRST-PGM)
                       COMMAREA(DFHCOMMAREA) END-EXEC
               WHEN '2'
                   EXEC CICS XCTL PROGRAM(WS-MENU-PGM)
                       COMMAREA(DFHCOMMAREA) END-EXEC
               WHEN OTHER
                   EXEC CICS XCTL PROGRAM(WS-NEXT-PGM)
                       COMMAREA(DFHCOMMAREA) END-EXEC
           END-EVALUATE.

The three sites are on lines 24, 27 and 30. In cobble's node names they are MAIN-PARA/2.when.0.0, MAIN-PARA/2.when.1.0 and MAIN-PARA/2.when.2.0. The operands are WS-FIRST-PGM@working_storage[0:8], WS-MENU-PGM@working_storage[8:16] and WS-NEXT-PGM@working_storage[16:24].

Step by step

Each site gets its own walk, over its own operand. The three walks are shown side by side because they visit the same nodes. Each row is the set arriving at that node, which is what the walk reports for a site. Values are shown as stored: PIC X(8) pads 'PROGB' with three spaces, written ␣. The program has no loop, so the worklist visits each node once, in order.

Three forward walks over PROGA (7 steps)

Entry. Each operand starts at what the program holds before any statement runs. WS-FIRST-PGM is covered by a VALUE, so it starts at that literal. The other two have no VALUE: uninitialised. An operand in LINKAGE would start as inbound-linkage.

operand arriving

WS-FIRST-PGM {'PROGB␣␣␣'}

WS-MENU-PGM {} + uninitialised

WS-NEXT-PGM {} + uninitialised
IF WS-FLAG = 'Y' writes nothing. Both arms start from the same sets.

operand arriving at each arm

WS-FIRST-PGM {'PROGB␣␣␣'}

WS-MENU-PGM {} + uninitialised

WS-NEXT-PGM {} + uninitialised
Each arm moves a literal into all eight bytes of WS-MENU-PGM. The write is exact, not weak, covers the whole operand, and its values are complete: it replaces. The then arm leaves {'PROGB␣␣␣'}, the else arm {'PROGC␣␣␣'}. The uninitialised doubt is gone on both: the write killed it.

operand leaving then leaving else

WS-FIRST-PGM {'PROGB␣␣␣'} {'PROGB␣␣␣'}

WS-MENU-PGM {'PROGB␣␣␣'} {'PROGC␣␣␣'}

WS-NEXT-PGM {} + uninitialised {} + uninitialised

operand	arriving
WS-FIRST-PGM	{'PROGB␣␣␣'}
WS-MENU-PGM	{} + uninitialised
WS-NEXT-PGM	{} + uninitialised

operand	arriving at each arm
WS-FIRST-PGM	{'PROGB␣␣␣'}
WS-MENU-PGM	{} + uninitialised
WS-NEXT-PGM	{} + uninitialised

The arms meet at MOVE LK-NEXT TO WS-NEXT-PGM (MAIN-PARA/1), so its arriving set is the union of both. Then the move: it covers all of WS-NEXT-PGM, but it copies rather than storing a literal, so it does not replace. Its source is in LINKAGE, and the write carries inbound-linkage, which is kept.

operand	arriving	leaving
WS-FIRST-PGM	{'PROGB␣␣␣'}	{'PROGB␣␣␣'}
WS-MENU-PGM	{'PROGB␣␣␣', 'PROGC␣␣␣'}	{'PROGB␣␣␣', 'PROGC␣␣␣'}
WS-NEXT-PGM	{} + uninitialised	{} + inbound-linkage

Line 24: XCTL PROGRAM(WS-FIRST-PGM). Its walk arrives with {'PROGB␣␣␣'} and no doubt. Trimmed, that spells PROGB. Resolved to PROGB. The XCTL's own write to DFHCOMMAREA does not overlap working storage, so it changes none of the three sets.

line 24 → PROGB
Line 27: XCTL PROGRAM(WS-MENU-PGM). Arrives with {'PROGB␣␣␣', 'PROGC␣␣␣'} and no doubt. Resolved to PROGB and PROGC.

line 24 → PROGBline 27 → PROGB, PROGC
Line 30: XCTL PROGRAM(WS-NEXT-PGM). Arrives with {} + inbound-linkage. That doubt is not uninitialised, so the site is unresolved: a caller supplies the name. The site goes to the cross-program walk later.

line 24 → PROGBline 27 → PROGB, PROGCline 30 unresolved: inbound-linkage

What each site is charged, and PROGA's entry row (3 steps)

The entry rows of the other members, on the commarea slot. Their union is what an unresolved commarea site is charged. PROGA's own row is in it too, because PROGA reads LK-NEXT (bytes 0–8) to pick its target.

member entry, commarea

PROGA [0:8]

PROGB [20:28]

PROGC [40:48]

PROGD [60:68]

union [0:8] [20:28] [40:48] [60:68] = 32 bytes
The charge at each site, as --explain PROGA reports it. A resolved site pays only for the programs it reaches. The unresolved one pays the union, including PROGD, which nothing can reach from here.

site resolution callees charge

line 24 resolved PROGB 8 bytes

line 27 resolved PROGB, PROGC 16 bytes

line 30 unresolved none 32 bytes
PROGA's entry row across rounds. In round 1 no row is known yet, so only its own target read counts: 8 bytes. In round 2 the charges arrive. The 32 bytes come from line 30 alone; lines 24 and 27 add nothing it does not already hold.

round PROGA on entry

1 [0:8], 8 bytes

2 [0:8] [20:28] [40:48] [60:68], 32 bytes

member	entry, commarea
PROGA	[0:8]
PROGB	[20:28]
PROGC	[40:48]
PROGD	[60:68]
union	[0:8] [20:28] [40:48] [60:68] = 32 bytes

site	resolution	callees	charge
line 24	resolved	PROGB	8 bytes
line 27	resolved	PROGB, PROGC	16 bytes
line 30	unresolved	none	32 bytes

round	PROGA on entry
1	[0:8], 8 bytes
2	[0:8] [20:28] [40:48] [60:68], 32 bytes

The --sites file for the same run holds one row per dynamic site, with the operand, the result, the reasons, and every write in the program that touches the operand. The VALUE clause is not a write, so line 24 lists none.

{"member":"PROGA","resolved":true,"place":"MAIN-PARA line 24","transfer":"XCTL",
 "operand":"WS-FIRST-PGM@working_storage[0:8]","callees":["PROGB"],"reasons":[],
 "definitions":[]}
{"member":"PROGA","resolved":true,"place":"MAIN-PARA line 27","transfer":"XCTL",
 "operand":"WS-MENU-PGM@working_storage[8:16]","callees":["PROGB","PROGC"],"reasons":[],
 "definitions":[
  {"place":"MAIN-PARA line 17","kind":"literal","values":["PROGB   "],"sources":[],"reasons":[]},
  {"place":"MAIN-PARA line 19","kind":"literal","values":["PROGC   "],"sources":[],"reasons":[]}]}
{"member":"PROGA","resolved":false,"place":"MAIN-PARA line 30","transfer":"XCTL",
 "operand":"WS-NEXT-PGM@working_storage[16:24]","callees":[],"reasons":["inbound-linkage"],
 "definitions":[
  {"place":"MAIN-PARA line 21","kind":"copy","values":[],"sources":["LK-NEXT@linkage[0:8]"],
   "reasons":["inbound-linkage"]}]}

Other writes, one program each

Small programs, each ending in XCTL PROGRAM(WS-PGM) COMMAREA(WS-AREA) unless noted, run through the same stage. The reasons column is the site's; for the copy, the write's own reasons say something different, which the next section explains.

what reaches the operand	resolved	reasons
`IF ... MOVE 'PROGB' TO WS-PGM END-IF`, no ELSE, no VALUE	yes, PROGB	uninitialised
`MOVE 'PROGB' TO WS-OTHER`, `MOVE WS-OTHER TO WS-PGM`	no	not-a-literal (write: copy, uninitialised)
`MOVE 'PROGB' TO WS-PGM`, then `LINK PROGRAM('PROGC') COMMAREA(WS-PGM)`	no	from-callee
`EXEC CICS RETRIEVE INTO(WS-PGM)`	no	not-a-literal
`RETURN TRANSID(WS-TRAN)`, `VALUE 'TRNB'`, CSD maps TRNB to PROGB	yes, PROGB	none
`START TRANSID(WS-TRAN) FROM(WS-AREA)`, same VALUE and CSD	yes, PROGB	none
`RETURN TRANSID(WS-TRAN)`, `VALUE 'ZZZZ'`, not in the CSD	yes, nothing	transaction-not-in-csd
either TRANSID case, run without `--config`	no	no-csd

The rule

initial(o) = inbound-linkage, if o is in LINKAGE
           = the VALUE bytes covering o, if a VALUE covers it
           = uninitialised, otherwise
in(entry) = initial(o);  in(n) = ⋃ out(p) for every predecessor p
out(n) = in(n) after each write w at n:
  w misses o's bytes                                    → unchanged
  w replaces o (strong, exact, covers o, literal values) → w's values, sliced to o
  otherwise                                             → w's reasons − {uninitialised}, or not-a-literal if none remain

resolved(site) ⇔ o is one exact extent ∧ reasons(in(site)) ⊆ {uninitialised}
callees(site)  = program names among values(in(site)); none → resolved to nothing, no-program-name

transaction site: literal TRANSID → resolved to it; then through the CSD
  no CSD              → unresolved, no-csd
  id not in the CSD → that id reaches nothing; transaction-not-in-csd; still resolved

charge(site, slot) = ⋃ entry(c)[slot] for c in callees(site), if resolved
                       = ⋃ entry(m)[slot] for every member m, otherwise

A callee outside the corpus, or one that does not receive that slot, is charged every byte of the area. A site resolved to nothing is charged nothing.

Why uninitialised is accepted, and a copy is not

Uninitialised means one thing here: on some path, no write reached the operand and no VALUE covers it. That storage is this program's own working storage. No caller, callee or file put anything in it. So the only names the site can reach are the literals on the other paths. If that path really runs, the operand holds whatever the storage started as, not a name some other program chose.

A copy is different. The writes are computed once per program, without a state, so a MOVE WS-OTHER TO WS-PGM looks up WS-OTHER in an empty state and finds it "unwritten". That is a fact about the empty state, not about the program: WS-OTHER may well hold 'PROGB' by then, or a name read from a file. The walk does not follow the copy to find out. So the copy's uninitialised reason is dropped and the write is not-a-literal. In the --sites row above the copy's own reasons still show uninitialised, and the site's reason is not-a-literal. Accepting it would resolve the site to nothing and charge nothing, while the combine, following the copy, links it to PROGB.

A copy whose source carries a real reason keeps it: a copy out of LINKAGE is inbound-linkage, a LINK or CALL BY REFERENCE that hands the operand over is from-callee, a READ into it is from-file. A RETRIEVE INTO is modelled as CICS state with no literal: not-a-literal.

What goes wrong

One unresolved site is enough. In the example, two of three sites resolved, and PROGA's entry row is still 32 bytes, because line 30 alone pulls in the union. Local resolution shrinks a row only when it resolves every unresolved site that hands over that area.
A copy of a literal stays unresolved. MOVE 'PROGB' TO WS-OTHER then MOVE WS-OTHER TO WS-PGM is plainly PROGB, but the walk tracks one operand and does not follow copies. The site pays the union. The later cross-program walk does follow it.
Only one exact extent. An operand that could be several places, such as a subscripted WS-PGMS(I), gets operand-not-one-exact-extent and stays unresolved here, even though the combine can resolve it.
Conditions are not evaluated. A literal on a branch that never runs still counts. The site is resolved to more programs than it really reaches and is charged their rows too. That is loose, not wrong.
Values that are not program names. If no value looks like a program name, the site is resolved to nothing and charged nothing, with no-program-name. That matches the combine, which links such a site to nothing.
The walk starts at the program's entry. It assumes storage holds its VALUE or nothing on entry. A CALLed batch subprogram keeps its working storage between calls; a literal written after the site on an earlier call is not a reaching definition here. The value is still one of this program's literals, but the site's callees can miss it. (Read from the code; not reproduced.)
Without a CSD, transactions say so. A RETURN TRANSID or START without --config is unresolved with no-csd, not resolved to nothing. Resolving to nothing would charge nothing and drop the bytes the started program needs.

In cobble

The resolution runs inside cobble-dataflow-area-need, once for each member before the rounds. One graph is built per program, and each dynamic site gets its own walk over it. The answers split into resolved sites and unresolved ones. A resolved site is charged its callees' rows; an unresolved one, the union of every member's entry need. Transaction ids from RETURN TRANSID and START are mapped to programs through the CSD files of the corpus config named by --config.

--sites writes one row per dynamic site, with each write that touches the operand marked as a literal, a copy or other. Sites that a finished fixpoint and combine resolved are added from --fixpoint-dir and --combined-dir. The command is documented under cobble-dataflow-area-need in the field dataflow reference.

Next: rounds across programs, and walking only what changed.