Gen/kill and reaching definitions

Read first: Fixpoints and worklists

Which write a read sees depends on the path the program took to get there. A write inside an IF may not have run, and a later write can replace an earlier one before the read. A search of the source for writes to the name finds them all, including the ones that are always overwritten first and the ones that only come after the read.

In the example below, WS-A is written three times and read twice. For the first read the analysis keeps the two writes in the arms of the IF. For the second it keeps only MOVE 'DONE', because that write replaces both of the others.

Definitions, gen and kill are introduced as the walk uses them; the worklist is on fixpoints.

The example

Both arms of an IF write WS-A. Then it is read, overwritten, and read again. Each box in the graph is one statement, named the way cobble names it. The labels on the arrows into the two reads say which write of WS-A arrives along that arrow.

flowchart TD
    I["MAIN-PARA/0
IF WS-FLAG = 'Y'"] -->|"true"| T["MAIN-PARA/0.then.0
MOVE 'YES ' TO WS-A"]
    I -->|"false"| E["MAIN-PARA/0.else.0
MOVE 'NO#nbsp;#nbsp;' TO WS-A"]
    T -->|"WS-A ← then.0"| M1["MAIN-PARA/1
MOVE WS-A TO WS-B"]
    E -->|"WS-A ← else.0"| M1
    M1 --> M2["MAIN-PARA/2
MOVE 'DONE' TO WS-A"]
    M2 -->|"WS-A ← MAIN-PARA/2"| M3["MAIN-PARA/3
MOVE WS-A TO WS-C"]
    M3 --> S["STOP RUN"]

That is the whole answer: one row per read of WS-A, listing the writes it could see. The first read has two, one from each arm of the IF. The second has one, because MAIN-PARA/2 sits between it and both arms.

The statements behind the graph, from the PROCEDURE DIVISION:

IF WS-FLAG = 'Y'
    MOVE 'YES ' TO WS-A
ELSE
    MOVE 'NO  ' TO WS-A
END-IF.
MOVE WS-A TO WS-B.
MOVE 'DONE' TO WS-A.
MOVE WS-A TO WS-C.
STOP RUN.

       IDENTIFICATION DIVISION.
       PROGRAM-ID. REACHDEF.
       DATA DIVISION.
       WORKING-STORAGE SECTION.
       01  WS-FLAG              PIC X.
       01  WS-A                 PIC X(4).
       01  WS-B                 PIC X(4).
       01  WS-C                 PIC X(4).
       PROCEDURE DIVISION.
       MAIN-PARA.
           IF WS-FLAG = 'Y'
               MOVE 'YES ' TO WS-A
           ELSE
               MOVE 'NO  ' TO WS-A
           END-IF.
           MOVE WS-A TO WS-B.
           MOVE 'DONE' TO WS-A.
           MOVE WS-A TO WS-C.
           STOP RUN.

In the graph, MAIN-PARA/0 is the IF, and MAIN-PARA/0.then.0 and MAIN-PARA/0.else.0 are the first statement in each arm; the arrow labels shorten those two to then.0 and else.0. In the table, a read is identified by its statement and the bytes it reads: WS-A@working_storage[1:5] is WS-A, occupying bytes [1, 5) of working storage — bytes 1, 2, 3 and 4, after the one-byte WS-FLAG at byte 0. Byte ranges in these pages count from 0 and are half-open: [start, end) includes start and stops just before end, and cobble writes the same range as [1:5]; byte extents builds on this.

Step by step

The walk below carries a set of definitions, each one “statement S wrote variable V”, written V ← S. It starts from an empty set, as cobble's does. Fixpoints instead credits every field to a start pseudo-definition on entry; that is a teaching device cobble does not have (see the last point under what goes wrong).

Why a search by name is not enough

You are looking at MOVE WS-A TO WS-C and want to know where the value in WS-A came from. Searching the listing for writes to WS-A finds three statements, for either read. The walk keeps fewer, as the table shows:

In the first row, MAIN-PARA/2 only runs after the read: no arrow in the graph leads from it back to MAIN-PARA/1. In the second row, both arms are always overwritten by MAIN-PARA/2 on the way down, which is step 5 of the walk. In a real program there may be dozens of writes to one field, behind branches and loops, and the gap between the two columns grows with them. What you want is only the writes with a path to the read along which nothing else overwrites the variable.

Gen, kill and union, read off the walk

Here is the example again with the definitions of WS-A written between the statements (the walk also carries WS-B and WS-C; they are left out here):

                 WS-A: {}
IF WS-FLAG = 'Y'
    MOVE 'YES ' TO WS-A
                 WS-A: {then.0}
ELSE
    MOVE 'NO  ' TO WS-A
                 WS-A: {else.0}
END-IF.
                 WS-A: {else.0, then.0}
MOVE WS-A TO WS-B.
                 WS-A: {else.0, then.0}
MOVE 'DONE' TO WS-A.
                 WS-A: {MAIN-PARA/2}
MOVE WS-A TO WS-C.

Three moves make every line of it, and a fourth reads the answer off. The table names each, says what it does, and points at where the fragment above and the walk show it:

Where this shows up in reverse engineering

This is the question behind almost every “why is this value wrong” investigation into unfamiliar code: ask the dataflow which writes could have produced the value a read sees, instead of reading top to bottom hoping to spot the write.

• A field holds an unexpected value in a dump or a log line, and the program is thousands of statements long. Reaching definitions lists every write that could be responsible before anyone opens the source: the right-hand column of the table under why a search by name is not enough, not the middle one. The search space goes from the whole program to a short, specific list.
• Why kill matters as much as gen: a write that always happens between the one you are chasing and the read throws every earlier candidate away, as MAIN-PARA/2 does in step 5. Skipping that half of the rule would leave both arms on MAIN-PARA/3's row, next to the one write that can actually be responsible:

  MAIN-PARA/3's definers with gen only (amber: could never be the one)

  MAIN-PARA/0.else.0MAIN-PARA/0.then.0MAIN-PARA/2
  In a real program that is a long list of writes that look plausible but could never actually be the one.
• The same question, asked backward instead of forward, on the Java side: starting from one variable at one statement and walking data-dependency edges backward across method boundaries — through parameters and return values — answers “what value reached this argument” the same way, including resolving the case where the answer is a literal handed to a call several frames up rather than anything stored in a variable at all.

The rule

Every line of the box ran in the walk. The table points each one back at the step that applied it.

This is the same shape as every analysis in the fixpoints page: a transfer per statement and a union where paths meet. The example has no loop, so the single walk above, in reverse postorder, already reaches the fixpoint — not necessarily in source order in general, since a PERFORMed paragraph may sit later in the text than the code that runs after it. With a loop, the worklist runs it until nothing grows; the second point below shows one.

What goes wrong

Each point below changes the example slightly. The rows quoted for each variant are what cobble wrote to defs.jsonl for it.

• Only a certain overwrite may kill. A write that might replace the value — through an array element with an unknown subscript, or a write that covers only part of the variable — must not remove the old definitions, because the old value may still be there. Such a write is a weak update: it generates without killing. That is this page's rule, on whole variables; cobble, on byte ranges, is finer, as below. Replace step 5's write with one that covers only the first two bytes:

  MOVE 'DO' TO WS-A(1:2).
  MOVE WS-A TO WS-C.

  treating the write as	definers at MAIN-PARA/3	WS-C actually receives
  a kill (wrong)	MAIN-PARA/2	'DOS ' or 'DO  '
  weak	MAIN-PARA/0.else.0, MAIN-PARA/0.then.0, MAIN-PARA/2	'DOS ' or 'DO  '

  The last two bytes of either value were written by an arm of the IF, so the first row leaves out writes that really are responsible. Killing on a maybe is the one mistake here that produces a wrong answer rather than a loose one. Cobble works on byte ranges: when the write's bytes are known exactly, as here, it cuts each old definition down to the bytes the write left alone, and only when either side is inexact does it keep the old definition whole. The cut gives the second row's three definers too: the arms still own bytes [3, 5) of WS-A's [1, 5), and MAIN-PARA/2 owns [1, 3). In COBOL the partial case is everywhere; the byte extents page is about it.
• Loops bring definitions back round. A write at the bottom of a loop reaches a read at the top on the next iteration. In this program the read in MOVE WS-A TO WS-B sees 'INIT' on the first iteration and 'NEXT' on every later one:

  MOVE 'INIT' TO WS-A.
  PERFORM UNTIL WS-FLAG = 'Y'
      MOVE WS-A TO WS-B
      MOVE 'NEXT' TO WS-A
  END-PERFORM.

  pass	WS-A on the way into MAIN-PARA/1.body.0
  1	WS-A ← MAIN-PARA/0
  2	WS-A ← MAIN-PARA/0, WS-A ← MAIN-PARA/1.body.1
  3	no change: settled

  On the first pass in reverse postorder, the loop's back arrow comes from a statement not yet visited, so MOVE 'NEXT' is missing. A single walk would stop there. That is why the analysis needs a fixpoint rather than a single walk. Cobble's row for that read lists MAIN-PARA/0 and MAIN-PARA/1.body.1, the settled pass.
• Union is generous. The answer is every write that could reach, along paths the analysis cannot rule out. Put MOVE 'Y' TO WS-FLAG. in front of the IF, so the condition is always true:

  MOVE 'Y' TO WS-FLAG.
  IF WS-FLAG = 'Y'

  The statements shift by one, and the first read of WS-A, now MAIN-PARA/2, still lists both arms:
  MAIN-PARA/1.else.0MAIN-PARA/1.then.0
  The else arm can never run, but the analysis does not evaluate conditions.
• A read with no definition gets no definer. In the example, nothing writes WS-FLAG; the IF reads it only as a condition, and cobble writes a row only for a read whose value goes into a write, so the IF's read gets no row at all. Copy WS-FLAG somewhere first, and the copy's read gets a row with an empty definer list:

  MOVE WS-FLAG TO WS-C.
  IF WS-FLAG = 'Y'

  model	definers of WS-FLAG@working_storage[0:1] at MAIN-PARA/0
  cobble	none ("definers": [])
  fixpoints' start	start

  Its value comes from outside the program, or from its initial state. With the start pseudo-definition the fixpoints page uses, the row's only definer would be start, as in the table; the rows for WS-A would not change, because both arms of the IF kill start. Value sets reports the same situation as the reason uninitialised, and that is the reason cobble gave this row.

In cobble

The fixpoint stage (cobble-dataflow-fixpoint) collects each read's definers as it walks and writes one row per read whose value goes into a write into defs.jsonl. Its definitions are kept per byte range, not per variable name. These are the commands as run on this page's program, and the two rows it wrote — the table under the example. The values column holds what those definers can have left there, which value sets builds on.

cobble-parse-corpus --config corpus.toml
cobble-extents --asg-dir parsed --out extents.jsonl
cobble-dataflow-fixpoint --asg-dir parsed \
    --extents extents.jsonl --out-dir fx --all

{"program": "REACHDEF", "node": "MAIN-PARA/1",
 "extent": "WS-A@working_storage[1:5]",
 "definers": ["MAIN-PARA/0.else.0",
              "MAIN-PARA/0.then.0"],
 "values": ["NO  ", "YES "], "reasons": []}
{"program": "REACHDEF", "node": "MAIN-PARA/3",
 "extent": "WS-A@working_storage[1:5]",
 "definers": ["MAIN-PARA/2"],
 "values": ["DONE"], "reasons": []}