An Example in Assembly Language Control Flow

This article is another in my series on understanding assembly language — it is a follow on to Conditional Logic in Assembly Language

Both these articles are written in plain C — not assembly language — but not structured C, rather C using if-goto, the style of control flow used in assembly language and machine code.

We're going to transform this simple bubble sort in C to remove the structure statements:

void bubbleSort ( int arr [], int n )
{
    for ( int i = 0; i < n-1; i++ ) {
        for ( int j = 0; j < n-i-1; j++ ) {
            if ( arr [j] > arr [j+1] ) {
                temp = arr [j];
                arr [i] = temp;
                arr [j] = temp;
            }
        }
    }
}

First, let's review the for-loop.  There are four sections to the for-loop:

for ( initialization; condition; increment )
    { body }

Control flow does initialization first, one time only, outside of the loop.  Next, the condition is tested to see if the loop is done.  Then, the body executes one time (an iteration).  And finally, the increment, followed by the condition retested to see if another iteration should happen.

Before we begin a first step is to transform the structured for-loops into slightly simpler yet still structured while-loops.

NB: One consideration here is whether the structured loop has any continue; statements because continue; in the for loop should run the increment followed by condition, etc..  Whereas, since a while loop doesn't have an increment part, a continue; therein goes right to the condition.

Since this code does not have continue; statements in the for-loops, the transformation is simple.  (Otherwise we would need to place a label at the increment part and replace continue; statements with a goto to that new label.)

void bubbleSort(int arr[], int n)
{ 
    int i = 0; // outer for-loop initialization
    while ( i < n-1 ) {
        int j = 0; // inner for-loop initialization
        while ( j < n-i-1 ) {
            if ( arr [j] > arr [j+1] ) {
                temp = arr [j];
                arr [i] = temp;
                arr [j] = temp;
            }
            j++; // inner for-loop increment
        }
        i++; // outer for-loop increment
    }
}

Next, let's do the if-goto for the outer while loop:

void bubbleSort(int arr[], int n)
{ 
    int i = 0; // outer for-loop initialization
outerLoopTop:
    if ( i >= n-1 ) goto outerLoopDone;  // exists the outer loop NB: condition reversed!
    int j = 0; 
    while ( j < n-i-1 ) {
        if ( arr [j] > arr [j+1] ) {
            temp = arr [j];
            arr [i] = temp;
            arr [j] = temp;
        }
        j++;
    }
    i++; // outer for-loop increment
    goto outerLoopTop;
outerLoopDone: ;
}

As explained in the previous post on this subject, the pattern matching while transformation introduces a label at the top to continue iteration, a label after the end of the while loop used to stop iteration and resume statements after the while-loop.  The while condition is necessarily reversed because the if-goto at the beginning tests to exit the loop (rather than teesting to continue the while-loop as in C).

Next, let's do the if-goto for the inner while loop:

void bubbleSort(int arr[], int n)
{ 
    int i = 0; // outer for-loop initialization
outerLoopTop:
    if ( i >= n-1 ) goto outerLoopDone;  // exists the outer loop NB: condition reversed!
    int j = 0; 
innerLoopTop:
    if ( j >= n-i-1 ) goto innerLoopDone; // exists the inner loop NB: condition reversed!
    if ( arr [j] > arr [j+1] ) {
        temp = arr [j];
        arr [i] = temp;
        arr [j] = temp;
    }
    j++;
    goto innerLoopTop;
innerLoopDone:
    i++; // outer for-loop increment
    goto outerLoopTop;
outerLoopDone: ;
}

Let's note that the rather mechanical transformations (outer loop to if-goto and inner to if-goto) do not negatively interact with each other and the substitution pattern for the two while-loops could have been applied in either order with ease.

Next, let's transform the if-then statement inside the inner loop into if-goto style.  (Again, let's note that these are relatively simple pattern matching replacements, and, the if-then could have been tranformed to if-goto style before the for-loop transformations, with the same final results.)

void bubbleSort(int arr[], int n)
{ 
    int i, j;
    i = 0; // outer for-loop initialization
outerLoopTop:
    if ( i >= n-1 ) goto outerLoopDone;
    j = 0; // inner for-loop initialization
innerLoopTop:
    if ( j >= n-i-1 ) goto innerLoopDone;
    
    if ( arr [j] <= arr [j+1] ) goto skipSwap; // conditionally skips the then-part NB: condition reversed!
    temp = arr [j];
    arr [i] = temp;
    arr [j] = temp;
skipSwap:               // <--- join point here from the if-then 
    // at the label above, the if-then is over.
    // this code will execute whether the if-then fires or not
    // simply resuming execution after the if-then

    j++;
    goto innerLoopTop;
innerLoopDone:
    i++; // outer for-loop increment
    goto outerLoopTop;
outerLoopDone: ;
}

The transformation to if-goto style is complete.  Structured statements have been removed — there's no curly braces within body of the function, and, all control flow is in terms of if-goto, goto, and labels.

This post is Copyright (C) 2019, Erik L. Eidt