Телеграмм чат группы compilerdev страница 1460

parrot.ru

Рейтинг популярных групп и каналов

В рейтинге участвует:

групп:

каналов:

Виртуальный сервер на SSD - недорого!

Аренда выделенных и виртуальных серверов (VDS/VPS), хостинг, аренда IP-адресов, администрирование, круглосуточная поддержка

qwarta.ru подробнее

Резервное копирование с проверкой на вирусы!!!

Удобный сервис создания резервных копий на любой сервер сети интернет. Отслеживайте изменения, проверяйте на вирусы. Надежно защитите свой бизнес!

go.backupland.com

Выбираете сервер? Любая конфигурация на заказ!

Аренда физических серверов любых конфигураций под любые запросы - 1С бухгалтерия, игровые сервера, нагруженные проекты, интернет-магазины!

qwarta.ru подробнее

Size: a a a

Compiler Development

882 membersпожаловаться на группу

2020 June 18

I

Ilmir in Compiler Development

Разница в том, вызов какой функции мы заменяем. Если вызов себя, то это, очевидно, выгодно настолько, что мы делаем замену всегда, иначе надо считать, выгодно ли вызвать другую функцию или лучше прыгнуть. Во втором случае, ктсати, ещё регистры надо не забыть почистить (если мы не имеет доступа к телу функции, а ABI гарантирует, что эти регистры можно использовать для локальных переменных).

Хотя не, я чего-то путаю с другой оптимизацией. Регистры чистить не надо.

источник

18:42пожаловаться #1

PS

Peter Sovietov in Compiler Development

Разница в том, вызов какой функции мы заменяем. Если вызов себя, то это, очевидно, выгодно настолько, что мы делаем замену всегда, иначе надо считать, выгодно ли вызвать другую функцию или лучше прыгнуть. Во втором случае, ктсати, ещё регистры надо не забыть почистить (если мы не имеет доступа к телу функции, а ABI гарантирует, что эти регистры можно использовать для локальных переменных).

Да, но второй случай это уже не про хвостовую рекурсию.

источник

18:43пожаловаться #2

I

Ilmir in Compiler Development

Да, но второй случай это уже не про хвостовую рекурсию.

По это я и говорю. Эта оптимизация не про хвостовую рекурсию https://t.me/CompilerDev/68238

Peter Sovietov in Compiler Development

Интересный доклад, спасибо!

Но вот этот абзац вызывает сомнения:
«Tail Call тоже классическая оптимизация: минимизирует оверхед, который создается за счет создания стекового фрейма; преобразует call, который находится в конце функции, просто в инструкцию jump, то есть в передачу управления на следующую функцию. Оптимизация выполняется в бэкенде, потому что не для всех архитектур её возможно выполнить. Есть архитектуры, где адрес передачи управления инструкции jump кодируется в меньшее количество бит, чем call, и не все адреса в jump удается представить.»

источник

18:43пожаловаться #3

PS

Peter Sovietov in Compiler Development

По это я и говорю. Эта оптимизация не про хвостовую рекурсию https://t.me/CompilerDev/68238

Peter Sovietov in Compiler Development

Интересный доклад, спасибо!

Но вот этот абзац вызывает сомнения:
«Tail Call тоже классическая оптимизация: минимизирует оверхед, который создается за счет создания стекового фрейма; преобразует call, который находится в конце функции, просто в инструкцию jump, то есть в передачу управления на следующую функцию. Оптимизация выполняется в бэкенде, потому что не для всех архитектур её возможно выполнить. Есть архитектуры, где адрес передачи управления инструкции jump кодируется в меньшее количество бит, чем call, и не все адреса в jump удается представить.»

А, действительно! Спасибо, невнимательно я прочел.

источник

18:45пожаловаться #4

PS

Peter Sovietov in Compiler Development

Мне вот любопытно, а есть ли в природе системы команд (для процессоров или VM), в которых команда пролога функции определяет, откуда к ней обратились, из call или из jump, и далее ведет себя соответственно. В случае, jump, например, переиспользует текущий фрейм, а не создает новый.

Вот варианты команды tail_call (с удалением фрейма, как я предлагал выше) существуют. Например: https://github.com/WebAssembly/tail-call/blob/master/proposals/tail-call/Overview.md

Или: https://docs.microsoft.com/en-us/previous-versions/windows/silverlight/dotnet-windows-silverlight/56c08k0k(v=vs.95)?redirectedfrom=MSDN

источник

18:55пожаловаться #5

AT

Alexander Tchitchigi... in Compiler Development

Да, но второй случай это уже не про хвостовую рекурсию.

В "Tail Call Optimization" нет слова "рекурсия" — любой вызов функции, идущий последней инструкцией является хвостовым.

В чём принципиальная разница между рекурсивным и нерекурсивным случаями?

источник

19:28пожаловаться #6

PS

Peter Sovietov in Compiler Development

Alexander Tchitchigin

В "Tail Call Optimization" нет слова "рекурсия" — любой вызов функции, идущий последней инструкцией является хвостовым.

В чём принципиальная разница между рекурсивным и нерекурсивным случаями?

Вызов в духе call foo; ret достаточно легко распознать и заменить на jump foo. Для этого достаточно простого правила peephole-оптимизации.
А вот определение вызова хвостовой рекурсии — значительно более сложная задача.
Кроме того, при хвостовой рекурсии мы могли бы переиспользовать текущий фрейм.

источник

19:33пожаловаться #7

AT

Alexander Tchitchigi... in Compiler Development

Вызов в духе call foo; ret достаточно легко распознать и заменить на jump foo. Для этого достаточно простого правила peephole-оптимизации.
А вот определение вызова хвостовой рекурсии — значительно более сложная задача.
Кроме того, при хвостовой рекурсии мы могли бы переиспользовать текущий фрейм.

А как ещё хвостовая рекурсия может выглядеть?

Если у нас в calling convention стек чистит вызывающая функция перед возвратом, то вообще никакой проблемы нет — мы в любом случае его чистим, а там уже неважно чем он будет перезаполнен, тем же самым фреймом или новым. 🤷‍♀️

источник

19:36пожаловаться #8

PS

Peter Sovietov in Compiler Development

Alexander Tchitchigin

А как ещё хвостовая рекурсия может выглядеть?

Если у нас в calling convention стек чистит вызывающая функция перед возвратом, то вообще никакой проблемы нет — мы в любом случае его чистим, а там уже неважно чем он будет перезаполнен, тем же самым фреймом или новым. 🤷‍♀️

Иногда выгоднее не чистить стек полностью, а просто заменить точечно что-то во фрейме — и снова его использовать :)

Как может выглядеть хвостовая рекурсия? В рекурсивных функциях обязательно есть какое-то условие выхода из рекурсии. А где условие — там и jump :)

источник

19:39пожаловаться #9

AN

Alexander Nasonov in Compiler Development

Иногда выгоднее не чистить стек полностью, а просто заменить точечно что-то во фрейме — и снова его использовать :)

Как может выглядеть хвостовая рекурсия? В рекурсивных функциях обязательно есть какое-то условие выхода из рекурсии. А где условие — там и jump :)

Про jump, почти, но https://github.com/xoreaxeaxeax/movfuscator

xoreaxeaxeax/movfuscator

The single instruction C compiler. Contribute to xoreaxeaxeax/movfuscator development by creating an account on GitHub.

источник

19:47пожаловаться #10

PS

Peter Sovietov in Compiler Development

Давайте я приведу пример хвостовой рекурсии.

Предположим, мы компилируем следующую функцию:

(define gcd (m n)
    (if (= n 0)
        m
        (gcd n (mod m n))))

Очевидно, что вызов gcd здесь хвостовой. Теперь давайте получим промежуточное стековое представление. Причем, используем оптимизацию для if (поменяем if и else части местами, чтобы избежать лишней проверки):

Enter('gcd', ['m', 'n'])
Load('n')
Jump0(0)
Load('n')
Load('m')
Over()
Op('mod')
Call('gcd')
Jump(1)
Label(0)
Load('m')
Label(1)
Return()

Вот и проблема. Вызов оказался где-то в центре кода скомпилированной функции, а главное, за ним не следует Return.

А вот грамотный оптимизатор способен с этим справиться:

Enter('gcd', ['m', 'n'])
Load('n')
Jump0(0)
Load('n')
Load('m')
Over()
Op('mod')
TCall('gcd')
Label(0)
Load('m')
Return()

источник

19:52пожаловаться #11

K

Kir in Compiler Development

CPS-трансформация, вроде как, решает вопрос с хвоствой рекурсией на корню

источник

20:42пожаловаться #12

PS

Peter Sovietov in Compiler Development

Kir

CPS-трансформация, вроде как, решает вопрос с хвоствой рекурсией на корню

Если бы это было так, то в стандарте на ту же Scheme не отводили бы специальный раздел на правила оптимизации хвостовой рекурсии.

источник

21:56пожаловаться #13

D

Danya in Compiler Development

По поводу flex/bison
Можете посоветовать годные туториалы/книги?
Просто стандартная документация как-то meh, беглый поиск ничего хорошего мне не дал, а университетские методички, которые у меня есть слишком скудные..

источник

22:09пожаловаться #14

A

Alex in Compiler Development

Чего не хватает в университетских/обычной документации?

источник

22:10пожаловаться #15

D

Danya in Compiler Development

Простоты, что ли

источник

22:11пожаловаться #16

D

Danya in Compiler Development

Я конечно глубоко не вникал ещё

источник

22:11пожаловаться #17

D

Danya in Compiler Development

Но просто хочется потратить минимум времени, чтобы достичь максимум профита

источник

22:11пожаловаться #18

PS

Peter Sovietov in Compiler Development

По поводу flex/bison
Можете посоветовать годные туториалы/книги?
Просто стандартная документация как-то meh, беглый поиск ничего хорошего мне не дал, а университетские методички, которые у меня есть слишком скудные..

А Вы начните с решения конкретной простой задачи. Тогда и вопросы появятся по существу.

источник

22:11пожаловаться #19

A

Alex in Compiler Development

Но просто хочется потратить минимум времени, чтобы достичь максимум профита

)))))))))

источник

22:12пожаловаться #20