Answering every walk once: strongly connected components and a memo

Read first: Value sets and dynamic calls, Visiting a graph, Strongly connected components

A jump such as XCTL PROGRAM(CA-NEXT-PGM) goes to whatever name another program put in the commarea, so the combine walks back through the programs that handed it in. On a large CICS corpus each of about 19,000 jumps walked on its own; one walk reached about 311,000 vertices, and its neighbours walked the same chains again.

PROGB and PROGC both jump to the commarea's name, and both walks go back round one three-program ring to PROGD, which wrote 'PROGE'. Walked one by one they expand 10 places. Keep each place's answer and solve the ring as one strongly connected component, and they expand 6; both get {PROGE}.

Vocabulary: the COBOL/CICS primer. A place is a program, a node (statement) in it and a byte range.

The example

Four programs hand an 8-byte commarea round: a ring PROGA → PROGB → PROGC → PROGA, entered from outside by PROGD with 'PROGE' in the first 8 bytes. Dashed arrows are the two dynamic jumps to answer.

flowchart TD
    D["PROGD: puts 'PROGE' in the commarea"] -->|XCTL| A[PROGA]
    A -->|XCTL| B[PROGB]
    B -->|XCTL| C[PROGC]
    C -->|XCTL| A
    B -.->|"XCTL PROGRAM(CA-NEXT-PGM)"| QB["?"]
    C -.->|"XCTL PROGRAM(CA-NEXT-PGM)"| QC["?"]

The answer for both jumps, and the places each walk expands (from the table at the start of the step-by-step):

The literal transfers resolve on their own, so by the round shown here the combine knows four links, the four solid arrows above: A→B, B→C, C→A and D→A. Six places matter. Each dynamic jump starts at its own node, on CA-NEXT-PGM (linkage bytes [0, 8)). Each literal transfer is a place on WS-AREA (working-storage bytes [0, 8)) at that XCTL. In the place graph below, each arrow points from a place to a place its bytes were copied from (the walk's direction, backwards against the transfers):

flowchart TD
    subgraph ring["one component"]
        AX["A-xctl"] --> CX["C-xctl"]
        CX --> BX["B-xctl"]
        BX --> AX
    end
    BJ["B-jump"] --> AX
    CJ["C-jump"] --> BX
    AX --> DX["D-xctl: finds PROGE"]

The lines that matter. PROGC has the same shape as PROGB but transfers to PROGA; PROGA is the same without the jump:

* PROGB
MOVE DFHCOMMAREA TO WS-AREA.
IF CA-NEXT-PGM NOT = SPACES
* B-jump
    EXEC CICS XCTL PROGRAM(CA-NEXT-PGM)
         END-EXEC
END-IF.
* B-xctl
EXEC CICS XCTL PROGRAM('PROGC')
     COMMAREA(WS-AREA) END-EXEC.

* PROGD: D-xctl finds 'PROGE'
MOVE 'PROGE' TO WS-NEXT-PGM.
EXEC CICS XCTL PROGRAM('PROGA')
     COMMAREA(WS-AREA) END-EXEC.

Read a row of the table like this, taking row 4: the bytes at B-xctl were copied from DFHCOMMAREA by PROGB's MOVE, and PROGB's commarea is handed in by PROGA's transfer, so B-xctl leads to A-xctl. Rows 3, 4 and 5 make the ring A-xctl → C-xctl → B-xctl → A-xctl, the box in the place graph, running opposite to the transfers in the program graph because the walk goes backwards.

Row 1 is the strip in the problem: the jump reads CA-NEXT-PGM and the MOVE behind B-xctl copies from DFHCOMMAREA: two names, the same linkage bytes, so one place. (What PROGA hands over is its own WS-AREA, which is A-xctl.) Steps inside a program are collapsed in the table: from row 3 the walk really goes through PROGA's own MOVE DFHCOMMAREA TO WS-AREA to the top of its linkage section before crossing to C-xctl and D-xctl, the transfers that hand PROGA its commarea.

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

       IDENTIFICATION DIVISION.
       PROGRAM-ID. PROGB.
      *    Same data division as PROGA.
       PROCEDURE DIVISION.
       MAIN-PARA.
           MOVE DFHCOMMAREA TO WS-AREA.
           IF CA-NEXT-PGM NOT = SPACES
               EXEC CICS XCTL PROGRAM(CA-NEXT-PGM) END-EXEC
           END-IF.
           EXEC CICS XCTL PROGRAM('PROGC') COMMAREA(WS-AREA) END-EXEC.

       IDENTIFICATION DIVISION.
       PROGRAM-ID. PROGC.
      *    Same data division as PROGA.
       PROCEDURE DIVISION.
       MAIN-PARA.
           MOVE DFHCOMMAREA TO WS-AREA.
           IF CA-NEXT-PGM NOT = SPACES
               EXEC CICS XCTL PROGRAM(CA-NEXT-PGM) END-EXEC
           END-IF.
           EXEC CICS XCTL PROGRAM('PROGA') COMMAREA(WS-AREA) END-EXEC.

       IDENTIFICATION DIVISION.
       PROGRAM-ID. PROGD.
       DATA DIVISION.
       WORKING-STORAGE SECTION.
       01  WS-AREA.
           05  WS-NEXT-PGM      PIC X(8).
       PROCEDURE DIVISION.
       MAIN-PARA.
           MOVE 'PROGE' TO WS-NEXT-PGM.
           EXEC CICS XCTL PROGRAM('PROGA') COMMAREA(WS-AREA) END-EXEC.

Step by step

The combine answers programs in name order, so PROGB's jump goes first. Two naive walks expand 10 places (the first two rows below); the memo expands 6 (the last two), since the walk from C-jump stops at B-xctl, already answered.

The walk below is Tarjan's algorithm with the memo. The path is the depth-first walk's current route; the stack holds places not yet in a finished component. Each place gets an index, the order it was first visited, and a low value, the lowest index it can get back to through places still in play. A-xctl's two successors in the place graph are taken C-xctl first here; the other order changes the visits, not the answers.

A third jump starting at any of these six places would expand nothing: the memo returns the stored answer straight away, from the last table of step 12. Both answers are what the naive walks in the table above the walk give: {PROGE}, and both naive walks would meet a place twice going round the box in the place graph.

The gap grows with the ring. A walk from inside a ring of n places expands all n; n jumps on it expand about n² between them. With the memo the ring is expanded once. The first two rows below are this page's example, from the table above the walk; the last is a test of a 15-program XCTL ring, with identical output.

Why each place is solved once

Step 12 of the walk is the saving: C-jump's only successor, B-xctl, was already answered, so the walk took that answer and went no further. That is safe because a place's answer does not depend on who is asking. It is the join of what the place finds itself and the answers of every place it leads to: D-xctl's answer is {PROGE} whether the walk got there from B-jump or from C-jump.

Cycles get in the way of "work out the successors first". In steps 3 to 5 the walk went A-xctl → C-xctl → B-xctl and back to A-xctl: none of them can be finished before the others. But they do not need to be: every place on a cycle reaches every other, so they all reach exactly the same set of places and all have the same answer:

A maximal set of places that all reach each other is a strongly connected component; the box in the place graph is one, and every place outside it is a component on its own. Solve the component as one unit: its answer is the join of what each member finds itself, plus the answers of the places the component leads out to. The box has one arrow leaving it, A-xctl → D-xctl.

Tarjan's algorithm finds the components during one depth-first walk, and it finishes each component only after every component it leads to. That is exactly the order the answers need. The walk from B-jump finished the components in this order (steps 9, 10 and 11), and the second walk, from C-jump, finished the last one (step 12):

Each chip comes after every chip its places lead to, so each answer is built from answers already settled. When the walk backs out of a place whose low equals its own index, nothing below it reaches anything older, so that place and everything above it on the stack form one component: pop them, give them their shared answer, and move on. Step 5 is where B-xctl's low dropped to A-xctl's index, 1, and step 10 is where A-xctl, low 1 and index 1, popped the box off the stack.

The textbook version is recursive, one call per place on the current path. Cobble keeps the path in explicit lists instead: the Path row in each step of the walk is that list, four places long at step 4:

Path at step 4

The combine had already crashed once on Python's recursion limit when it recursed once per program, and a walk across a corpus can be millions of places deep.

Two smaller changes make each step cheaper. A step that reaches the top of a program asks which links lead into it; it used to scan every link the round knew, and a profiler showed every sample inside that scan. The links are now indexed by what each step looks them up by. For the example's four links, the lookup by callee is the table below: when A-xctl reaches the top of PROGA's linkage (walk step 2), it reads row PROGA and gets its two successors without looking at the other two links.

And a place is told apart by its bytes alone. In the strip in the problem, DFHCOMMAREA and CA-NEXT-PGM both span bytes [0, 8): reached under either name (or a REDEFINES name over the same bytes) it is one place, since the walk never reads the name.

What one walk per jump costs

The strip is B-jump, row 1 of the example's table: program PROGB, node MAIN-PARA/1.then.0 (the XCTL inside the IF), bytes [0, 8) of the linkage section, holding the name PROGD wrote. The combine asks what values the outlined bytes can hold, and answers by walking back from that place. Each step looks at one place, collects any literal values written there, and lists the places the bytes were copied from: a MOVE inside the program, or, at the top of a program's linkage section, the caller that handed the commarea in. From the strip, that is PROGA's transfer; from there, PROGC's and PROGD's.

The walk's answer is everything found at every place it reaches, joined. Done once per jump, as in the naive rows of the table above the walk, the cost is the number of jumps times the number of places each one reaches. Here are the programs each jump walks back through, one chip per place expanded:

From PROGB's jump

From PROGC's jump

The second row repeats four of the first row's places: 10 expansions where 6 different places exist. When most jumps reach the same few hundred places, almost all of that work is repeated.

Why it matters on a real corpus

The combine, the last stage of cobble's field dataflow, resolves dynamic call targets such as CALL WS-PGM across programs. When the name came in a commarea, the answer is only found by walking back through the program that sent it, and the one that sent it there.

• CICS programs hand control in rings. In the example, PROGA → PROGB → PROGC → PROGA is such a ring, and the 8-byte commarea goes round with it. Walked backwards, the graph of "where could these bytes have come from" is full of cycles, and every program on a ring sees the same handful of commarea bytes.
• Many questions, one graph. The example's two jumps walk back over the same ring and reach the same PROGD. On a large CICS corpus each jump started its own walk, and the jumps next to the one in the table below walked the same commarea chains again:

  large CICS corpus	about
  programs	3,800
  jumps, each walked on its own	19,000
  vertices reached by one walk	311,000
  program positions in that walk	850

• The same shape appears whenever many starts ask a reachability question of one fixed graph: which sources can taint this sink, which allocation sites can this variable point to. Read the dashed jumps in the example's graph as sinks and PROGD as a source. Solving the graph once and sharing the answers is the standard way out.

The rule

Each line of the box was applied somewhere in the walk:

Line 1 holds for every member of a component at once, because they all reach the same places; that is why line 2 can give the whole box one answer. Tarjan settles a component only after every component it leads to (the chips in the intuition), so the answers line 2 needs are always there.

The join has to be the walk's join, and it must not care about order or repetition: here, set unions of values, reasons and outside callers, and an "or" of the revisit flag. A naive walk from B-jump meets A-xctl twice in the place graph, once from B-jump and once coming round the box from B-xctl; a union of {PROGE} with {PROGE} is still {PROGE}, and step 10 joins the box's members in any order to the same {PROGE}. That is what lets a stored answer stand in for walking again.

The revisit flag. Besides values, the combine asks whether a walk from a place would reach some place twice: exactly when what it reaches is not a tree, since a tree on k places, counting the start, has k − 1 edges. Line 5, counted on the place graph:

Most places settle the flag when their component settles, without counting. A component of two or more places is a cycle, so every member revisits: row 2, settled in step 10. A single place with an edge to itself, the same successor twice, or a successor that revisits, revisits: rows 3 and 4, B-jump in step 11 and C-jump in step 12, each because its successor revisits. A single place with at most one successor, which does not revisit, does not: row 1, D-xctl in step 9, with no successors at all. What is left is a single place with several successors that do not revisit, like the top of a diamond. The example has none; the shape is this abstract four-place graph, not drawn from the example's programs:

flowchart TD
    dP["P"] --> dQ["Q"]
    dP --> dR["R"]
    dQ --> dS["S"]
    dR --> dS

Neither Q nor R revisits, yet their reach overlaps at S: P reaches 4 places over 4 edges, not 3, so it revisits. That one is decided on demand by walking the successor lists the memo already keeps, counting edges against places, as in the last bullet of what goes wrong. Nothing is expanded.

The combine reads the flag in one case only: when a jump's answer has no values and no reasons. A walk that went round a ring and found nothing is reporting that the bytes come from whoever first started the ring, so the target is marked as received from outside (inbound-linkage) rather than left empty with no explanation. In the example, without PROGD, both jumps would end that way: the place graph loses D-xctl, B-jump then reaches 4 places over 4 edges, and finds nothing. Run on PROGA, PROGB and PROGC alone, cobble's combine writes these two targets:

{"caller": "PROGB", "node": "MAIN-PARA/1.then.0", "transfer": "CICS_XCTL", "expression": "CA-NEXT-PGM", "candidates": [], "reasons": ["inbound-linkage"], "dropped": [], "outside": []}
{"caller": "PROGC", "node": "MAIN-PARA/1.then.0", "transfer": "CICS_XCTL", "expression": "CA-NEXT-PGM", "candidates": [], "reasons": ["inbound-linkage"], "dropped": [], "outside": []}

What goes wrong

• The graph must not change while the memo lives. A stored answer is only right for the links it was computed with. Each round of the combine finds new links: a target's values become new edges, which feed other walks (see rounds couple targets in hop limits), so the cross-program memo is built per round and dropped. In the example, round 1 starts with no links: B-jump's walk stops at the top of PROGB's linkage with no values, and C-jump's the same. Round 2 has the four links. Kept into round 2, the round-1 memo would hand B-jump its round-1 answer instead of {PROGE}.

  round	links known	places answered	B-jump's values
  1	0	2: B-jump, C-jump	none
  2	4	6: the place graph	{PROGE}

  Inside one program the facts and copies never change, so the second memo, over positions inside a program, lives for the whole run.
• The memo only shares places that are equal. In the strip below, PROGA's WS-AREA and WS-NEXT-PGM are the same bytes [0, 8): one place, A-xctl. If some copy moved only the first four bytes (the bottom span), the same node reached under [0, 4) would be a second place, expanded on its own, and so would the places behind it, which inherit the narrower range. Copies that move part of a field, and links whose windows line up on different lengths, narrow the range like this, so one node can turn into many places. Telling places apart by bytes rather than field name removed the duplicates that were only names (the top two spans in the strip below); it does nothing for real byte-range fragmentation (the bottom one).
  0

  1

  2

  3

  4

  5

  6

  7

  WS-AREA

  WS-NEXT-PGM

  [0, 4) copy

  P

  R

  O

  G

  E

  ␣

  ␣

  ␣
• One component can be most of the corpus. In the example the box is 3 of the 6 places. On the large corpus the links joined into one cyclic group, and one solve grew past a million places on the stack before anything settled. The memo makes each place cost once; it does not make the set of places small. Hop limits bound that. A hop limit also puts the crossing count into the place, so the same bytes reached after 1 crossing and after 2 are separate places, and the memo shares less. With a limit of 2 on the example, A-xctl appears twice in the table below, and there are 7 places where there were 6. C-jump's walk now stops at A-xctl before it reaches D-xctl, so its target says hop-limit with no names:

  place	crossings	reached from
  B-jump	0	start
  A-xctl	1	B-jump
  C-xctl	2	A-xctl (stops: limit)
  D-xctl	2	A-xctl
  C-jump	0	start
  B-xctl	1	C-jump
  A-xctl	2	B-xctl (stops: limit)

• A component's answer is all-or-nothing. Every member gets the full join. That is exact for reachability, since every member does reach it all, but it means one wide entry into a ring widens every jump on the ring. Add a fifth program to the example that enters the ring at PROGB with another name:

         IDENTIFICATION DIVISION.
         PROGRAM-ID. PROGX.
        *    Same data division as PROGD.
         PROCEDURE DIVISION.
         MAIN-PARA.
             MOVE 'PROGF' TO WS-NEXT-PGM.
             EXEC CICS XCTL PROGRAM('PROGB') COMMAREA(WS-AREA) END-EXEC.

  B-xctl (and B-jump, which reads the same commarea) now also leads to a new place, X-xctl, which finds {PROGF}. The box now has two edges leaving it, so all three members, and both jumps behind them, get both names:

  place	answer
  D-xctl	{PROGE}
  X-xctl	{PROGF}
  A-, B-, C-xctl	{PROGE, PROGF}
  B-jump, C-jump	{PROGE, PROGF}

• The revisit check can still walk. For diamond-shaped starts it walks the stored successor lists. On the diamond above, taking places off a stack, last in first out:

  takes	follows	edges counted	places reached
  P	Q, R	2	P, Q, R
  R	S	3	P, Q, R, S
  S	nothing	3	P, Q, R, S
  Q	S, already reached	4	P, Q, R, S

  4 edges against 4 − 1: P revisits. That is cheap compared to expanding, but it is not free on a large reach, and its result is cached per start.
• The memo is mutable. It is the one place in the combine that mutates state, and is excluded from the functional-style lint for that reason: threading the memo and the stack through as values would copy them at every step. In the walk, steps 9 to 12 add their rows (amber) to one Answered table that grows in place, and the Stack row shrinks in place.

In cobble

The combine (cobble-dataflow-combine) holds two memos. Run on the example's four programs, its log for round 2 and its two targets are below: the log's six places are the place graph's six, and both targets carry the {PROGE} of step 11 and step 12.

[0h00m00s] combine:   round 2: answered 4 programs, 6 jumps in 0.0s; 6 vertices answered once each
{"caller": "PROGB", "node": "MAIN-PARA/1.then.0", "transfer": "CICS_XCTL", "expression": "CA-NEXT-PGM", "candidates": ["PROGE"], "reasons": [], "dropped": [], "outside": []}
{"caller": "PROGC", "node": "MAIN-PARA/1.then.0", "transfer": "CICS_XCTL", "expression": "CA-NEXT-PGM", "candidates": ["PROGE"], "reasons": [], "dropped": [], "outside": []}

Of the two memos, the first answers jumps across programs. Each round builds one over the places it reaches: it resolves a place inside its program and follows each stop across links. A place met again on a cycle is flagged, and an empty answer so flagged becomes inbound-linkage. Links are found through an index by (callee, parameter), (caller, node, parameter) and (callee, node), not by a scan; the links-into table is the first of those for the example. The second memo works inside one program and lasts the whole run. Both tell places apart by their bytes alone, not by the field name that reached them.

The command and its options are in the field dataflow reference. Related pages: fixpoints, traversal orders, hop limits.