Explainer 5 of 11

Value sets and dynamic calls

Read first: Fixpoints and worklists, Gen/kill and reaching definitions

VALSETS moves 'PROGB' into WS-PGM on one arm of an IF and 'PROGC' on the other, then does CALL WS-PGM; it also does CALL WS-OTHER, which nothing assigns. Value sets track every value a field may hold, and why that list may be short: the first call gets candidate edges to PROGB and PROGC, the second a visible unresolved node, reason uninitialised.

New to CALL, MOVE or PIC X(8)? The COBOL/CICS primer has the vocabulary.

The example

Read alone, the CALL statements of VALSETS give a call graph with no edges (box read alone); value sets give the box with value sets.

flowchart LR
    subgraph vs["with value sets"]
        b0["VALSETS"] -.->|CALL_CANDIDATE| b1["PROGB"]
        b0 -.->|CALL_CANDIDATE| b2["PROGC"]
        b0 -->|CALL| b3["VALSETS.WS-OTHER
dynamic target: uninitialised"]
    end
    subgraph read["read alone"]
        a0["VALSETS"]
    end

That is the whole answer for this example, one row per call:

call	values	reasons	reads as
CALL WS-PGM	PROGB, PROGC	none	these and no others
CALL WS-OTHER	none	uninitialised	at least these (none known)

The lines that matter. Neither field has a VALUE clause:

01  WS-PGM     PIC X(8).
01  WS-OTHER   PIC X(8).
    IF WS-FLAG = 'Y'
        MOVE 'PROGB' TO WS-PGM
    ELSE
        MOVE 'PROGC' TO WS-PGM
    END-IF.
    CALL WS-PGM.
    CALL WS-OTHER.

Full listing (VALSETS)

       IDENTIFICATION DIVISION.
       PROGRAM-ID. VALSETS.
       DATA DIVISION.
       WORKING-STORAGE SECTION.
       01  WS-FLAG              PIC X.
       01  WS-PGM               PIC X(8).
       01  WS-OTHER             PIC X(8).
       PROCEDURE DIVISION.
       MAIN-PARA.
           IF WS-FLAG = 'Y'
               MOVE 'PROGB' TO WS-PGM
           ELSE
               MOVE 'PROGC' TO WS-PGM
           END-IF.
           CALL WS-PGM.
           CALL WS-OTHER.
           STOP RUN.

Step by step

Values are shown as stored. The strip below is WS-PGM, a PIC X(8), after MOVE 'PROGB' TO WS-PGM (step 2 of the walk): the literal fills bytes [0, 5) and the field is padded with three spaces in bytes [5, 8), written ␣. That is why the set in step 2 reads 'PROGB␣␣␣'. A call trims the trailing spaces off a value to get a program name: PROGB.

WS-PGM after step 2 (amber: bytes from the literal; blue: padding)

WS-PGM

␣

The value sets, one statement at a time (6 steps)

IF WS-FLAG = 'Y'. On entry, nothing has been written: every field is empty and uninitialised.

Value sets after this statement (amber: reasons the set may be short)
field values
WS-FLAG {} + uninitialised
WS-PGM {} + uninitialised
WS-OTHER {} + uninitialised
MOVE 'PROGB' TO WS-PGM replaces WS-PGM's set with exactly one value, and no reasons.

Value sets after this statement (amber: reasons the set may be short)
field values
WS-FLAG {} + uninitialised
WS-PGM {'PROGB␣␣␣'}
WS-OTHER {} + uninitialised
MOVE 'PROGC' TO WS-PGM replaces WS-PGM's set with exactly one value, and no reasons.

Value sets after this statement (amber: reasons the set may be short)
field values
WS-FLAG {} + uninitialised
WS-PGM {'PROGC␣␣␣'}
WS-OTHER {} + uninitialised
Two paths meet: each field's values and reasons are the union of both arms'. CALL WS-PGM: candidates: 2 possible edges, to PROGB and PROGC.

Value sets after this statement (amber: reasons the set may be short)
field values
WS-FLAG {} + uninitialised
WS-PGM {'PROGB␣␣␣', 'PROGC␣␣␣'}
WS-OTHER {} + uninitialised
Row written for this call
candidates PROGB, PROGC
reasons none
in the graph candidates: 2 possible edges, to PROGB and PROGC
CALL WS-OTHER: unresolved: a dynamic-target node for WS-OTHER, because uninitialised.

Value sets after this statement (amber: reasons the set may be short)
field values
WS-FLAG {} + uninitialised
WS-PGM {'PROGB␣␣␣', 'PROGC␣␣␣'}
WS-OTHER {} + uninitialised
Row written for this call
candidates none
reasons uninitialised
in the graph unresolved: a dynamic-target node for WS-OTHER, because uninitialised
STOP RUN.

Value sets after this statement (amber: reasons the set may be short)
field values
WS-FLAG {} + uninitialised
WS-PGM {'PROGB␣␣␣', 'PROGC␣␣␣'}
WS-OTHER {} + uninitialised

field	values
WS-FLAG	{} + uninitialised
WS-PGM	{} + uninitialised
WS-OTHER	{} + uninitialised

field	values
WS-FLAG	{} + uninitialised
WS-PGM	{'PROGB␣␣␣'}
WS-OTHER	{} + uninitialised

field	values
WS-FLAG	{} + uninitialised
WS-PGM	{'PROGC␣␣␣'}
WS-OTHER	{} + uninitialised

field	values
WS-FLAG	{} + uninitialised
WS-PGM	{'PROGB␣␣␣', 'PROGC␣␣␣'}
WS-OTHER	{} + uninitialised

field	values
WS-FLAG	{} + uninitialised
WS-PGM	{'PROGB␣␣␣', 'PROGC␣␣␣'}
WS-OTHER	{} + uninitialised

field	values
WS-FLAG	{} + uninitialised
WS-PGM	{'PROGB␣␣␣', 'PROGC␣␣␣'}
WS-OTHER	{} + uninitialised

Sets, and reasons they may be short

The walk carried, for every field, the set of byte values it may hold after each statement. Follow WS-PGM through it: a MOVE of a literal sets the set to exactly that value (rows 1 and 2, steps 2 and 3 of the walk); where the two arms of the IF meet, take the union (row 3, step 4); at a CALL through the field, the set is the list of programs that call could reach (row 4, also step 4). A MOVE from another field, which the example does not have, copies that field's set.

#	statement	WS-PGM's set after it
1	MOVE 'PROGB' TO WS-PGM (then-arm)	{'PROGB␣␣␣'}
2	MOVE 'PROGC' TO WS-PGM (else-arm)	{'PROGC␣␣␣'}
3	END-IF (arms meet)	{'PROGB␣␣␣', 'PROGC␣␣␣'}
4	CALL WS-PGM	can reach PROGB, PROGC

The set can be incomplete: the value may come from a file, from a caller, or from nowhere the analysis can see. So each set also carries reasons it may be missing values, and the answer table under the example shows both readings. WS-PGM ends with two values and no reasons: "these and no others". WS-OTHER is never assigned, so from step 1 to the call in step 5 it carries no values and the reason uninitialised: "at least these" — here, at least nothing.

Why a call through a field needs this

CALL 'PROGB'.   target in the source:
                edge to PROGB
CALL WS-PGM.    target is whatever
                WS-PGM holds

The first call names its target; a call graph can draw that edge by reading it. The second calls whatever is in WS-PGM when it runs, which in VALSETS is PROGB on one arm of the IF and PROGC on the other. Reading statements alone gives the example's edgeless read alone box; the walk fills in with value sets.

Where this shows up

A menu, a router, a transaction dispatcher — any program whose next call is chosen by a field's runtime value — looks like the edgeless read alone box until value sets turn it into with value sets: real edges, and a visible node where the answer is unknown.
On the Java side, a backward data-dependency walk across method boundaries can resolve a literal that reaches a dynamically-dispatched call's argument several call frames up: the same question, "what value could this hold", answered by walking data flow backward instead of forward.
Virtual dispatch resolution is the same kind of set one level up: every concrete class an interface call's receiver could be at runtime, with classes where the graph has PROGB and PROGC.

The rule

value set = (values, reasons)
entry:
  f := ({f's VALUE bytes}, {})
    if f has a VALUE clause,
    else ({}, {uninitialised})
MOVE literal TO f:
  f := ({literal padded or truncated
    to f}, {})
MOVE g TO f:
  f := g's set
merge:
  (values₁ ∪ values₂, reasons₁ ∪ reasons₂);
  if more than 32 values, keep the first
  32 in sorted order and add over-budget
call through f:
  candidates = trimmed values of f,
  reasons = f's reasons

Each line of the box is one the walk above has already used. The table points every line back at the step that applied it:

rule line	where the walk applied it
entry	step 1: none of the three fields has a `VALUE` clause, so each starts as {} + uninitialised
MOVE literal TO f	steps 2 and 3: WS-PGM becomes {'PROGB␣␣␣'}, then {'PROGC␣␣␣'} on the other arm
MOVE g TO f	not used: the example has no field-to-field `MOVE` (but see the fragment just below)
merge	step 4: {'PROGB␣␣␣'} ∪ {'PROGC␣␣␣'} is two values, well under 32, so nothing is cut and no over-budget
call through f	step 4 (WS-PGM: PROGB, PROGC, no reasons) and step 5 (WS-OTHER: no candidates, uninitialised)

cobble departs from the MOVE g TO f line in one case: when g holds no known value. Change the example's else-arm to MOVE WS-OTHER TO WS-PGM, as below. By the box, that arm gives WS-PGM the set of WS-OTHER, {} + uninitialised. cobble stores no value for such a move, only that WS-PGM was written, so the call reads that arm as not-a-literal instead. Both reasons say the same thing to the graph: the list may be short.

ELSE
    MOVE WS-OTHER TO WS-PGM
END-IF.
CALL WS-PGM.   candidates PROGB
               reasons    not-a-literal

The entry line plays the part of the teaching-only start definition on the fixpoints page (cobble itself has no such definition): a VALUE clause supplies the field's starting value, and without one the starting value is unknown. Change one line of the example to give WS-OTHER a VALUE, and step 1 starts it as ({'PROGD␣␣␣'}, {}) instead of {} + uninitialised; nothing else writes it, so CALL WS-OTHER gets candidate PROGD with no reasons.

01  WS-OTHER  PIC X(8) VALUE 'PROGD'.

The two MOVE lines gloss over size: when source and target differ in length, an alphanumeric MOVE pads the target with spaces, as in the strip under step by step, or cuts the value off on the right. If the else-arm were MOVE 'PROGRAMNAME' TO WS-PGM, the eleven-byte literal would not fit: its bytes [0, 8) land in WS-PGM, shown below, and AME, its bytes [8, 11), is cut off. The set after the arms meet would be {'PROGB␣␣␣', 'PROGRAMN'}. Read both MOVE lines as applying this to each value in the set.

WS-PGM after MOVE 'PROGRAMNAME' TO WS-PGM (amber: bytes from the literal)

WS-PGM

A call site then becomes one of three things in the graph. The table after the list has one site of each kind: the two calls of VALSETS, and CALL WS-OTHER in the VALUE 'PROGD' variant above (call that variant VALSETV).

Proven — exactly one candidate and no reasons. An ordinary call edge, as if the name were written in the source: row 3, VALSETV → PROGD.
Candidates — any other site with at least one candidate. One edge per candidate, marked as possible rather than certain: row 1, the two dashed edges in the graph under the example.
Unresolved — no candidates. A single dynamic-target node carrying the expression and the reasons, so the hole is visible rather than silent: row 2, the VALSETS.WS-OTHER node in that graph.

#	site	candidates	reasons	in the graph
1	VALSETS: CALL WS-PGM	PROGB, PROGC	none	candidates: two `CALL_CANDIDATE` edges
2	VALSETS: CALL WS-OTHER	none	uninitialised	unresolved: a `CALL` edge to node `VALSETS.WS-OTHER`
3	VALSETV: CALL WS-OTHER	PROGD	none	proven: a `CALL` edge to `PROGD`

Reasons taxonomy

Each reason explains why a value set may be incomplete — why the true set of values could be larger than what the analysis found.

uninitialised: Some path reaches this point without an exact write to the field, and no WORKING-STORAGE VALUE that cobble can image (text, figurative, or unsigned zoned) covers it. On that path its value is whatever the storage started as. (Introduced here.)

Example: row 2 of the three-way table above. Nothing writes WS-OTHER between step 1 of the walk and the call in step 5, so the call reads whatever the storage started as.

site	VALSETS: CALL WS-OTHER (walk step 5)
candidates	none
reasons	uninitialised

over-budget: More than 32 values reached the field. The first 32 in sorted order are kept; the rest are dropped. The field may have that many possible values — some may come from paths that never actually run — but the analysis cannot carry all of them. (Introduced here.)

Example: an EVALUATE whose 33 arms each move a different name into WS-PGM. The arms' sets merge into 33 values, one over the budget: sorted, PROG01 to PROG32 are kept and PROG33 is dropped.

EVALUATE WS-CHOICE
    WHEN 1   MOVE 'PROG01' TO WS-PGM
    WHEN 2   MOVE 'PROG02' TO WS-PGM
      ...    (one arm each, PROG03 to PROG32)
    WHEN OTHER MOVE 'PROG33' TO WS-PGM
END-EVALUATE.
CALL WS-PGM.  candidates PROG01 … PROG32
              reasons    over-budget

incomplete-walk: The fixpoint stopped before settling because it ran out of its sweep budget — the cap on how many passes over the program it may make. Values that would have arrived on later passes are missing. See bounded sweeps.
hop-limit: The cross-program walk — following a field's bytes backwards from one program into the programs that handed them over (answering every walk once) — was cut after a fixed number of program crossings. Programs beyond that depth were never visited. See bounding walks by crossings.
readback-skipped: The cross-program walk was told not to follow bytes a called program writes back to its caller, so names a callee puts in the commarea are missing. See bounding walks by crossings.

The value comes from somewhere a single program's walk cannot follow. In the fragment, each call reads a field filled from one of these places; the reason on the right is what the fixpoint records for that call, and none of them gets a candidate.

LINKAGE SECTION.
01  LK-PGM  PIC X(8).
PROCEDURE DIVISION USING LK-PGM.
    READ PGM-FILE INTO WS-PGM.
    CALL WS-PGM.   from-file
    CALL LK-PGM.   inbound-linkage

inbound-linkage: The bytes are in LINKAGE: a caller handed them in. Also used when a cross-program walk goes round a cycle of programs and finds nothing. See local site resolution and answering every walk once.
from-callee: A LINK or CALL BY REFERENCE handed the field to another program, which may have written it. See local site resolution.
from-file: A READ or a CICS file command put the value there. See local site resolution.
not-a-literal: The value is not a quoted literal, so the analysis does not evaluate it: arithmetic (ADD through COMPUTE), STRING, INITIALIZE, a numeric or figurative MOVE such as MOVE 0 or MOVE SPACES, a non-file CICS receiver such as RETRIEVE INTO, a value partly overwritten where either the write or the old value's bytes are inexact (the old value is dropped), a read spanning the pieces an exact partial write cut a value into, or a RETRIEVE with no matching START. See local site resolution and bounded sweeps.

Example: SPACES is a figurative constant, not a quoted literal, so this MOVE stores no value and the call after it gets no candidate.

MOVE SPACES TO WS-OTHER.
CALL WS-OTHER.               not-a-literal

unmodelled: A statement cobble does not model may have written the field; it counts as a weak write, so the old values stay and this reason joins them.
outside-analysed-set: The program can be entered from callers outside the analysed members, which may hand it other names. See answering every walk once.
not-recorded: The cross-program walk reached a place where the fixpoint recorded no fact. See answering every walk once.

Reasons the per-site resolution on local site resolution gives about the call site itself, two of them shown here: WS-PGMS is a table of names (OCCURS), and WS-PGM holds only spaces.

CALL WS-PGMS(I).
            operand-not-one-exact-extent
MOVE ' ' TO WS-PGM.
CALL WS-PGM.   no-program-name

no-extent: The operand names no storage cobble could lay out, so there is nothing to read.
operand-not-one-exact-extent: The operand could be several places, such as a subscripted WS-PGMS(I), so the site stays unresolved there.
no-program-name: No value reaching the site looks like a program name; the site is resolved to nothing.
no-csd: A RETURN TRANSID or START was analysed without a CSD, so its transaction id cannot be mapped to a program; the site stays unresolved.
transaction-not-in-csd: The transaction id is not listed in the CSD supplied; the site is resolved to nothing, which is wrong if the CSD is merely incomplete.

What goes wrong

Under-approximation is the normal case, and the reasons say why. Each code in the taxonomy above names one way the set can be short; any reason at all means "at least these values". Delete the else-arm from the example, as below, and the path that skips the IF reaches CALL WS-PGM with nothing written: the merge in step 4 becomes ({'PROGB␣␣␣'}, {}) ∪ ({}, {uninitialised}). The true set is PROGB plus whatever the storage started as; the analysis can only list the first and flag the second.
```
IF WS-FLAG = 'Y'
    MOVE 'PROGB' TO WS-PGM
END-IF.
CALL WS-PGM.   candidates PROGB
               reasons    uninitialised
```
One candidate is not proof. The call above has a single candidate, but it is not a proven edge, because its reasons are not empty. Row 2 of the table below is that call; row 1 is CALL WS-OTHER in the VALUE 'PROGD' variant, which also has one candidate but no reasons. A walk that stopped early can leave a single value in the set in the same way, while a second was still on its way. That is why a proven edge needs an empty set of reasons, not just one candidate.
# site candidates reasons in the graph
1 VALSETV: CALL WS-OTHER PROGD none proven: CALL edge
2 no-else variant: CALL WS-PGM PROGB uninitialised candidates: CALL_CANDIDATE edge

#	site	candidates	reasons	in the graph
1	VALSETV: CALL WS-OTHER	PROGD	none	proven: `CALL` edge
2	no-else variant: CALL WS-PGM	PROGB	uninitialised	candidates: `CALL_CANDIDATE` edge

A value is not always a program name. A field can hold spaces on some path. Values that cannot be a program name — nothing left after trimming the spaces, or bytes that are not printable — are dropped from the candidates and recorded separately. A sentinel such as 'NONE' is not dropped: it trims to a name like any other, so it becomes a candidate edge to a program called NONE. The table shows the example with its else-arm changed to each of the two.

else-arm	values after the arms meet	candidates	dropped	in the graph
MOVE ' ' TO WS-PGM	{'PROGB␣␣␣', '␣␣␣␣␣␣␣␣'}	PROGB	'' (spaces)	proven: `CALL` edge to PROGB
MOVE 'NONE' TO WS-PGM	{'NONE␣␣␣␣', 'PROGB␣␣␣'}	NONE, PROGB	none	two `CALL_CANDIDATE` edges

In the first row the spaces path leaves one candidate and no reasons, so the edge to PROGB is proven; the spaces stay visible only in the row's dropped list.

In cobble

The fixpoint stage (cobble-dataflow-fixpoint) builds the value sets, applies the budget and records the reasons. It writes each dynamic call site as a targets.jsonl row. These are the two rows it writes for VALSETS; MAIN-PARA/1 and MAIN-PARA/2 are the two CALL statements, and the columns are rows 1 and 2 of the three-way table under the rule.

{"caller": "VALSETS", "node": "MAIN-PARA/1",
 "transfer": "CALL", "expression": "WS-PGM",
 "candidates": ["PROGB", "PROGC"],
 "reasons": [], "dropped": []}
{"caller": "VALSETS", "node": "MAIN-PARA/2",
 "transfer": "CALL", "expression": "WS-OTHER",
 "candidates": [], "reasons": ["uninitialised"],
 "dropped": []}

The graph build (cobble-build) reads those rows and applies the three-way rule. From these two it draws the with value sets box in the graph under the example: two CALL_CANDIDATE edges from the first row, and from the second a CALL edge to a DYNAMIC_TARGET node with id VALSETS.WS-OTHER and reason uninitialised.