Graph algorithms · rewriting a tree, not just reading one

Eliminating GOTOs

Read first: nothing — standalone

A GO TO names where control goes next, not which statements it skips. When the jump and its label share a block, the skipped statements are the ones between them, and an IF can be wrapped around those. When the jump is nested inside an IF and the label is a paragraph further out, no one block holds "what the jump skips".

In the example below, GO TO SZ1 sits inside an IF inside paragraph SA1. The rewrite climbs it out one level at a time, leaving a flag behind, until the jump and SZ1 are siblings; a forward rewrite then removes it. The result has no GO TO and prints the same lines whatever WS-NUM1 holds.

Sections, paragraphs and fall-through are in the COBOL/CICS primer.

The example

The program is simple-goto.cbl from cobol-rekt's test programs. Drawn as a tree, its GO TO SZ1 (amber) sits in the THEN branch of an IF in paragraph SA1; its label SZ1 is a paragraph of section S, two levels further out:

flowchart TD
    S["S SECTION"] --> SA1["SA1"]
    S --> SZ1["SZ1"]
    SA1 --> D1["DISPLAY #quot;ABCD#quot;"]
    SA1 --> If["IF WS-NUM1 #gt; 10"]
    SA1 --> D3["DISPLAY #quot;SA1-1#quot;
DISPLAY #quot;SA1-2#quot;"]
    If -->|THEN| G["GO TO SZ1"]
    If -->|ELSE| D2["DISPLAY #quot;#lt;= 10#quot;"]
    SZ1 --> D4["DISPLAY #quot;ENDING...#quot;"]
    G -.->|"jumps to, 2 levels out"| SZ1
    class G changed
    classDef changed fill:#f5b041,stroke:#f5b041,color:#000

The answer: two climbs and one forward rewrite leave no GO TO and one flag. The table traces both programs for a value of WS-NUM1 on each side of the test; they print the same lines.

GO TOs left: 0climbs: 2flags: 1 (FLAG)final rewrite: forward

WS-NUM1	original prints	rewrite prints
5 (its VALUE)	ABCD, <= 10, SA1-1, SA1-2, ENDING...	ABCD, <= 10, SA1-1, SA1-2, ENDING...
12	ABCD, ENDING...	ABCD, ENDING...

The procedure division first, then the tree the rewrite leaves, written out as COBOL-like text:

S SECTION.
SA1.
    DISPLAY "ABCD".
    IF WS-NUM1 > 10
     THEN
         GO TO SZ1
     ELSE
         DISPLAY "<= 10".
    DISPLAY "SA1-1"
    DISPLAY "SA1-2".
SZ1.
    DISPLAY "ENDING...".

S SECTION.
SA1.
    DISPLAY "ABCD"
    SET FLAG TO FALSE
    IF WS-NUM1 > 10
        SET FLAG TO TRUE
    ELSE
        DISPLAY "<= 10"
    END-IF
    IF NOT FLAG
        DISPLAY "SA1-1"
        DISPLAY "SA1-2"
    END-IF.
IF NOT FLAG        *> wraps nothing
END-IF
SZ1.
    DISPLAY "ENDING...".

Full listing (simple-goto.cbl)

       IDENTIFICATION DIVISION.
       PROGRAM-ID.    SIMPLE-GOTO.
       AUTHOR.        MOJO
       DATE-WRITTEN.  SEP 2024.
       ENVIRONMENT DIVISION.
       DATA DIVISION.
       WORKING-STORAGE SECTION.
            01 WS-NUM1 PIC 9(9) VALUE 5.
       PROCEDURE DIVISION.
       S SECTION.
       SA1.
           DISPLAY "ABCD".
           IF WS-NUM1 > 10
            THEN
                GO TO SZ1
            ELSE
                DISPLAY "<= 10".
           DISPLAY "SA1-1"
           DISPLAY "SA1-2".
       SZ1.
           DISPLAY "ENDING...".

FLAG is a name this page invents for the one boolean the rewrite needs; it is not declared in the listing. The second row of the table shows what the flag has to reproduce: at 12 the jump skips SA1-1 and SA1-2, which sit in SA1 after the IF, not in the IF the jump is in.

Step by step

The walk starts from the tree in the diagram above. Each step shows only the part of the tree it changed; *> comments mark the new lines.

Removing GO TO SZ1 (3 steps)

Classify the jump by where it and its label sit in the tree. GO TO SZ1 comes before SZ1 in tree order, so it is a forward jump. It sits two scopes deeper than SZ1, so it climbs twice before the forward rewrite can apply.

node sits in which sits in

GO TO SZ1 THEN of the IF SA1, in S

SZ1 S —

kind: forwardclimbs needed: 2
Climb out of the IF. Nothing follows the GO TO in its THEN branch, so there is nothing to guard. The GO TO becomes SET FLAG TO TRUE. The flag is cleared just before the IF is entered, and the jump is re-emitted right after the IF, in SA1, now conditional on the flag.
```
SA1.
    DISPLAY "ABCD"
    SET FLAG TO FALSE      *> new
    IF WS-NUM1 > 10
        SET FLAG TO TRUE   *> was GO TO SZ1
    ELSE
        DISPLAY "<= 10"
    END-IF
    IF FLAG GO TO SZ1      *> re-emitted
    DISPLAY "SA1-1"
    DISPLAY "SA1-2".
```
jump now in: SA1climbs left: 1
Climb out of SA1. Everything after the jump in SA1, the two DISPLAYs, goes inside IF NOT FLAG. Where the jump stood, the flag should take the jump's condition; that condition is FLAG itself, so nothing new is set. The jump is re-emitted after SA1, in S, still reading FLAG. No second clear is needed: the one from step 1 sits inside SA1, ahead of the only place the flag is set.
```
    ...
    END-IF
    IF NOT FLAG      *> new guard
        DISPLAY "SA1-1"
        DISPLAY "SA1-2"
    END-IF.
IF FLAG GO TO SZ1    *> re-emitted in S
SZ1.
    DISPLAY "ENDING...".
```
jump now in: S, sibling of SZ1climbs left: 0
Forward rewrite. The jump and SZ1 are siblings in S. The statements strictly between them are none, so the new IF NOT FLAG wraps nothing: the climbs already guarded everything the jump skipped. The label stays.
```
    END-IF.
IF NOT FLAG          *> was the jump
END-IF
SZ1.
    DISPLAY "ENDING...".
```
GO TOs left: 0SZ1: kept, no jump targets it

node	sits in	which sits in
GO TO SZ1	THEN of the IF	SA1, in S
SZ1	S	—

Step 3 leaves the second fragment under the example. Trace its second row, WS-NUM1 = 12, through the steps: step 1's SET FLAG TO TRUE runs, step 2's guard skips SA1-1 and SA1-2, and control falls through to SZ1, as the jump did.

Why the jump cannot just be wrapped

In the original fragment, the line GO TO SZ1 says "control passes to SZ1", and nothing in the tree's shape shows that this means skipping SA1-1 and SA1-2. In the rewritten fragment the same fact is on the page: those two lines are inside IF NOT FLAG. The rewrite does not change what the program does, as the trace table shows; it changes whether a reader, or anything built on the tree's shape, can see it.

The forward rewrite alone could not do this, because it needs one block that directly holds the jump and the label. In the example's tree no scope does:

scope	holds GO TO SZ1	holds SZ1	holds SA1-1, SA1-2
THEN of the IF	yes	no	no
SA1	no	no	yes
S	no	yes	no

Steps 1 and 2 of the walk move the jump down this table's rows: into SA1 after step 1, into S after step 2, where the last row then reads yes for both the jump and SZ1.

When the target is in an outer scope

Each climb is one move, applied at whatever depth the jump is: wrap everything after the jump, in the scope it is in, inside an IF guarded by NOT a flag; set that flag where the jump was; re-emit the jump one level up, reading the flag. Repeat until the jump and its label are siblings, then apply the forward or backward rewrite. This is Erosa and Hendren's outward-movement transformation.^[1] In the walk, step 1's guard was empty, because nothing followed the jump in the THEN branch. The general shape, with statements I2 after the jump, is below.

flowchart TD
    subgraph Outer["outer block"]
        O1["..."]
        subgraph Inner["IF something"]
            I1["..."]
            Jump["GOTO LABEL"]
            I2["..."]
        end
        O1 --> Inner
        Inner --> O2["..."]
    end
    Label["LABEL: ..."]
    I1 --> Jump
    Jump --> I2
    Jump -.->|"jumps to, 2 levels out"| Label
    O2 --> Label
    class Jump changed
    classDef changed fill:#f5b041,stroke:#f5b041,color:#000

becomes, one climb:

flowchart TD
    subgraph Outer["outer block"]
        O1["..."]
        subgraph Inner["IF something"]
            I1["..."]
            SetFlag["SET FLAG TO TRUE"]
            subgraph Guard["IF NOT FLAG"]
                I2["... (now conditional)"]
            end
            I1 --> SetFlag --> Guard
        end
        O1 --> InitFlag["SET FLAG TO FALSE"] --> Inner
        Inner --> CheckFlag["IF FLAG GOTO LABEL"]
        CheckFlag --> O2["..."]
    end
    Label["LABEL: ..."]
    CheckFlag -.->|"jumps to, same condition"| Label
    O2 --> Label
    class InitFlag,SetFlag,CheckFlag changed
    classDef changed fill:#f5b041,stroke:#f5b041,color:#000

Traced both ways: when something holds, the original runs I1 then jumps straight to LABEL; the rewrite runs I1, sets the flag, skips I2, and the re-emitted jump skips O2 — the same. When something does not hold, both run O2 then reach LABEL, and the flag, cleared on the way in, is false.

The SET FLAG TO FALSE in the second diagram is not optional. Inside a loop, a flag left TRUE by one pass makes the next pass skip O2 and take the jump again, though the jump never fired; the stale-flag table under what goes wrong shows it on the example. (Erosa and Hendren initialise the flag and clear it again at the label; clearing it just before the construct, as here and in step 1 of the walk, has the same effect for one climb. cobol-rekt does neither — a known gap.)

A forward jump becomes an IF

Step 3 of the walk was this rewrite with nothing to wrap. Here it is where the jump and its label already share a block and statements sit between them:

flowchart TD
    J["IF C1 GOTO SKIP"] -->|"not C1"| S1
    S1 --> S2
    S2 --> Skip["SKIP: S3"]
    J -->|C1| Skip

Read it the other way round: S1 and S2 run exactly when the jump is not taken — when C1 does not hold. That is an IF waiting to be written down.

Rewriting the forward jump (1 step)

The statements strictly between the jump and the label — not the jump itself, not the label — are what the jump skips when C1 holds.

flowchart TD
    J["IF C1 GOTO SKIP"] -->|"not C1"| S1
    S1 --> S2
    S2 --> Skip["SKIP: S3"]
    J -->|C1| Skip
    class S1,S2 changed
    classDef changed fill:#f5b041,stroke:#f5b041,color:#000

Skipped when C1 holds

S1S2

Wrap exactly those statements in an IF guarded by the negated condition — run them precisely when the jump would not have fired. Everything from the jump up to (but not including) the label is replaced by the one new IF; the label itself is untouched.
```
flowchart TD
    Guard["IF NOT C1"] -->|true| S1
    S1 --> S2
    S2 --> Skip["SKIP: S3"]
    Guard -->|false| Skip
    class Guard,S1,S2 changed
    classDef changed fill:#f5b041,stroke:#f5b041,color:#000
```

The label SKIP survives in step 1's graph, unused for now, as SZ1 did in the example — removing a label nothing points to any more is a separate, later cleanup, not this step's job.

A backward jump becomes a loop

The example has no backward jump. A conditional jump back to a label earlier in the same block looks like this:

flowchart TD
    Loop["LOOP: S1"] --> S2
    S2 --> Test["IF C1 GOTO LOOP"]
    Test -->|C1| Loop
    Test -->|"not C1"| S3

Read the other way round: S1 and S2 run again every time C1 holds, checked after they run — a loop whose test comes at the bottom, not the top.

Rewriting the backward jump (1 step)

The label itself and everything up to, but not including, the jump are the loop's body — the jump statement contributes its condition, not its own place in the body.

flowchart TD
    Loop["LOOP: S1"] --> S2
    S2 --> Test["IF C1 GOTO LOOP"]
    Test -->|C1| Loop
    Test -->|"not C1"| S3
    class Loop,S2 changed
    classDef changed fill:#f5b041,stroke:#f5b041,color:#000

Loop body

S1S2

Wrap the body in a loop tested at the bottom, using the jump's own condition unchanged — "keep going while C1 holds" is exactly what the back-jump already meant. The label, the body, and the jump together collapse into the one new loop.
```
flowchart TD
    S1 --> S2
    S2 --> Test["test after body: WHILE C1"]
    Test -->|true| S1
    Test -->|false| S3
    class S1,S2,Test changed
    classDef changed fill:#f5b041,stroke:#f5b041,color:#000
```

Compare the two step-1 graphs: the forward rewrite's guard is NOT C1, this loop's test is C1 unchanged. The back-jump's condition already says "go again", which is exactly what a bottom-tested loop's condition means too.

The rules

classify: forward if the jump comes before its label in tree order, else backward
climb (jump in scope B, condition C):
  SET FLAG TO FALSE before the construct holding B
  SET FLAG TO C where the jump was
  IF NOT FLAG around the rest of B
  IF FLAG GO TO label right after the construct
repeat climb until jump and label are siblings
forward: IF NOT C around the statements strictly between jump and label
backward: loop tested after the body, condition C; body = label up to the jump

Each line was applied above. classify is the walk's first panel. climb is steps 1 and 2: step 1 shows the clear, the set (C is true: GO TO SZ1 is unconditional in its branch) and the re-emitted jump; step 2 shows the guard, and a set that vanishes because C is FLAG. forward is step 3, and step 1 of the forward walk. backward is step 1 of the backward walk.

Where this shows up in reverse engineering

The order these rules run in matters: classification comes first and comes purely from where the jump and its label sit in the statement tree, as in the walk's first panel. A cross-scope jump climbs outward first; only once it and its label are siblings does the forward or backward rewrite apply. For the example:
classify: forwardclimb: step 1climb: step 2forward: step 3
Legacy-to-modern migration, directly: turning COBOL control flow into Java, or any other target that lacks an unrestricted jump, has to clear every GO TO out before a code generator can start. The example's walk is that clearing step for one jump; a program with many runs it once per jump.
Why local rules, not the universal construction: a COBOL GO TO can only target a paragraph, and paragraph labels sit at the top level of their section, never inside a nested IF or loop — SZ1 in the example's tree is a child of S. So a jump only ever needs to move outward, as in steps 1 and 2, never flattening the program into one dispatch loop — the structured program theorem's generic fallback.

What goes wrong

Climbing out is implemented; climbing in or sideways is not. A jump into a scope it is not currently in, or across to a sibling scope's interior, needs a different transformation. cobol-rekt's README states that the outward transformation is the only one in the paper applicable to COBOL, and that the other three are not implemented.

label sits jump must move in cobol-rekt

further out (SZ1 in the example) outward implemented

inside a nested block inward or sideways not implemented

The second row cannot arise from a COBOL GO TO, whose label is always a paragraph; it arises in languages that can label a statement inside a block.
The fresh flag is not fresh at all. Each climb needs a flag, but cobol-rekt uses one hard-coded name for every climb of every jump, and another fixed name for the forward and backward rewrites. Its README acknowledges these names are not yet unique.

name set in (TreeSmith.java) used for

SOME escapeScopeOnce every climb of every jump

EFGH replaceJumpWithJumpIf a plain jump turned into a conditional one, before a forward or backward rewrite

Two jumps climbing out of one IF then share a flag. In the first fragment, with A false, control goes to L2. In the second, after one climb each, the ELSE branch sets the shared flag and the first re-emitted jump, to L1, catches it:
```
IF A
    GO TO L1
ELSE
    GO TO L2
END-IF
```
```
SET FLAG TO FALSE
IF A
    SET FLAG TO TRUE       *> for L1
ELSE
    SET FLAG TO TRUE       *> for L2
END-IF
IF FLAG GO TO L1
IF FLAG GO TO L2
```
The flag is never cleared, and later climbs drop the condition. cobol-rekt only ever sets the flag to true. Run the example's section twice, first with WS-NUM1 = 12 and then with 5, with FLAG false at the start and step 1's SET FLAG TO FALSE left out:

pass WS-NUM1 FLAG before the IF original prints without the clear

1 12 FALSE ABCD, ENDING... ABCD, ENDING...

2 5 TRUE (from pass 1) ABCD, <= 10, SA1-1, SA1-2, ENDING... ABCD, <= 10, ENDING...

Worse, each climb replaces the conditional jump it re-emitted one level up with an unconditional set-to-true rather than a conditional one, so a jump nested two or more levels deep comes out always taken. The project's README notes the climb "does not utilise the value of the IF condition", and prints its result for the example. Its tree has a block per sentence too, so the jump climbs three times there, setting SOME three times; two of those, trimmed:
```
if (gt(ref('WS-NUM1'), primitive(10.0)))
{
  set(ref('SOME'), primitive(true))
  ...
}
else
{
  print(value(primitive("<= 10")))
}
set(ref('SOME'), primitive(true))
...
if (not(primitive(true)))
{
  {
    print(value(primitive("SA1-1")))
    print(value(primitive("SA1-2")))
  }
}
```
The second set sits after the if, where step 2 of the walk sets nothing, so it runs at WS-NUM1 = 5 too and the guard around SA1-1 and SA1-2 is false on every path. The construction in the walk is the correct one; the implementation is not there yet.
This mutates the tree it is given, in place. Each rewrite in cobol-rekt's TreeSmith edits a scope of the tree it was handed:
```
// climb
currentScope.replaceToEnd(jumpNode, ...)
// forward
parent.replaceRangeToExclusive(...)
// backward
parent.replaceRangeToInclusive(...)
```
After the walk, the tree that held GO TO SZ1 no longer has it. Tree zippers are related background: they show how one could make the same deep edits to an immutable tree, building a new path to a new root and leaving the original as it was. This pass does not. Keep a copy first if the original still needs to exist afterward.

label sits	jump must move	in cobol-rekt
further out (SZ1 in the example)	outward	implemented
inside a nested block	inward or sideways	not implemented

name	set in (TreeSmith.java)	used for
SOME	escapeScopeOnce	every climb of every jump
EFGH	replaceJumpWithJumpIf	a plain jump turned into a conditional one, before a forward or backward rewrite

pass	WS-NUM1	FLAG before the IF	original prints	without the clear
1	12	FALSE	ABCD, ENDING...	ABCD, ENDING...
2	5	TRUE (from pass 1)	ABCD, <= 10, SA1-1, SA1-2, ENDING...	ABCD, <= 10, ENDING...

Where this is used

Clearing arbitrary jumps out of legacy procedural code one block at a time, as a step before translating it into a language that only has structured control flow. Best suited to jumps confined to a modest span of code, like one section: the example's jump climbed two levels and left one guard. A jump spanning most of a large program climbs through most of that program's nesting, adding a guard at each level, before it reaches a scope it shares with its label.

References

A. M. Erosa and L. J. Hendren. "Taming Control Flow: A Structured Approach to Eliminating Goto Statements." Proceedings of the 1994 International Conference on Computer Languages (ICCL), 1994, pp. 229–240. The outward-movement transformation and its logical flag variables.