Gen/kill and reaching definitions

For every read of a variable, which writes could have produced the value it sees.

Where this shows up in reverse engineering

This is the question behind almost every "why is this value wrong" investigation into unfamiliar code: not reading the program top to bottom hoping to spot the write, but asking the dataflow directly which writes could have produced the value a specific read sees.

• A field holds an unexpected value in a dump or a log line, and the program is thousands of statements long. Reaching definitions enumerates every write that could be responsible before anyone opens the source — the search space goes from the whole program to a short, specific list.
• 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.
• 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. Skipping that half of the rule turns a precise answer into a long list of writes that look plausible but could never actually be the one.

The problem

You are looking at MOVE WS-A TO WS-B and want to know where the value in WS-A came from. In a real program there may be dozens of statements that write WS-A, behind branches and loops. Some can reach this read; some are always overwritten before it. Searching for every write by name gives you all of them, including the ones that cannot matter. You want only the ones with a path to the read along which nothing else overwrites the variable.

The intuition

Walk the program carrying a set of definitions: each one is "statement S wrote variable V". When a statement writes V, it adds its own definition — it generates it — and throws away every other definition of V, because the new value replaced them: it kills them. Where two paths meet, either path could have been taken, so keep the definitions from both. At any read, the definitions of that variable in the set are the answer.

The example

Both arms of an IF write WS-A. Then it is read, overwritten, and read again.

       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.

Statements are named the way cobble names them: 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. A read is identified by its statement and the bytes it reads: WS-A@working_storage[1:5] is WS-A, bytes 1 to 5 of working storage, after the one-byte WS-FLAG.

Step by step

The rule

This is the same shape as every analysis in the fixpoints page: a transfer per statement and a union where paths meet. With no loop, a single walk in program order already reaches the fixpoint. With a loop, the worklist runs it until nothing grows.

What goes wrong

• 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. Killing on a maybe is the one mistake here that produces a wrong answer rather than a loose one. 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. That is why the analysis needs a fixpoint rather than a single walk.
• Union is generous. The answer is every write that could reach, along paths the analysis cannot rule out. If the IF condition were always true, the else arm's write would still be listed: the analysis does not evaluate conditions.
• A read with no definition — WS-FLAG in the IF here — gets no row. Its value comes from outside the program, or from its initial state.

In cobble

The fixpoint stage (cobble-dataflow-fixpoint) collects each read's definers as it walks and writes one row per read into defs.jsonl. Its definitions are kept per byte range, not per variable name; the next page shows why.