Summarising a PERFORM

Read first: Fixpoints and worklists, Value sets and dynamic calls

The solution in one example

MAIN-PARA.
    MOVE 'PROGA' TO WS-A.
    PERFORM OUTER.
    MOVE WS-C TO WS-X.
    CALL WS-X.
    STOP RUN.
OUTER.
    PERFORM INNER.
    MOVE WS-B TO WS-C.
INNER.
    MOVE WS-A TO WS-B.

Values are shown with trailing spaces dropped (PROGA is 'PROGA␣␣␣'); U means uninitialised. Every field on this page is PIC X(8), laid out in declaration order: here WS-A is working-storage bytes [0,8), WS-B [8,16), WS-C [16,24); in section 4's program WS-D is [24,32); in the two-call program below, WS-V is [0,8) and WS-W [8,16).

Each performed paragraph becomes a function on just the fields it touches. Build them from the inside out:

The PERFORM OUTER in MAIN-PARA then applies fOUTER to (A = PROGA, B = U, C = U), gets (PROGA, PROGA, PROGA), and hands it to the statement after itself. WS-X is not in OUTER's fields, so it skips the call unchanged. MOVE WS-C TO WS-X makes it PROGA, and cobble resolves CALL WS-X to PROGA. Cobble's footprints for the two paragraphs are working-storage bytes [0,16) (WS-A, WS-B) and [0,24) (WS-A to WS-C).

The same functions keep two calls of one paragraph apart. P is performed twice, and a real run calls PROGA at CALL WS-W:

MAIN-PARA.
    MOVE 'PROGA' TO WS-V.        MAIN-PARA/0
    PERFORM P.                   MAIN-PARA/1
    CALL WS-W.                   MAIN-PARA/2
    MOVE 'PROGB' TO WS-V.        MAIN-PARA/3
    PERFORM P.                   MAIN-PARA/4
    STOP RUN.                    MAIN-PARA/5
P.
    MOVE WS-V TO WS-W.           P/0

P touches WS-V and WS-W, so it becomes fP(V, W) = (V, V). Each PERFORM applies it to its own state and hands the result only to the statement after itself:

So CALL WS-W sees only PROGA, as in a real run. An analysis that just follows the control-flow graph also lets the second call's result reach CALL WS-W, and says PROGA or PROGB. The rest of the page shows that failure, the rules at the boundary of a performed paragraph, the new walk, and how nested PERFORMs compose.

The method in notation

A state. A state \(\sigma\) is what the analysis knows at one point in the program: for each field \(x\), \(\sigma[x]\) is the set of values \(x\) may hold there. For a set of fields \(X\), \(\sigma[X]\) is the same, kept only for the fields in \(X\). \(U\) in a set means "may be uninitialised". (Cobble works per byte range rather than per field.)

A node. Each node \(n\) has two states: \(\mathit{in}(n)\), arriving at it, and \(\mathit{out}(n)\), leaving it. It reads the fields \(\mathit{reads}(n)\) and writes the fields \(\mathit{writes}(n)\). Let \(g_n\) be what \(n\)'s statement computes: it takes the state of the fields \(n\) reads and returns a state of the fields \(n\) writes, holding their new values. So \(g_n(\mathit{in}(n)[\mathit{reads}(n)])\) is a state, and \(g_n(\mathit{in}(n)[\mathit{reads}(n)])[x]\) is the new value set it gives field \(x\).

For example, for \(n\) = MOVE WS-V TO WS-W: \(\mathit{reads}(n) = \{\texttt{WS-V}\}\), \(\mathit{writes}(n) = \{\texttt{WS-W}\}\), and \(\mathit{out}(n)[\texttt{WS-W}] = \mathit{in}(n)[\texttt{WS-V}]\). A write is weak when cobble cannot be sure it lands on \(x\): the target is a table element whose subscript is not a constant, or a reference modification whose start or length is not a constant, or the statement is one cobble has no rule for but whose node lists fields it writes. Then the old values are kept as well. A statement with no rule and no listed writes leaves every field as it was.

The join. A node with several incoming edges gets the field-by-field union of the states leaving the nodes those edges come from, its predecessors \(p_1, \dots, p_k\). Write \(\sqcup\) for that union:

For example, \(\sigma_1[\texttt{WS-V}] = \{\text{PROGA}\}\) and \(\sigma_2[\texttt{WS-V}] = \{\text{PROGB}\}\) give \((\sigma_1 \sqcup \sigma_2)[\texttt{WS-V}] = \{\text{PROGA}, \text{PROGB}\}\). \(\bot\) is no state at all: no route has reached that point yet. \(\bot \sqcup \sigma = \sigma\), and every function on this page maps \(\bot\) to \(\bot\).

A performed range. A range \(Q\) is what one PERFORM runs: from \(Q\)'s entry node \(\mathrm{entry}_Q\) to \(Q\)'s end node \(\mathrm{end}_Q\). \(n \in Q\) means \(n\) is one of \(Q\)'s nodes: those a route from \(\mathrm{entry}_Q\) reaches without passing \(\mathrm{end}_Q\), along every edge but PERFORM and RETURN edges (so a GO TO out of \(Q\)'s paragraphs is followed), a PERFORM node stepping over its range to the statement after it unless that range is entered at \(\mathrm{entry}_Q\). Its footprint \(F(Q)\) is the set of fields that \(Q\)'s nodes read or write, together with the footprints of the ranges performed at \(Q\)'s nodes, other than ranges entered at \(\mathrm{entry}_Q\). The definition is recursive:

Cobble does not evaluate it by recursion. It starts every range's footprint at its own nodes' fields, then keeps adding the footprints of the ranges each one performs until no footprint grows. That gives the smallest sets satisfying the equation, and it stops even when PERFORMs form a cycle.

For a set of fields \(X\), let \(S(X)\) be the set of all states over \(X\): every way of giving each field in \(X\) a value set. \(Q\)'s transfer function \(f_Q\) takes the arriving state, kept to \(F(Q)\), to the state leaving \(\mathrm{end}_Q\), kept to \(F(Q)\) as well, or to \(\bot\) when no route reaches \(\mathrm{end}_Q\). Fields in \(F(Q)\) that \(Q\) only reads come out as they went in.

For example, for \(P\) = MOVE WS-V TO WS-W, \(F(P) = \{\texttt{WS-V}, \texttt{WS-W}\}\) and

A PERFORM node \(p\) of range \(Q\) applies \(f_Q\) to the fields in \(F(Q)\) and keeps every other field as it arrived. Let \(\mathbb{F}\) be the set of all the program's fields, so \(\mathbb{F} \setminus F(Q)\) is the fields \(Q\) never touches, and write \(\sigma_1 \oplus \sigma_2\) for putting together two states over disjoint sets of fields:

with \(\bot \oplus \sigma = \bot\). Where \(p\)'s state goes depends on whether any edge of the graph leads to \(\mathrm{end}_Q\):

\(\mathit{resume}(p)\) is the statement right after that PERFORM; sending \(\bot\) sends nothing. In the second case the graph says \(Q\) never returns, so the statement after \(p\) would be dead. Cobble keeps \(p\)'s edge to it anyway, because the graph can be wrong (an ALTERed GO TO, control flow the parser dropped), and passes on the state from before the PERFORM, ignoring \(Q\)'s writes.

Composition. For a range whose nodes run in a straight line \(n_1, \dots, n_k\), its function is theirs applied in order, with a nested PERFORM node's rule standing in for the inner range. With branches or loops, \(f_Q(\sigma)\) is the state leaving \(\mathrm{end}_Q\) once a walk of \(Q\) from \(\sigma\) stops changing, or \(\bot\) if the walk never reaches \(\mathrm{end}_Q\).

For example, with OUTER = PERFORM INNER, then MOVE WS-B TO WS-C, and INNER = MOVE WS-A TO WS-B:

The fixpoint, with summaries. \(\mathit{walk}(Q, \sigma)\) walks range \(Q\) from input \(\sigma\) and returns \(\mathit{out}(\mathrm{end}_Q)\), the state leaving \(Q\)'s end node, or \(\bot\) if the walk never reached it. \(\mathit{results}\) is a table of finished walks, keyed by (range, input). The worklist \(L\) holds the nodes whose arriving state has grown and must be visited again. \(\mathit{succ}_Q(n)\) is \(n\)'s successors along every edge but PERFORM and RETURN edges, and none if \(n\) is \(\mathrm{end}_Q\); a PERFORM node with a \(\mathit{resume}\) has no other such edge. \(\sigma' \not\sqsubseteq \mathit{in}(m)\) means \(\mathit{in}(m) = \bot \neq \sigma'\), or \(\sigma'\) has, for some field, a value \(\mathit{in}(m)\) lacks. \(\mathrm{end}_Q\) is visited like any other node; it differs only in having no successors, so its \(\mathit{out}\) is returned rather than passed on. The whole analysis is \(\mathit{walk}(T, \sigma_{\text{start}})\), from the program's starting state, where \(T\) is the whole program taken as a range with no end node: \(\mathrm{entry}_T\) is the first paragraph's start node, and \(\mathit{succ}_T\) cuts no node's successors.

The PERFORM stack. The recursion of \(\mathit{walk}\) is a stack of PERFORMs. Reaching a PERFORM node \(n\) pushes a new \(\mathit{walk}\) for its range; when that walk returns, it is popped and the outer walk is still at \(n\), so it reads \(\mathit{resume}(n)\) from the right node. That is how each call's result returns to its own call site, which a walk following RETURN edges cannot tell apart. In section 4's example, where MAIN-PARA runs PERFORM P1 THRU P2 and paragraph P1 runs PERFORM SET-B, the stack is at most three deep: \(T\), then the range from P1's start to P2's end, then SET-B.

Left out for brevity: cobble also keeps the set of entry nodes of the ranges on the stack. A PERFORM of a range whose entry is in that set ends that route (COBOL leaves recursive PERFORM undefined), so PERFORM P1 inside a walk of P1 THRU P2 is refused. The table's key also holds the part of that set the range's walk can come to a PERFORM of. A PERFORM statement reached again, with the same set and an input that contains its last one, continues its last walk instead of starting over.

1. The problem: a walk that follows the graph

MAIN-PARA.
    MOVE 'PROGA' TO WS-V.  MAIN-PARA/0
    PERFORM P.             MAIN-PARA/1
    CALL WS-W.             MAIN-PARA/2
    MOVE 'PROGB' TO WS-V.  MAIN-PARA/3
    PERFORM P.             MAIN-PARA/4
    STOP RUN.              MAIN-PARA/5
P.
    MOVE WS-V TO WS-W.     P/0

flowchart TD
    M1["MAIN-PARA/1 PERFORM P"] -->|PERFORM| PL["P#label"]
    M4["MAIN-PARA/4 PERFORM P"] -->|PERFORM| PL
    PL --> P0["P/0 MOVE WS-V TO WS-W"]
    P0 --> PE["P#end"]
    PE -->|RETURN| M2["MAIN-PARA/2 CALL WS-W"]
    PE -->|RETURN| M5["MAIN-PARA/5 STOP RUN"]

Both mistakes happen at P: its start joins the two calls' states, and its end sends the result to both resume points. The walk also goes round MAIN-PARA/2 → /3 → /4 → P → MAIN-PARA/2, a cycle the program does not have.

2. Cutting out a range: the contract

The fix is to stop treating a performed paragraph as part of the graph the walk wanders through, and treat it as a unit with a boundary. Each PERFORM names a range: where it enters, and the end node it returns from.

At the boundary of a range R, the contract is:

• Footprint. R's footprint is every byte R's nodes read or write (every node reached from R's entry before its end, GO TOs out of R's paragraphs followed), plus the footprint of every range R performs. For P it is bytes [0,16): WS-V and WS-W.
• In. A walk of R starts at R's entry with the caller's state cut to the footprint. Bytes outside it are not passed in.
• Inside. The walk follows ordinary edges (flow, test outcomes, GO TO, fall-through into the next paragraph). It never follows a RETURN edge. A PERFORM inside R is handled by this same contract, not by following its edges. The walk stops at R's end node.
• Out. The state after R's end node is the only thing handed back. It goes to the resume node of the PERFORM that started the walk, which the PERFORM node records: MAIN-PARA/1 resumes at MAIN-PARA/2, MAIN-PARA/4 at MAIN-PARA/5. A walk that never reaches R's end hands back nothing. If no edge leads to R's end at all, the PERFORM has no resume node: it keeps its edge to the next statement and sends the state it arrived with along it.
• Frame. The bytes that were not passed in are put back unchanged. R cannot have changed them: nothing in R, or in any range R performs, writes them.

What this implies: R becomes a function fR from a state over its footprint to a state over its footprint, its transfer function. A PERFORM of R is then an ordinary node whose transfer is "cut, apply fR, put the rest back". For P, f maps (WS-V = v, WS-W = w) to (WS-V = v, WS-W = v).

3. The walk now

The same program under the contract, printed step by step from cobble's current fixpoint. Numbered rows are visits of the top-level walk, which starts at MAIN-PARA. Under a PERFORM's visit are the rows of that call: the cut, whether the table already had a result, the separate walk of the range (states arriving at each of its nodes), and what is handed back and where. P touches both fields, so nothing is held out here; the opening example and section 4 show fields held out.

MAIN-PARA.
    MOVE 'PROGA' TO WS-V.  MAIN-PARA/0
    PERFORM P.             MAIN-PARA/1
    CALL WS-W.             MAIN-PARA/2
    MOVE 'PROGB' TO WS-V.  MAIN-PARA/3
    PERFORM P.             MAIN-PARA/4
    STOP RUN.              MAIN-PARA/5
P.
    MOVE WS-V TO WS-W.     P/0

Compare with section 1. Each walk of P starts from one call's state, so nothing is joined at P#label. Each hand-back goes to one node: MAIN-PARA/2 for the first call, MAIN-PARA/5 for the second. The top-level walk visits each statement once, with no cycle, and WS-W arrives at CALL WS-W (visit 4) as PROGA only.

4. Composing ranges

When a range performs another, its function is built from the inner one. Which function a PERFORM applies depends on its range, not just on the paragraph it names:

MAIN-PARA.
    MOVE 'PROGA' TO WS-A.  MAIN-PARA/0
    PERFORM P1.            MAIN-PARA/1
    MOVE WS-B TO WS-X.     MAIN-PARA/2
    MOVE 'PROGB' TO WS-A.  MAIN-PARA/3
    PERFORM P1 THRU P2.    MAIN-PARA/4
    MOVE WS-C TO WS-Y.     MAIN-PARA/5
    CALL WS-X.             MAIN-PARA/6
    CALL WS-Y.             MAIN-PARA/7
    STOP RUN.              MAIN-PARA/8
P1.
    PERFORM SET-B.         P1/0
    MOVE 'DONE' TO WS-D.   P1/1
P2.
    MOVE WS-B TO WS-C.     P2/0
SET-B.
    MOVE WS-A TO WS-B.     SET-B/0

Inside the walk of (P1, P1#end), the nested cut holds out only WS-D, the one field of that range SET-B does not touch. Inside the walk of (P1, P2#end) it holds out WS-C and WS-D. Either way SET-B hands back to P1/1, because that is P1/0's resume node. Both walks of SET-B were table misses, because they were passed different values. Counted in cobble's fixpoint on this program: 2 walks of a range entered at P1 (one per range) and 2 walks of SET-B. It resolves CALL WS-X to PROGA and CALL WS-Y to PROGB.

5. Why composing stays correct

The claim: the state a PERFORM hands back is the state you would get by pasting the range's statements in place of the PERFORM and walking them there. Pasting is correct by construction, since each pasted copy can only return to where it was pasted. The argument, by how deeply ranges nest:

• A range with no PERFORM in it. Its statements only read bytes in its footprint, so cutting the state to the footprint does not change what any of them computes. They only write bytes in its footprint, so every other byte leaves the pasted copy exactly as it entered, which is what the frame puts back.
• A range that performs others. Assume each inner PERFORM already hands back what pasting the inner range would. Then walking the outer range with those PERFORMs is walking the outer range with the inner ranges pasted in, which is the outer range pasted. The outer footprint includes the inner footprints, so the frame argument above still holds for the outer cut.
• Reusing a stored result. fR depends only on what is passed in. An identical input gives the identical result, so taking it from the table is the same as walking again.
• Loops and joins. Each statement's transfer is monotone (more in never gives less out), and a composition of monotone functions is monotone. So a fixpoint over composed functions is reached, and joins where routes meet behave as they would over the pasted program.

Checked on both examples: the programs with every PERFORM replaced by a pasted copy of its range give cobble the same answers.

The argument needs four things to hold, and breaks without any one of them:

• The footprint covers every byte the range or its callees write. A missed byte would be put back over a write. Cobble errs large: a subscripted name counts as every occurrence of its table.
• The range is not already being walked. COBOL leaves a PERFORM of a range that is still running undefined, and pasting would never end. Cobble ends a route at a PERFORM whose range's entry is already being walked, and adds to the table's key the open entries the range's walk can come to a PERFORM of.
• Only the end node hands back. A route that leaves the range by GO TO or EXEC CICS RETURN is not a return, and pasting would not return there either.
• Some edge leads to the range's end. If none does, cobble sends the state from before the PERFORM to the next statement, which a pasted copy never reaches. With MOVE 'PROGA' TO WS-X. PERFORM P. CALL WS-X., where P is MOVE 'PROGB' TO WS-X. GO TO Q., cobble resolves CALL WS-X to PROGA; pasted, the CALL is never reached and cobble finds no program for it, with WS-X uninitialised.

In cobble

The fixpoint stage (cobble-dataflow-fixpoint) handles every PERFORM this way, with no option to turn it off. --sweeps N, which bounds the walk to N passes over the program, bounds every range walk the same way, and marks the program unsettled if any walk stopped with work left. Cobble computes every range's footprint once per program, before walking. A PERFORM of a paragraph the program does not declare has no range and no PERFORM edge: it keeps its edge to the next statement and passes its state on unchanged.