Как работают подпрограммы?

← →
TStas (2009-10-10 13:25) [0]

Понятно, что они для временных (локальных) переменных использую стек. Допустим, есть подпрограммка функция Плюсик(Х, У: Число): Число {Результат := Х + У};

Компилятор, встретив объявление этой функции, написал её описание, чтобы обнаружив код вызова, он мог проверить правильность параметров и значения. Он написал некий код этой функции, узнав, что у неё есть две локальные переменные. Обнаружил вызов, написал дажепролог вызова функции, где скопировал фактические параметры на место формальных. Это всё понятно. А вот дальше?

В момент разбора выражения компилятор не может выделить память для хравнения локальных переменных. Да если бы и мог, то рекурсия была бы запрещена. Сама память выделяется в момент вызова в стеке. Но как же он тогда пишет само сложение? Ведь нужно, чтобы написать саму операция, пускай, как в примере, это будет сложение двух чисел, знать адреса этих чисел. Или хотя бы адреса будущих адресов.

Вопрос возник вот как: я стал думать, как же устроена рекурсия. Код у функции всегда один и компилятор написал его, когда разбирал выражение, то есть код самой функции. Этот код не меняется, т. к., эсли не ошибаюсь, ож живёт в области кода, которая доступна только для чтения. Как же тогда работает рекурсия.

Вот самый простой пример, который из всех книжек:

Функция Факториал(Х: ЧИсло): Число;
{
Результат := 1;
Если Х = 1, тогда выход
иначе
Результат *= Факториал(Х - 1)
};
Понятно, что глубина рекурсии неизвестна на момент разбора выражения и зависит от переданного числа. Код самой функции будет состоять из одной операции сравнения, одной вычитания и одной умножения.
Но как же компилятор напишет эти операции, если адреса переменных неизвестны и будут выделены только в прологе функции, а сам код функции в процессе её выполнения менять нельзя?

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

← →
KSergey © (2009-10-10 14:14) [1]

Я советую сделать просто: запустите свою программу под отладчиком в дельфи, встаньте на точке останова (breakpiont) и View->Debug windows->CPU
В открывшемся окне вы увидите в какие машинные команды скомпилировалась каждай строка вашей программы, а немного изучив ассемблер - сразу же найдете ответы на подбные вопросы.

В частности, что касается "откуда она знает адрес в стеке" - все просто: в сгенерированном коде адресация переменных, созданных на стеке, идет не по абсолютным адресам, а всегда относительно указателя стека - регистра EBP процессора.

← →
Григорьев Антон © (2009-10-10 14:37) [2]

В стеке при вызове находятся:
1. Параметры - их кладёт в стек программа перед передачей управления по адресу подпрограммы.
2. Локальные переменные - память для них выделяет пролог подпрограммы.

На момент начала работы пролога параметры уже лежат в стеке, а локальные переменные - ещё нет. Таким образом, регистр ESP, который указывает на вершину стека, указывает на место сразу после параметров. Пролог заносит значение регистра EBP в стек, а значение ESP (которое из-за сохранения ESP сдвинулось ещё на 4 байта) копирует в EBP. Потом в стеке выделяется место для локальных переменных, значение ESP снова изменяется, а EBP уже остаётся неизменным. Таким образом, к моменту начала работы кода подпрограммы регистр EBP указывает на то место в памяти, где расположены локальные переменные текущей активации подпрограммы. Компилятор обращается к локальным переменным не по абсолютному адресу, а по смещению относительно текущего значения EBP. Параметры тоже адресуются относительно EBP, только смещение идёт в другую сторону. Эпилог функции помимо очистки стека восстанавливает значение EBP, которое было на момент вызова.

Теперь разберёмся с рекурсией. Функция вызывается первый раз. Старое значение EBP сохраняется в стеке, присваивается новое. Внутри этой активации подпрограммы она вызывает сама себя. Значение EBP первой активации сохраняется в стеке, EBP получает новое значение, соответствующее новому состоянию стека, заносится в EBP, и вторая активация работает со своей копией локальных переменных и параметров, не смешиваясь с первой активацией. Когда вторая активация заканчивает работу, она восстанавливает старое значение EBP, которое имела первая активация, и первая активация продолжает работать со своей копией локальных переменных. Так как адресация не абсолютная, а относительная по смещению от EBP, а значение EBP у каждой активации своё, плюс ещё каждая активация принимает меры для восстановления EBP после своей работы, рекурсия может быть сколь угодно глубокой, пока хватает стека.

Несколько сложнее обстоит дело с вложенными процедурами. Рассмотрим такой пример:

procedure ExternalProc(...); procedure InternalProcA(...); begin ... end; procedure InternalProcB(...); begin InternalProcA(...); // (**) end; begin InternalProcB(...); InternalProcA(...); // (*) end;

Здесь InternalProcA вызывается в двух разных местах: непосредственно из ExternalProc (*) и из InternalProcB (**) В первом случае стек на момент начала работы выглядит так:

Локальные переменные InternalProcA <-- EBP Параметры InternalProcA Адрес для возврата из InternalProcA Локальные переменные ExternalProc Параметры ExternalProc

Во втором случае стек выглядит так:

Локальные переменные InternalProcA <-- EBP Параметры InternalProcA Адрес для возврата из InternalProcB Локальные переменные InternalProcB Параметры InternalProcB Адрес для возврата из InternalProcA Локальные переменные ExternalProc Параметры ExternalProc

Понятно, что смещение локальных переменных и параметров ExternalProc не относительно значения EBP для активации IntrernalProcA не может быть фиксированным - оно зависит от предыстории вызовов. Тем не менее, InternalProcA при любом способе вызова нормально работает с переменными ExternalProc. Это достигается следующим образом: в каждом конкретном случае вызова InternalProcA смещение переменных ExternalProc относительно значения EBP для InternalProcA может быть вычислено на этапе компиляции, так как компилятору известен и стек вызовов, и сколько каждая из вызванных подпрограмм заняла места в стеке. Это значение кладётся в стек перед параметрами внутренней подпрограммы и оказывается по фиксированному смещению от её значения EBP. Когда внутренняя подпрограмма обращается к локальным переменным внешней, получается следующее:

1. По известному смещению от текущего значения EBP получается смещение переменных внешней подпрограммы относительно текущего значения EBP.

2. К полученному таким образом смещению добавляется смещение, адресующее конкретную внешнюю локальную переменную, и выполняется по этому суммарному смещению отнсительно текущего значения EBP.

Если глубина вложенности подпрограмм, например, не два, а три, то обращение к переменным самой внешней подпрограммы из самой внутренней осуществляется в три этапа:

1. По известному смещению от текущего значения EBP получается смещение переменных средней подпрограммы относительно текущего значения EBP.

2. Относительно этого смещения известно смещение, где хранится смещение локальных переменных внешней подпрограммы относительно EBP средней. Это смещение извлекается из стека и складывается с уже известным смещением локальных переменных средней подпрограммы отнсительно внутренней.

3. Теперь к сумме этих смещений добавляется смещение для конкретной переменной, и получается смещение данной внешней локальной переменной относительно EBP внутренней процедуры.

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

← →
KSergey © (2009-10-10 14:53) [3]

> Григорьев Антон © (10.10.09 14:37) [2]

Вот, я чуял, что про EBP - вру. Т.е. оно относительно EBP меряется, но чую же, что это не указатель стека...

← →
TStas (2009-10-10 16:22) [4]

Спасибо огромное за ответы, наипаче же Анону Григорьеву. И не за ответ только, но и за книжку "Чего не пишут в ....". Очень хорошая книжка, хотя многое из неё я читал и раньше.
Ассемблер я хотел давно изучить хотябы на уровне чтения, но всё время занят. :(.

← →
TStas (2009-10-10 20:21) [5]

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

← →
Inovet © (2009-10-10 22:02) [6]

> [5] TStas (10.10.09 20:21)
> Получается, что один и тот же код, один из которых в подпрограмме,
> а другой просто в программе, должен работать с разной скоростью,

А WinMain по твоему не подпрограмма? И вообще почитай о типах памяти в Делфи не знаю как они называются, а в Си основные глобальная, динамическая, статическая.

← →
Григорьев Антон © (2009-10-11 09:14) [7]

> TStas (10.10.09 20:21) [5]
> Значит мне неверно ответили, что вызовы подпрограмм очень
> незначительно тормозят вычислиния. Получается, что значительно

Не факт. Такты не считал, но пусть будет ваше число - 10 тактов. Много ли это? Всё познаётся в сравнении. Если само вычисление требует 100 тактов, то многовато, а если 10000 тактов - копейки. Тот, кто вам писал про незначительность, скорее всего, имел ввиду очень сложные вычисления с небольшим количеством обращений к внешним локальным переменным.

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

← →
Григорьев Антон © (2009-10-11 09:20) [8]

> Inovet © (10.10.09 22:02) [6]
> А WinMain по твоему не подпрограмма? И вообще почитай о
> типах памяти в Делфи не знаю как они называются, а в Си
> основные глобальная, динамическая, статическая.

Тогда два вопроса к вам:

1. В чём разница между глобальной и статической?

2. Где компилятор Си хранит локальные переменные функций?

И не знаю, как там в Си, но в Delphi главный блок - особая подпрограмма. Подпрограммой она является только с точки зрения наличия ret в конце. Собственных параметров и локальных переменных блок не имеет, значение EBP для него безразлично, так что рассуждения из [5] к нему не применимы.

← →
Inovet © (2009-10-11 11:50) [9]

> [8] Григорьев Антон © (11.10.09 09:20)
>
> > основные глобальная, динамическая, статическая.
>
> Тогда два вопроса к вам:
>
> 1. В чём разница между глобальной и статической?

Это у меня опмска должна быть не гловальная а автоматическая.

> 2. Где компилятор Си хранит локальные переменные функций?

Вот в ней как раз

> так что рассуждения из [5] к нему не применимы.

Пожалуй.

Атору. Предположим локальные переменные размещаются компиляторов не на стеке, а где-либо по фиксированным аресам, Кроме того что этот подход в общем случае требует больше памати т.к. заранее не известно глубина вложений вызовов и надо под каждую переменную свой адрес выделить, ещё и рекурсия станет не возможной. Но возможно явно указать такое размещение в Си модификатор ststic.

← →
Inovet © (2009-10-11 12:12) [10]

> [9] Inovet © (11.10.09 11:50)

Поменять местами кроме невозможности рекурсии больше памяти т.к. о рекурсии автор и писал.

← →
Alex Konshin © (2009-10-11 13:10) [11]

Вот и выросло поколение, которое не знает, что такое Ассемблер...

Почитай книжку по процессорам Intel x86. Это избавит тебя от многих подобных вопросов, а заодно и научит оценивать цену каждой операции в языках высокого уровня типа Delphi. Если ты хочешь быть настоящим программистом, то иметь представление об используемом процессоре просто необходимо. И ещё рекомендую прочесть что-нибудь про компиляторы, например известную книгу Ахо и Ульмана. Тогда узанешь, что такое фрейм на стеке, да и заодно как работают компиляторы.

← →
Григорьев Антон © (2009-10-11 18:26) [12]

> Inovet © (11.10.09 11:50) [9]
> Но возможно явно указать такое размещение в Си модификатор
> ststic.

А по научному это называется "глобальная переменная с локальной областью видимости" :) В Delphi они тоже бывают, только очень криво объявляются. Бросьте на форму Memo1 и Button1, и добавьте такой код:

{$J+} function GetValue: Integer; const N: Integer = 1; begin Result := N; Inc(N); end; procedure TForm1.Button1Click(Sender: TObject); var I: Integer; begin Memo1.Lines.Clear; for I := 1 to 100 do Memo1.Lines.Add(IntToStr(GetValue)); end;

Вы увидите, что Memo1 заполнится отнюдь не единицами. И происходит это потому, что N будет расположена не в стеке, а в сегменте данных, т.е. это будет аналог static в Си.

← →
Inovet © (2009-10-11 19:30) [13]

> В Delphi они тоже бывают, только очень криво объявляются.

Ну да снижение контроля со стороны компилятора. Константы менять всёж не хорошо.

← →
Германн © (2009-10-12 03:38) [14]

PUSH BP
MOVE BP,SP
Это должно висеть на стенке у любого паскалиста.
:)

← →
Германн © (2009-10-12 03:40) [15]

> Alex Konshin © (11.10.09 13:10) [11]
>
> Вот и выросло поколение, которое не знает, что такое Ассемблер.
> ..
>

И которое не хочет знать.

← →
brother © (2009-10-12 05:02) [16]

> И которое не хочет знать.

ну пока с батонокидателей вырастут, более менее стоящие программисты... потом уже и до этого дойдут)

← →
Inovet © (2009-10-12 13:26) [17]

> [14] Германн © (12.10.09 03:38)
> PUSH BP
> MOVE BP,SP
> Это должно висеть на стенке у любого паскалиста.
> :)

Не только паскалиста - Intel BP не специально для паскаля ввёл, а потом ещё добавл и команды для работы с фреймом для ЯВУ, кстати на сколько они используются, кто знает? Розыч наверно много всякого разглядывал.

← →
Rouse_ © (2009-10-12 14:33) [18]

> а потом ещё добавл и команды для работы с фреймом для ЯВУ

Ты про enter/leave? В дельфи не используются.
так-же как и ret используется только в варианте "Near return" (опкод C3)
По поводу VС++, сейчас взял наш проект из SDK, тоже чегой-то не видать :)
В библиотеках системных, все есть.

← →
Inovet © (2009-10-12 14:51) [19]

> [18] Rouse_ © (12.10.09 14:33)
>
> > а потом ещё добавл и команды для работы с фреймом для
> ЯВУ
>
> Ты про enter/leave? В дельфи не используются.

В C++Builder как-то давно смотрел, не специально именно эти, с разными опциями компилятора, обычно-то дебаг версия перед глазами - тоже не видел.

> так-же как и ret используется только в варианте "Near return"
> (опкод C3)
> По поводу VС++, сейчас взял наш проект из SDK, тоже чегой-
> то не видать :)

Как-то у меня возникал вопрос что за причины не любви к ним.

> В библиотеках системных, все есть.

В Windows всмысле?

← →
Григорьев Антон © (2009-10-12 15:20) [20]

> Rouse_ © (12.10.09 14:33) [18]
> Ты про enter/leave? В дельфи не используются.

Действительно, ни разу в дельфийском коде не видел их. Даже странно, потому что в Турбо Паскале была опция Intel 80286 Instruction set, при включении которой при возврате использовалась LEAVE.

← →
Rouse_ © (2009-10-12 15:23) [21]

> Как-то у меня возникал вопрос что за причины не любви к ним.

Ну это не ко мне :)

> В Windows всмысле?

Ну в NTDLL.DLL например.

← →
Игорь Шевченко © (2009-10-12 16:07) [22]

enter и leave медленее, насколько мне известно, чем аналогичная последовательность команд пролога/эпилога.

← →
icWasya © (2009-10-12 17:10) [23]

А ещё вот История соглашений о вызовах
http://transl-gunsmoker.blogspot.com/2008/12/1.html

← →
oldman © (2009-10-12 17:14) [24]

> Но как же компилятор напишет эти операции, если адреса переменных
> неизвестны и будут выделены только в прологе функции, а
> сам код функции в процессе её выполнения менять нельзя?

Читать Вам и читать про рекурсию, выделение памяти etc...
Ничего Вам компилятор писать не будет, поскольку шелезяка.

← →
oxffff © (2009-10-12 17:31) [25]

Вообще для косвенного обращения к параметрам можно и не использовать EBP, можно обращаться через esp. Если не изменяет память C++ компилятор именно такой обращение и использует.
Что касаемо отличия Enter с уровнем вложенности 0, аналог
push ebp,
mov ebp,esp
то вот рекомендации из мануала по оптимизации от intel

Complex Instructions
Avoid using complex instructions (for example, enter, leave, loop). Use sequences of simple instructions instead.

← →
Игорь Шевченко © (2009-10-12 17:36) [26]

> Если не изменяет память C++ компилятор именно такой обращение
> и использует.

Компилятор - он хитрый. Он может в одном модуле для разных функций и по ESP адресоваться, и по EBP, в зависимости от использования регистров внутри тела функции, размера генерируемых инструкций по доступу к локальным переменным, расположения звезд и фазы луны во время компиляции...

← →
oxffff © (2009-10-12 18:46) [27]

> Игорь Шевченко © (12.10.09 17:36) [26]

И Вы правы.
Я упомянул о отличной от использования EBP технике доступа для других.

P.S. В данный момент в свободное время я как раз занимаюсь описанием L атрибутивной грамматики для языка Pascal для построения аннотированного дерева разбора.
Вы были заинтересованы в неком средстве для получения такого дерева. Что вас именно интересует(какое подможество грамматики и в каком виде)?

oxffff © (12.10.09 18:46) [27]

Да, я был заинтересован в средстве для получения подобного дерева, спасибо.

Основной идеей был поиск алгоритмически дублирующихся участков кода, отсюда и требования к подмножеству грамматики. Вид - либо XML, либо объект.

> Игорь Шевченко © (12.10.09 18:58) [28]

Я пока только делаю первые шаги в этом направлении.
Но насколько понял вам нужно построение DAG для выражения.

Поскольку для остального даже человеку сложно выявить идентичность или неидентичность алгоритма.
Если не сложно приведите пример о каких дублежах идет речь.
О a=a+(b-c)*e+(b-c)*d
или о чем то другом. :)

← →
TStas (2009-10-12 19:54) [30]

>внутренние процедуры нельзя вызывать по указателю
Помню, был косяк, но я тогда не понял, почему это так получилось и как-то исправил.

← →
TStas (2009-10-12 19:57) [31]

[11] А как книжка-то называется?

> Если не сложно приведите пример о каких дублежах идет речь.
>
> О a=a+(b-c)*e+(b-c)*d
> или о чем то другом. :)

Скорее о:

procedure TFoo.Bar1; begin Bazz1 := MumbleVango(Foo1, Foo2); end;
и

procedure TFoo.Bar2; begin Bazz2 := MumbleVango(Foo3, Foo4); end;

> Честное слово не вижу. :)

Лень было придумывать более объемный пример,
подобный код можно без ущерба функциональности перевести в

function TFoo.Bar (FooA, FooB: TFoo): TBazz;
begin
Result:= MumbleVango(FooA, FooB);
end;

> Игорь Шевченко © (12.10.09 20:38) [34]
>
> > Честное слово не вижу. :)
>
>
> Лень было придумывать более объемный пример,
> подобный код можно без ущерба функциональности перевести
> в
>
> function TFoo.Bar (FooA, FooB: TFoo): TBazz;
> begin
> Result:= MumbleVango(FooA, FooB);
> end;

Я честно не понял сокральной мысли этого преобразования. Поэтому прошу пояснить на наглядном примере.
Чтобы мы с Вами разговаривали на одном языке.

Поскольку
по вашему TFoo.Bar1 TFoo.Bar2 будут выглядеть следующим образом

procedure TFoo.Bar1;
begin
Bazz1 :=Bar (Foo1, Foo2);
end;
и

procedure TFoo.Bar2;
begin
Bazz2 :=Bar (Foo3, Foo4);
end;

Фактически Вы ввели аналог "цепного правила грамматики" от которых стараются избавиться. Зачем?

Можно по другому проанализировать ваше преобразование. Вы некому недоступному правилу(private protected) дали публичный доступ.
Однако для вызова(сохранения функциональности возможности TFoo.Bar1 TFoo.Bar2 ) вам также необходимо дать публичный доступ и к Foo1, Foo2, Foo3, Foo4. Как быть в случае, что такой доступ давать нельзя, но дергать такой метод с параметрами Foo1, Foo2, Foo3, Foo4 нужно. Как компилятор может эвристически вывести такой решение, если он не проектирует классы? И как он может доказать ненужность такого преобразования?

oxffff © (12.10.09 23:34) [35]

Для того, чтобы стало несколько понятнее - я неспешно ищу инструмент для анализа уже готового, прекрасно компилируемого кода. Для этого я предполагаю разобрать этот код в дерево, и средствами анализа дерева поискать такие вот "практические одинаковые" куски.

> Игорь Шевченко © (13.10.09 00:23) [38]

Нет, как только будет готово можно будет воспользоваться средством от меня. Буду работать и дальше в этом направлении в свободное время.

Как работают подпрограммы? Найти похожие ветки