Пример потока управления на языке ассемблера

Эта статья — еще одна статья из моей серии о понимании языка ассемблера — она является продолжением условной логики на языке ассемблера.

Обе эти статьи написаны на простом C, а не на ассемблере, но не на структурированном C, а на C с использованием if-goto, стиля потока управления, используемого в языке ассемблера и машинном коде.

Мы собираемся преобразовать эту простую пузырьковую сортировку в C, чтобы удалить операторы структуры:

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;
            }
        }
    }
}

Во-первых, давайте рассмотрим цикл for. Цикл for состоит из четырех частей:

for ( initialization; condition; increment )
{ body }

Поток управления делает initialization сначала только один раз, вне цикла. Далее, condition проверяется, завершен ли цикл. Затем body выполняется один раз (итерация). И, наконец, incrementа затем condition повторно протестировано, чтобы увидеть, должна ли произойти еще одна итерация.

Прежде чем мы начнем, первым шагом будет преобразование структурированных циклов for в несколько более простые, но все же структурированные циклы while.

NB: Одно из соображений здесь заключается в том, имеет ли структурированный цикл какие-либо continue; заявления, потому что continue; в цикле for следует запустить increment с последующим conditionи т. д. Принимая во внимание, что цикл while не имеет increment часть, а continue; в нем идет прямо к condition.

Поскольку в этом коде нет continue; операторы в циклах for, преобразование простое. (В противном случае нам нужно было бы поместить метку в часть приращения и заменить continue; заявления с goto к этому новому лейблу.)

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
    }
}

Далее, давайте сделаем if-goto для внешнего цикла while:

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: ;
}

Как объяснялось в предыдущем посте на эту тему, сопоставление с образцом во время преобразования вводит вверху метку для продолжения итерации, метку после конца цикла while, используемую для остановки итерации и возобновления операторов после цикла. Условие пока обязательно изменено, потому что if-goto в начале проверяет выход из цикла (вместо проверки продолжения цикла while, как в C).

Далее, давайте сделаем if-goto для внутреннего цикла while:

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: ;
}

Отметим, что довольно механические преобразования (внешний цикл в if-goto и внутренний в if-goto) не взаимодействуют негативно друг с другом, и шаблон замены для двух циклов while можно было бы легко применять в любом порядке.

Далее, давайте преобразуем оператор if-then внутри внутреннего цикла в стиль if-goto. (Опять же, отметим, что это относительно простые замены сопоставления с образцом, и если-то можно было бы преобразовать в стиль if-goto перед преобразованиями цикла for с теми же конечными результатами.)

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: ;
}

Преобразование в стиль if-goto завершено. Структурированные операторы были удалены — в теле функции нет фигурных скобок, и весь поток управления осуществляется с точки зрения if-goto, goto и меток.