ДС18в06-машинный-уровень-3-Процедуры (Лекции Северов Часть 1)

Carnegie MellonМашинный уровень 3: ПроцедурыОсновы информатики.Компьютерные основы программированияgoo.gl/X7evFНа основе CMU 15-213/18-243:Introduction to Computer Systemsgoo.gl/Q7vgWwЛекция 6, 12 марта, 2018Лектор:Дмитрий Северов, кафедра информатики 608 КПМdseverov@mail.mipt.rucs.mipt.ru/wp/?page_id=3461Механизмы процедур¢Передача управления§ к началу кода процедуры§ обратно в точку вызова¢Передача данных§ Аргументы процедуры§ Возвращаемое значение¢Управление памятью§ Выделение на время выполнения§ Высвобождение перед возвратомВсе механизмы реализованымашинными командами¢ Реализация процедур в x86-64задействует только необходимыемеханизмы¢P(…) {••y = Q(x);print(y)•}int Q(int i){int t = 3*i;int v[10];••return v[t];}2Машинный уровень 3: Процедуры¢Процедуры x86-64§ Структура стека§ Соглашения вызова процедурПередача управления§ Передача данных§ Управление локальными данными§ Иллюстрация рекурсии§3Стек x86-64Участок памяти используемыйпо правилам стека¢ Растёт в сторону меньшихадресов¢ Регистр %rsp содержитнаименьший адрес стекаДно стека¢Ростадресов§ адрес вершинного элементаСтекрастётвнизУказатель стека: %rspВершина стека4Стек x86-64: Вталкивание¢Дно стекаpushq Src§ Выбирает операнд Src§ Уменьшает %rsp на 8§ Записывает операнд по адресу (%rsp)Указатель стека: %rspРостадресовСтекрастётвниз-8Вершина стека5Стек x86-64: Выталкивание¢popq DestДно стека§ Выбирает операнд по адресу (%rsp)§ Увеличивает %rsp на 8§ Записывает операнд в регистр DestУказатель стека: %rspРостадресов+8СтекрастётвнизВершина стека6Машинный уровень 3: Процедуры¢Процедуры x86-64§ Структура стека§ Соглашения вызова процедурПередача управления§ Передача данных§ Управление локальными данными§ Иллюстрация рекурсии§7Пример кода0000000000400540400540: push400541: mov400544: callq400549: mov40054c: pop40054d: retqlong mult2(long a, long b){long s = a * b;return s;}void multstore(long x, long y, long *dest){long t = mult2(x, y);*dest = t;}<multstore>:%rbx%rdx,%rbx400550 <mult2>%rax,(%rbx)%rbx######Сохранить %rbxСохранить destmult2(x,y)Сохранить по *destВосстановить %rbxВернуть0000000000400550 <mult2>:400550: mov%rdi,%rax400553: imul%rsi,%rax400557: retq# a# a * b# вернуть8Поток управления процедурыСтек используется при вызове процедур и возврате изних¢ Вызов процедуры: call label¢§ Вталкивает адрес возврата в стек§ Переходит к label¢Адрес возврата:§ Адрес команды следующей за сразу за командой вызова§ Дизассемблированный пример400544: callq400550 <mult2># mult2(x,y)400549: mov%rax,(%rbx)# Сохранить по *dest§ Адрес возврата = 0x400544¢Возврат из процедуры: ret§ Выталкивает адрес возврата из стека§ Переходит по адресу возврата9Пример потока управления 1 •0000000000400540 <multstore>:••400544: callq 400550 <mult2>400549: mov%rax,(%rbx)••0x1300x128••0x120%rsp 0x120%rip 0x4005440000000000400550 <mult2>:400550: mov%rdi,%rax••400557: retq10Пример потока управления 2 •0000000000400540 <multstore>:••400544: callq 400550 <mult2>400549: mov%rax,(%rbx)••0x1300x128••0x1200x118 0x400549%rsp 0x118%rip 0x4005500000000000400550 <mult2>:400550: mov%rdi,%rax••400557: retq11Пример потока управления 3 •0000000000400540 <multstore>:••400544: callq 400550 <mult2>400549: mov%rax,(%rbx)••0x1300x128••0x1200x118 0x400549%rsp 0x118%rip 0x4005570000000000400550 <mult2>:400550: mov%rdi,%rax••400557: retq12Пример потока управления 4 •0000000000400540 <multstore>:••400544: callq 400550 <mult2>400549: mov%rax,(%rbx)••0x1300x128••0x120%rsp 0x120%rip 0x4005490000000000400550 <mult2>:400550: mov%rdi,%rax••400557: retq13Машинный уровень 3: Процедуры¢Процедуры x86-64§ Структура стека§ Соглашения вызова процедурПередача управления§ Передача данных§ Управление локальными данными§ Иллюстрация рекурсии§14Carnegie MellonПередача данных в процедуру и обратноРегистры¢ Первые 6 аргументовСтек•••%rdiАргумент n%rsi%rdx•••%rcx¢%r8Аргумент 8%r9Аргумент 7Возвращаемый результат%rax¢Стек занимается только понеобходимости15Примерыпередачиданныхvoid multstore(long x, long y, long *dest){long t = mult2(x, y);*dest = t;}0000000000400540 <multstore>:# x в %rdi, y в %rsi, dest в %rdx•••400541: mov%rdx,%rbx# сохранить dest400544: callq 400550 <mult2> # вызвать mult2(x,y)# t в %rax400549: mov%rax,(%rbx)# сохранить по *dest•••long mult2(long a, long b){long s = a * b;return s;}0000000000400550 <mult2>:# a in %rdi, b in %rsi400550: mov%rdi,%rax400553: imul%rsi,%rax# s in %rax400557: retq# a# a * b# вернуть16Машинный уровень 3: Процедуры¢Процедуры x86-64§ Структура стека§ Соглашения вызова процедурПередача управления§ Передача данных§ Управление локальными данными§ Иллюстрация рекурсии§17Языки использующие стек¢Языки поддерживающие рекурсию§ например, Си, Паскаль, Ява§ код процедуры может быть реентерабельнымпригоден для следующего вызова, до завершения предыдущего§ есть отдельное место для хранения состояния каждого вызова§ Аргументы§ Локальные переменные§ Адрес возврата§¢Вызов процедур следует стековой дисциплине§ Состояние процедуры востребовано ограниченное времяот момента вызова до момента возврата§ Возврат из вызванной всегда раньше возврата из вызвавшей§¢Стек наполняется кадрами (frames)§ Стековый кадр – состояние одного запуска процедуры18Пример нескольких вызововyoo(…){••who();••}Примернаясхема вызововyoowho(…){• • •amI();• • •amI();• • •}whoamI(…){••amI();••}amIamIamIamIamI() - рекурсивная процедура19Стековые кадры¢КадрвызвавшейпроцедурыСодержимое§ Локальные переменные§ Информация для возврата§ Временное пространствоУказатель кадра: %rbp(если нужен)КадрвызваннойпроцедурыУказатель стека: %rsp¢Управление§ Место занимается при входе в процедурувершина стекаКод пролога§ Освобождается при выходе§ Код эпилога§20СтекПримерyooyoo(…){••who();••}%rbpyooyoowhoamI%rspamIamIamI21СтекПримерyooyoo(…){ who(…)•{• • • •amI();who();• • • •• amI();• • •}}yooyoowhoamI%rbpamI%rspwhoamIamI22СтекПримерyooyoo(…){ who(…)•{amI(…)• • • •{amI();who();•• • • ••• amI();• •amI();•}•}•}yooyoowhoamIwhoamI%rbpamI%rspamIamI23СтекПримерyooyoo(…){ who(…)•{amI(…)• • • •{amI();who();amI(…)•• • • {••• amI();•• •amI();••}•}• amI();•}•}yooyoowhoamIwhoamIamIamIamI%rbpamI%rsp24СтекПримерyooyoo(…){ who(…)•{amI(…)• • • •{amI();who();amI(…)•• • • {••• amI();• amI(…)• •amI();• •{}•}•amI();•• •}• amI();•}•}yooyoowhoamIwhoamIamIamIamIamI%rbpamI%rsp25СтекПримерyooyoo(…){ who(…)•{amI(…)• • • •{amI();who();amI(…)•• • • {••• amI();•• •amI();••}•}• amI();•}•}yooyoowhoamIwhoamIamIamIamI%rbpamI%rsp26СтекПримерyooyoo(…){ who(…)•{amI(…)• • • •{amI();who();•• • • ••• amI();• •amI();•}•}•}yooyoowhoamIwhoamI%rbpamI%rspamIamI27СтекПримерyooyoo(…){ who(…)•{• • • •amI();who();• • • •• amI();• • •}}yooyoowhoamI%rbpamI%rspwhoamIamI28СтекПримерyooyoo(…){ who(…)•{amI(…)• • • •{amI();who();•• • • ••• amI();• •amI();•}•}•}yooyoowhoamIwhoamI%rbpamI%rspamIamI29СтекПримерyooyoo(…){ who(…)•{• • • •amI();who();• • • •• amI();• • •}}yooyoowhoamI%rbpamI%rspwhoamIamI30СтекПримерyooyoo(…){••who();••}%rbpyooyoowhoamI%rspamIamIamI31Стековый кадр x86-64/Linux¢Текущий кадр(от вершины ко дну стека)§ Аргументы 7+ следующего вызова:Кадрвызвавшейпроцедурыпараметры вызываемой позже функции§ Локальные переменные(если не хватает регистров)Указатель кадра%rbp§ Сохранённые значения регистров§ Старое значение %rbp (если нужен)¢Кадр вызвавшей процедуры§ Адрес возвратаВтолкнут в стек командой call§ Аргументы 7+ вызова текущей§Указатель стека%rspАргументы 7+Адр.

возвратаСтарый %rbpСохранённыерегистры+ЛокальныепеременныеАргументыследующеговызова32Carnegie MellonПример: incrlong incr(long *p, long val) {long x = *p;long y = x + val;*p = y;return x;}incr:movqaddqmovqret(%rdi), %rax%rax, %rsi%rsi, (%rdi)РегистрИспользование%rdiАргумент p%rsiАргумент val, y%raxx, возвращаемое33Carnegie MellonПример: вызов incr 1Исходная структура стекаlong call_incr() {long v1 = 15213;long v2 = incr(&v1, 3000);return v1+v2;}call_incr:subq$16, %rspmovq$15213, 8(%rsp)movl$3000, %esileaq8(%rsp), %rdicallincraddq8(%rsp), %raxaddq$16, %rspret...Адр.возврата%rspНовая структура стека...Адр.возврата15213%rsp+8Не использ.%rsp34Carnegie MellonПример: вызов incr 2long call_incr() {long v1 = 15213;long v2 = incr(&v1, 3000);return v1+v2;}call_incr:subq$16, %rspmovq$15213, 8(%rsp)movl$3000, %esileaq8(%rsp), %rdicallincraddq8(%rsp), %raxaddq$16, %rspretСтруктура стека...Адр.возврата15213%rsp+8Не использ.%rspРегистрИспользование%rdi&v1%rsi300035Carnegie MellonПример: вызов incr 3long call_incr() {long v1 = 15213;long v2 = incr(&v1, 3000);return v1+v2;}call_incr:subq$16, %rspmovq$15213, 8(%rsp)movl$3000, %esileaq8(%rsp), %rdicallincraddq8(%rsp), %raxaddq$16, %rspretСтруктура стека...Адр.возврата18213%rsp+8Не использ.%rspРегистрИспользование%rdi&v1%rsi300036Carnegie MellonПример: вызов incr 4long call_incr() {long v1 = 15213;long v2 = incr(&v1, 3000);return v1+v2;}call_incr:subq$16, %rspmovq$15213, 8(%rsp)movl$3000, %esileaq8(%rsp), %rdicallincraddq8(%rsp), %raxaddq$16, %rspretСтруктура стека...Адр.возврата18213%rsp+8Не использ.%rspРегистрИспользование%raxВозвращаемоеСтруктура изменённого стека...Адр.возврата%rsp37Carnegie MellonПример: вызов incr 5long call_incr() {long v1 = 15213;long v2 = incr(&v1, 3000);return v1+v2;}call_incr:subq$16, %rspmovq$15213, 8(%rsp)movl$3000, %esileaq8(%rsp), %rdicallincraddq8(%rsp), %raxaddq$16, %rspretСтруктура изменённого стека...Адр.возврата%rspРегистрИспользование%raxВозвращаемоеФинальная структура стека...%rsp38Соглашения о сохранении регистров¢При вызове процедурой yoo процедуры who:§ yoo - вызывающая§ who - вызываемая¢Можно ли в регистрах временно хранить данные?yoo:• • •movl $15213, %rdxcall whoaddl %rdx, %rax• • •retwho:• • •subq $18213, %rdx• • •ret§ Данные yoo для регистра %rdx затираются данными who§ Требуется согласованное использование39Соглашения о сохранении регистров¢При вызове процедурой yoo процедуры who:§ yoo - вызывающая§ who - вызываемаяМожно ли в регистрах временно хранить данные?¢ Варианты соглашений¢§ “Сохраняет вызывающая”Вызывающая сохраняет временные значения в своём кадреперед вызовом§ “Сохраняет вызываемая”§ Вызываемая сохраняет временные значения в своём кадреперед началом использования§ Вызываемая восстанавливает временные значения из своего кадраперед возвратом§40Carnegie MellonИспользование регистров в x86-64 Linux 1¢%rax§ Возвращаемое значение§ Сохраняет вызывающая§ Вызываемая может менять¢%rdi, ..., %r9§ Arguments§ Сохраняет вызывающая§ Вызываемая может менять¢ВозвращаемоеАргументы%r10, %r11§ Сохраняет вызывающая§ Вызываемая может менятьСохраняемыевызывающейпромежуточные%rax%rdi%rsi%rdx%rcx%r8%r9%r10%r1141Carnegie MellonИспользование регистров в x86-64 Linux 2¢%rbx, %r12, %r13, %r14§ Вызываемая должна сохранить Сохраняемыеи восстановить¢%rbpвызываемойпромежуточные§ Вызываемая должна сохранитьи восстановить§ Может использоваться какуказатель кадра¢Специальные%rbx%r12%r13%r14%rbp%rsp%rsp§ Вызываемая должна сохранитьи восстановить специальнымобразом перед возвратом42Carnegie MellonПример сохранения вызываемой 1Исходная структура стекаlong call_incr2(long x) {long v1 = 15213;long v2 = incr(&v1, 3000);return x+v2;}call_incr2:pushq%rbxsubq$16, %rspmovq%rdi, %rbxmovq$15213, 8(%rsp)movl$3000, %esileaq8(%rsp), %rdicallincraddq%rbx, %raxaddq$16, %rsppopq%rbxret...Адрес возврата%rspНовая структура стека...Адрес возвратаСохранённый %rbx15213%rsp+8Не использован%rsp43Carnegie MellonПример сохранения вызываемой 2long call_incr2(long x) {long v1 = 15213;long v2 = incr(&v1, 3000);return x+v2;}Новая структура стека...Адрес возвратаcall_incr2:pushq%rbxsubq$16, %rspmovq%rdi, %rbxmovq$15213, 8(%rsp)movl$3000, %esileaq8(%rsp), %rdicallincraddq%rbx, %raxaddq$16, %rsppopq%rbxretСохранённый %rbx15213%rsp+8Не использован%rspСтруктура стека перед возвратом...Адрес возврата%rsp44Машинный уровень 3: Процедуры¢Процедуры х86-64§ Структура стека§ Соглашения вызова процедурПередача управления§ Передача данных§ Управление локальными данными§ Иллюстрация рекурсии§45Carnegie MellonРекурсивная функция/* Рекурсивный счётчик бит */long pcount_r(unsigned long x) {if (x == 0)return 0;elsereturn (x & 1)+ pcount_r(x >> 1);}pcount_r:movl$0, %eaxtestq%rdi, %rdije.L6pushq%rbxmovq%rdi, %rbxandl$1, %ebxshrq%rdicallpcount_raddq%rbx, %raxpopq%rbx.L6:rep; ret46Carnegie MellonНерекурсивный возврат/* Рекурсивный счётчик бит */long pcount_r(unsigned long x) {if (x == 0)return 0;elsereturn (x & 1)+ pcount_r(x >> 1);}РегистрИспользованиеКатегория%rdixАргумент%raxВозвращаемоеВозвращаемоеpcount_r:movl$0, %eaxtestq%rdi, %rdije.L6pushq%rbxmovq%rdi, %rbxandl$1, %ebxshrq%rdicallpcount_raddq%rbx, %raxpopq%rbx.L6:rep; ret47Carnegie MellonСохранение регистров/* Рекурсивный счётчик бит */long pcount_r(unsigned long x) {if (x == 0)return 0;elsereturn (x & 1)+ pcount_r(x >> 1);}РегистрИспользованиеКатегория%rdixАргументpcount_r:movl$0, %eaxtestq%rdi, %rdije.L6pushq%rbxmovq%rdi, %rbxandl$1, %ebxshrq%rdicallpcount_raddq%rbx, %raxpopq%rbx.L6:rep; ret...Адрес возвратаСохранённый %rbx%rsp48Carnegie MellonПодготовка вызова/* Рекурсивный счётчик бит */long pcount_r(unsigned long x) {if (x == 0)return 0;elsereturn (x & 1)+ pcount_r(x >> 1);}РегистрИспользованиеКатегория%rdix >> 1Рекурсивный арг.%rbxx & 1Сохр.вызываемаяpcount_r:movl$0, %eaxtestq%rdi, %rdije.L6pushq%rbxmovq%rdi, %rbxandl$1, %ebxshrq%rdicallpcount_raddq%rbx, %raxpopq%rbx.L6:rep; ret49Carnegie MellonРекурсивный вызов/* Рекурсивный счётчик бит */long pcount_r(unsigned long x) {if (x == 0)return 0;elsereturn (x & 1)+ pcount_r(x >> 1);}РегистрИспользованиеКатегория%rbxx & 1Сохр.вызываемая%raxРекурсивноевозвращаемоеpcount_r:movl$0, %eaxtestq%rdi, %rdije.L6pushq%rbxmovq%rdi, %rbxandl$1, %ebxshrq%rdicallpcount_raddq%rbx, %raxpopq%rbx.L6:rep; ret50Carnegie MellonРекурсивный учёт результата/* Рекурсивный счётчик бит */long pcount_r(unsigned long x) {if (x == 0)return 0;elsereturn (x & 1)+ pcount_r(x >> 1);}РегистрИспользованиеКатегория%rbxx & 1Сохр.вызываемая%raxВозвращаемоеpcount_r:movl$0, %eaxtestq%rdi, %rdije.L6pushq%rbxmovq%rdi, %rbxandl$1, %ebxshrq%rdicallpcount_raddq%rbx, %raxpopq%rbx.L6:rep; ret51Carnegie MellonРекурсивный возврат/* Рекурсивный счётчик бит */long pcount_r(unsigned long x) {if (x == 0)return 0;elsereturn (x & 1)+ pcount_r(x >> 1);}РегистрИспользованиеКатегория%raxВозвращаемоеВозвращаемоеpcount_r:movl$0, %eaxtestq%rdi, %rdije.L6pushq%rbxmovq%rdi, %rbxandl$1, %ebxshrq%rdicallpcount_raddq%rbx, %raxpopq%rbx.L6:rep; ret...%rsp52Важное o рекурсии¢Организуется без специальных мер§ Стековый кадр – каждому вызову функции отдельное хранилище§Сохранённые регистры и локальные переменные§Сохранённый адрес возврата§ Соглашение о сохранении регистров предотвращает повреждениеданных одного процедурного вызова другим§Пока Си-код не сделает это явно§ Схема вызовов/возвратов следует стековой дисциплине¢§Если P вызывает Q, то Q возвращает управление раньше, чем P§Последним вошёл, первым ушёл (LIFO)Также работает для взаимной рекурсии§ P вызывает Q, а Q вызывает P53Сводка: процедуры x86-64¢Важно!§ Стек – походящая структура данных дляКадрвызова процедур и возврата из нихвызвавшей§ если P вызывает Q, то возврат из Q раньшепроцедурычем из P¢(Взаимная) рекурсия реализуетсяобычными правилами вызова%rbp§ Значения безопасно хранятся в своём кадре иСохранённыерегистры+Локальныепеременныерегистрах сохраняемых вызванной§ Аргументы функции – на вершине стека§ Результат возвращается в %rax¢Аргументы7+Адр.

возвратаСтарый %rbpУказатели – адреса значений§ В стеке или среди глобальных переменных%rspАргументыследующеговызова54.