Byte-extent aliasing

Read first: Gen/kill and reaching definitions

Reaching definitions matches a read to the writes of the same name, and lets a new write of that name kill the old ones. Both assume a name owns its storage. But a write to a group never names its children, and a write to one child changes only part of what the group's write left. So the test has to be on byte ranges, and it splits in two — does a write touch a read, and does it wipe out an older write — which can answer differently for the same pair.

In the example below, eight bytes carry four names. Comparing ranges finds that the read of WS-B depends on a MOVE into REC that never names it, and the read of WHOLE on both writes, though neither names WHOLE.

New to REDEFINES? See the COBOL primer.

The example

REC is eight bytes, [0, 8): WS-A is bytes [0, 4) and WS-B is bytes [4, 8). WHOLE redefines all eight. Each cell shows its final character and the statement that last wrote it.

Bytes [0, 8) of working storage at the end of the program

The program writes the group, then one child, then reads each child and the redefinition. Cobble numbers the statements of MAIN-PARA from 0, as on the left:

/0  MOVE 'AAAABBBB' TO REC.
/1  MOVE 'XXXX' TO WS-A.
/2  MOVE WS-A TO OUT-A.
/3  MOVE WS-B TO OUT-B.
/4  MOVE WHOLE TO OUT-ALL.

This is the answer: for each read, which writes it may see. The middle column compares byte ranges; the right-hand column compares names, as the reaching definitions page did.

Byte ranges here count from 0 and are half-open: [start, end) includes start and stops just before end, so [0, 4) is bytes 0, 1, 2 and 3, and its length is end − start. Two ranges that meet end to start, like [0, 4) and [4, 8), share no byte. Cobble's own identifiers write the same range as [a:b] — WS-A [0:4] in the table is [0, 4).

       IDENTIFICATION DIVISION.
       PROGRAM-ID. BYTEEXT.
       DATA DIVISION.
       WORKING-STORAGE SECTION.
       01  REC.
           05  WS-A             PIC X(4).
           05  WS-B             PIC X(4).
       01  WHOLE REDEFINES REC  PIC X(8).
       01  OUT-A                PIC X(4).
       01  OUT-B                PIC X(4).
       01  OUT-ALL              PIC X(8).
       PROCEDURE DIVISION.
       MAIN-PARA.
           MOVE 'AAAABBBB' TO REC.
           MOVE 'XXXX' TO WS-A.
           MOVE WS-A TO OUT-A.
           MOVE WS-B TO OUT-B.
           MOVE WHOLE TO OUT-ALL.
           STOP RUN.

Step by step

The strip is bytes [0, 8) of working storage — the bytes of REC. Each byte shows the statement that last wrote it. Below it are the definitions the analysis keeps within REC, one per write, each with the range it wrote; writes to OUT-A, OUT-B and OUT-ALL also become definitions, but they lie outside the strip and are left out.

The cobble rows of steps 3 to 5 are the middle column of the answer table. Only step 3's rows disagree: the page's rule keeps one definition per write, and MAIN-PARA/0 still claims bytes [0, 8) there, though step 2's strip shows its first four bytes repainted. Cobble's row comes from running it on this program; see in cobble.

What tracking by name misses

The right-hand column of the answer table is what tracking by name gets. It is right for WS-A, because step 2 wrote WS-A by name. It finds nothing for WS-B: step 1 wrote REC, and a group is just the bytes of its children laid end to end, so writing REC wrote WS-B without naming it. It finds nothing for WHOLE either: REDEFINES (analogous to a C union — two names for the same bytes) gives the strip's eight bytes a second name with a different shape, and no statement ever names that one. Two of the three reads would have no source at all. By name, these are the only writes there are:

Paint the bytes, forget the names

The strips in the walk lay the data out as the compiler does: each field is a start offset and a length in some storage region, the span rows above the cells. A write paints the bytes it covers — step 2 repaints cells 0 to 3 from /0 to /1. A read looks at the bytes it covers and asks which writes painted any of them — the outlined cells in steps 3 to 5. Two fields alias when their ranges overlap, whatever they are called, however they were declared: WHOLE and REC are the same span, and WS-A sits inside both. Every pair of the strip's four names, and the bytes they share:

Where this shows up in reverse engineering

Step 5's read through WHOLE is the trap in its smallest form: a write through one REDEFINES view and a read through another look unrelated by name and identical by byte range. A commarea passed between programs is the same picture with the two span rows in two programs: each lays the bytes out with its own copybook, so following a value across the boundary means following its byte range, not either side's field name. The same overlap-versus-cover question comes up in any byte-oriented format — a packed binary buffer, shared memory seen through a foreign-function boundary, a union read as two shapes.

The rule

Two different tests, on purpose. A definition is a possible source of a read when it overlaps any byte of it. A definition is certainly gone only when a later write covers every byte it wrote. Anything between — a partial overwrite — leaves it alive. Each line has already run in the walk:

What goes wrong

• The answer can be loose. At MAIN-PARA/2 (step 3) the strip shows that bytes [0, 4) were last written by MAIN-PARA/1 alone. But the rule keeps one definition per write, and MAIN-PARA/1 covers only half of MAIN-PARA/0's eight bytes, so it cannot kill it. MAIN-PARA/0 still overlaps the read — the top span below — and is reported as a definer although none of its bytes survive there. That is an over-approximation: it never misses a real source, it sometimes names one too many. Getting it exact means splitting a definition into byte ranges whenever something writes part of it. Cobble does that when both the write and the definition are exact: after MAIN-PARA/1 it keeps MAIN-PARA/0 only for REC [4:8], the bottom row of spans, which the read does not touch.

  Read at MAIN-PARA/2 (outlined), against MAIN-PARA/0 kept whole by the rule (top) and cobble's pieces (bottom)

  0

  1

  2

  3

  4

  5

  6

  7

  MAIN-PARA/0 REC [0:8]

  MAIN-PARA/1 WS-A [0:4]

  MAIN-PARA/0 REC [4:8]

  /1

  /1

  /1

  /1

  /0

  /0

  /0

  /0
  Where either side is not exact, nothing can be cut, and cobble keeps the whole definition, as the rule does.
• Kill only on certainty. A write whose position is not known exactly — a table element with a computed subscript, a field after an OCCURS DEPENDING ON, a reference modification with a run-time start — may alias widely but must cover nothing. Change MAIN-PARA/1 to write four bytes at a run-time position in REC:

  01  WS-POS  PIC 9.
  /1  MOVE 'XXXX' TO REC(WS-POS : 4).

  Its extent is all of REC, but not exact: cobble writes it REC@working_storage[0:8]~, the ~ marking it clamped. It covers nothing, so every read keeps both writes:

  read	kill nothing (cobble)	if /1 killed /0
  MAIN-PARA/2: WS-A [0:4]	MAIN-PARA/0, MAIN-PARA/1	MAIN-PARA/1
  MAIN-PARA/3: WS-B [4:8]	MAIN-PARA/0, MAIN-PARA/1	MAIN-PARA/1
  MAIN-PARA/4: WHOLE [0:8]	MAIN-PARA/0, MAIN-PARA/1	MAIN-PARA/1

  With WS-POS = 1 the write lands on [0, 4), and WS-B still holds BBBB from MAIN-PARA/0. The right-hand column has lost that source: a wrong answer, not a loose one.
• A field that cannot be sized has no extent at all, and the analysis cannot place its reads and writes. If WS-A's width were unknown, the strip's ranges after it would be unknown too:

  field	extent
  WS-A	[0, ?)
  WS-B	[?, ? + 4)
  which bytes step 4 reads	cannot say

  Cobble reports such a program as unsizeable rather than guess.

In cobble

Every dataflow stage works on these extents. Each field's extent comes from its declaration alone — level, PIC (which sets the length), usage, OCCURS, REDEFINES. Separate 01 items are laid end to end, as in the example: cobble-extents puts OUT-A at [8:12], straight after REC, and WHOLE back at [0:8]. That is a modelling choice — a real compiler may align or pad between 01 items — and it is safe because distinct 01 items never share bytes unless one REDEFINES another. The two tests are the ones above, whether two extents may overlap and whether one covers all of the other, plus the cut from the first bullet under what goes wrong. A move of a literal has no source field, so cobble names its source LITERAL. Run on this page's program, cobble-dataflow-fixpoint reports these definers, the "cobble" rows of steps 3 to 5 (one row per read, other fields left out):

"node": "MAIN-PARA/2",
"extent": "WS-A@working_storage[0:4]",
"definers": ["MAIN-PARA/1"]

"node": "MAIN-PARA/3",
"extent": "WS-B@working_storage[4:8]",
"definers": ["MAIN-PARA/0"]

"node": "MAIN-PARA/4",
"extent": "WHOLE@working_storage[0:8]",
"definers": ["MAIN-PARA/0", "MAIN-PARA/1"]