Подпрограммы

Очень часто программа должна по многу раз выполнять определенную подзада­чу, но с разными значениями данных. Такая подзадача обычно называется под­программой. Подпрограмма может, скажем, вычислять функцию sin или сортиро­вать список в порядке возрастания или убывания значений.

Составляющий такую подпрограмму блок команд можно включать во все те места программы, где он должен выполняться. Однако на практике так никогда не поступают. Для экономии места в память помещают только одну копию блока команд, и любая программа, которой потребуется выполнить эту подпрограмму, просто переходит к ее начальному адресу. Такой переход называется вызовом подпрограммы и выполняется в помощью команды Call.

После реализации подпрограммы работа вызывающей ее программы должна быть продолжена. В таком случае говорят, что выполняется возврат из подпро­граммы в вызывающую программу. Делается это с помощью команды Return. По­скольку подпрограмма может вызываться из нескольких разных мест основной программы, при ее вызове где-то должен сохраняться адрес возврата. Иными сло­вами, для обеспечения правильного возврата из подпрограммы команда Call должна сохранить содержимое регистра PC.

Применяемый компьютером способ выполнения вызовов подпрограмм и воз­врата из таковых называется методом связывания подпрограмм. Простейший ме­тод связывания подпрограмм заключается в сохранении адреса возврата в задан­ном месте, которым может быть специально выделенный для этого регистр. Такой регистр называется регистром связи. Когда работа подпрограммы заверша­ется, команда Return возвращает управление вызывающей программе, выполняя неявный переход через регистр связи.

Особой разновидностью команды перехода является команда Call, выполняю­щая такие операции, как сохранение содержимого регистра PC в регистре связи и переход по указанному в команде целевому адресу. Команда Return также явля­ется разновидностью команды перехода, но она выполняет переход по адресу, за­данному в регистре связи. Этот процесс проиллюстрирован на рис. 6.5.

Рис. 6.5. Связывание подпрограммы через регистр связи

6.6.1. Вложенность подпрограмм и стек процессора

В программировании очень распространена практика вызова одних подпрограмм из других. Такие подпрограммы, вызываемые друг из друга, называются вложен­ными. Если вложенные вызовы будут реализованы по описанной выше техноло­гии, вторая команда Call сохранит адрес возврата в регистре связи, уничтожив его текущее содержимое, после чего возврат в исходную программу станет не воз­можным. Поэтому перед вызовом очередной подпрограммы нужно где-то сохра­нять содержимое регистра связи.

Теоретически подпрограммы могут вкладываться на любую глубину. Рано или поздно последняя вызванная подпрограмма завершит свою работу и вернет управление вызвавшей ее подпрограмме. Необходимый для этого адрес возвра­та — это последний адрес, сохраненный в данной цепочке вызовов подпрограмм. Иными словами, адреса возврата сохраняются и используются в порядке LIFO (Last In First Out, что в переводе с английского значит «последним вошел — пер­вым вышел»). Очевидно, что адреса возврата, связанные с вызовами подпрограмм, должны помещаться в стек. Многие процессоры делают это автоматически, как часть работы команды Call. Для использования в качестве указателя стека (SP) вы­зовов подпрограмм выделяется отдельный регистр, именуемый стеком процессора. Команда Call помещает в стек процессора содержимое регистра PC, а команда Return выталкивает из этого стека адрес возврата и помещает его в PC.

6.6.2. Организация стека

Стек, это специальная структура данных (один из способов организации данных), которая предназначена для обмена информацией между главной программой и подпрограммой.

Стек — это список элементов данных, обычно слов или байтов, доступ к которым ограничен следующим правилом: элементы этого списка могут добавляться толь­ко в его конец и удаляться только из конца. Конец списка называется вершиной стека, а его начало — дном. Такую структуру иногда называют магазином. Этот механизм хранения и обработки данных хорошо описывается емкой фразой «последним вошел — пер­вым вышел» (Last In First Out, LIFO), означающей, что элемент данных, поме­щенный в стек последним, удаляется из него первым. Операцию помещения но­вого элемента в стек часто называют его проталкиванием (push), а операцию извлечения последнего элемента из стека называют его выталкиванием (pop).

Данные, организованные в виде сте­ка хранятся, так чтобы последовательные элементы располагались друг за другом. Первый элемент хранится по адресу BOTTOM, а когда в стек помеща­ются новые элементы, они располагаются в порядке уменьшения последователь­ных адресов. Таким образом, стек растет в направлении уменьшения адресов. На рис. 6.6 показано, как располагается в памяти компьютера стек, элементы которого занимают по одному 32-разрядному слову. На дне он содержит числовое значение 43, а на вершине -28. Для отслеживания адреса вершины стека используется регистр процессора, называемый указателем стека (Stack Pointer, SP (ESP)).

Так как память адресуется побайтово и слово имеет длину 32 разряда (4 байта), операцию проталкивания в стек можно реализовать так:

SUB ESP,4

MOV NEWITEM,(ESP)

где команда SUB вычитает операнд 4 из результирующего операн­да, содержащегося в регистре ESP, и помещает результат в регистр ESP. Эти две ко­манды помещают слово, хранящееся по адресу NEWITEM, на вершину стека, предварительно уменьшая указатель стека (адрес вершины) на одно слово равное 4 байтам. Операция выталкивания из стека может быть реализована так:

MOV ITEM,(ESP)

ADD ESP,4

Эти две команды перемещают значение, хранившееся на вершине стека, в дру­гое место памяти, по адресу ITEM, а затем уменьшают указатель стека на 4, чтобы он указывал на тот элемент, который теперь располагается на вершине стека.

Рис. 6.6. Стек слов в памяти

Как было уже отмечено, стек процессора удобно применять для выпол­нения операций, связанных с входом в подпрограммы и возвратом из таковых. В архитектуре IA-32 в качестве указателя стека используется регистр ESP, указы­вающий на текущую вершину стека процессора (то есть на его верхний элемент). Ширина стека составляет 32 разряда, а это означает, что его эле­менты являются двойными словами.

Существует четыре команды для проталкивания элементов в стек и выталки­вания их из стека.

Команда

PUSH Source

уменьшает значение ESP на 4, а затем сохраняет двойное слово, находящееся по адресу Source, в па­мяти, который указан в ESP.

Команда POP

POP Destination

выполняет обратную операцию: считывает из памяти двойное слово, на которое указывает ESP, то есть считывает из стека верхний элемент, а затем сохраняет его по адресу Destination и увеличивает значение ESP на 4, удаляя тем самым верхний эле­мент из стека. Регистр ESP используется в этой команде неявно. Исходный и ре­зультирующий операнды задаются в одном из режимов адресации IA-32. Еще две команды предназначены для выталкивания из стека и проталкивания в него сра­зу нескольких элементов.

Команда

PUSHAD

проталкивает в стек содержимое восьми регистров общего назначения, от ЕАХ до EDI, а команда

POPAD

выталкивает их из стека в обратном порядке. При извлечении сохраненного значе­ния ESP команда POPAD удаляет его из стека, не загружая в регистр ESP, и про­должает выталкивать последующие элементы, записывая их в соответствующие регистры. Применение этих двух команд при реализации подпрограмм позволяет более эффективно сохранять и восстанавливать содержимое всех регистров.

6.6.3. Передача параметров

Вызывая подпрограмму, программа должна передать ей параметры (операнды), которые будут использоваться в вычислениях, или же их адреса. Закончив свою работу, подпрограмма вернет другие параметры — результаты вычислений. Такой обмен информацией между вызывающей программой и подпрограммой называ­ется передачей параметров. Передача параметров может выполняться нескольки­ми способами. Например, параметры можно помещать в регистры или в память, от­куда подпрограмма сможет их считать. В качестве альтернативы параметры можно поместить в стек процессора, используемый для хранения адресов возврата.

Использование регистров процессора — способ простой и эффективный. На рис. 6.7 показано, как реализовать программу, вы­полняющую сложение последовательности чисел, в виде подпрограммы с передачей параметров через регистры. Длина последовательности n, информация о которой хранится в памяти по адресу N, и адрес первого числа, NUM1, передаются под­программе через регистры ECX и EBX. Вычисленная подпрограммой сумма возвра­щается вызывающей программе через регистр EAX. Соответствующую часть вызы­вающей программы составляют первые четыре команды из числа представлен­ных на рис. 5.19. Первые две команды загружают в регистры ECX и EBX значения N и NUM1. Команда Call выполняет переход к подпрограмме, начинающейся по ад­ресу LISTADD. Кроме того, эта команда помещает в стек процессора адрес воз­врата из подпрограммы. Подпрограмма вычисляет сумму и помещает ее в регистр EAX. После возврата из подпрограммы вызывающая программа сохраняет эту сум­му в памяти по адресу SUM.

Таким образом, регистры ЕВХ, ЕСХ и ЕАХ используются для передачи параметров. Регистр EDI подпрограмма при выполнении сложения за­действует в качестве индексного регистра, поэтому его содержимое должно со­храняться и восстанавливаться при помощи команд PUSH и POP. Подпрограмма вызывается командой

CALL LISTADD

Первым делом эта команда проталкивает в стек адрес возврата, а затем выпол­няет переход по адресу LISTADD. Содержимое стека после сохранения в нем со­держимого регистра EDI показано на рис. 6.7, б. Адрес возврата в нашем приме­ре — это адрес команды MOV, непосредственно следующей в вызывающей про­грамме за командой CALL. Команда RET возвращает управление вызывающей программе, выталкивая из стека содержимое указателя команды EIP.

а

б

Рис. 6.7. Программа с рис. 5.8, переписанная в виде подпрограммы для процессоров IA-32; параметры передаются через регистры: вызывающая программа и подпрограмма (а);

содержимое стека после сохранения значения EDI в подпрограмме (б)

На рис. 6.8 показан еще один вариант этой же программы, в котором парамет­ры передаются подпрограмме через стек. Параметры NUM1 и N проталкиваются в стек двумя командами PUSH в вы­зывающей программе. После выполнения команды CALL вершина стека располагается на уровне 2. Регистры EDI, ЕАХ, ЕВХ и ЕСХ используются так же, как в подпрограмме на рис. 5.7. Их значения сохраняются в стеке, затем в них загру­жаются начальные значения и параметры. Эту работу выполняют первые 8 ко­манд подпрограммы. В результате вершина стека оказывается на уровне 3. После сложения чисел при помощи цикла из четырех команд сумма помещается в стек на место параметра NUM1. Выполнив команду RET, команды вызывающей про­граммы ADD и POP удаляют из стека параметр N и помещают результирующую сумму в память по адресу SUM, возвращая вершину стека на уровень 1.

а

б

Рис. 6.8. Программа с рис. 6.7, а, переписанная в виде подпрограммы для процессоров IA-32 (параметры передаются через стек): вызывающая программа и подпрограмма (а);

содержимое стека после сохранения значения EDI в подпрограмме (б)

В завершение темы вызова подпрограмм мы рассмотрим пример обработки вложенных вызовов. На рис. 5.9 приведен код программы на языке ассемблера IA-32, иллюстрирующей пример обработки вложенных вызовов. Стековые фреймы обоих подпрограммы вы видите на рис. 5.10. Указателем на фрейм служит ре­гистр ЕВР. В наборе команд IA-32 имеются команды PUSHAD и POPAD, с помощью которых можно сохранить в стеке и восстановить из него все восемь регистров общего назначе­ния, но в программе на рис. 5.9 мы предпочли воспользоваться отдельными ко­мандами PUSH и POP, поскольку в подпрограммах задействована только поло­вина всех регистров.

Рис. 6.9. Вложенные подпрограммы на языке ассемблера IA-32

Рис. 6.10. Стековые фреймы для программы, представленной на рис 6.9. (Вершина стека ESP)

6.7. Примеры программ

6.7.1. Программа для вычисления скалярного произведения двух векторов

На рис. 6.11 приведена программа вычисления скалярного произведения двух векторов для процессоров архитектуры IA-32. Начальные адреса этих векторов равны AVEC и BVEC. В программе для доступа к последовательным элементам векторов используется базовая индексная адресация. В качестве индексного ре­гистра применяется регистр EDI. Коэффициент масштабирования равен 4, по­скольку элементы векторов являются двойными словами (4 байта). В качестве счетчика цикла используется регистр ЕСХ, инициализированный значением n. Это позволяет задействовать команду LOOP (см. раздел 5.2), кото­рая сначала уменьшает значение регистра ЕСХ, а затем выполняет условный пе­реход по адресу LOOPSTART, если содержимое регистра ЕСХ не равно нулю. Предполагается, что произведение двух элементов векторов поместится в двой­ное слово, поэтому в команде умножения IMUL явно задан регистр назначения EDX (см. раздел 5.14).

Рис. 6.11. Программа для процессоров IA-32, вычисляющая скалярное произведение двух векторов

6.7.2. Программа сортировки байтов

int main (int argc, char*, argv[])

{

for (j=n-1; j>0; j=j-1)

{for(k=j-1; k >= 0; k = k - 1)

{if (LIST[k] > LIST[j])

{TEMP = LIST[k];

LIST[k] = LIST[j];

LIST[j] = TEMP;

}

}

}

}

Рис 6.12. Программа сортировки байтов для процессоров IA-32 на языке С

На рис. 6.13, вы видите программу для процессора IA-32, выполняющую сорти­ровку байтов. Регистр ЕАХ инициализируется значением LIST и используется в качестве базо­вого регистра для доступа к элементам списка при базовой индексной адресации. Регистр EDI служит индексным регистром для внешнего цикла (индекс j), а ре­гистр ЕСХ — индексным регистром для внутреннего цикла (индекс k). В регистре DL содержится текущий наибольший байт сортируемого подсписка. Для замены элементов LIST(k) и LIST(j) программе требуются три команды, а также регистр для временного хранения данных.

В программе введена еще одна неизвестная команда

XCNG operand1,operand2,

которая меняет значения операндов.

Рис. 6.13. Программа сортировки байтов для процессоров IA-32 на языке ассемблера

6.7.3. Подпрограммы для вставки и удаления элементов связного списка

Программы на рис. 6.14 и 6.15, выполняют вставку и удаление элементов связ­ного списка. Па­раметры им передаются через регистры. Причем регистры с именами RHEAD, RNEWREC, RIDNUM, RCURRENT и RNEXT используются так же, как в уни­версальных подпрограммах. Указанные имена применяются вместо имен регист­ров IA-32 ЕАХ, ЕВХ и т. д. Для хранения кода новой вставляемой записи задейст­вован шестой регистр, RNEWID, в который первая команда подпрограммы с рис. 6.14 загружает код новой записи.

В программе вставки в связный список нового элемента для процессоров IA-32 предполагается, что код новой записи не совпадает ни с одним из кодов, имеющихся с списке записей, а в программе уда­ления предполагается, что в списке имеется запись с кодом, заданным в регистре RIDNUM.

Рис. 6.14. Подпрограмма для процессоров IA-32, вставляющая в связный список новый элемент

Рис. 6.15. Подпрограмма для процессоров ia-32 удаляющая элемент из связного списка