Graph algorithms · rewriting a tree, not just reading one

Eliminating GOTOs

A forward jump past some statements becomes an IF that skips them. A backward jump back to a label becomes a loop around them. Both are the same move: wrap the statements the jump used to skip over, in whichever control structure makes the skipping implicit.

Where this shows up in reverse engineering

This is the step that makes a decades-old, GOTO-heavy program's logic expressible in a modern language at all. A code generator that only emits if and while has nothing to produce from a jump — something upstream has to remove every one first.

Legacy-to-modern migration, directly: turning COBOL control flow into Java, or any other target that lacks an unrestricted jump, has to clear every GOTO out before a code generator can even start — this page's three rewrites are that clearing step, applied one jump at a time.
Why local rules, not the universal construction: real COBOL sections are almost always already reducible, so the forward/backward/climb-one-level rewrites finish the job without ever flattening the method into one dispatch loop — see the structured program theorem for the generic fallback these rules are quietly avoiding.
The order these rules run in matters for the same reason it matters anywhere else in this pipeline: a jump has to be classified — forward, backward, or crossing a scope — using the dominance and reducibility results from the earlier pages before any rewrite can be chosen safely.

The problem

A jump to a label says "control passes to there" without saying anything about why — nothing in the shape of the code shows which statements it skips, or which statements it repeats. An IF or a loop says that directly: everything inside the block is what the jump used to skip, or used to repeat, right there in the tree's own shape. Rewriting a jump into one or the other does not change what the program does; it changes whether a reader — or anything built on the tree's shape — can see it.

Two shapes to tell apart first, both jumping to a label in the same block of statements as the jump itself: one jumps to a label later in the block (forward), one jumps to a label earlier (backward).

A forward jump becomes an IF

A conditional jump past some statements, landing on a label later in the same block:

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 (2 steps)

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 J,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 survives, unused for now — removing a label nothing points to any more is a separate, later cleanup, not this step's job.

A backward jump becomes a loop

A conditional jump back to a label earlier in the same block:

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 (2 steps)

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["WHILE C1"]
    Test -->|true| S1
    Test -->|false| S3
    class S1,S2,Test changed
    classDef changed fill:#f5b041,stroke:#f5b041,color:#000
```

No negation this time — the back-jump's condition already says "go again," which is exactly what a bottom-tested loop's condition means too.

When the target is in an outer scope

Both rewrites above assume the jump and its label sit in the same block of statements. A jump into or out of a nested IF or loop does not — there is no single enclosing block containing exactly "the statements the jump skips," because the jump and its label are nested at different depths.

The fix climbs one level at a time: wrap everything after the jump, in whatever scope the jump is currently in, inside a new IF guarded by a fresh flag — set that flag right where the jump was, instead of jumping. The jump itself is then re-emitted one level up, in the enclosing scope, now reading that same flag to decide whether to keep going. Repeat until the jump and its label are siblings in the same block — at which point the ordinary forward or backward rewrite above finishes the job.

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 --> Inner
        Inner --> CheckFlag["IF FLAG GOTO LABEL"]
        CheckFlag --> O2["..."]
    end
    Label["LABEL: ..."]
    CheckFlag -.->|"jumps to, same condition"| Label
    O2 --> Label
    class SetFlag,CheckFlag changed
    classDef changed fill:#f5b041,stroke:#f5b041,color:#000

After one climb the jump is a level shallower; a jump nested several levels deep climbs several times before it and its label are finally siblings, ready for the ordinary rewrite.

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 — this technique's own source project states plainly that only the outward climb is implemented, the others are not.
The fresh flag is not actually guaranteed fresh. Each climb invents a flag name to carry the "should I keep going" fact up one level — and the real implementation does not yet guarantee two different jumps, descoped through overlapping scopes, get two different names. A second jump reusing the same name mid-transformation is a real, acknowledged risk, not a hypothetical one.
This mutates the tree it is given, in place. Unlike tree zippers, which build a new path to a new root and leave the original tree exactly as it was, this rewrite changes the one tree handed to it. Keep a copy first if the original still needs to exist afterward.

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 at all — a language with no GOTO cannot express one directly, so something has to remove it first. Best suited to jumps confined to a modest span of code, like one section; a jump spanning most of a large program climbs through most of that program's nesting before it reaches a scope it shares with its label.