GOTO Elimination Algorithm

GOTO Elimination Algorithm (Unstructured to Structured)

Problem Description

Devise an algorithm to eliminate any GOTO statements from a program, in order to get a structured program, which is logically and functionally equivalent.

For example:

stmt 1
stmt 2
stmt 3
stmt 4
EXSR SR1
stmt 6
stmt 7
stmt 8
stmt 9
BEGSR SR1
if cond1 goto line17
stmt 12
if cond4 goto line11
if cond5 goto line6
if cond3 goto line20
stmt 16
if cond2 goto line13
if condo goto line2
ENDSR

Goto Branching Cases

The following are the different abstract cases that may arise in programs that contain GOTO branching:

Goto Branching Special Cases

The following are the special cases that are a variant of the cases mentioned above and thus can be resolved as per the algorithm outlined for those cases:

Goto Branching Primitive Case

From the cases mentioned above, the following is the primitive case that serves as the base to which all other cases can be converted to, through code transformations:

Goto Elimination Algorithm

The following section of the document details out the algorithms that can be applied for all the cases outlined above, to eliminate gotos and labels from code.

Base Algorithm

1. Take the original program as input

2. Collect all goto and label statements as pairs

3. For Each goto-label pair,

• Convert goto to single statement conditional goto, if it is not already

• Classify the goto-label pair to a single case (from among the cases outlined above)

• Execute specific case's algorithm of which the current goto-label pair corresponds to

4. Output the restructured program

Key Points

For the all case specific algorithms that are detailed below, following are some of the key points to consider:

• Every goto statement should be conditional (i.e. conditional with the single goto statement in it)

Eg:

if (cond) {
  goto L1
}

• Every case (code structure) should be reduced to the primitive case/state outlined above
• For any goto-label pair, only the goto statement must be adjusted/moved to reduce the structure to primitive case/state
• Every new introduced boolean variable in the algorithms, that is used without initialization, is assumed to be initialized to false

Note: In all the algorithms outline below, when referring to goto statement, it refers to the single statement conditional goto i.e.:

if (cond) {
  goto L1
}

Case 1.1 Algorithm

Goto and label occur at the same indent level in the same container/block and goto occurs before the label.

• Conditionally execute all the statements between the goto statement and the label statement, based on the inverse condition that is applied on the goto statement and remove the goto statement and the label

Case 1.2 Algorithm

Goto and label occur at the same indent level in the same container/block and label occurs before the goto.

• Execute all the statements between the label statement and the goto statement in a do-while loop, including the label statement, based on the condition that is applied on the goto statement and remove the label and the goto statement.
• If a LEAVE/BREAK or ITER/CONTINUE falls under the do-while introduced in step#1, introduce a new variable and set it to true just before the LEAVE/BREAK or ITER/CONTINUE statement. Also create a new conditional block just after the do-while block introduced in step#1, based on this new variable that tracks the LEAVE/BREAK or ITER/CONTINUE statement, and re-set this new variable to false and execute the LEAVE/BREAK or ITER/CONTINUE statement

Case 2.1 Algorithm

Goto occurs in some parent container/block (container level > 1) of the container/block where the label is contained in and goto occurs before the label.

1. Introduce a new temporary variable to the store the value of the condition that is applied on the goto statement and use this new variable as the conditional for the goto statement.
2. Modify the condition of immediate child block/container, if it is conditioned, to include the goto condition with the OR (||) operator (short-circuit). In case the immediate child block/container is a if-then-else block and the label statement resides in the else block, then the inverse of the goto condition is included with the AND (&&) operator
3. Conditionally execute all the statements after the goto statement in the same block/container, based on the inverse condition that is applied on the goto statement.
4. Move the goto statement downwards to that child block/container (identified in step#2) (i.e. move the goto statement as the first statement in the child block/container).
5. Repeat steps #2 to #4 till the goto statement and label statement end up in the same block/container.
6. Apply Case 1.1 algorithm
7. If the label statement was originally contained in a loop, re-initialize the temporary variable (introduced in step#1) to false, just before the statement where label was applied

Case 2.2 Algorithm

Goto occurs in some parent container/block (container level > 1) of the container/block where the label is contained in and label occurs before the goto.

1. Introduce a new temporary variable to the store the value of the condition that is applied on the goto statement and use this new variable as the conditional for the goto statement.
2. Find the parent block/container where the label is contained, which is in the same block/container as the goto statement. Encapsulate this parent block/container and all the statements till the goto statement in a do-while loop, based on the condition that is applied on the goto statement.
3. Move the goto statement as the first statement in the do-while loop created in step#2
4. Apply Case 2.1 algorithm

Case 3.1 Algorithm

Label occurs in some parent container/block (container level > 1) of the container/block where the goto is contained in and goto occurs before the label.

1. Introduce a new variable to the store the value of the condition that is applied on the goto statement and use this new variable as the conditional for the goto statement.
2. If goto is inside a block that is not a loop, then conditionally execute all the statements after the goto statement in the same block/container, based on the inverse condition that is applied on the goto statement. If goto is inside a loop, use break to break out of the loop.
3. Move the goto statement upwards to the parent block/container (i.e. move the goto statement to the next statement after the current block/container).
4. Repeat steps #2 and #3 till the goto statement and label statement end up in the same block/container.
5. Apply Case 1.1 algorithm

Case 3.2 Algorithm

Label occurs in some parent container/block (container level > 1) of the container/block where the goto is contained in and label occurs before the goto.

1. Introduce a new variable to the store the value of the condition that is applied on the goto statement and use this new variable as the conditional for the goto statement.
2. If goto is inside a block that is not a loop, then conditionally execute all the statements after the goto statement in the same block/container, based on the inverse condition that is applied on the goto statement. If goto is inside a loop, use break to break out of the loop.
3. Move the goto statement upwards to the parent block/container (i.e. move the goto statement to the next statement after the current block/container).
4. Repeat steps #2 and #3 till the goto statement and label statement end up in the same block/container.
5. Apply Case 1.2 algorithm
6. Re-initialize the temporary variable (introduced in step#1) to false, just before the statement where label was applied

Case 4.1 Algorithm

Goto occurs in a disjoint container/block compared to where label is located and goto occurs before the label.

1. Introduce a new variable to the store the value of the condition that is applied on the goto statement and use this new variable as the conditional for the goto statement.
2. If goto is inside a block that is not a loop, then conditionally execute all the statements after the goto statement in the same block/container, based on the inverse condition that is applied on the goto statement. If goto is inside a loop, use break to break out of the loop.
3. Move the goto statement upwards to the parent block/container (i.e. move the goto statement to the next statement after the current block/container).
4. Repeat steps #2 and #3 till the goto statement occurs in some parent container/block (container level > 1) of the container/block where the label is contained in
5. Apply Case 2.1 algorithm

Case 4.2 Algorithm

Goto occurs in a disjoint container/block compared to where label is located, and label occurs before the goto.

1. Introduce a new variable to the store the value of the condition that is applied on the goto statement and use this new variable as the conditional for the goto statement.
2. If goto is inside a block that is not a loop, then conditionally execute all the statements after the goto statement in the same block/container, based on the inverse condition that is applied on the goto statement. If goto is inside a loop, use break to break out of the loop.
3. Move the goto statement upwards to the parent block/container (i.e. move the goto statement to the next statement after the current block/container).
4. Repeat steps #2 and #3 till the goto statement occurs in some parent container/block (container level > 1) of the container/block where the label is contained in
5. Apply Case 2.2 algorithm

Case 5 Algorithm

For a goto-label pair, goto occurs in a method/sub-routine and label occurs in the main program body.

1. Encapsulate the program body into a method
2. Introduce a new variable to the store the value of the condition that is applied on the goto statement and use this new variable as the conditional for the goto statement. Initialize this variable to false in the program body
3. Replace the goto statement in the single statement conditional goto, with a method call statement that calls the method where the label is contained
4. Move the single statement conditional goto, as the first statement in the method where the label is contained
5. Apply Case 1.1 algorithm
6. Add an initialization statement just before the label statement, which initializes the variable introduced in step#2 to false

Goto Elimination Algorithm Visualization

Case 1.1 Algorithm

Case 1.2 Algorithm

Case 2.1 Algorithm

Case 2.2 Algorithm

Case 3.1 Algorithm

Case 3.2 Algorithm

Case 4.1 Algorithm

Case 4.2 Algorithm

Case 5 Algorithm

Case SP1

Case SP2